Случайный лес - Random forest

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий Очистка данных AutoML Правила ассоциации Обучение с подкреплением Структурированный прогноз Функциональная инженерия Особенности обучения Онлайн обучение Полу-контролируемое обучение Неконтролируемое обучение Учимся ранжировать Введение в грамматику
Обучение с учителем ( классификация  • регрессия ) Деревья решений Ансамбли Упаковка Повышение Случайный лес k -NN Линейная регрессия Наивный байесовский Искусственные нейронные сети Логистическая регрессия Перцептрон Вектор релевантности (RVM) Машина опорных векторов (SVM)
Кластеризация БЕРЕЗА ИЗЛЕЧИВАТЬ Иерархический k -средство Ожидание – максимизация (EM) DBSCAN ОПТИКА Средний сдвиг
Снижение размерности Факторный анализ CCA ICA LDA NMF PCA PGD t-SNE
Структурированный прогноз Графические модели Сеть Байеса Условное случайное поле Скрытый Марков
Обнаружение аномалий k -NN Фактор местного выброса
Искусственная нейронная сеть Автоэнкодер Когнитивные вычисления Глубокое обучение DeepDream Многослойный перцептрон RNN LSTM ГРУ ESN Ограниченная машина Больцмана GAN SOM Сверточная нейронная сеть U-Net Трансформатор Пиковая нейронная сеть Мемтранзистор Электрохимическая RAM (ECRAM)
Обучение с подкреплением Q-обучение SARSA Временная разница (TD)
Теория Компромисс смещения и дисперсии Теория вычислительного обучения Минимизация эмпирического риска Обучение Оккама PAC обучение Статистическое обучение Теория ВК
Площадки для машинного обучения NeurIPS ICML ML JMLR ArXiv: cs.LG
Статьи по Теме Глоссарий искусственного интеллекта Список наборов данных для исследований в области машинного обучения Краткое описание машинного обучения
v т е

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

Первый алгоритм для лесов случайных решений был создан в 1995 году Тином Кам Хо с использованием метода случайных подпространств , который, по формулировке Хо, является способом реализации подхода «стохастической дискриминации» к классификации, предложенного Юджином Клейнбергом.

Расширение алгоритма было разработано Лео Брейманом и Адель Катлер , которые зарегистрировали «Случайные леса» в качестве товарного знака в 2006 году (по состоянию на 2019 год принадлежит Minitab, Inc. ). Расширение сочетает в себе идею Бреймана о « мешковине » и случайный выбор функций, введенных сначала Хо, а затем независимо друг от друга Амитом и Джеманом для построения коллекции деревьев решений с контролируемой дисперсией.

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

История

Общий метод лесов случайных решений был впервые предложен Хо в 1995 году. Хо установил, что леса из деревьев, расщепляющиеся наклонными гиперплоскостями, могут получать точность по мере роста, не страдая от перетренированности, при условии, что леса случайным образом ограничены, чтобы быть чувствительными только к выбранным размеры элемента . Последующая работа в том же направлении пришла к выводу, что другие методы расщепления ведут себя аналогичным образом, если они случайным образом вынуждены быть нечувствительными к размерам некоторых элементов. Обратите внимание, что это наблюдение более сложного классификатора (более крупного леса), почти монотонно становящегося более точным, резко контрастирует с распространенным мнением о том, что сложность классификатора может вырасти только до определенного уровня точности, прежде чем будет нарушена переоснащение. Объяснение устойчивости метода леса к перетренированности можно найти в теории стохастической дискриминации Клейнберга.

На раннее развитие концепции случайных лесов Бреймана повлияли работы Амита и Гемана, которые представили идею поиска по случайному подмножеству доступных решений при разделении узла в контексте выращивания одного дерева . Идея случайного выбора подпространства из Ho также повлияла на дизайн случайных лесов. В этом методе выращивается лес деревьев, и вводятся различия между деревьями путем проецирования обучающих данных в случайно выбранное подпространство перед подгонкой каждого дерева или каждого узла. Наконец, идея рандомизированной оптимизации узлов, где решение в каждом узле выбирается рандомизированной процедурой, а не детерминированной оптимизацией, была впервые введена Диттерихом.

