28. Деревья принятия решений.

Индуктивный логический вывод деревьев решений представляет собой одну из простейших и вместе с тем наиболее успешных форм алгоритмов обучения. Дерево решений принимает в качестве входных данных объект или ситуацию, описанную с помощью множества атрибутов, и возвращает “решение” — пред­сказанное выходное значение, соответствующее входным данным. Входные атрибу­ты могут быть дискретными или непрерывными. Выходные значения также могут быть дискретными или непрерывными; процесс формирования в ходе обучения функции с дискретными значениями называется обучением классификации; формирование в ходе обучения непрерывной функции называется обучением регрессии. Вначале мы сосредоточимся на булевой классификации, согласно ко­торой каждый пример обозначается как истинный (положительный) или ложный (отрицательный).

Дерево решений позволяет перейти к содержащемуся в нем решению путем вы­полнения последовательности проверок. Каждый внутренний узел в дереве соответ­ствует проверке значения одного из свойств, а ветви, исходящие из этого узла, обо­значены возможными значениями результатов проверки. Каждый листовой узел в дереве задает значение, возвращаемое после достижения этого листа.

Например: клиент ждет, пока освободится место за столиком в ресторане. Цель состоит в том, чтобы изучить определение для целевого предиката WillWait (Следует ли ждать). Используем следующие атрибуты:

• AIternate (Альтернативный вариант). Есть ли поблизости подходящий рес­торан такого же класса.

• Ваr (Бар). Имеется ли в ресторане уютный бар, в котором можно подождать.

• Fri /Sat (Уик-энд). Принимает истинное значение по пятницам и субботам.

• Hungry (Чувство голода). Испытывает ли посетитель чувство голода.

• Patrons (Посетители). Сколько людей находится в ресторане; значениями этого атрибута являются None (Ресторан пуст), Some (В ресторане есть посе­тители) и Full (Ресторан заполнен).

• Price (Цены). Ценовая категория ресторана (*, **, ***).

• Raining (Дождь). Идет ли дождь на улице.

• Reservation (Бронирование). Забронировано ли место за посетителем.

• Туре (Тип). Тип ресторана (ресторан с французской (French), итальянской (Italian), тайской (Thai) кухней или ресторан-закусочная (Burger)).

• WaitEstimate (Оценка продолжительности ожидания). Продолжитель­ность ожидания, оценка которой сделана метрдотелем (0-10, 10-30, 30-60, >60 минут).

Выразительность деревьев решений

С точки зрения логики любая конкретная гипотеза из дерева решений для целевого предиката WillWait может рассматриваться как утверждение в следующей форме:

где каждое условие P_i(s) представляет собой конъюнкцию проверок, соответст­вующих пути от корня дерева к листу с положительным результатом. Деревья решений в рамках класса пропозициональных языков являются полно­стью выразительными; это означает, что в виде дерева решений может быть оформ­лена любая булева функция.

Деревья решений вполне подходят для функций одних типов и не подходят для других(для мажоритарной функции,для функции определения четности)