Random forest

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Random forest (англ. випадковий ліс) — алгоритм машинного навчання, запропонований Лео Брейманом[1][2] і Адель Катлер, що полягає у використанні комітету (ансамблю) вирішальних дерев. Алгоритм поєднує в собі дві основні ідеї: метод беггінга Брейман і метод випадкових підпросторів, запропонований Tin Kam Ho. Алгоритм застосовується для задач класифікації, регресії і кластеризації.

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

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

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

  1. Згенеруємо випадкову підвибірку з повторенням розміром n з навчальної вибірки. (Таким чином, деякі приклади потраплять в неї кілька разів, а приблизно N / 3 прикладів не ввійдуть у неї взагалі)
  2. Побудуємо дерево рішень, яке класифікує приклади даної підвибірки, причому в ході створення чергового вузла дерева будемо вибирати ознаку, на основі якої проводиться розбиття, не з усіх M ознак, а лише з m випадково вибраних. Вибір найкращого з цих m ознак може здійснюватися різними способами. В оригінальному коді Брейман використовується критерій Джині[en], що застосовується також в алгоритмі побудови вирішальних дерев CART. У деяких реалізаціях алгоритму замість нього використовується критерій приросту інформації[en].[3]
  3. Дерево будується до повного вичерпання підвибірки і не піддається процедурі відсікання[en] (на відміну від дерев рішень, побудованих за таким алгоритмам, як CART або C4.5).

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

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

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

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

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

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

Параметри вибірки, які дають більші значення, вважаються більш важливими для тренувального набору. Метод має наступний потенційний недолік — для категоріальних змінних з великою кількістю значень метод схильний вважати такі змінні більш важливими. Часткове переваження значень в цьому випадку може знижувати вплив цього ефекту.[4][5] If the data contain groups of correlated features of similar relevance for the output, then smaller groups are favored over larger groups.[6]

Переваги[ред.ред. код]

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

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

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

Реалізації[ред.ред. код]

Примітки[ред.ред. код]

  1. Breiman, Leo (2001). Random Forests. Machine Learning[en] 45 (1). с. 5–32. doi:10.1023/A:1010933404324. (англ.)(Перевірено 7 червня 2009)
  2. Опис алгоритму на сайті Лео Брейман(англ.)(Перевірено 7 червня 2009)
  3. Опис процедури побудови дерев, яка застосовується в Apache Mahout (англ.) (Перевірено 7 червня 2009)
  4. 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. 
  5. Altmann A, Tolosi L, Sander O, Lengauer T (2010). Permutation importance:a corrected feature importance measure. Bioinformatics. doi:10.1093/bioinformatics/btq134. 
  6. Tolosi L, Lengauer T (2011). Classification with correlated features: unreliability of feature ranking and solutions.. Bioinformatics. doi:10.1093/bioinformatics/btr300. 
  7. Segal, Mark R. (April 14 2004). Machine Learning Benchmarks and Random Forest Regression. Center for Bioinformatics & Molecular Biostatistics. (англ.)(Перевірено 7 червня 2009)

Література[ред.ред. код]

  • Chapter 15. Random Forests // The Elements of Statistical Learning. — 2009.