Алговики - Вклад [ru]

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

2018-10-21T20:47:52Z

AVKaledin: /* Математическое описание алгоритма */

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

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

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

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

'''Random forest''' — метод машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев<ref> Wikipedia.org: [http://ru.wikipedia.org/wiki/Random_forest Random forest] </ref>. 

'''Бэггинг''' (''от 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'').

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

Решающие деревья являются хорошим семейством базовых классификаторов для бэггинга, поскольку они достаточно сложны и могут достигать нулевой ошибки на любой выборке. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом<ref>Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес. [http://habr.com/company/ods/blog/324402/ Open Data Science]</ref>.

=== Математическое описание алгоритма ===
'''Метод бутстрэпа''' 
Пусть имеется выборка <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>. Итоговый классификатор будет усреднять ответы всех этих алгоритмов. В частности, для задачи классификации выбирается решение голосованием, а в задаче регрессии — средним. 

[[file:Bagging.png|center|thumb|800px|Визуализация метода Бэггинга]] 

'''Алгоритм построения Random forest, состоящего из N деревьев'''<ref>«Введение в машинное обучение», К.В.Воронцов. [http://www.machinelearning.ru Machinelearning.ru]</ref> 
Для каждого <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> исходных, и оптимальное разделение выборки ищется только среди них.
 

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

== Литература ==

 

<references />

[[Категория:Начатые статьи]]

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

2018-10-21T20:36:31Z

AVKaledin: /* Общее описание алгоритма */

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

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

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

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

'''Random forest''' — метод машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев<ref> Wikipedia.org: [http://ru.wikipedia.org/wiki/Random_forest Random forest] </ref>. 

'''Бэггинг''' (''от 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'').

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

Решающие деревья являются хорошим семейством базовых классификаторов для бэггинга, поскольку они достаточно сложны и могут достигать нулевой ошибки на любой выборке. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом<ref>Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес. [http://habr.com/company/ods/blog/324402/ Open Data Science]</ref>.

=== Математическое описание алгоритма ===
'''Метод бутстрэпа''' 
Пусть имеется выборка <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 деревьев'''<ref>«Введение в машинное обучение», К.В.Воронцов. [http://www.machinelearning.ru Machinelearning.ru]</ref> 
Для каждого <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> исходных, и оптимальное разделение выборки ищется только среди них.
 

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

== Литература ==

 

<references />

[[Категория:Начатые статьи]]

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

2018-10-21T20:35:54Z

AVKaledin: Новая страница: «Описание параллельной реализации алгоритма Random Forest. Автор: А.В.Каледин (416 группа, 2018 год)…»

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

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

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

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

'''Random forest''' — метод машинного обучения, предложенный Лео Брейманом и Адель Катлер, заключающийся в использовании ансамбля решающих деревьев<ref> Wikipedia.org: [http://ru.wikipedia.org/wiki/Random_forest Random forest] </ref>. 

'''Бэггинг''' (''от 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).

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

Решающие деревья являются хорошим семейством базовых классификаторов для бэггинга, поскольку они достаточно сложны и могут достигать нулевой ошибки на любой выборке. Метод случайных подпространств позволяет снизить коррелированность между деревьями и избежать переобучения. Базовые алгоритмы обучаются на различных подмножествах признакового описания, которые также выделяются случайным образом<ref>Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес. [http://habr.com/company/ods/blog/324402/ Open Data Science]</ref>.

=== Математическое описание алгоритма ===
'''Метод бутстрэпа''' 
Пусть имеется выборка <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 деревьев'''<ref>«Введение в машинное обучение», К.В.Воронцов. [http://www.machinelearning.ru Machinelearning.ru]</ref> 
Для каждого <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> исходных, и оптимальное разделение выборки ищется только среди них.
 

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

== Литература ==

 

<references />

[[Категория:Начатые статьи]]