Extremely randomized trees что это

Разница между случайным лесом и чрезвычайно рандомизированными деревьями

Я понял, что Случайный Лес и Чрезвычайно Рандомизированные Деревья отличаются в том смысле, что расщепления деревьев в Случайном Лесу являются детерминированными, тогда как они случайны в случае Чрезвычайно Рандомизированных Деревьев (чтобы быть более точным, следующее разделение является лучшим разделением среди случайных равномерных расщеплений в выбранных переменных для текущего дерева). Но я не до конца понимаю влияние этого разделения в различных ситуациях.

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

Тем не менее, при условии, что (возможно, ручной) выбор функций близок к оптимальному, производительность примерно одинакова, однако, ET могут быть вычислительно быстрее.

Нет серебряной пули как всегда.

Пьер Гёртс, Дэмиен Эрнст, Луи Вехенке. «Чрезвычайно рандомизированные деревья»

Вот две проблемы, над которыми я работал лично, когда дополнительные деревья оказались полезными с очень шумными данными:

Большое спасибо за ответы! Поскольку у меня все еще оставались вопросы, я выполнил некоторые численные моделирования, чтобы получить больше информации о поведении этих двух методов.

Когда все переменные релевантны, оба метода, похоже, достигают одинаковой производительности,

Дополнительные деревья кажутся в три раза быстрее, чем случайный лес (по крайней мере, в реализации scikit learn)

источники

ExtraTreesClassifier похож на брата в RandomForest, но с двумя важными отличиями.

Мы строим несколько деревьев решений. Для построения нескольких деревьев нам нужно несколько наборов данных. Лучшая практика заключается в том, что мы не обучаем деревья решений по всему набору данных, а обучаем только части данных (около 80%) для каждого дерева. В случайном лесу мы рисуем наблюдения с заменой. Таким образом, мы можем повторять наблюдения в случайном лесу. В ExtraTreesClassifier мы рисуем наблюдения без замены, поэтому у нас не будет повторения наблюдений, как в случайном лесу.

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

1. Дерево решений (высокая дисперсия)

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

2. Случайный лес (средняя дисперсия)

Модели случайных лесов снижают риск переобучения путем введения случайности путем:

3. Дополнительные деревья (низкая дисперсия)

Дополнительные деревья похожи на случайный лес в том смысле, что он строит несколько деревьев и разделяет узлы, используя случайные подмножества объектов, но с двумя ключевыми отличиями: он не запускает наблюдения (то есть выборки без замены), а узлы разбиваются на случайные разбиения, не лучшие расколы. Итак, в заключение, ExtraTrees:

В Extra Trees случайность не возникает из-за начальной загрузки данных, а скорее из случайного разделения всех наблюдений. ExtraTrees назван в честь (чрезвычайно рандомизированных деревьев).

Источник

1.11. Ensemble methods¶

The goal of ensemble methods is to combine the predictions of several base estimators built with a given learning algorithm in order to improve generalizability / robustness over a single estimator.

Two families of ensemble methods are usually distinguished:

In averaging methods, the driving principle is to build several estimators independently and then to average their predictions. On average, the combined estimator is usually better than any of the single base estimator because its variance is reduced.

By contrast, in boosting methods, base estimators are built sequentially and one tries to reduce the bias of the combined estimator. The motivation is to combine several weak models to produce a powerful ensemble.

1.11.1. Bagging meta-estimator¶

In ensemble algorithms, bagging methods form a class of algorithms which build several instances of a black-box estimator on random subsets of the original training set and then aggregate their individual predictions to form a final prediction. These methods are used as a way to reduce the variance of a base estimator (e.g., a decision tree), by introducing randomization into its construction procedure and then making an ensemble out of it. In many cases, bagging methods constitute a very simple way to improve with respect to a single model, without making it necessary to adapt the underlying base algorithm. As they provide a way to reduce overfitting, bagging methods work best with strong and complex models (e.g., fully developed decision trees), in contrast with boosting methods which usually work best with weak models (e.g., shallow decision trees).

Bagging methods come in many flavours but mostly differ from each other by the way they draw random subsets of the training set:

L. Breiman, “Pasting small votes for classification in large databases and on-line”, Machine Learning, 36(1), 85-103, 1999.

L. Breiman, “Bagging predictors”, Machine Learning, 24(2), 123-140, 1996.

