Решающее дерево — алгоритм, который можно изобразить в виде дерева.
Визуализация реашющего дерева для ирисов:
Необходимо в каждой вершине строить разбиение дошедших объектов, то есть находить некоторое условие $[x^j \le t]$, по которому будет строиться разбиение. (конечно, кажется неразумным разбивать объекты в некоторой вершине, если все одного класса. в этом случае просто объявляем вершину листовой)
Для того чтобы сравнить несколько разбиений между собой, будем сравнивать их, например, с помощью энтропии.
Энтропия (мера неопределенности)
Пусть имеется некотрое дискретное распределение, принимающее n значений, с вероятностями $p_1, \dots p_n$. Тогда энтропией распределения будет следующая величина:
$$ H(p_1, \dots p_n) = -\sum_{i=1}^n p_i\log{p_i} $$В случае регрессии выбирается разбиение с наименьшей суммарной дисперсией. Чем меньше дисперсия, тем меньше неопределенность.
Получается, процесс нахождения наилучшего разбиения в вершине устроен следующим образом. Пусть в вершину пришла выборка $X^m$. Хотим найти некоторые $j, t$, где $[x^j < t]$. Будем просто перебирать возможные значения $j, t$, чтобы значение выбранного критерия качества было наибольшим.
Критерий качества:
$$ Q(X^m, j, t) = H(X_m) - \frac{|X_l|}{|X_m|}H(X_l) - \frac{|X_r|}{|X_m|}H(X_r)$$После того как разбиение выбрано, разбиваем $X^m$ на два множества по выбранному разбиению и повторяем для следующих вершин.
Рассмотрим задачу регрессии. Предсказываемой меткой назначим расстояние от начала координат до точки.
import numpy as np
import pandas as pd
import pylab as plt
%matplotlib inline
data_x = np.random.normal(size=(100, 2))
data_y = (data_x[:, 0] ** 2 + data_x[:, 1] ** 2) ** 0.5
plt.figure(figsize=(8, 8))
plt.scatter(data_x[:, 0], data_x[:, 1], c=data_y, s=100, cmap='spring')
<matplotlib.collections.PathCollection at 0x112afd190>
Вспомогательная функция для дальнейшей взуализации:
def get_grid(data):
x_min, x_max = data[:, 0].min() - 1, data[:, 0].max() + 1
y_min, y_max = data[:, 1].min() - 1, data[:, 1].max() + 1
return np.meshgrid(np.arange(x_min, x_max, 0.01),
np.arange(y_min, y_max, 0.01))
Обучимся на наших данных, предскажем ответ для каждой точки решетки и визуализируем результат.
from sklearn.tree import DecisionTreeRegressor
clf = DecisionTreeRegressor()
clf.fit(data_x, data_y)
xx, yy = get_grid(data_x)
predicted = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.figure(figsize=(8, 8))
plt.pcolormesh(xx, yy, predicted, cmap='spring')
plt.scatter(data_x[:, 0], data_x[:, 1], c=data_y, s=100, cmap='spring')
<matplotlib.collections.PathCollection at 0x112c8dd90>
У решающего дерева есть различные параметры, например:
Посмотрим как эти параметры будут влиять на предсказание.
plt.figure(figsize=(14, 14))
for i, max_depth in enumerate([2, 4, None]):
for j, min_samples_leaf in enumerate([1, 5, 15]):
clf = DecisionTreeRegressor(max_depth=max_depth, min_samples_leaf=min_samples_leaf)
clf.fit(data_x, data_y)
xx, yy = get_grid(data_x)
predicted = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.subplot2grid((3, 3), (i, j))
plt.pcolormesh(xx, yy, predicted, cmap='summer')
plt.scatter(data_x[:, 0], data_x[:, 1], c=data_y, s=30, cmap='summer')
plt.title('max_depth=' + str(max_depth) + ', min_samples_leaf: ' + str(min_samples_leaf))
Можно увидеть, что увеличение глубины дерева и уменьшение количества объектов в листьях способствует гибкости модели и, как следствие, переобучению.
Основным достоинством решающих деревьев можно назвать возможность интерпретации:
Основной недостаток — склонность к переобучению. Нужно очень тщательно подбирать параметры дерева, чтобы оно не было слишком грубым, но при этом строило хорошие предсказания. В борьбе с этим недостатком на помощь приходят случайные леса!
Одна из проблем: при небольших колебаниях выборки деревья могут получиться очень разными.
plt.figure(figsize=(20, 6))
for i in xrange(3):
clf = DecisionTreeRegressor(random_state=42)
indecies = np.random.randint(data_x.shape[0], size=(data_x.shape[0] * 0.9))
clf.fit(data_x[indecies], data_y[indecies])
xx, yy = get_grid(data_x)
predicted = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.subplot2grid((1, 3), (0, i))
plt.pcolormesh(xx, yy, predicted, cmap='winter')
plt.scatter(data_x[:, 0], data_x[:, 1], c=data_y, s=30, cmap='winter')
Одно дерево — плохо. Поэтому:
Однако теперь получается, что гиперпараметров становится больше:
+ все гиперпараметры решающих деревьев
Реализация случайных лесов в sklearn используются бутстреппинг — из исходной выборки каждый раз генерируется выборка с повторениями такого же размера.
from sklearn.ensemble import RandomForestRegressor
plt.figure(figsize=(20, 6))
for i, n in enumerate([1, 2, 10]):
clf = RandomForestRegressor(n_estimators=n, random_state=42)
clf.fit(data_x, data_y)
xx, yy = get_grid(data_x)
predicted = clf.predict(np.c_[xx.ravel(), yy.ravel()]).reshape(xx.shape)
plt.subplot2grid((1, 3), (0, i))
plt.pcolormesh(xx, yy, predicted, cmap='autumn')
plt.scatter(data_x[:, 0], data_x[:, 1], c=data_y, s=30, cmap='autumn')
plt.title('estimators: %i' % n)
plt.show()