WikiSort.ru - Не сортированное

Машинное обучение и data mining

Задачи Задача классификации Обучение без учителя Обучение с частичным привлечением учителя Регрессионный анализ AutoML Ассоциативные правила Выделение признаков Обучение признакам Обучение ранжированию Грамматический вывод Онлайновое обучение

Обучение с учителем Метод k-ближайших соседей Наивный байесовский классификатор Дерево решений Метод опорных векторов Линейная регрессия Логистическая регрессия Перцептрон Ансамбли моделей (Бэггинг, Бустинг, Random forest) Метод релевантных векторов

Кластерный анализ Метод k-средних Метод нечёткой кластеризации Иерархическая кластеризация EM-алгоритм BIRCH CURE DBSCAN OPTICS Mean-shift

Снижение размерности Факторный анализ Метод главных компонент CCA ICA LDA Неотрицательное матричное разложение t-SNE

Структурное прогнозирование Графовая вероятностная модель (Байесовская сеть, Скрытая марковская модель, CRF)

Выявление аномалий Метод k-ближайших соседей Локальный уровень выброса

Графовые вероятностные модели Байесовская сеть Марковская сеть Скрытая марковская модель

Искусственные нейронные сети Ограниченная машина Больцмана Самоорганизующаяся карта Функция активации (Сигмоида, Softmax, Радиально-базисная функция) Метод обратного распространения ошибки Глубокое обучение Многослойный перцептрон Рекуррентная нейронная сеть (Долгая краткосрочная память, Управляемый рекуррентный блок) Свёрточная нейронная сеть (U-Net) Автокодировщик

Обучение с подкреплением Марковский процесс Уравнение Беллмана Жадный алгоритм Q-learning SARSA Temporal difference (TD)

Теория Теория Вапника — Червоненкиса Дилемма смещения–дисперсии Теория вычислительного обучения Минимизация эмпирического риска Оккамово обучение PAC learning Статистическая теория обучения

Журналы и конференции NIPS ICML ML JMLR ArXiv:cs.LG

Глоссарий Глоссарий по машинному обучению

Статьи по теме List of datasets for machine-learning research Outline of machine learning

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

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

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

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

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

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

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

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

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

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

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

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

Достоинства

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

Недостатки

• Большой размер получающихся моделей. Требуется ${\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.