3.2. Алгоритм cart

CART, сокращение от Classification And Regression Tree, переводится как 'Дерево Классификации и Регрессии' – алгоритм бинарного дерева решений, впервые опубликованный Бриманом и др. в 1984 году [1]. Алгоритм предназначен для решения задач классификации и регрессии. Существует также несколько модифицированных версий – алгоритмы IndCART и DB-CART. Алгоритм IndCART, является частью пакета Ind и отличается от CART использованием иного способа обработки пропущенных значений, не осуществляет регрессионную часть алгоритма CART и имеет иные параметры отсечения. Алгоритм DB-CART базируется на следующей идее: вместо того чтобы использовать обучающий набор данных для определения разбиений, используем его для оценки распределения входных и выходных значений и затем используем эту оценку, чтобы определить разбиения. DB, соответственно означает – 'distribution based'. Утверждается, что эта идея дает значительное уменьшение ошибки классификации, по сравнению со стандартными методами построения дерева. Основными отличиями алгоритма CART от алгоритмов семейства ID3 являются:

-бинарное представление дерева решений;

-функция оценки качества разбиения;

-механизм отсечения дерева;

-алгоритм обработки пропущенных значений;

-построение деревьев регрессии.

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

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

, где p_i – вероятность (относительная частота) класса i в T.

Если набор Т разбивается на две части Т₁ и Т₂ с числом примеров в каждом N₁ и N₂ соответственно, тогда показатель качества разбиения будет равен:

Наилучшим считается то разбиение, для которого Gini_split(T) минимально.

Обозначим N – число примеров в узле – предке, L, R – число примеров соответственно в левом и правом потомке, l_i и r_i – число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:

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

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

В итоге, лучшим будет то разбиение, для которого величина максимальна. Реже в алгоритме CART используются другие критерии разбиения Twoing, Symmetric Gini и др.

Вектор предикторных переменных, подаваемый на вход дерева может содержать как числовые (порядковые) так и категориальные переменные. В любом случае в каждом узле разбиение идет только по одной переменной. Если переменная числового типа, то в узле формируется правило вида x_i< = c. Где с – некоторый порог, который чаще всего выбирается как среднее арифметическое двух соседних упорядоченных значений переменной x_i обучающей выборки. Если переменная категориального типа, то в узле формируется правило x_i V(x_i), где V(x_i) – некоторое непустое подмножество множества значений переменной x_i в обучающей выборке. Следовательно, для n значений числового атрибута алгоритм сравнивает n-1 разбиений, а для категориального (2^n-1 – 1). На каждом шаге построения дерева алгоритм последовательно сравнивает все возможные разбиения для всех атрибутов и выбирает наилучший атрибут и наилучшее разбиение для него.

Механизм отсечения дерева, оригинальное название minimal cost-complexity tree pruning, – наиболее серьезное отличие алгоритма CART от других алгоритмов построения дерева. CART рассматривает отсечение как получение компромисса между двумя проблемами: получение дерева оптимального размера и получение точной оценки вероятности ошибочной классификации.

Основная проблема отсечения – большое количество всех возможных отсеченных поддеревьев для одного дерева. Более точно, если бинарное дерево имеет |T| – листов, тогда существует ~[1.5028369^|T|] отсечённых поддеревьев. И если дерево имеет хотя бы 1000 листов, тогда число отсечённых поддеревьев становится просто огромным.

Базовая идея метода – не рассматривать все возможные поддеревья, ограничившись только 'лучшими представителями' согласно приведённой ниже оценке.

Обозначим |T| – число листов дерева, R(T) – ошибка классификации дерева, равная отношению числа неправильно классифицированных примеров к числу примеров в обучающей выборке. Определим C (T) – полную стоимость (оценку/показатель затраты-сложность) дерева Т как:

