CART (Classification and regression tree)

CART (Classification and regression tree) — реализация решающего дерева четырьмя профессорами статистики.

Формальное определение

CART-дерево — это самое обычное решающее дерево, которое:

• совершает разбиение в узле только по одному признаку $i(t)$, где $t$ — текущий узел
• бинарно
• решающее правило есть разбиение по порогу, то есть: $S_{t}(1)=\left\{x|x_{i}\leq h\right\};S_{t}(2)=\left\{x|x_{i}>h\right\}$
• порог выбирается из значений этого признака в обучающей выборке
• one-hot кодирование для категориальных признаков (предварительно категориальные признаки можно обработать каким-нибудь стандартным образом)
• Стрижка осуществляется с помощью cost-complexity pruning.

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

• + простота (отсутствуют параметры)
• + эффективность (в силу "бедности" класса функций, выбранных для решающих правил, быстро найти оптимальное можно тупым перебором)
• + интерпретируемость
• + устойчиво к линейным масштабированиям
• - не является онлайновым.
• - как и у любого решающего дерева, если истинное разделение классов — по диагональной прямой, оптимальное дерево будет очень глубоким (так как оно будет пытаться приблизить эту прямую лесенкой)
• - как и любое решающее дерево не устойчиво к шуму, составу выборки, критерию.
• + возможность обработки пропусков (метод суррогатных признаков).
• + допустимы разнотипные данные.
• + трудоемкость линейна по длине выборки $O(hl|\beta |)$
• + не бывает отказов от классификации