Разберитесь с деревом решений в одной статье: ID3, C4.5, алгоритм CART

В области машинного обучения глубокое обучение ($\text {Deep Learning}$) преобладают нейронные сети, в то время как поверхностное обучение ($\text {Shallow Learning}$) по-прежнему является областью модели дерева. С одной стороны, хотя глубокое обучение эффективно при крупномасштабном обучении, его производительность при маломасштабном обучении оставляет желать лучшего; с другой стороны, ансамблевые древовидные модели ($\text {RF}$,$\text {GBDT}$,$\text {XGBoost}$и т. д.) из-за его высокой интерпретации модели, низкой сложности в настройке параметров, высокой скорости работы и почти отсутствия необходимости в разработке признаков, он полностью подавляет глубокое обучение на малых и средних наборах данных, и это трудно для «разнородных данных». (такие как контроль рисков), данные, такие как возраст, доход, город в сцене), модель дерева ансамбля работает лучше, чем глубокое обучение, даже на крупномасштабных наборах данных. В практических приложениях крупные предприятия, такие как Facebook и Alibaba, используют комбинацию LR.$\text {GBDT}$В качестве технической поддержки для важных предприятий, таких как оценка рейтинга кликов и рекомендации по рекламе, а также$\text {XGBoost}$В последние годы он неоднократно процветал в конкурсе алгоритмов Kaggle.

В этой статье представлены основные алгоритмы ID3, C4.5 и CART модели дерева.Если вы хотите узнать о модели дерева ансамбля (случайный лес, дерево повышения градиента и т. д.), вы можете обратиться к двум другим моим сообщениям в блоге. :

Один из алгоритмов обучения ансамбля:$\text {Bagging}$Методы и случайные леса

Один из алгоритмов обучения ансамбля:$\text {Boosting}$метод с$\text {AdaBoost}$,$\text {GBDT}$

$\text {ID3}$Древо решений

$\text {ID3}$Это классический алгоритм очень раннего происхождения. Его идея основана на теории информации, а прирост информации используется для измерения выбора признаков.Каждый раз, когда для ветвления выбирается признак с наибольшим приростом информации, алгоритм использует жадный поиск сверху вниз для обхода всех возможных пространств дерева решений.

получение информации

• «Информационная энтропия» является наиболее часто используемым показателем для измерения чистоты выборки. Предположим, что текущий набор образцов$D$Б$k$Доля образцов класса$p_{k}(k=1,2, \ldots,|\mathcal{Y}|)$, но$D$Информационная энтропия определяется как:

• Информационная энтропия$\operatorname{Ent}(D)$Чем меньше значение , тем множество$D$Чем выше уверенность, тем выше чистота. Предположим, что дискретные свойства$a$имеют$V$возможные значения$\left\{a^{1}, a^{2}, \ldots, a^{V}\right\}$, если использовать$a$к набору образцов$D$подразделение, оно будет производить$V$узлы ответвления, где$v$узлы ветвления содержат$D$Все в свойствах$a$Верхнее значение$a^{v}$образец, обозначаемый как$D^{v}$,Рассчитать$D^{v}$Информационная энтропия , а затем, учитывая различное количество выборок, содержащихся в разных узлах ветвления, присваивает веса узлам ветвления.$\left|D^{v}\right| /|D|$, то есть большее влияние оказывает узел ответвления с большим количеством отсчетов, поэтому его можно вычислить с помощью атрибута$a$для набора образцов$D$«Информационный прирост», полученный путем деления:

• Принцип мысли:

  В целом, чем больше прирост информации, тем выше использование атрибутов.$a$Чем больше «улучшение достоверности» (или «улучшение чистоты»), полученное разделением, и алгоритм обучения дерева решений ID3 использует прирост информации в качестве критерия для выбора атрибутов, которые будут использоваться в каждой ветви, так что дерево решений ближе к корню.Ветвь узла имеет более сильную способность «детерминированного повышения».

генерация дерева

• Взяв в качестве примера приведенный выше набор данных (классификация арбузов по внешнему виду), всего имеется 17 обучающих выборок. В начале обучения дерева решений корневой узел содержит$D$Все примеры в , из которых положительные примеры составляют$p_{1}=\frac{8}{17}$, контрпример учитывает$p_{2}=\frac{9}{17}$, то по формуле информационная энтропия корневого узла может быть рассчитана как:

