Эта статья возникла из личного публичного аккаунта:TechFlow, оригинальность это не просто, прошу внимания
СегодняТемы машинного обученияВ статье 22 мы продолжаем тему деревьев решений.
В предыдущей статье был представлен один из самых простых способов построения дерева решений —Алгоритм ID3, то есть каждый раз, когда для разделения данных выбирается функция. Сколько значений у этого признака, то на сколько разветвлений делится Весь процесс построения дерева очень прост. Если вы пропустили предыдущую статью, вы можете просмотреть ее на портале ниже:
Если вы еще не знаете дерево решений, то вы должны зайти и посмотреть
Поскольку у нас уже есть алгоритм ID3 для реализации деревьев решений, зачем нам новый алгоритм? Очевидно, что необходимо провести некоторые оптимизации или улучшения, иначе новый алгоритм заведомо бессмысленен. Поэтому, прежде чем изучать новые алгоритмы, нам нужно понять, какие улучшения были сделаны и почему.
Как правило, улучшения основаны наСлабые стороны и недостаткиДа, поэтому давайте сначала рассмотрим некоторые проблемы с алгоритмом ID3.
Одной из самых больших проблем, очевидно, является то, чтоФункции, которые не могут обеспечить непрерывность. Причина, по которой он не может быть обработан, также очень проста, потому что ID3 выбирает не значение признака, а конкретный признак каждый раз, когда он разбивает данные. Вилок столько, сколько значений под этим признаком.Если мы используем непрерывные признаки, например, мы берем диаметр арбуза в качестве признака. Теоретически диаметр каждого арбуза разный, если такие данные закинуть в алгоритм ID3, то он выдаст столько же вилок, сколько и выборок, что заведомо бессмысленно.
На самом деле есть еще один вопрос, который будет скрыт чуть глубже.получение информациииз. Мы используем разницу информационной энтропии до и после деления в качестве прироста информации, а затем выбираем деление, которое приносит наибольший прирост информации. Здесь есть проблема, из-за которой модель будет стремиться выбирать объекты с большим количеством бифуркаций при выборе. В крайних случаях, таких как непрерывные признаки, под каждым признаком имеется только одна выборка, тогда информационная энтропия, вычисляемая таким образом, равна 0, и получаемый таким образом прирост информации очень велик. Это неразумно, потому чтоФункции со многими ответвлениями не обязательно хороши для деления, не обязательно является благоприятным в целом.
Для решения этих двух проблем предлагается усовершенствованная схема, а именно алгоритм С4.5. Строго говоря, это не самостоятельный алгоритм, а улучшенная версия алгоритма ID3.
Давайте посмотрим, как алгоритм C4.5 поочередно решает эти две проблемы.
коэффициент усиления информации
Во-первых, давайте рассмотрим проблему получения информации. Как упоминалось ранее, если мы просто используем прирост информации для фильтрации разделенных функций, легко попасть в ловушку и выбрать функции с большим количеством значений.
В ответ на эту проблему мы можем внести небольшую корректировку, мы изменим прирост информации накоэффициент усиления информации. Так называемый коэффициент прироста информации состоит в том, чтобы разделить прирост информации на информационную энтропию самого нашего подразделения, чтобы получить коэффициент. Для фичи со многими ответвлениями будет велика и собственная информационная энтропия. Поскольку разветвлений много, чистота неизбежно будет очень низкой. Таким образом, мы можем сбалансировать смещение, вызванное бифуркацией признаков, чтобы модель могла сделать более правильный выбор.
Давайте посмотрим на формулу, она действительно очень проста:
Здесь D — наш набор обучающих выборок, a — функция, которую мы выбираем,IV(a) — информационная энтропия распределения этого признака..
Давайте посмотрим на формулу для IV:
Объясните здесь значения, где V — множество всех значений признака а.
Естественно, это пропорция, соответствующая каждому v, так что это формула информационной энтропии признака a.
Обработка непрерывных значений
Алгоритм C4.5 также оптимизирован для непрерывных значений,Непрерывные значения поддерживаются, поддерживаемый способ также очень прост, для набора значений V функции a мыВыберите порог t для деления, разделим его на две части, меньшие t и те, что больше t.
То есть алгоритм C4.5 отличается для сегментации непрерывных значений и дискретных значений, Для дискретных переменных мы сегментируем каждое значение, а для непрерывных значений мытолько разрезать на два. На самом деле такой дизайн очень разумен, потому что в большинстве случаев непрерывнозначные характеристики каждого фрагмента данных часто различны. И у нас нет возможности определить, на сколько частей разумно разделить непрерывный признак, поэтому более интуитивно понятно разделить его на две части, что лучше, чем не иметь возможности его использовать.
В крайних случаях количество признаков с непрерывными значениями равно количеству выборок, так как же выбрать этот порог? Даже если мы пройдемся по всем случаям сегментации, будет n-1 видов, что, очевидно, очень много, особенно при большом количестве выборок.
Существует также решение этой проблемы, заключающееся в сортировке по собственным значениям,Выберите истинную точку отсечки. Что вы имеете в виду, давайте посмотрим на кусок данных:
| диаметр | Это сладко |
|---|---|
| 3 | сладкий |
| 4 | сладкий |
| 5 | не сладкий |
| 6 | не сладкий |
| 7 | сладкий |
| 8 | не сладкий |
| 9 | не сладкий |
Эти данные являются результатом сортировки нашей команды по диаметру арбуза. Мы видим, чтоЗначение изменения тренировочной цели на самом деле составляет всего 3, когда диаметры равны 5, 7 и 8, нам нужно рассмотреть только эти три случая, а другие случаи можно игнорировать.
Рассмотрим эти два момента и добавим их к предыдущей реализации модели ID3.
Код
Просто говоря об этом, а не практикуя фальшивую ручку, поскольку мы понимаем ее принцип, мы должны сделать следующее, чтобы считаться истинным пониманием, а ямы во многих местах можно считать истинным пониманием. В основном мы можем использовать предыдущий код, но нам нужно внести некоторые изменения на его основе.
Прежде всего, давайте преобразуем часть данных построения, мы по-прежнему используем последние данные, три оценки студента за тест и то, прошел ли он стандартные данные. Мы считаем, что три предмета с оценкой 150 и выше считаются соответствующими стандарту. Курсы с оценкой более 70 относятся к 2-му классу, от 40 до 70 — к 1-му классу, а ниже 40 — к 0-му классу. На этой основе мыДобавлен счет как функция, мы добавляем к оценке ошибку, не позволяющую модели получить результат напрямую.
import numpy as np
import math
def create_data():
X1 = np.random.rand(50, 1)*100
X2 = np.random.rand(50, 1)*100
X3 = np.random.rand(50, 1)*100
def f(x):
return 2 if x > 70 else 1 if x > 40 else 0
# 学生的分数作为特征，为了公平，加上了一定噪音
X4 = X1 + X2 + X3 + np.random.rand(50, 1) * 20
y = X1 + X2 + X3
Y = y > 150
Y = Y + 0
r = map(f, X1)
X1 = list(r)
r = map(f, X2)
X2 = list(r)
r = map(f, X3)
X3 = list(r)
x = np.c_[X1, X2, X3, X4, Y]
return x, ['courseA', 'courseB', 'courseC', 'score']
Поскольку нам необходимо рассчитать коэффициент прироста информации, нам необходимо разработатьДля расчета коэффициента усиления информации используется специальная функция. Поскольку данные на этот раз включают непрерывные функции, нам нужно пройти дополнительный порог, чтобы определить, является ли это непрерывной функцией. Если это дискретная функция, порог равен None, в противном случае это конкретное значение.
def info_gain(dataset, idx):
# 计算基本的信息熵
entropy = calculate_info_entropy(dataset)
m = len(dataset)
# 根据特征拆分数据
split_data, _ = split_dataset(dataset, idx)
new_entropy = 0.0
# 计算拆分之后的信息熵
for data in split_data:
prob = len(data) / m
# p * log(p)
new_entropy += prob * calculate_info_entropy(data)
return entropy - new_entropy
def info_gain_ratio(dataset, idx, thred=None):
# 拆分数据，需要将阈值传入，如果阈值不为None直接根据阈值划分
# 否则根据特征值划分
split_data, _ = split_dataset(dataset, idx, thred)
base_entropy = 1e-5
m = len(dataset)
# 计算特征本身的信息熵
for data in split_data:
prob = len(data) / m
base_entropy -= prob * math.log(prob, 2)
return info_gain(dataset, idx) / base_entropy, thred
Функцию split_dataset также необходимо изменить, потому что существует другой способ разделения в соответствии с пороговым значением, и судят о том, делится ли пороговое значение или разделение объектов, исходя из того, является ли пороговое значение None.
def split_dataset(dataset, idx, thread=None):
splitData = defaultdict(list)
# 如果阈值为None那么直接根据特征划分
if thread is None:
for data in dataset:
splitData[data[idx]].append(np.delete(data, idx))
return list(splitData.values()), list(splitData.keys())
else:
# 否则根据阈值划分，分成两类大于和小于
for data in dataset:
splitData[data[idx] < thread].append(np.delete(data, idx))
return list(splitData.values()), list(splitData.keys())
Как упоминалось ранее, нам не нужно проходить все значения при выборе порога, потому что некоторые значения не вызывают изменений в распределении меток, и мы можем игнорировать это значение. Итак, нам нужна функция дляПолучите все возможности для порога, это тоже очень просто, мы напрямую сортируем по порогу, а потом проходим, чтобы посмотреть изменится ли метка, и записываем значение всех позиций изменения метки:
def get_thresholds(X, idx):
# numpy多维索引用法
new_data = X[:, [idx, -1]].tolist()
# 根据特征值排序
new_data = sorted(new_data, key=lambda x: x[0], reverse=True)
base = new_data[0][1]
threads = []
for i in range(1, len(new_data)):
f, l = new_data[i]
# 如果label变化则记录
if l != base:
base = l
threads.append(f)
return threads
С помощью этих методов нам нужноРазработайте функцию для выбора разделенных значений, то есть вычислите коэффициент получения информации для всех признаков и найдите признак с наибольшим коэффициентом получения информации для разделения. На самом деле, после того, как мы разработали функции для разбиения и получения всех порогов, найти наилучшую точку разбиения очень легко, в основном мы используем ранее разработанный код и перебираем все возможности:
def choose_feature_to_split(dataset):
n = len(dataset[0])-1
m = len(dataset)
# 记录最佳增益比、特征和阈值
bestGain = 0.0
feature = -1
thred = None
for i in range(n):
# 判断是否是连续性特征，默认整数型特征不是连续性特征
# 这里只是我个人的判断逻辑，可以自行diy
if not dataset[0][i].is_integer():
threds = get_thresholds(dataset, i)
for t in threds:
# 遍历所有的阈值，计算每个阈值的信息增益比
ratio, th = info_gain_ratio(dataset, i, t)
if ratio > bestGain:
bestGain, feature, thred = ratio, i, t
else:
# 否则就走正常特征拆分的逻辑，计算增益比
ratio, _ = info_gain_ratio(dataset, i)
if ratio > bestGain:
bestGain = ratio
feature, thred = i, None
return feature, thred
На данный момент базовый метод разработан, осталось только два метода: построение дерева и предсказание. Эти два метода и предыдущие изменения кода невелики, в основном небольшие изменения. Давайте сначала рассмотрим построение дерева Единственная разница между построением дерева заключается в том, что в словаре необходимо хранить дополнительную пороговую информацию. Если это None, это означает дискретные функции, а если это не None, это означает непрерывные функции, а остальная логика в основном неизменна.
def create_decision_tree(dataset, feature_names):
dataset = np.array(dataset)
# 如果都是一类，那么直接返回类别
counter = Counter(dataset[:, -1])
if len(counter) == 1:
return dataset[0, -1]
# 如果只有一个特征了，直接返回占比最多的类别
if len(dataset[0]) == 1:
return counter.most_common(1)[0][0]
# 记录最佳拆分的特征和阈值
fidx, th = choose_feature_to_split(dataset)
fname = feature_names[fidx]
node = {fname: {'threshold': th}}
feature_names.remove(fname)
split_data, vals = split_dataset(dataset, fidx, th)
for data, val in zip(split_data, vals):
node[fname][val] = create_decision_tree(data, feature_names[:])
return node
Последняя функция прогнозирования.Логика такая же, как и раньше, за исключением того, что добавлено суждение о том, является ли пороговое значение None.Это должно быть очень просто:
def classify(node, feature_names, data):
key = list(node.keys())[0]
node = node[key]
idx = feature_names.index(key)
pred = None
thred = node['threshold']
# 如果阈值为None，那么直接遍历dict
if thred is None:
for key in node:
if key != 'threshold' and data[idx] == key:
if isinstance(node[key], dict):
pred = classify(node[key], feature_names, data)
else:
pred = node[key]
else:
# 否则直接访问
if isinstance(node[data[idx] < thred], dict):
pred = classify(node[data[idx] < thred], feature_names, data)
else:
pred = node[data[idx] < thred]
# 放置pred为空，挑选一个叶子节点作为替补
if pred is None:
for key in node:
if not isinstance(node[key], dict):
pred = node[key]
break
return pred
Суммировать
На данный момент разработан алгоритм C4.5 всего дерева решений.В целом, из-за добавления коэффициента усиления информации и логики функции непрерывности, общий код немного сложнее, чем раньше, но основная логика и подпрограммы остались в той же строке, в основном мало что изменилось.
Дерево решений в принципе очень простое, но многие детали не будут реализованы, если вы сами этого не сделали. Например, как найти пороговое множество непрерывных признаков, таких как смешение непрерывных признаков и дискретных признаков, как различить их в коде и так далее. Только реально делая это, вы можете осознать эти проблемы. Хотя модель дерева решений обычно не используется, ноОн является основой для многих продвинутых моделей., это очень полезно для дальнейшего обучения и продвижения.Если у вас есть время, я рекомендую всем попробовать это для себя.
Сегодняшняя статья здесь, оригинальность непростая, вам нужен вашбеспокойство, ваше небольшое усилие очень важно для меня.