Random forest

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

Розширення алгоритму було запропоновано Лео Брейманом(інші мови)^[1]^[2] і Аделем Катлером(інші мови), «Random Forests» є їхньою торговою маркою. Алгоритм поєднує в собі дві основні ідеї: метод беггінга Бреймана і метод випадкових підпросторів(інші мови), запропонованийТін Кам Хо(інші мови).

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

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

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

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

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

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

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

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

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

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

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

Переваги

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

Недоліки

Алгоритм схильний до перенавчання на деяких завданнях, особливо з великою кількістю шумів.^[8]
Великий розмір отримуваних моделей. Потрібно $O(NK)$ пам'яті для зберігання моделі, де $K$ — число дерев.

Реалізації

Авторська реалізація [Архівовано 25 лютого 2021 у Wayback Machine.] Брейман і Катлер на мові Fortran77
Пакет randomForest [Архівовано 8 березня 2021 у Wayback Machine.] для R — портована версія оригінального авторського коду в R
Пакет party [Архівовано 24 лютого 2021 у Wayback Machine.] для R, містить модифікацію алгоритму
Існують реалізації алгоритму в системах Weka і RapidMiner^[en]
FastRandomForest [Архівовано 24 грудня 2014 у Wayback Machine.]

Примітки

↑ Breiman, Leo (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.{{cite web}}: Обслуговування 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). Permutation importance:a corrected feature importance measure. Bioinformatics. doi:10.1093/bioinformatics/btq134. Архів оригіналу за 8 листопада 2016. Процитовано 17 грудня 2014.
↑ Tolosi L, Lengauer T (2011). Classification with correlated features: unreliability of feature ranking and solutions. Bioinformatics. doi:10.1093/bioinformatics/btr300. Архів оригіналу за 31 серпня 2015. Процитовано 17 грудня 2014.
↑ Segal, Mark R. (April 14 2004), Machine Learning Benchmarks and Random Forest Regression, 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

[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.{{cite web}}: Обслуговування CS1: Сторінки з параметром url-status, але без параметра archive-url (посилання)

[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). Permutation importance:a corrected feature importance measure. Bioinformatics. doi:10.1093/bioinformatics/btq134. Архів оригіналу за 8 листопада 2016. Процитовано 17 грудня 2014.

[7] Tolosi L, Lengauer T (2011). Classification with correlated features: unreliability of feature ranking and solutions. Bioinformatics. doi:10.1093/bioinformatics/btr300. Архів оригіналу за 31 серпня 2015. Процитовано 17 грудня 2014.

[8] Segal, Mark R. (April 14 2004), Machine Learning Benchmarks and Random Forest Regression, Center for Bioinformatics & Molecular Biostatistics, архів оригіналу за 16 жовтня 2009, процитовано 17 грудня 2014(англ.)(Перевірено 7 червня 2009)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]