• Затем мы должны вычислить текущий набор атрибутов$\{$Получение информации для каждого атрибута в цвете, корне, ударе, текстуре, пупке, осязании}. Возьмем в качестве примера свойство «цвет», оно имеет 3 возможных значения:$\{$Бирюзовый, угольно-черный, светло-белый}. Если вы используете эту пару атрибутов$D$Разделив, можно получить три подмножества, которые записываются как$D^{1}$(цвет = зеленый$), D^{2}($цвет$=$угольно-черный$), D^{3}$(цвет = светло-белый). Подмножество$D^{1}$Включить номер$\{1,4,6,10,13,17\}$6 примеров, из которых положительные примеры составляют$p_{1}=\frac{3}{6}$, контрпример учитывает$p_{2}=\frac{3}{6} ; D^{2}$Включить номер$\{2,3,7,8,9,15\}$6 примеров , в которых учитываются положительные и отрицательные примеры$p_{1}=\frac{4}{6}, p_{2}=\frac{2}{6} ; D^{3}$Включить номер$\{5,11,12,14,16\}$5 примеров, в которых учитываются положительные и отрицательные примеры$p_{1}=\frac{1}{5}, p_{2}=\frac{4}{5}$. Согласно формуле, информационная энтропия трех узлов ветвления, полученная после деления на «цвет», может быть рассчитана как:

• Следовательно, по формуле информационный прирост признака «цвет» можно рассчитать как:

• Точно так же мы можем рассчитать прирост информации для других атрибутов:

• Очевидно, что атрибут «текстура» имеет наибольший информационный прирост, поэтому он выбран в качестве атрибута раздела. На следующем рисунке показан результат разделения корневого узла на основе «текстуры», а образцы подмножеств, содержащиеся в каждом узле ответвления, отображаются в узле:

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

• Возьмите в качестве примера первый узел ответвления (texture = clear) на приведенном выше рисунке, образец набора, содержащийся в этом узле.$D^{1}$имеет количество$\{1$,$2,3,4,5,6,8,10,15\}$9 примеров , набор доступных свойств$\{$цвет, корень, стук, пупок, тактильный$\}$. на основе$D^{1}$Рассчитайте информационный прирост каждого атрибута:

  $$\begin{array}{l} \operatorname{Gain}\left(D^{1}, \text {color}\right)=0,043 ; \quad \operatorname{Gain}\left(D^{1}, \ text {Root}\right)=0,458 \\ \operatorname{Gain}\left(D^{1}, \text {kn}\right)=0,331 ; \quad \operatorname{Gain}\left(D^ {1 }, \text {пупок}\right)=0,458 \\ \operatorname{Gain}\left(D^{1}, \text {touch}\right)=0,458 .\end{array}$$

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

  

окончание дерева

законченный$\text {ID3}$Метод генерации дерева решений, то в процессе непрерывного разбиения узлов дерева, когда следует прекратить расщепление? Обычно, когда узел удовлетворяет следующим трем условиям, ему необходимо прекратить разделение:

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

$\text {ID3}$Алгоритмические недостатки

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

$\text {C4.5}$Древо решений

$\text {C4.5}$да$\text {ID3}$Сам предлагающий$\text {ID3}$Недостатки алгоритма исправлены в следующих аспектах:

1. Внедрение скорости получения информации в качестве стандарта классификации атрибутов
2. Внедрить стратегию обрезки для обрезки
3. Дискретизация непрерывных функций
4. Обработка пропущенных значений

Скорость получения информации

• спереди$\text {ID3}$В процессе построения дерева решений мы намеренно игнорировали столбец «Число» в таблице 4.1, а если «Число» используется еще и как признак-кандидат деления, то его информационный прирост можно рассчитать по формуле$0.998$, намного больше, чем другие атрибуты деления-кандидата, это связано с тем, что «число» в качестве атрибута деления будет генерировать 17 ветвей, каждый узел ветви содержит только одну выборку, и одна выборка соответствует только одной категории, тогда «детерминированный» или «чистота» будет очень большим. Однако такое дерево решений, очевидно, не обладает способностью к обобщению и не может делать эффективные прогнозы на новых выборках. На самом деле критерий получения информации отдает предпочтение атрибутам с большим числом возможных значений.Чтобы уменьшить возможные неблагоприятные последствия этого предпочтения,$C4.5$Вместо прямого использования прироста информации для выбора оптимального свойства разделения используется «коэффициент усиления»:

  $$\operatorname{Gain}_{\operatorname{ratio}}(D, a)=\frac{\operatorname{Gain}(D, a)}{\operatorname{IV}(a)}$$

