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

редактировать
Метод машинного обучения ансамбля Диаграмма леса случайных решений

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

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

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

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

Contents

  • 1 История
  • 2 Алгоритм
    • 2.1 Предварительные сведения: изучение дерева решений
    • 2.2 Бэггинг
    • 2.3 От бэггинга к случайным лесам
    • 2.4 ExtraTrees
  • 3 Свойства
    • 3.1 Переменная важность
    • 3.2 Связь с ближайшими соседями
  • 4 Неконтролируемое обучение со случайными лесами
  • 5 Варианты
  • 6 Ядровый случайный лес
    • 6.1 История
    • 6.2 Обозначения и определения
      • 6.2.1 Предварительные условия: Центрированные леса
      • 6.2.2 Унифицированный лес
      • 6.2.3 Из случайного леса в KeRF
      • 6.2.4 Центрированный KeRF
      • 6.2.5 Унифицированный KeRF
    • 6.3 Свойства
      • 6.3.1 Связь между KeRF и случайным лесом
      • 6.3.2 Связь между бесконечным KeRF и бесконечным случайным лесом
    • 6.4 Результаты согласованности
      • 6.4.1 Согласованность центрированного KeRF
      • 6.4.2 Согласованность однородного KeRF
  • 7 См. Также
  • 8 Ссылки
  • 9 Дополнительная литература
  • 10 Внешние ссылки

История

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

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

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

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

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

Алгоритм

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

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

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

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

Бэггинг

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

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

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

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

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

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

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

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

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

От упаковки к случайным лесам

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

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

ExtraTrees

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

Свойства

Важность переменной

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

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

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

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

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

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

Отношение между случайными лесами и Алгоритм k-ближайшего соседа (k-NN) был отмечен Лином и Чон в 2002 году. Оказывается, оба могут рассматриваться как так называемые схемы взвешенных окрестностей. Это модели, построенные на основе обучающего набора {(xi, yi)} i = 1 n {\ displaystyle \ {(x_ {i}, y_ {i}) \} _ {i = 1} ^ {n} }\ {(x_ {i}, y_ {i }) \} _ {я = 1} ^ {n} , которые делают прогнозы y ^ {\ displaystyle {\ hat {y}}}{\ hat {y}} для новых точек x ', глядя на «окрестность» точки, формализованную весовая функция W:

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

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

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

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

