CART (дерево классификации и регрессии) в машинном обучении

CART (Дерево классификации и регрессии) — это разновидность алгоритма дерева решений. Он может обрабатывать как задачи классификации, так и регрессии. Scikit-Learn использует алгоритм дерева классификации и регрессии (CART) для обучения деревьев решений (также называемых «растущими» деревьями). CART был впервые создан Лео Брейманом, Джеромом Фридманом, Ричардом Олшеном и Чарльзом Стоуном в 1984 году.

Алгоритм КОРЗИНЫ

CART — это алгоритм прогнозирования, используемый в машинном обучении, и он объясняет, как можно прогнозировать значения целевой переменной на основе других факторов. Это дерево решений, в котором каждая вилка разделена на переменную-предиктор, а в конце каждого узла есть предсказание для целевой переменной.

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

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

• Получается лучшая точка разделения каждого входа.
• На основе лучших точек разделения каждого входа на шаге 1 определяется новая «лучшая» точка разделения.
• Разделите выбранный вход в соответствии с «лучшей» точкой разделения.
• Продолжайте разделение до тех пор, пока не будет выполнено правило остановки или дальнейшее желаемое разделение не станет доступным.

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

Индекс Джини/примесь Джини

Индекс Джини — это показатель для задач классификации в CART. Он хранит сумму квадратов вероятностей каждого класса. Он вычисляет степень вероятности того, что конкретная переменная будет неправильно классифицирована при случайном выборе, а также изменение коэффициента Джини. Он работает с категориальными переменными, выдает результаты «успешно» или «неудачно» и, следовательно, проводит только бинарное разбиение.

Степень индекса Джини варьируется от 0 до 1,

• Где 0 означает, что все элементы связаны с определенным классом или существует только один класс.
• Индекс Джини со значением 1 означает, что все элементы случайным образом распределены по различным классам, и
• Значение 0,5 означает, что элементы равномерно распределены по некоторым классам.

Математически мы можем записать примесь Джини следующим образом:

где pi — вероятность того, что объект будет отнесен к тому или иному классу.

Дерево классификации

Дерево классификации — это алгоритм, в котором целевая переменная является категориальной. Затем алгоритм используется для определения «класса», в который, скорее всего, попадет целевая переменная. Деревья классификации используются, когда набор данных необходимо разделить на классы, принадлежащие переменной ответа (например, да или нет).

Дерево регрессии

Дерево регрессии — это алгоритм, в котором целевая переменная является непрерывной, а дерево используется для прогнозирования ее значения. Деревья регрессии используются, когда переменная отклика непрерывна. Например, если переменной ответа является температура дня.

Псевдокод алгоритма CART

d = 0, endtree = 0
Note(0) = 1, Node(1) = 0, Node(2) = 0
while endtree < 1
    if Node(2d-1) + Node(2d) + .... + Node(2d+1-2) = 2 - 2d+1   
        endtree = 1
    else
        do i = 2d-1, 2d, .... , 2d+1-2
            if Node(i) > -1
                Split tree
            else 
                Node(2i+1) = -1
                Node(2i+2) = -1
            end if
        end do
    end if
d = d + 1
end while

Представление модели CART

Модели CART формируются путем выбора входных переменных и оценки точек разделения этих переменных до тех пор, пока не будет создано соответствующее дерево.

Шаги для создания дерева решений с использованием алгоритма CART:

• Жадный алгоритм : в этом входное пространство делится с использованием жадного метода, известного как рекурсивное двоичное выделение. Это численный метод, в рамках которого все значения выравниваются, а несколько других точек разделения пробуются и оцениваются с использованием функции стоимости.
• Критерий остановки: по мере того, как он движется вниз по дереву с обучающими данными, описанный выше метод рекурсивного бинарного разделения должен знать, когда прекратить разделение. Наиболее частый метод остановки заключается в использовании минимального количества обучающих данных, выделенных для каждого конечного узла. Если количество меньше указанного порога, разделение отклоняется, а узел также считается последним конечным узлом.
• Обрезка дерева: сложность дерева решений определяется как количество расщеплений в дереве. Рекомендуются деревья с меньшим количеством ветвей, поскольку они просты для понимания и менее склонны к кластеризации данных. Работа с каждым конечным узлом в дереве и оценка эффекта его удаления с помощью набора задержек — самый быстрый и простой подход к сокращению.
• Подготовка данных для CART : Для алгоритма CART не требуется специальной подготовки данных.

Преимущества КОРЗИНЫ

• Результаты упрощены.
• Деревья классификации и регрессии являются непараметрическими и нелинейными.
• Деревья классификации и регрессии неявно выполняют выбор признаков.
• Выбросы не оказывают существенного влияния на CART.
• Он требует минимального контроля и создает простые для понимания модели.

Ограничения КОРЗИНЫ

• Переоснащение.
• Высокая дисперсия.
• низкое смещение.
• структура дерева может быть нестабильной.

Приложения алгоритма CART

• Для быстрого анализа данных.
• В классификации доноров крови.
• Для экологических и экологических данных.
• В финансовых секторах.