• в

• Согласно этой формуле свойство$a$Чем больше количество возможных значений (т.е.$V$больше), то$\operatorname{IV}(a)$Значение обычно больше. Например, для предыдущей таблицы$4.1$арбузный набор данных$2.0$,имеют$\mathrm{IV}($трогать$)=0.874(V=2), \mathrm{IV}($цвет$)=1.580(V=3)$,$\mathrm{IV}($Нумерация$)=4.088(V=17)$.

• Следует отметить, что критерий коэффициента усиления отдает предпочтение атрибутам с меньшим числом возможных значений, поэтому$\text {C4.5}$Алгоритм напрямую не выбирает атрибут-кандидат раздела с наивысшим коэффициентом усиления, а использует эвристический метод: сначала находят атрибут с более высоким информационным приростом, чем средний уровень, из атрибутов-кандидатов раздела, а затем выбирают атрибут с наивысшим коэффициентом усиления. .

Обрезка

• Обрезка$\text {C4.5}$Алгоритмы имеют дело с «переоснащением». в$\text {ID3}$Чтобы как можно точнее классифицировать обучающие выборки, деление узлов будет слишком сложным, что иногда приводит к слишком большому количеству ветвей дерева решений.В это время обучающие выборки могут быть «слишком хорошими», так что некоторые характеристики используется сам обучающий набор.Переобучение происходит как общее свойство всех данных. Следовательно, риск переобучения можно снизить, активно удаляя некоторые ветки.

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

  

• Результирующее неусеченное дерево решений выглядит следующим образом:

  

• Процесс обрезки представлен ниже.Обрезка обычно делится на два типа: «до обрезки» и «после обрезки»:

  • Предварительная обрезка

    • Предварительная обрезка заключается в оценке производительности обобщения каждого узла до и после разделения в процессе генерации дерева решений.Если точность прогнозирования дерева решений в наборе проверки после разделения ниже, чем до разделения, оно также будет То есть разбиение текущего узла не может улучшить обобщающую способность дерева решений, тогда остановите разбиение узла и пометьте его как конечный узел, а его категория помечается как категория с наибольшим количеством обучающих образцы.
    • На следующем рисунке показано дерево решений, в котором представлена ​​предварительная обрезка:
    
    • Плюсы: предварительная обрезка не только снижает риск переобучения, но и значительно сокращает время обучения.
    • Недостатки: Предварительная обрезка основана на «жадной» стратегии, что влечет за собой риск недообучения.

  • после обрезки

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

    • На следующем рисунке показано дерево решений после введения обрезки:

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

Непрерывная обработка значений

• $\text {C4.5}$Непрерывная обработка значений вводится путем дискретизации непрерывных признаков, предполагая, что непрерывный признак А имеет$m$ценность,$\text {C4.5}$Отсортируйте его и возьмите среднее значение каждых двух соседних значений.$m-1$точки деления, рассчитать$m-1$Каждая точка деления используется в качестве информационного прироста точки деления пополам, а точка с наибольшим информационным приростом выбирается в качестве двоичной дискретной точки классификации непрерывного признака.

• Возьмем в качестве примера следующий набор данных:

  

• Для атрибута «плотность» в начале обучения дерева решений 17 обучающих выборок, содержащихся в корневом узле, имеют 17 различных непрерывных значений этого атрибута. В соответствии с описанным выше методом точками-кандидатами пополам этого атрибута являются 16 значений-кандидатов:$T _ {\ text {плотность}} = \ {0,244, 0,294, 0,351, 0,381, 0,420, 0,459, 0,518$, $0.574,0.600,0.621,0.636,0.648,0.661,0.681,0.708,0.746\}$. Рассчитайте прирост информации для этих возможных точек деления пополам соответственно, и максимальный прирост информации атрибута «плотность» может быть получен как$0.262$, соответствующий точке бисекции$0.381$. Аналогичным образом дискретизируется и показатель «сахаристость», в итоге получаемое дерево решений выглядит следующим образом:

  

