Дерево принятия решений
Материал из Википедии — свободной энциклопедии
Деревья принятия решений обычно используются для решения задач классификации данных или, иначе говоря, для задачи аппроксимации заданной булевой функции. Ситуация, в которой стоит применять деревья принятия решений, обычно выглядит так: есть много случаев, каждый из которых описывается некоторым конечным набором дискретных атрибутов, и в каждом из случаев дано значение некоторой (неизвестной) булевой функции, зависящей от этих атрибутов. Задача — создать достаточно экономичную конструкцию, которая бы описывала эту функцию и позволяла классифицировать новые, поступающие извне данные.
Дерево принятия решений — это дерево, на ребрах которого записаны атрибуты, от которых зависит целевая функция, в листьях записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи.
Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.
Содержание |
[править] Пример задачи
Предположим, что нас интересует, выиграет ли наша любимая футбольная команда следующий матч. Мы знаем, что это зависит от ряда параметров; перечислять их все — задача безнадежная, поэтому ограничимся основными:
- выше ли находится соперник по турнирной таблице;
- дома ли играется матч;
- пропускает ли матч кто-либо из лидеров команды;
- идет ли дождь.
У нас есть некоторая статистика на этот счет:
| Соперник | Играем | Лидеры | Дождь | Победа |
|---|---|---|---|---|
| Выше | Дома | На месте | Да | Нет |
| Выше | Дома | На месте | Нет | Да |
| Выше | Дома | Пропускают | Нет | Да |
| Ниже | Дома | Пропускают | Нет | Да |
| Ниже | В гостях | Пропускают | Нет | Нет |
| Ниже | Дома | Пропускают | Да | Да |
| Выше | В гостях | На месте | Да | Нет |
| Ниже | В гостях | На месте | Нет | ??? |
Хочется понять, выиграет ли наша команда в очередной игре.
Один из вариантов дерева принятия решений для этой задачи приведен на рис. 1.
[править] Алгоритмы построения дерева
Общая схема построения дерева принятия решений по тестовым примерам выглядит следующим образом:
- Выбираем очередной атрибут Q, помещаем его в корень.
- Для всех его значений i:
- Оставляем из тестовых примеров только те, у которых значение атрибута Q равно i
- Рекурсивно строим дерево в этом потомке
Основной вопрос: как выбирать очередной атрибут?
Есть различные способы выбирать очередной атрибут:
- Алгоритм ID3
- Алгоритм 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
