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

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

Алгарытм навучання класіфікатара

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

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

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

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

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

Ацэнка важнасці пераменных

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

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

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

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

Перавагі

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

Недахопы

• Вялікі памер атрыманых мадэляў. Патрабуецца $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. — ISBN 978-0-387-84857-0..

Спасылкі

Рэалізацыі

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