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

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

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

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

Литература

• 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.