http://npc-news.ru/

Что же такое «лучший» элемент?

Лучшим элементом естественно считать такой элемент, на котором некоторая функция даёт лучшую оценку. Основное требование к такой функции — выбор элемента 0{ должен уве­личивать (по сравнению с исходной ситуацией) информацию о классах, помечающих обучающие выборки при разбиении рас­сматриваемого множества S на подмножества S\, So, . • •, Sn в со­ответствии с элементом 0{.

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

Пусть — вероятность того, что случайно взятый из Sj

пример есть С^. Она может быть оценена относительной часто­той

к

Пусть элемент oi расщепляет множество S примеров на подмно­жества Sj. Тогда энтропия семейства подмножеств Sj, порож­дённых значениями 0{, есть

H(S,ot) = YJP(SJ) xH(Sj),

j

где P(Sj) — вероятность принадлежности некоторого примера Sj и оценивается отношением мощностей подмножеств Sj к мощ­ности S:

т

\s\’

Увеличение информации при таком расщеплении происходит благодаря уменьшению энтропии:

IG(S,Ai) = H(S)-H(S,Oi),

где H(S) есть априорная (до расщепления) энтропия S.

Таким образом, алгоритм TDIDT выглядит следующим об­разом.

Использовать значение энтропии для поиска оптимального расщепления для каждого элемента.

Определить такой элемент, расщепление посредством ко­торого максимизирует энтропию при делении множества примеров на два подмножества.

Если критерий окончания не выполняется, повторить про­цедуру для каждого из подмножеств.


Комментарии закрыты.