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

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

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

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

Расширение алгоритма было разработано Лео Брейманом ^[7] и Адель Катлер ^[8] , которые зарегистрировали ^[9] «Random Forests» как торговую марку в 2006 году (по состоянию на 2019 год ^[update]принадлежит Minitab, Inc. ). ^{[10] Расширение объединяет идею «} бэггинга » Бреймана и случайный выбор признаков, впервые представленную Хо ^[1] , а затем независимо Амитом и Джиманом ^[11] для построения коллекции деревьев решений с контролируемой дисперсией.

История

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

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

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

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

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

Алгоритм

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

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

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

Упаковка в мешки

Иллюстрация обучения модели Random Forest. Обучающий набор данных (в данном случае из 250 строк и 100 столбцов) случайным образом выбирается с заменой n раз. Затем на каждом образце обучается дерево решений. Наконец, для прогнозирования результаты всех n деревьев объединяются для выработки окончательного решения.

Алгоритм обучения для случайных лесов применяет общую технику бутстрап-агрегирования или бэггинга к обучающимся деревьям. При наличии обучающего набора 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 в своей выборке бутстрепа. ^[14]

Ошибка обучения и тестирования, как правило, выравнивается после того, как будет подобран определенный объем деревьев.

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

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

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

ExtraTrees

Добавление еще одного шага рандомизации дает чрезвычайно рандомизированные деревья , или ExtraTrees. Как и обычные случайные леса, они представляют собой ансамбль отдельных деревьев, но есть два основных отличия: (1) каждое дерево обучается с использованием всей обучающей выборки (а не выборки bootstrap), и (2) нисходящее разделение рандомизировано: для каждого рассматриваемого признака выбирается ряд случайных точек отсечения вместо вычисления локально оптимальной точки отсечения (основанной, например, на приросте информации или примеси Джини ). Значения выбираются из равномерного распределения в пределах эмпирического диапазона признака (в обучающем наборе дерева). Затем из всех случайно выбранных разделений для разделения узла выбирается разделение, дающее наивысшую оценку.

Подобно обычным случайным лесам, можно указать количество случайно выбранных признаков, которые следует учитывать в каждом узле. Значения по умолчанию для этого параметра предназначены для классификации и регрессии, где — количество признаков в модели. ^[16] ${\displaystyle {\sqrt {p}}}$ ${\displaystyle p}$ ${\displaystyle p}$

Случайные леса для многомерных данных

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

• Предварительная фильтрация: устранение признаков, которые в основном представляют собой просто шум. ^{[17] [18]}
• Обогащенный случайный лес (ERF): использование взвешенной случайной выборки вместо простой случайной выборки в каждом узле каждого дерева, придавая больший вес признакам, которые кажутся более информативными. ^{[19] [20]}
• Случайный лес с весами деревьев (TWRF): придать больший вес более точным деревьям. ^{[21] [22]}

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

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

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

Важность перестановки

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

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

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

Этот метод определения важности переменных имеет некоторые недостатки:

• Когда признаки имеют разное количество значений, случайные леса отдают предпочтение признакам с большим количеством значений. Решения этой проблемы включают частичные перестановки ^{[24] [25] [26]} и выращивание несмещенных деревьев. ^{[27] [28]}
• Если данные содержат группы коррелированных признаков схожей значимости, то меньшие группы имеют преимущество перед большими группами. ^[29]
• Если есть коллинеарные признаки, процедура может не определить важные признаки. Решением является перестановка групп коррелированных признаков вместе. ^[30]

Среднее уменьшение важности примесных признаков

Этот подход к важности признаков для случайных лесов рассматривает как важные переменные, которые значительно уменьшают примеси во время разделения. ^[31] Он описан в книге «Деревья классификации и регрессии» Лео Бреймана ^[32] и является реализацией по умолчанию в sci-kit learnи R. Определение таково: где $${\displaystyle {\text{unormalized average importance}}(x)={\frac {1}{n_{T}}}\sum _{i=1}^{n_{T}}\sum _{{\text{node }}j\in T_{i}|{\text{split variable}}(j)=x}p_{T_{i}}(j)\Delta i_{T_{i}}(j),}$$

• ${\displaystyle x}$это особенность
• ${\displaystyle n_{T}}$это количество деревьев в лесу
• ${\displaystyle T_{i}}$это дерево ${\displaystyle i}$
• ${\displaystyle p_{T_{i}}(j)={\frac {n_{j}}{n}}}$это доля образцов, достигших узла ${\displaystyle j}$
• ${\displaystyle \Delta i_{T_{i}}(j)}$изменение примеси в дереве в узле . ${\displaystyle t}$ ${\displaystyle j}$

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

