Лучшим элементом естественно считать такой элемент, на котором некоторая функция даёт лучшую оценку. Основное требование к такой функции — выбор элемента 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'
Увеличение информации при таком расщеплении происходит благодаря уменьшению энтропии:
где H(S) есть априорная (до расщепления) энтропия S.
Таким образом, алгоритм TDIDT выглядит следующим образом.
Использовать значение энтропии для поиска оптимального расщепления для каждого элемента.
Определить такой элемент, расщепление посредством которого максимизирует энтропию при делении множества примеров на два подмножества.
Если критерий окончания не выполняется, повторить процедуру для каждого из подмножеств.