Перейти к основному содержимому

Ансамбли рандомизированных деревьев

Как известно из разложения неоднозначности (ambiguity decomposition), ансамбли дают долее точные прогнозы, если базовые модели оказываются более непохожими друг на друга и дают более рассогласованные прогнозы. Когда строится ансамбль над решающими деревьями, то для повышения разнообразия предлагается строить деревья рандомизированным способом, то есть включая элемент случайности при их построении. На этом основаны алгоритмы решающего леса (random forest) и особо случайных деревьев (extra random trees), представляющие собой сильные базовые решения для работы с табличными данными.

Настройка решающих правил в деревьях​

При настройке решающих деревьев в каждом внутреннем узле нужно выбрать правило вида xi≤hx^i\le h: если ii-й признак больше порога hh, то происходит переход в правую дочернюю вершину, иначе в левую. Выбор номера признака и порога в узле tt осуществляется по правилу:

i^,h^=arg max⁡f,h∈P(t)Δϕ(t)(1)\widehat{i},\widehat{h}=\argmax_{f,h\in P(t)}\Delta\phi(t) \tag{1}

где Δϕ(t)\Delta \phi(t) - изменение функции неопределённости в вершине tt после разбиения.

Обычное дерево​

В стандартном решающем дереве CART в формуле (1) P(t)P(t) представляет собой набор пар (признак, порог) формирующийся перебором всех возможных пар (признак, порог):

P={}P=\{\}
для каждого ii in {1,...,D}\{1,...,D\}

для каждого hh из unique{xni}n:xn∈t\text{unique}\left\{ x_{n}^{i}\right\} _{n:\mathbf{x}_{n\in t}}

P:=P∪(i,h)P:=P\cup(i,h)

Оператор unique{xni}n:xn∈t\text{unique}\left\{ x_{n}^{i}\right\} _{n:\mathbf{x}_{n}\in t} возвращает все уникальные значения признака xix^i для объектов, попавших в узел tt.

Настройка правил в случайном лесе​

Случайный лес (random forest) строится как бэггинг над решающими деревьями, но правила в каждом узле (1) каждого дерева настраиваются по случайному подмножеству признаков и всем допустимым порогам для них:

P={}P=\{\}, K=αDK=\alpha D
сэмплируем без возвращения i1,...iK{i_1,...i_K} случайно из {1,...,D}\{1,...,D\}
для каждого ii из {i1,...iK}\{i_1,...i_K\}:

для каждого hh из unique{xni}n:xn∈t\text{unique}\left\{ x_{n}^{i}\right\}_{n:\mathbf{x}_{n}\in t}:

P:=P∪(i,h)P:=P\cup(i,h)

α∈(0,1]\alpha\in (0,1] - гиперпараметр метода, характеризующий долю признаков, по которым происходит настройка правила в узле. Например, при α=0.5\alpha=0.5 для каждого узла дерева будет сэмплироваться только половина всех признаков, по которым будет настраиваться правило (1).

Обратим внимание, что в каждом узле дерева сэмплируется своё случайное подмножество признаков, поэтому дерево как целое может зависеть от всех признаков. Это отличает деревья случайного леса от деревьев в методе случайных подпространств (random subspaces), в котором каждое дерево целиком будет зависеть от случайного подмножества признаков.

Гиперпараметр α\alpha - основной гиперпараметр случайного леса, контролирующий выразительную сложность модели.

Чем ниже α\alpha, тем меньше свободы у каждого решающего дерева в подборе оптимального правила, и тем оно получается менее гибким и смещенным (недообученным). Зато деревья получаются более разнообразными за счёт большего разнообразия правил, по которым строятся решающие деревья.

Если же увеличивать α\alpha, то деревья гибче подстраиваются под данные и становятся более переобученными и менее разнообразными.

Оптимальная точность ансамбля достигается при некотором балансе между точностью отдельных моделей и разнообразием их прогнозов. Поэтому в алгоритме случайного леса параметр α\alpha - главный гиперпараметр и его нужно настраивать в первую очередь.

Нужен ли бэггинг?

Каждая базовая модель случайного леса представляет собой рандомизированное решающее дерево. В силу случайности при его построении, использование бэггинга, то есть обучение каждого дерева на случайных псевдовыборках, становится необязательным, так как всё равно базовые алгоритмы будут получаться различными. Поэтому бэггинг можно как использовать, так и нет, в зависимости от того, какой вариант себя лучше покажет на валидационной выборке.

Настройка правил в особо случайных деревьях​

Особо случайные деревья (extra trees, extremely randomized trees) также представляет собой бэггинг над решающими деревьями. Но если в деревьях решающего леса правила настраивались по подмножеству признаков и всем допустимым для них порогам, то в особо случайном дереве пороги сэмплируются случайно вместе с признаками, и настройка по порогу не производится. Это делает оптимизацию правил в каждом узле дерева еще более ограниченной, в результате чего деревья получаются ещё менее гибкими, зато дополнительно повышается их разнообразие по сравнению с деревьями из случайного леса.

