Математика за деревьями классификации и регрессии

Может ли кто-нибудь помочь объяснить некоторые математические основы классификации в CART? Я смотрю, чтобы понять, как происходит два основных этапа. Например, я обучил классификатор CART на наборе данных и использовал тестовый набор данных, чтобы отметить его прогнозную производительность, но:

1. Как выбрать начальный корень дерева?

2. Почему и как формируется каждая отрасль?

Мой набор данных, состоящий из 400 тысяч записей с 15 столбцами и 23 классами, достигает 100% точности из матрицы путаницы, я использую 10-кратную перекрестную проверку на наборе данных. Я был бы очень признателен, если бы кто-нибудь мог помочь объяснить этапы классификации CART?

CART и деревья решений, такие как алгоритмы, работают через рекурсивное разбиение обучающего набора, чтобы получить подмножества, максимально чистые для данного целевого класса. Каждый узел дерева связан с определенным набором записей который разделен определенным тестом объекта. Например, разделение на непрерывный атрибут A может быть вызвано тестом A ≤ x . Набор записей T затем разделяется на два подмножества, что приводит к левой ветви дерева и правой ветви.$T$$A$$A \le x$$T$

$T_l = \{ t \in T: t(A) \le x \}$

и

$T_r = \{ t \in T: t(A) > x \}$

Точно так же категориальная особенность может использоваться, чтобы вызвать расщепления согласно его значениям. Например, если B = { b 1 , … , b k }, каждая ветвь i может быть индуцирована с помощью теста B = b i .$B$$B = \{b_1, \dots, b_k\}$$i$$B = b_i$

Шаг деления рекурсивного алгоритма для создания дерева решений учитывает все возможные разбиения для каждого признака и пытается найти лучший в соответствии с выбранной мерой качества: критерием разделения. Если ваш набор данных индуцирован по следующей схеме

$$A_1, \dots, A_m, C$$

где - атрибуты, а C - целевой класс, все кандидаты-расщепления генерируются и оцениваются по критерию расщепления. Разбиения по непрерывным и категориальным атрибутам генерируются, как описано выше. Выбор наилучшего разделения обычно проводится с помощью примесных мер. Примесь родительского узла должна быть уменьшена путем разделения . Пусть ( E 1 , E 2 , … , E k ) - расщепление, индуцированное на множестве записей E , критерий расщепления, который используется для примесной меры I ( ⋅ ), равен:$A_j$$C$$(E_1, E_2, \dots, E_k)$$E$$I(\cdot)$

$$\Delta = I(E) - \sum_{i=1}^{k}\frac{|E_i|}{|E|}I(E_i)$$

Стандартными мерами примеси являются энтропия Шеннона или индекс Джини. В частности, CART использует индекс Джини, который определен для набора следующим образом. Пусть p j - доля записей в E класса c j p j = | { t ∈ E : t [ C ] = c j } $E$$p_j$$E$$c_j$ тогда Gini(E)=1- Q ∑ j=1p 2 j, гдеQ- количество классов.

$$p_j = \frac{|\{t \in E:t[C] = c_j\}|}{|E|}$$ $$\mathit{Gini}(E) = 1 - \sum_{j=1}^{Q}p_j^2$$ $Q$

Это приводит к примесям 0, когда все записи принадлежат одному и тому же классу.

В качестве примера, давайте предположим , что у нас есть двоичный набор классов записей , где распределение класса ( 1 / +2 , 1 / +2 ) - следующий хороший раскол для $T$$(1/2, 1/2)$$T$

$T_l$$(1,0)$$T_r$$(0,1)$$T_l$$T_r$$|T_l|/|T| = |T_r|/|T| = 1/2$$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 0 - 0 = 1/2$$

$\Delta$

$$\Delta = 1 - 1/2^2 - 1/2^2 - 1/2 \bigg( 1 - (3/4)^2 - (1/4)^2 \bigg) - 1/2 \bigg( 1 - (1/4)^2 - (3/4)^2 \bigg) = 1/2 - 1/2(3/8) - 1/2(3/8) = 1/8$$

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

Новый экземпляр легко классифицировать с помощью дерева решений, на самом деле достаточно пройти путь от корневого узла до листа. Запись классифицируется по классу большинства листа, которого она достигает.

Скажем, что мы хотим классифицировать квадрат на этой фигуре

$A,B,C$$C$$A$$B$

Возможное индуцированное дерево решений может быть следующим:

Ясно, что квадрат записи будет классифицирован деревом решений как кружок, учитывая, что запись попадает на лист, помеченный кружками.

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

Есть много литературы по деревьям решений, я хотел просто записать схематичное введение. Другая известная реализация - C4.5.

Я не эксперт по CART, но вы можете попробовать книгу «Элементы статистического обучения», которая свободно доступна онлайн (см. Главу 9 для CART). Я считаю, что книга была написана одним из создателей алгоритма CART (Фридман).