Влияние отсечения частей на точность и наглядность деревьев решения

Методы отсечения поддеревьев дерева решения являются исключительно важны­ми, поскольку они оказывают благоприятное воздействие на процесс обучения при обработке зашумленных данных. Отсечение частей дерева решения оказывает свое воздействие на два критерия успеха обучения. Во-первых, оно способствует повыше­нию точности классификации новых объектов с помощью дерева решения, а во-вторых, позволяет сделать дерево решения более наглядным. Рассмотрим более под­робно оба эти результата отсечения.

Понятность описания зависит от его структуры и размеров. Удачно структуриро­ванное дерево решения проще понять, чем полностью неструктурированное. С другой стороны, если дерево решения невелико (состоит только из десяти или примерно та­кого небольшого количества узлов), то его можно легко понять независимо от струк­туры. Поскольку отсечение поддеревьев приводит к уменьшению размеров дерева, оно способствует лучшему пониманию дерева решения. Как было доказано экспери­ментально во многих проблемных областях, характеризующихся использованием зашумленных данных (таких как медицинская диагностика), сокращение размеров дерева может быть весьма значительным. В усеченном дереве количество узлов ино­гда составляет всего лишь десять процентов от первоначального количества, притом что сохраняется, по меньшей мере, такая же точность классификации.

Отсечение частей дерева позволяет также повысить точность классификации с помощью дерева. Такой результат отсечения поддеревьев может на первый взгляд

Глава 18. Машинное обучение

показаться противоречащим здравому смыслу, поскольку, отсекая часть поддерева, мы отбрасываем некоторую информацию, и может создаться впечатление, что в ре­зультате должна быть в некоторой степени потеряна точность. Но в случае обучения с использованием аашумленных данных отсечение некоторых поддеревьев (в ка­кой-то приемлемой степени) обычно приводит к повышению точности. Этот феномен можно объяснить на основе теории статистики. С точки зрения статистики отсечение поддеревьев выполняет функции своего рода подавления шума. В результате отсече­ния мы устраняем ошибки в обучающих данных, возникшие под воздействием шума, а не отбрасываем полезную информацию.

Проект

Осуществите типичный исследовательский проект в области машинного обучения. Он состоит в реализации алгоритма обучения и испытании его точности на множест­вах экспериментальных данных с использованием 10-кратной перекрестной провер­ки. Изучите, как влияет усечение дерева на точность классификации новых данных. Исследуйте влияние отсечения с минимальной ошибкой, варьируя значение пара­метра га в нищенке. Большое количество наборов обучающих данных, взятых из практики, приведено в электронном виде для использования в подобных экспери­ментах в широко известном репозитарии данных для машинного обучения UCI Repository for Machine Learning (Калифорнийский университет, г. Ирвин; http:// www. ics. uci. edu/~nu.earn/MLRepository.html).

Резюме

• К основным формам обучения относятся обучение путем сообщения необходи­мых знаний, обучение в результате открытия и обучение на примерах. Ос­воение понятий на примерах называют также индуктивным обучением. По­следняя форма обучения позволила добиться наиболее значительных успехов в создании практических приложений.

• Для обучения на примерах требуются следующие информационные компоненты:

 

• объекты и понятия, представленные в виде множеств;

• положительные и отрицательные примеры изучаемых понятий;

• гипотезы о целевом понятен;

• язык гипотез.

 

• Задача обучения на примерах состоит в формировании гипотезы, которая дос­таточно хорошо "объясняет" предъявленные примеры. При этом можно наде­яться, что такая гипотеза позволит также точно классифицировать и будущие примеры. Гипотеза является совместимой с обучающими примерами, если она классифицирует все учебные данные таким же образом, как указано в этих примерах.

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

 

• В процессе ее формирования гипотеза может быть обобщена или конкретизи­рована. Как правило, окончательная гипотеза представляет собой обобщение положительных примеров.

• В настоящей главе представлены следующие программы:

• программа, которая в результате обучения формирует правила вывода на
основании примеров, сформулированных в виде векторов атрибутов и зна­
чений;

Часть II. Применение языка Prolog в области искусственного интеллекта

• программа, которая в результате обучения формирует деревья решения на
основании примеров, сформулированных в виде векторов атрибутов и зна­
чений.

• Отсечение поддеревьев дерева решения — это мощный подход к организации
обучения с использованием зашумленных данных. Б главе подробно описан
метод отсечения с минимальной ошибкой.

• Показана сложность оценки вероятностей, на основе малых выборок и сфор­мулировано понятие т-щенки.

• Критерии оценки того, насколько успешным явилось применение некоторого метода обучения на примерах, включают следующие:

• точность логически выведенных гипотез;

• постижим ость формулировок понятий, составленных в результате обучения;

• вычислительная эффективность, во-первых, логического вывода гипотез на
основании данных, а во-вторых, классификации новых объектов с помощью
логически выведенных гипотез.

• Ожидаемая точность гипотез, сформированных в результате обучения, при обработке новых данных обычно оценивается с помощью перекрестной про­верки. Чаще всего используется 10-кратная перекрестная проверка. Особой формой перекрестной проверки является метод с исключением одного примера.

• В этой главе рассматриваются следующие понятия;

 

• машинное обучение;

• изучение понятий на примерах, индуктивное обучение;

• языки гипотез;

• реляционные описания;

• описания атрибутов и значений;

«общность и конкретность гипотез;

• обобщение и конкретизация описаний;

• формирование путем обучения реляционных описаний по такому же прин­ципу, как в программе ARCHES;

• формирование путем обучения правил вывода;

• нисходящий логический вывод деревьев решения;

• обучение с использованием зашумленных данных;

• отсечение частей дерева, последующее отсечение, отсечение с минимальной ошибкой;

• оценка вероятностей;

• перекрестная проверка.