Обработка пропущенных значений

• $\text {C4.5}$Была введена обработка пропущенных значений. Неполные выборочные данные обычно встречаются в реальных данных.Очевидно, что просто отказываться от неполных выборок и использовать только выборки без пропущенных значений для обучения - большая трата информации о данных. Чтобы иметь дело с наборами данных с пропущенными значениями, вам необходимо решить следующие две проблемы:

  1. Как разделить выбор атрибута при наличии отсутствующих значений атрибута?
  2. Для определенного узла атрибута, если значение выборки по атрибуту отсутствует, как разделить выборку?

• На вопрос один,$\text {C4.5}$Подход таков: для признаков с пропущенными значениями используйте подмножество выборок без пропущенных значений для расчета прироста информации и умножьте результат на долю выборок без пропущенных значений для этой характеристики; для вопроса 2,$\text {C4.5}$Подход такой: разделить выборку на все дочерние узлы с разными значениями веса, то есть разделить выборку на каждый дочерний узел с разными вероятностями, а его вероятность равна доле выборок без пропущенных значений в каждой ветви.

$\text {C4.5}$Алгоритмические недостатки

​ Хотя$\text {C4.5}$алгоритм по сравнению с$\text {ID3}$Он был значительно улучшен, но все еще имеет следующие недостатки:

• Стратегия обрезки может быть повторно оптимизирована
• Он использует дерево с несколькими ответвлениями, но бинарное дерево более эффективно.
• Его можно использовать только для классификации, а не для регрессии.
• В используемой энтропийной модели много трудоемких логарифмических операций.

$\text {CART}$Древо решений

• $\text {CART}$Полное название "$Classification \ and \ regression \ tree$"(Дерево регрессии классификации) - это мощный алгоритм, известный$\text {GBDT}$Алгоритм представляет собой основанный на нем алгоритм обучения ансамбля.

• $\text {CART}$по сравнению с наличием$\text {C4.5}$Значительные улучшения, в основном отраженные в следующих моментах:

  1. Его структура представляет собой бинарное дерево, которое быстрее, чем дерево с несколькими ветвями.
  2. Он может выполнять как классификацию, так и регрессию
  3. Когда он выполняет классификацию, он использует коэффициент Джини в качестве стандарта разделения атрибутов, объем операций намного меньше, чем логарифмическая операция, а скорость выше.
  4. Он выполняет обрезку на основе метода сложности затрат, и эффект лучше.

Коэффициент Джини

• Информационная энтропия содержит логарифмы, и операция занимает много времени.$\text {CART}$При классификации вместо информационной энтропии вводится коэффициент Джини, эквивалентный расширению Тейлора энтропийной модели, что является более эффективным стандартом классификации атрибутов. Он рассчитывается следующим образом:

• Индекс Джини отражает вероятность того, что две случайно взятые выборки из набора данных имеют несовместимые метки классов. Следовательно, чем меньше индекс Джини, тем выше достоверность и чистота набора данных. так как$\text {CART}$является бинарным деревом, для бинарной задачи предположим, что множество$D$в свойствах$A$в условиях$D_1$и$D_2$две части, то имущество$A$Коэффициент Джини рассчитывается как:
  $$\operatorname{Gini}(D, A)=\frac{\left|D_{1}\right|}{|D|} \operatorname{Gini}\left(D_{1}\right)+\frac{\left|D_{2}\right|}{|D|} \operatorname{Gini}\left(D_{2}\right)$$

Бинарное рекурсивное разбиение

• $\text {CART}$Алгоритм принимает бинарное рекурсивное разбиение, В процессе генерации дерева текущий набор выборок всегда делится на два набора подвыборок, так что каждый нелистовой узел сгенерированного дерева решений имеет только две ветви, а все дерево решений представляет собой структуру краткого бинарного дерева, поэтому алгоритм CART подходит для сценариев, в которых значение выборочной функции равно «Да» или «Нет».