T. Ho, “The random subspace method for constructing decision forests”, Pattern Analysis and Machine Intelligence, 20(8), 832-844, 1998.

G. Louppe and P. Geurts, “Ensembles on Random Patches”, Machine Learning and Knowledge Discovery in Databases, 346-361, 2012.

1.11.2. Forests of randomized trees¶

The sklearn.ensemble module includes two averaging algorithms based on randomized decision trees : the RandomForest algorithm and the Extra-Trees method. Both algorithms are perturb-and-combine techniques [B1998] specifically designed for trees. This means a diverse set of classifiers is created by introducing randomness in the classifier construction. The prediction of the ensemble is given as the averaged prediction of the individual classifiers.

As other classifiers, forest classifiers have to be fitted with two arrays: a sparse or dense array X of shape (n_samples, n_features) holding the training samples, and an array Y of shape (n_samples,) holding the target values (class labels) for the training samples:

1.11.2.1. Random Forests¶

In random forests (see RandomForestClassifier and RandomForestRegressor classes), each tree in the ensemble is built from a sample drawn with replacement (i.e., a bootstrap sample) from the training set.

The purpose of these two sources of randomness is to decrease the variance of the forest estimator. Indeed, individual decision trees typically exhibit high variance and tend to overfit. The injected randomness in forests yield decision trees with somewhat decoupled prediction errors. By taking an average of those predictions, some errors can cancel out. Random forests achieve a reduced variance by combining diverse trees, sometimes at the cost of a slight increase in bias. In practice the variance reduction is often significant hence yielding an overall better model.

1.11.2.2. Extremely Randomized Trees¶

In extremely randomized trees (see ExtraTreesClassifier and ExtraTreesRegressor classes), randomness goes one step further in the way splits are computed. As in random forests, a random subset of candidate features is used, but instead of looking for the most discriminative thresholds, thresholds are drawn at random for each candidate feature and the best of these randomly-generated thresholds is picked as the splitting rule. This usually allows to reduce the variance of the model a bit more, at the expense of a slightly greater increase in bias:

1.11.2.3. Parameters¶

Источник

Daring to quantify the markets |

Pablo Aznar

17/06/2020

Extra Trees and Random Forest are two very similar ensemble methods and often a doubt arises as to whether to use one or the other. What is really the difference between them?

In previous posts, “Random forest: many are better than one”, we have seen how to create a Random Forest from decision trees and how they improve their performance. Furthermore, if you want more information about simple decision trees, you can find read “Classification trees in Matlab“.

Extra Trees vs Random Forest

Therefore, trees ensemble methods are better than simple decision trees, but is an ensemble better than the other? Which one should I use? This post is going to try to answer these questions, studying the differences between the Extra Trees and Random Forest and comparing both of them in terms of results.

The two ensembles have a lot in common. Both of them are composed of a large number of decision trees, where the final decision is obtained taking into account the prediction of every tree. Specifically, by majority vote in classification problems, and by the arithmetic mean in regression problems. Furthermore, both algorithms have the same growing tree procedure (with one exception explained below). Moreover, when selecting the partition of each node, both of them randomly choose a subset of features.

So, the main two differences are the following:

These differences motivate the reduction of both bias and variance. On one hand, using the whole original sample instead of a bootstrap replica will reduce bias. On the other hand, choosing randomly the split point of each node will reduce variance.

In terms of computational cost, and therefore execution time, the Extra Trees algorithm is faster. This algorithm saves time because the whole procedure is the same, but it randomly chooses the split point and does not calculate the optimal one.

From these reasons comes the name of Extra Trees (Extremely Randomized Trees)

Comparison

In this section, we are going to compare the performance of the two algorithms. For that purpose, we are going to analyze the obtained results when using different datasets.

In order to generate these datasets, the function make_classification of the sklearn python library has been used. It has been chosen to use synthetic datasets instead of real ones because, in this way, the properties of the dataset can be tuned. Furthermore, this function allows us to select the number of features and their characteristics.

Therefore, this gives us the opportunity of analyzing the performance of the two algorithms in a classification problem, using datasets with different properties. In total, five datasets have been generated in which all of them have 1000 samples, 20 features, and 2 classes (binary classification). Moreover, 30% of the samples are assigned randomly. In this way, introducing noise make the classification harder. Moreover, the chosen differences between the features of the datasets are the following:

