Дерево принятия решений

Дерево принятия решений (также могут назваться деревьями классификации или регрессионными деревьями) — используется в области статистики и анализа данных для прогнозных моделей. Структура дерева представляет собой следующее: «листья» и «ветки». На ребрах («ветках») дерева решения записаны атрибуты, от которых зависит целевая функция, в «листьях» записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение. Подобные деревья решений широко используются в интеллектуальном анализе данных. Цель состоит в том, чтобы создать модель, которая предсказывает значение целевой переменной на основе нескольких переменных на входе.

Каждый лист представляет собой значение целевой переменной, измененной в ходе движения от корня по листу. Каждый внутренний узел соответствует одной из входных переменных. Дерево может быть также «изучено» разделением исходных наборов переменных на подмножества, основанные на тестировании значений атрибутов. Это процесс, который повторяется на каждом из полученных подмножеств. Рекурсия завершается тогда, когда подмножество в узле имеет те же значения целевой переменной, таким образом, оно не добавляет ценности для предсказаний. Процесс, идущий «сверху вниз», индукция деревьев решений (TDIDT)^[1], является примером поглощающего «жадного» алгоритма, и на сегодняшний день является наиболее распространенной стратегией деревьев решений для данных, но это не единственная возможная стратегия. В интеллектуальном анализе данных, деревья решений могут быть использованы в качестве математических и вычислительных методов, чтобы помочь описать, классифицировать и обобщить набор данных, которые могут быть записаны следующим образом:

$(x, Y) = (x_1, x_2, x_3\dots x_k, Y)$

Зависимая переменная Y является целевой переменной, которую необходимо проанализировать, классифицировать и обобщить. Вектор х состоит из входных переменных $x_1$, $x_2$, $x_3$ и т. д., которые используются для выполнения этой задачи.

Основные определения

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

Дерево решений состоит из трёх типов узлов:

• Узлы решения — обычно представлены квадратами
• Вероятностные узлы — представляются в виде круга
• Замыкающие узлы — представляются в виде треугольника

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

Типология деревьев

Деревья решений, используемые в Data Mining, бывают двух основных типов:

• Анализ дерева классификации, когда предсказываемый результат является классом, к которому принадлежат данные;
• Регрессионный анализ дерева, когда предсказанный результат можно рассматривать как вещественное число (например, цена на дом, или продолжительность пребывания пациента в больнице).

Упомянутые выше термины впервые были введены Брейманом и др.^[2] Перечисленные типы имеют некоторые сходства, а также некоторые различия, такие, как процедура используется для определения, где разбивать.^[2] Некоторые методы позволяют построить более одного дерева решений:

1. Деревья решений «мешок», наиболее раннее дерево решений, строит несколько деревьев решений, неоднократно интерполируя данные с заменой, и деревья голосований для прогноза консенсуса;^[3]
2. Случайный классификатор «лесной» использует ряд деревьев решений, с целью улучшения ставки классификации;
3. «Повышенные» деревья могут быть использованы для регрессионного типа и классификации типа проблем.^[4]
4. «Вращение леса» — деревья, в которых каждое дерево решений анализируется первым применением метода главных компонент (PCA) на случайные подмножества входных функций.^[5]

Алгоритмы построения дерева

Общая схема построения дерева принятия решений по тестовым примерам выглядит следующим образом:

• Выбираем очередной атрибут $Q$, помещаем его в корень.
• Для всех его значений $i$:
  • Оставляем из тестовых примеров только те, у которых значение атрибута $Q$ равно $i$
  • Рекурсивно строим дерево в этом потомке

Основной вопрос: как выбирать очередной атрибут?

Есть различные способы выбирать очередной атрибут:

• Алгоритм ID3, где выбор атрибута происходит на основании прироста информации (англ. Gain), либо на основании индекса Гини.
• Алгоритм C4.5 (улучшенная версия ID3), где выбор атрибута происходит на основании нормализованного прироста информации (англ. Gain Ratio).
• Алгоритм CART и его модификации — IndCART, DB-CART.
• Автоматический детектор взаимодействия Хи-квадрат (CHAID). Выполняет многоуровневое разделение при расчете классификации деревьев;^[6]
• MARS: расширяет деревья решений для улучшения обработки цифровых данных.

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

Достоинства метода

Среди прочих методов Data Mining, метод дерева принятия решений имеет несколько достоинств:

• Прост в понимании и интерпретации. Люди способны интерпретировать результаты модели дерева принятия решений после краткого объяснения
• Не требует подготовки данных. Прочие техники требуют нормализации данных, добавления дамми-переменных, а также удаления пропущенных данных.
• Способен работать, как с категориальными, так и с интервальными переменными. Прочие методы работают лишь с теми данными, где присутствует лишь один тип переменных. Например, метод отношений может быть применен только на номинальных переменных, а метод нейронных сетей только на переменных, измеренных по интервальной шкале.
• Использует модель «белого ящика». Если определенная ситуация наблюдается в модели, то её можно объяснить при помощи булевой логики. Примером «черного ящика» может быть искусственная нейронная сеть, так как результаты данной модели поддаются объяснению с трудом.
• Позволяет оценить модель при помощи статистических тестов. Это дает возможность оценить надежность модели.
• Является надежным методом. Метод хорошо работает даже в том случае, если были нарушены первоначальные предположения, включенные в модель.
• Позволяет работать с большим объемом информации без специальных подготовительных процедур. Данный метод не требует специального оборудования для работы с большими базами данных.

