Деревья решений от скрещивания: учебник по кодированию для начинающих

Основные понятия, которые вы должны понять

Узлы, ветви и листья

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

Критерии разделения

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

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

Алгоритм оценивает каждый возможный раскол на каждой функции и выбирает ту, которая дает наибольшее снижение примеси (или прироста информации).

Информационный прирост и коэффициент прироста

Информационный прирост — это разница между примесями родительского узла и взвешенной суммой детских примесей. Хотя он прост, он склонен благоприятствовать функциям со многими значениями. Соотношение усиления (используемое в C4.5) нормализует это. Для этого учебника мы будем придерживаться стандартного информационного прироста с использованием примеси Джини, которая является по умолчанию в CART (Дерево классификации и регрессии).

Построение дерева решений шаг за шагом

1.Подготовьте свои данные

Для простоты используйте набор данных с числовыми признаками двоичной классификации. Например:

• Особенности: Возраст, доход
• Цель: Одобренный (1) или не утвержденный (0)

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

2.Определить функцию разделительного критерия

Мы будем внедрять примеси Джини. Индекс Джини для набора элементов:

где p i - доля элементов в классе i. Для двоичного разделения общий Джини - средневзвешенное значение узлов ребенка.

3. Осуществление оценки разделения

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

4.Построй дерево рекурсивно

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

5. делать прогнозы

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

Полная реализация на Python

Ниже приведена полная, минимальная реализация дерева решений для классификации с использованием примеси Джини. Этот код предназначен для обучения - он не оптимизирован для больших наборов данных.

import numpy as np
from collections import Counter

class DecisionTree:
 def __init__(self, max_depth=None, min_samples_split=2):
 self.max_depth = max_depth
 self.min_samples_split = min_samples_split
 self.tree = None

 def fit(self, X, y):
 dataset = np.column_stack((X, y))
 self.tree = self._grow_tree(dataset)

 def _grow_tree(self, dataset, depth=0):
 X, y = dataset[:, :-1], dataset[:, -1]
 n_samples, n_features = X.shape
 n_labels = len(np.unique(y))

 # Stopping conditions
 if (n_labels == 1 or depth == self.max_depth or n_samples < self.min_samples_split):
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 best_feature, best_threshold = self._best_split(dataset, n_features)
 if best_feature is None:
 leaf_value = Counter(y).most_common(1)[0][0]
 return {'leaf': True, 'value': leaf_value}

 left_idx, right_idx = self._split(dataset[:, best_feature], best_threshold)
 left_subtree = self._grow_tree(dataset[left_idx], depth+1)
 right_subtree = self._grow_tree(dataset[right_idx], depth+1)
 return {'leaf': False,
 'feature': best_feature,
 'threshold': best_threshold,
 'left': left_subtree,
 'right': right_subtree}

 def _best_split(self, dataset, n_features):
 best_gini = float('inf')
 best_feature, best_threshold = None, None
 for feature in range(n_features):
 thresholds = np.unique(dataset[:, feature])
 for i in range(len(thresholds)-1):
 thresh = (thresholds[i] + thresholds[i+1]) / 2
 left_idx, right_idx = self._split(dataset[:, feature], thresh)
 if len(left_idx) == 0 or len(right_idx) == 0:
 continue
 gini = self._gini_gain(dataset, left_idx, right_idx)
 if gini < best_gini:
 best_gini = gini
 best_feature = feature
 best_threshold = thresh
 return best_feature, best_threshold

 def _split(self, values, threshold):
 left_idx = np.where(values <= threshold)[0]
 right_idx = np.where(values > threshold)[0]
 return left_idx, right_idx

 def _gini_gain(self, dataset, left_idx, right_idx):
 total = len(left_idx) + len(right_idx)
 gini_left = self._gini(dataset[left_idx, -1])
 gini_right = self._gini(dataset[right_idx, -1])
 return (len(left_idx)/total) * gini_left + (len(right_idx)/total) * gini_right

 def _gini(self, labels):
 _, counts = np.unique(labels, return_counts=True)
 p = counts / np.sum(counts)
 return 1 - np.sum(p**2)

 def predict(self, X):
 return np.array([self._predict_row(x, self.tree) for x in X])

 def _predict_row(self, x, node):
 if node['leaf']:
 return node['value']
 if x[node['feature']] <= node['threshold']:
 return self._predict_row(x, node['left'])
 else:
 return self._predict_row(x, node['right'])

Испытание дерева