y ^ = 1 m ∑ j = 1 m ∑ i = 1 n W j (xi, x ′) yi = ∑ i = 1 n (1 m ∑ j = 1 m W j (xi, x ′)) yi. {\ 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}.}{\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 'в этой интерпретации являются точки xi {\ displaystyle x_ {i}}x_ {i} , имеющие один и тот же лист в любом дереве j {\ displaystyle j}j. Таким образом, окрестность x 'сложным образом зависит от структуры деревьев и, следовательно, от структуры обучающей выборки. Лин и Чон показывают, что форма окрестности, используемой случайным лесом, адаптируется к локальной важности каждой функции.

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

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

Варианты

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

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

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

История

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

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

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

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

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

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

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

Для обучающей выборки D n = {(X i, Y i)} i = 1 n {\ displaystyle {\ mathcal {D}} _ {n} = \ {(\ mathbf {X} _ {i}, Y_ {i}) \} _ {i = 1} ^ {n}}{\ mathcal {D}} _ {n} = \ {({ \ mathbf {X}} _ {i}, Y_ {i}) \} _ {{i = 1}} ^ {n} из [0, 1 ] p × R {\ displaystyle [0,1] ^ {p} \ times \ mathbb {R}}[0,1] ^ {p} \ times {\ mathbb {R}} -значные независимые случайные величины, распределенные как независимая пара прототипов (X, Y) { \ displaystyle (\ mathbf {X}, Y)}({\ mathbf {X}}, Y) , где E ⁡ [Y 2] < ∞ {\displaystyle \operatorname {E} [Y^{2}]<\infty }{\ displaystyle \ operatorname {E} [Y ^ {2}] <\ infty} . Мы стремимся предсказать ответ Y {\ displaystyle Y}Y , связанный со случайной величиной X {\ displaystyle \ mathbf {X}}\ mathbf {X} , путем оценки функция регрессии m (x) = E ⁡ [Y ∣ X = x] {\ displaystyle m (\ mathbf {x}) = \ operatorname {E} [Y \ mid \ mathbf {X} = \ mathbf {x }]}{\ displaystyle m (\ mathbf {x}) = \ operatorname {E} [Y \ mid \ mathbf { X} = \ mathbf {x}]} . Лес случайной регрессии - это совокупность M {\ displaystyle M}M деревьев рандомизированной регрессии. Обозначим mn (x, Θ j) {\ displaystyle m_ {n} (\ mathbf {x}, \ mathbf {\ Theta} _ {j})}m_ {n} ({\ mathbf {x}}, {\ mathbf {\ Theta }} _ {j}) предсказанное значение в точке <165.>x {\ displaystyle \ mathbf {x}}\ mathbf {x} по j {\ displaystyle j}j-м дереву, где Θ 1,…, Θ M { \ displaystyle \ mathbf {\ Theta} _ {1}, \ ldots, \ mathbf {\ Theta} _ {M}}{\ displaystyle \ mathbf {\ Theta} _ {1}, \ ldots, \ mathbf {\ Theta} _ { M}} - независимые случайные величины, распределенные как общая случайная величина Θ {\ displaystyle \ mathbf {\ Theta}}{\ mathbf {\ Theta}} , независимо от образца D n {\ displaystyle {\ mathcal {D}} _ {n}}\ mathcal {D} _n . Эта случайная величина может использоваться для описания случайности, вызванной разделением узла и процедурой выборки для построения дерева. Деревья объединяются для формирования оценки конечного леса m M, n (x, Θ 1,…, Θ M) = 1 M ∑ j = 1 M mn (x, Θ j) {\ 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_ {M, n} (\ mathbf {x}, \ Theta _ {1}, \ ldots, \ Theta _ { M}) = {\ frac {1} {M}} \ sum _ {j = 1} ^ {M} m_ {n} (\ mathbf {x}, \ Theta _ {j})} . Для деревьев регрессии mn = ∑ i = 1 n Y i 1 X i ∈ A n (x, Θ j) N n (x, Θ 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})}}}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})}} , где A n (x, Θ j) {\ displaystyle A_ { n} (\ mathbf {x}, \ Theta _ {j})}A_ {n} ({\ mathbf {x}}, \ Theta _ {j}) - это ячейка, содержащая x {\ displaystyle \ mathbf {x}}\ mathbf {x} , созданная со случайностью Θ j {\ displaystyle \ Theta _ {j}}\ Theta _ {j} и набор данных D n {\ displaystyle {\ mathcal {D}} _ {n}}\ mathcal {D} _n , и N N (Икс, Θ J) знак равно ∑ я = 1 N 1 Икс я ∈ A N (Икс, Θ J) {\ Displaystyle N_ {n} (\ mathbf {x}, \ Theta _ {j}) = \ sum _ {i = 1} ^ {n} \ mathbf {1} _ {\ mathbf {X} _ {i} \ in A_ {n} (\ mathbf {x}, \ Theta _ {j}) }}N_ {n} ({\ mathbf {x}}, \ Theta _ {j}) = \ sum _ {{i = 1}} ^ {n} {\ mathbf {1}} _ {{{\ mathbf {X}} _ {i} \ in A_ {n} ({\ mathbf {x}}, \ Theta _ {j})}} .

Таким образом, случайные оценки лесов удовлетворяют для всех x ∈ [0, 1] d {\ displaystyle \ mathbf {x} \ in [0,1] ^ {d}}{\ mathbf {x}} \ in [0,1] ^ {d} , m M, n (x, Θ 1,…, Θ M) = 1 M ∑ j = 1 M (∑ i = 1 n Y i 1 X i ∈ A n (x, Θ j) N n (x, Θ j)) { \ 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)}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) . Лес случайной регрессии имеет два уровня усреднения: сначала по выборкам в целевой ячейке дерева, а затем по всем деревьям. Таким образом, вклад наблюдений, которые происходят в ячейках с высокой плотностью точек данных, меньше, чем вклад наблюдений, которые принадлежат менее заселенным ячейкам. Чтобы улучшить методы случайного леса и компенсировать неправильную оценку, Скорнет определил KeRF как

m ~ M, n (x, Θ 1,…, Θ M) = 1 ∑ j = 1 MN n (x, Θ j) ∑ J знак равно 1 M ∑ я знак равно 1 N Y я 1 Икс я ∈ A N (x, Θ j), {\ 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} \ в A_ {n} (\ mathbf {x}, \ Theta _ {j})},}{\ 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} (\ mat hbf {x}, \ Theta _ {j})},}