So, we can analyze if the two algorithms behave differently when having redundant, noisy, and repeated features.

Besides, the sklearn implementation of the two algorithms has been used. In addition, as for the parameters, the same number of estimators has been chosen, 100, leaving the rest of the parameters by default. Furthermore, cross-validation has been applied with K=3.

Results

The following table summarizes the obtained results comparing the F-Score and the execution time:

From the above results, we can see that results barely vary for the two algorithms. It seems that the Random Forest gets better results, but the difference is very small. As mentioned above, the variance of the Extra Trees is lower, but again, the difference is practically insignificant. It is remarkable that results vary more for datasets 4 and 5 where most of the features are redundant or repeated.

Moreover, as expected, Extra Trees is much faster. This is because instead of looking for the optimal split at each node it does it randomly.

Conclusions

In this post, we have studied the difference between Extra Trees and Random Forest algorithms, comparing the obtained results when applying them for different datasets.

In the comparison that has been made, the obtained results are practically the same for both algorithms. It is worth noting the difference in the execution time, where the Extra Trees is much faster. Therefore, if you have any doubt about which of the two ensembles to use, it seems a good idea to use Extra Trees since the same result is obtained in a faster way.

References

[1] Geurts, Pierre, Damien Ernst, and Louis Wehenkel. “Extremely randomized trees.” Machine learning 63.1 (2006): 3-42.

Источник

Random Forest: прогулки по зимнему лесу

1. Вступление

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

2. Несколько слов о деревьях

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

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

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

Следовательно, его визуальное представление будет таким:

Разумеется, каждый признак обладает разной степенью важности. Из следующего набора данных (формат LibSVM) видно, что первый признак (его индекс 1, так как нумерация начинается не с нуля) абсолютно идентичен у представителей всех классов. Фактически, этот показатель не имеет никакой ценности для классификации, следовательно, его можно назвать избыточной информацией, которая не несёт никакой практической пользы. Аналогичная ситуация и со вторым признаком (предиктором). Однако, третий из них отличается.

Именно третий признак (feature 2) и будет служить тем самым заветным различием, с помощью которого можно предсказывать класс по вектору. Логично предположить, что задача может быть решена одним единственным условием (If-Else). Действительно, каждое дерево в алгоритме машинного обучения правильно смогло понять различия. Далее показана отладочная информация (использован классификатор Random Forest из фреймворка Apache Spark 2.1.0) для нескольких деревьев ансамбля случайного леса.

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

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

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

3. Random Forest

По сути, Random Forest является композицией (ансамблем) множества решающих деревьев, что позволяет снизить проблему переобучения и повысить точность в сравнении с одним деревом. Прогноз получается в результате агрегирования ответов множества деревьев. Тренировка деревьев происходит независимо друг от друга (на разных подмножествах), что не просто решает проблему построения одинаковых деревьев на одном и том же наборе данных, но и делает этот алгоритм весьма удобным для применения в системах распределённых вычислений. Вообще, идея бэггинга, предложенная Лео Брейманом, хорошо подходит для распределения вычислений.

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

Так, например, если в задаче бинарной классификации была сформирована модель с 500 деревьями, среди которых 100 указывают на нулевой класс, а остальные 400 на первый класс, то в результате модель будет предсказывать именно первый класс. Если использовать Random Forest для задач регрессии, то подход выбора того решения, за которое проголосовало большинство деревьев будет неподходящим. Вместо этого происходит выбор среднего решения по всем деревьям.

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

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

Рассмотрим пример классификации на языке программирования R. Так как нам сейчас нужна классификационная модель, а не регрессионная, то в качестве первого параметра следует явно задать, что класс является именно фактором. Кроме количества деревьев уделим внимание числу признаков (mtry), которое будет использовать элементарная модель (дерево) для ветвлений. Фактически, это два основных параметра, которые есть смысл настраивать в первую очередь.

Убедимся, что это именно модель для классификации:

Ознакомимся с результатами confusion matrix:

Интересно увидеть предсказанные значения (на основе out-of-bag):

А функции varImpPlot и importance предназначены для отображения важности предикторов (ценности для точности работы классификатора).

Разумеется, для получения вероятного класса существует специальная функция. Она называется predict. В качестве первого аргумента требует модель, а в качестве второго — набор данных. Результатом будет вектор предсказанных классов. Для надёжной проверки необходимо выполнять тренировку на одном наборе данных, а проверку на другом наборе данных.

