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

Алгоритм обучения классификатораПравить

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

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

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

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

Оптимальное число деревьев подбирается таким образом, чтобы минимизировать ошибку классификатора на тестовой выборке. В случае её отсутствия, минимизируется оценка ошибки на не вошедших в набор образцах.

Оценка важности переменныхПравить

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

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

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

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

ДостоинстваПравить

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

НедостаткиПравить

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

Использование в научных работахПравить

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

ПримечанияПравить

  1. Breiman, Leo. Random Forests (англ.) // Machine Learning (англ.) : journal. — 2001. — Vol. 45, no. 1. — P. 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. Permutation importance:a corrected feature importance measure (англ.) // Bioinformatics : journal. — 2010. — doi:10.1093/bioinformatics/btq134.
  6. Tolosi L., Lengauer T. Classification with correlated features: unreliability of feature ranking and solutions. (англ.) // Bioinformatics : journal. — 2011. — doi:10.1093/bioinformatics/btr300.
  7. Węcel K., Lewoniewski W. Modelling the Quality of Attributes in Wikipedia Infoboxes (англ.) // Lecture Notes in Business Information Processing : journal. — 2015. — 2 December (vol. 228). — P. 308—320. — doi:10.1007/978-3-319-26762-3_27.
  8. Lewoniewski W., Węcel K., Abramowicz W. Quality and Importance of Wikipedia Articles in Different Languages (англ.) // Information and Software Technologies. ICIST 2016. Communications in Computer and Information Science : journal. — 2016. — 22 September (vol. 639). — P. 613—624. — doi:10.1007/978-3-319-46254-7_50.
  9. Warncke-Wang M., Cosley D., Riedl J. Tell me more: An actionable quality model for wikipedia (англ.) // WikiSym '13 Proceedings of the 9th International Symposium on Open Collaboration : journal. — 2013. — doi:10.1145/2491055.2491063.

ЛитератураПравить

СсылкиПравить

Реализации