Случайный лес

Часть серии по
Машинное обучение и интеллектуальный анализ данных
Проблемы Классификация Кластеризация Регресс Обнаружение аномалий 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 т е

Случайные леса или леса случайных решений - это метод обучения ансамбля для классификации , регрессии и других задач, которые работают путем построения множества деревьев решений во время обучения и вывода класса, который является режимом классов (классификация) или средним / средним прогнозом ( регрессия) отдельных деревьев. ^{[1] [2]} Случайные леса решений корректируют привычку деревьев решений переобучаться их обучающему набору . ^{[3] : 587–588} Случайные леса обычно превосходят деревья решений., но их точность ниже, чем у деревьев с градиентным усилением. Однако характеристики данных могут повлиять на их производительность. ^{[4] [5]}

Первый алгоритм случайных решения лесов был создан Тины Ок Хо ^[1] , используя метод случайной выборки подпространства , ^[2] , который, в формулировке Х, является способом реализации «стохастических дискриминации» подхода к классификации , предложенный Евгений Клейнберг. ^{[6] [7] [8]}

Расширение алгоритма была разработана Лео Breiman ^[9] и Адель Катлер , ^[10] , который зарегистрировал ^[11] «Случайные леса» в качестве товарного знака (по состоянию на 2019 г. ^{[Обновить]}, принадлежащей Minitab, Inc. ). ^[12] Расширение сочетает в себе идею Бреймана о « мешковине » и случайный выбор функций, впервые представленных Хо ^[1], а затем независимо друг от друга Амитом и Джеманом ^[13], с целью построения коллекции деревьев решений с контролируемой дисперсией.

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

История [ править ]

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

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

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

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

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

Алгоритм [ править ]

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

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

В частности, деревья, которые выросли очень глубоко, имеют тенденцию усваивать весьма нерегулярные модели: они превышают свои обучающие наборы, то есть имеют низкую систематическую ошибку, но очень высокую дисперсию . Случайные леса - это способ усреднения нескольких глубоких деревьев решений, обученных на разных частях одного и того же обучающего набора, с целью уменьшения дисперсии. ^{[3] : 587–588} Это происходит за счет небольшого увеличения систематической ошибки и некоторой потери интерпретируемости, но в целом значительно повышает производительность окончательной модели.

Леса подобны объединению усилий алгоритмов дерева решений. Совместная работа множества деревьев, повышающая производительность одного случайного дерева. Хотя это и не совсем похоже, леса дают эффект перекрестной проверки в 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 ' :

