Разбиение множества признаков на подмножества

Предыдущая 1 2 3 4 5 6 789 10 11 12 13 14 Следующая

Запишем матрицу парных информаций вида

Рассмотрим множество элементов столбца i, из которого исключен диагональный элемент. Максимальный элемент этого множества обозначим max J_i. Очевидно, он будет равен максимальной информации, даваемой о признаке і некоторым другим признаком. Образуем множество признаков S, для которых действительно неравенство max J_i ≥ к Н(Xi); 0 < к ≤ 1 едино

для всех признаков и выбирается произвольно.

Требования на М и N следующие:

1. Для любого признака из М должен существовать хотя бы один признак из N, такой, что . Очевидно, что при таком условии

2. Количество признаков множества N должно быть минимальным.

3. Должно выполняться равенство .

М и N удобнее искать на графах парных информаций.

Введем множества , для элементов которого действительно неравенство

; (1)

Для Х_α, неравенство (1) очевидно, так как

Правила построения графов парных информаций:

1. Для столбца 1 матрицы J выделяются Т(1). Если Т(1)≡Х, . то делается шаг 2, иначе признаки изображаются вершинами графа от вершин признаков проводятся дуги к вершине признака Х1.

2. На S + 1 шаге для столбца S + 1 матрицы J выделяются T⁽^S⁺¹⁾. Если T⁽^S⁺¹⁾≡Х_S₊₁, то делается шаг S + 2, иначе признаки, вошедшие в , изображаются вершинами графа и от вершин признаков, вошедших в проводятся дуги к вершине признака Х_S₊₁.

3. Построение графа кончается на шаге.

Пример. На рис. 1 дана матрица J. На главной диагонали-энтропии признаков. Используя значения энтропий и к =0.8, получаем, что S={Х₁, Х₂, Х₃, Х₄, Х₅, Х₆, Х₇, Х₈};

Т⁽¹⁾ = {X₁}; Т⁽²⁾ = {X₁, X₂}; Т⁽³⁾ = {X₁, X₄, X₃}; Т⁽⁴⁾ = {X₁, X₃, X₅, X₄}; Т⁽⁵⁾ = {Х₃, Х₇, Х₅}; Т⁽⁶⁾ = { Х₄, Х₆}; Т⁽⁷⁾ = {Х₅, Х₇}; Т⁽⁸⁾ = {Х₄, Х₈}; Т⁽⁹⁾ = {Х₉}.

Строится граф с использованием найденных T⁽ⁱ⁾ (i = 1,2,…,9) (см. рис.2).

На графе выбраны множества N = {X₁, X₂, X₃} и M = {X₂, X₃, X₆, X₇, X₈}. Однако выбор не единствен, так как возможны N = {X₁, X₄, X₇} и M = {X₂, X₃, X₅, X₄, X₈}.

Объединение подмножества множества α

После исключения из α пустых подмножеств и перенумерации получим . После исключения из rq градаций, соответствующих пустым подмножествам α, и перенумерации получим и .

Пусть пройдено S шагов объединения и делается S + 1 шаг. На шаге S вычислена матрица вида

Рис.3.

Здесь – разностное информационное отношение для подмножеств и из , где α_s = d₁ – S.

1. В Q⁽^s⁾, исключая диагональные элементы, находится минимальный элемент и соответствующие ему подмножества объединяются. После перенумерации получаем .

2. Вычисляется величина , где информация признака о признаке X_z

на шаге S + 1, а – их совместная энтропия.

3. Если R(s) < R(s+1) то для множества α(s+1) вычисляется матрица Q⁽^s⁺¹⁾ и делается шаг S+2, иначе объединение должно быть прекращено на шаге S.

Выведем некоторые свойства, необходимые для алгоритма объединения. Обозначим минимальный элемент Q⁽^s⁾, найденный по пункту 1, как . Понадобятся следующие равенства:

(1)

(2)

(3)

(4)

Здесь — потеря информации; — потеря энтропии; — потеря совместной энтропии; и — признаки при объединении наиболее одинаковых по элементов из α. Введем обозначение

4. Если , то ;

Если , ;

Если ,

Докажем только первое утверждение.

Из (1) и (3) следует, что равносильно или

Используя (4) и равенство , получим

5. Если и , то , т.е.

Если покажем, что то утверждение будет доказано. Используя (1) и (2), получим

После несложного преобразования это неравенство переходит в первое условие.

6. Если и , то , т.е.

Доказывается аналогично свойству 5.

7. Если на первом шаге объединения и на каждом шаге объединения выполняется неравенство , то

; ; ; ; ; ; ; .

Очевидно, что и . Найдем . , и следовательно .

Напишем матрицу вида

Из Q⁽¹⁾ видно, что подмножества объектов и наиболее близки друг к другу по Х_z, так как элемент матрицы Q⁽¹⁾ минимален среди недиагональных элементов.

Объединим подмножества и . Получим признак с множеством градаций . Здесь – градация, полученная в результате объединения и . Нетрудно получить: ; ; ; ; ; ; ; ; ; ; ;

Составим матрицу

Так как элемент матрицы Q⁽²⁾ минимален среди недиагональных элементов, то объединим подмножества объектов α⁽⁴⁾ и α⁽³⁾. Получим признак с множеством градаций . Не трудно подсчитать, что ; ; ; ; ; ; ; ; .

Если объединить последние две градации в Х⁽³⁾, то получим признак с одной градацией. В этом случае ; и

График как функции S представлен на рис. 4 и имеет тот же вид, что и на рис. 3. Это понятно, так как .

Очевидно, что при S = 3 следует прекратить объединение подмножеств объектов. Выпишем для иллюстрации распределения условных вероятностей до и после объединения.

До объединения:

; ; ; ; ; ; ; ;

После объединения:

; ; ; .

Дополним список свойств разностного информационного отношения.

1. Если множество объектов α_i одинаково по X_z с множествами α_j и α_k, то множества объектов α_j и α_k одинаковы по X_z.

Если Q_ij(X_q,X_z) = Q_ik(X_q,X_z) = 0, то Q_jk(X_q,X_z) = 0.

На основании свойства 4 пишем, что

; l = 1,2,…,t_z;

, откуда , т.е. . В частности, отсюда следует, что если, α_i – непустое множество и строка (столбец) i в матрице Q⁽^s⁾ нулевая, то матрица Q⁽^s⁾ будет нулевой матрицей.

Следующее ниже свойство 2 означает, что если в М есть признак, не зависящий от множества признаков , то при объединении конечных групп в классы он будет игнорироваться.