Иллюстрированный самоучитель по введению в экспертные системы



              

Алгоритм формирования дереврешений по обучающей выборке - часть 3


После того как соответствующая тестирующая процедура Т выполнит разделение S на подмножества {S1, S2, ..., Sn}, энтропия будет определяться соотношением

Uт(S) = -Sumi=1,...k(|S|/|Si|)х U(Si).

Полученная оценка говорит нам, сколько информации еще необходимо после того, как выполнено разделение. Оценка формируется как сумма неопределенностей сформированных подмножеств, взвешенная в пропорции размеров этих подмножеств.

Из этих рассуждений очевидно следует эвристика выбора очередного атрибута для тестирования, используемая в алгоритме, — нужно выбрать тот атрибут, который сулит наибольший прирост информации. Прирост информации GS(T) после выполнения процедуры тестирования Т по отношению к множеству 5 равен

GS(7)=U(S)-Uт(S).

Такую эвристику иногда называют "минимизацией энтропии", поскольку увеличивая прирост информации на каждом последующем тестировании, алгоритм тем самым уменьшает энтропию или меру беспорядка в множестве.

Вернемся теперь к нашему примеру с погодой и посмотрим, как эти формулы интерпретируются в самом простом случае, когда множество целевых классов включает всего два элемента. Пусть р — это количество объектов класса П в множестве обучающей выборки S, а п — количество объектов класса Н в этом же множестве. Таким образом, произвольный объект принадлежит к классу П с вероятностью p / (p + п), а к классу Н с вероятностью n /(p + п). Ожидаемое количество информации в множестве сообщений М = {П, Н} равно

U(M) = -p / (p + п) log2(p/(p + n )) -

n / (p + n) 1оg2(n/(р + п))

Пусть тестирующая процедура Т, как и ранее, разделяет множество S на подмножества {S1, S2.....Sn}, и предположим, что каждый компонент S, содержит pi, объектов класса

П и и, объектов класса Н. Тогда энтропия каждого подмножества Si будет равна

U(Si) = -рi/(рi + ni) log2(pi/(pi + ni)) -

n/(рi + ni) log2(ni/(pi +ni))

Ожидаемое количество информации в той части дерева, которая включает корневой узел, можно представить в виде взвешенной суммы:

Uт(S) = -Sumi=1,...n((pi, + ni)/(р + n)) х U(Si) Отношение (р, + п,)/(р + п) соответствует весу каждой i-и ветви дерева, вроде того, которое показано на рис. 20.3.


Содержание  Назад  Вперед