Random forest

Пусть обучающая выборка состоит из 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 — отсечение ветвей), в отличие от решающих деревьев алгоритмов вроде CART или C4.5.

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

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

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

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

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

Параметры выборки, которые дают бо́льшие значения, считаются более важными для тренировочного набора. Метод имеет потенциальный недостаток — для категориальных переменных с большим количеством значений метод склонен считать такие переменные более важными. Частичное перемешивание значений в этом случае может снижать влияние этого эффекта.[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.