Главная arrow книги arrow Копия Глава 18. Обучение на основе наблюдений arrow Индуктивный вывод деревьев решений на основе примеров
Индуктивный вывод деревьев решений на основе примеров

Пример для булева дерева решений состоит из вектора входных атрибутов X и одного булева выходного значения у. Множество примеров показано в табл. 18.1. Положительными примерами являются те, в которых цель WillWait имеет истинное значение, а отрицательными — те, в которых эта цель имеет ложное значение. Полное множество примеров называется обучающим множеством.

Таблица 18.1. Примеры для проблемной области задачи с рестораном

Проблема поиска дерева решений, которое согласуется с обучающим множеством, на первый взгляд может показаться сложной, но фактически имеет простейшее решение. Можно просто сформировать дерево решений, в котором имеется по одному пути к листовому узлу для каждого примера, где в пути проверяется каждый атрибут по очереди и происходит переход к значению для данного примера, а листовой узел содержит классификацию для данного примера. После повторного поступления того же примера дерево решений обеспечивает правильную классификацию. Но, к сожалению, оно не позволяет учесть какие-либо иные случаи!

Недостатком такого простейшего дерева решений является то, что в нем просто запоминаются результаты наблюдений. Оно не позволяет извлечь какие-либо закономерности из примеров, поэтому нельзя надеяться на то, что оно даст возможность экстраполировать примеры, которые еще не встречались. Применяя принцип бритвы Оккама, необходимо вместо этого найти наименьшее дерево решений, совместимое с рассматриваемым примером. К сожалению, применительно к любому обоснованному определению понятия "наименьший" задача поиска наименьшего дерева является трудноразрешимой. Однако с помощью некоторой простой эвристики можно многого достичь в направлении поиска "меньшего" дерева. Основная идея, лежащая в основе алгоритма Decision-Tree-Learning, состоит в том, что в первую очередь следует проверять наиболее важный атрибут. Под "наиболее важным" атрибутом подразумевается такой атрибут, который вносит наибольшее различие в классификацию примера. Таким образом, можно рассчитывать на обеспечение правильной классификации с помощью небольшого количества проверок, а это означает, что все пути в дереве будут короткими, а само дерево в целом окажется небольшим.