Ещё один пример. На этот раз используем Apache Spark 2.1.0 и язык программирования Scala. Информацию мы прочитаем из файла формата LibSVM. После этого необходимо будет явно разделить набор данных на две части. Одна из них будет учебная, а вторая — проверочная. Выполнять стандартизацию или нормализацию нет особого смысла. Наша модель устойчива к этому, равно как и достаточно устойчива к данным различной природы (вес, возраст, доход).

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

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

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

4. Несколько мыслей о практическом применении

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

Помню, несколько лет назад впервые столкнулся с необходимостью применения ML-технологий. Была ситуация, когда мы с коллегами (группа разработчиков) пытались придумать метод классификации материалов подробного справочника на очень большом портале. Раньше классификация выполнялась вручную другими специалистами, что требовало огромного количества времени. А вот автоматизировать никак не получалось (правила и статистические методы не дали нужной точности). У нас уже был набор векторов, который ранее разметили специалисты.

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

Таких примеров очень много. Расскажу ещё одну историю. Была задача повысить эффективность огромной системы управления рекламой. Её работа напрямую зависела от точности предсказания рейтинга товаров и услуг. У каждого из них был вектор из 64-ти признаков. Стратегически важно было заранее дать относительно точный прогноз значения рейтинга для каждого нового вектора признаков. До этого система управлялась нехитрыми правилами и описательной статистикой. Но, как известно, эффективности и точности в таких вопросах много не бывает. Для решения задачи повышения эффективности была использована регрессионная модель, похожая на указанную в примере:

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

Источник

Открытый курс машинного обучения. Тема 5. Композиции: бэггинг, случайный лес

Пятую статью курса мы посвятим простым методам композиции: бэггингу и случайному лесу. Вы узнаете, как можно получить распределение среднего по генеральной совокупности, если у нас есть информация только о небольшой ее части; посмотрим, как с помощью композиции алгоритмов уменьшить дисперсию и таким образом улучшить точность модели; разберём, что такое случайный лес, какие его параметры нужно «подкручивать» и как найти самый важный признак. Сконцентрируемся на практике, добавив «щепотку» математики.

Видеозапись лекции по мотивам этой статьи в рамках второго запуска открытого курса (сентябрь-ноябрь 2017).

План этой статьи

1. Бэггинг

Из прошлых лекций вы уже узнали про разные алгоритмы классификации, а также научились правильно валидироваться и оценивать качество модели. Но что делать, если вы уже нашли лучшую модель и повысить точность модели больше не можете? В таком случае нужно применить более продвинутые техники машинного обучения, которые можно объединить словом «ансамбли». Ансамбль — это некая совокупность, части которой образуют единое целое. Из повседневной жизни вы знаете музыкальные ансамбли, где объединены несколько музыкальных инструментов, архитектурные ансамбли с разными зданиями и т.д.

Ансамбли

Хорошим примером ансамблей считается теорема Кондорсе «о жюри присяжных» (1784). Если каждый член жюри присяжных имеет независимое мнение, и если вероятность правильного решения члена жюри больше 0.5, то тогда вероятность правильного решения присяжных в целом возрастает с увеличением количества членов жюри и стремится к единице. Если же вероятность быть правым у каждого из членов жюри меньше 0.5, то вероятность принятия правильного решения присяжными в целом монотонно уменьшается и стремится к нулю с увеличением количества присяжных.
— количество присяжных
— вероятность правильного решения присяжного
— вероятность правильного решения всего жюри
— минимальное большинство членов жюри,
— число сочетаний из по

Давайте рассмотрим ещё один пример ансамблей — «Мудрость толпы». Фрэнсис Гальтон в 1906 году посетил рынок, где проводилась некая лотерея для крестьян.
Их собралось около 800 человек, и они пытались угадать вес быка, который стоял перед ними. Бык весил 1198 фунтов. Ни один крестьянин не угадал точный вес быка, но если посчитать среднее от их предсказаний, то получим 1197 фунтов.
Эту идею уменьшения ошибки применили и в машинном обучении.

Бутстрэп

Bagging (от Bootstrap aggregation) — это один из первых и самых простых видов ансамблей. Он был придуман Ле́о Бре́йманом в 1994 году. Бэггинг основан на статистическом методе бутстрэпа, который позволяет оценивать многие статистики сложных распределений.

