Метод дерева решений

     Деревья решений дают возможность извлекать  правила из базы данных на естественном языке. Пример правила: Если Возраст > 35 и Доход > 200, то выдать кредит.

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

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

     Точность  моделей, созданных при помощи деревьев решений, сопоставима с другими  методами построения классификационных  моделей (статистические методы, нейронные  сети).

     Разработан  ряд масштабируемых алгоритмов, которые  могут быть использованы для построения деревьев решения на сверхбольших базах  данных; масштабируемость здесь означает, что с ростом числа примеров или  записей базы данных время, затрачиваемое  на обучение, т.е. построение деревьев решений, растет линейно. Примеры таких  алгоритмов: SLIQ, SPRINT.

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

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

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

     В процессе построения дерева, чтобы  его размеры не стали чрезмерно  большими, используют специальные процедуры, которые позволяют создавать  оптимальные деревья, так называемые деревья "подходящих размеров".

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

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

     Вторая  стратегия состоит в использовании  набора процедур, определяющих "подходящий размер" дерева, они разработаны  Бриманом, Куилендом и др. в 1984 году. Однако, как отмечают авторы, нельзя сказать, что эти процедуры доступны начинающему пользователю.

     Процедуры, которые используют для предотвращения создания чрезмерно больших деревьев, включают: сокращение дерева путем  отсечения ветвей; использование  правил остановки обучения.

     Не  все алгоритмы при конструировании  дерева работают по одной схеме. Некоторые  алгоритмы включают два отдельных  последовательных этапа: построение дерева и его сокращение; другие чередуют эти этапы в процессе своей  работы для предотвращения наращивания  внутренних узлов.

     Остановка построения дерева. Рассмотрим правило  остановки. Оно должно определить, является ли рассматриваемый узел внутренним узлом, при этом он будет разбиваться  дальше, или же он является конечным узлом, т.е. узлом решением.

     Остановка – такой момент в процессе построения дерева, когда следует прекратить дальнейшие ветвления.

     Один  из вариантов правил остановки – "ранняя остановка", она определяет целесообразность разбиения узла. Преимущество использования такого варианта –  уменьшение времени на обучение модели. Однако здесь возникает риск снижения точности классификации. Поэтому рекомендуется  вместо остановки использовать отсечение.

     Второй  вариант остановки обучения –  ограничение глубины дерева. В  этом случае построение заканчивается, если достигнута заданная глубина.

     Еще один вариант остановки – задание  минимального количества примеров, которые  будут содержаться в конечных узлах дерева. При этом варианте ветвления продолжаются до того момента, пока все конечные узлы дерева не будут  чистыми или будут содержать  не более чем заданное число объектов.

     Существует  еще ряд правил, но следует отметить, что ни одно из них не имеет большой  практической ценности, а некоторые  применимы лишь в отдельных случаях.

     Сокращение  дерева или отсечение ветвей. Решением проблемы слишком ветвистого дерева является его сокращение путем отсечения  некоторых ветвей.

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

     Точность  распознавания рассчитывается как  отношение объектов, правильно классифицированных в процессе обучения, к общему количеству объектов набора данных, которые принимали  участие в обучении.

     Ошибка  рассчитывается как отношение объектов, неправильно классифицированных в  процессе обучения, к общему количеству объектов набора данных, которые принимали  участие в обучении.

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

     Если  такое усеченное дерево все еще  не является интуитивным и сложно для понимания, используют извлечение правил, которые объединяют в наборы для описания классов. Каждый путь от корня дерева до его вершины или  листа дает одно правило. Условиями  правила являются проверки на внутренних узлах дерева.

     Ни  один алгоритм построения дерева нельзя считать наилучшим или совершенным, подтверждение целесообразности использования  конкретного алгоритма должно быть проверено и подтверждено экспериментом.

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