Алгоритм Decision-Tree-Learning показан в листинге 18.1. Подробные сведения о методе Choose-Attribute приведены в следующем подразделе.

Листинг 18.1. Алгоритм обучения дерева решений

Окончательное дерево решений, полученное с помощью этого алгоритма после применения к набору данных с 12 примерами, показано на рис. 18.4. Очевидно, что указанное дерево отличается от исходного дерева, показанного на рис. 18.2, несмотря на тот факт, что обучающие данные в действительности были сформированы агентом, использовавшим исходное дерево. Можно было бы прийти к заключению, что этот обучающий алгоритм не очень хорошо справляется с задачей изучения правильной функции. Однако такое заключение далеко от истины. В обучающем алгоритме рассматриваются примеры, а не правильная функция, и на самом деле сформированная в нем гипотеза (см. рис. 18.4) не только согласуется со всеми примерами, но и значительно проще по сравнению с первоначальным деревом. В процессе работы обучающего алгоритма не было обнаружено причин для включения проверок значений атрибутов Raining и Reservation, поскольку алгоритм мог классифицировать все примеры без них. Кроме того, алгоритм обнаружил интересный и ранее не наблюдавшийся шаблон поведения: первый автор, указанный на обложке данной книги, готов ждать, чтобы поесть тайской пищи по уик-эндам.

Рис. 18.4. Дерево решений, сформированное на основании обучающего множества с 12 примерами

Безусловно, если бы было собрано больше примеров, то вполне возможно, что сформированное дерево в большей степени напоминало бы исходное. К тому же дерево, приведенное на рис. 18.4, способно выработать ошибочное решение, например, при его формировании никогда не встречался случай, в котором требовалось ждать от 0 до 10 минут, а ресторан был полон. На ту ситуацию, в которой атрибут Hungry имеет ложное значение, дерево сообщает, что ждать не следует, тогда как сам автор (Стюарт Рассел), безусловно, стал бы ждать. Исходя из этого, возникает очевидный вопрос: если алгоритм выводит на основании примеров согласованное, но неправильное дерево, то насколько неправильным может вообще оказаться это дерево? Ниже, после рассмотрения подробных сведений об этапе выбора атрибутов, будет показано, как проводить экспериментальный анализ этого вопроса.