www.wikidata.uk-ua.nina.az

Random forest англ випадковий ліс ансамблевий метод en машинного навчання для класифікації регресії та інших завдань яки

Random forest

Random forest (англ. випадковий ліс) — ансамблевий метод[en] машинного навчання для класифікації, регресії та інших завдань, який працює за допомогою побудови численних дерев прийняття рішень під час тренування моделі й продукує моду для класів (класифікацій) або усереднений прогноз (регресія) побудованих дерев. Недоліком є схильність до перенавчання.

Розширення алгоритму було запропоновано Лео Брейманом і Аделем Катлером, «Random Forests» є їхньою торговою маркою. Алгоритм поєднує в собі дві основні ідеї: метод беггінга Бреймана і метод випадкових підпросторів, запропонований Tin Kam Ho.

Алгоритм навчання класифікатора ред.

Нехай навчальна вибірка складається з N прикладів, розмірність простору ознак дорівнює M, і заданий параметр m (в задачах класифікації зазвичай ).

Усі дерева комітету будуються незалежно один від одного за такою процедурою:

  1. Згенеруємо випадкову підвибірку з повторенням розміром n з навчальної вибірки. (Таким чином, деякі приклади потраплять в неї кілька разів, а приблизно N/3 прикладів не ввійдуть у неї взагалі).
  2. Далі випадково обиремо m предикторів (ознак) із М.
  3. Побудуємо дерево рішень, яке класифікує приклади даної підвибірки, причому в ході створення чергового вузла дерева будемо вибирати ознаку, на основі якої проводиться розбиття, не з усіх M ознак, а лише з m випадково вибраних. Вибір найкращого з цих m ознак може здійснюватися різними способами. В оригінальному коді Брейман використовується критерій Джині, що застосовується також в алгоритмі побудови вирішальних дерев CART. У деяких реалізаціях алгоритму замість нього використовується критерій приросту інформації[en].
  4. Розділимо ознаку Х на два класи, Xі Sі та Xі < Sі.
  5. Виміряємо гомогенність у двох нових класах за допомогую критерію Джині.
  6. Оберемо таке значення «спліт-поінту» Sі ознаки Х, для якого досягнуто максимальної гомогенності класу.
  7. Дерево будується до повного вичерпання підвибірки і не піддається процедурі відсікання[en] (на відміну від дерев рішень, побудованих за таким алгоритмам, як CART або C4.5).
  8. Повертаємося до пункту 1. генеруємо нову вибірку і повторюємо пункти 2. — 4. будуючи наступне дерево. Чим більше дерев побудовано, тим меншою буде помилка класифікатора на тестовій вибірці.

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

Оптимальне число дерев підбирається таким чином, щоб мінімізувати помилку класифікатора на тестовій вибірці. У разі її відсутності, мінімізується оцінка помилки out-of-bag: частка прикладів навчальної вибірки, неправильно класифікованих комітетом, якщо не враховувати голоси дерев на прикладах, що входять в їх власну навчальну підвибірку.

Оцінка важливості змінних ред.

Випадкові ліси, отримані в результаті застосування технік, описаних раніше, можуть бути природним чином використані для оцінки важливості змінних в задачах регресії та класифікації. Наступний спосіб такої оцінки був описаний Breiman.

Перший крок в оцінці важливості змінної в тренувальному наборі — тренування випадкового лісу на цьому наборі. Під час процесу побудови моделі для кожного елемента тренувального набору вважається так звана out-of-bag — помилка. Потім для кожної сутності така помилка опосередковується по всьому випадковому лісі.

Для того, щоб оцінити важливість -ого параметра після тренування, значення -ого параметра перемішуються для всіх записів тренувального набору та out-of-bag — помилка рахується знову. Важливість параметра оцінюється шляхом усереднення по всіх деревах різниці показників out-of-bag — помилок до і після перемішування значень. При цьому значення таких помилок нормалізуються на стандартне відхилення.

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

