CART (алгоритм)

Алгоритм CART (Classification and Regression Tree), как видно из названия, решает задачи классификации и регрессии построением дерева решений. Он разработан в 1974—1984 годах четырьмя профессорами статистики: Лео Брейманом (Беркли), Джеромом Фридманом (Стэнфорд), Чарлзом Стоуном (Charles Stone, Беркли) и Ричардом Олшеном (Richard A. Olshen, Стэнфорд).

На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: CART, C4.5, CHAID, CN2, NewId, ITrule и другие.

Основной смысл алгоритма

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

Преимуществом алгоритма CART является определенная гарантия того, что если искомые детерминации существуют в исследуемой совокупности, то они будут выявлены. Кроме того, CART позволяет не «замыкаться» на единственном значении выходного признака, а искать все такие его значения, для которых можно найти соответствующее объясняющее выражение.

Метод CART применяется для номинальных (обычно двухуровневых) и порядковых предикторных переменных. В этом методе перебираются все возможные варианты ветвления для каждого узла, и выбирается та предикторная переменная, при которой оценочная функция дает наилучший показатель.

Правила разбиения

Для номинальной предикторной переменной, принимающей в данном узле k значений, имеется ровно 2^(k-1) −1 вариантов разбиения множества её значений на две части.

Для порядкового предиктора, имеющего в данном узле k различных уровней, имеется k-1 точек, разделяющих разные уровни. Количество различных вариантов ветвления, которые необходимо просмотреть, будет очень большим: если в задаче много предикторов, то у них много уровней значений, а значит в дереве много терминальных вершин. Кроме того, этот метод имеет склонность выбирать для ветвления те предикторные переменные, у которых больше уровней, поэтому необходим индикатор, который позволил бы оценить качество построенной модели.

Оценка качества модели

Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения неопределённости (неоднородности) в узле. В качестве примера рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров каждого класса. Узел имеет максимальную неопределенность. Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно неоднородность уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея неопределенности формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется следующим образом

$Gini(T)=1-\sum _{i=1}^{n}p_{i}^{2}$

,где pi — вероятность (относительная частота) класса i в T. Если набор Т разбивается на две части Т1 и Т2 с числом примеров в каждом N1 и N2 соответственно, тогда показатель качества разбиения будет равен:

$Gini_{\text{split}}(T)={\frac {N_{1}}{N}}\cdot Gini(T_{1})+{\frac {N_{2}}{N}}\cdot Gini(T_{2})$

Наилучшим считается то разбиение, для которого Ginisplit(T) минимально. Обозначим N — число примеров в узле — предке, L, R — число примеров соответственно в левом и правом потомке, li и ri — число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

$Gini_{\text{split}}={\frac {L}{N}}\cdot \left(1-\sum _{i=1}^{n}\left({\frac {l_{i}}{L}}\right)^{2}\right)+{\frac {R}{N}}\cdot \left(1-\sum _{i=1}^{n}\left({\frac {r_{i}}{R}}\right)^{2}\right)\to \min$

Чтобы уменьшить объем вычислений формулу можно преобразовать:

$Gini_{\text{split}}={\frac {1}{N}}\cdot \left(L\cdot \left(1-{\frac {1}{L^{2}}}\cdot \sum _{i=1}^{n}l_{i}^{2}\right)+R\cdot \left(1-{\frac {1}{R^{2}}}\cdot \sum _{i=1}^{n}r_{i}^{2}\right)\right)\to \min$

Так как умножение на константу не играет роли при минимизации:

${\begin{array}{l}\displaystyle Gini_{\text{split}}=L-{\frac {1}{L}}\cdot \sum _{i=1}^{n}l_{i}^{2}+R-{\frac {1}{R}}\cdot \sum _{i=1}^{n}r_{i}^{2}\to \min \\\displaystyle Gini_{\text{split}}=N-\left({\frac {1}{L}}\cdot \sum _{i=1}^{n}l_{i}^{2}+{\frac {1}{R}}\cdot \sum _{i=1}^{n}r_{i}^{2}\right)\to \min \\\displaystyle {\tilde {G}}_{\text{split}}={\frac {1}{L}}\cdot \sum _{i=1}^{n}l_{i}^{2}+{\frac {1}{R}}\cdot \sum _{i=1}^{n}r_{i}^{2}\to \max \end{array}}$

В итоге, лучшим будет то разбиение, для которого величина максимальна. Таким образом, при построении «дерева решений» по методу CART ищется такой вариант ветвления, при котором максимально уменьшается значение показателя Ginisplit(T).

Механизм отсечения

Основная статья: Прореживание (деревья решений)

Этим механизмом, имеющим название minimal cost-complexity tree pruning (см. статью Pruning в английской Википедии), алгоритм CART принципиально отличается от некоторых других алгоритмов конструирования деревьев решений. В рассматриваемом алгоритме отсечение — это некий компромисс между получением дерева «подходящего размера» и получением наиболее точной оценки классификации. Отсечение (прореживание) важно не только для упрощения деревьев, но и для избежания переобучения (оверфиттинга). Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только «лучшие представители».

Перекрёстная проверка

Основная статья: Перекрёстная проверка

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

Достоинства и недостатки метода

Достоинства:

1. Данный метод является непараметрическим, это значит, что для его применения нет необходимости рассчитывать различные параметры вероятностного распределения.
2. Для применения алгоритма CART нет необходимости заранее выбирать переменные, который будут участвовать в анализе: переменные отбираются непосредственно во время проведения анализа на основании значения индекса Gini.
3. CART легко борется с выбросами: механизм «разбиения» (от англ. splitting), заложенный в алгоритме просто помещает «выбросы» в отдельный узел, что позволяет очистить имеющиеся данные от шумов.
4. Для применения этого алгоритма не надо принимать в расчет никаких предположений или допущений перед проведением анализа.
5. Большим преимуществом является скорость работы алгоритма.

Недостатки:

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

Литература

• Паклин Н.Б., Орешков В.И. Глава 9. // Бизнес-аналитика: от данных к знаниям(+CD): Учебное пособие. 2-е изд.. — СПб.: Питер, 2013. — С. 459-465. — ISBN 978-5-459-00717-6.