• Для функций с несколькими дискретными значениями$\text {CART}$Делается разрез пополам и выбирается разрез с наименьшим коэффициентом Джини. Если собственное значение имеет$['молодой', 'средний', 'старый']$Три значения, то разрез пополам будет иметь следующие три возможности:$[('молодой'), ('средний', 'старый')], [('средний'), ('молодой', 'старый')], [('старый'), ('молодой', 'средний' )]$, а затем вычислить коэффициент Джини, когда приведенный выше список раздвоен, и выбрать оптимальный метод сегментации.

• в то же время,$\text {CART}$Для дерева не задан критерий завершения, что означает, что дерево вырастет до максимального размера. Поэтому обрезка особенно важна, и стратегия обрезки будет обсуждаться позже.

$\text {CART}$дерево регрессии

• Существенное различие между регрессией и классификацией заключается в том, является ли результат непрерывным или дискретным.$\text {CART}$Его можно использовать не только как дерево классификации, но и как дерево регрессии.При использовании в качестве дерева регрессии применимый сценарий: хотя значения меток результатов непрерывно распределяются, их можно разделить на сообщества, то есть похожи внутри сообщества и различны между сообществами.

• $\text {CART}$Функция потерь для деревьев регрессии: сумма квадратов ошибок

  • В ранее изученном дереве решений мы использовали информационную энтропию или коэффициент Джини в качестве функции потерь, но в дереве регрессии, поскольку полученные метки являются непрерывными числовыми значениями, информационная энтропия и коэффициент Джини уже неприменимы.$\text {CART}$Функция потерь для деревьев регрессии обычно использует «сумму квадратов ошибок»:
  $$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$$
  • В приведенной выше формуле$y_i$в обучающей выборке$x_i$соответствующий фактический$y_i$ценность,$c_{1}$за$D_{1}$соответствующие образцам набора данных$y$среднее,$c_{2}$за$D_{2}$соответствующие образцам набора данных$y$средний из.

• $\text {CART}$Генерация деревьев регрессии

  Для заданного обучающего набора D

  1. Пройдите значение каждой переменной по очереди, найдите оптимальную переменную сегментации j и точку сегментации s, а затем решите:
  $$\min _{j, s}\left[\min _{c_{1}} \sum_{x_{i} \in R_{1}(j, s)}\left(y_{i}-c_{1}\right)^{2}+\min _{c_{2}} \sum_{x_{i} \in R_{2}(j, s)}\left(y_{i}-c_{2}\right)^{2}\right]$$
  • Этот шаг заключается в поиске оптимальной точки разделения для текущего узла, чтобы общая квадратичная ошибка двух узлов после разделения была наименьшей.
  
  
  2. Затем разделите область с выбранной парой (j, s) и определите соответствующее выходное значение:
  $$\begin{array}{c} R_{1}(j, s)=\left\{x \mid x^{(j)} \leq s\right\}, R_{2}(j, s)=\left\{x \mid x^{(j)}>s\right\} \\ \hat{c}_{m}=\frac{1}{N_{m}} \sum_{x_{i} \in R_{m}(j, s)} y_{i}, x \in R_{m}, m=1,2 \end{array}$$
  • $R_{1}(j, s)$, $R_{2}(j, s)$соответственно представляют левый и правый дочерние узлы, а оценочные значения на двух узлах$\hat{c}_{m}$Он представлен средним значением целевого значения на соответствующем дочернем узле (обратите внимание, что интервал всегда делится в соответствии с минимальными потерями квадратной ошибки, но$\hat{c}_{m}$Используется среднее значение, потому что функция потерь в это время представляет собой квадрат ошибки, а не среднее значение при изменении функции потерь).

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

  4. Разделите входное пространство на M областей$R_{1}, R_{2}, \cdots, R_{M}$, чтобы сгенерировать дерево решений:

  $$f(x)=\sum_{m=1}^{M} \hat{c}_{m} I\left(x \in R_{m}\right)$$
  • f(x) — дерево решений CART, которое мы изучили, I\left(x \in R_{m}\right) представляет область, к которой принадлежит соответствующий образец, и его значение равно 1 в соответствующей области, в противном случае оно равно 0 .
  • Наконец, конечные узлы обученного дерева регрессии содержат несколько значений y, так как же вывести предсказанное значение? Метод по-прежнему заключается в том, чтобы найти значение, которое минимизирует функцию потерь конечного узла, и вывести его как прогнозируемое значение. Что касается «суммы квадратов ошибок» в качестве функции потерь здесь, поскольку ее можно непосредственно использовать в качестве ошибки после вывода, среднее значение - это значение, которое минимизирует функцию потерь, и для вывода требуется только среднее значение.

