Полная реализация с нуля
Дерево решений — самый мощный и популярный инструмент, используемый как для классификации, так и для регрессии. Это похоже на блок-схему, или мы можем использовать древовидную модель, где каждый узел отображает функцию, а верхний узел называется корневым узлом.
Ключевые моменты дерева решений
- Простая древовидная структура, модель может принимать решения в любой точке
- Простота объяснения, поскольку она показывает, как принимается решение!
- Рекурсивный и жадный алгоритм
- Четко определенная логика
- Имитирует человеческую логику
- Характеристики предпочтительнее быть категоричными
Построение дерева решений может включать любой из двух критериев:
- Индекс Джини (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. После этого создаем новое дерево решений и цикл повторяется.
Наконец, мы принимаем решение большинством голосов.