Участник:AVKaledin/Метод Random Forest

Описание параллельной реализации алгоритма Random Forest.

Автор: А.В.Каледин (416 группа, 2018 год).

1 Свойства и структура алгоритма

1.1 Общее описание алгоритма

Random forest — метод машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев.

Бэггинг (от Bootstrap aggregation) — один из первых и самых простых видов ансамблей, разработанный Лео Брейманом в 1994 году. Бэггинг основан на статистическом методе бутстрэпа, который позволяет оценивать статистики сложных распределений (математическое описание будет дано ниже).

Метод Random forest сочетает две основные идеи: метод бэггинга и метод случайных подпространств, предложенный Tin Kam Ho. Усовершенствование также заключено в построении некоррелируемых деревьев на основе CART (Classification and Regression Tree).

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

Решающие деревья являются хорошим семейством базовых классификаторов для бэггинга, поскольку они достаточно сложны и могут достигать нулевой ошибки на любой выборке. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом.

1.2 Математическое описание алгоритма

Метод бутстрэпа
Пусть имеется выборка $X$ размера $N$. Равномерно возьмем из выборки $N$ объектов с возвращением. Обозначим новую выборку через $X_1$. Повторяя процедуру $M$ раз, сгенерируем $M$ подвыборок $X_1, X_2, ..., X_M$.

Метод Бэггинга
Пусть имеется обучающая выборка $X$. С помощью бутстрэпа сгенерируем выборки $X_1, X_2, ..., X_M$. Далее на каждой выборке обучим свой классификатор $a_i(x)$. Итоговый классификатор будет усреднять ответы всех этих алгоритмов. В частности, для задачи классификации выбирается решение голосованием, а в задаче регрессии — средним.

Визуализация метода Бэггинга

Алгоритм построения Random forest, состоящего из N деревьев
Для каждого $n=1,…,N$: Сгенерировать выборку $X_n$с помощью бутстрэпа;
Построить решающее дерево $b_n$ по выборке $X_n$:
— по заданному критерию мы выбираем лучший признак, делаем разбиение в дереве по нему и так до исчерпания выборки
— дерево строится, пока в каждом листе не более $n_{min}$ объектов или пока не достигнем определенной высоты дерева
— при каждом разбиении сначала выбирается $m$ случайных признаков из $n$ исходных, и оптимальное разделение выборки ищется только среди них.