Не удалось выполнить синтаксический анализ (MathML с запасным вариантом SVG или PNG (рекомендуется для современных браузеров и инструментов специальных возможностей): недопустимый ответ («Расширение Math не может подключиться к Restbase.») От сервера «/ mathoid / local / v1 /» :): {\ displaystyle \ sigma = \ sqrt {\ frac {\ sum_ {b = 1} ^ B (f_b (x ') - \ hat {f}) ^ 2} {B-1}}.}

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

От мешков до случайных лесов [ править ]

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

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

ExtraTrees [ править ]

Добавление еще одного шага рандомизации дает чрезвычайно рандомизированные деревья или ExtraTrees. Хотя они похожи на обычные случайные леса в том смысле, что они представляют собой ансамбль отдельных деревьев, есть два основных отличия: во-первых, каждое дерево обучается с использованием всей обучающей выборки (а не выборки начальной загрузки), а во-вторых, нисходящее разбиение в ученик дерева рандомизирован. Вместо того, чтобы вычислять локально оптимальную точку отсечения для каждой рассматриваемой функции (на основе, например, получения информации или примеси Джини ), случайныйточка отсечки выбрана. Это значение выбирается из равномерного распределения в пределах эмпирического диапазона функции (в обучающем наборе дерева). Затем из всех случайно сгенерированных разбиений выбирается разбиение, дающее наивысший балл, для разбиения узла. Подобно обычным случайным лесам, можно указать количество случайно выбранных объектов, которые будут учитываться в каждом узле. Значения по умолчанию для этого параметра предназначены для классификации и для регрессии, где не удалось выполнить синтаксический анализ (MathML с резервным SVG или PNG (рекомендуется для современных браузеров и инструментов специальных возможностей): недопустимый ответ («Расширение Math не может подключиться к Restbase.») С сервера »/ mathoid / local / v1 / ":): p - количество функций в модели. ^[17]${\ displaystyle {\ sqrt {p}}}$${\ displaystyle p}$

Свойства [ править ]

Переменная важность [ править ]

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

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

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

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

Этот метод определения важности переменных имеет ряд недостатков. Для данных, включающих категориальные переменные с разным количеством уровней, случайные леса смещены в пользу атрибутов с большим количеством уровней. Для решения проблемы можно использовать такие методы, как частичные перестановки ^{[19] [20] [4]} и выращивание несмещенных деревьев ^{[21] [22]} . Если данные содержат группы коррелированных характеристик, имеющих одинаковую значимость для выходных данных, то группы меньшего размера предпочтительнее, чем группы большего размера. ^[23]

Отношения с ближайшими соседями [ править ]

Связь между случайными лесами и K -ближайших соседей алгоритма ( K -nn) было отмечено, Лин и Jeon в 2002 г. ^[24] Оказалось, что оба могут быть просмотрены в виде так называемых схем взвешенных окрестностей . Это модели, построенные на основе обучающего набора, которые делают прогнозы для новых точек x ' , глядя на «окрестность» точки, формализованную весовой функцией W :${\displaystyle \{(x_{i},y_{i})\}_{i=1}^{n}}$${\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 ' сложным образом зависит от структуры деревьев и, следовательно, от структуры обучающей выборки. Лин и Чон показывают, что форма окрестностей, используемых случайным лесом, адаптируется к местной важности каждой особенности. ^[24]${\displaystyle x_{i}}$${\displaystyle j}$

Неконтролируемое обучение со случайными лесами [ править ]

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

Варианты [ править ]

Вместо деревьев решений были предложены и оценены линейные модели в качестве базовых оценок в случайных лесах, в частности, полиномиальная логистическая регрессия и наивные байесовские классификаторы . ^{[5] [27] [28]} В случаях, когда взаимосвязь между предикторами и целевой переменной является линейной, базовые учащиеся могут иметь такую ​​же высокую точность, как и учащиеся группы. ^{[29] [5]}

Случайный лес ядра [ править ]

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

История [ править ]

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

Обозначения и определения [ править ]

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

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

Единый лес [ править ]

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

Из случайного леса в KeRF [ править ]

Учитывая обучающую выборку из -значных независимых случайных величин , распределенных в качестве независимого прототипа пары , где . Мы стремимся предсказать ответ , связанный со случайной величиной , путем оценки функции регрессии . Лес случайной регрессии - это e${\displaystyle {\mathcal {D}}_{n}=\{(\mathbf {X} _{i},Y_{i})\}_{i=1}^{n}}$${\displaystyle [0,1]^{p}\times \mathbb {R} }$${\displaystyle (\mathbf {X} ,Y)}$${\displaystyle \operatorname {E} [Y^{2}]<\infty }$${\displaystyle Y}$${\displaystyle \mathbf {X} }$${\displaystyle m(\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})</math.h>.Forregressiontrees,wehave<math>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_{n}(\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})}}$

Таким образом , случайный лес оценки удовлетворяют условиям, для всех , . Лес случайной регрессии имеет два уровня усреднения: сначала по выборкам в целевой ячейке дерева, а затем по всем деревьям. Таким образом, вклад наблюдений, которые находятся в ячейках с высокой плотностью точек данных, меньше, чем вклад наблюдений, которые принадлежат менее заселенным ячейкам. Чтобы улучшить методы случайного леса и компенсировать неверную оценку, Скорнет ^[30] определил KeRF следующим образом:${\displaystyle \mathbf {x} \in [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{aligned}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{ for all }}\mathbf {x} ,\mathbf {z} \in [0,1]^{d}.\end{aligned}}}$

Униформа 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{ for all }}\mathbf {x} \in [0,1]^{d}.}$

Свойства [ править ]

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

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

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

${\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).}$

Результаты согласованности [ править ]

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

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

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

Согласованность единого KeRF [ править ]

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

Недостатки [ править ]

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

См. Также [ править ]

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

Ссылки [ править ]

Дальнейшее чтение [ править ]

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

Внешние ссылки [ править ]

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