Главная / Уроки / Случайный лес

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

Доброго времени суток, читатель. Random Forest сегодня является одним из популярнейших и крайне эффективных методов решения задач машинного обучения, таких как классификация и регрессия. По эффективности он конкурирует с машинами опорных векторов, нейронными сетями и бустингом, хотя конечно не лишен своих недостатков. С виду алгоритм обучения крайне прост (в сравнении скажем с алгоритмом обучения машины опорных векторов, кому мало острых ощущений в жизни, крайне советую заняться этим на досуге). Мы же попробуем в доступной форме разобраться в основных идеях, заложенных в Random Forest (бинарное дерево решений, бутстреп аггрегирование или бэггинг, метод случайных подпространств и декорреляция) и понять почему все это вместе работает. Модель относительно своих конкурентов довольно таки молодая: началось все со статьи 1997 года в которой авторы предлагали способ построения одного дерева решений, используя метод случайных подпространств признаков при создании новых узлов дерева; затем был ряд статей, который завершился публикацией каноничной версии алгоритма в 2001 году, в котором строится ансамбль решающих деревьев на основе бутстреп агрегирования, или бэггинга. В конце будет приведен простой, совсем не шустрый, но крайне наглядный способ реализации этой модели на c#, а так же проведен ряд тестов. Кстати на фотке справа вы можете наблюдать настоящий случайный лес который произрастает у нас тут в Калининградской области на Куршской косе.

Бинарное дерево решений

Начать следует с дерева, как с основного структурного элемента леса, но в контексте изучаемой модели. Изложение будет строится на предположении, что читатель понимает, что из себя представляет дерево, как структура данных. Построение дерева будет выполняться примерно по алгоритму CART(Classification and Regression Tree), который строит бинарные деревья решений. Кстати тут на хабре есть годная статья по построению такихдеревьев на базе минимизации энтропии, в нашем варианте это будет частным случаем. Итак представьте себе пространство признаков, допустим двумерное, что бы было легче визуализировать, в котором задано множество объектов двух классов.

Введем ряд обозначений. Обозначим множество признаков следующим образом:

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

Так же необходимо ввести так называемую меру неоднородности множества относительно его меток. Представьте, что некоторое подмножество обучающего множества состоит из 5 красных и 10 синих объектов, тогда мы можем утверждать, что в этом подмножестве вероятность вытянуть красный объект будет 1/3, а синий 2/3. Обозначим следующим образом вероятность k-ого класса в некотором подмножестве обучающего множества:

Таким образом мы задали эмпирическое дискретное вероятностное распределение меток в подмножестве наблюдений. Мерой неоднородностиэтого подмножества будем называть функцию следующего вида, где K(A) — общее количество меток подмножества A:

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

Давайте взглянем на некоторые примеры мер неоднородности (вектор pсостоит из m вероятностей меток встречающихся в некотором подмножестве Aобучающего множества):

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

где — вектор вероятностей полученный по вышеописанной процедуре от подмножества множества A, состоящего из тех элементов для которых выполняется условие f < x. Так же не стоит забывать, что средняя стоимость разбиения не должна превышать стоимость исходного множества. Давайте теперь вернемся к исходной картинке и глянем что реально происходит, разделим вышеописанным образом исходное множество данных:

Как видите множество выше линии y=2.840789 полностью состоит из синих меток, таким образом имеет смыл разбивать далее только второе множество.

В этот раз линия x=2.976719. В общем кому интересно побаловаться с этой картинкой, вот код на R:

Код визуализации

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

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

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

Вроде с деревьями все порешали. Мы не будем останавливаться на плюсах и минусах этого метода, в википедии есть хороший список. Но в конце хочется добавить иллюстрацию из книги An Introduction to Statistical Learning про разницу линейных моделей и деревьев.

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

Bootstrap aggregating или bagging

Перейдем к следующей идейной составляющей random forest’а. Итак названиеBAGging, образовано от Bootstrap AGgregating. В статистике под бутстрепом понимают как способ оценки стандартной ошибки статистик выборочного вероятностного распределения, так и способ семплирования выборок из набора данных основанный на методе Монте-Карло.

Бутстреп семплинг довольно таки прост по своей идее, и применяется тогда, когда мы не имеем возможности получить большое количество выборок из реального распределения, а это почти всегда так. Допустим мы хотим получить m множеств наблюдений размера n, но у нас в распоряжении только одно множество из n наблюдений. Тогда мы генерируем m множествравновероятностым выбором n элементов из исходного множества с возвратом выбранного элемента (выборка с повторением или возвращением). При больших значениях n, количество уникальных элементов полученного бутстреп семплингом множества будет составлять (1 — 1/e) ≈ 63.2% от общего числа уникальных наблюдений исходного множества. Обозначим Dii-ое множество полученное бутстреп семплированием, мы оцениваем на нем некоторый параметр ai, и повторяем эту процедуру m раз. Стандартная ошибка бутстреп оценки параметра записывается следующим образом:

Итак, статистический бутстреп позволяет оценить ошибку оценки некоторого параметра распределения. Но это так отвлечение от темы, нам же интересен метод бутстреп семплирования.

А теперь рассмотрим набор из m независимых случайно выбранных элементовx из одного вероятностного распределения, с некоторым математическим ожиданием и дисперсией σ2. Тогда выборочное среднее будет равно:

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

Получается, что усреднение множества значений случайной переменной уменьшает вариативность. На этом и строится идея агрегирования бутстреп выборок. Сгенерируем m бутстреп выборок размера n из обучающего множества D (тоже размера n):

На каждой бутстреп выборке обучим модель f и введем следующую функцию, такой подход и называется bootstrap aggregating или bagging:

Bagging можно проиллюстрировать следующим графиком из википедии, где bag-модель изображена красной линией и является усреднением множества других моделей.

Декорреляция

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

Мы видим что из 1000 деревьев 22-ой признак (очевидно значение фичи одно и тоже) встречается в 526 деревьях, и почти во всех дочерние ноды одинаковые. Другими словами деревья скоррелированны относительно друг друга. Получается, что нет смысла строить 1000 деревьев, если достаточно всего нескольких, а чаще всего одного или двух. А теперь давайте попробуем при построении дерева использовать при разделении каждого узла только некоторый небольшой случайный набор признаков из множества всех признаков, скажем 7 случайных из 32.

Как видите, распределение значительно изменилось в сторону большего разнообразия деревьев (кстати не только в корневом узле, но и в дочерних), что и было целью такого трюка. Теперь 22 признак встречается только в 158 случаях. Выбор “7 случайных из 32 признаков” обоснован эмпирическим наблюдением (я так и не нашел автора этого наблюдения), и в задачах классификации это как правило квадратный корень из общего количества признаков. Другими словами деревья стали менее скореллированными, а процесс называется декорреляция.

Такой метод, в общем, называется Random subspace method и применяется не только для деревьев решений, но и для других моделей, таких как нейросети.

В общем как то так выглядел бы обычный ровный лес, и декоррелированный.

 

Давайте глянем на некоторые из них, они получаются совсем разные благодаря декорреляции.

Раз

 

Два

 

Три

 

Оригинал статьи: http://habrahabr.ru/post/215453/

 

comments powered by HyperComments

Посмотрите также

Нейронные сети за 1 день

Всем привет. В этот раз мы попытаемся разобраться с нейронными сетями без биологии и за 1 день. Зачем они нужны? Для того чтобы понять зачем нужны нейронные сети, нужно разобраться с тем, что они из себя представляют. Искусственные нейронные сети — это совокупность искусственных нейронов, которые выполняют роль сумматоров. Искусственные нейронные сети нужны для решения [...]