введение
Модель нейронной сети, особенно модель глубокой нейронной сети, стала блокбастером со времен AlexNet в Imagenet Challenge 2012. Это, несомненно, самый красивый мальчик в исследованиях машинного обучения. Различные достижения и прорывы появляются бесконечным потоком. Все ученые и инженеры любить это.
С момента развития исследований в области машинного обучения, в дополнение к пути метода модели нейронной сети, существует множество различных путей метода, таких как байесовский алгоритм, генетический алгоритм, машина опорных векторов и т. д. Эти классические алгоритмы использовались во многих сценариях. . Модель дерева, представленная в этой статье, также является очень классическим алгоритмом машинного обучения, который часто можно увидеть в рекомендательных системах.
Как строится и реализуется эта древовидная модель и какова ее основная идея? Эффект древовидной модели недостаточно хорош, какие идеи и методы можно использовать для его улучшения? Эта статья в основном включает в себя следующие три аспекта:
1.决策树
2.集成学习
3.随机森林与梯度提升决策树
Древо решений
Дерево решений — это простейшая модель в древовидной модели, а также основа двух моделей стохастического глубокого леса и дерева решений с градиентным усилением, которые будут представлены позже. Используя алгоритм дерева решений, мы можем нарисовать такое дерево на наборе данных исторического датирования, Листовые узлы на этом дереве представляют заключение, а нелистовые узлы представляют собой основу. По своим характеристикам выборка начинается с корневого узла и делится на дочерние узлы по разным решениям до тех пор, пока листовой узел не будет содержать только одну категорию (т. е. один тип заключения).
Предположим, что в приведенной выше таблице есть набор данных, на основе таких данных можно построить такое дерево решений, как показано на следующем рисунке.
Информационная энтропия и примесь Джини
Можно видеть, что ключом к построению дерева решений является «разделение», которое непрерывно разбивается на дочерние узлы до конечного узла (который не может быть разделен). Итак, каковы стандарты и методы для этого критического разделения, и как лучше всего его разделить? Очевидно, что лучше всего полностью разделить положительные и отрицательные образцы, одна сторона положительная, а другая отрицательная, и наборы с обеих сторон очень «детерминированы». Здесь определенность относится к возможности только одного исхода события.Таким образом, как количественно оценить показатель «определенности», как правило, существует два метода: информационная энтропия и примесь Джини.
Информационная энтропия Энтропия – показатель, используемый для измерения неопределенности информации, рассчитывается следующим образом:
где P(X=i) — вероятность того, что случайная величина X примет значение i.
Примесь Джини на самом деле является приближенным упрощенным вычислением информационной энтропии, посколькуПосле разложения Тейлора, поскольку
, поэтому член старшего порядка приблизительно равен 0 и может быть проигнорирован, и сохраняется только член первого порядка 1-P(X=i).
вУказывает вероятность того, что выбранная выборка относится к k-му классу. С точки зрения формулы примесь Джини можно понимать как вероятность того, что две выборки выбраны случайным образом из набора данных D, и эти две выборки просто относятся к разным классам.
И информационная энтропия, и примесь Джини могут объективно и конкретно количественно определять «неопределенность», и чем больше два показателя, тем выше степень неопределенности вещей.
Например, если есть три монеты, первая монета имеет полностью сбалансированное качество лицевой и оборотной сторон, и вероятность переворота лицевой и оборотной сторон одинакова. Среди трех монет третья монета имеет наименьшую степень неопределенности, так как у нее нет неопределенности, а выпадение орла является неизбежным событием; у первой монеты наибольшая степень неопределенности, и определить подбрасывание нет возможности. монета имеет следующую наивысшую степень неопределенности, потому что она имеет относительно высокую вероятность выпадения решки и относительно надежна.
Построить дерево классификации
С методом количественной оценки «неопределенности» мы используем эти индикаторы, чтобы указать нам, какую функцию следует выбрать и как разветвить функцию, чтобы гарантировать, что каждый шаг «разделения» является оптимальным, и повторяем до конечного узла. Очевидно, что алгоритм построения этого дерева решений является жадным алгоритмом. Учитывая проблему реализации алгоритма, это дерево решений предпочтительно должно быть бинарным, а не разветвленным, поэтому мы обычно используем бинарный алгоритм CART (Дерево классификации и регрессии) для построения дерева решений.
Взяв в качестве примера набор данных датирования D, Gini(D) = 0,5, разделенный на два набора d1, d2, а метки 0 и 1 означают «нет» и «да». Джини усиление, как показано в таблице ниже, мы используем усиление Джини для выбора признаков и подтверждения их оптимальных точек бифуркации.
Видно, что когда точка бифуркации равна 26,5 на основе температурных характеристик, набор данных D делится на два набора
Построить дерево регрессии
Деревья решений используются для задач регрессии, и идея та же, что и у задач классификации. Просто измените метод оценки разделения качества и информационной энтропии на функцию квадрата ошибки, то есть измените функцию усиления на квадрат усиления ошибки.
Предположим, что j-я переменная признака в обучающем набореи его значение s, как переменную сегментации и точку сегментации, и определить две области
,
Чтобы найти оптимальные j и s, решите следующие уравнения
Улучшение производительности модели дерева
В процессе построения дерева решений мы видим, что до тех пор, пока выборки не конфликтуют (выборки являются как положительными, так и отрицательными выборками), они обязательно сойдутся за счет добавления большего количества листьев (охватывающих меньше выборок). к дереву решений. Однако такое дерево решений совершенно бесполезно для обобщения законов данных.Это всего лишь эквивалентно запоминанию обучающей выборки в виде дерева.Это может быть не то же самое для необученных выборок данных.Обученная модель на самом деле выше бессмысленно.
Деревья решений более склонны к переоснащению, поэтому они должны быть ограничены структурой дерева. Используйте такие методы, как отсечение, чтобы отрезать избыточные ветви, чтобы максимально упростить структуру дерева, чтобы улучшить производительность прогнозирования (то есть способность к обобщению) модели дерева на необученных данных. Кроме того, ансамблевое обучение (Ensemble Learning), добавление нескольких деревьев по горизонтали и использование результатов моделей нескольких деревьев для вынесения всесторонних суждений, также является распространенным методом повышения производительности модели. Он часто используется в различных соревнованиях и олимпиадах в области машинного обучения, и является классической рутиной для ранжирования списков.
интегрированное обучение
Мы знаем, что модели не идеальны, но имеют ошибки. Ошибку модели можно разделить на два типа: один — смещение, которое можно понимать как ошибку между средним значением, предсказанным моделью, и истинным значением выборки, а другой — дисперсия, которую можно понимать как изменение сама модель предсказала значение. На рисунке ниже наглядно изображены эти два понятия.
Проблема, о которой думает алгоритм обучения ансамбля, заключается в следующем: можно ли несколько отдельных моделей с большими ошибками и плохими эффектами интегрировать в той или иной форме, чтобы стать общей моделью с меньшими ошибками и лучшими эффектами? Ответ должен быть очевиден: все мы знаем, что народ силен. Идея заключается в том, что даже если индивидуальная модель предсказывает неправильно, есть другие модели, которые могут это исправить.Как говорится, три сапожника лучше, чем один Чжугэ Лян.
С точки зрения формы интеграции ее можно в основном разделить на две категории: одна — это метод параллельной интеграции моделей с пакетированием, а другая — метод бустинга последовательной интеграции моделей. Что касается того, почему производительность может быть улучшена с помощью этой формы интеграции, какова теоретическая основа? Это может быть получено из взаимосвязи между общим ожиданием и дисперсией модели, а также дисперсией и смещением отдельной модели, и может быть получен строгий математический вывод и доказательство, которые не будут здесь подробно излагаться.
случайный лес
Случайный лес, модельный алгоритм, основанный на методе мешков, который объединяет вместе несколько деревьев решений. Основная идея алгоритма состоит в том, чтобы использовать среднее значение нескольких (с низким смещением и высокой дисперсией) отдельных моделей, чтобы уменьшить общую дисперсию метода обучения. Структура алгоритма случайного леса показана на следующем рисунке.
Процесс построения случайного леса выглядит следующим образом:
1. 把原始集上随机只采样N份样本数据集，且每份样本数据集随机只采样M个特征，得到若干份数据集
2. 在每个数据集上独立构建一颗决策树，得到N颗决策树
Процесс использования случайного леса выглядит следующим образом:
1. 把待预测的样本数据，输入到N个决策数，得到N个预测结果
2. 对这些预测结果，以投票(分类)或平均(回归)的计算方式最终结果
Видно, что в случайном лесу построение (обучение) каждого дерева решений является независимым, и зависимости между ними нет. Просто в конечном использовании (прогноз) должны быть пропущены результаты всех деревьев в лесу, а окончательное решение будет дано путем голосования или усреднения.
Дерево решений с градиентным усилением
GBDT (Gradient Boosting Decision Tree) для краткости, алгоритм, который последовательно объединяет несколько деревьев решений на основе повышения для обучения и обучения. Его основная идея алгоритма основана на остаточном обучении с помощью нескольких (с низкой дисперсией и высоким отклонением) отдельных моделей. метод обучения, который накладывает и суммирует, чтобы уменьшить общую погрешность.
Предполагая, что истинное значение выборки X равно 30, остаточная ошибка между результатом прогнозирования модели 1 и истинным значением равна 10. Чтобы исправить этот остаток, образец X необходимо отправить в модель 2, но в это время целью обучения модели 2 является не истинное значение самого образца, 30, а текущий остаток 10. На данный момент, после добавления модели 1 и модели 2, остаток был уменьшен с 10 до 4. При повторном обучении модели 3 и модели 4 общий остаток будет становиться все меньше и меньше, а общий результат представляет собой сумму всех выходных данных модели.Ниже представлена схематическая диаграмма процесса обучения GBDT.
Можно видеть, что это полностью отличается от метода случайного леса. Первые модели не зависят друг от друга, пока подмодели обучаются индивидуально одна за другой. Последняя модель имеет зависимую связь между передней и задней частью и должна обучаться последовательно после обучения предыдущего дерева. Как реализовать такой алгоритм обучения? GBDT является таким алгоритмом обучения, и его схема кадра выглядит следующим образом:
Построение целевой функции
Мы знаем, что для задачи обучения модели логистической регрессии целью оптимизации является минимизация функции потерь кросс-энтропии (CrossEntropy):
Поскольку эта функция является выпуклой функцией, проблема решения этого минимального значения относительно проста. Пока итерационный параметр W приближается к экстремальному значению с помощью метода градиентного спуска, функция потерь перекрестной энтропии может быть минимизирована. Итак, для проблемы обучения аддитивной модели, такой как повышение, ее цель оптимизации или функция потерь, как должна выглядеть эта функция и как она устроена?
Чтобы определить функцию потерь, первым шагом является определение того, как модель выводит прогнозируемые значения. Предполагая, что обучено K деревьев, текущее прогнозируемое значение для i-й выборки равно:
Тогда целевая функция может быть построена следующим образом:
Правая часть выражения представляет собой обычный термин, который используется для управления сложностью структуры модели.В модели дерева решений количество конечных узлов дерева, значение конечных узлов и глубина дерево обычно используется для его определения. Сосредоточьтесь на функции потерь слева, как найти ее минимальное значение. Далее разберите функцию потерь и осуществите параметризацию функции потерь: предположим, что существуют K-деревья, предыдущие деревья K-1 были обучены, и сейчас нужно обучить K-е дерево. для входных образцов,Как показано ниже:
Тогда целевая функция может быть упрощена до
При обучении дерева K были определены первые деревья K-1, поэтомуможно рассматривать как константу,
Это не имеет никакого отношения к K-му дереву, поэтому целевая функция на данный момент такова:
Целевую функцию все еще трудно оптимизировать, и ряд Тейлора используется для аппроксимации
Расширение Тейлора сохраняет только первые два порядка, и целевая функция может быть записана как:
Оптимизированный целевой параметр теперь, так что с
Ненужные элементы можно удалить. сделать
и
за
о
Первая и вторая производные от , поскольку первые деревья К-1 были обучены, эти два значения можно вычислить и считать известными.
Таким образом, целевая функция упрощается до:
Решение оптимальных параметров дерева
Выходная функция f дерева решений может быть определена следующим образом:, где q(x) — позиционная функция, указывающая, что выборка x попадет в позицию дерева (количество листовых узлов),
Представляет значение j-го листа. в то время как функция ограничения древовидной структуры
, что связано со значением W листьев и количеством листьев T, которые контролируются двумя гиперпараметрами:
Таким образом, целевая функция упрощается до:
В случае определения формы дерева при обходе формы организации выборки набор выборок на листе может быть разделен и пройден один за другим. Например, на следующем рисунке выборка {1,2} на листовом узле 1 является первой. , а затем лист соединяется с 2 на {3, 5}, как показано ниже:
Представляет набор образцов на листовом узле j.,
Тогда целевую функцию можно записать в следующем виде:
заказать снова, обе из которых являются константами, когда форма дерева детерминистически известна. В этой точке имеется только один параметр W, а целевая функция в этот момент становится простейшей одномерной квадратичной функцией, крайнюю точку которой можно вычислить непосредственно по общей формуле решения.
Оптимальное решение по форме дерева
Данные для обучения ограничены, а форма дерева не ограничена. Существует бесконечно много форм деревьев, и эти тренировки можно поместить в их листовые узлы. Поиск оптимального варианта здесь на самом деле является типичной NP-сложной задачей, и ее трудно оптимизировать напрямую. Более того, форму дерева сложно определить как непрерывную функцию, и нет условия использовать для ее решения градиентный спуск. Итак, как решить эту проблему? Подобно алгоритму построения дерева решений, следуйте идее жадного алгоритма, пройдитесь по всем функциям, найдите текущий оптимальный метод деления функций F и определите оптимальную форму дерева.
Как показано на рисунке выше, предполагая, что дерево решений было разделено на две конечные точки (в линии прямоугольника), должны ли мы продолжать разбивать функцию F в это время, какой способ выбрать лучше всего?
Следовательно, дерево, сформированное методом деления признаков F, делаетМаксимизация — это текущая оптимальная форма дерева. Для удобства реализации алгоритма мы ограничили форму деления признаков: на каждом шаге операции деления листовых узлов можно разделить только два левых и правых листовых узла, чтобы дерево было бинарным. Итак, в итоге есть:
Цитировать
XGBoost: масштабируемая система повышения дерева, KDD 2016 ChenTianqi
【Машинное обучение】Дерево решений (средний уровень)zhuanlan.zhihu.com/p/86263786