Недостатки метода

• Проблема получения оптимального дерева решений является NP-полной с точки зрения некоторых аспектов оптимальности даже для простых задач^[7][8]. Таким образом, практическое применение алгоритма деревьев решений основано на эвристических алгоритмах, таких как алгоритм «жадности», где единственно оптимальное решение выбирается локально в каждом узле. Такие алгоритмы не могут обеспечить оптимальность всего дерева в целом.
• Те, кто изучает метод дерева принятия решений, могут создавать слишком сложные конструкции, которые не достаточно полно представляют данные. Данная проблема называется проблемой «чрезмерной подгонки»^[9] Для того, чтобы избежать данной проблемы, необходимо использовать Метод «регулирования глубины дерева».
• Существуют концепты, которые сложно понять из модели, так как модель описывает их сложным путем. Данное явление может быть вызвано проблемами XOR, четности или мультиплексарности. В этом случае мы имеем дело с непомерно большими деревьями. Существует несколько подходов решения данной проблемы, например, попытка изменить репрезентацию концепта в модели (составление новых суждений)^[10], или использование алгоритмов, которые более полно описывают и репрезентируют концепт (например, метод статистических отношений, индуктивная логика программирования).
• Для данных, которые включают категориальные переменные с большим набором уровней (закрытий), больший информационный вес присваивается тем атрибутам, которые имеют большее количество уровней.^[11]

Регулирование глубины дерева

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

Один из вопросов, который возникает в алгоритме дерева решений — это оптимальный размер конечного дерева. Так, небольшое дерево может не охватить ту или иную важную информацию о выборочном пространстве. Тем не менее, трудно сказать, когда алгоритм должен остановиться, потому что невозможно спрогнозировать, добавление какого узла позволит значительно уменьшить ошибку. Эта проблема известна как «эффект горизонта». Тем не менее, общая стратегия ограничения дерева сохраняется, то есть удаление узлов реализуется в случае, если они не дают дополнительной информации^[12].

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

Методы регулирования

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

Пример задачи

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

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

У нас есть некоторая статистика на этот счет:

Соперник	Играем	Лидеры	Дождь	Победа
Выше	Дома	На месте	Да	Нет
Выше	Дома	На месте	Нет	Да
Выше	Дома	Пропускают	Нет	нет
Ниже	Дома	Пропускают	Нет	Да
Ниже	В гостях	Пропускают	Нет	Нет
Ниже	Дома	Пропускают	Да	Да
Выше	В гостях	На месте	Да	Нет
Ниже	В гостях	На месте	Нет	???

Хочется понять, выиграет ли наша команда в очередной игре.

См. также

• Random forest − классификатор, основанный на применении комитетов из решающих деревьев
• Переобучение
• Машинное обучение
• Таблица принятия решений

Примечания

1. ↑ Quinlan, J. R., (1986). Induction of Decision Trees. Machine Learning 1: 81-106, Kluwer Academic Publishers
2. ↑ ^{1 2} Breiman, Leo; Friedman, J. H., Olshen, R. A., & Stone, C. J. (1984). Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software. ISBN 978-0-412-04841-8.
3. ↑ Breiman, L. (1996). Bagging Predictors. «Machine Learning, 24»: pp. 123—140.
4. ↑ Friedman, J. H. (1999). Stochastic gradient boosting. Stanford University.
5. ↑ Hastie, T., Tibshirani, R., Friedman, J. H. (2001). The elements of statistical learning : Data mining, inference, and prediction. New York: Springer Verlag.
6. ↑ Kass, G. V. (1980). «An exploratory technique for investigating large quantities of categorical data». Applied Statistics 29 (2): 119—127. DOI:10.2307/2986296. JSTOR 2986296.
7. ↑ Hyafil, Laurent; Rivest, RL (1976). «Constructing Optimal Binary Decision Trees is NP-complete». Information Processing Letters 5 (1): 15-17. DOI:10.1016/0020-0190(76)90095-8.
8. ↑ Murthy S. (1998). Automatic construction of decision trees from data: A multidisciplinary survey. Data Mining and Knowledge Discovery
9. ↑ Principles of Data Mining. 2007. DOI:10.1007/978-1-84628-766-4. ISBN 978-1-84628-765-7. edit.
10. ↑ Horváth, Tamás; Yamamoto, Akihiro, eds. (2003). Inductive Logic Programming. Lecture Notes in Computer Science. 2835. DOI:10.1007/b13700. ISBN 978-3-540-20144-1. edit
11. ↑ Deng,H.; Runger, G.; Tuv, E. (2011). «Bias of importance measures for multi-valued attributes and solutions». Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). pp. 293—300.
12. ↑ Fast, Bottom-Up Decision Tree Pruning Algorithm

Ссылки

• Конспект лекции по деревьям принятия решений
• Алгоритмы построения деревьев решений (BaseGroup Labs)
• Decision trees applet provides several sample data sets of examples to learn and classify

Литература

• Ананий В. Левитин Глава 10. Ограничения мощи алгоритмов: Деревья принятия решения // Алгоритмы: введение в разработку и анализ = Introduction to The Design and Analysis of Aigorithms. — М.: Вильямс, 2006. — С. 409-417. — ISBN 0-201-74395-7