Участник:AVKaledin/Метод Random Forest: различия между версиями
AVKaledin (обсуждение | вклад) |
AVKaledin (обсуждение | вклад) |
||
| Строка 23: | Строка 23: | ||
'''Метод Бэггинга''' <br> | '''Метод Бэггинга''' <br> | ||
Пусть имеется обучающая выборка <math>X</math>. С помощью бутстрэпа сгенерируем выборки <math>X_1, X_2, ..., X_M</math>. Далее на каждой выборке обучим свой классификатор <math>a_i(x)</math>. Итоговый классификатор будет усреднять ответы всех этих алгоритмов. В частности, для задачи классификации выбирается решение голосованием, а в задаче регрессии — средним.<br> | Пусть имеется обучающая выборка <math>X</math>. С помощью бутстрэпа сгенерируем выборки <math>X_1, X_2, ..., X_M</math>. Далее на каждой выборке обучим свой классификатор <math>a_i(x)</math>. Итоговый классификатор будет усреднять ответы всех этих алгоритмов. В частности, для задачи классификации выбирается решение голосованием, а в задаче регрессии — средним.<br> | ||
[[file:Bagging.png|center|thumb|800px|Визуализация метода Бэггинга]] <br> | |||
'''Алгоритм построения Random forest, состоящего из N деревьев'''<ref>«Введение в машинное обучение», К.В.Воронцов. [http://www.machinelearning.ru Machinelearning.ru]</ref> <br> | '''Алгоритм построения Random forest, состоящего из N деревьев'''<ref>«Введение в машинное обучение», К.В.Воронцов. [http://www.machinelearning.ru Machinelearning.ru]</ref> <br> | ||
| Строка 31: | Строка 33: | ||
— дерево строится, пока в каждом листе не более <math>n_{min}</math> объектов или пока не достигнем определенной высоты дерева<br> | — дерево строится, пока в каждом листе не более <math>n_{min}</math> объектов или пока не достигнем определенной высоты дерева<br> | ||
— при каждом разбиении сначала выбирается <math>m</math> случайных признаков из <math>n</math> исходных, и оптимальное разделение выборки ищется только среди них. | — при каждом разбиении сначала выбирается <math>m</math> случайных признаков из <math>n</math> исходных, и оптимальное разделение выборки ищется только среди них. | ||
<br> | <br> | ||
== Программная реализация алгоритма == | == Программная реализация алгоритма == | ||
Текущая версия от 20:47, 21 октября 2018
Описание параллельной реализации алгоритма Random Forest.
Автор: А.В.Каледин (416 группа, 2018 год).
Свойства и структура алгоритма
Общее описание алгоритма
Random forest — метод машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев[1].
Бэггинг (от Bootstrap aggregation) — один из первых и самых простых видов ансамблей, разработанный Лео Брейманом[2] в 1994 году. Бэггинг основан на статистическом методе бутстрэпа, который позволяет оценивать статистики сложных распределений (математическое описание будет дано ниже).
Метод Random forest сочетает две основные идеи: метод бэггинга и метод случайных подпространств, предложенный Tin Kam Ho[3]. Усовершенствование также заключено в построении некоррелируемых деревьев на основе CART (Classification and Regression Tree).
Ансамблирование моделей — метод, заключающийся в обучении нескольки базовых моделей с дальнейшей агрегацией результатов по какому-либо правилу.
Решающие деревья являются хорошим семейством базовых классификаторов для бэггинга, поскольку они достаточно сложны и могут достигать нулевой ошибки на любой выборке. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом[4].
Математическое описание алгоритма
Метод бутстрэпа
Пусть имеется выборка [math]\displaystyle{ X }[/math] размера [math]\displaystyle{ N }[/math]. Равномерно возьмем из выборки [math]\displaystyle{ N }[/math] объектов с возвращением. Обозначим новую выборку через [math]\displaystyle{ X_1 }[/math]. Повторяя процедуру [math]\displaystyle{ M }[/math] раз, сгенерируем [math]\displaystyle{ M }[/math] подвыборок [math]\displaystyle{ X_1, X_2, ..., X_M }[/math].
Метод Бэггинга
Пусть имеется обучающая выборка [math]\displaystyle{ X }[/math]. С помощью бутстрэпа сгенерируем выборки [math]\displaystyle{ X_1, X_2, ..., X_M }[/math]. Далее на каждой выборке обучим свой классификатор [math]\displaystyle{ a_i(x) }[/math]. Итоговый классификатор будет усреднять ответы всех этих алгоритмов. В частности, для задачи классификации выбирается решение голосованием, а в задаче регрессии — средним.
Алгоритм построения Random forest, состоящего из N деревьев[5]
Для каждого [math]\displaystyle{ n=1,…,N }[/math]:
Сгенерировать выборку [math]\displaystyle{ X_n }[/math]с помощью бутстрэпа;
Построить решающее дерево [math]\displaystyle{ b_n }[/math] по выборке [math]\displaystyle{ X_n }[/math]:
— по заданному критерию мы выбираем лучший признак, делаем разбиение в дереве по нему и так до исчерпания выборки
— дерево строится, пока в каждом листе не более [math]\displaystyle{ n_{min} }[/math] объектов или пока не достигнем определенной высоты дерева
— при каждом разбиении сначала выбирается [math]\displaystyle{ m }[/math] случайных признаков из [math]\displaystyle{ n }[/math] исходных, и оптимальное разделение выборки ищется только среди них.
Программная реализация алгоритма
Литература
- ↑ Wikipedia.org: Random forest
- ↑ Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324
- ↑ Tin Kam Ho. Random decision forests. Conference Paper. IEEE Computer Society Washington, DC, USA ©1995 Article
- ↑ Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес. Open Data Science
- ↑ «Введение в машинное обучение», К.В.Воронцов. Machinelearning.ru