Алгоритм CART (Classification and Regression Tree), как видно из названия, решает задачи классификации и регрессии построением дерева решений. Он разработан в 1974—1984 годах четырьмя профессорами статистики: Лео Брейманом (Беркли), Джеромом Фридманом (Jerome H. Friedman, Стэнфорд), Чарлзом Стоуном (Charles Stone, Беркли) и Ричардом Олшеном (Richard A. Olshen, Стэнфорд).
На сегодняшний день существует большое число алгоритмов, реализующих деревья решений: CART, C4.5, CHAID, CN2, NewId, ITrule и другие[1].
Алгоритм CART предназначен для построения бинарного дерева решений. Бинарные деревья также называют двоичными, значит, что каждый узел дерева при разбиении имеет только двух потомков. Для алгоритма CART «поведение» объектов выделенной группы означает долю модального значения выходного признака. Выделенные группы — те, для которых эта доля достаточно высока. На каждом шаге построения дерева правило, формируемое в узле, делит заданное множество примеров на две части — часть, в которой выполняется правило (потомок — right) и часть, в которой правило не выполняется (потомок — left).[2]
Преимуществом алгоритма CART является определенная гарантия того, что если искомые детерминации существуют в исследуемой совокупности, то они будут выявлены. Кроме того, CART позволяет не «замыкаться» на единственном значении выходного признака, а искать все такие его значения, для которых можно найти соответствующее объясняющее выражение.[3]
Метод CART применяется для номинальных (обычно двухуровневых) и порядковых предикторных переменных. В этом методе перебираются все возможные варианты ветвления для каждого узла, и выбирается та предикторная переменная, при которой оценочная функция дает наилучший показатель.
Для номинальной предикторной переменной, принимающей в данном узле k значений, имеется ровно 2(k-1) −1 вариантов разбиения множества её значений на две части.
Для порядкового предиктора, имеющего в данном узле k различных уровней, имеется k-1 точек, разделяющих разные уровни. Количество различных вариантов ветвления, которые необходимо просмотреть, будет очень большим: если в задаче много предикторов, то у них много уровней значений, а значит в дереве много терминальных вершин. Кроме того, этот метод имеет склонность выбирать для ветвления те предикторные переменные, у которых больше уровней, поэтому необходим индикатор, который позволил бы оценить качество построенной модели.[4]
Оценочная функция, используемая алгоритмом CART, базируется на интуитивной идее уменьшения неопределённости (неоднородности) в узле. В качестве примера рассмотрим задачу с двумя классами и узлом, имеющим по 50 примеров каждого класса. Узел имеет максимальную неопределенность. Если будет найдено разбиение, которое разбивает данные на две подгруппы 40:5 примеров в одной и 10:45 в другой, то интуитивно неоднородность уменьшится. Она полностью исчезнет, когда будет найдено разбиение, которое создаст подгруппы 50:0 и 0:50. В алгоритме CART идея неопределенности формализована в индексе Gini. Если набор данных Т содержит данные n классов, тогда индекс Gini определяется следующим образом[5]
,где pi — вероятность (относительная частота) класса i в T. Если набор Т разбивается на две части Т1 и Т2 с числом примеров в каждом N1 и N2 соответственно, тогда показатель качества разбиения будет равен:
Наилучшим считается то разбиение, для которого Ginisplit(T) минимально. Обозначим N — число примеров в узле — предке, L, R — число примеров соответственно в левом и правом потомке, li и ri — число экземпляров i-го класса в левом/правом потомке. Тогда качество разбиения оценивается по следующей формуле:
Чтобы уменьшить объем вычислений формулу можно преобразовать:
Так как умножение на константу не играет роли при минимизации:
В итоге, лучшим будет то разбиение, для которого величина максимальна. Таким образом, при построении «дерева решений» по методу CART ищется такой вариант ветвления, при котором максимально уменьшается значение показателя Ginisplit(T).
Этим механизмом, имеющим название minimal cost-complexity tree pruning (см. статью Pruning в английской Википедии), алгоритм CART принципиально отличается от некоторых других алгоритмов конструирования деревьев решений. В рассматриваемом алгоритме отсечение — это некий компромисс между получением дерева «подходящего размера» и получением наиболее точной оценки классификации. Отсечение (прореживание) важно не только для упрощения деревьев, но и для избежания переобучения (оверфиттинга). Метод заключается в получении последовательности уменьшающихся деревьев, но деревья рассматриваются не все, а только «лучшие представители».[1]
Перекрёстная проверка является наиболее сложной и одновременно оригинальной частью алгоритма CART. Она представляет собой путь выбора окончательного дерева, при условии, что набор данных имеет небольшой объем или же записи набора данных настолько специфические, что разделить набор на обучающую и тестовую выборку не представляется возможным[1].
Достоинства:
Недостатки:
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .