Участник:AVKaledin/Метод Random Forest: различия между версиями

Материал из Алговики
Перейти к навигации Перейти к поиску
(Новая страница: «Описание параллельной реализации алгоритма Random Forest. Автор: А.В.Каледин (416 группа, 2018 год)…»)
 
 
(не показана 1 промежуточная версия этого же участника)
Строка 11: Строка 11:
 
'''Бэггинг''' (''от Bootstrap aggregation'') — один из первых и самых простых видов ансамблей, разработанный Лео Брейманом<ref>Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324</ref> в 1994 году. Бэггинг основан на статистическом методе бутстрэпа, который позволяет оценивать статистики сложных распределений (математическое описание будет дано ниже).
 
'''Бэггинг''' (''от Bootstrap aggregation'') — один из первых и самых простых видов ансамблей, разработанный Лео Брейманом<ref>Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324</ref> в 1994 году. Бэггинг основан на статистическом методе бутстрэпа, который позволяет оценивать статистики сложных распределений (математическое описание будет дано ниже).
  
Метод Random forest сочетает две основные идеи: метод бэггинга и метод случайных подпространств, предложенный Tin Kam Ho<ref>Tin Kam Ho. Random decision forests. Conference Paper. IEEE Computer Society Washington, DC, USA ©1995 [http://ect.bell-labs.com/who/tkh/publications/papers/odt.pdf Article]</ref>. Усовершенствование также заключено в построении некоррелируемых деревьев на основе CART (Classification and Regression Tree).  
+
Метод Random forest сочетает две основные идеи: метод бэггинга и метод случайных подпространств, предложенный Tin Kam Ho<ref>Tin Kam Ho. Random decision forests. Conference Paper. IEEE Computer Society Washington, DC, USA ©1995 [http://ect.bell-labs.com/who/tkh/publications/papers/odt.pdf Article]</ref>. Усовершенствование также заключено в построении некоррелируемых деревьев на основе CART (''Classification and Regression Tree'').  
  
 
'''Ансамблирование моделей''' — метод, заключающийся в обучении нескольки базовых моделей с дальнейшей агрегацией результатов по какому-либо правилу.
 
'''Ансамблирование моделей''' — метод, заключающийся в обучении нескольки базовых моделей с дальнейшей агрегацией результатов по какому-либо правилу.
Строка 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>
  
 
== Программная реализация алгоритма ==
 
== Программная реализация алгоритма ==

Текущая версия на 23:47, 21 октября 2018

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

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

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

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

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

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

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

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

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

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

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

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

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


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

2 Программная реализация алгоритма

3 Литература


  1. Wikipedia.org: Random forest
  2. Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324
  3. Tin Kam Ho. Random decision forests. Conference Paper. IEEE Computer Society Washington, DC, USA ©1995 Article
  4. Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес. Open Data Science
  5. «Введение в машинное обучение», К.В.Воронцов. Machinelearning.ru