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

[править]

Материал из Википедии — свободной энциклопедии

Перейти к: навигация, поиск

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

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

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

Содержание [убрать] 1 Пример задачи 2 Алгоритмы построения дерева 3 См. также 4 Ссылки 5 Литература

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

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

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

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

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

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

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

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

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

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

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

• Алгоритм ID3

Алгоритм ID3 — один из алгоритмов для построения дерева принятия решений. Разработан Джоном Р. Квинланом (англ. John R. Quinlan).

[править] Алгоритм

В общем, алгоритм ID3 следующий:

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

Алгоритм следующий:

ID3(Таблица примеров, Целевой признак, Признаки)

1. Если все примеры положительны, то возвратить узел с меткой «+».
2. Если все примеры отрицательны, то возвратить узел с меткой «-».
3. Если множество признаков пустое, то возвратить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
4. Иначе:
1. A — признак, который лучше всего классифицирует примеры (с максимальной информационной выгодой).
2. Создать корень дерева решения; признаком в корне будет являться A.
3. Для каждого возможного значения A (v_i):
1. Добавить новую ветвь дерева ниже корня с узлом со значением A = v_i
2. Выделить подмножество Examples (v_i) примеров, у которых A = v_i.
3. Если подмножество примеров пусто, то ниже этой новой ветви добавить узел с меткой, которая больше других встречается в значениях целевого признака в примерах.
4. Иначе, ниже этой новой ветви добавить поддерево, вызывая рекурсивно ID3(Examples (v_i), Целевой признак, Признаки)
5. Возвратить корень.

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

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

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

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

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

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

• Конспект лекции по деревьям принятия решений
• Алгоритмы построения деревьев решений (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

Источник — «https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D1%80%D0%B8%D0%BD%D1%8F%D1%82%D0%B8%D1%8F_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9»

Категория: Деревья принятия решений