Деревья решений

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

Дерево решений строится сверху вниз, жадно решая, какой фактор будет лучше всего использовать для классификации выборок, доступных в каждом узле. Существуют различные меры для определения того, насколько хорошо функция может быть классифицирована. Один из них Джини. Индекс Джини/примесь расщепления рассчитывается как средневзвешенное значение примесей двух классов, полученных после расщепления. Чем меньше примесь Джини, тем лучше признак для классификации.

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

Ветки узла с данными из дискретного упорядоченного набора можно сделать таким же образом.

Иногда примесь Джини может увеличиваться, когда мы решаем разбить узел дальше, если это так, мы просто делаем его листовым узлом.

Если у нас отсутствуют данные о признаке, мы можем заполнить его средним значением этого признака или найти сильно коррелированный признак и заполнить его в соответствии с ним.

Случайный лес

  1. Создайте набор данных с начальной загрузкой, выбрав случайным образом n выборок из исходных данных (где n — размер исходного набора данных). Не все образцы будут заканчиваться вашими данными начальной загрузки. Кроме того, он может содержать повторяющиеся образцы. Образцы, которые не попадают в загрузочные данные, называются данными «из коробки».
  2. Теперь составьте дерево решений, но на каждом этапе разделения узлов в дереве решений рассматривайте только случайное подмножество признаков как признаков, которые можно использовать для разделения этого узла. В обычном дереве решений вы бы рассмотрели все функции, чтобы разделить узел.
  3. Повторите шаги 1 и 2 много раз.

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

Вышеописанный процесс известен как «упаковка» = (Bootstrap+aggregating)

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

Для заполнения недостающих данных мы:

  1. сделать первоначальные оценки, используя методы, рассмотренные ранее.
  2. Затем мы делаем матрицу близости образцов. Значение близости двух выборок определяется как количество деревьев, в которых эти две оказались в одном конечном узле, деленное на общее количество деревьев в случайном лесу.
  3. Теперь мы получаем новое значение для нашего первоначального предположения о признаке fвыборки s, взяв среднее значение всех других выборок признака f, взвешиваются в соответствии с их близостью к s.
  4. Повторите еще раз, чтобы получить более точную оценку.

Мы также можем использовать значение (1-близость) в качестве меры расстояния между выборками.

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

Регрессия

Это тип дерева решений, в котором каждый лист представляет числовое значение, а не метку класса.

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

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

Если есть несколько предикторов/функций, скажем, для прогнозирования эффективности лекарства, а не только один (дозировка лекарства), вы можете найти оптимальный порог, соответствующий каждому из этих предикторов/функций, и выбрать пару (функция, оптимальный порог) что дает минимальную сумму квадратов остатков (SSR). В случае, если функция является бинарной, ее все равно можно рассматривать как поиск оптимального порога, при этом доступен только один порог.

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

По мере того, как мы увеличиваем штраф за сложность дерева, оптимальными становятся все меньшие и меньшие деревья. Итак, чтобы найти штраф, мы проверяем (путем вычисления SSR) все обрезанные деревья в наборе проверки и выбираем значение альфа, которое приводит к минимальной оценке дерева для дерева с минимальным SSR. Мы также можем сделать это с помощью перекрестной проверки.

АдаБуст

  1. Присвойте каждому образцу вес , указывающий, насколько важно для текущей культи правильно классифицировать ее. Изначально всем присваивается равный вес.
  2. Сделайте культи на основе каждой функции, чтобы классифицировать все выборки в данных. Выберите тот, который приводит к минимальному взвешенному индексу Джини. Взвешенный индекс Джини аналогичен индексу Джини, но предполагает, что вероятность появления выборки равна ее весу.
  3. Вычислите общую ошибку для этого пня. Суммарная ошибка для пня представляет собой сумму весов неправильно классифицированных образцов. Количество скажем пня определяется как:

4. Обновите веса неправильного образца следующим образом:

5. Обновите веса для правильно классифицированных образцов следующим образом:

6. Нормируйте новые веса выборки.

7. Повторите вышеуказанный процесс.

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

Повышение градиента

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

В отличие от AdaBoost, деревья здесь не пни, а ограничены количеством листьев, обычно от 8 до 32. Каждый лист содержит выборочное среднее выходных значений всех назначенных ему выборок.

Для любой общей функции потерь алгоритм повышения градиента работает следующим образом:

Связывание направлений движений и расчет оптимального размера шага — вот что отличает этот алгоритм от градиентного спуска.

Если мы пытаемся использовать повышение градиента для двоичной классификации, наш первоначальный прогноз будет X = Sigmoid (логарифмические шансы класса == 1). Это считается вероятностью того, что образец принадлежит классу 1. Но в действительности образцы, имеющие метку класса 1, имеют вероятность быть в классе 1, как 1, а образцы, имеющие метку класса 0, имеют вероятность быть в классе 1, как 0 , Таким образом, теперь мы можем сделать остатки, поскольку у нас есть фактические вероятности (0/1) и предсказанные (X).

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

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

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

XGBoost

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

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

«Прибыль» разделения определяется как сумма сходств разделенных узлов за вычетом сходства исходного узла до его разделения. Мы также можем обрезать дерево, удалив разбиения (восходящим образом), которые не привели к выигрышу, превышающему пороговое значение (известное как гамма).

Мы строим несколько деревьев, каждое из которых учится на остатках предыдущих. Мы также умножаем каждое последующее дерево на скорость обучения (известную как эта), прежде чем складывать результаты.

В случае, если мы решаем проблему классификации, мы заставляем наши деревья предсказывать вероятности, а не классы. Начальная оценка по умолчанию сделана равной 0,5 (мы можем ее изменить), что соответствует логарифму (коэффициенты) = 0. Показатели сходства узла рассчитываются как:

Остатки по-прежнему рассчитываются, как и раньше, а узлы разделяются, как и раньше. Точкам выборочных данных присваиваются вероятности 0 или 1 в зависимости от того, что есть на выходе. Среднее значение различных выборок, которые попадают в один и тот же листовой узел, берутся так же, как и в Gradient Boost, т. е. следующим образом:

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

«обложка» (параметр min_child_weight) определяется как знаменатель показателя сходства минус лямбда. XGBoost разрешает только ветки с покрытием>некоторое минимальное значение (по умолчанию 1).

Приведенная выше формула (A) и аналогичная формула для регрессии ((сумма остатков в листе/(общее количество остатков + лямбда)) являются результатом нахождения результата, который минимизирует следующую функцию:

Результат должен быть получен с помощью разложения L в ряд Тейлора. Для любой общей функции потерь значение, которое минимизируется, задается как:

Показатель сходства может быть выражен как:

Следовательно, покрытие также можно рассматривать как сумму Гессиана.

Оптимизация XGBoost

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

В случае отсутствия данных функции f XGBoost разбивает данные на выборки со значением для f и без него; при попытке разделить узел в соответствии с f. Далее процедура проводится как обычно, без семплов с пропущенным значением, но в конце мы пытаемся поместить все оставшиеся семплы в каждую из двух ветвей(все семплы в одну ветвь за раз), усиления рассчитываются для всех случаев, со всеми возможными разбиениями корневого узла и двумя возможными размещениями выборок с пропущенными значениями. Случай с максимальным усилением выбирается как расщепленный. Это известно как «Раздельный поиск с учетом разреженности».

Рекомендации

Вышеупомянутое содержание является кратким изложением этих видео по вышеуказанной теме от StatQuest.