Метод случайного леса ( англ. 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}$ , где e {\displaystyle e} — основание натурального логарифма ) образцов оказываются не вошедшими в набор или неотобранными ( англ. out-of-bag).
2. Построим решающее дерево , классифицирующее образцы данной подвыборки, причём в ходе создания очередного узла дерева будем выбирать набор признаков, на основе которых производится разбиение (не из всех M признаков, а лишь из m случайно выбранных). Выбор наилучшего из этих m признаков может осуществляться различными способами. В оригинальном методе Бреймана используется , применяющийся также в алгоритме построения решающих деревьев CART . В некоторых реализациях алгоритма вместо него используется .
3. Дерево строится до полного исчерпания подвыборки и не подвергается процедуре прунинга ( англ. — отсечение ветвей), в отличие от решающих деревьев алгоритмов вроде CART или C4.5 .

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

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

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

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

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

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

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

Достоинства

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

Недостатки

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

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

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

Примечания

Литература

• Hastie, T., Tibshirani R., Friedman J. Chapter 15. Random Forests // . — 2nd ed. — Springer-Verlag, 2009. — 746 p. — ISBN 978-0-387-84857-0 . .

Ссылки

Реализации

• Бреймана и Катлер на языке Fortran 77
• Пакет для R — портированная версия оригинального авторского кода в R
• Пакет для R , содержит модификацию алгоритма
• от 2 апреля 2015 на Wayback Machine .