Просмотр кода страницы Метод случайного леса

'''Метод случайного леса''' ({{lang-en|random forest}}) — алгоритм [[Машинное обучение|машинного обучения]], предложенный [[Брейман, Лео|Лео Брейманом]]<ref>{{статья
|заглавие=Random Forests
|издание={{iw|Machine Learning (журнал)|Machine Learning||Machine Learning (journal)}}
|том=45
|номер=1
|страницы=5—32
|doi=10.1023/A:1010933404324
|язык=en
|автор=[[Брейман, Лео|Breiman, Leo]]
|год=2001
|тип=journal}}{{ref-en}}{{проверено|07|06|2009}}</ref><ref>[http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm Описание алгоритма на сайте Лео Бреймана] {{webarchive|url=https://web.archive.org/web/20080622230434/http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm |date=2008-06-22 }}{{ref-en}}{{проверено|07|06|2009}}</ref> и {{iw|Катлер, Адель|Адель Катлер||Adele Cutler}}, заключающийся в использовании ансамбля [[Дерево принятия решений|решающих деревьев]]. Алгоритм сочетает в себе две основные идеи: метод [[бэггинг]]а Бреймана и {{iw|метод случайных подпространств|||Random subspace method}}, предложенный {{iw|Тин Кам Хо|||Tin Kam Ho}}. Алгоритм применяется для задач классификации, регрессии и кластеризации. Основная идея заключается в использовании большого [[Ансамбль (машинное обучение)|ансамбля]] [[Дерево принятия решений|решающих деревьев]], каждое из которых само по себе даёт очень невысокое качество классификации, но за счёт их большого количества результат получается хорошим.

== Алгоритм обучения классификатора ==
Пусть обучающая выборка состоит из ''N'' образцов, [[размерность пространства]] признаков равна ''M'',
и задан параметр ''m'' (в задачах классификации обычно <math>m \approx \sqrt{M}</math>) как неполное количество признаков для обучения.

Наиболее распространённый способ построения деревьев ансамбля — [[бэггинг]] ({{lang-en|bagging}}, сокращение от {{lang-en|bootstrap aggregation)}} — производится следующим образом:
# Сгенерируем [[Выборка#Простая повторная выборка|случайную повторную подвыборку]] размером <math>N</math> из обучающей выборки. Некоторые образцы попадут в неё два или более раза, тогда как в среднем <math>N(1-1/N)^N</math> (при больших <math>N</math> примерно <math>N/e</math>, где [[e (число)|<math>e</math>]] — [[E (число)|основание натурального логарифма]]) образцов оказываются '''''не вошедшими в набор''''' или '''''неотобранными''''' ({{lang-en|out-of-bag}}).
# Построим [[Дерево принятия решений|решающее дерево]], классифицирующее образцы данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать набор признаков, на основе которых производится разбиение (не из всех ''M'' признаков, а лишь из ''m'' случайно выбранных). Выбор наилучшего из этих ''m'' признаков может осуществляться различными способами. В оригинальном методе Бреймана используется [[критерий Джини]], применяющийся также в алгоритме построения решающих деревьев [[CART (алгоритм)|CART]]. В некоторых реализациях алгоритма вместо него используется [[критерий прироста информации]]<ref>[http://cwiki.apache.org/MAHOUT/random-forests.html Описание процедуры построения деревьев, применяющейся в Apache Mahout] {{Wayback|url=http://cwiki.apache.org/MAHOUT/random-forests.html |date=20120513133842 }}{{ref-en}}{{проверено|07|06|2009}}</ref>.
# Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга ({{lang-en|{{iw|Pruning (decision trees)|pruning}}}} — отсечение ветвей), в отличие от решающих деревьев алгоритмов вроде [[CART (алгоритм)|CART]] или [[C4.5]].

Классификация объектов проводится путём голосования: каждое дерево комитета относит классифицируемый объект к одному из классов, а побеждает класс, за который проголосовало наибольшее число деревьев.

Оптимальное число деревьев подбирается таким образом, чтобы минимизировать ошибку классификатора на тестовой выборке. В случае её отсутствия, минимизируется оценка ошибки на не вошедших в набор образцах.

== Оценка важности переменных ==
Случайные леса, получаемые описанными выше методами, могут быть естественным образом использованы для оценки важности переменных в задачах [[Линейная регрессия|регрессии]] и [[Задача классификации|классификации]]. Следующий способ такой оценки был описан Брейманом.

Первый шаг в оценке важности переменной в тренировочном наборе <math>\mathcal{D}_n =\{(X_i, Y_i)\}_{i=1}^n</math> — тренировка случайного леса на этом наборе. Во время процесса построения модели для каждого элемента тренировочного набора записывается так называемая {{нп2|ошибка неотобранных элементов|||out-of-bag error}}. Затем для каждой сущности такая ошибка усредняется по всему случайному лесу.

Для того, чтобы оценить важность <math>j</math>-го параметра после тренировки, значения <math>j</math>-го параметра перемешиваются для всех записей тренировочного набора и ошибка неотобранных элементов вычисляется снова. Важность параметра оценивается путём усреднения по всем деревьям разности показателей ошибок неотобранных элементов до и после перемешивания значений. При этом значения таких ошибок нормализуются на [[Среднеквадратическое отклонение|стандартное отклонение]].

Параметры выборки, которые дают бо́льшие значения, считаются более важными для тренировочного набора. Метод имеет потенциальный недостаток — для категориальных переменных с большим количеством значений метод склонен считать такие переменные более важными. Частичное перемешивание значений в этом случае может снижать влияние этого эффекта<ref>{{cite conference
|author=Deng,H.|author2=Runger, G. |author3=Tuv, E.
 |title=Bias of importance measures for multi-valued attributes and solutions
|conference=Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN)
|year=2011|pages=293–300
}}</ref><ref>{{статья |заглавие=Permutation importance:a corrected feature importance measure |издание=Bioinformatics |doi=10.1093/bioinformatics/btq134 |ссылка=http://bioinformatics.oxfordjournals.org/content/early/2010/04/12/bioinformatics.btq134.abstract |язык=en |тип=journal |автор=Altmann A., Tolosi L., Sander O., Lengauer T. |год=2010 |archivedate=2016-11-08 |archiveurl=https://web.archive.org/web/20161108094546/http://bioinformatics.oxfordjournals.org/content/early/2010/04/12/bioinformatics.btq134.abstract }}</ref>. Из групп коррелирующих параметров, важность которых оказывается одинаковой, выбираются меньшие по численности группы<ref>{{статья |заглавие=Classification with correlated features: unreliability of feature ranking and solutions. |издание=Bioinformatics |doi=10.1093/bioinformatics/btr300 |ссылка=http://bioinformatics.oxfordjournals.org/content/27/14/1986.abstract |язык=en |тип=journal |автор=Tolosi L., Lengauer T. |год=2011 |archivedate=2015-08-31 |archiveurl=https://web.archive.org/web/20150831012131/http://bioinformatics.oxfordjournals.org/content/27/14/1986.abstract }}</ref>.

== Достоинства ==
* Способность эффективно обрабатывать данные с большим числом [[Признак (машинное обучение)|признаков]] и классов.
* Нечувствительность к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков.
* Одинаково хорошо обрабатываются как непрерывные, так и дискретные признаки. Существуют методы построения деревьев по данным с пропущенными значениями признаков.
* Существуют методы оценивания [[критерий значимости|значимости]] отдельных признаков в модели.
* Внутренняя оценка способности модели к обобщению (тест по неотобранным образцам).
* Высокая параллелизуемость и [[масштабируемость]].

== Недостатки ==
* Большой размер получающихся моделей. Требуется <math>O(K)</math> памяти для хранения модели, где <math>K</math> — число деревьев.

== Использование в научных работах ==
Алгоритм используется в научных работах, например, для оценки качества статей [[Википедия|Википедии]]<ref>{{статья |заглавие=Modelling the Quality of Attributes in Wikipedia Infoboxes |ссылка=https://link.springer.com/chapter/10.1007/978-3-319-26762-3_27 |издание=Lecture Notes in Business Information Processing |том=228 |страницы=308—320 |doi=10.1007/978-3-319-26762-3_27 |язык=en |тип=journal |автор=Węcel K., Lewoniewski W. |число=2 |месяц=12 |год=2015 |archivedate=2018-01-22 |archiveurl=https://web.archive.org/web/20180122125837/https://link.springer.com/chapter/10.1007/978-3-319-26762-3_27 }}</ref><ref>{{статья |заглавие=Quality and Importance of Wikipedia Articles in Different Languages |ссылка=https://link.springer.com/chapter/10.1007/978-3-319-46254-7_50 |издание=Information and Software Technologies. ICIST 2016. Communications in Computer and Information Science |том=639 |страницы=613—624 |doi=10.1007/978-3-319-46254-7_50 |язык=en |тип=journal |автор=Lewoniewski W., Węcel K., Abramowicz W. |число=22 |месяц=9 |год=2016 |archivedate=2018-01-22 |archiveurl=https://web.archive.org/web/20180122125730/https://link.springer.com/chapter/10.1007/978-3-319-46254-7_50 }}</ref><ref>{{статья |заглавие=Tell me more: An actionable quality model for wikipedia |ссылка=https://dl.acm.org/citation.cfm?id=2491063 |издание=WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration |doi=10.1145/2491055.2491063 |язык=en |тип=journal |автор=Warncke-Wang M., Cosley D., Riedl J. |год=2013 |archivedate=2021-04-01 |archiveurl=https://web.archive.org/web/20210401062955/https://dl.acm.org/doi/10.1145/2491055.2491063 }}</ref>.

== Примечания ==
{{примечания}}

== Литература ==
* {{Книга:The Elements of Statistical Learning|2009|часть=Chapter 15. Random Forests}}

== Ссылки ==
'''Реализации:'''
* [http://www.stat.berkeley.edu/~breiman/RandomForests/cc_software.htm Авторская реализация] Бреймана и Катлер на языке [[Fortran|Fortran 77]]
* Пакет [http://cran.r-project.org/web/packages/randomForest/index.html randomForest] для [[R (язык программирования)|R]] — портированная версия оригинального авторского кода в R
* Пакет [http://cran.r-project.org/web/packages/party/index.html party] для [[R (язык программирования)|R]], содержит модификацию алгоритма
* [https://web.archive.org/web/20090506094817/http://alglib.sources.ru/dataanalysis/decisionforest.php Реализация модификации алгоритма на alglib.sources.ru]
* [http://code.google.com/p/fast-random-forest/ FastRandomForest]
* [https://mahout.apache.org/users/classification/partial-implementation.html Apache Mahout] {{Wayback|url=https://mahout.apache.org/users/classification/partial-implementation.html |date=20150402150941 }}.
{{rq|style|tex}}
{{Машинное обучение}}

[[Категория:Деревья принятия решений]]
[[Категория:Теория принятия решений]]
[[Категория:Машинное обучение]]