На рисунке 27 изображена задача «ирисы Фишера», предполагающая классификацию на 3 класса, линейными классификаторами ее решить невозможно, нелинейные будут избыточны из-за малого количества признаков. Но с этой задачей справятся деревья решений (decision trees), которые последовательно применяют решающие правила (предикаты).
Рисунок 27. Задача «ирисы Фишера»
Дерево решений – способ представления правил в иерархической, последовательной структуре, где каждому объекту соответствует единственный узел, дающий решение. В результате формируется покрывающий набор конъюнкций.
Каждый узел дерева содержит признак, ребра – значения признака, листы – метки классов, пример такого дерева показан на рисунке 27 справа. Классы должны быть дискретными. Каждый пример должен однозначно относиться к одному из классов. Справа показаны решающие поверхности, порожденные деревом решений.
C4.5 [45] – алгоритм построения дерева решений, количество потомков у узла не ограничено. Решает только задачи классификации. В нем есть важное требование: количество классов должно быть значительно меньше количества записей в исследуемом наборе данных.
Пусть – множество примеров, где каждый элемент описывается атрибутами, - метка класса
Процесс построения дерева будет происходить итеративно сверху вниз.
На первом шаге мы имеем пустое дерево (имеется только корень) и исходное множество (ассоциированное с корнем). Требуется разбить исходное множество на подмножества. Делается через выбор одного из атрибутов в качестве проверки.
Тогда в результате разбиения получаются (по числу значений атрибута) подмножеств и, соответственно, создаются потомков корня, каждому из которых поставлено в соответствие свое подмножество, полученное при разбиении множества .
В процессе построения любого дерева решений необходимо выбрать критерий разбиения (в случае C4.5 это прирост информации), правило остановки (при небольшой выборке дерево строят до ее исчерпания, при большой – применяют отсечение).
Отсечение ветвей (pruning) - эвристический метод. Идем от листов к корню, помечая по некоторому критерию, например качество классификации, узлы на удаление. Вместо узлов ставится лист с меткой класса с наибольшим количеством исходов в этом поддереве.
Критерий разбиения
Пусть мы имеем проверку (в качестве проверки может быть выбран любой атрибут), которая принимает значений . Тогда разбиение по проверке даст нам подмножества , при равном соответственно . – количество примеров из множества , относящихся к классу .
Оценка среднего количества информации, необходимого для определения класса примера из множества (энтропия):