Приветствую всех вСообщество облачных технологий Tencent, получить больше крупной технической практики Tencent по галантерее~
автор:Ван Исюн
ВведениеВ этой статье используется простой для понимания язык и примеры для объяснения трех распространенных алгоритмов дерева решений, их плюсов и минусов, а также значения случайного леса.Я считаю, что это может помочь новичкам по-настоящему понять соответствующие знания.
Древо решений
введение
Дерево решений — очень распространенный метод классификации в машинном обучении, а также можно сказать, что это самый интуитивно понятный и понятный алгоритм среди всех алгоритмов. Сначала возьмем самый простой пример:
А: Ты будешь есть?
Б: Я пойду, если ты пойдешь.
«Если ты пойдешь, я пойду» — это типичная идея дерева решений.
Другой пример:
Кто-то попросил меня одолжить денег (конечно, вряд ли...), одолжить или не одолжить? Я буду комбинировать три характеристики: есть ли у меня деньги, использую ли я их или нет, и хороша ли кредитоспособность другой стороны, чтобы определить свой ответ.
Давайте обратимся к более общей перспективе.Для некоторых характеристических данных, если мы можем иметь такое дерево решений, мы можем легко предсказать вывод выборки. Таким образом, проблема заключается в том, как найти подходящее дерево решений, то есть как отсортировать эти признаки.
Перед сортировкой признаков представьте, что, принимая решение по признаку,Мы определенно надеемся, что чем выше чистота классифицируемых образцов, тем лучше, то есть образцы узлов-ветвей максимально принадлежат к одной категории.
Поэтому при выборе корневого узла мы должны выбрать функцию, которая может сделать «узел ответвления с наивысшей чистотой». После обработки корневого узла продолжайте рекурсивно применять идею корневого узла для его узлов ветвления, чтобы можно было сформировать дерево. На самом деле это основная идея жадного алгоритма. Так как же количественно определить «высшую чистоту»? Энтропия является наиболее распространенной мерой чистоты. Его математическое выражение выглядит следующим образом:
Среди них N представляет, сколько возможных значений имеет вывод, p представляет вероятность появления при взятии k-го значения, а для выборки это частота/общее количество событий.
Чем меньше энтропия, тем чище образец.
Проиллюстрируем это изображением функции энтропии двухточечной выборки распределения X (x=0 или 1), абсцисса представляет вероятность того, что значение выборки равно 1, а ордината представляет собой энтропию.
Можно видеть, что когда p(x=1)=0, то есть все выборки равны 0, и энтропия в это время равна 0.
Когда p(x=1)=1, то есть все выборки равны 1, и энтропия также равна 0.
При p(x=1)=0,5, то есть на 0 и 1 в выборке приходится по половине, энтропия может достигать максимального значения в это время.
В более широком смысле выборка X может принимать n видов значений (x1...xn). Можно доказать, что когда p(xi) равно 1/n, то есть выборка абсолютно однородна, энтропия может достигать максимума. Когда одно из p(xi) равно 1, а остальные равны 0, то есть все значения выборки равны xi, а энтропия наименьшая.
алгоритм дерева решений
ID3
Предполагая, что в выборке X для признака a он может иметь (a1, a2...an) эти значения, если выборка X делится на признак a (он считается корневым узлом), то должно быть n узлом ответвления. Как только что упоминалось, мы надеемся, что после деления чем чище образец узла ветвления, тем лучше, то есть чем меньше «полная энтропия» узла ветвления, тем лучше.
Поскольку количество узлов каждой ветви различно, мы должны сделать взвешивание при вычислении «общей энтропии», предполагая, что количество выборок i-й вершины равно W(ai), а ее вес во всех выборках равен W(ai). / W(X). Таким образом, мы можем получить полную энтропию:
Эта формула представляет смысл предложения:Сумма энтропии каждого узла после взвешивания. Чем меньше должно быть это значение, тем выше чистота.
На этот раз мы вводим термин, называемый приростом информации G(X, a), который означает улучшение информации, привносимой в выборку функцией a. Формула:, так как H(X) является фиксированным значением для выборки, прирост информации G должен быть как можно больше.Найдите функцию, которая максимизирует получение информации в качестве целевого узла, и рекурсивно постройте дерево шаг за шагом., это идея алгоритма ID3,
Что ж, простой пример для иллюстрации расчета прироста информации:
В приведенном выше примере я рассчитываю информационный прирост функции 1.
Сначала вычислите энтропию H (X) образца
Затем вычислите общую энтропию, вы можете видеть, что функция 1 имеет 3 узла A, B, C, которые равны 6, 6 и 5 соответственно.
Таким образом, вес A равен 6/(6+6+5), вес B равен 6/(6+6+5), а вес C равен 5/(6+6+5).
Поскольку мы надеемся, что чем выше чистота разделенных узлов, тем лучше, поэтому нам нужно вычислить энтропию узлов A, B и C отдельно.
Признак 1=A: 3 да, 3 нет, его энтропия равна
Признак 1=B: 2 да, 4 нет, его энтропия равна
Признак 1=C: 4 да, 1 нет, его энтропия равна
Тогда полная энтропия узла ветвления равна:
Прирост информации по признаку 1 равен 0,998-0,889=0,109.
Точно так же мы можем также рассчитать прирост информации от других функций и, наконец, взять функцию с наибольшим приростом информации в качестве корневого узла.
Приведенный выше расчет также может быть получен из эмпирической условной энтропии: G (X, A) = H (X) - H (X | A) Заинтересованные студенты могут узнать об этой части.
C4.5
На самом деле в алгоритме ID3 есть очевидная проблема.
Если есть набор образцов, который имеет (уникальную) функцию, называемую идентификатором или именем, это все. Представьте, что если есть n выборок, то признак id обязательно разделит выборку на n частей, то есть узлов n, каждый узел имеет только одно значение, а энтропия каждого узла равна 0. То есть суммарная энтропия всех узлов ветвления равна 0, тогда информационный прирост этого признака должен достигать максимального значения. Следовательно, если в настоящее время в качестве алгоритма дерева решений используется ID3, корневой узел должен быть свойством id. Но очевидно, что это неразумно. . .
Конечно, описанное выше является предельным случаем.В общем случае, если признак слишком разрежен для деления выборки, это также неразумно (другими словами, он смещается в сторону признаков с большим количеством значений). Для решения этой проблемы,Алгоритм C4.5 использует скорость получения информации в качестве критерия выбора признаков..
Так называемая скорость прироста информации основана на приросте информации в дополнение к расщепленной информации, чтобы наказывать атрибуты с большей ценностью.
И эта разделенная информация на самом деле является энтропией H(A) числа признаков.
Почему это можно уменьшить, разберемся на примере id выше. Если id делит n выборок на n частей, то вероятность значения признака id равна 1/n Как упоминалось во введении статьи, когда выборки абсолютно однородны, энтропия наибольшая.
Таким образом, эта ситуация характеризуется id.Хотя прирост информации является самым большим, информация о расщепленном коэффициенте штрафа также является самой большой, чтобы уменьшить скорость ее усиления, что является идеей C4.5.
CART
Цель деревьев решений, в конечном счете, состоит в том, чтобы найти количественный стандарт чистоты различных образцов. В дереве решений CART в качестве эталона измерения используется индекс Джини. Интуитивное понимание коэффициента Джини состоит в том, что из множества случайным образом выбираются две выборки, и чем чище выборка, тем меньше вероятность получения разных выборок. Эта вероятность отражает коэффициент Джини.
Итак, если выборка имеет K категорий. Предполагая, что некоторая характеристика a выборки имеет n значений, вероятность того, что узел возьмет другую выборку, равна:
Итак, сумму вероятностей k классов мы называем коэффициентом Джини:
Индекс Джини представляет собой взвешенную обработку коэффициентов Джини всех узлов.
После расчета мы выберем признак с наименьшим коэффициентом Джини в качестве оптимального признака разбиения.
обрезка
Цель обрезки на самом деле состоит в том, чтобы предотвратить переоснащение, что является наиболее важным средством предотвращения переоснащения деревьев решений. В дереве решений, чтобы попытаться максимально классифицировать обучающие выборки, наше дерево решений всегда будет расти. Однако иногда обучающие образцы могут обучаться настолько хорошо, что уникальные свойства некоторых образцов рассматриваются как общие свойства. В это время нам нужно активно удалять некоторые ветки, чтобы снизить риск переобучения.
Как правило, существует два типа обрезки: предварительная обрезка и постобрезка.
Предварительная обрезка
Как правило, дерево перестает расти, пока выборка узла чиста на 100%. Но это может привести к переобучению, поэтому нам не нужно увеличивать его на 100%, поэтому перед этим установите некоторые условия завершения, чтобы завершить его раньше. Это называется предварительной обрезкой, и этот процесс происходит до создания дерева решений.
Как правило, наши методы предварительной обрезки:
1. Ограничьте глубину дерева
2. Количество дочерних узлов узла меньше порога
3. Установите порог энтропии узла
и Т. Д.
после обрезки
Как следует из названия, эта обрезка выполняется после процесса построения дерева решений. Существует множество алгоритмов алгоритма пост-обрезки, некоторые из которых весьма эзотеричны, здесь я не буду углубляться в идею простого алгоритма.
Reduced-Error Pruning (REP)
Этот метод обрезки рассматривает каждый узел в дереве как кандидата на отсечение, но есть некоторые условия, чтобы решить, следует ли отрезать, обычно это следующие шаги:
1. Удалите все его поддеревья и сделайте их листовыми узлами.
2. Дайте узлу наиболее релевантную категорию
3. Используйте данные проверки, чтобы проверить их точность и сравнить их с данными перед обработкой.
Если оно не хуже исходного, его поддерево фактически удаляется. Затем итеративно обработайте узлы снизу вверх. Этот метод обработки фактически предназначен для борьбы с этими «вредными» узлами.
случайный лес
На самом деле теория случайного леса не должна заниматься самим деревом решений, а дерево решений можно использовать только как алгоритм своих идей.
Зачем вводить случайные леса? Мы знаем, что с одним и тем же пакетом данных мы можем сгенерировать только одно дерево решений, и это изменение относительно простое. Как насчет комбинации нескольких алгоритмов?
Это приводит к концепции ансамблевого обучения.
Как видно на рисунке, каждый отдельный ученик (слабый ученик) может содержать алгоритм, который может быть одинаковым или различным. Если это одно и то же, мы называем это гомогенной интеграцией, в противном случае — гетерогенной.
Случайный лес — это частный случай ансамблевого обучения с использованием стратегии на основе мешков.
Как видно из приведенного выше рисунка, обучающая выборка отдельных обучающихся бэггингу получается методом случайной выборки. Через n случайных выборок мы можем получить n выборок. Для этих n выборочных наборов мы можем независимо обучить n отдельных учащихся, а затем использовать коллективную стратегию для получения окончательного результата для этих n отдельных учащихся.Эти n отдельных учащихся независимы друг от друга, могут быть распараллелены.
Примечание: есть еще один способ интегрированного обучения, называемый бустингом, в этом случае существует сильная корреляция между учащимися, если вам интересно, вы можете узнать об этом.
Метод выборки, используемый случайным лесом, обычно представляет собой выборку Bootstap, Для исходного набора выборок мы случайным образом собираем выборку и каждый раз помещаем ее в набор выборки, а затем возвращаем ее, то есть образец все еще может быть собран в следующей выборке.Выборочная совокупность получается после определенного количества проб. Из-за случайной выборки каждый набор выборок отличается от исходного набора выборок и других наборов выборок, поэтому полученные отдельные учащиеся также отличаются.
Основная проблема случайного леса заключается в том, что есть n результатов, как установить стратегию комбинации, основные методы следующие:
Средневзвешенный метод:
Метод усреднения часто используется для регрессии. Метод заключается в том, чтобы сначала установить заранее установленный вес wi для каждого учащегося,
Тогда окончательный вывод:
Когда веса всех учащихся равны 1/n, этот метод усреднения называется простым методом усреднения.
способ голосования:
Метод голосования аналогичен голосованию в нашей жизни, если веса каждого ученика одинаковы.
Затем идет метод абсолютного голосования, то есть более половины голосов. При относительном голосовании меньшинство подчиняется большинству.
Если есть взвешивание, то меньшинство все равно подчиняется большинству, но здесь цифры взвешены.
пример
Давайте посмотрим на код простой квадратичной функции, чтобы увидеть, как используются деревья решений.
Учебные данные представляют собой 100 случайных данных в реальном квадрате, разные глубины будут иметь разные кривые.
Тестовые данные также являются случайными данными, но модели деревьев с разной глубиной дают разные прогнозируемые значения. Как показано
Код для этого изображения выглядит следующим образом:
Моя среда - python 3.6. Мне нужно установить три библиотеки numpy, matplotlib и sklearn. Если необходимо, установите pip напрямую. Вы можете запустить и посмотреть. Это просто, но интересно.
#!/usr/bin/python
# -*- coding:utf-8 -*-
import numpy as np
import matplotlib as mpl
import matplotlib.pyplot as plt
from sklearn.tree import DecisionTreeRegressor
if __name__ == "__main__":
# 准备训练数据
N = 100
x = np.random.rand(N) * 6 - 3
x.sort()
y = x*x
x = x.reshape(-1, 1)
mpl.rcParams['font.sans-serif'] = ['SimHei']
mpl.rcParams['axes.unicode_minus'] = False
# 决策树深度及其曲线颜色
depth = [2, 4, 6, 8, 10]
clr = 'rgbmy'
# 实际值
plt.figure(facecolor='w')
plt.plot(x, y, 'ro', ms=5, mec='k', label='实际值')
# 准备测试数据
x_test = np.linspace(-3, 3, 50).reshape(-1, 1)
# 构建决策树
dtr = DecisionTreeRegressor()
# 循环不同深度情况下决策树的模型，并用之测试数据的输出
for d, c in zip(depth, clr):
# 设置最大深度（预剪枝）
dtr.set_params(max_depth=d)
# 训练决策树
dtr.fit(x, y)
# 用训练数据得到的模型来验证测试数据
y_hat = dtr.predict(x_test)
# 画出模型得到的曲线
plt.plot(x_test, y_hat, '-', color=c, linewidth=2, markeredgecolor='k', label='Depth=%d' % d)
# 一些画图的基本参数
plt.legend(loc='upper center', fontsize=12)
plt.xlabel('X')
plt.ylabel('Y')
plt.grid(b=True, ls=':', color='#606060')
plt.title('二次函数决策树', fontsize=15)
plt.tight_layout(2)
plt.show()использованная литература
Машинное обучение Чжоу Чжихуа
Курс машинного обучения Бо Цзоу
Связанное Чтение
Машинное обучение: от новичка до первой модели
Эта статья была разрешена автором для публикации в сообществе Tencent Cloud Technology Community, укажите это при перепечатке.Источник статьи
Оригинальная ссылка: https://www.qcloud.com/community/article/160232