Прагляд зыходнага тэксту старонкі Метад выпадковага лесу

{{універсальная картка}}
'''Метад выпадковага лесу''' ({{Lang-en|random forest}}) — алгарытм [[Машыннае навучанне|машыннага навучання]], прапанаваны {{нп3|Леа Брэйман|Леа Брэйманам|ru|Брейман, Лео}} і {{нп3|Адэль Катлер|||Adele Cutler}}, які зводзіцца да выкарыстання ансамбля {{нп3|Дрэва рашэнняў|дрэў рашэнняў|ru|Дерево решений}}. Алгарытм спалучае ў сабе дзве асноўныя ідэі: метад {{нп3|Бэгінг|бэгінга|ru|Бэггинг}} Брэймана і {{нп3|метад выпадковых падпрастор|||Random subspace method}}, прапанаваны {{нп3|Цін Кам Хо|||Tin Kam Ho}}. Алгарытм ужываецца для задач класіфікацыі, рэгрэсіі і кластарызацыі. Асноўная ідэя зводзіцца да выкарыстання вялікага {{нп3|Ансамблевае навучанне|ансамбля|ru|Ансамблевое обучение}} {{нп3|Дрэва рашэнняў|дрэў рашэнняў|ru|Дерево решений}}, кожнае з якіх само па сабе дае вельмі невысокую якасць класіфікацыі, але за кошт іх вялікай колькасці вынік атрымліваецца добрым.

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

Найбольш распаўсюджаны спосаб пабудовы дрэў ансамбля — {{нп3|бэгінг||ru|Бэггинг}} ({{Lang-en|bagging}}, скарачэнне ад {{Lang-en|bootstrap aggregation)}} — адбываецца наступным чынам:

# Згенеруем {{нп3|Выбарка|выпадковую паўторную выбарку|ru|Выборка}} памерам <math>N</math> з навучальнай выбаркі. Некаторыя ўзоры трапяць у яе два ці больш разы, тады як у сярэднім <math>N(1-1/N)^N</math> (пры вялікіх <math>N</math> прыкладна <math>N/e</math>, дзе <math>e</math> — [[E (лік)|аснова натуральнага лагарыфма]]) узораў аказваюцца тымі, '''''якія не ўвайшлі ў набор''''' або '''''неадабранымі''''' ({{Lang-en|out-of-bag}}).
# Пабудаваць {{нп3|дрэва рашэнняў||ru|Дерево решений}}, класіфікуе ўзоры дадзенай падвыбаркі, прычым у ходзе стварэння чарговага вузла дрэва будзем выбіраць набор прыкмет, на аснове якіх вырабляецца разбіццё (не з усіх ''M'' прыкмет, а толькі з ''m'' выпадкова выбраных). Выбар найлепшай з гэтых ''m'' прыкмет можа ажыццяўляцца рознымі спосабамі. У арыгінальным метадзе Брэймана выкарыстоўваецца [[крытэрый Джыні]], які прымяняецца таксама ў алгарытме пабудовы вырашальных дрэў {{нп3|CART (алгарытм)|CART|ru|CART (алгоритм)}}. У некаторых рэалізацыях алгарытму замест яго выкарыстоўваецца [[крытэрый прыросту інфармацыі]].
# Дрэва будуецца да поўнага вычарпання падвыбаркі і не падвяргаецца працэдуры {{нп3|Прунінг|прунінга||Pruning (decision trees)}} — адсячэнне галін), у адрозненне ад дрэў рашэнняў алгарытмаў накшталт {{нп3|CART (алгарытм)|CART|ru|CART (алгоритм)}} або {{нп3|C4.5||ru|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}}</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}}</ref>.

== Перавагі ==

* Здольнасць эфектыўна апрацоўваць дадзеныя з вялікім лікам {{нп3|Прыкмета (машыннае навучанне)|прыкмет|ru|Признак (машинное обучение)}} і класаў.
* Неадчувальнасць да маштабавання (і наогул да любых манатонных пераўтварэнняў) значэнняў прыкмет.
* Аднолькава добра апрацоўваюцца як бесперапынныя, так і дыскрэтныя прыкметы. Існуюць метады пабудовы дрэў па дадзеных з прапушчанымі значэннямі прыкмет.
* Існуюць метады ацэньвання {{нп3|Статыстычны крытэрый|значнасці|ru|Статистический критерий}} асобных прыкмет у мадэлі.
* Унутраная ацэнка здольнасці мадэлі да абагульнення (тэст па неадабраных узорах).
* Высокая паралелізавальнасць і {{нп3|маштабаванасць||ru|Масштабируемость}}.

== Недахопы ==

* Вялікі памер атрыманых мадэляў. Патрабуецца <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. |год=2015}}</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. |год=2016}}</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}}</ref>.
{{зноскі}}

== Літаратура ==

* Hastie, T., Tibshirani R., Friedman J. Chapter 15. Random Forests // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — <nowiki>ISBN 978-0-387-84857-0</nowiki>..

== Спасылкі ==

; Рэалізацыі
:

* [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]{{Архівавана|url=https://web.archive.org/web/20150402150941/https://mahout.apache.org/users/classification/partial-implementation.html |date=2 красавіка 2015 }}.
{{Бібліяінфармацыя}}
[[Катэгорыя:Машыннае навучанне]]
[[Катэгорыя:Тэорыя прыняцця рашэнняў]]