Глоссарий

Один из популярных алгоритмов построения деревьев решений, предложенный в 1984 г. (Leo Breiman, Jerome Friedman, Richard Olshen, and Charles Stone). Аббревиатура CART означает Classification and Regression Tree – дерево классификации и регрессии. Из названия алгоритма следует, что он может работать как с непрерывной, так и с дискретной выходной переменной.

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

В процессе роста дерева алгоритм CART проводит для каждого узла полный перебор всех атрибутов, на основе которых может быть построено разбиение, и выбирает тот, который максимизирует значение показателя

,

где s - идентификатор разбиения, t - идентификатор узла, t_L и t_R - левый и правый потомки узла t соответственно, P_L и P_R - отношение числа примеров в левом и правом потомках к их общему числу в обучающем множестве, P(_j|t_L) и P(_j|t_R) – отношение числа примеров класса j в левом и правом потомках к их общему числу в каждом из них.

Процесс построения регрессионных деревьев решений в основном аналогичен классификационным, но вместо меток классов в листьях будут располагаться числовые значения. Фактически при этом реализуется кусочно-постоянная функция входных переменных.

В результате в каждом листе должны оказаться примеры с похожими значениями выходной переменной. Чем ближе они будут, тем меньше станет их дисперсия. Поэтому она является хорошей мерой «чистоты» узла. Тогда наилучшим разбиением в узле является то, которое обеспечит максимальное уменьшение дисперсии выходной переменной в нем.