Метод бутстрэпа заключается в следующем. Пусть имеется выборка размера . Равномерно возьмем из выборки объектов с возвращением. Это означает, что мы будем раз выбирать произвольный объект выборки (считаем, что каждый объект «достается» с одинаковой вероятностью ), причем каждый раз мы выбираем из всех исходных объектов. Можно представить себе мешок, из которого достают шарики: выбранный на каком-то шаге шарик возвращается обратно в мешок, и следующий выбор опять делается равновероятно из того же числа шариков. Отметим, что из-за возвращения среди них окажутся повторы. Обозначим новую выборку через . Повторяя процедуру раз, сгенерируем подвыборок . Теперь мы имеем достаточно большое число выборок и можем оценивать различные статистики исходного распределения.

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

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

В итоге мы получили, что с 95% вероятностью среднее число звонков от лояльных клиентов будет лежать в промежутке между 1.40 и 1.50, в то время как наши бывшие клиенты звонили в среднем от 2.06 до 2.40 раз. Также ещё можно обратить внимание, что интервал для лояльных клиентов уже, что довольно логично, так как они звонят редко (в основном 0, 1 или 2 раза), а недовольные клиенты будут звонить намного чаще, но со временем их терпение закончится, и они поменяют оператора.

Бэггинг

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

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

и записать матожидание среднеквадратичной ошибки

Средняя ошибка построенных функций регрессии имеет вид

Предположим, что ошибки несмещены и некоррелированы:

Построим теперь новую функцию регрессии, которая будет усреднять ответы построенных нами функций:

Найдем ее среднеквадратичную ошибку:

Таким образом, усреднение ответов позволило уменьшить средний квадрат ошибки в n раз!

Напомним вам из нашего предыдущего урока, как раскладывается общая ошибка:

Бэггинг позволяет снизить дисперсию (variance) обучаемого классификатора, уменьшая величину, на сколько ошибка будет отличаться, если обучать модель на разных наборах данных, или другими словами, предотвращает переобучение. Эффективность бэггинга достигается благодаря тому, что базовые алгоритмы, обученные по различным подвыборкам, получаются достаточно различными, и их ошибки взаимно компенсируются при голосовании, а также за счёт того, что объекты-выбросы могут не попадать в некоторые обучающие подвыборки.

Ошибка дерева решений

По графику и результатам выше видно, что ошибка дисперсии намного меньше при бэггинге, как мы и доказали теоретически выше.

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

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

Out-of-bag error

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

Каждое дерево строится с использованием разных образцов бутстрэпа из исходных данных. Примерно 37% примеров остаются вне выборки бутстрэпа и не используются при построении k-го дерева.

Это можно легко доказать: пусть в выборке объектов. На каждом шаге все объекты попадают в подвыборку с возвращением равновероятно, т.е отдельный объект — с вероятностью Вероятность того, что объект НЕ попадет в подвыборку (т.е. его не взяли раз): . При получаем один из «замечательных» пределов . Тогда вероятность попадания конкретного объекта в подвыборку .

Давайте рассмотрим, как это работает на практике:

На рисунке изображена оценка oob-ошибки. Верхний рисунок – это наша исходная выборка, ее мы делим на обучающую(слева) и тестовую(справа). На рисунке слева у нас есть сетка из квадратиков, которая идеально разбивает нашу выборку. Теперь нужно оценить долю верных ответов на нашей тестовой выборке. На рисунке видно, что наш классификатор ошибся в 4 наблюдениях, которые мы не использовали для обучения. Значит, доля верных ответов нашего классификатора:

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

63% исходных объектов. Значит, на оставшихся

37% его можно сразу проверять. Out-of-Bag оценка — это усредненная оценка базовых алгоритмов на тех

37% данных, на которых они не обучались.

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

Лео Брейман нашел применение бутстрэпу не только в статистике, но и в машинном обучении. Он вместе с Адель Катлер усовершенстовал алгоритм случайного леса, предложенный Хо, добавив к первоначальному варианту построение некоррелируемых деревьев на основе CART, в сочетании с методом случайных подпространств и бэггинга.

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

Алгоритм

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

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

