Введение в Алгебраическую теорию информации - Гоппа В.Д.
Скачать (прямая ссылка):
зависимости признаков. Метрика р(Х., А\) показывает, насколько далеки
признаки X. и X. от взаимной эквивалентности. В предельном случае, когда
р(Х., А\) = 0, существует функциональная зависимость в обе стороны:
xt - Хг Xj - X,..
Например, можно считать, что признаки
1 2
1 2
1 2
1 2
0 1
0 1
повторяют друг друга. Более глубокий кластерный анализ связан с понятием
условной независимости.
Скажем, что признак (слово) Z дублирует признак X относительно У, если
I0(Y: (X (r)Z)) = I0(Y:X).
Другими словами, если известен признак X, то добавление признака Z не
приносит новой информации относительно признака У. Очевидно, это
определение равносильно равенству
I0(Y/X (r) Z) = IQ(Y/X).
Естественно назвать при этом признаки У и Z условно независимыми при
условии X.
Это отношение симметрично, т. е. У и Z можно поменять местами:
IQ(Z/X (r) У) = I0(Z/X).
Доказательство тривиально:
10(Х (r) Z) + /0(У/X (r) Z) = I0(X <8> Z) + I0(Y/X),
I0(X(r)Z(r)Y)= IQ(X) + I0(Z/X) + Iq(Y/ X),
I0(X(r)Z(r)Y)= IQ(X (r)Y)+ IQ{Z/X),
IQ{X (r) Y) + I0(Z/X (r)Y) = IQ(X (r)Y)+ I0(Z/X),
I0(Z/X (r)Y) = I0(Z/X).
Отношение "Z дублирует признак X относительно У" мы будем обозначать
двойной стрелкой:
В частности, если имеет место функциональная зависимость
X -* Z,
то
i0(z/x) = о,
так что для любого У имеем
IQ(Z/X (r) Y) = 0.
Поэтому
X -*-* Z.
к
Приведем пример условно независимых признаков. Если X-тривиальное слово,
состоящее из одной буквы:
X (д, а, ..., а),
то понятие условной независимости совпадает с безусловной независимостью,
поскольку в этом случае
I0(Y/X) = I0(Y)
для любого слова У.
Поэтому мы можем строить условно независимые слова для произвольного
слова X, рассматривая его канонические подслова, полученные ограничением
на позиции, занятые одной и той же буквой:
X' Z' Г X" 7Г Г
а ь а ь а с
а ь Ь ь а d
а с а
а с Ь
Здесь Z' и Y' независимы, точно так же независимы Z" и У". Теперь
"склеиваем" эти слова:
X Z Y
а ь а
а ь b
а с а
а с b
Ь а с
Ь а d
В результате получаем условно независимые слова Y и Z.
Для фиксированного признака X рассмотрим множество S(A'), состоящее из
всех признаков, дублирующих X относительно У с точностью до е >0:
S(X) = {Z I I0(Y.(X <g> Z)) - I0(Y:X) < e}.
Это множество естественно назвать кластером, соответствующим признаку X.
Кластер состоит из признаков, сходных с признаком X по его способности
распознавать значение признака У, т. е. проводить классификацию.
Множество S(X) состоит из
39
всех признаков Z, для которых с некоторой погрешностью выполняется
зависимость
X -"- Z.
У
Все признаки из S(X) непригодны для образования сложного признака на
основе признака X.
2.4. Формирование сложных признаков
Обычно один отдельно взятый признак X. раскрывает лишь
частично неопределенность относительно признака У, поэтому приходится
рассматривать наборы признаков (сложные признаки).
В обозначениях главы 1 сложный признак U, составленный из простых
признаков X и 2,-это слово
и = X&Z.
Теорема 2.1. Если и Х2 независимы, то информативность сложного признака
Х1 (r) Х2 не меньше суммы
информативностей простых признаков, его составляющих. Более точно,
/0(У:(*, 0 Х2)) > /"(У:*,) + /0(У:*2) - 10{Хх:Х2).
Доказательство.
I0(Y:(Xl 0 Х2)) - Iq(Y) - IQ(Y/Xl 0 Х2),
iq(y/xx 0 х2) = i0(x1 (r)x2(r)Y)~ i0(x1 0 х2) =
= *о(х0 + *о(Х2 (r) Y/X0 - т - *о(Х2/Х0 =
= *о(У/Х0 + f0(X2/Xl (r)у)~ fo(X2/X0 =
= IQ(Y/X{) + fQ(X2) - IQ(X2/X{) - (fQ(X2) - I0(X2/X{ 0 Y)). Поскольку
TO
<"<>'/X, " ЛГ2) a V + V^V - W*|) - Vx2: y> -
так что
I0(Y:(Xi 0 X2)) > /"(И,) + /0(Х2:У) - /,(*,:*,).
Если признаки независимы, то I (Ху.Х^ = 0 и в этом случае получаем
I0{Y:{Xx 0 X,)) > /0(y:Xj) + /0(У:*2).
Если же признаки повторяют друг друга, то величина IQ(Xy.X^ становится
большой, а информативность сложного ^
40
признака оказывается такой же, что и информативность простого признака.
Поэтому при образовании сложного признака не следует объединять признаки,
лежащие в одном и том же кластере.
Введем второй параметр настройки /3, равный минимально допустимой
информативности сложного признака. Величина /3 колеблется обычно от 60 %
/0(У) до /Q(y). При выбранном
значении /3 найдем все сложные признаки, информативность которых
превышает /3.
Сначала находим все двойные признаки, удовлетворяющие этому
условию. В примере 2.1 при /3 = 80 % /0(У) =
= 0.8 • 14.26 = 11.4 сочетание достаточно информативно,
поэтому остается для дальнейшей обработки. Сочетание же Х2 <g> Х^ имеет
информативность, меньшую /3, поэтому добавляется третий признак
Тройной признак ' Х^ <8> <8> Х& имеет
уже достаточную информативность.
Для отобранных сложных признаков U и V выполняется условие
и <t.v, V фи.
Для каждого отобранного сложного признака составляем матрицу перехода
букв этого признака (слова) в буквы признака Y. Например, для Х^ <g>
X <8> в примере 2.1, если
заменить 1 -* 0, 2 -* 1, 3 -* 2, получаем
0 1 2 Сумма
100 1 1
110 1 1
100 1 1
011 2 2
010 1 1
001 2 2
