Метад выпадковага лесу

**Метад выпадковага лесу** () — алгарытм машыннага навучання, прапанаваны  і , які зводзіцца да выкарыстання ансамбля . Алгарытм спалучае ў сабе дзве асноўныя ідэі: метад  Брэймана і , прапанаваны . Алгарытм ужываецца для задач класіфікацыі, рэгрэсіі і кластарызацыі. Асноўная ідэя зводзіцца да выкарыстання вялікага  , кожнае з якіх само па сабе дае вельмі невысокую якасць класіфікацыі, але за кошт іх вялікай колькасці вынік атрымліваецца добрым.

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

Найбольш распаўсюджаны спосаб пабудовы дрэў ансамбля —  (, скарачэнне ад  — адбываецца наступным чынам:

# Згенеруем  памерам N з навучальнай выбаркі. Некаторыя ўзоры трапяць у яе два ці больш разы, тады як у сярэднім N(1-1/N)^N (пры вялікіх N прыкладна N/e, дзе e — аснова натуральнага лагарыфма) узораў аказваюцца тымі, ***якія не ўвайшлі ў набор*** або ***неадабранымі*** ().
# Пабудаваць , класіфікуе ўзоры дадзенай падвыбаркі, прычым у ходзе стварэння чарговага вузла дрэва будзем выбіраць набор прыкмет, на аснове якіх вырабляецца разбіццё (не з усіх *M* прыкмет, а толькі з *m* выпадкова выбраных). Выбар найлепшай з гэтых *m* прыкмет можа ажыццяўляцца рознымі спосабамі. У арыгінальным метадзе Брэймана выкарыстоўваецца крытэрый Джыні, які прымяняецца таксама ў алгарытме пабудовы вырашальных дрэў . У некаторых рэалізацыях алгарытму замест яго выкарыстоўваецца крытэрый прыросту інфармацыі.
# Дрэва будуецца да поўнага вычарпання падвыбаркі і не падвяргаецца працэдуры  — адсячэнне галін), у адрозненне ад дрэў рашэнняў алгарытмаў накшталт  або .

Класіфікацыя аб’ектаў праводзіцца шляхам галасавання: кожнае дрэва камітэта адносіць класіфікавальны аб’ект да аднаго з класаў, а перамагае клас, за які прагаласавала найбольшая колькасць дрэў.

Аптымальная колькасць дрэў падбіраецца такім чынам, каб мінімізаваць памылку класіфікатара на тэставай выбарцы. У выпадку яе адсутнасці, мінімізуецца ацэнка памылкі на ўзорах, якія не ўвайшлі ў набор.

## Ацэнка важнасці пераменных 
Выпадковыя лясы, якія атрымліваюцца апісанымі вышэй метадамі, могуць быць натуральным чынам выкарыстаны для ацэнкі важнасці пераменных у задачах рэгрэсіі і класіфікацыі. Наступны спосаб такой ацэнкі быў апісаны Брэйманам.

Першы крок у ацэнцы важнасці пераменнай у трэніровачным наборы \mathcal{D}_n =\{(X_i, Y_i)\}_{i=1}^n — трэніроўка выпадковага лесу на гэтым наборы. Падчас працэсу пабудовы мадэлі для кожнага элемента трэніровачнага набору запісваецца так званая . Затым для кожнай сутнасці такая памылка асерадняецца па ўсім выпадковым лесе.

Каб ацаніць важнасць j-га параметру пасля трэніроўкі, значэнні j-га параметру змешваюцца для ўсіх запісаў трэніровачнага набору і памылка неадабраных элементаў вылічваецца зноў. Важнасць параметру ацэньваецца шляхам асераднення па ўсіх дрэвах рознасці паказчыкаў памылак неадабраных элементаў да і пасля мяшання значэнняў. Пры гэтым значэнні такіх памылак нармалізуюцца на стандартнае адхіленне.

Параметры выбаркі, якія даюць вялікія значэнні, лічацца больш важнымі для трэніровачнага набору. Метад мае патэнцыйны недахоп — для катэгарыяльных пераменных з вялікай колькасцю значэнняў метад схільны лічыць такія пераменныя больш важнымі. Частковае перамешванне значэнняў у гэтым выпадку можа зніжаць ўплыў гэтага эфекту. З груп карэліруючых параметраў, важнасць якіх аказваецца аднолькавай, выбіраюцца меншыя па колькасці групы.

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

## Недахопы 
* Вялікі памер атрыманых мадэляў. Патрабуецца O(K) памяці для захоўвання мадэлі, дзе K — колькасць дрэў.

## Выкарыстанне ў навуковых працах 
Алгарытм выкарыстоўваецца ў навуковых працах, напрыклад, для ацэнкі якасці артыкулаў Вікіпедыі.

## Літаратура 
* 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. — ..

## Спасылкі 
; Рэалізацыі
:

* Аўтарская рэалізацыя Брэймана і Катлер на мове Fortran 77
* Пакет randomForest для R — партаванай версіі арыгінальнага аўтарскага коду ў R
* Пакет party для R, змяшчае мадыфікацыю алгарытму
* Рэалізацыя мадыфікацыі алгарытму на alglib.sources.ru
* FastRandomForest
* Apache Mahout.

Катэгорыя:Машыннае навучанне
Катэгорыя:Тэорыя прыняцця рашэнняў