Рекомендуется в задачах классификации брать , а в задачах регрессии — , где — число признаков. Также рекомендуется в задачах классификации строить каждое дерево до тех пор, пока в каждом листе не окажется по одному объекту, а в задачах регрессии — пока в каждом листе не окажется по пять объектов.

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

Сравнение с деревом решений и бэггингом

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

Также можно увидеть преимущество случайного леса и бэггинга в задачах классификации.

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

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

Параметры

Метод случайного леса реализован в библиотеке машинного обучения scikit-learn двумя классами RandomForestClassifier и RandomForestRegressor.

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

Для задачи классификации все почти то же самое, мы приведем только те параметры, которыми RandomForestClassifier отличается от RandomForestRegressor

Далее рассмотрим несколько параметров, на которые в первую очередь стоит обратить внимание при построении модели:

Рассмотрим применение случайного леса в реальной задаче

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

Получили долю верных ответов 91.21%, теперь попробуем улучшить этот результат и посмотреть, как ведут себя кривые валидации при изменении основных параметров.

Начнем с количества деревьев:

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

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

В данном случае мы не выигрываем в точности на валидации, но зато можем сильно уменьшить переобучение до 2% при сохранении точности около 92%.

В нашем случае оптимальное число признаков — 10, именно с таким значением достигается наилучший результат.

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

Вариация и декорреляционный эффект

Давайте запишем дисперсию для случайного леса как

где и – случайно выбранная пара деревьев на случайно выбранных объектах выборки
— это выборочная дисперсия любого произвольно выбранного дерева:

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

По факту, условная ковариация пары деревьев равна 0, потому что бустрэп и отбор признаков — независимы и одинаково распределены.

Если рассмотреть дисперсию по одному дереву, то она практически не меняется от переменных для разделения (), а вот для ансамбля это играет большую роль, и дисперсия для дерева намного выше, чем для ансамбля.
В книге The Elements of Statistical Learning (Trevor Hastie, Robert Tibshirani и Jerome Friedman) есть отличный пример, который это демонстрирует.

Смещение

Как и в бэггинге, смещение в случайном лесе такое же, как и смещение в отдельно взятом дереве :

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

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

В сверхслучайных деревьях (Extremely Randomized Trees) больше случайности в том, как вычисляются разделения в узлах. Как и в случайных лесах, используется случайное подмножество возможных признаков, но вместо поиска наиболее оптимальных порогов, пороговые значения произвольно выбираются для каждого возможного признака, и наилучший из этих случайно генерируемых порогов выбирается как лучшее правило для разделения узла. Это обычно позволяет немного уменьшить дисперсию модели за счет несколько большего увеличения смещения.

В библиотеке scikit-learn есть реализация ExtraTreesClassifier и ExtraTreesRegressor. Данный метод стоит использовать, когда вы сильно переобучаетесь на случайном лесе или градиентном бустинге.

Схожесть случайного леса с алгоритмом k-ближайших соседей

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

Рассмотрим задачу регрессии с квадратичной функцией потерь. Пусть — номер листа -го дерева из случайного леса, в который попадает объект . Ответ объекта равен среднему ответу по всем объектам обучающей выборки, которые попали в этот лист . Это можно записать так

Тогда ответ композиции равен

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

Все в той же книге The Elements of Statistical Learning есть хороший наглядный пример сходства случайного леса и k-ближайших соседей.

Преобразование признаков в многомерное пространство

Все привыкли использовать случайный лес для задач обучения с учителем, но также есть возможность проводить обучение и без учителя. С помощью метода RandomTreesEmbedding мы можем сделать трансформацию нашего датасета в многомерное разреженное его представление. Его суть в том, что мы строим абсолютно случайные деревья, и индекс листа, в котором оказалось наблюдение, мы считаем за новый признак. Если в первый лист попал объект, то мы ставим 1, а если не попал, то 0. Так называемое бинарное кодирование. Контролировать количество переменных и также степень разреженности нашего нового представления датасета мы можем увеличивая/уменьшая количество деревьев и их глубины. Поскольку соседние точки данных скорее всего лежат в одном и том же листе дерева, преобразование выполняет неявную, непараметрическую оценку плотности.

3. Оценка важности признаков

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

Суть метода

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

Если построить много деревьев решений (случайный лес), то чем выше в среднем признак в дереве решений, тем он важнее в данной задаче классификации/регрессии. При каждом разбиении в каждом дереве улучшение критерия разделения (в нашем случае неопределенность Джини(Gini impurity)) — это показатель важности, связанный с переменной разделения, и накапливается он по всем деревьям леса отдельно для каждой переменной.

