Полная реализация с нуля
Дерево решений — самый мощный и популярный инструмент, используемый как для классификации, так и для регрессии. Это похоже на блок-схему, или мы можем использовать древовидную модель, где каждый узел отображает функцию, а верхний узел называется корневым узлом.
Ключевые моменты дерева решений
- Простая древовидная структура, модель может принимать решения в любой точке
- Простота объяснения, поскольку она показывает, как принимается решение!
- Рекурсивный и жадный алгоритм
- Четко определенная логика
- Имитирует человеческую логику
- Характеристики предпочтительнее быть категоричными
Построение дерева решений может включать любой из двух критериев:
- Индекс Джини (CART — деревья классификации и регрессии)
- Энтропия (ID3 — Итеративный дихромайзер 3)
Наиболее важным моментом в дереве решений является то, как решить, какую функцию следует выбрать в каждой точке! Так что указанные выше критерии помогают нам в этом.
Индекс Джини
Оценка Джини дает представление о том, насколько хорошо разделение, по тому, насколько смешаны классы ответов в группах, созданных в результате разделения. Следующая формула дает нам значение индекса Джини.
Энтропия
Энтропия — это мера случайности в системе.
Мы рассчитываем прирост информации, используя энтропию, которую необходимо максимизировать, чтобы получить правильную характеристику узла.
Мы дадим все функции любому из вышеперечисленных критериев, а затем для того, который имеет максимальный прирост информации, мы будем разделять данные на основе порогового значения или среднего значения.
Давайте возьмемся за код энтропии:
def entropy(col):
counts = np.unique(col,return_counts=True)
N = float(col.shape[0])
entropy = 0.0
for i in counts[1]:
p = i/N
entropy += (-1.0 * p * np.log2(p))
return entropy
- Мы посчитаем количество уникальных записей и общее количество записей.
- Затем применить формулу энтропии.
Разделение данных
Мы знаем, что разделяем наши данные на левое и правое поддерево, поэтому значения, превышающие пороговое значение, будут попадать в правую сторону, а меньше единиц — в левую.
fkey → Имя функции
fval → Пороговое значение
def divide_data(x_data,fkey,fval):
# work with Pandas dataframe
# creating 2 empty dataframe
x_right = pd.DataFrame([],columns=x_data.columns)
x_left = pd.DataFrame([],columns=x_data.columns)
for i in range(x_data.shape[0]):
val = x_data[fkey].loc[i]
if val > fval:
x_right = x_right.append(x_data.loc[i])
else:
x_left = x_left.append(x_data.loc[i])
return x_left,x_right
Получение информации
def information_gain(x_data,fkey,fval):
# Split data
left,right = divide_data(x_data,fkey,fval)
# we will compute reduction in entropy after this entropy
# % fo people on left and right
l = float(left.shape[0])/x_data.shape[0]
r = float(right.shape[0])/x_data.shape[0]
# All examples can come to one side
if left.shape[0] == 0 or right.shape[0] == 0:
return -1000000 # Min information Gain
i_gain = entropy(x_data.Survived) - (l*entropy(left.Survived) + r*entropy(right.Survived))
return i_gain
- Мы разделяем наши данные на левые и правые, а затем вычисляем энтропию.
- Применяется формула информации.
Теперь все готово для перехода к коду Дерева решений!!
class DecisionTree:
# Constructor
def __init__(self,depth=0,max_depth=5):
self.left = None
self.right = None
self.fkey = None
self.fval = None
self.max_depth = max_depth
self.depth = depth
self.target = None
def train(self,X_train):
features = ["Pclass","Sex","Age","SibSp","Parch","Fare"]
info_gain = []
for i in features:
i_gain = information_gain(X_train,i,X_train[i].mean())
info_gain.append(i_gain)
self.fkey = features[np.argmax(info_gain)]
self.fval = X_train[self.fkey].mean()
print("Making tree Feature is",self.fkey)
# Split Data
data_left,data_right = divide_data(X_train,self.fkey,self.fval)
data_left = data_left.reset_index(drop=True)
data_right = data_right.reset_index(drop=True)
# we have reached leaf node
if data_left.shape[0] == 0 or data_right.shape[0] ==0 :
if X_train.Survived.mean() >=0.5:
self.target = "Survived"
else:
self.target = "Dead"
return
# Stop early when depth >=maxDepth
if self.depth >= self.max_depth:
if X_train.Survived.mean() >=0.5:
self.target = "Survived"
else:
self.target = "Dead"
return
# Recursive Case
self.left = DecisionTree(depth=self.depth+1,max_depth=self.max_depth)
self.left.train(data_left)
self.right = DecisionTree(depth=self.depth+1,max_depth=self.max_depth)
self.right.train(data_right)
# Setting Target at every node
if X_train.Survived.mean() >=0.5:
self.target = "Survived"
else:
self.target = "Dead"
return
def predict(self,test):
if test[self.fkey]>self.fval:
# right
if self.right is None:
return self.target
return self.right.predict(test)
else:
if self.left is None:
return self.target
return self.left.predict(test)
Мы сталкиваемся с проблемой переобучения в дереве решений, что означает, что до определенного момента точность увеличивается как в обучающем, так и в тестовом наборе данных, но после определенного момента она начинает уменьшаться для тестовой части. Это означает, что наш код не является обобщенным.
Чтобы преодолеть это, мы можем использовать два метода
- Post Pruning → Здесь мы позволяем дереву полностью вырасти, а затем удаляем бесполезные узлы.
- Предварительная обрезка → Мы можем установить максимальную высоту дерева, которая предотвращает рост дерева после определенного предела.
Мы использовали Pre-Pruning в нашем коде.
Помимо этого дерева решений, также имеют высокую дисперсию. Даже если мы внесем небольшое изменение в наш набор данных, результаты сильно изменятся.
Чтобы преодолеть это, мы приходим к идее ансамбля. Ансамбльные методы, которые объединяют несколько деревьев решений для повышения производительности прогнозирования, чем использование одного дерева решений.
Основной принцип модели ансамбля заключается в том, что группа слабых учеников объединяется, чтобы сформировать сильного ученика.
- Бэггинг (агрегация Bootsrap) здесь наша главная цель — минимизировать дисперсию дерева. Используется среднее значение всех прогнозов из разных деревьев, что является более надежным, чем одно дерево решений.
Random Forest — это расширение по сравнению с пакетированием. Требуется один дополнительный шаг, когда в дополнение к выбору случайного подмножества данных также используется случайный выбор функций, а не использование всех функций для выращивания деревьев. Когда у вас много случайных деревьев. Он называется «Случайный лес».
2. Бустирование — это еще один метод ансамбля для создания набора предикторов. В этом методе учащиеся изучаются последовательно: учащиеся раннего возраста подгоняют простые модели к данным, а затем анализируют данные на наличие ошибок. Другими словами, мы подбираем последовательные деревья (случайная выборка), и на каждом шаге цель состоит в том, чтобы найти чистую ошибку из предыдущего дерева.
Например, adaboost, усилитель градиента. В adaboost нам нужны веса для записей. Изначально всем присваиваются одинаковые веса и создается дерево решений, но с высотой =1. Они называются пни. Для каждой функции мы создаем пень.
- Мы выберем пень с минимальной энтропией или коэффициентом Джинни.
- Считаем общую ошибку.
- Производительность Stump рассчитывается
4. Мы увеличим веса неправильно предсказанного класса на Вес новой выборки = вес X e ^ Производительность пня
5. Мы обновим веса правильно прогнозируемого класса с помощью Вес новой выборки = вес X e^- Производительность пня
6. Теперь делим на сумму новых весов, чтобы получить нормализованные веса.
7. После этого создаем новое дерево решений и цикл повторяется.
Наконец, мы принимаем решение большинством голосов.
