Перегляд вихідного коду сторінки Random forest

{{Машинне навчання|Кероване навчання}}
'''Random forest''' ({{lang-en|випадковий ліс}})&nbsp;— [[Ансамблеве навчання|ансамблевий метод]] машинного навчання для [[Класифікація (машинне навчання)|класифікації]], [[Регресійний аналіз|регресії]] та інших завдань, який працює за допомогою побудови численних [[Дерево прийняття рішень|дерев прийняття рішень]] під час тренування моделі й продукує [[Мода (статистика)|моду]] для класів (класифікацій) або усереднений прогноз (регресія) побудованих дерев. Недоліком є схильність до [[перенавчання]].

Розширення алгоритму було запропоновано {{Li|Лео Брейман|Q=Q931461|text=Лео Брейманом}}<ref>{{cite journal
 |first=Leo |last=Breiman |authorlink=Лео Брейман
 |title=Random Forests 
 |journal=[[Machine Learning (журнал)|Machine Learning]]
 |year=2001 |volume=45 |issue=1 |pages=5–32
 |doi=10.1023/A:1010933404324
}}{{ref-en}}{{перевірено|07|06|2009}}</ref><ref>[http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm Опис алгоритму на сайті Лео Бреймана] {{Webarchive|url=https://web.archive.org/web/20080622230434/http://stat-www.berkeley.edu/users/breiman/RandomForests/cc_home.htm |date=22 червня 2008 }}{{ref-en}}{{перевірено|07|06|2009}}</ref> і {{Li|Адель Катлер|Q=Q66725870|text=Аделем Катлером}}, «Random Forests» є їхньою [[Торгова марка|торговою маркою]]. Алгоритм поєднує в собі дві основні ідеї: метод [[Bootstrap aggregating|беггінга]] Бреймана і {{Li|метод випадкових підпросторів|Q=Q7291993}}, запропонований{{Li|Тін Кам Хо|Q=Q48972688}}.

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

Усі дерева комітету будуються незалежно один від одного за такою процедурою:
# Згенеруємо випадкову підвибірку '''з повторенням''' розміром ''n'' з навчальної вибірки. (Таким чином, деякі приклади потраплять в неї кілька разів, а приблизно ''N''/3 прикладів не ввійдуть у неї взагалі).
# Далі випадково обиремо ''m'' предикторів (ознак) із ''М.''
# Побудуємо [[Дерево прийняття рішень|дерево рішень]], яке класифікує приклади даної підвибірки, причому в ході створення чергового вузла дерева будемо вибирати ознаку, на основі якої проводиться розбиття, не з усіх ''M'' ознак, а лише з ''m'' випадково вибраних. Вибір найкращого з цих ''m'' ознак може здійснюватися різними способами. В оригінальному коді Брейман використовується [[Дерева рішень у машинному навчанні#критерій Джині|критерій Джині]], що застосовується також в алгоритмі побудови вирішальних дерев [[CART(алгоритм)|CART]]. У деяких реалізаціях алгоритму замість нього використовується {{нп|Information gain in decision trees|критерій приросту інформації|en|Information gain in decision trees}}.<ref>[http://cwiki.apache.org/MAHOUT/random-forests.html Опис процедури побудови дерев, яка застосовується в Apache Mahout] {{Webarchive|url=https://web.archive.org/web/20120513133842/https://cwiki.apache.org/MAHOUT/random-forests.html |date=13 травня 2012 }} {{ref-en}} {{перевірено|07|06|2009}}</ref>
# Розділимо ознаку Х на два класи, ''X<sub>і</sub>'' <math>\geq</math> ''S<sub>і</sub>'' та ''X<sub>і</sub>'' < ''S<sub>і</sub>''.
# Виміряємо гомогенність у двох нових класах за допомогую критерію Джині.
# Оберемо таке значення «спліт-поінту» ''S<sub>і</sub>'' ознаки ''Х'', для якого досягнуто максимальної гомогенності класу.
# Дерево будується до повного вичерпання підвибірки і не піддається процедурі {{нп|відсікання (дерева рішень)|відсікання|en|Pruning (decision trees)}} (на відміну від дерев рішень, побудованих за таким алгоритмам, як [[CART(алгоритм)|CART]] або [[C4.5 (алгоритм)|C4.5]]).
# Повертаємося до пункту 1. генеруємо нову вибірку і повторюємо пункти 2.&nbsp;— 4. будуючи наступне дерево. Чим більше дерев побудовано, тим меншою буде помилка класифікатора на тестовій вибірці.<ref>{{Cite web|title=[~Download~] Practical Statistics for Data Scientists: 50+ Essential Concepts Using R and Python BY : Peter Bruce - opo iki a|url=https://sites.google.com/a/cintaiakumas.web.app/opo-iki-a/-download-practical-statistics-for-data-scientists-50-essential-concepts-using-r-and-python-by-peter-bruce|website=sites.google.com|accessdate=2021-05-21|url-status=dead}}</ref>

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

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

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

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

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

Параметри вибірки, які дають більші значення, вважаються більш важливими для тренувального набору. Метод має наступний потенційний недолік&nbsp;— для категоріальних змінних з великою кількістю значень метод схильний вважати такі змінні більш важливими. Часткове переваження значень в цьому випадку може знижувати вплив цього ефекту.<ref>{{cite conference
|author=Deng,H.|author2=Runger, G. |author3=Tuv, E.
 |title=Bias of importance measures for multi-valued attributes and solutions
|conference=Proceedings of the 21st International Conference on Artificial Neural Networks (ICANN)
|year=2011|pages=293&ndash;300
}}</ref><ref>{{cite journal |author=Altmann A, Tolosi L, Sander O, Lengauer T |title=Permutation importance:a corrected feature importance measure |journal=Bioinformatics |year=2010 |doi=10.1093/bioinformatics/btq134 |url=http://bioinformatics.oxfordjournals.org/content/early/2010/04/12/bioinformatics.btq134.abstract |accessdate=17 грудня 2014 |archive-date=8 листопада 2016 |archive-url=https://web.archive.org/web/20161108094546/http://bioinformatics.oxfordjournals.org/content/early/2010/04/12/bioinformatics.btq134.abstract }}</ref> Якщо дані містять групи корельованих ознак, що мають подібне значення для результату, то більш дрібні групи мають переваги над більшими групами.<ref>{{cite journal |author=Tolosi L, Lengauer T |title=Classification with correlated features: unreliability of feature ranking and solutions. |journal=Bioinformatics |year=2011 |doi=10.1093/bioinformatics/btr300 |url=http://bioinformatics.oxfordjournals.org/content/27/14/1986.abstract |accessdate=17 грудня 2014 |archive-date=31 серпня 2015 |archive-url=https://web.archive.org/web/20150831012131/http://bioinformatics.oxfordjournals.org/content/27/14/1986.abstract }}</ref>

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

== Недоліки ==
* Алгоритм схильний до [[перенавчання]] на деяких завданнях, особливо з великою кількістю шумів.<ref>{{citation
 |first=Mark R.
 |last=Segal
 |title=Machine Learning Benchmarks and Random Forest Regression
 |month=April 14
 |year=2004
 |publisher=Center for Bioinformatics & Molecular Biostatistics
 |url=http://repositories.cdlib.org/cbmb/bench_rf_regn/
 |accessdate=17 грудня 2014
 |archive-date=16 жовтня 2009
 |archive-url=https://web.archive.org/web/20091016043837/http://repositories.cdlib.org/cbmb/bench_rf_regn/
 }}{{ref-en}}{{проверено|07|06|2009}}</ref>
* Великий розмір отримуваних моделей. Потрібно <math>O(NK)</math> пам'яті для зберігання моделі, де <math>K</math>&nbsp;— число дерев.

== Реалізації ==
* [http://www.stat.berkeley.edu/~breiman/RandomForests/cc_software.htm Авторська реалізація] {{Webarchive|url=https://web.archive.org/web/20210225115642/https://www.stat.berkeley.edu/~breiman/RandomForests/cc_software.htm |date=25 лютого 2021 }} Брейман і Катлер на мові [[Fortran|Fortran77]]
* Пакет [http://cran.r-project.org/web/packages/randomForest/index.html randomForest] {{Webarchive|url=https://web.archive.org/web/20210308051225/https://cran.r-project.org/web/packages/randomForest/index.html |date=8 березня 2021 }} для [[R (мова програмування)|R]]&nbsp;— портована версія оригінального авторського коду в R
* Пакет [http://cran.r-project.org/web/packages/party/index.html party] {{Webarchive|url=https://web.archive.org/web/20210224192518/https://cran.r-project.org/web/packages/party/index.html |date=24 лютого 2021 }} для [[R (мова програмування)| R]], містить модифікацію алгоритму
* Існують реалізації алгоритму в системах [[Weka]] і {{нп|RapidMiner|RapidMiner|en|RapidMiner}}
* [http://code.google.com/p/fast-random-forest/ FastRandomForest] {{Webarchive|url=https://web.archive.org/web/20141224125739/https://code.google.com/p/fast-random-forest/ |date=24 грудня 2014 }}

== Примітки ==
{{примітки}}

== Література ==
* {{Книга|назва=The Elements of Statistical Learning|автор=Trevor Hastie, Robert Tibshirani, Jerome Friedman|рік=2009|частина=Chapter 15. Random Forests|посилання=https://web.stanford.edu/~hastie/Papers/ESLII.pdf|сторінки=587-623|archivedate=28 вересня 2018|archiveurl=https://web.archive.org/web/20180928060423/https://web.stanford.edu/~hastie/Papers/ESLII.pdf}}

[[Категорія:Дерева рішень]]
[[Категорія:Алгоритми класифікації]]
[[Категорія:Ансамблеве навчання]]