Сокращение на основе сложности затрат

• так как$\text {CART}$Для дерева нет определенного критерия завершения, и дерево вырастет до своего максимального размера, поэтому обрезка особенно важна.$\text {CART}$Используя стратегию сокращения, основанную на стоимости, этот метод в конечном итоге сгенерирует серию деревьев разных размеров, каждое дерево получается путем замены некоторых поддеревьев самого большого дерева узлами-листами, из которых самое маленькое дерево содержит только один лист. узел, и, наконец, перекрестная проверка используется в наборе проверки для оценки производительности всех деревьев, и выбирается дерево с наилучшей производительностью классификации.

• Конкретные шаги алгоритма:

• Сначала назовем самое большое дерево как$T_0$, мы хотим уменьшить размер дерева, чтобы предотвратить «переоснащение», но беспокоимся о «недообучении» после удаления слишком большого количества поддеревьев, поэтому мы определяем функцию потерь, чтобы сбалансировать два:

  $$C_{\alpha}(T)=C(T)+\alpha|T|$$

  • $T$: любое поддерево;

  • $C(T)$: ошибка прогнозирования поддерева в обучающем наборе (коэффициент Джини для классификации и сумма квадратов ошибок для регрессии), которая используется для измерения степени соответствия поддерева обучающим данным;

  • $|T|$: количество листовых узлов поддерева, которое используется для измерения сложности поддерева;

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

  • Наша конечная цель — сделать функцию потерь$C_{\alpha}(T)$минимум, как видно из формулы, с параметром регуляризации$\alpha$возрастает, сложность модели дерева$|T|$будет вынужден уменьшаться, а количество сокращений увеличивается, поэтому степень соответствия уменьшается, а ошибка прогноза$C(T)$постепенно увеличивается, поэтому функция потерь$C_{\alpha}(T)$размер не может быть определен интуитивно. Поэтому мы вводим «коэффициент увеличения ошибки».

• Скорость увеличения ошибки:

  $$g(t)=\frac{C(t)-C\left(T_{t}\right)}{\left|T_{t}\right|-1}$$

  • $t$: любой внутренний одиночный узел

  • $T_t$:Узел$t$Включенное поддерево

  • $C(t)$:от$t$для листовых узлов (отрезать$t$поддерево) ошибка предсказания

  • $C(T_t)$: поддерево$T_t$ошибка предсказания

  • $|T_t|$: поддерево$T_t$Количество листовых узлов

  • Понимание формулы:

  1. Скорость увеличения ошибки используется для измерения «выгоды» или «экономической эффективности» «поведения обрезки».

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

• Далее, для самого большого дерева$T_0$, вычислить «коэффициент увеличения ошибки» каждого внутреннего узла отдельно, выбрать узел с наименьшей «коэффициентом увеличения ошибки», обрезать его ветви, и обрезанное дерево помечается как$T_1$; следующий за$T_1$«Скорость увеличения ошибки» каждого узла, выберите нижнюю часть, обрежьте и пометьте ее как$T_2$; повторяйте этот шаг до последнего дерева$T_n$Только с одним листовым узлом ряд деревьев получается следующим образом:$T_{0}, T_{1}, T_{2}, T_{3}, \ldots, T_{n}$, которые являются оптимальными поддеревьями при разном числе узлов соответственно, а также являются параметрами регуляризации.$\alpha$от$0$увеличить до$\infty$время в каждом интервале$\left[\alpha_{i}, \alpha_{i+1}\right)$оптимальное поддерево . Наконец, каждое поддерево оценивается в наборе проверки (оценка перекрестной проверки) и выбирается оптимальное поддерево.

Если у вас есть какие-либо вопросы, пожалуйста, оставьте сообщение.

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