Алгоритм CART (CART algorithm)

Синонимы: Classification and Regression Tree

Разделы: Алгоритмы

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

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

Алгоритм реализует обучение с учителем и использует в качестве критерия для выбора разбиений в узлах индекс чистоты Джини (Gini impurity index). В процессе роста дерева алгоритм CART проводит для каждого узла полный перебор всех атрибутов, на основе которых может быть построено разбиение, и выбирает тот, который максимизирует значение индекса Джини.

Основная идея алгоритма заключается в том, чтобы выбрать такое разбиение из всех возможных в данном узле, чтобы полученные дочерние узлы были максимально однородными. При этом каждое разбиение производится только по одному атрибуту.

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

  1. Для каждого атрибута ищется лучшее разбиение (в смысле однородности результирующих подмножеств).
  2. Среди всех разбиений, найденных на предыдущем шаге, выбирается то, для которого критерий разбиения наибольший.
  3. Разбить узел, используя его лучшее разбиение, найденное на шаге 2, если не выполнено условие остановки.

Процедура упрощения деревьев решений, построенных с помощью алгоритма CART, реализуется с помощью специального метода соотношения издержки-сложность (Cost-Complexity Pruning) и перекрёстной проверки (для малых наборов данных, где полноценное разделение на обучающее и тестовое множества проблематично).

Алгоритм обладает следующими преимуществами:

  • алгоритм не является статистическим, поэтому не требует вычисления параметров вероятностных распределений;
  • атрибуты разбиения выбираются непосредственно в процессе построения дерева, поэтому нет необходимости проводить процедуру отбора переменных для модели;
  • алгоритм устойчив к выбросам и аномальным значениям;
  • высокая скорость работы.

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

Алгоритм предложен в 1984 г. Лео Брейманом, Джеромом Фридманом, Ричардом Олшеном и Чарльзом Стоуном.

results matching ""

    No results matching ""