Давайте немного углубимся в детали. Среднее снижение точности, вызываемое переменной, определяется во время фазы вычисления out-of-bag ошибки. Чем больше уменьшается точность предсказаний из-за исключения (или перестановки) одной переменной, тем важнее эта переменная, и поэтому переменные с бо́льшим средним уменьшением точности более важны для классификации данных. Среднее уменьшение неопределенности Джини (или ошибки mse в задачах регрессии) является мерой того, как каждая переменная способствует однородности узлов и листьев в окончательной модели случайного леса. Каждый раз, когда отдельная переменная используется для разбиения узла, неопределенность Джини для дочерних узлов рассчитывается и сравнивается с коэффициентом исходного узла. Неопределенность Джини является мерой однородности от 0 (однородной) до 1 (гетерогенной). Изменения в значении критерия разделения суммируются для каждой переменной и нормируются в конце вычисления. Переменные, которые приводят к узлам с более высокой чистотой, имеют более высокое снижение коэффициента Джини.

А теперь представим все вышеописанное в виде формул.

— предсказание класса перед перестановкой/удалением признака
— предсказание класса после перестановки/удаления признака

Заметим, что , если не находится в дереве

Расчет важности признаков в ансамбле:
— ненормированные

Пример

Рассмотрим результаты анкетирования посетителей хостелов с сайтов Booking.com и TripAdvisor.com. Признаки — средние оценки по разным факторам (перечислены ниже) — персонал, состояние комнат и т.д. Целевой признак — рейтинг хостела на сайте.

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

4. Плюсы и минусы случайного леса

Плюсы:
— имеет высокую точность предсказания, на большинстве задач будет лучше линейных алгоритмов; точность сравнима с точностью бустинга
— практически не чувствителен к выбросам в данных из-за случайного сэмлирования
— не чувствителен к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков, связано с выбором случайных подпространств
— не требует тщательной настройки параметров, хорошо работает «из коробки». С помощью «тюнинга» параметров можно достичь прироста от 0.5 до 3% точности в зависимости от задачи и данных
— способен эффективно обрабатывать данные с большим числом признаков и классов
— одинаково хорошо обрабатывет как непрерывные, так и дискретные признаки
— редко переобучается, на практике добавление деревьев почти всегда только улучшает композицию, но на валидации, после достижения определенного количества деревьев, кривая обучения выходит на асимптоту
— для случайного леса существуют методы оценивания значимости отдельных признаков в модели
— хорошо работает с пропущенными данными; сохраняет хорошую точность, если большая часть данных пропущенна
— предполагает возможность сбалансировать вес каждого класса на всей выборке, либо на подвыборке каждого дерева
— вычисляет близость между парами объектов, которые могут использоваться при кластеризации, обнаружении выбросов или (путем масштабирования) дают интересные представления данных
— возможности, описанные выше, могут быть расширены до неразмеченных данных, что приводит к возможности делать кластеризацию и визуализацию данных, обнаруживать выбросы
— высокая параллелизуемость и масштабируемость.

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

5. Домашнее задание

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

В качестве закрепления материала предлагаем выполнить это задание – разобраться с бэггингом и обучить модели случайного леса и логистической регрессии для решения задачи кредитного скоринга. Проверить себя можно отправив ответы в веб-форме (там же найдете и решение).

6. Полезные источники

– Open Machine Learning Course. Topic 5. Bagging and Random Forest (перевод этой статьи на английский)
– Видеозапись лекции по мотивам этой статьи
– 15 раздел книги “Elements of Statistical Learning” Jerome H. Friedman, Robert Tibshirani, and Trevor Hastie
– Блог Александра Дьяконова
– Больше про практические применение случайного леса и других алгоритмов-композиций в официальной документации scikit-learn
– Курс Евгения Соколова по машинному обучению (материалы на GitHub). Есть дополнительные практические задания для углубления ваших знаний
– Обзорная статья «История развития ансамблевых методов классификации в машинном обучении» (Ю. Кашницкий)

Статья написана в соавторстве с yorko (Юрием Кашницким). Автор домашнего задания – vradchenko (Виталий Радченко). Благодарю bauchgefuehl (Анастасию Манохину) за редактирование.

Источник