• Энтропия
• Коэффициент Джини
• Среднеквадратическая ошибка

Нормализованная важность затем получается путем нормализации по всем признакам, так что сумма нормализованных важностей признаков равна 1.

Реализация sci-kit learnпо умолчанию может сообщать о вводящей в заблуждение важности признаков: ^[30]

• он отдает предпочтение признакам с высокой кардинальностью
• он использует статистику обучения и поэтому не отражает полезность признака для прогнозов на тестовом наборе ^[33]

Связь с ближайшими соседями

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

Неконтролируемое обучение

В рамках своей конструкции предикторы случайного леса естественным образом приводят к мере различия между наблюдениями. Аналогично можно определить различие между немаркированными данными, обучив лес различать исходные «наблюдаемые» данные от соответствующим образом сгенерированных синтетических данных, взятых из эталонного распределения. ^{[7] [35]} Различие случайного леса привлекательно, поскольку оно очень хорошо обрабатывает смешанные типы переменных, инвариантно к монотонным преобразованиям входных переменных и устойчиво к выпадающим наблюдениям. Различие случайного леса легко справляется с большим количеством полунепрерывных переменных благодаря своему внутреннему выбору переменных; например, различие случайного леса «Addcl 1» взвешивает вклад каждой переменной в соответствии с тем, насколько она зависит от других переменных. Различие случайного леса использовалось в различных приложениях, например, для поиска кластеров пациентов на основе данных маркеров тканей. ^[36]

Варианты

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

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

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

История

Лео Брейман ^[42] был первым, кто заметил связь между случайным лесом и методами ядра . Он указал, что случайные леса, обученные с использованием случайных векторов iid при построении дерева, эквивалентны ядру, действующему на истинном пределе. Лин и Чон ^[43] установили связь между случайными лесами и адаптивным ближайшим соседом, подразумевая, что случайные леса можно рассматривать как адаптивные оценки ядра. Дэвис и Гахрамани ^[44] предложили случайный лес ядра (KeRF) и показали, что он может эмпирически превзойти самые современные методы ядра. Скорнет ^[41] первым определил оценки KeRF и дал явную связь между оценками KeRF и случайным лесом. Он также дал явные выражения для ядер, основанных на центрированном случайном лесу ^[45] и равномерном случайном лесу ^[46] , двух упрощенных моделях случайного леса. Он назвал эти два KeRF центрированным KeRF и равномерным KeRF и доказал верхние границы их показателей согласованности.

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

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

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

Однородный лес

Однородный лес ^[46] — еще одна упрощенная модель для исходного случайного леса Бреймана, который равномерно выбирает признак среди всех признаков и выполняет разбиение в точке, равномерно нарисованной на стороне ячейки, вдоль предварительно выбранного признака.

От случайного леса к KeRF

Дана обучающая выборка независимых случайных величин со значениями -, распределенных как независимая прототипная пара , где . Мы стремимся предсказать отклик , связанный со случайной величиной , путем оценки функции регрессии . Случайный регрессионный лес представляет собой ансамбль рандомизированных деревьев регрессии. Обозначим предсказанное значение в точке -м деревом, где - независимые случайные величины, распределенные как общая случайная величина , независимая от выборки . Эту случайную величину можно использовать для описания случайности, вызванной разделением узлов и процедурой выборки для построения дерева. Деревья объединяются для формирования конечной оценки леса . Для деревьев регрессии мы имеем , где - ячейка, содержащая , разработанная с учетом случайности и набора данных , и . ${\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})}$ ${\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_{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})}}$

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

Равномерный 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 {\left(-\ln |x_{m}|\right)^{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).}$$

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

Предположим, что , где — центрированный гауссовский шум, независимый от , с конечной дисперсией . Более того, равномерно распределено на и является липшицевым . Скорне ^[41] доказал верхние границы скоростей согласованности для центрированного 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}}$

Недостатки

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

Другим ограничением случайных лесов является то, что если признаки линейно коррелируют с целью, случайный лес может не повысить точность базового обучающегося. ^{[37] [40]} То же самое и в задачах с несколькими категориальными переменными. ^[49]

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

• Boosting  – Метод в машинном обучении
• Обучение дереву решений  – алгоритм машинного обучения
• Ансамбльное обучение  – Статистика и методы машинного обучения
• Градиентный бустинг  – метод машинного обучения
• Непараметрическая статистика  – Тип статистического анализаPages displaying short descriptions of redirect targets
• Рандомизированный алгоритм  – алгоритм, который использует некоторую степень случайности как часть своей логики или процедуры.

