Решающие правила в дереве Cart и алгоритм их выбора. Возможные критерии перемешанности классов и откликов в задачи регрессии (теормин)

Решающие деревья

Решающее дерево — алгоритм классификации, основанный на поиске конъюктивных закономерностей. Дерево — конечный ацикличный связный граф, имеющий выделенную вершину, не имеющую входящих ребер — корень дерева. Вершины, не имеющие выходящих ребер называются листьями. В каждой вершине дерева записано решающее правило, делящее входные объекты на n классов.

Алгоритм CART

CART (classification and regression trees) — алгоритм, решающий задачи классификации и регрессии. В CART решающее правило имеет вид бинарной пороговой функции одного признака. Решающее правило должно делить выборку наилучшим способом на две части $X_{l}(i,h)=\{x|x_{i}\leq h\}$ и $X_{r}(i,h)=\{x|x_{i}>h\}$ относительно критерия информативности $Q(X,i,h)$.

Нужно найти порог $h_{t}$ и признак $i_{t}$ (t - индекс вершины), при которых достигается максимум следующего критерия $Q(X_{t},i,h)=\phi (t)-{\frac {N_{l}}{N_{m}}}\phi (t_{l})-{\frac {N_{r}}{N_{m}}}\phi (t_{r})$, где $\phi (t)$ — impurity function.

Виды impurity function

Критерий Джини

$\phi (t)=\sum _{i}p(\omega _{i}|t)(1-p(\omega _{i}|t))=1-\sum _{i}p(\omega _{i}|t)^{2}$

Интерпретация: вероятность допустить ошибку при выборе порога $h_{t}$ и признака $i_{t}$.

Энтропийный критерий

$\phi (t)=-\sum _{i}p(\omega _{i}|t)\ln p(\omega _{i}|t)$

Интерпретация: мера неопределенности случайной величины

Ошибка классификации

$\phi (t)=1-max_{i}p(\omega _{i}|t)$

Интерпретация: частота ошибок при классификации наиболее мощным классом.

Случай регрессии

Для задач регрессии обычно используют MSE или MAE.

Аня: нужны ссылки на статьи c MSE и MAE

Ссылки

Слайды лекции В. Китова

Конспект семинаров по машинному обучению

Лекции В. Китова