Правильное введение случайных лесов было сделано в статье Лео Бреймана . В этой статье описывается метод построения леса некоррелированных деревьев с использованием процедуры, подобной CART , в сочетании со случайной оптимизацией узлов и сбором пакетов . Кроме того, этот документ сочетает в себе несколько ингредиентов, некоторые из которых были известны ранее, а некоторые - новые, которые составляют основу современной практики случайных лесов, в частности:

1. Использование ошибки вне сумки в качестве оценки ошибки обобщения .
2. Измерение важности переменных путем перестановки.

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

Алгоритм

Предварительные сведения: изучение дерева решений

Деревья решений - популярный метод для различных задач машинного обучения. Обучение на основе дерева «ближе всего к удовлетворению требований для использования в качестве стандартной процедуры интеллектуального анализа данных», - говорят Хасти и др. , «потому что он инвариантен при масштабировании и различных других преобразованиях значений признаков, устойчив к включению нерелевантных функций и дает проверяемые модели. Однако они редко бывают точными».

В частности, деревья, которые выросли очень глубоко, имеют тенденцию усваивать весьма нерегулярные модели: они превышают свои обучающие наборы, т. Е. Имеют низкую систематическую ошибку, но очень высокую дисперсию . Случайные леса - это способ усреднения нескольких глубоких деревьев решений, обученных на разных частях одного и того же обучающего набора, с целью уменьшения дисперсии. Это происходит за счет небольшого увеличения систематической ошибки и некоторой потери интерпретируемости, но в целом значительно повышает производительность окончательной модели.

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

Упаковка

Алгоритм обучения для случайных лесов применяет общую технику агрегирования начальной загрузки или бэггинга к ученикам деревьев. Учитывая обучающий набор X = x ₁ , ..., x _n с ответами Y = y ₁ , ..., y _n , повторная упаковка ( B раз) выбирает случайную выборку с заменой обучающего набора и подгоняет деревья к этим образцы:

Для b = 1, ..., B :

1. Пример, с заменой, n обучающих примеров из X , Y ; назовем их X _b , Y _b .
2. Обучите дерево классификации или регрессии f _b на X _b , Y _b .

После обучения прогнозы для невидимых выборок x ' могут быть сделаны путем усреднения прогнозов всех отдельных деревьев регрессии по x' :

