36. Метод «деревья решений».

Возникновение – 50-е годы. Метод также называют деревьями решающих правил, деревьями классификации и регрессии. Это способ представления правил в иерархической, последовательной структуре.

Пример.

Преимущества метода:

-интуитивность деревьев решений;

-возможность извлекать правила из базы данных на естественном языке;

-не требует от пользователя выбора входных атрибутов;

-точность моделей;

-разработан ряд масштабируемых алгоритмов;

-быстрый процесс обучения;

-обработка пропущенных значений;

-работа и с числовыми, и с категориальными типам данных.

Процесс конструирования:

Основные этапы алгоритмов конструирования деревьев:

-построение или создание дерева (treebuilding);

-сокращение дерева (tree pruning).

Критерии расщепления:

-мера информационного выигрыша (informationgainmeasure)

-индекс Gini, т.е.gini(T), определяется по формуле:

- Большое дерево не означает, что оно подходящее.

Остановка построения дерева.

Остановка – такой момент в процессе построения дерева, когда следует прекратить дальнейшие ветвления.

Варианты остановки:

-ранняя остановка;

-ограничение глубины дерева;

-задание минимального количества примеров.

Сокращение дерева или отсечение ветвей:

Критерии:

-точность распознавания

-ошибка.

Алгоритмы. CART.

-CART (Classification and Regression Tree)

-разработан в 1974-1984 годах четырьмя профессорами статистики

-CARTпредназначен для построения бинарного дерева решений.

Особенности:

-функция оценки качества разбиения;

-механизм отсечения дерева;

-алгоритм обработки пропущенных значений;

-построение деревьев регрессии.

Алгоритмы. С4.5

-строит дерево решений с неограниченным количество ветвей у узла.

-дискретные значения => только классификация

-каждая запись набора данных ассоциирована с одним из предопределенных классов => один из атрибутов набора данных должен являться меткой класса.

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

Перспективы и методы:

- разработка новых масштабируемых алгоритмов;

-метод деревьев – иерархическое, гибкое средство предсказания принадлежности объектов к определенному классу или прогнозирования значений числовых переменных.

-качество работы зависит как от выбора алгоритма, так и от набора исследуемых данных.

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