Дерево принятия решений
Дерево принятия решений — дерево, использующееся для решения задач классификации данных или, иначе говоря, для задачи аппроксимации заданной булевой функции. Один из вариантов машинного обучения с учителем.
Ситуация, в которой стоит применять деревья принятия решений, обычно выглядит так: есть много случаев, каждый из которых описывается некоторым конечным набором дискретных атрибутов, и в каждом из случаев дано значение некоторой (неизвестной) булевой функции, зависящей от этих атрибутов. Задача — создать достаточно экономичную конструкцию, которая бы описывала эту функцию и позволяла классифицировать новые, поступающие извне данные.
На ребрах дерева решения записаны атрибуты, от которых зависит целевая функция, в листьях записаны значения целевой функции, а в остальных узлах — атрибуты, по которым различаются случаи. Чтобы классифицировать новый случай, надо спуститься по дереву до листа и выдать соответствующее значение.
Содержание |
[править] Пример задачи
Предположим, что нас интересует, выиграет ли наша любимая футбольная команда следующий матч. Мы знаем, что это зависит от ряда параметров; перечислять их все — задача безнадежная, поэтому ограничимся основными:
- выше ли находится соперник по турнирной таблице;
- дома ли играется матч;
- пропускает ли матч кто-либо из лидеров команды;
- идет ли дождь.
У нас есть некоторая статистика на этот счет:
| Соперник | Играем | Лидеры | Дождь | Победа |
|---|---|---|---|---|
| Выше | Дома | На месте | Да | Нет |
| Выше | Дома | На месте | Нет | Да |
| Выше | Дома | Пропускают | Нет | нет |
| Ниже | Дома | Пропускают | Нет | Да |
| Ниже | В гостях | Пропускают | Нет | Нет |
| Ниже | Дома | Пропускают | Да | Да |
| Выше | В гостях | На месте | Да | Нет |
| Ниже | В гостях | На месте | Нет | ??? |
Хочется понять, выиграет ли наша команда в очередной игре.
[править] Алгоритмы построения дерева
Общая схема построения дерева принятия решений по тестовым примерам выглядит следующим образом:
- Выбираем очередной атрибут
, помещаем его в корень. - Для всех его значений
:
- Оставляем из тестовых примеров только те, у которых значение атрибута равно
- Рекурсивно строим дерево в этом потомке
- Оставляем из тестовых примеров только те, у которых значение атрибута
, помещаем его в корень.
:
Основной вопрос: как выбирать очередной атрибут?
Есть различные способы выбирать очередной атрибут:
- Алгоритм ID3, где выбор атрибута происходит на основании прироста информации (англ. Gain), либо на основании индекса Гини.
- Алгоритм C4.5 (улучшенная версия ID3), где выбор атрибута происходит на основании нормализованного прироста информации (англ. Gain Ratio).
- Алгоритм CART и его модификации — IndCART, DB-CART.
На практике в результате работы этих алгоритмов часто получаются слишком детализированные деревья, которые при их дальнейшем применении дают много ошибок. Это связано с явлением переобучения. Для сокращения деревьев используется отсечение ветвей (англ. pruning).
[править] См. также
- Random forest − классификатор, основанный на применении комитетов из решающих деревьев
- Переобучение
- Машинное обучение
- Таблица принятия решений
[править] Ссылки
- Конспект лекции по деревьям принятия решений
- Алгоритмы построения деревьев решений (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