Переваги ред.

  • Здатність ефективно обробляти дані з великим числом ознак і класів.
  • Нечутливість до масштабування (і взагалі до будь-яких монотонних перетворень) значень ознак.
  • Однаково добре обробляються як безперервні, так і дискретні ознаки. Існують методи побудови дерев за даними з пропущеними значеннями ознак.
  • Існують методи оцінювання значущості окремих ознак в моделі.
  • Внутрішня оцінка здатності моделі до узагальнення (тест out-of-bag).
  • Здатність працювати паралельно в багато потоків.

Недоліки ред.

  • Алгоритм схильний до перенавчання на деяких завданнях, особливо з великою кількістю шумів.
  • Великий розмір отримуваних моделей. Потрібно пам'яті для зберігання моделі, де  — число дерев.

Реалізації ред.

Примітки ред.

  1. Breiman, Leo (2001). Random Forests. Machine Learning 45 (1): 5–32. doi:10.1023/A:1010933404324. (англ.)(Перевірено 7 червня 2009)
  2. Опис алгоритму на сайті Лео Бреймана [ 22 червня 2008 у Wayback Machine.](англ.)(Перевірено 7 червня 2009)
  3. Опис процедури побудови дерев, яка застосовується в Apache Mahout [ 13 травня 2012 у Wayback Machine.] (англ.) (Перевірено 7 червня 2009)
  4. [~Download~] Practical Statistics for Data Scientists: 50+ Essential Concepts Using R and Python BY : Peter Bruce - opo iki a. sites.google.com. Процитовано 21 травня 2021. 
  5. Deng,H.; Runger, G.; Tuv, E. (2011). Bias of importance measures for multi-valued attributes and solutions Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN). с. 293–300. 
  6. Altmann A, Tolosi L, Sander O, Lengauer T (2010). . Bioinformatics. doi:10.1093/bioinformatics/btq134. Архів оригіналу за 8 листопада 2016. Процитовано 17 грудня 2014. 
  7. Tolosi L, Lengauer T (2011). . Bioinformatics. doi:10.1093/bioinformatics/btr300. Архів оригіналу за 31 серпня 2015. Процитовано 17 грудня 2014. 
  8. Segal, Mark R. (April 14 2004). . Center for Bioinformatics & Molecular Biostatistics. Архів оригіналу за 16 жовтня 2009. Процитовано 17 грудня 2014. (англ.)(Перевірено 7 червня 2009)

Література ред.

  • Trevor Hastie, Robert Tibshirani, Jerome Friedman. Chapter 15. Random Forests // The Elements of Statistical Learning. — 2009. — С. 587-623. з джерела 28 вересня 2018
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
Random forest angl vipadkovij lis ansamblevij metod en mashinnogo navchannya dlya klasifikaciyi regresiyi ta inshih zavdan yakij pracyuye za dopomogoyu pobudovi chislennih derev prijnyattya rishen pid chas trenuvannya modeli j produkuye modu dlya klasiv klasifikacij abo userednenij prognoz regresiya pobudovanih derev Nedolikom ye shilnist do perenavchannya Rozshirennya algoritmu bulo zaproponovano Leo Brejmanom 1 2 i Adelem Katlerom Random Forests ye yihnoyu torgovoyu markoyu Algoritm poyednuye v sobi dvi osnovni ideyi metod begginga Brejmana i metod vipadkovih pidprostoriv zaproponovanij Tin Kam Ho Zmist 1 Algoritm navchannya klasifikatora 2 Ocinka vazhlivosti zminnih 3 Perevagi 4 Nedoliki 5 Realizaciyi 6 Primitki 7 LiteraturaAlgoritm navchannya klasifikatora red Nehaj navchalna vibirka skladayetsya z N prikladiv rozmirnist prostoru oznak dorivnyuye M i zadanij parametr m v zadachah klasifikaciyi zazvichaj m M displaystyle m approx sqrt M nbsp Usi dereva komitetu buduyutsya nezalezhno odin vid odnogo za takoyu proceduroyu Zgeneruyemo vipadkovu pidvibirku z povtorennyam rozmirom n z navchalnoyi vibirki Takim chinom deyaki prikladi potraplyat v neyi kilka raziv a priblizno N 3 prikladiv ne vvijdut u neyi vzagali Dali vipadkovo obiremo m prediktoriv oznak iz M Pobuduyemo derevo rishen yake klasifikuye prikladi danoyi pidvibirki prichomu v hodi stvorennya chergovogo vuzla dereva budemo vibirati oznaku na osnovi yakoyi provoditsya rozbittya ne z usih M oznak a lishe z m vipadkovo vibranih Vibir najkrashogo z cih m oznak mozhe zdijsnyuvatisya riznimi sposobami V originalnomu kodi Brejman vikoristovuyetsya kriterij Dzhini sho zastosovuyetsya takozh v algoritmi pobudovi virishalnih derev CART U deyakih realizaciyah algoritmu zamist nogo vikoristovuyetsya kriterij prirostu informaciyi en 3 Rozdilimo oznaku H na dva klasi Xi displaystyle geq nbsp Si ta Xi lt Si Vimiryayemo gomogennist u dvoh novih klasah za dopomoguyu kriteriyu Dzhini Oberemo take znachennya split pointu Si oznaki H dlya yakogo dosyagnuto maksimalnoyi gomogennosti klasu Derevo buduyetsya do povnogo vicherpannya pidvibirki i ne piddayetsya proceduri vidsikannya en na vidminu vid derev rishen pobudovanih za takim algoritmam yak CART abo C4 5 Povertayemosya do punktu 1 generuyemo novu vibirku i povtoryuyemo punkti 2 4 buduyuchi nastupne derevo Chim bilshe derev pobudovano tim menshoyu bude pomilka klasifikatora na testovij vibirci 4 Klasifikaciya ob yektiv provoditsya shlyahom golosuvannya kozhne derevo komitetu vidnosit ob yekt yakij klasifikuyetsya do odnogo z klasiv i peremagaye klas za yakij progolosuvalo najbilshe chislo derev Optimalne chislo derev pidbirayetsya takim chinom shob minimizuvati pomilku klasifikatora na testovij vibirci U razi yiyi vidsutnosti minimizuyetsya ocinka pomilki out of bag chastka prikladiv navchalnoyi vibirki nepravilno klasifikovanih komitetom yaksho ne vrahovuvati golosi derev na prikladah sho vhodyat v yih vlasnu navchalnu pidvibirku Ocinka vazhlivosti zminnih red Vipadkovi lisi otrimani v rezultati zastosuvannya tehnik opisanih ranishe mozhut buti prirodnim chinom vikoristani dlya ocinki vazhlivosti zminnih v zadachah regresiyi ta klasifikaciyi Nastupnij sposib takoyi ocinki buv opisanij Breiman Pershij krok v ocinci vazhlivosti zminnoyi v trenuvalnomu nabori trenuvannya vipadkovogo lisu na comu nabori Pid chas procesu pobudovi modeli dlya kozhnogo elementa trenuvalnogo naboru vvazhayetsya tak zvana out of bag pomilka Potim dlya kozhnoyi sutnosti taka pomilka oposeredkovuyetsya po vsomu vipadkovomu lisi Dlya togo shob ociniti vazhlivist j displaystyle j nbsp ogo parametra pislya trenuvannya znachennya j displaystyle j nbsp ogo parametra peremishuyutsya dlya vsih zapisiv trenuvalnogo naboru ta out of bag pomilka rahuyetsya znovu Vazhlivist parametra ocinyuyetsya shlyahom userednennya po vsih derevah riznici pokaznikiv out of bag pomilok do i pislya peremishuvannya znachen Pri comu znachennya takih pomilok normalizuyutsya na standartne vidhilennya Parametri vibirki yaki dayut bilshi znachennya vvazhayutsya bilsh vazhlivimi dlya trenuvalnogo naboru Metod maye nastupnij potencijnij nedolik dlya kategorialnih zminnih z velikoyu kilkistyu znachen metod shilnij vvazhati taki zminni bilsh vazhlivimi Chastkove perevazhennya znachen v comu vipadku mozhe znizhuvati vpliv cogo efektu 5 6 Yaksho dani mistyat grupi korelovanih oznak sho mayut podibne znachennya dlya rezultatu to bilsh dribni grupi mayut perevagi nad bilshimi grupami 7 Perevagi red Zdatnist efektivno obroblyati dani z velikim chislom oznak i klasiv Nechutlivist do masshtabuvannya i vzagali do bud yakih monotonnih peretvoren znachen oznak Odnakovo dobre obroblyayutsya yak bezperervni tak i diskretni oznaki Isnuyut metodi pobudovi derev za danimi z propushenimi znachennyami oznak Isnuyut metodi ocinyuvannya znachushosti okremih oznak v modeli Vnutrishnya ocinka zdatnosti modeli do uzagalnennya test out of bag Zdatnist pracyuvati paralelno v bagato potokiv Nedoliki red Algoritm shilnij do perenavchannya na deyakih zavdannyah osoblivo z velikoyu kilkistyu shumiv 8 Velikij rozmir otrimuvanih modelej Potribno O N K displaystyle O NK nbsp pam yati dlya zberigannya modeli de K displaystyle K nbsp chislo derev Realizaciyi red Avtorska realizaciya Arhivovano 25 lyutogo 2021 u Wayback Machine Brejman i Katler na movi Fortran77 Paket randomForest Arhivovano 8 bereznya 2021 u Wayback Machine dlya R portovana versiya originalnogo avtorskogo kodu v R Paket party Arhivovano 24 lyutogo 2021 u Wayback Machine dlya R mistit modifikaciyu algoritmu Isnuyut realizaciyi algoritmu v sistemah Weka i RapidMiner en FastRandomForest Arhivovano 24 grudnya 2014 u Wayback Machine Primitki red Breiman Leo 2001 Random Forests Machine Learning 45 1 5 32 doi 10 1023 A 1010933404324 angl Perevireno 7 chervnya 2009 Opis algoritmu na sajti Leo Brejmana Arhivovano 22 chervnya 2008 u Wayback Machine angl Perevireno 7 chervnya 2009 Opis proceduri pobudovi derev yaka zastosovuyetsya v Apache Mahout Arhivovano 13 travnya 2012 u Wayback Machine angl Perevireno 7 chervnya 2009 Download Practical Statistics for Data Scientists 50 Essential Concepts Using R and Python BY Peter Bruce opo iki a sites google com Procitovano 21 travnya 2021 Deng H Runger G Tuv E 2011 Bias of importance measures for multi valued attributes and solutions Proceedings of the 21st International Conference on Artificial Neural Networks ICANN s 293 300 Altmann A Tolosi L Sander O Lengauer T 2010 Permutation importance a corrected feature importance measure Bioinformatics doi 10 1093 bioinformatics btq134 Arhiv originalu za 8 listopada 2016 Procitovano 17 grudnya 2014 Tolosi L Lengauer T 2011 Classification with correlated features unreliability of feature ranking and solutions Bioinformatics doi 10 1093 bioinformatics btr300 Arhiv originalu za 31 serpnya 2015 Procitovano 17 grudnya 2014 Segal Mark R April 14 2004 Machine Learning Benchmarks and Random Forest Regression Center for Bioinformatics amp Molecular Biostatistics Arhiv originalu za 16 zhovtnya 2009 Procitovano 17 grudnya 2014 angl Perevireno 7 chervnya 2009 Literatura red Trevor Hastie Robert Tibshirani Jerome Friedman Chapter 15 Random Forests The Elements of Statistical Learning 2009 S 587 623 Arhivovano z dzherela 28 veresnya 2018 Otrimano z https uk wikipedia org w index php title Random forest amp oldid 37414694