Деревья решений и ансамблевые методы для машинного обучения

машинное обучение искусственный интеллект алгоритм

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

теория информации

Алгоритмы ID3 и c4.5 в деревьях решений основаны на теории информации Шеннона.Что такое информационная энтропия?
Энтропия Шеннона: при заданном распределении вероятностей P и экземпляре S информационная энтропия может быть рассчитана следующим образом:
$Entropie(P) =-\sum_{i=1}^{n}p_i * log(p_i)$

Получение информации G(P, T): Дерево решений классифицируется путем нарезки и оценки различных признаков. Так как же решить, какая функция больше подходит? Прирост информации можно использовать для измерения степени смешения всех признаков выборки, а также можно выбрать те признаки, которые более хаотичны (энтропия относительно велика), которые можно отличить по суждению о меньшем. Рассчитывается следующим образом:
$Gain(p, T) = Entropie(P) - \sum_{i=1}^{n}(p_i * Entropie(p_i))$
pi представляет вероятность появления в T-признаке.

Ниже приведен простой расчет на примере:

In [2]: 
import numpy as np
import pandas as pd
In [24]: 
outlook = np.array(['sun', 'sun', 'overcast', 'rain', 
                    'rain','rain','overcast','sun',
                    'sun','rain', 'sun',  'overcast',
                    'overcast', 'rain'])
temperature = np.array(['hot', 'hot', 'hot', 'sweet', 
                        'cold','cold', 'cold', 'sweet',
                        'cold', 'sweet','sweet','sweet',
                        'hot', 'sweet'])
humidity = np.array(['high', 'high', 'high', 'high', 
                    'normal', 'normal', 'normal', 'high',
                    'normal', 'normal', 'normal', 'high',
                    'normal', 'high'])
wind = np.array(['low', 'high', 'low', 'low', 
                'low', 'high', 'high', 'low', 
                'low', 'low', 'low', 'high', 
                'low', 'high'])
label_play = np.array(['no', 'no', 'yes', 'yes', 
                      'yes', 'no', 'yes', 'no',
                      'yes','yes','yes','yes',
                      'yes', 'no'])
tree_df = pd.DataFrame({
    'outlook':outlook,
    'temperature':temperature,
    'humidity':humidity,
    'wind':wind,
    'play':label_play,
})
tree_df = tree_df[['outlook', 'temperature','humidity', 'wind', 'play']]
tree_df
Out[24]:
outlook temperature humidity wind play
0 sun hot high low no
1 sun hot high high no
2 overcast hot high low yes
3 rain sweet high low yes
4 rain cold normal low yes
5 rain cold normal high no
6 overcast cold normal high yes
7 sun sweet high low no
8 sun cold normal low yes
9 rain sweet normal low yes
10 sun sweet normal low yes
11 overcast sweet high high yes
12 overcast hot normal low yes
13 rain sweet high high no

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

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

In [25]: 
# 定义简单的熵计算函数：
def entropy(label_set):
    return -np.sum(label_set * np.log2(label_set))
In [30]: 
# 全集S的熵：
entropy_s = entropy([9/14, 5/15]) # 两个类别
entropy_s
Out[30]: 
0.9380972111121206
In [31]: 
# 计算每个特征的信息增益：
tree_df[['outlook', 'play']]
Out[31]:
outlook play
0 sun no
1 sun no
2 overcast yes
3 rain yes
4 rain yes
5 rain no
6 overcast yes
7 sun no
8 sun yes
9 rain yes
10 sun yes
11 overcast yes
12 overcast yes
13 rain no

Как и выше, особенности прогноза делятся на 3 категории, а вероятность их появления составляет 5/14, 4/14 и 5/14.

In [43]: 
for attr in ['outlook', 'temperature', 'humidity', 'wind']:
    print(tree_df.groupby([attr, 'play']).size())
    print('-' * 30)

outlook   play
overcast  yes     4
rain      no      2
          yes     3
sun       no      3
          yes     2
dtype: int64
------------------------------
temperature  play
cold         no      1
             yes     3
hot          no      2
             yes     2
sweet        no      2
             yes     4
dtype: int64
------------------------------
humidity  play
high      no      4
          yes     3
normal    no      1
          yes     6
dtype: int64
------------------------------
wind  play
high  no      3
      yes     2
low   no      2
      yes     7
