Объединение подмножества множества α
После
исключения из α пустых подмножеств и
перенумерации получим
.
После исключения из rq градаций,
соответствующих пустым подмножествам
α, и перенумерации получим
и
.
Пусть пройдено S шагов объединения и делается S + 1 шаг. На шаге S вычислена матрица вида
Рис.3.
Здесь
– разностное информационное отношение
для подмножеств
и
из
,
где αs
= d1
– S.
1.
В Q(s),
исключая диагональные элементы, находится
минимальный элемент и соответствующие
ему подмножества объединяются. После
перенумерации получаем
.
2.
Вычисляется величина
,
где
информация признака
о признаке Xz
98
на
шаге S
+ 1, а
– их совместная энтропия.
3. Если R(s) < R(s+1) то для множества α(s+1) вычисляется матрица Q(s+1) и делается шаг S+2, иначе объединение должно быть прекращено на шаге S.
Выведем
некоторые свойства, необходимые для
алгоритма объединения. Обозначим
минимальный элемент Q(s),
найденный по пункту 1, как
.
Понадобятся следующие равенства:
(1)
(2)
(3)
(4)
Здесь
— потеря информации;
— потеря энтропии;
— потеря совместной энтропии;
и
— признаки при объединении наиболее
одинаковых по
элементов из α. Введем обозначение
4.
Если
,
то
;
Если
,
;
Если
,
Докажем только первое утверждение.
99
Из
(1) и (3) следует, что
равносильно
или
Используя
(4) и равенство
,
получим
5.
Если
и
,
то
,
т.е.
Если
покажем, что
то утверждение будет доказано. Используя
(1) и (2), получим
После несложного преобразования это неравенство переходит в первое условие.
6.
Если
и
,
то
,
т.е.
Доказывается аналогично свойству 5.
7.
Если на первом шаге объединения
и на каждом шаге объединения выполняется
неравенство
,
то
100
;
;
;
;
;
;
;
.
Очевидно,
что
и
.
Найдем
.
,
и следовательно
.
Напишем матрицу вида
Из
Q(1)
видно, что подмножества объектов
и
наиболее близки друг к другу по Хz,
так как элемент
матрицы Q(1)
минимален среди недиагональных элементов.
Объединим
подмножества
и
.
Получим признак
с множеством градаций
.
Здесь
– градация, полученная в результате
объединения
и
.
Нетрудно получить:
;
;
;
;
;
;
;
;
;
;
;
101
Составим матрицу
Так
как элемент
матрицы Q(2)
минимален среди недиагональных элементов,
то объединим подмножества объектов
α(4)
и α(3).
Получим признак
с множеством градаций
.
Не трудно подсчитать, что
;
;
;
;
;
;
;
;
.
Если
объединить последние две градации в
Х(3),
то получим признак
с одной градацией. В этом случае
;
и
График
как функции S
представлен на рис. 4 и имеет тот же вид,
что и на рис. 3. Это понятно, так как
.
102
Очевидно, что при S = 3 следует прекратить объединение подмножеств объектов. Выпишем для иллюстрации распределения условных вероятностей до и после объединения.
До объединения:
;
;
;
;
;
;
;
;
После объединения:
;
;
;
.
Дополним список свойств разностного информационного отношения.
1. Если множество объектов αi одинаково по Xz с множествами αj и αk, то множества объектов αj и αk одинаковы по Xz.
Если Qij(Xq,Xz) = Qik(Xq,Xz) = 0, то Qjk(Xq,Xz) = 0.
На основании свойства 4 пишем, что
;
l
= 1,2,…,tz;
,
откуда
,
т.е.
.
В частности, отсюда следует, что если,
αi
– непустое множество и строка (столбец)
i
в матрице Q(s)
нулевая, то матрица Q(s)
будет нулевой матрицей.
Следующее
ниже свойство 2 означает, что если в М
есть признак, не зависящий от множества
признаков
,
то при объединении конечных групп в
классы он будет игнорироваться.
Выделим
из М
признак Хψ
и образуем множество Мψ
, которое есть М
без Хψ
и имеет эквивалентный
.
103
2. Если признак Хψ независим от эквивалентного признака множества , то
(5)
Пусть
и Хψ
имеют множества градаций
и
,
где
и
– количества градаций по признакам
и Хψ
соответственно. Достаточно показать,
что
.
Из
независимости Хψ
от
следует, что
,
Подставляя
последнее в формулу для
,
получим требуемое равенство (10).
Выделим
из множества F
признаков N
признак Хψ
и образуем Nφ,
которое есть N
без Хφ.
Эквивалентный признак Nφ
назовем
.
Введем
и
.
104
Рассмотрим
множества объектов αij
и αik,
которые по
попадают в одну градацию
,
а по признаку Хφ,
попадают в градации
и
соответственно.
3.
Если признак Хφ
независим от эквивалентного признака
множества признаков
,
то
для j,k
= 1,2,…,tφ
(6)
Из
независимости Хφ
от
,
следует, что
,
т.е. что
Найдем,
что
;
;
т.е. равенство (6) доказано.
105