20.3.1. Структура дерева решений
Дерево решений представляет один из способов разбиения множества данных на классы или категории. Корень дерева неявно содержит все классифицируемые данные, а листья — определенные классы после выполнения классификации. Промежуточные узлы дерева представляют пункты принятия решения о выборе или выполнения тестирующих процедур с атрибутами элементов данных, которые служат для дальнейшего разделения данных в этом узле.
В работе [Quinlan, 1993] дерево решений определено как структура, которая состоит из
- узлов-листьев, каждый из которых представляет определенный класс;
- узлов принятия решений, специфицирующих определенные тестовые процедуры, которые должны быть выполнены по отношению к одному из значений атрибутов; из узла принятия решений выходят ветви, количество которых соответствует количеству возможных исходов тестирующей процедуры.
На этом дереве промежуточные узлы представляют атрибуты наблюдение, влажность, ветрено. Листья дерева промаркированы одним из двух классов П или Н. Можно считать, что П соответствует классу позитивных экземпляров концепта, а Н — классу негативных. Например, П может представлять класс "выйти на прогулку", а Н — класс "сидеть дома".
Хотя очевидно, что дерево решений является способом представления, отличным от порождающих правил, дереву можно сопоставить определенное правило классификации, которое дает для каждого объекта, обладающего соответствующим набором атрибутов (он представлен множеством промежуточных узлов дерева), решение, к какому из классов отнести этот объект (набор классов представлен множеством значений листьев дерева). В приведенном примере правило будет относить объекты к классу П или Н. Можно прямо транслировать дерево в правило, показанное ниже:
если наблюдение = облачно
v
наблюдение = солнечно &
влажность = нормально
v
наблюдение = дождливо &
ветрено = нет то П
