Алгоритм построения новых ветвей.

Пусть S — полное множество примеров (экземпляров) из некоторого класса эквивалентности. Далее операторы о из множества О будем называть элементами (примеров).

Шаг 1. Выполнить поиск «лучшего» элемента од

Шаг 2.

Шаг 3. Для каждого множества Sj, если все примеры в Sj принадлежат одному и тому же классу (имеющему ту же метку класса), создать лист дерева решений и пометить меткой этого класса. Иначе перейти к 1, положив S = Sj. Алгоритм заканчивает работу, когда все подмножества помечены, либо отсутствуют элементы, разделяющие непомеченные множества.

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

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

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

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

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

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

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