Ссылки

1. Ho, Tin Kam (1995). Random Decision Forests (PDF) . Труды 3-й Международной конференции по анализу и распознаванию документов, Монреаль, Квебек, 14–16 августа 1995 г. стр. 278–282. Архивировано из оригинала (PDF) 17 апреля 2016 г. . Получено 5 июня 2016 г. .
2. Ho TK (1998). «Метод случайного подпространства для построения лесов решений» (PDF) . Труды IEEE по анализу шаблонов и машинному интеллекту . 20 (8): 832–844. doi :10.1109/34.709601. S2CID  206420153.
3. Хасти, Тревор ; Тибширани, Роберт ; Фридман, Джером (2008). Элементы статистического обучения (2-е изд.). Springer. ISBN 0-387-95284-5.
4. Kleinberg E (1990). "Стохастическая дискриминация" (PDF) . Annals of Mathematics and Artificial Intelligence . 1 (1–4): 207–239. CiteSeerX 10.1.1.25.6750 . doi :10.1007/BF01531079. S2CID  206795835. Архивировано из оригинала (PDF) 2018-01-18. 
5. Kleinberg E (1996). «Метод стохастического моделирования, устойчивый к перетренировке, для распознавания образов». Annals of Statistics . 24 (6): 2319–2349. doi : 10.1214/aos/1032181157 . MR  1425956.
6. Kleinberg E (2000). «Об алгоритмической реализации стохастической дискриминации» (PDF) . IEEE Transactions on Pattern Analysis and Machine Intelligence . 22 (5): 473–490. CiteSeerX 10.1.1.33.4131 . doi :10.1109/34.857004. S2CID  3563126. Архивировано из оригинала (PDF) 2018-01-18. 
7. Брейман Л (2001). «Случайные леса». Машинное обучение . 45 (1): 5–32. Bibcode :2001MachL..45....5B. doi : 10.1023/A:1010933404324 .
8. Liaw A (16 октября 2012 г.). "Документация для пакета R randomForest" (PDF) . Получено 15 марта 2013 г.
9. Регистрационный номер товарного знака в США 3185828, зарегистрирован 19 декабря 2006 г.
10. "Торговая марка RANDOM FORESTS компании Health Care Productivity, Inc. - Регистрационный номер 3185828 - Серийный номер 78642027 :: Торговые марки Justia".
11. Amit Y, Geman D (1997). "Квантование и распознавание форм с помощью рандомизированных деревьев" (PDF) . Neural Computation . 9 (7): 1545–1588. CiteSeerX 10.1.1.57.6069 . doi :10.1162/neco.1997.9.7.1545. S2CID  12470146. Архивировано из оригинала (PDF) 2018-02-05 . Получено 2008-04-01 . 
12. Хит, Д., Касиф, С. и Зальцберг, С. (1993). k-DT: Метод обучения с использованием множества деревьев. В трудах Второго международного семинара по обучению с использованием множества стратегий , стр. 138-149.
13. Дитерих, Томас (2000). «Экспериментальное сравнение трех методов построения ансамблей деревьев решений: бэггинг, бустинг и рандомизация». Машинное обучение . 40 (2): 139–157. doi : 10.1023/A:1007607513941 .
14. Гарет Джеймс; Даниэла Виттен; Тревор Хасти; Роберт Тибширани (2013). Введение в статистическое обучение. Springer. С. 316–321.
15. Хо, Тин Кам (2002). «Анализ сложности данных сравнительных преимуществ конструкторов леса решений» (PDF) . Анализ шаблонов и приложения . 5 (2): 102–112. doi :10.1007/s100440200009. S2CID  7415435. Архивировано из оригинала (PDF) 2016-04-17 . Получено 2015-11-13 .
16. Гертс П., Эрнст Д., Вехенкель Л. (2006). «Чрезвычайно рандомизированные деревья» (PDF) . Машинное обучение . 63 : 3–42. дои : 10.1007/s10994-006-6226-1 .
17. Dessi, N. & Milia, G. & Pes, B. (2013). Повышение производительности случайных лесов при классификации данных микрочипов. Доклад конференции, 99-103. 10.1007/978-3-642-38326-7_15.
18. Ye, Y., Li, H., Deng, X. и Huang, J. (2008) Случайный лес взвешивания признаков для обнаружения скрытых интерфейсов веб-поиска. Журнал вычислительной лингвистики и обработки китайского языка, 13, 387–404.
19. Амаратунга, Д., Кабрера, Дж., Ли, YS (2008) Обогащенный случайный лес. Биоинформатика, 24, 2010-2014.
20. Гош Д., Кабрера Дж. (2022) Обогащенный случайный лес для высокоразмерных геномных данных. IEEE/ACM Trans Comput Biol Bioinform. 19(5):2817-2828. doi:10.1109/TCBB.2021.3089417.
21. Уинхэм, Стейси и Фреймут, Роберт и Бернака, Джоанна. (2013). Подход с использованием взвешенных случайных лесов для улучшения предсказательной эффективности. Статистический анализ и интеллектуальный анализ данных. 6. 10.1002/sam.11196.
22. Li, HB, Wang, W., Ding, HW, & Dong, J. (2010, 10-12 ноября 2010 г.). Метод случайного леса с весами деревьев для классификации высокоразмерных зашумленных данных. Доклад, представленный на 7-й международной конференции IEEE 2010 года по инжинирингу электронного бизнеса.
23. Zhu R, Zeng D, Kosorok MR (2015). «Деревья обучения с подкреплением». Журнал Американской статистической ассоциации . 110 (512): 1770–1784. doi :10.1080/01621459.2015.1036994. PMC 4760114. PMID  26903687 . 
24. Дэн, Х.; Рунгер, Г.; Тув, Э. (2011). Смещение мер важности для многозначных атрибутов и решений. Труды 21-й Международной конференции по искусственным нейронным сетям (ICANN). стр. 293–300.
25. Altmann A, Toloşi L, Sander O, Lengauer T (май 2010 г.). «Важность перестановки: скорректированная мера важности признака». Биоинформатика . 26 (10): 1340–7. doi : 10.1093/bioinformatics/btq134 . PMID  20385727.
26. Пирионеси С. Мадех; Эль-Дираби Тамер Э. (2020-06-01). «Роль аналитики данных в управлении инфраструктурными активами: преодоление проблем с размером и качеством данных». Журнал транспортной инженерии, часть B: Дорожные покрытия . 146 (2): 04020022. doi :10.1061/JPEODX.0000175. S2CID  216485629.
27. Strobl C, Boulesteix AL, Augustin T (2007). "Непредвзятый выбор разделенных деревьев классификации на основе индекса Джини" (PDF) . Computational Statistics & Data Analysis . 52 : 483–501. CiteSeerX 10.1.1.525.3178 . doi :10.1016/j.csda.2006.12.030. 
28. Painsky A, Rosset S (2017). «Cross-Validated Variable Selection in Tree-Based Methods Improves Predictive Performance». Труды IEEE по анализу шаблонов и машинному интеллекту . 39 (11): 2142–2153. arXiv : 1512.03444 . doi : 10.1109/tpami.2016.2636831. PMID  28114007. S2CID  5381516.
29. Tolosi L, Lengauer T (июль 2011 г.). «Классификация с коррелированными признаками: ненадежность ранжирования признаков и решений». Биоинформатика . 27 (14): 1986–94. doi : 10.1093/bioinformatics/btr300 . PMID  21576180.
30. "Остерегайтесь важности случайного леса по умолчанию". explained.ai . Получено 2023-10-25 .
31. Ортис-Посадас, Марта Рефухио (29.02.2020). Методы распознавания образов, применяемые к биомедицинским проблемам. Springer Nature. ISBN 978-3-030-38021-2.
32. Брейман, Лео (2017-10-25). Деревья классификации и регрессии. Нью-Йорк: Routledge. doi :10.1201/9781315139470. ISBN 978-1-315-13947-0.
33. https://scikit-learn.org/stable/auto_examples/inspection/plot_permutation_importance.html 31 августа 2023 г.
34. Lin, Yi; Jeon, Yongho (2002). Случайные леса и адаптивные ближайшие соседи (Технический отчет). Технический отчет № 1055. Университет Висконсина. CiteSeerX 10.1.1.153.9168 . 
35. Ши, Т.; Хорват, С. (2006). «Неконтролируемое обучение с предикторами случайного леса». Журнал вычислительной и графической статистики . 15 (1): 118–138. CiteSeerX 10.1.1.698.2365 . doi :10.1198/106186006X94072. JSTOR  27594168. S2CID  245216. 
36. Shi T, Seligson D, Belldegrun AS, Palotie A, Horvath S (апрель 2005 г.). «Классификация опухолей с помощью профилирования микрочипов тканей: кластеризация случайного леса, применяемая к почечноклеточной карциноме». Modern Pathology . 18 (4): 547–57. doi : 10.1038/modpathol.3800322 . PMID  15529185.
37. Пирионеси, С. Мадех; Эль-Дираби, Тамер Э. (2021-02-01). «Использование машинного обучения для изучения влияния типа показателя эффективности на моделирование ухудшения состояния гибкого дорожного покрытия». Журнал инфраструктурных систем . 27 (2): 04021005. doi :10.1061/(ASCE)IS.1943-555X.0000602. ISSN  1076-0342. S2CID  233550030.
38. Prinzie, A.; Van den Poel, D. (2008). «Случайные леса для многоклассовой классификации: случайный многономинальный логит». Expert Systems with Applications . 34 (3): 1721–1732. doi :10.1016/j.eswa.2007.01.029.
39. Prinzie, Anita (2007). "Случайная многоклассовая классификация: обобщение случайных лесов до случайных MNL и случайных NB". В Roland Wagner; Norman Revell; Günther Pernul (ред.). Database and Expert Systems Applications: 18th International Conference, DEXA 2007, Regensburg, Germany, September 3-7, 2007, Proceedings . Lecture Notes in Computer Science. Vol. 4653. pp. 349–358. doi :10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
40. Смит, Пол Ф.; Ганеш, Сива; Лю, Пин (2013-10-01). «Сравнение случайной лесной регрессии и множественной линейной регрессии для прогнозирования в нейронауке». Журнал методов нейронауки . 220 (1): 85–91. doi :10.1016/j.jneumeth.2013.08.024. PMID  24012917. S2CID  13195700.
41. Скорнет, Эрван (2015). «Случайные леса и методы ядра». arXiv : 1502.03836 [math.ST].
42. Брейман, Лео (2000). «Некоторая теория бесконечности для ансамблей предикторов». Технический отчет 579, Департамент статистики UCB. {{cite journal}}: Цитировать журнал требует |journal=( помощь )
43. Лин, Йи; Чон, Ёнхо (2006). «Случайные леса и адаптивные ближайшие соседи». Журнал Американской статистической ассоциации . 101 (474): 578–590. CiteSeerX 10.1.1.153.9168 . doi :10.1198/016214505000001230. S2CID  2469856. 
44. Дэвис, Алекс; Гахрамани, Зубин (2014). «Ядро случайного леса и другие ядра для больших данных из случайных разделов». arXiv : 1402.4293 [stat.ML].
45. Breiman L, Ghahramani Z (2004). "Согласованность для простой модели случайных лесов". Статистический департамент Калифорнийского университета в Беркли. Технический отчет (670). CiteSeerX 10.1.1.618.90 . 
46. Arlot S, Genuer R (2014). «Анализ смещения чисто случайных лесов». arXiv : 1407.3939 [math.ST].
47. Саги, Омер; Рокач, Лиор (2020). «Объяснимый лес решений: преобразование леса решений в интерпретируемое дерево». Information Fusion . 61 : 124–138. doi :10.1016/j.inffus.2020.03.013. S2CID  216444882.
48. Видаль, Тибо; Шиффер, Максимилиан (2020). «Возрожденные ансамбли деревьев». Международная конференция по машинному обучению . 119. PMLR: 9743–9753. arXiv : 2003.11132 .
49. Пирионеси, Сайед Мадех (ноябрь 2019 г.). Применение аналитики данных к управлению активами: ухудшение состояния дорог Онтарио и адаптация к изменению климата (докторская диссертация) (тезис).

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

• Prinzie A, Poel D (2007). "Случайная многоклассовая классификация: обобщение случайных лесов до случайных MNL и случайных NB". Приложения для баз данных и экспертных систем . Конспект лекций по информатике . Том 4653. стр. 349. doi :10.1007/978-3-540-74469-6_35. ISBN 978-3-540-74467-2.
• Denisko D, Hoffman MM (февраль 2018 г.). «Классификация и взаимодействие в случайных лесах». Труды Национальной академии наук Соединенных Штатов Америки . 115 (8): 1690–1692. Bibcode : 2018PNAS..115.1690D. doi : 10.1073/pnas.1800256115 . PMC  5828645. PMID  29440440 .

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

• Описание классификатора Random Forests (сайт Лео Бреймана)
• Лио, Энди и Винер, Мэтью «Классификация и регрессия с помощью случайного леса» R News (2002) Том 2/3 стр. 18 (Обсуждение использования пакета случайного леса для R )