dtype: int64
------------------------------
In [46]: 
# 其中每个类别对应的play情况如上， 因此信息增益如下计算：
gain_s_outlook = entropy_s - 4/14 * entropy([1]) - 5/14*entropy([2/5, 3/5]) - 5/14*entropy([3/5, 2/5])
# 同样方法可以计算出另外两个特征的信息增益
gain_s_temperature = entropy_s - 4/14*entropy([1/4, 3/4]) - 4/14 * entropy([2/4, 2/4]) - 6/14*entropy([2/6, 4/6])
gain_s_humidity = entropy_s - 7/14 * entropy([4/7, 3/7]) - 7/14 * entropy([1/7, 6/7])
gain_s_wind = entropy_s - 5/14*entropy([3/5, 2/5]) - 9/14 * entropy([2/9, 7/9])
In [48]: 
# 4个特征的信息增益计算完毕，选组最大的特征作为根节点进行切分
gain_s_outlook, gain_s_humidity, gain_s_wind, gain_s_temperature
Out[48]: 
(0.24456107221592882,
 0.14964675380383113,
 0.10005481605134026,
 0.027033818100444362)

После выбора Outlook в качестве корневого узла для разделения он делится на 3 ветви. Облачная ветвь больше не нуждается в оценке. Оставшиеся две ветви делятся таким же образом до тех пор, пока их больше нельзя будет разделить. Это процесс вычисления алгоритма ID3. Недостатки: как подсчитано выше, если предположить, что в Outlook 14 категорий, прирост информации, конечно, самый большой, и его следует выбрать в качестве сегментации корневого узла, но это не обязательно лучшая функция сегментации в настоящее время, потому что она не имеет возможности обобщать. В это время коэффициент усиления информации выбирается для улучшения.

коэффициент усиления информации

Его можно рассчитать по следующей формуле:
$gainratio(p, T) = \frac{Gain(P, T)}{splitinfo(p, T)}$
$splitinfo(p, T) = -\sum_{j=1}^{n}p^`(\frac{j}{p}) * log(p^`(\frac{j}{p}))$
Вышеупомянутый процесс рассчитывается в дополнение к числителю, далее в основном вычисляется знаменатель, а именно:

In [87]: 
splitinfo_s_outlook = entropy([5/14, 5/14, 4/14])
splitinfo_s_temperature = entropy([4/14, 4/ 14, 6/14])
splitinfo_s_humidity = entropy([7/14, 7/14])
splitinfo_s_wind = entropy([5/14, 9/14])

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

In [88]: 
print(gain_s_outlook / splitinfo_s_outlook)
print(gain_s_temperature / splitinfo_s_temperature)
print(gain_s_humidity / splitinfo_s_humidity)
print(gain_s_wind / splitinfo_s_wind)

0.15504000134556406
0.017366589544657203
0.14964675380383113
0.10640892286937578

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

После приведенных выше расчетов два приведенных выше дерева решений имеют следующие характеристики:

  1. Обработка отсутствующих значений Если некоторые функции имеют небольшое количество отсутствующих значений, дерево решений вычисляет коэффициент прироста информации, например, значение в приведенной выше функции прогноза отсутствует, но вычисленные результаты не сильно отличаются, поэтому может обрабатывать данные с небольшим количеством пропущенных значений.
  2. Функции непрерывной строки В отличие от ID3, который может обрабатывать только категориальные данные, C4.5 также может обрабатывать непрерывные данные. Метод заключается в том, чтобы удалить значение в середине непрерывных данных, разделить признак на две категории, а затем рассчитать коэффициент прироста информации, а также выбрать максимальное значение для сегментации.
  3. Сокращение генерирует дерево решений из обучающего набора, которое обычно соответствует данным и чувствительно к некоторым значениям шума. Для повышения точности дерево необходимо обрезать. Сокращение — это метод уменьшения размера дерева решений путем удаления частей дерева, которые обеспечивают несколько экземпляров классификации.
    Обрезка деревьев решений

Сравнение алгоритмов ID3 ​​и C4.5

Алгоритм ID3 выбирает оптимальную функцию сегментации для построения дерева на основе энтропии и прироста информации. А C4.5 похож на ID3, но добавляет некоторые возможности:

  • Можно использовать непрерывные данные
  • Может содержать небольшое количество пропущенных значений
  • Возможность использовать атрибуты с разным весом
  • Постобрезка после создания дерева (ошибка пессимистического прогноза 0,5, поддерево поднимается)
In [ ]:

CART