${\ displaystyle {\ hat {f}} = {\ frac {1} {B}} \ sum _ {b = 1} ^ {B} f_ {b} (x ')}$

или путем получения большинства голосов в случае деревьев классификации.

Эта процедура начальной загрузки приводит к лучшей производительности модели, поскольку она уменьшает дисперсию модели без увеличения смещения. Это означает, что, хотя прогнозы одного дерева очень чувствительны к шуму в его обучающем наборе, среднее значение многих деревьев нет, пока деревья не коррелированы. Простое обучение множества деревьев на одном обучающем наборе даст сильно коррелированные деревья (или даже одно и то же дерево много раз, если алгоритм обучения детерминирован); Самостоятельная выборка - это способ декорреляции деревьев путем показа им различных обучающих наборов.

Кроме того, оценка неопределенности прогноза может быть сделана как стандартное отклонение прогнозов по всем отдельным деревьям регрессии по x ' :

${\ displaystyle \ sigma = {\ sqrt {\ frac {\ sum _ {b = 1} ^ {B} (f_ {b} (x ') - {\ hat {f}}) ^ {2}} {B -1}}}.}$

Количество образцов / деревьев, B , является свободным параметром. Обычно используется от нескольких сотен до нескольких тысяч деревьев, в зависимости от размера и характера обучающего набора. Оптимальное количество деревьев B можно найти с помощью перекрестной проверки или наблюдения за ошибкой вне пакета : средней ошибкой прогнозирования для каждой обучающей выборки x _i , используя только деревья, у которых не было x _i в их выборке начальной загрузки. . Ошибка обучения и тестирования имеет тенденцию выравниваться после подгонки некоторого количества деревьев.

От мешков до случайных лесов

Вышеупомянутая процедура описывает исходный алгоритм упаковки деревьев. Случайные леса также включают в себя другой тип схемы упаковки: они используют модифицированный алгоритм обучения дерева, который выбирает при каждом разбиении кандидатов в процессе обучения случайное подмножество функций . Этот процесс иногда называют «сборкой функций». Причина для этого - корреляция деревьев в обычной выборке начальной загрузки: если одна или несколько функций являются очень сильными предикторами для переменной ответа (целевой результат), эти функции будут выбраны во многих B- деревьях, вызывая их чтобы стать коррелированными. Хо провел анализ того, как мешки и случайная проекция подпространства способствуют повышению точности при различных условиях.

Как правило, для задачи классификации с p признаками в каждом разбиении используются признаки √ p (с округлением в меньшую сторону). Для задач регрессии изобретатели рекомендуют p / 3 (с округлением в меньшую сторону) с минимальным размером узла 5 по умолчанию. На практике наилучшие значения этих параметров будут зависеть от проблемы, и их следует рассматривать как параметры настройки.

ExtraTrees

Добавление еще одного шага рандомизации дает чрезвычайно рандомизированные деревья или ExtraTrees. Хотя они похожи на обычные случайные леса в том смысле, что они представляют собой ансамбль отдельных деревьев, есть два основных отличия: во-первых, каждое дерево обучается с использованием всей обучающей выборки (а не выборки начальной загрузки), а во-вторых, нисходящее разбиение в ученик дерева рандомизирован. Вместо вычисления локально оптимальной точки отсечения для каждой рассматриваемой особенности (на основе, например, прироста информации или примеси Джини ) выбирается случайная точка отсечения. Это значение выбирается из равномерного распределения в пределах эмпирического диапазона функции (в обучающем наборе дерева). Затем из всех случайно сгенерированных разбиений выбирается разбиение, дающее наивысший балл, для разбиения узла. Подобно обычным случайным лесам, можно указать количество случайно выбранных объектов, которые будут учитываться в каждом узле. Значения по умолчанию для этого параметра предназначены для классификации и регрессии, где - количество функций в модели. ${\ displaystyle {\ sqrt {p}}}$${\ displaystyle p}$${\ displaystyle p}$

Характеристики

Переменная важность

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

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

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

Характеристики, которые производят большие значения для этой оценки, считаются более важными, чем функции, которые производят маленькие значения. Статистическое определение меры важности переменной было дано и проанализировано Zhu et al.

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

Отношение к ближайшим соседям

Связь между случайными лесами и K -ближайшим соседями алгоритмом ( K -nn) была отмечена, Лин и Jeon в 2002 Оказывается, что оба может быть просмотрена в виде так называемых схемами взвешенных окрестностей . Это модели, построенные на основе обучающего набора, которые делают прогнозы для новых точек x ' , глядя на «окрестность» точки, формализованную весовой функцией W : ${\ Displaystyle \ {(х_ {я}, у_ {я}) \} _ {я = 1} ^ {п}}$${\ displaystyle {\ hat {y}}}$

${\ displaystyle {\ hat {y}} = \ sum _ {i = 1} ^ {n} W (x_ {i}, x ') \, y_ {i}.}$

Здесь - неотрицательный вес i -й обучающей точки относительно новой точки x ' в том же дереве. Для любого конкретного x ' веса баллов должны в сумме равняться единице. Весовые функции представлены следующим образом: ${\ displaystyle W (x_ {i}, x ')}$${\ displaystyle x_ {i}}$

• В k -NN веса равны, если x _i - одна из k точек, ближайших к x ' , и нулю в противном случае.${\ displaystyle W (x_ {i}, x ') = {\ frac {1} {k}}}$
• В дереве, если x _i - одна из k ' точек в том же листе, что и x' , и ноль в противном случае.${\ displaystyle W (x_ {i}, x ') = {\ frac {1} {k'}}}$

Поскольку лес усредняет прогнозы набора m деревьев с индивидуальными весовыми функциями , его прогнозы ${\ displaystyle W_ {j}}$

${\ displaystyle {\ hat {y}} = {\ frac {1} {m}} \ sum _ {j = 1} ^ {m} \ sum _ {i = 1} ^ {n} W_ {j} ( x_ {i}, x ') \, y_ {i} = \ sum _ {i = 1} ^ {n} \ left ({\ frac {1} {m}} \ sum _ {j = 1} ^ { m} W_ {j} (x_ {i}, x ') \ right) \, y_ {i}.}$

Это показывает, что весь лес снова представляет собой взвешенную схему соседства со средними весами отдельных деревьев. Соседи x ' в этой интерпретации - это точки, имеющие общий лист любого дерева . Таким образом, окрестность x ' сложным образом зависит от структуры деревьев и, следовательно, от структуры обучающей выборки. Лин и Чон показывают, что форма окрестностей, используемых случайным лесом, адаптируется к местной важности каждой особенности. ${\ displaystyle x_ {i}}$${\ displaystyle j}$

Неконтролируемое обучение со случайными лесами

Как часть их построения, случайные предикторы леса естественным образом приводят к измерению несходства между наблюдениями. Можно также определить случайную меру несходства лесов между немаркированными данными: идея состоит в том, чтобы построить случайный предиктор леса, который отличает «наблюдаемые» данные от соответствующим образом сгенерированных синтетических данных. Наблюдаемые данные являются исходными немаркированными данными, а синтетические данные взяты из эталонного распределения. Несходство случайного леса может быть привлекательным, поскольку оно очень хорошо обрабатывает смешанные типы переменных, инвариантно к монотонным преобразованиям входных переменных и устойчиво к внешним наблюдениям. Несходство случайного леса легко справляется с большим количеством полунепрерывных переменных из-за присущего ему выбора переменных; например, несходство случайного леса «Addcl 1» взвешивает вклад каждой переменной в зависимости от того, насколько она зависит от других переменных. Несходство случайного леса использовалось во множестве приложений, например, для поиска кластеров пациентов на основе данных маркеров тканей.

Варианты

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

Случайный лес ядра

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

История

Лео Брейман был первым, кто заметил связь между методами случайного леса и ядра . Он указал, что случайные леса, которые выращиваются с использованием случайных векторов iid при построении дерева, эквивалентны ядру, действующему на истинную границу. Лин и Чон установили связь между случайными лесами и адаптивным ближайшим соседом, подразумевая, что случайные леса можно рассматривать как адаптивные оценки ядра. Дэвис и Гахрамани предложили ядро ​​случайного леса и показали, что оно может эмпирически превзойти современные методы ядра. Скорнет сначала определил оценки KeRF и дал явную связь между оценками KeRF и случайным лесом. Он также дал явные выражения для ядер, основанных на центрированном случайном лесу и равномерном случайном лесу, двух упрощенных моделях случайного леса. Он назвал эти два KeRF, центрированный KeRF и Uniform KeRF, и доказал верхние границы их степени согласованности.

Обозначения и определения

Предварительные испытания: Центрированные леса

Центрированный лес - это упрощенная модель исходного случайного леса Бреймана, которая равномерно выбирает атрибут среди всех атрибутов и выполняет разбиение в центре ячейки по заранее выбранному атрибуту. Алгоритм останавливается, когда построено полностью двоичное дерево уровней , где - параметр алгоритма. ${\ displaystyle k}$${\ Displaystyle к \ в \ mathbb {N}}$

Равномерный лес

Единый лес - это еще одна упрощенная модель исходного случайного леса Бреймана, которая равномерно выбирает объект среди всех объектов и выполняет разбиение в точке, равномерно нарисованной на стороне ячейки, вдоль предварительно выбранного объекта.

Из случайного леса в KeRF

Учитывая обучающую выборку из -значных независимых случайных величин , распределенных в качестве независимого прототипа пары , где . Мы стремимся предсказать ответ , связанный со случайной величиной , путем оценки функции регрессии . Лес случайной регрессии - это ансамбль деревьев рандомизированной регрессии. Обозначим прогнозируемое значение в точке по -му дерева, где независимые случайные величины, распределенные в качестве общей случайной величины , независимо от образца . Эта случайная величина может использоваться для описания случайности, вызванной разделением узла и процедуры выборки для построения дерева. Деревья объединяются для получения оценки конечного леса . Для деревьев регрессии у нас есть , где - ячейка, содержащая , спроектированная со случайностью и набором данных , и . ${\ displaystyle {\ mathcal {D}} _ {n} = \ {(\ mathbf {X} _ {i}, Y_ {i}) \} _ {i = 1} ^ {n}}$${\ Displaystyle [0,1] ^ {p} \ раз \ mathbb {R}}$${\ Displaystyle (\ mathbf {X}, Y)}$${\ Displaystyle \ OperatorName {E} [Y ^ {2}] <\ infty}$${\ displaystyle Y}$${\ displaystyle \ mathbf {X}}$${\ Displaystyle м (\ mathbf {x}) = \ OperatorName {E} [Y \ mid \ mathbf {X} = \ mathbf {x}]}$${\ displaystyle M}$${\ displaystyle m_ {n} (\ mathbf {x}, \ mathbf {\ Theta} _ {j})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle j}$${\ Displaystyle \ mathbf {\ Theta} _ {1}, \ ldots, \ mathbf {\ Theta} _ {M}}$${\ Displaystyle \ mathbf {\ Theta}}$${\ displaystyle {\ mathcal {D}} _ {n}}$${\ displaystyle m_ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ frac {1} {M}} \ sum _ {j = 1} ^ {M} m_ {n} (\ mathbf {x}, \ Theta _ {j})}$${\ displaystyle m_ {n} = \ sum _ {i = 1} ^ {n} {\ frac {Y_ {i} \ mathbf {1} _ {\ mathbf {X} _ {i} \ in A_ {n} (\ mathbf {x}, \ Theta _ {j})}} {N_ {n} (\ mathbf {x}, \ Theta _ {j})}}}$${\ Displaystyle A_ {п} (\ mathbf {x}, \ Theta _ {j})}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ Theta _ {j}}$${\ displaystyle {\ mathcal {D}} _ {n}}$${\ displaystyle N_ {n} (\ mathbf {x}, \ Theta _ {j}) = \ sum _ {i = 1} ^ {n} \ mathbf {1} _ {\ mathbf {X} _ {i} \ in A_ {n} (\ mathbf {x}, \ Theta _ {j})}}$

Таким образом , случайный лес оценки удовлетворяют условиям, для всех , . Лес случайной регрессии имеет два уровня усреднения: сначала по выборкам в целевой ячейке дерева, а затем по всем деревьям. Таким образом, вклад наблюдений, которые находятся в ячейках с высокой плотностью точек данных, меньше, чем вклад наблюдений, которые принадлежат менее заселенным ячейкам. Чтобы улучшить методы случайного леса и компенсировать неверную оценку, Скорнет определил KeRF следующим образом: ${\ Displaystyle \ mathbf {x} \ в [0,1] ^ {d}}$${\ displaystyle m_ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ frac {1} {M}} \ sum _ {j = 1} ^ {M} \ left (\ sum _ {i = 1} ^ {n} {\ frac {Y_ {i} \ mathbf {1} _ {\ mathbf {X} _ {i} \ in A_ {n } (\ mathbf {x}, \ Theta _ {j})}} {N_ {n} (\ mathbf {x}, \ Theta _ {j})}} \ right)}$

${\ displaystyle {\ tilde {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ frac {1} {\ sum _ {j = 1} ^ {M} N_ {n} (\ mathbf {x}, \ Theta _ {j})}} \ sum _ {j = 1} ^ {M} \ sum _ {i = 1} ^ {n} Y_ {i} \ mathbf {1} _ {\ mathbf {X} _ {i} \ in A_ {n} (\ mathbf {x}, \ Theta _ {j})},}$

что равно среднему значению числа падений в ячейках, содержащихся в лесу. Если мы определим функцию соединения конечного леса как , то есть пропорцию ячеек, разделяемых между и , то почти наверняка у нас есть , что определяет KeRF. ${\ displaystyle Y_ {i}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle M}$${\ displaystyle K_ {M, n} (\ mathbf {x}, \ mathbf {z}) = {\ frac {1} {M}} \ sum _ {j = 1} ^ {M} \ mathbf {1} _ {\ mathbf {z} \ in A_ {n} (\ mathbf {x}, \ Theta _ {j})}}$${\ displaystyle \ mathbf {x}}$${\ displaystyle \ mathbf {z}}$${\ displaystyle {\ tilde {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M}) = {\ frac {\ sum _ {i = 1} ^ {n} Y_ {i} K_ {M, n} (\ mathbf {x}, \ mathbf {x} _ {i})} {\ sum _ {\ ell = 1} ^ {n} K_ {M, n} (\ mathbf {x}, \ mathbf {x} _ {\ ell})}}}$

Центрированный KeRF

Конструкция центрированного KeRF уровня такая же, как и для центрированного леса, за исключением того, что прогнозы делаются соответствующей функцией ядра или функцией соединения. ${\ displaystyle k}$${\ displaystyle {\ tilde {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M})}$

${\ displaystyle {\ begin {align} K_ {k} ^ {cc} (\ mathbf {x}, \ mathbf {z}) = \ sum _ {k_ {1}, \ ldots, k_ {d}, \ sum _ {j = 1} ^ {d} k_ {j} = k} & {\ frac {k!} {k_ {1}! \ cdots k_ {d}!}} \ left ({\ frac {1} { d}} \ right) ^ {k} \ prod _ {j = 1} ^ {d} \ mathbf {1} _ {\ lceil 2 ^ {k_ {j}} x_ {j} \ rceil = \ lceil 2 ^ {k_ {j}} z_ {j} \ rceil}, \\ & {\ text {для всех}} \ mathbf {x}, \ mathbf {z} \ in [0,1] ^ {d}. \ end {выровнено}}}$

Униформа KeRF

Унифицированный KeRF построен так же, как и равномерный лес, за исключением того, что прогнозы делаются , соответствующей функцией ядра или функцией соединения. ${\ displaystyle {\ tilde {m}} _ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ {M})}$

${\ displaystyle K_ {k} ^ {uf} (\ mathbf {0}, \ mathbf {x}) = \ sum _ {k_ {1}, \ ldots, k_ {d}, \ sum _ {j = 1} ^ {d} k_ {j} = k} {\ frac {k!} {k_ {1}! \ ldots k_ {d}!}} \ left ({\ frac {1} {d}} \ right) ^ {k} \ prod _ {m = 1} ^ {d} \ left (1- | x_ {m} | \ sum _ {j = 0} ^ {k_ {m} -1} {\ frac {(- \ ln | x_ {m} |) ^ {j}} {j!}} \ right) {\ text {для всех}} \ mathbf {x} \ in [0,1] ^ {d}.}$

Характеристики

Связь между KeRF и случайным лесом

Прогнозы, данные KeRF и случайными лесами, близки, если количество точек в каждой ячейке контролируется:

Предположим, что существуют такие последовательности , что почти наверняка ${\ Displaystyle (а_ {п}), (б_ {п})}$

${\ displaystyle a_ {n} \ leq N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n} {\ text {and}} a_ {n} \ leq {\ frac {1} {M }} \ sum _ {m = 1} ^ {M} N_ {n} {\ mathbf {x}, \ Theta _ {m}} \ leq b_ {n}.}$

Тогда почти наверняка,

${\ displaystyle | m_ {M, n} (\ mathbf {x}) - {\ tilde {m}} _ {M, n} (\ mathbf {x}) | \ leq {\ frac {b_ {n} - a_ {n}} {a_ {n}}} {\ tilde {m}} _ {M, n} (\ mathbf {x}).}$

Связь между бесконечным KeRF и бесконечным случайным лесом

Когда количество деревьев стремится к бесконечности, мы получаем бесконечный случайный лес и бесконечный KeRF. Их оценки близки, если количество наблюдений в каждой ячейке ограничено: ${\ displaystyle M}$

Предположим, что существуют такие последовательности , что почти наверняка ${\ displaystyle (\ varepsilon _ {n}), (a_ {n}), (b_ {n})}$

• ${\ Displaystyle \ OperatorName {E} [N_ {N} (\ mathbf {x}, \ Theta)] \ geq 1,}$
• ${\ displaystyle \ operatorname {P} [a_ {n} \ leq N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n} \ mid {\ mathcal {D}} _ {n}] \ geq 1- \ varepsilon _ {n} / 2,}$
• ${\ displaystyle \ operatorname {P} [a_ {n} \ leq \ operatorname {E} _ {\ Theta} [N_ {n} (\ mathbf {x}, \ Theta)] \ leq b_ {n} \ mid { \ mathcal {D}} _ {n}] \ geq 1- \ varepsilon _ {n} / 2,}$

Тогда почти наверняка,

${\ displaystyle | m _ {\ infty, n} (\ mathbf {x}) - {\ tilde {m}} _ {\ infty, n} (\ mathbf {x}) | \ leq {\ frac {b_ {n } -a_ {n}} {a_ {n}}} {\ tilde {m}} _ {\ infty, n} (\ mathbf {x}) + n \ varepsilon _ {n} \ left (\ max _ { 1 \ leq i \ leq n} Y_ {i} \ right).}$

Последовательность результатов

Предположим, что , где - центрированный гауссовский шум, не зависящий от , с конечной дисперсией . Кроме того, равномерно распределяется на и является Липшица . Скорнет доказал верхнюю границу согласованности для центрированного KeRF и однородного KeRF. ${\ Displaystyle Y = м (\ mathbf {X}) + \ varepsilon}$${\ displaystyle \ varepsilon}$${\ displaystyle \ mathbf {X}}$${\ Displaystyle \ sigma ^ {2} <\ infty}$${\ displaystyle \ mathbf {X}}$${\ displaystyle [0,1] ^ {d}}$${\ displaystyle m}$

Согласованность центрированного KeRF

Предоставление и существует постоянная такая , что для всех , . ${\ Displaystyle к \ rightarrow \ infty}$${\ Displaystyle п / 2 ^ {к} \ rightarrow \ infty}$${\ displaystyle C_ {1}> 0}$${\ displaystyle n}$${\ displaystyle \ mathbb {E} [{\ тильда {m}} _ {n} ^ {cc} (\ mathbf {X}) -m (\ mathbf {X})] ^ {2} \ leq C_ {1 } n ^ {- 1 / (3 + d \ log 2)} (\ log n) ^ {2}}$

Консистенция единого KeRF

При условии и существует такая константа , что ,. ${\ Displaystyle к \ rightarrow \ infty}$${\ Displaystyle п / 2 ^ {к} \ rightarrow \ infty}$${\ displaystyle C> 0}$${\ displaystyle \ mathbb {E} [{\ тильда {m}} _ {n} ^ {uf} (\ mathbf {X}) -m (\ mathbf {X})] ^ {2} \ leq Cn ^ { -2 / (6 + 3d \ log 2)} (\ log n) ^ {2}}$

Недостатки

Хотя случайные леса часто достигают более высокой точности, чем одно дерево решений, они приносят в жертву внутреннюю интерпретируемость, присущую деревьям решений. Деревья решений относятся к довольно небольшому семейству моделей машинного обучения, которые легко интерпретировать вместе с линейными моделями, моделями на основе правил и моделями на основе внимания . Эта интерпретируемость - одно из наиболее желаемых качеств деревьев решений. Это позволяет разработчикам подтвердить, что модель получила реалистичную информацию из данных, и позволяет конечным пользователям доверять решениям, принимаемым моделью. Например, проследить путь, по которому дерево решений принимает свое решение, довольно тривиально, но следовать путем десятков или сотен деревьев намного сложнее. Для достижения производительности и интерпретируемости некоторые методы сжатия моделей позволяют преобразовать случайный лес в минимальное «возрожденное» дерево решений, которое точно воспроизводит ту же функцию принятия решений. Если установлено, что прогнозные атрибуты линейно коррелируют с целевой переменной, использование случайного леса может не повысить точность базового обучающегося. Кроме того, в задачах с несколькими категориальными переменными случайный лес может не повысить точность базового учащегося.

Смотрите также

• Повышение
• Обучение дереву решений
• Ансамблевое обучение
• Повышение градиента
• Непараметрическая статистика
• Рандомизированный алгоритм

использованная литература

дальнейшее чтение

У Схолии есть тематический профиль Случайный лес .

внешние ссылки

• Описание классификатора случайных лесов (сайт Лео Бреймана)
• Лиау, Энди и Винер, Мэтью "Классификация и регрессия с помощью randomForest" R News (2002) Vol. 2/3 п. 18 (Обсуждение использования пакета random forest для R )