Дерево решений и случайный лес

Дерево решений

Определение:

Дерево решений (англ. decision tree, DT) — логический алгоритм классификации, основанный на поиске конъюнктивных закономерностей.

Определение:

Бинарное решающее дерево — это алгоритм классификации, задающийся бинарным деревом, в котором каждой внутренней вершине [math] v \in V [/math] приписан предикат [math] \betta_v : X \rarrow {0, 1} [/math], каждой терминальной вершине v ∈ V приписано имя класса [math] c_v \in Y [/math]. При классификации объекта x ∈ X он проходит по дереву путь от корня до некоторого листа, в соответствии с Алгоритмом 1.5..

Разновидности решающих деревьев

Тип задачи

• Классификация
• Регрессия

Критерии ветвления

• Энтропийный критерий
• Критерий Джини

Передача информации между вершинами

• (alternating decision tree)

Рецукция решающих деревьев

• Предредукция
• Постредукция

Алгоритмы построения решающих деревьев

• Алгоритм ID3
• Алгоритм C4.5
• Алгоритм C5.0
• Алгоритм CART
• Алгоритм LISTBB

Композиции решающих деревьев

• Решающий лес
• Бустинг над решающими деревьями

Ссылки

• Classification and Regression Trees — лекции Cosma Shalizi, ноябрь 2009.