Метод случайного леса

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

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

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

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

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

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

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

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

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

Первый шаг в оценке важности переменной в тренировочном наборе ${\displaystyle {\mathcal {D}}_{n}=\{(X_{i},Y_{i})\}_{i=1}^{n}}$ — тренировка случайного леса на этом наборе. Во время процесса построения модели для каждого элемента тренировочного набора записывается так называемая ошибка неотобранных элементов (англ. out-of-bag error). Затем для каждой сущности такая ошибка усредняется по всему случайному лесу.

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

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

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

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

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

• Большой размер получающихся моделей. Требуется ${\displaystyle O(K)}$ памяти для хранения модели, где ${\displaystyle K}$ — число деревьев.

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

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

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

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

• Hastie, T., Tibshirani R., Friedman J. Chapter 15. Random Forests // The Elements of Statistical Learning: Data Mining, Inference, and Prediction. — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0..

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

Реализации

• Авторская реализация Бреймана и Катлер на языке Fortran 77
• Пакет randomForest для R — портированная версия оригинального авторского кода в R
• Пакет party для R, содержит модификацию алгоритма
• Реализация модификации алгоритма на alglib.sources.ru
• FastRandomForest
• Apache Mahout Архивная копия от 2 апреля 2015 на Wayback Machine.

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. Оформить математические формулы После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.