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

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

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

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

[править] Пример задачи

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

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

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

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

Один из вариантов дерева принятия решений для этой задачи приведен на рис. 1.

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

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

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

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

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

• Алгоритм ID3
• Алгоритм ID3 с выбором атрибута с помощью Gain Ratio
• Алгоритм ID3 с выбором атрибута с помощью индекса Гини

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

[править] См. также

• Оверфиттинг
• Машинное обучение

[править] Ссылки

• Конспект лекции по Деревья принятия решений
• Алгоритмы построения деревьев решений (BaseGroup Labs)
• See5 and C5.0 (Rulequest Research)
• DecideIT Decision Tree Software (Preference)
• Decision Tree Software (TreeAge Software)
• Decision Tree Tool for Excel (Lumenaut)
• Decision Tree Tool for Excel (TreePlan)
• Decision trees applet provides several sample data sets of examples to learn and classify
• PrecisionTree (Palisade)

[править] Литература

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