C (T) = R(T) + *|T|, где |T| – число листов (терминальных узлов) дерева,  – некоторый параметр, изменяющийся от 0 до + . Полная стоимость дерева состоит из двух компонент – ошибки классификации дерева и штрафа за его сложность. Если ошибка классификации дерева неизменна, тогда с увеличением полная стоимость дерева будет увеличиваться. Тогда в зависимости от менее ветвистое дерево, дающее бОльшую ошибку классификации может стоить меньше, чем дающее меньшую ошибку, но более ветвистое.

Определим T_max – максимальное по размеру дерево, которое предстоит обрезать. Если мы зафиксируем значение , тогда существует наименьшее минимизируемое поддерево , которое выполняет следующие условия:

С (T( )) = min_{T< = Tmax} C (T)

if C (T) = C (T( )) then T( ) <= T

Первое условие говорит, что не существует такого поддерева дерева T_max , которое имело бы меньшую стоимость, чем Т( ) при этом значении . Второе условие говорит, что если существует более одного поддерева, имеющего данную полную стоимость, тогда мы выбираем наименьшее дерево.

Можно показать, что для любого значения существует такое наименьшее минимизируемое поддерево. Но эта задача не тривиальна. Что она говорит – что не может быть такого, когда два дерева достигают минимума полной стоимости и они несравнимы, т.е. ни одно из них не является поддеревом другого. Мы не будем доказывать этот результат.

Хотя имеет бесконечное число значений, существует конечное число поддеревьев дерева Tmax. Можно построить последовательность уменьшающихся поддеревьев дерева T_max:

T₁ > T₂ > T₃ > … > {t₁}

,(где t₁ – корневой узел дерева) такую, что T_k – наименьшее минимизируемое поддерево для [ _k, _k+1). Это важный результат, так как это означает, что мы можем получить следующее дерево в последовательности, применив отсечение к текущему дереву. Это позволяет разработать эффективный алгоритм поиска наименьшего минимизируемого поддерева при различных значениях . Первое дерево в этой последовательности – наименьшее поддерево дерева T_max, имеющее такую же ошибку классификации, как и T_max, т.е. T₁ = T( = 0). Пояснение: если разбиение идет до тех пор, пока в каждом узле останется только один класс, то T₁ = T_max, но так как часто применяются методы ранней остановки (prepruning), тогда может существовать поддерево дерева T_max имеющее такую же ошибку классификации.

Как мы получаем следующее дерево в последовательности и соответствующее значение ? Обозначим T_t – ветвь дерева Т с корневым узлом t. При каких значениях дерево T – T_t будет лучше, чем Т? Если мы отсечём в узле t, тогда его вклад в полную стоимость дерева T – T_t станет C ({t}) = R(t) + , где R(t) = r(t)* p(t), r(t) – это ошибка классификации узла t и p(t) – пропорция случаев, которые 'прошли' через узел t. Альтернативный вариант: R(t)= m/n, где m – число примеров классифицированных некорректно, а n – общее число классифицируемых примеров для всего дерева.

Вклад T_t в полную стоимость дерева Т составит C (T_t) = R(T_t) + |T_t|, где

Дерево T – T_t будет лучше, чем Т, когда C ({t}) = C (T_t), потому что при этой величине они имеют одинаковую стоимость, но T – T_t наименьшее из двух. Когда C ({t}) = C (T_t) мы получаем:

решая для , получаем:

Так для любого узла t в Т₁ ,если мы увеличиваем , тогда когда

дерево, полученное отсечением в узле t, будет лучше, чем Т₁.

Основная идея состоит в следующем: вычислим это значение для каждого узла в дереве Т₁, и затем выберем 'слабые связи' (их может быть больше чем одна), т.е. узлы для которых величина

является наименьшей. Мы отсекаем Т₁ в этих узлах, чтобы получить Т₂ – следующее дерево в последовательности. Затем мы продолжаем этот процесс для полученного дерева и так пока мы не получим корневой узел (дерево в котором только один узел).