Random forest

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

Алгоритм обучения классификатора[править | править код]

Пусть обучающая выборка состоит из N образцов, размерность пространства признаков равна M, и задан параметр m (в задачах классификации обычно ) как неполное количество признаков для обучения.

Наиболее распространённый способ построения деревьев комитета следующий (называется бэггинг (англ. bagging, сокращение от англ. bootstrap aggregation)):

  1. Сгенерируем случайную подвыборку с повторениями размером N из обучающей выборки. (Таким образом, некоторые образцы попадут в неё два или более раза, а в среднем N*, а примерно N/e образцов не войдут в неё вообще). Те образцы, которые не попали в выборку, называются out-of-bag (неотобранные).
  2. Построим решающее дерево, классифицирующее образцы данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать набор признаков, на основе которых производится разбиение (не из всех M признаков, а лишь из m случайно выбранных). Выбор наилучшего из этих m признаков может осуществляться различными способами. В оригинальном коде Бреймана используется критерий Джини, применяющийся также в алгоритме построения решающих деревьев CART. В некоторых реализациях алгоритма вместо него используется критерий прироста информации.[3]
  3. Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга (англ. pruning — отсечение ветвей) (в отличие от решающих деревьев, построенных по таким алгоритмам, как CART или C4.5).

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

Оптимальное число деревьев подбирается таким образом, чтобы минимизировать ошибку классификатора на тестовой выборке. В случае её отсутствия, минимизируется оценка ошибки out-of-bag: тех образцов, которые не попали в обучающую подвыборку за счёт повторений (их примерно N/e ).

Оценка важности переменных[править | править код]

Случайные леса, получаемые в результате применения техник, описанных ранее, могут быть естественным образом использованы для оценки важности переменных в задачах регрессии и классификации. Следующий способ такой оценки был описан Breiman.

Первый шаг в оценке важности переменной в тренировочном наборе — тренировка случайного леса на этом наборе. Во время процесса построения модели для каждого элемента тренировочного набора называемая out-of-bag-ошибка (ошибка на неотобранных образцах). Затем для каждой сущности такая ошибка усредняется по всему случайному лесу.

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

Параметры выборки, которые дают бо́льшие значения, считаются более важными для тренировочного набора. Метод имеет следующий потенциальный недостаток — для категориальных переменных с большим количеством значений метод склонен считать такие переменные более важными. Частичное перемешивание значений в этом случае может снижать влияние этого эффекта.[4][5] Из групп коррелирующих параметров, важность которых оказывается одинаковой, выбираются меньшие по численности группы.[6]

Достоинства[править | править код]

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

Недостатки[править | править код]

  • Большой размер получающихся моделей. Требуется памяти для хранения модели, где  — число деревьев.

Использование в научных работах[править | править код]

Алгоритм часто используется в научных работах из-за его преимуществ. Например, его можно использовать для оценки качества статей Википедии[7][8][9].

Примечания[править | править код]

  1. Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324. (англ.) (Проверено 7 июня 2009)
  2. Описание алгоритма на сайте Лео Бреймана Архивировано 22 июня 2008 года. (англ.) (Проверено 7 июня 2009)
  3. Описание процедуры построения деревьев, применяющейся в Apache Mahout (англ.) (Проверено 7 июня 2009)
  4. Deng,H. (2011). "Bias of importance measures for multi-valued attributes and solutions" in 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. Węcel K., Lewoniewski W. (2015-12-02). «Modelling the Quality of Attributes in Wikipedia Infoboxes». Lecture Notes in Business Information Processing 228: 308-320. DOI:10.1007/978-3-319-26762-3_27.
  8. Lewoniewski W., Węcel K., Abramowicz W. (2016-09-22). «Quality and Importance of Wikipedia Articles in Different Languages». Information and Software Technologies. ICIST 2016. Communications in Computer and Information Science 639: 613-624. DOI:10.1007/978-3-319-46254-7_50.
  9. Warncke-Wang M., Cosley D., last3=Riedl J. (2013). «Tell me more: An actionable quality model for wikipedia». WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration. DOI:10.1145/2491055.2491063.

Литература[править | править код]

Ссылки[править | править код]

Реализации