Методы отсечения поддеревьев дерева решения являются исключительно важными, поскольку они оказывают благоприятное воздействие на процесс обучения при обработке зашумленных данных. Отсечение частей дерева решения оказывает свое воздействие на два критерия успеха обучения. Во-первых, оно способствует повышению точности классификации новых объектов с помощью дерева решения, а во-вторых, позволяет сделать дерево решения более наглядным. Рассмотрим более подробно оба эти результата отсечения.
Понятность описания зависит от его структуры и размеров. Удачно структурированное дерево решения проще понять, чем полностью неструктурированное. С другой стороны, если дерево решения невелико (состоит только из десяти или примерно такого небольшого количества узлов), то его можно легко понять независимо от структуры. Поскольку отсечение поддеревьев приводит к уменьшению размеров дерева, оно способствует лучшему пониманию дерева решения. Как было доказано экспериментально во многих проблемных областях, характеризующихся использованием зашумленных данных (таких как медицинская диагностика), сокращение размеров дерева может быть весьма значительным. В усеченном дереве количество узлов иногда составляет всего лишь десять процентов от первоначального количества, притом что сохраняется, по меньшей мере, такая же точность классификации.
Отсечение частей дерева позволяет также повысить точность классификации с помощью дерева. Такой результат отсечения поддеревьев может на первый взгляд
Глава 18. Машинное обучение
показаться противоречащим здравому смыслу, поскольку, отсекая часть поддерева, мы отбрасываем некоторую информацию, и может создаться впечатление, что в результате должна быть в некоторой степени потеряна точность. Но в случае обучения с использованием аашумленных данных отсечение некоторых поддеревьев (в какой-то приемлемой степени) обычно приводит к повышению точности. Этот феномен можно объяснить на основе теории статистики. С точки зрения статистики отсечение поддеревьев выполняет функции своего рода подавления шума. В результате отсечения мы устраняем ошибки в обучающих данных, возникшие под воздействием шума, а не отбрасываем полезную информацию.
Проект
Осуществите типичный исследовательский проект в области машинного обучения. Он состоит в реализации алгоритма обучения и испытании его точности на множествах экспериментальных данных с использованием 10-кратной перекрестной проверки. Изучите, как влияет усечение дерева на точность классификации новых данных. Исследуйте влияние отсечения с минимальной ошибкой, варьируя значение параметра га в нищенке. Большое количество наборов обучающих данных, взятых из практики, приведено в электронном виде для использования в подобных экспериментах в широко известном репозитарии данных для машинного обучения UCI Repository for Machine Learning (Калифорнийский университет, г. Ирвин; http:// www. ics. uci. edu/~nu.earn/MLRepository.html).
Резюме
• К основным формам обучения относятся обучение путем сообщения необходимых знаний, обучение в результате открытия и обучение на примерах. Освоение понятий на примерах называют также индуктивным обучением. Последняя форма обучения позволила добиться наиболее значительных успехов в создании практических приложений.
• Для обучения на примерах требуются следующие информационные компоненты:
• объекты и понятия, представленные в виде множеств;
• положительные и отрицательные примеры изучаемых понятий;
• гипотезы о целевом понятен;
• язык гипотез.
• Задача обучения на примерах состоит в формировании гипотезы, которая достаточно хорошо "объясняет" предъявленные примеры. При этом можно надеяться, что такая гипотеза позволит также точно классифицировать и будущие примеры. Гипотеза является совместимой с обучающими примерами, если она классифицирует все учебные данные таким же образом, как указано в этих примерах.
• Процесс индуктивного обучения предусматривает поиск среди возможных гипотез. Такая задача по самой своей сути является комбинаторной. Для уменьшения комбинаторной сложности этот процесс поиска обычно управляется с помощью эвристических методов.
• В процессе ее формирования гипотеза может быть обобщена или конкретизирована. Как правило, окончательная гипотеза представляет собой обобщение положительных примеров.
• В настоящей главе представлены следующие программы:
• программа, которая в результате обучения формирует правила вывода на
основании примеров, сформулированных в виде векторов атрибутов и зна
чений;
Часть II. Применение языка Prolog в области искусственного интеллекта
• программа, которая в результате обучения формирует деревья решения на
основании примеров, сформулированных в виде векторов атрибутов и зна
чений.
• Отсечение поддеревьев дерева решения — это мощный подход к организации
обучения с использованием зашумленных данных. Б главе подробно описан
метод отсечения с минимальной ошибкой.
• Показана сложность оценки вероятностей, на основе малых выборок и сформулировано понятие т-щенки.
• Критерии оценки того, насколько успешным явилось применение некоторого метода обучения на примерах, включают следующие:
• точность логически выведенных гипотез;
• постижим ость формулировок понятий, составленных в результате обучения;
• вычислительная эффективность, во-первых, логического вывода гипотез на
основании данных, а во-вторых, классификации новых объектов с помощью
логически выведенных гипотез.
• Ожидаемая точность гипотез, сформированных в результате обучения, при обработке новых данных обычно оценивается с помощью перекрестной проверки. Чаще всего используется 10-кратная перекрестная проверка. Особой формой перекрестной проверки является метод с исключением одного примера.
• В этой главе рассматриваются следующие понятия;
• машинное обучение;
• изучение понятий на примерах, индуктивное обучение;
• языки гипотез;
• реляционные описания;
• описания атрибутов и значений;
«общность и конкретность гипотез;
• обобщение и конкретизация описаний;
• формирование путем обучения реляционных описаний по такому же принципу, как в программе ARCHES;
• формирование путем обучения правил вывода;
• нисходящий логический вывод деревьев решения;
• обучение с использованием зашумленных данных;
• отсечение частей дерева, последующее отсечение, отсечение с минимальной ошибкой;
• оценка вероятностей;
• перекрестная проверка.
