CART (алгоритм)

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

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

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

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

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

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

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

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

${\displaystyle 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-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

${\displaystyle 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 }$

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

${\displaystyle 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 }$

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

${\displaystyle {\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 принципиально отличается от некоторых других алгоритмов конструирования деревьев решений. В рассматриваемом алгоритме отсечение — это некий компромисс между получением дерева «подходящего размера» и получением наиболее точной оценки классификации. Отсечение (прореживание) важно не только для упрощения деревьев, но и для избежания переобучения (оверфиттинга). Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только «лучшие представители».[1]

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

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

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

Недостатки:

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

1. Чубукова И. А. Data Mining. М.: Бином, 2008
2. Breiman L., Friedman J. H., Olshen R. A., & Stone C. J. Classification and regression trees. Monterey, CA: Wadsworth & Brooks/Cole Advanced Books & Software, 1984
3. Толстова Ю.Н. Анализ социологических данных. М.: Научный мир, 2000
4. Деревья решений – CART математический аппарат. Часть №1 // http://www.basegroup.ru/trees/math_cart_part1.htm
5. Электронный учебник «Statistica» // http://www.statsoft.ru/home/textbook.htm (недоступная+ссылка)

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