Random forest

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

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

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

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

Все деревья комитета строятся независимо друг от друга по следующей процедуре:

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

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

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

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

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

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

Для того, чтобы оценить важность j-ого параметра после тренировки, значения j-ого параметра перемешиваются для всех записей тренировочного набора и 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]

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

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

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

  • Алгоритм склонен к переобучению на некоторых задачах, особенно на зашумленных задачах.[8]
  • Большой размер получающихся моделей. Требуется O(NK) памяти для хранения модели, где K — число деревьев.

Реализации[править | править вики-текст]

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

  1. Breiman, Leo (2001). «Random Forests». Machine Learning 45 (1): 5–32. DOI:10.1023/A:1010933404324. (англ.) (Проверено 7 июня 2009)
  2. Описание алгоритма на сайте Лео Бреймана (англ.) (Проверено 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. Caruana R., Niculescu-Mizil A., An Empirical Comparison of Supervised Learning Algorithms Using Different Performance Metrics (англ.) (Проверено 7 июня 2009)
  8. Segal, Mark R. (2004), «Machine Learning Benchmarks and Random Forest Regression», Center for Bioinformatics & Molecular Biostatistics, <http://repositories.cdlib.org/cbmb/bench_rf_regn/>  (англ.) (Проверено 7 июня 2009)

Литература[править | править вики-текст]