Создайте свою собственную модель
Понимание через реализацию: дерево решений
Узнайте, как работает дерево решений, и реализуйте его на Python.
Многие передовые модели машинного обучения, такие как случайные леса или алгоритмы повышения градиента, такие как XGBoost, CatBoost или LightGBM (и даже автоэнкодеры!) опираются на ключевой общий компонент: дерево решений!
Без понимания деревьев решений невозможно также понять ни один из вышеупомянутых продвинутых алгоритмов бэггинга или повышения градиента, что является позором для любого специалиста по данным! 😁 Итак, давайте демистифицируем внутреннюю работу дерева решений, реализовав его на Python.
В этой статье вы узнаете
- почему и как дерево решений разбивает данные,
- прирост информации и
- как реализовать деревья решений в Python с помощью NumPy.
Вы можете найти код на мой Github.
Теория
Чтобы делать прогнозы, деревья решений основаны на разбиении набора данных на более мелкие части рекурсивным способом.
На картинке выше вы можете увидеть один пример разделения — исходный набор данных разделяется на две части. На следующем шаге обе эти части снова разделяются и так далее. Это продолжается до тех пор, пока не будет выполнен какой-либо критерий остановки, например,
- если разделение приводит к тому, что часть становится пустой
- если была достигнута определенная глубина рекурсии
- если (после предыдущих разбиений) набор данных состоит только из нескольких элементов, что делает дальнейшие разбиения ненужными.
Как мы находим эти расщепления? И почему нас это вообще волнует? Давай выясним.
Мотивация
Предположим, что мы хотим решить двоичную проблему классификации, которую сейчас создаем сами:
import numpy as np np.random.seed(0) X = np.random.randn(100, 2) # features y = ((X[:, 0] > 0) * (X[:, 1] < 0)) # labels (0 and 1)
Двумерные данные выглядят так:
Мы видим, что есть два разных класса — фиолетовый примерно в 75% и желтый примерно в 25% случаев. Если вы передадите эти данные классификатору дерева решений, у этого дерева изначально будут следующие мысли:
«Есть два разных лейбла, что для меня слишком запутанно. Я хочу убрать этот беспорядок, разделив данные на две части — эти части должны быть чище, чем полные данные раньше». — дерево, которое обрело сознание
Так и дерево делает.
Дерево решает сделать разделение примерно по оси x. Это приводит к тому, что верхняя часть данных теперь совершенно чиста, а это означает, что вы найдете там только один класс (фиолетовый в данном случае).
Однако нижняя часть по-прежнему грязная, в каком-то смысле даже более грязная, чем раньше. Соотношение классов было около 75:25 в полном наборе данных, но в этой меньшей части оно составляет около 50:50, что настолько запутанно, насколько это возможно.
⚠️ Примечание. Здесь не имеет значения, что фиолетовый и желтый хорошо разделены на картинке. Учитывается только необработанное количество различных ярлыков в двух частях.
Тем не менее, этого достаточно для первого шага для дерева, и поэтому оно продолжается. Хотя он больше не будет создавать еще одно разделение в верхней, чистой части, он может создать еще одно разделение в нижней части, чтобы очистить ее.
И вуаля, каждая из трех отдельных частей полностью чистая, так как мы находим только один цвет (метку) для каждой части.
Теперь очень легко делать прогнозы: если появляется новая точка данных, вы просто проверяете, в какой из трех частей она лежит, и присваиваете ей соответствующий цвет. Теперь это работает так хорошо, потому что каждая часть чиста. Легко, верно?
Хорошо, мы говорили о чистых и беспорядочных данных, но пока эти слова представляют собой лишь смутное представление. Чтобы реализовать что-либо, мы должны найти способ определить чистоту.
Меры по обеспечению чистоты
Предположим, что у нас есть несколько меток, например
y_1 = [0, 0, 0, 0, 0, 0, 0, 0] y_2 = [1, 0, 0, 0, 0, 0, 1, 0] y_3 = [1, 0, 1, 1, 0, 0, 1, 0]
Интуитивно понятно, что y₁ — это самый чистый набор ярлыков, за которым следует y₂, а затем y₃. Пока все хорошо, но как мы можем оценить это поведение? Возможно, самое простое, что приходит на ум, это следующее:
Просто посчитайте количество нулей и количество единиц. Вычислите их абсолютную разницу. Чтобы сделать его лучше, нормализуйте его, разделив длину массивов.
Например, в y₂ всего 8 записей — 6 нулей и 2 единицы. Следовательно, наша пользовательская оценка чистоты будет равна |6 - 2| / 8 = 0,5. Легко подсчитать, что показатели чистоты y₁ и y₃ равны 1,0 и 0,0 соответственно. Здесь мы видим общую формулу:
Здесь n₀ и n₁ — количество нулей и единиц соответственно, n = n₀ + n₁ — длина массива, а p₁ = n₁ / n — доля 1 меток .
Проблема с этой формулой в том, что она специально адаптирована для случая двух классов, но очень часто нас интересует мультиклассовая классификация. Одной из формул, которая работает достаточно хорошо, является мера примесей Джини:
или общий случай:
Он работает настолько хорошо, что scikit-learn принял его в качестве показателя по умолчанию для своего класса DecisionTreeClassifier.
⚠️ Примечание. Джини измеряет беспорядок, а не чистоту. Пример: если список содержит только один класс (= очень чистые данные!), то все элементы в сумме равны нулю, следовательно, сумма равна нулю. В худшем случае все классы появляются точное количество раз, и в этом случае коэффициент Джини равен 1–1/C, гдеC— количество классов.
Теперь, когда у нас есть мера чистоты/беспорядка, давайте посмотрим, как ее можно использовать для поиска хороших расщеплений.
Поиск расколов
Есть много сплитов, из которых мы выбираем, но какой из них хороший? Давайте снова воспользуемся нашим исходным набором данных вместе с мерой примесей Джини.
Мы не будем сейчас считать баллы, но предположим, что 75% — фиолетовые, а 25% — желтые. Используя определение Джини, примесь полного набора данных равна
Если мы разделим набор данных по оси x, как это делалось ранее:
В верхней части примесь Джини равна 0,0, а в нижней части
В среднем две части имеют примесь Джини (0,0 + 0,5) / 2 = 0,25, что лучше, чем 0,375 всего набора данных ранее. Мы также можем выразить это в терминах так называемого прироста информации:
Информационная выгода от этого разделения составляет 0,375 – 0,25 = 0,125.
Просто так. Чем выше прирост информации (т. е. чем меньше примесь Джини), тем лучше.
Примечание. Другим не менее удачным начальным разделением будет ось Y.
Важно помнить, что полезно взвешивать примеси Джини частей по размеру частей. Например, предположим, что
- часть 1 состоит из 50 точек данных и имеет примесь Джини 0,0 и
- часть 2 состоит из 450 точек данных и имеет примесь Джини 0,5,
тогда средняя примесь Джини должна быть не (0,0 + 0,5) / 2 = 0,25, а скорее 50 / (50 + 450) * 0,0 + 450 / (50 + 450) * 0,5 = 0,45.
Хорошо, и как нам найти лучшее разделение? Простой, но отрезвляющий ответ:
Просто попробуйте все сплиты и выберите тот, который принесет больше информации. По сути, это метод грубой силы.
Чтобы быть более точным, стандартные деревья решений используют разбиения по осям координат, т. е. xᵢ = cдля некоторого признакаiи порогc. Это означает, что
- одна часть разделенных данных состоит из всех точек данных xсxᵢ ‹ cи
- другая часть всех точекxгдеxᵢ ≥ c.
Эти простые правила разделения оказались достаточно хорошими на практике, но вы, конечно, можете расширить эту логику, чтобы создать другие разделения (например, диагональные линии, такие как xᵢ + 2xⱼ = 3).
Отлично, это все ингредиенты, которые нам нужны для работы!
Реализация
Сейчас мы реализуем дерево решений. Поскольку он состоит из узлов, давайте сначала определим класс Node.
from dataclasses import dataclass
@dataclass
class Node:
feature: int = None # feature for the split
value: float = None # split threshold OR final prediction
left: np.array = None # store one part of the data
right: np.array = None # store the other part of the data
Узел знает функцию, которую он использует для разделения (feature), а также значение разделения (value). value также используется в качестве хранилища для окончательного прогноза дерева решений. Поскольку мы будем строить бинарное дерево, каждый узел должен знать своих левых и правых дочерних элементов, хранящихся в left и right.
Теперь давайте займемся реальной реализацией дерева решений. Я делаю его совместимым с scikit-learn, поэтому использую некоторые классы из sklearn.base. Если вы не знакомы с этим, ознакомьтесь с моей статьей о том, как создавать модели, совместимые с scikit-learn:
Реализуем!
import numpy as np
from sklearn.base import BaseEstimator, ClassifierMixin
class DecisionTreeClassifier(BaseEstimator, ClassifierMixin):
def __init__(self):
self.root = Node()
@staticmethod
def _gini(y):
"""Gini impurity."""
counts = np.bincount(y)
p = counts / counts.sum()
return (p * (1 - p)).sum()
def _split(self, X, y):
"""Bruteforce search over all features and splitting points."""
best_information_gain = float("-inf")
best_feature = None
best_split = None
for feature in range(X.shape[1]):
split_candidates = np.unique(X[:, feature])
for split in split_candidates:
left_mask = X[:, feature] < split
X_left, y_left = X[left_mask], y[left_mask]
X_right, y_right = X[~left_mask], y[~left_mask]
information_gain = self._gini(y) - (
len(X_left) / len(X) * self._gini(y_left)
+ len(X_right) / len(X) * self._gini(y_right)
)
if information_gain > best_information_gain:
best_information_gain = information_gain
best_feature = feature
best_split = split
return best_feature, best_split
def _build_tree(self, X, y):
"""The heavy lifting."""
feature, split = self._split(X, y)
left_mask = X[:, feature] < split
X_left, y_left = X[left_mask], y[left_mask]
X_right, y_right = X[~left_mask], y[~left_mask]
if len(X_left) == 0 or len(X_right) == 0:
return Node(value=np.argmax(np.bincount(y)))
else:
return Node(
feature,
split,
self._build_tree(X_left, y_left),
self._build_tree(X_right, y_right),
)
def _find_path(self, x, node):
"""Given a data point x, walk from the root to the corresponding leaf node. Output its value."""
if node.feature == None:
return node.value
else:
if x[node.feature] < node.value:
return self._find_path(x, node.left)
else:
return self._find_path(x, node.right)
def fit(self, X, y):
self.root = self._build_tree(X, y)
return self
def predict(self, X):
return np.array([self._find_path(x, self.root) for x in X])
Вот и все! Теперь вы можете делать все, что вам нравится в scikit-learn:
dt = DecisionTreeClassifier().fit(X, y) print(dt.score(X, y)) # accuracy # Output # 1.0
Поскольку дерево нерегуляризовано, оно сильно переоснащается, отсюда и идеальный результат поезда. Точность будет хуже для невидимых данных. Мы также можем проверить, как выглядит дерево, с помощью
print(dt.root) # Output (prettified manually): # Node( # feature=1, # value=-0.14963454032767076, # left=Node( # feature=0, # value=0.04575851730144607, # left=Node( # feature=None, # value=0, # left=None, # right=None # ), # right=Node( # feature=None, # value=1, # left=None, # right=None # ) # ), # right=Node( # feature=None, # value=0, # left=None, # right=None # ) # )
На картинке будет так:
Заключение
В этой статье мы подробно рассмотрели, как работают деревья решений. Мы начали с расплывчатых, но интуитивных идей и превратили их в формулы и алгоритмы. В итоге мы смогли реализовать дерево решений с нуля.
Однако предостережение: наше дерево решений пока нельзя упорядочить. Обычно мы хотели бы указать такие параметры, как
- Максимальная глубина
- размер листа
- и минимальный информационный прирост
среди многих других. К счастью, эти вещи не так уж сложны в реализации, поэтому это идеальное домашнее задание для вас. Например, если вы укажете в качестве параметра leaf_size=10, то узлы, содержащие более 10 сэмплов, больше не должны разбиваться. Кроме того, эта реализация неэффективна. Обычно вы не хотите хранить части наборов данных в узлах, а только индексы. Таким образом, ваш (потенциально большой) набор данных находится в памяти только один раз.
Хорошо, что теперь вы можете сойти с ума с этим шаблоном дерева решений. Ты можешь:
- реализовать диагональное разделение, т.е. xᵢ + 2xⱼ = 3вместо простоxᵢ = 3,
- изменить логику, которая происходит внутри листьев, т. е. вы можете запустить логистическую регрессию внутри каждого листа вместо того, чтобы просто голосовать большинством, что дает вам линейное дерево
- изменить процедуру разбиения, т.е. вместо перебора пробовать несколько случайных комбинаций и выбирать лучшую, что дает вам дополнительный классификатор дерева
- и более.
Кроме того, ознакомьтесь с другими моими реализациями базовых алгоритмов машинного обучения!
Надеюсь, что сегодня вы узнали что-то новое, интересное и полезное. Спасибо за прочтение!
И последнее, если вы
- поддержите меня в написании дополнительных статей о машинном обучении и
- в любом случае планируйте получить подписку на Medium,
почему бы не сделать это по этой ссылке? Это бы мне очень помогло! 😊
Чтобы быть прозрачным, цена для вас не меняется, но около половины абонентской платы идет непосредственно мне.
Большое спасибо, если вы поддержите меня!
Если у вас есть вопросы, пишите мне в LinkedIn!
