«

»

Окт 15

Алгоритм классификации “Classification and Regression Tree”

CART (сокращение от Classification And Regression Tree) переводится как «Дерево Классификации и Регрессии» — алгоритм бинарного дерева решений, впервые опубликованный Бриманом и др. в 1984 году. Алгоритм предназначен для решения задач классификации и регрессии.

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

Бинарное представление дерева решений
В алгоритме CART каждый узел дерева решений имеет двух потомков. На каждом шаге построения дерева
правило, формируемое в узле, делит заданное множество примеров (обучающую выборку) на две части —
часть, в которой выполняется правило (потомок — right), и часть, в которой правило не выполняется (потомок —
left). Для выбора оптимального правила используется функция оценки качества разбиения.

Предлагаемое алгоритмическое решение
Каждый узел (структура или класс) должен иметь ссылки на двух потомков: Left и Right (структуры аналогичного вида). Узел также должен содержать идентификатор правила (подробнее о правилах см. ниже), каким-либо образом описывать правую часть правила, содержать информацию о количестве или отношении примеров каждого класса обучающей выборки, «прошедшей» через узел, и иметь признак терминального узла — листа. Таковы минимальные требования к структуре (классу) узла дерева.

Функция оценки качества разбиения
При разбиении узла на потомков используется функция оценки качества разбиения – индекс Gini.данная оценочная функция основана на идее уменьшения неопределенности в узле. Допустим, есть узел, и он разбит на два класса. Максимальная неопределенность в узле будет достигнута при разбиении его на два подмножества по 50 примеров, а максимальная определенность – при разбиении на 100 и 0 примеров.

Правила разбиения.
Алгоритм CART работает с числовыми и категориальными атрибутами. В каждом узле разбиение может идти только по одному атрибуту. Если атрибут является числовым, то во внутреннем узле формируется правило вида xi <= c. Значение c в большинстве случаев выбирается как среднее арифметическое двух соседних упорядоченных значений переменной xi обучающего набора данных. Если же атрибут относится к категориальному типу, то во внутреннем узле формируется правило xi V(xi), где V(xi) – некоторое не пустое подмножество множества значений переменной xi в обучающем наборе данных.

Механизм отсечения.
Этим механизмом, имеющим название minimal cost-complexity tree pruning, алгоритм CART принципиально отличается от других алгоритмов конструирования деревьев решений. В рассматриваемом алгоритме отсечение – это некий компромисс между получением дерева “подходящего размера” и получением наиболее точной оценки классификации. Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только “лучшие представители”.

Перекрестная проверка (V-fold cross-validation) является наиболее сложной и одновременно оригинальной частью алгоритма CART. Она представляет собой путь выбора окончательного дерева, при условии, что набор данных имеет небольшой объем или же записи набора данных настолько специфические, что разделить набор на обучающую и тестовую выборку не представляется возможным.

Алгоритм CART успешно сочетает в себе качество построенных моделей и, при удачной реализации, высокую скорость их построения. Также он включает в себя уникальные методики обработки пропущенных значений и
построения оптимального дерева на основе совокупности алгоритмов cost-complexity pruning и V-fold cross-validation.