В отличие от первых двух алгоритмов, алгоритм дерева классификации CART использует коэффициент Джини для замены коэффициента прироста информации. Коэффициент Джини представляет собой примесь модели. Чем меньше коэффициент Джини, тем меньше примесь и тем лучше характеристики. Это противоположно получению информации (коэффициенту). В задаче классификации, предполагая наличие n категорий, вероятность равна pn, а метод расчета следующий:
$Gini(p)=\sum_{i=1}^{n}(p_i * (1 - p_i)) = 1 - \sum_{i=1}^{n}p_i^2$
В частности, предположим, что выборка D разделена на две части по некоторому признаку A, и ее коэффициент Джини таков:
$Gini(D,A) = \frac{|D_1|}{|D|}Gini(D_1) + \frac{|D_2|}{|D|}Gini(D_2)$

Поэтому CART использует бинарные деревья для построения деревьев решений. Коэффициент Джини можно рассчитать с использованием приведенных выше данных следующим образом:

In [94]: 
def gini(attr_list):
    return 1 - np.sum(np.power(attr_list, 2))
In [112]: 
for attr in ['outlook', 'temperature', 'humidity', 'wind']:
    print(tree_df.groupby([attr]).size())
    print('-' * 30)

outlook
overcast    4
rain        5
sun         5
dtype: int64
------------------------------
temperature
cold     4
hot      4
sweet    6
dtype: int64
------------------------------
humidity
high      7
normal    7
dtype: int64
------------------------------
wind
high    5
low     9
dtype: int64
------------------------------
In [116]: 
# 可以看到不同的特征分为两类， 计算基尼系数，选择较小的值进行切分:
gini_s_outlook = gini([5/14, 5/14,5/14])
gini_s_temperature = gini([4/14, 4/14, 6/14])
gini_s_humidity = gini([7/14, 7/14])
gini_s_wind = gini([5/14, 9/14])
In [117]: 
gini_s_outlook, gini_s_humidity, gini_s_wind, gini_s_temperature
Out[117]: 
(0.6173469387755102, 0.5, 0.4591836734693877, 0.653061224489796)

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

In [ ]:

Комплексный подход

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

бэггинг и случайные леса

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

  1. Выборка с заменой из исходной выборки, выбор n выборок.
  2. Случайным образом выберите k признаков для n образцов, чтобы построить дерево решений.
  3. Повторите m раз, чтобы получить m деревьев решений.
  4. Делайте прогнозы голосования.

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

бустинг и GBDT

Распространенными методами бустинга являются adaboosting и GBDT. Среди них adaboost — это метод проведения следующего обучения с этой важностью за счет увеличения важности экземпляра ошибки обучения в прогнозе. Однако GBDT использует остатки, полученные в результате предыдущего обучения дерева, для следующего обучения и, наконец, добавляет все результаты для получения окончательного результата. Деревья решений в GBDT представляют собой деревья регрессии, а не деревья классификации, которые широко применимы.Недостатком является то, что если классификаторы сериализованы, их трудно обучать параллельно. Общий алгоритм бустинга представляет собой итеративный процесс, и каждое новое обучение направлено на улучшение предыдущих результатов, то есть на улучшение.

Сравнение случайного леса и GBDT

  1. Случайный лес использует идею мешков, а GBDT использует идею повышения, Оба эти метода являются применением идеи бустинга, и оба являются случайной выборкой с заменой. Разница в том, что при бэггинге используется равномерная выборка с заменой, а бустинг выборок в соответствии с частотой ошибок (бустинг инициализирует каждый обучающий пример с равным весом 1/n, а затем использует этот алгоритм для обучения тренировочного набора за t раундов каждый раз После обучения больший вес придается примерам, которые не удалось обучить), потому что точность лучше, чем бэггинг, а также есть разница между параллельным и последовательным.
  2. Случайные леса могут состоять из деревьев регрессии и деревьев классификации, тогда как GBDT может состоять только из деревьев регрессии.
  3. Деревья, составляющие случайный лес, можно генерировать параллельно, а GBDT можно генерировать только последовательно.
  4. Для окончательных выходных результатов случайные леса используют голосование по большинству и т. д., в то время как GBDT накапливает все результаты или взвешивает их вместе.
  5. Случайный лес не чувствителен к выбросам, а GBDT очень чувствителен к выбросам.
  6. Случайный лес одинаково обрабатывает обучающую выборку; GBDT представляет собой ансамбль слабых весовых классификаторов.
  7. Случайный лес повышает производительность за счет уменьшения дисперсии модели, а GBDT повышает производительность за счет уменьшения смещения модели.
In [ ]:
Категории