Индуктивный вывод деревьев решений на основе примеров
Пример для булева дерева решений состоит из вектора входных атрибутов X и одного булева выходного значения у. Множество примеров (Х1гу1) (X12fyi2) показано в табл. 18.1. Положительными примерами являются те, в которых цель WillWait имеет истинное значение (х1, Хъ,...), а отрицательными — те, в которых эта цель имеет ложное значение (Х2, Хъ,...). Полное множество примеров называется обучающим множеством.
Проблема поиска дерева решений, которое согласуется с обучающим множеством, на первый взгляд может показаться сложной, но фактически имеет простейшее решение. Можно просто сформировать дерево решений, в котором имеется по одному пути к листовому узлу для каждого примера, где в пути проверяется каждый атрибут по очереди и происходит переход к значению для данного примера, а листовой узел содержит классификацию для данного примера. После повторного поступления того же примера3 дерево решений обеспечивает правильную классификацию. Но, к сожалению, оно не позволяет учесть какие-либо иные случаи!
Недостатком такого простейшего дерева решений является то, что в нем просто запоминаются результаты наблюдений. Оно не позволяет извлечь какие-либо закономерности из примеров, поэтому нельзя надеяться на то, что оно даст возможность экстраполировать примеры, которые еще не встречались. Применяя принцип бритвы Оккама, необходимо вместо этого найти наименьшее дерево решений, совместимое с рассматриваемым примером. К сожалению, применительно к любому обоснованному определению понятия "наименьший" задача поиска наименьшего дерева является трудноразрешимой. Однако с помощью некоторой простой эвристики можно многого достичь в направлении поиска "меньшего" дерева. Основная идея, лежащая в основе алгоритма Decision-Tree-Learning, состоит в том, что в первую очередь следует проверять наиболее важный атрибут. Под "наиболее важным" атрибутом подразумевается такой атрибут, который вносит наибольшее различие в классификацию примера. Таким образом, можно рассчитывать на обеспечение правильной классификации с помощью небольшого количества проверок, а это означает, что все пути в дереве будут короткими, а само дерево в целом окажется небольшим.
На рис. 18.3 показано, как начинается работа алгоритма. Ему предъявляются 12 обучающих примеров, которые классифицированы на множества положительных и отрицательных примеров. После этого принимается решение о том, какой атрибут должен использоваться для первой проверки дерева. На рис. 18.3, а показано, что Туре — неподходящий атрибут, поскольку после его проверки остаются четыре возможных результата, каждый из которых содержит одинаковое количество положительных и отрицательных примеров. С другой стороны, на рис. 18.3, б можно видеть, что Patrons — довольно важный атрибут, поскольку если его значение равно None или Some, то остаются такие множества примеров, для которых можно сразу же получить определенный ответ (No и Yes соответственно). А если значением является Full, то остается смешанное множество примеров. Вообще говоря, после того, как проверка первого атрибута разбивает множество примеров на подмножества, каждый результат сам становится определением новой задачи обучения дерева решений с меньшим количеством примеров и количеством атрибутов, сократившимся на единицу. Ниже описаны четыре случая, которые следует рассматривать при анализе подобных рекурсивных задач.
1. Если имеются некоторые положительные и отрицательные примеры, то следует выбрать наилучший атрибут для выполнения по нему разбиения. Как показано на рис. 18.3,5, для разбиения оставшихся примеров используется атрибут Hungry.
2. Если все оставшиеся примеры являются положительными (или отрицательными), то работа закончена и можно дать ответ Yes или No. На рис. 18.3, б показаны примеры достижения этой цели в случаях None и Some.
3. Если не осталось ни одного примера, это означает, что соответствующие примеры не наблюдались, поэтому следует возвратить применяемое по умолчанию значение, вычисленное на основании мажоритарной классификации в родительском узле данного узла.
4. Если не осталось ни одного атрибута, но имеются и положительные и отрицательные примеры, то налицо проблема. Такая ситуация означает, что данные примеры имеют полностью одинаковое описание, но классифицированы по
1.
разному. Такое происходит, если некоторые данные определены неправильно; принято говорить, что в данных присутствует шум. Кроме того, такое происходит, либо если атрибуты не предоставляют достаточной информации для полного описания ситуации, либо если данная проблемная область действительно является недетерминированной. Одним из простых способов преодоления такой проблемы является использование мажоритарного голосования.
Алгоритм Decision-Tree-Learning показан в листинге 18.1. Подробные сведения о методе Choose-Attribute приведены в следующем подразделе.
Листинг 18.1. Алгоритм обучения дерева решений
function Decision-Tree-Learning(examples,attribs,default) returns дерево решений
inputs: examples, множество примеров attribs, множество атрибутов
default, заданное по умолчанию значение для целевого предиката
if множеств examples пусто then return default
else if все примеры имеют одну и ту же классификацию
then return классификация else if множество attribs пусто then return Majority-Value(examples)
Окончательное дерево решений, полученное с помощью этого алгоритма после применения к набору данных с 12 примерами, показано на рис. 18.4. Очевидно, что указанное дерево отличается от исходного дерева, показанного на рис. 18.2, несмотря на тот факт, что обучающие данные в действительности были сформированы агентом, использовавшим исходное дерево. Можно было бы прийти к заключению, что этот обучающий алгоритм не очень хорошо справляется с задачей изучения правильной функции. Однако такое заключение далеко от истины. В обучающем алгоритме рассматриваются примеры, а не правильная функция, и на самом деле сформированная в нем гипотеза (см. рис. 18.4) не только согласуется со всеми примерами, но и значительно проще по сравнению с первоначальным деревом. В процессе работы обучающего алгоритма не было обнаружено причин для включения проверок значений атрибутов Raining и Reservation, поскольку алгоритм мог классифицировать все примеры без них. Кроме того, алгоритм обнаружил интересный и ранее не наблюдавшийся шаблон поведения: первый автор, указанный на обложке данной книги, готов ждать, чтобы поесть тайской пищи по уик-эндам.
Безусловно, если бы было собрано больше примеров, то вполне возможно, что сформированное дерево в большей степени напоминало бы исходное. К тому же дерево, приведенное на рис. 18.4, способно выработать ошибочное решение, например, при его формировании никогда не встречался случай, в котором требовалось ждать от 0 до 10 минут, а ресторан был полон. На ту ситуацию, в которой атрибут Hungry имеет ложное значение, дерево сообщает, что ждать не следует, тогда как сам автор (Стюарт Рассел), безусловно, стал бы ждать. Исходя из этого, возникает очевидный вопрос: если алгоритм выводит на основании примеров согласованное, но неправильное дерево, то насколько неправильным может вообще оказаться это ерево? Ниже, после рассмотрения подробных сведений об этапе выбора атрибутов, будет показано, как проводить экспериментальный анализ этого вопроса.