Псевдокод для формирования пар (признак, порог), по которым производится настройка решающих правил в узле (1) каждого особо случайного дерева приведён ниже:

S={}S=\{\}, K=αDK=\alpha D
сэмплируем без возвращения i1,...iK{i_1,...i_K} случайно из {1,...,D}\{1,...,D\}
для каждого ii из d1,...dK{d_1,...d_K}:

сэмплируем hh случайно без возвращения из unique{xni}n:xn∈tunique\left\{ x_{n}^{i}\right\}_{n:\mathbf{x}_{n}\in t}
P:=P∪(f,h)P:=P\cup(f,h)

Так же, как и в случае решающего леса, α∈(0,1]\alpha \in (0,1] - главный гиперпараметр метода, контролирующий сложность модели. Поскольку деревья используют случайность при настройке, они будут получаться разнообразными даже при перенастройке на одной и той же обучающей выборке, поэтому процедура бэггинга для генерации разных обучающих псевдовыборок необязательна. Использовать её, или нет, определяется тем, какой вариант лучше себя покажет на валидационной выборке.

Пример запуска на Python​

Случайный лес для классификации:
from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score
from sklearn.metrics import brier_score_loss

X_train, X_test, Y_train, Y_test = get_demo_classification_data()  

# инициализация модели:
model = RandomForestClassifier(n_estimators=100,  # число базовых моделей 
                               bootstrap=True,    # обучать на подвыборках или всей выборке 
                               max_features=0.5,  # доля случайных признаков для обучения 
                               n_jobs=-1)         # использовать все ядра процессора  
model.fit(X_train, Y_train)    # обучение модели   
Y_hat = model.predict(X_test)  # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')

P_hat = model.predict_proba(X_test)  # можно предсказывать вероятности классов
loss = brier_score_loss(Y_test, P_hat[:,1])  # мера Бриера на вероятности положительного класса
print(f'Мера Бриера ошибки прогноза вероятностей: {loss:.2f}')

Случайный лес для регрессии:
from sklearn.ensemble import RandomForestRegressor
from sklearn.metrics import mean_absolute_error

X_train, X_test, Y_train, Y_test = get_demo_regression_data()

# инициализация модели:
model = RandomForestRegressor(n_estimators=100,  # число базовых моделей
                              bootstrap=True,    # обучать на подвыборках или всей выборке
                              max_features=0.5,  # доля случайных признаков для обучения
                              n_jobs=-1)         # использовать все ядра процессора
model.fit(X_train, Y_train)      # обучение модели   
Y_hat = model.predict(X_test)    # построение прогнозов
print(f'Средний модуль ошибки (MAE): {mean_absolute_error(Y_test, Y_hat):.2f}')

Больше информации. Полный код.

Особо случайные деревья для классификации:
from sklearn.ensemble import ExtraTreesClassifier
from sklearn.metrics import accuracy_score
from sklearn.metrics import brier_score_loss

X_train, X_test, Y_train, Y_test = get_demo_classification_data()  

# инициализация модели:
model = ExtraTreesClassifier(n_estimators=100,  # число базовых моделей 
                             bootstrap=True,    # обучать на подвыборках или всей выборке 
                             max_features=1.0,  # доля случайных признаков для обучения 
                             n_jobs=-1)         # использовать все ядра процессора 
model.fit(X_train, Y_train)       # обучение модели   
Y_hat = model.predict(X_test)     # построение прогнозов
print(f'Точность прогнозов: {100*accuracy_score(Y_test, Y_hat):.1f}%')

P_hat = model.predict_proba(X_test)  # можно предсказывать вероятности классов
loss = brier_score_loss(Y_test, P_hat[:,1])  # мера Бриера на вероятности положительного класса
print(f'Мера Бриера ошибки прогноза вероятностей: {loss:.2f}')

Особо случайные деревья для регрессии:
from sklearn.ensemble import ExtraTreesRegressor
from sklearn.metrics import mean_absolute_error

X_train, X_test, Y_train, Y_test = get_demo_regression_data() 

# инициализация модели:
model = ExtraTreesRegressor(n_estimators=100,  # число базовых моделей  
                            bootstrap=True,    # обучать на подвыборках или всей выборке  
                            max_features=0.5,  # доля случайных признаков для обучения
                            n_jobs=-1)         # использовать все ядра процессора
model.fit(X_train, Y_train)       # обучение модели   
Y_hat = model.predict(X_test)     # построение прогнозов
print(f'Средний модуль ошибки (MAE): {mean_absolute_error(Y_test, Y_hat):.2f}')

Больше информации. Полный код.