, которое равно среднему значению Y i {\ displaystyle Y_ {i}}Y_ {i } попадает в ячейки, содержащие x {\ displaystyle \ mathbf {x}}\ mathbf {x} в лесу. Если мы определим функцию соединения M {\ displaystyle M}M конечного леса как KM, n (x, z) = 1 M ∑ j = 1 M 1 z ∈ A n (Икс, Θ J) {\ 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 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})}} , то есть доля ячеек, разделяемых между x {\ displaystyle \ mathbf {x}}\ mathbf {x} и z {\ displaystyle \ mathbf {z}}\ mathbf {z} , тогда почти наверняка мы имеем m ~ M, N (Икс, Θ 1,…, Θ М) знак равно ∑ я знак равно 1 N Y я КМ, N (Икс, Икс) ∑ ℓ = 1 N КМ, N (Икс, Икс ℓ) {\ Displaystyle {\ тильда { 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})}}}{\ 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

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

K kcc (x, z) = ∑ k 1,…, kd, ∑ j = 1 dkj = кк! к 1! ⋯ к д! (1 d) k ∏ j = 1 d 1 ⌈ 2 k j x j ⌉ = ⌈ 2 k j z j для всех x, z ∈ [0, 1] d. {\ 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 {align}}}{\ displaystyle {\ begin {выровнено } 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 {align}}}

Uniform KeRF

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

K kuf (0, x) = ∑ k 1,…, kd, ∑ j = 1 dkj = kk! к 1! … К д! (1 d) k ∏ m = 1 d (1 - | x m | ∑ j = 0 k m - 1 (- ln ⁡ | x m |) j j!) Для всех x ∈ [0, 1] d. {\ 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}.}{\ 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 {f или все}} \ mathbf {x} \ in [0,1] ^ {d}.}

Свойства

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

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

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

an ≤ N n (x, Θ) ≤ bn и an ≤ 1 M ∑ m = 1 MN nx, Θ m ≤ bn. {\ 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 a_ {n} \ leq N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n } {\ text {и}} a_ {n} \ leq {\ frac {1} {M}} \ sum _ {m = 1} ^ {M} N_ {n} {\ mathbf {x}, \ Theta _ {m}} \ leq b_ {n}.}

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

| т М, п (х) - т ~ М, п (х) | ≤ b n - a n a n m ~ M, n (x). {\ 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}).}{\ 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 и бесконечным случайным лесом

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

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

  • E ⁡ [N n (x, Θ)] ≥ 1, {\ displaystyle \ operatorname {E} [N_ {n} (\ mathbf {x}, \ Theta)] \ geq 1,}{\ displaystyle \ operatorname {E} [N_ {n} (\ mathbf {x}, \ Theta)] \ geq 1,}
  • P ⁡ [an ≤ N n (x, Θ) ≤ bn ∣ D n] ≥ 1 - ε n / 2, {\ 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 N_ {n} (\ mathbf {x}, \ Theta) \ leq b_ {n} \ mid {\ mathcal {D} } _ {n}] \ geq 1- \ varepsilon _ {n} / 2,}
  • P ⁡ [an ≤ E Θ ⁡ [N n (x, Θ)] ≤ bn ∣ D n] ≥ 1 - ε 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 \ 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,}

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

| m ∞, n (x) - m ~ ∞, n (x) | ≤ b n - a n a n m ~ ∞, n (x) + n ε n (макс.1 ≤ i ≤ n Y i). {\ 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).}{\ displaystyle | m _ {\ infty, n} (\ mathbf {x}) - {\ тильда {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).}

Результаты согласованности

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

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

Обеспечение k → ∞ {\ displaystyle k \ rightarrow \ infty}k \ rightarrow \ infty и n / 2 k → ∞ {\ displaystyle n / 2 ^ {k} \ rightarrow \ infty}n / 2 ^ {k} \ rightarrow \ infty , существует константа C 1>0 {\ displaystyle C_ {1}>0}C_{1}>0 таким образом, для всех n {\ displaystyle n}n , E [m ~ ncc (X) - m (X)] 2 ≤ C 1 n - 1 / (3 + d log ⁡ 2) (log ⁡ n) 2 {\ 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}}{\ 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

Обеспечение k → ∞ {\ displaystyle k \ rightarrow \ infty}k \ rightarrow \ infty и n / 2 k → ∞ {\ displaystyle n / 2 ^ {k} \ rightarrow \ infty}n / 2 ^ {k} \ rightarrow \ infty , существует константа C>0 {\ displaystyle C>0}C>0 такое, что E [m ~ nuf (X) - m (X)] 2 ≤ C n - 2 / (6 + 3 d log ⁡ 2) (log ⁡ n) 2 {\ displaystyle \ mathbb {E} [{\ тильда {m}} _ {n} ^ {uf} (\ mathbf {X}) -m (\ mathbf {X})] ^ {2} \ leq Cn ^ {- 2 / (6 + 3d \ log 2)} (\ log n) ^ {2}}{\ mathbb {E}} [{\ tilde {m}} _ {n} ^ {{uf}} ({ \ mathbf {X}}) - m ({\ mathbf {X}})] ^ {2} \ leq Cn ^ {{- 2 / (6 + 3d \ log 2)}} (\ log n) ^ {2 } .

См. Также

Ссылки

Дополнительная литература

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

Последняя правка сделана 2021-06-03 08:07:28
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте