Random forest (англ. випадковий ліс) — ансамблевий метод машинного навчання для класифікації, регресії та інших завдань, який працює за допомогою побудови численних дерев прийняття рішень під час тренування моделі й продукує моду для класів (класифікацій) або усереднений прогноз (регресія) побудованих дерев. Недоліком є схильність до перенавчання.
Розширення алгоритму було запропоновано і Аделем Катлером, «Random Forests» є їхньою торговою маркою. Алгоритм поєднує в собі дві основні ідеї: метод (беггінга) Бреймана і , запропонований Tin Kam Ho.
Алгоритм навчання класифікатора
Нехай навчальна вибірка складається з N прикладів, розмірність простору ознак дорівнює M, і заданий параметр m (в задачах класифікації зазвичай ).
Усі дерева комітету будуються незалежно один від одного за такою процедурою:
- Згенеруємо випадкову підвибірку з повторенням розміром n з навчальної вибірки. (Таким чином, деякі приклади потраплять в неї кілька разів, а приблизно N/3 прикладів не ввійдуть у неї взагалі).
- Далі випадково обиремо m предикторів (ознак) із М.
- Побудуємо дерево рішень, яке класифікує приклади даної підвибірки, причому в ході створення чергового вузла дерева будемо вибирати ознаку, на основі якої проводиться розбиття, не з усіх M ознак, а лише з m випадково вибраних. Вибір найкращого з цих m ознак може здійснюватися різними способами. В оригінальному коді Брейман використовується , що застосовується також в алгоритмі побудови вирішальних дерев . У деяких реалізаціях алгоритму замість нього використовується [en].
- Розділимо ознаку Х на два класи, Xі Sі та Xі < Sі.
- Виміряємо гомогенність у двох нових класах за допомогую критерію Джині.
- Оберемо таке значення «спліт-поінту» Sі ознаки Х, для якого досягнуто максимальної гомогенності класу.
- Дерево будується до повного вичерпання підвибірки і не піддається процедурі [en] (на відміну від дерев рішень, побудованих за таким алгоритмам, як або (C4.5)).
- Повертаємося до пункту 1. генеруємо нову вибірку і повторюємо пункти 2. — 4. будуючи наступне дерево. Чим більше дерев побудовано, тим меншою буде помилка класифікатора на тестовій вибірці.
Класифікація об'єктів проводиться шляхом голосування: кожне дерево комітету відносить об'єкт, який класифікується до одного з класів, і перемагає клас, за який проголосувало найбільше число дерев.
Оптимальне число дерев підбирається таким чином, щоб мінімізувати помилку класифікатора на тестовій вибірці. У разі її відсутності, мінімізується оцінка помилки out-of-bag: частка прикладів навчальної вибірки, неправильно класифікованих комітетом, якщо не враховувати голоси дерев на прикладах, що входять в їх власну навчальну підвибірку.
Оцінка важливості змінних
Випадкові ліси, отримані в результаті застосування технік, описаних раніше, можуть бути природним чином використані для оцінки важливості змінних в задачах регресії та класифікації. Наступний спосіб такої оцінки був описаний Breiman.
Перший крок в оцінці важливості змінної в тренувальному наборі — тренування випадкового лісу на цьому наборі. Під час процесу побудови моделі для кожного елемента тренувального набору вважається так звана — помилка. Потім для кожної сутності така помилка опосередковується по всьому випадковому лісі.
Для того, щоб оцінити важливість -ого параметра після тренування, значення -ого параметра перемішуються для всіх записів тренувального набору та — помилка рахується знову. Важливість параметра оцінюється шляхом усереднення по всіх деревах різниці показників — помилок до і після перемішування значень. При цьому значення таких помилок нормалізуються на стандартне відхилення.
Параметри вибірки, які дають більші значення, вважаються більш важливими для тренувального набору. Метод має наступний потенційний недолік — для категоріальних змінних з великою кількістю значень метод схильний вважати такі змінні більш важливими. Часткове переваження значень в цьому випадку може знижувати вплив цього ефекту. Якщо дані містять групи корельованих ознак, що мають подібне значення для результату, то більш дрібні групи мають переваги над більшими групами.
Переваги
- Здатність ефективно обробляти дані з великим числом ознак і класів.
- Нечутливість до масштабування (і взагалі до будь-яких монотонних перетворень) значень ознак.
- Однаково добре обробляються як безперервні, так і дискретні ознаки. Існують методи побудови дерев за даними з пропущеними значеннями ознак.
- Існують методи оцінювання значущості окремих ознак в моделі.
- Внутрішня оцінка здатності моделі до узагальнення (тест out-of-bag).
- Здатність працювати паралельно в багато потоків.
Недоліки
- Алгоритм схильний до перенавчання на деяких завданнях, особливо з великою кількістю шумів.
- Великий розмір отримуваних моделей. Потрібно пам'яті для зберігання моделі, де — число дерев.
Реалізації
- Авторська реалізація [ 25 лютого 2021 у Wayback Machine.] Брейман і Катлер на мові Fortran77
- Пакет randomForest [ 8 березня 2021 у Wayback Machine.] для R — портована версія оригінального авторського коду в R
- Пакет party [ 24 лютого 2021 у Wayback Machine.] для R, містить модифікацію алгоритму
- Існують реалізації алгоритму в системах (Weka) і [en]
- FastRandomForest [ 24 грудня 2014 у Wayback Machine.]
Примітки
- (2001). Random Forests. Machine Learning. 45 (1): 5—32. doi:10.1023/A:1010933404324.(англ.)(Перевірено 7 червня 2009)
- Опис алгоритму на сайті Лео Бреймана [ 22 червня 2008 у Wayback Machine.](англ.)(Перевірено 7 червня 2009)
- Опис процедури побудови дерев, яка застосовується в Apache Mahout [ 13 травня 2012 у Wayback Machine.] (англ.) (Перевірено 7 червня 2009)
- [~Download~] Practical Statistics for Data Scientists: 50+ Essential Concepts Using R and Python BY : Peter Bruce - opo iki a. sites.google.com. Процитовано 21 травня 2021.
{{}}
: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url () - 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.
- Altmann A, Tolosi L, Sander O, Lengauer T (2010). . Bioinformatics. doi:10.1093/bioinformatics/btq134. Архів оригіналу за 8 листопада 2016. Процитовано 17 грудня 2014.
- Tolosi L, Lengauer T (2011). . Bioinformatics. doi:10.1093/bioinformatics/btr300. Архів оригіналу за 31 серпня 2015. Процитовано 17 грудня 2014.
- 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, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет