Как работает регуляризация в решающих деревьях какие параметры мы штрафуем в данных алгоритмах

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

Шамаева, Д. Р. Деревья решения для задач построения рейтинга коммерческих банков / Д. Р. Шамаева. — Текст : непосредственный // Технические науки: проблемы и перспективы : материалы V Междунар. науч. конф. (г. Санкт-Петербург, июль 2017 г.). — Санкт-Петербург : Свое издательство, 2017. — С. 18-22. — URL: https://moluch.ru/conf/tech/archive/231/12434/ (дата обращения: 29.10.2023).

В настоящее время в рамках машинного обучения большое внимание уделяется непараметрическим методам кластеризации, регрессии и классификации, в частности различным деревьям решений. В основе любого дерева решения лежит принцип бинарного разделения объектов на две группы исходя из байесовского принципа, нахождение объекта в одном из листов наиболее вероятно. К таким методам относятся CART, CLOPE, Random Forest.

Random Forest — один из самых популярных алгоритмов машинного обучения, придуманные Лео Брейманом и Адель Катлер ещё в прошлом веке. Алгоритм сочетает в себе две основные идеи: метод бэггинга Бреймана, и метод случайных подпространств, предложенный Tin Kam Ho. Random Forest — это множество решающих деревьев. В задаче регрессии их ответы усредняются, в задаче классификации принимается решение голосованием по большинству. Все деревья строятся независимо по следующей схеме:

1. Выбирается подвыборка обучающей выборки случайного размера, по ней строится дерево (для каждого дерева — своя подвыборка).

2. Для построения каждого расщепления в дереве просматриваем наиболее частые ветви случайных признаков (для каждого нового расщепления — свои случайные признаки).

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

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

Рис. 1. Построение одного случайного дерева

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

Подведя итог всему вышесказанному, следует отметить достоинства метода:

‒ способность эффективно обрабатывать данные с большим числом признаков и классов;

‒ нечувствительность к масштабированию (и вообще к любым монотонным преобразованиям) значений признаков;

‒ одинаково хорошо обрабатываются как непрерывные, так и дискретные признаки;

‒ существуют методы построения деревьев по данным с пропущенными значениями признаков;

‒ существует методы оценивания значимости отдельных признаков в модели;

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

‒ робастный метод, так как робастные наблюдения уходят в отдельные листы дерева решений и не участвуют в формировании решающих правил;

‒ внутренняя оценка способности модели к обобщению;

‒ высокая параллезуемость и масштабируемость.

К недостаткам данного метода можно отнести большой размер получающихся моделей и склонность к переобучению моделей.

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

XGBoost (eXtreme Gradient Boosting Training) — один из многих открытых алгоритмов, реализующих градиентный бустинг. С точки зрения классификации бустинг деревьев решений считается одним из наиболее эффективных методов. Данный алгоритм строит модель в виде суммы деревьев:

(1)

где h0 — начальное приближение, v — параметр, регулирующий скорость обучения и влияние отдельных деревьев на всю модель, hj(x) — деревья решений.

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

(2)

(3)

предназначена для решения задач классификации на 2 класса.

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

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

Для реализации алгоритмов RandomForest [https://cran.r-project.org/web/packages/randomForest/randomForest.pdf] и XGBoost следует установить одноименные библиотеки.

Параметры для реализации метода случайного леса представлены в таблице 1.

Основные параметры для настройки алгоритма RandomForest

Параметр

Назначение

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

Если для анализа следует выбрать лишь некоторые строки, то данный параметр является вектором индексов этих строк

Функция, указывающая на тип обработки пропущенных наблюдений (встроенные обработки на языке R)

Матрица показателей или формула, указывающая объект для описания способа печати

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

Набор данных, состояний только из предикторов для тестового набора данных

Вектор-ответ для тестового набора данных

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

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

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

В качестве параметров модели зададим количество лесов равное 200, а также обеспечим подсчет важности факторов. Результаты построения модели представлены на рисунке 2.

Рис. 2. Параметры модели, проверка адекватности модели

Построенная модель на 84,24 % адекватно описывает текущие данные, а значит правомерным является использование ее для прогноза. На рисунке 3 представлен график оценки значимости факторов на итоговое ранжирование.

Рис. 3. Оценка значимости факторов на ранжирование банков

Как можем заметить, наиболее весомым признаками оказались «Средства акционеров (участников) (тыс.руб.)» и «процентная ставка по кредиту (%)», что не противоречит ранее полученным результатам.

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

Рис. 4. Результаты прогнозирования для ранжировки банков

Согласно полученным данным ОАО «Нико-Банк» следует отнести к 27 позиции, а ЗАО «РКБ», ОАО «Россельхозбанк», ПАО «Нота-Банк», ПАО «Росбанк» к 25, 4, 15 и 6 соответственно.

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

Исходя из того, что нами было задано число случайных деревьев равное 200, мы получили порядка 1000 решающих правил. Даже произведя отбор по частоте попадания объектов в конечные листы деревьев решений, все равно количество решающих правил для рассмотрения остается достаточно велико. Следовательно, мы столкнулись с недостатков модели, а именно с ее громоздкостью. Для того, чтобы решить возникшую проблему воспользуемся градиентным бустингом. Результаты оценки ошибки представлены на рисунке 5:

Рис. 5. Ошибка модели RandomForest после использования градиентного бустинга

Таким образом, адекватность построенной модели после применения XGBoosting значительно возросла.

Дружнов, П.Н., Золотых, Н.Ю., Половинкин, А. Н. Программная реализация алгоритма градиентного бустинга деревьев решений / П. Н. Дружнов, Н. Ю. Зотолых, А.Ню Половинкин // Вестник Нижегородского университета им. Н. И. Лобачевского, 2011.-№ 1.-С.193–200.
Дружнов, П.Н., Золотых, Н.Ю., Половинкин, А. Н. Реализация параллельного алгоритма предсказания в методе градиентного бустинга деревьев решений / П. Н. Дружнов, Н. Ю. Зотолых, А. Н. Половинкин // Вестник Южно-Уральского государственного университета. Серия: Математическое моделирование и программирование, 2011.-№ 37 (254).-С.82–89.
Дружнов, П. Н. Параллельная реализация алгоритма градиентного бустинга деревьев решений / П. Н. Дружнов // Вычислительные методы и программирование: новые вычислительные технологии, 2013.-№ 2 (28).-С.109–114.

Основные термины (генерируются автоматически): дерево, дерево решений, машинное обучение, параметр, случайный лес, CART, CLOPE, алгоритм построения, набор данных, тестовый набор данных.

Классификация, регрессия и другие алгоритмы Data Mining с использованием R

4.4 Ансамбли моделей: бэггинг, случайные леса, бустинг

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

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

Ансамбль из пяти линейных классификаторов: каждый сегмент пространства объектов отличается средними вероятностями предсказания классов (подробности см. Флах, 2015, с. 344)

Рисунок 4.14: Ансамбль из пяти линейных классификаторов: каждый сегмент пространства объектов отличается средними вероятностями предсказания классов (подробности см. Флах, 2015, с. 344)

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

4.4.1 Бэггинг и случайные леса

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

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

\[\hat_ = \left( f^1(x) + f^2(x) + \dots + f^B(x)\right) / B\]

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

Метод случайного леса (Random Forest) представляет собой дальнейшее улучшение бэггинга деревьев решений, которое заключается в устранении корреляции между деревьями. Как и в случае с бэггингом, мы строим несколько сотен деревьев решений по обучающим бутстреп-выборкам. Однако на каждой итерации построения дерева случайным образом выбирается \(m\) из \(p\) подлежащих рассмотрению предикторов и разбиение разрешается выполнять только по одной из \(m\) этих переменных.

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

Выбор малого значения m при построении случайного леса обычно будет полезным при наличии большого числа коррелирующих предикторов. Естественно, если случайный лес строится с использованием \(m = p\) , то вся процедура сводится к простому бэггингу.

Применим методы бэггинга и случайного леса к прогнозированию данных по обилию водорослей в реках разного типа (см. три предыдущих раздела). Поскольку бэггинг — это просто частный случай метода случайного леса, то мы можем использовать одну и ту же функцию randomForest() пакета randomForest для R. Бэггинг выполняется, если задать параметр mtry = ncol(x) :

load(file="algae.RData") # Загрузка таблицы algae - раздел 4.1

x as.data.frame(model.matrix(a1~ ., data = algae[, 1:12])[, -1]) library(randomForest) set.seed(101) randomForest(x, algae$a1, mtry = ncol(x))

## ## Call: ## randomForest(x = x, y = algae$a1, mtry = ncol(x)) ## Type of random forest: regression ## Number of trees: 500 ## No. of variables tried at each split: 15 ## ## Mean of squared residuals: 275.4992 ## % Var explained: 39.25

Как видно из полученных результатов, прогнозирование выполнялось по 500 деревьям, в которых было использовано только 40% исходных переменных. Оценить эффективность этой модели при перекрестной проверке можно с использованием функции train() из пакета caret :

set.seed(101) (bag.a1 train(x, algae$a1, preProc = c('center', 'scale'), method = 'rf', trControl = trainControl(method = "cv"), tuneGrid = expand.grid(.mtry = ncol(x))))

## Random Forest ## ## 200 samples ## 15 predictor ## ## Pre-processing: centered (15), scaled (15) ## Resampling: Cross-Validated (10 fold) ## Summary of sample sizes: 179, 181, 180, 180, 180, 180, . ## Resampling results: ## ## RMSE Rsquared ## 16.52067 0.4332375 ## ## Tuning parameter 'mtry' was held constant at a value of 15 ##

Модель случайного леса можно построить этой же процедурой, задав последовательность значений mtry для оптимизации:

set.seed(101) (ranfor.a1 train(x, algae$a1, preProc = c('center', 'scale'), method = 'rf', trControl = trainControl(method = "cv"), tuneGrid = expand.grid(.mtry = 2:10), importance = TRUE))

## Random Forest ## ## 200 samples ## 15 predictor ## ## Pre-processing: centered (15), scaled (15) ## Resampling: Cross-Validated (10 fold) ## Summary of sample sizes: 179, 181, 180, 180, 180, 180, . ## Resampling results across tuning parameters: ## ## mtry RMSE Rsquared ## 2 15.40795 0.4986732 ## 3 15.53822 0.4907074 ## 4 15.75865 0.4768690 ## 5 15.85763 0.4706729 ## 6 15.85864 0.4702870 ## 7 16.08860 0.4572620 ## 8 16.12184 0.4561278 ## 9 16.30819 0.4454158 ## 10 16.32886 0.4438528 ## ## RMSE was used to select the optimal model using the smallest value. ## The final value used for the model was mtry = 2.

Заметим, что бутстреп дает хорошую возможность провести специальную процедуру перекрестной проверки, называемую тестом по “наблюдениям, не попавшим в сумку” (out-of-bag observations). Поскольку ключевая идея бэггинга состоит в многократном построении моделей по наблюдениям из бутстреп-выборок, то каждое конкретное дерево строится на основе примерно двух третей всех наблюдений. Остальная треть наблюдений не используется в обучении, но вполне может быть использована для независимого тестирования: ошибка на таких оставшихся данных (out–of–bag error) является состоятельной оценкой ошибки на контрольной выборке (Джеймс и др., 2016).

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

varImpPlot(ranfor.a1$finalModel)

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

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

На рис. 4.15 приведены два показателя важности: %IncMSE основан на среднем снижении точности предсказания на оставшихся данных, а IncNodePurity — мера среднего увеличения “чистоты узла” дерева (node purity) в результате разбиения данных по соответствующей переменной. В случае деревьев регрессии чистота узла выражается через ошибку RSS .

Количество деревьев \(B\) не является критическим параметром при использовании бэггинга: очень большое значение \(B\) не приведет к переобучению. На практике обычно используется значение \(B\) , достаточно большое для стабилизации ошибки: в частности, как следует из графика на рис. 4.16, величина \(B = 100\) уже обеспечивает хорошее качество предсказаний в нашем примере (по умолчанию, \(B = 500\) ).

plot(ranfor.a1$finalModel, col = "blue", lwd = 2) plot(bag.a1$finalModel, col = "green", lwd = 2, add = TRUE) legend("topright", c("Bagging", "RandomForrest"), col = c("green","blue"), lwd = 2)

Зависимость ошибки на обучающей выборке от числа агрегируемых деревьев при бэггинге и использовании алгоритма

Рисунок 4.16: Зависимость ошибки на обучающей выборке от числа агрегируемых деревьев при бэггинге и использовании алгоритма “случайный лес”

4.4.2 Бустинг

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

Бутстреп-выборки в ходе реализации бустинга не создаются, но вместо этого каждое дерево строится по набору данных \(\) , который на каждом шаге модифицируется определенным образом. На первой итерации по значениям исходных предикторов строится дерево \(f^1(x)\) и находится вектор остатков \(r_1\) . На последующем этапе новое регрессионное дерево \(f^2(x)\) строится уже не по обучающим данным \(X\) , а по остаткам \(r_1\) предыдущей модели. Линейная комбинация прогноза по построенным деревьям дает нам новые остатки \(r_2 \leftarrow r_1 + \lambda f^2(x)\) , и этот итерационный процесс повторяется \(B\) раз. Благодаря построению неглубоких деревьев по остаткам, прогноз отклика медленно улучшается в областях, где одиночное дерево работает не очень хорошо. Такие деревья могут быть довольно небольшими, лишь с несколькими конечными узлами. Параметр сжатия \(\lambda\) регулирует скорость этого процесса, позволяя создавать комбинации деревьев более сложной формы для “атаки” остатков. Итоговая модель бустинга представляет собой ансамбль \(\hat(x) = \sum_^B \lambda f^b(x)\) .

В среде R для построения бустинг-моделей на основе деревьев решений можно использовать функцию gbm() из пакета gbm (Generalized Boosted Models). Процесс моделирования проходит под управлением трех гиперпараметров:

Число деревьев \(В\) (формальный параметр n.tree ). В отличие от бэггинга, бустинг может, хотя и медленно, приводить к переобучению при чрезмерно большом В.
Параметр сжатия \(\lambda\) (shrinkage), который корректирует величину вклада каждого дополнительного дерева и контролирует скорость, с которой происходит обучение модели при реализации бустинга. Типичные значения \(\lambda\) варьируют от 0.01 до 0.001, и их оптимальный выбор зависит от решаемой проблемы. Для достижения хорошего качества предсказаний очень низкие значения \(\lambda\) требуют очень большого значения \(B\) .
Число внутренних узлов \(d\) ( interaction.depth ) в каждом дереве, которое контролирует сложность получаемого в результате бустинга ансамбля моделей. По своей сути, параметр \(d\) отражает глубину взаимодействий между предикторами в итоговой модели. Если эти взаимодействия не слишком выражены, то хорошо работает \(d = 1\) , и тогда дополнительные деревья представляют собой просто “пни” (stump), т.е. содержат только один внутренний узел. В таком случае получаемый в результате бустинга ансамбль становится аддитивной моделью, поскольку каждый ее член представлен только одной переменной.

Тип решаемой задачи регулируется параметром distribution , который определяет оптимизируемую функцию:

для решения задач регрессии задается значение «gaussian» — квадратичный штраф, или «laplace» — штраф по абсолютной величине отклонения;
для задач бинарной классификации используют значение «bernoulli» — функция кросс-энтропии, или «adaboost» — экспоненциальный штраф.

Используем значение shrinkage = 0.001 , установленное функцией gbm() по умолчанию. Функция summary() в отношение этого метода выводит список предикторов и соответствующие им значения показателя важности:

library(gbm) set.seed(1) xd cbind(a1 = algae$a1, x) boost.a1 = gbm(a1 ~ ., data = xd, distribution = "gaussian", n.trees = 1000, interaction.depth = 3) summary(boost.a1, plotit = FALSE)

## var rel.inf ## oPO4 oPO4 28.46291329 ## NH4 NH4 24.40284599 ## PO4 PO4 20.25519899 ## Cl Cl 14.62528341 ## Chla Chla 4.78710908 ## mxPH mxPH 2.55817883 ## NO3 NO3 2.06210934 ## mnO2 mnO2 1.63005364 ## sizesmall sizesmall 0.70955559 ## speedmedium speedmedium 0.20058490 ## seasonwinter seasonwinter 0.13929129 ## speedlow speedlow 0.05886592 ## seasonsummer seasonsummer 0.04095099 ## sizemedium sizemedium 0.03617319 ## seasonspring seasonspring 0.03088555

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

pred = predict(boost.a1, x, n.trees = 1000) mean((pred - algae$a1)^2)

## [1] 232.8693

Выполним оптимизацию параметров построения градиентного бустинга с использованием функции train() . Как скаано выше, таких параметров три:

Принимая во внимание, что параметры shrinkag и n.trees связаны обратно пропорциональной зависимостью, уменьшим число деревьев до 50, одновременно увеличив значение shrinkage по сравнению с применяемыми выше:

(gbmFit.a1 train(a1 ~ ., data = xd, method = "gbm", trControl = trainControl(method = "cv"), tuneGrid = expand.grid(shrinkage = c(0.1,0.05,0.02), interaction.depth = 2:5, n.trees = 50, n.minobsinnode = 10), verbose = FALSE))

## Stochastic Gradient Boosting ## ## 200 samples ## 15 predictor ## ## No pre-processing ## Resampling: Cross-Validated (10 fold) ## Summary of sample sizes: 179, 180, 180, 179, 180, 180, . ## Resampling results across tuning parameters: ## ## shrinkage interaction.depth RMSE Rsquared ## 0.02 2 16.19348 0.5037032 ## 0.02 3 16.14000 0.5060133 ## 0.02 4 16.13229 0.5094717 ## 0.02 5 16.03985 0.5161377 ## 0.05 2 15.54586 0.4918096 ## 0.05 3 15.42194 0.4969380 ## 0.05 4 15.23162 0.5082960 ## 0.05 5 15.23295 0.5092289 ## 0.10 2 15.40549 0.4984676 ## 0.10 3 15.43270 0.5014440 ## 0.10 4 15.62864 0.4921172 ## 0.10 5 15.45538 0.4997536 ## ## Tuning parameter 'n.trees' was held constant at a value of 50 ## ## Tuning parameter 'n.minobsinnode' was held constant at a value of 10 ## RMSE was used to select the optimal model using the smallest value. ## The final values used for the model were n.trees = 50, interaction.depth ## = 4, shrinkage = 0.05 and n.minobsinnode = 10.

Бустинг деревьев регрессии может быть реализован также с использованием другого метода: с помощью функции bstTree() из пакета bst :

modelLookup("bstTree")

## model parameter label forReg forClass probModel ## 1 bstTree mstop # Boosting Iterations TRUE TRUE FALSE ## 2 bstTree maxdepth Max Tree Depth TRUE TRUE FALSE ## 3 bstTree nu Shrinkage TRUE TRUE FALSE

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

library(bst) (boostFit.a1 train(a1 ~ ., data = xd, method = 'bstTree', trControl = trainControl(method = "cv"), preProc = c('center', 'scale')))

## Boosted Tree ## ## 200 samples ## 15 predictor ## ## Pre-processing: centered (15), scaled (15) ## Resampling: Cross-Validated (10 fold) ## Summary of sample sizes: 180, 179, 180, 181, 180, 180, . ## Resampling results across tuning parameters: ## ## maxdepth mstop RMSE Rsquared ## 1 50 15.66507 0.4838143 ## 1 100 15.65839 0.4847449 ## 1 150 15.62656 0.4844995 ## 2 50 15.72647 0.4836585 ## 2 100 16.23836 0.4576188 ## 2 150 16.84847 0.4299882 ## 3 50 16.20853 0.4625459 ## 3 100 17.07712 0.4228308 ## 3 150 17.51597 0.4033881 ## ## Tuning parameter 'nu' was held constant at a value of 0.1 ## RMSE was used to select the optimal model using the smallest value. ## The final values used for the model were mstop = 150, maxdepth = 1 and ## nu = 0.1.

plot(boostFit.a1)

Зависимость ошибки от числа агрегируемых деревьев при бустинге (по результатам перекрестной проверки)

Рисунок 4.17: Зависимость ошибки от числа агрегируемых деревьев при бустинге (по результатам перекрестной проверки)

4.4.3 Тестирование моделей с использованием дополнительного набора данных

Используем для прогноза набор данных (Torgo, 2011) из 140 наблюдений, который мы уже применяли в предыдущем разделе. Данные, с восстановленными пропущенными значениями мы сохранили ранее в файле algae_test.RData (см раздел 4.1).

Выполним прогноз для набора предикторов тестовой выборки и оценим точность каждой модели по трем показателям: среднему абсолютному отклонению (MAE), корню из среднеквадратичного отклонения ( RSME ) и квадрату коэффициента детерминации Rsq = 1 — NSME , где NSME — относительная ошибка, равная отношению среднему квадрату отклонений от модельных значений и от общего среднего:

load(file = "algae_test.RData") # Загрузка таблиц Eval, Sols

y Sols$a1 EvalF as.data.frame(model.matrix(y ~ ., Eval)[, -1]) # Функция, выводящая вектор критериев ModCrit function(pred, fact) mean(abs(pred - fact)) rmse sqrt(mean((pred - fact)^2)) Rsq 1 - sum((fact - pred)^2)/sum((mean(fact) - fact)^2) c(MAE = mae, RSME = rmse, Rsq = Rsq) > Result rbind( bagging = ModCrit(predict(bag.a1, EvalF), Sols[, 1]), ranfor = ModCrit(predict(ranfor.a1, EvalF), Sols[, 1]), bst.gbm = ModCrit(predict(gbmFit.a1, EvalF), Sols[, 1]), bst.bst = ModCrit(predict(boostFit.a1, EvalF), Sols[, 1])) Result

## MAE RSME Rsq ## bagging 9.927347 14.44141 0.5031193 ## ranfor 9.962148 14.10063 0.5262930 ## bst.gbm 10.351657 14.79918 0.4781952 ## bst.bst 10.108705 14.67850 0.4866704

XGBoost

XGBoost [1] — одна из самых популярных и эффективных реализаций алгоритма градиентного бустинга на деревьях на 2019-й год.

История

XGBoost изначально стартовал как исследовательский проект Тяньцзи Чена (Tianqi Chen) как часть сообщества распределенного глубинного машинного обучения. Первоначально он начинался как терминальное приложение, которое можно было настроить с помощью файла конфигурации libsvm. После победы в Higgs Machine Learning Challenge, он стал хорошо известен в соревновательный кругах по машинному обеспечению. Вскоре после этого были созданы пакеты для Python и R, и теперь у него есть пакеты для многих других языков, таких как Julia, Scala, Java и т. д. Это принесло библиотеке больше разработчиков и сделало ее популярной среди сообщества Kaggle [2] , где она использовалось для большого количества соревнований. Программное обеспечение разработано по методологии SCRUM.

Она вскоре стала использоваться с несколькими другими пакетами, что облегчает ее использование в соответствующих сообществах. Теперь у нее есть интеграция с scikit-learn для пользователей Python, а также с пакетом caret для пользователей R. Она также может быть интегрирована в рамах потока данных, таких как Apache Spark [3] , Apache Hadoop [4] , и Apache Flink [5] с использованием абстрактных Rabit [6] и XGBoost4J [7] . Принцип работы XGBoost также был опубликован Тяньцзи Ченом (Tianqi Chen) и Карлосом Гастрин (Carlos Guestrin).

Описание алгоритма

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

Рассмотрим иллюстрацию бустинга. На ней рассматривается поведение модели на одной точке абстрактной задачи линейной регрессии. Предположим, что первая модель ансамбля [math]F[/math] всегда выдает выборочное среднее предсказываемой величины [math]f_0[/math] . Такое предсказание довольно грубое, поэтому среднеквадратичное отклонение на выбранной нами точке будет довольно большим. Мы попробуем это исправить обучив модель [math]\Delta_1[/math] , которая будет «корректировать» предсказание предыдущего ансамбля [math]F_0[/math] . Таким образом мы получим ансамбль [math]F_1[/math] , предсказание которого будет суммироваться из предсказаний моделей [math]f_0[/math] и [math]\Delta_1[/math] . Продолжая такую последовательность мы приходим к ансамблю [math]F_4[/math] предсказание которого суммируется из предсказаний [math]f_0[/math] , [math]\Delta_1[/math] , [math]\Delta_2[/math] , [math]\Delta_3[/math] , [math]\Delta_4[/math] и предсказывает в точности значение заданного таргета.

Математика за алгоритмом

[math]\mathcal^ = \sum_^n l(y_i,\hat^+f_t(x_i))+\Omega(f_t)[/math] — функция для оптимизации градиентного бустинга, где:

[math]l[/math] — функция потерь, см. Общие понятия.

[math]y_i, \hat^[/math] — значение i-го элемента обучающей выборки и сумма предсказаний первых t деревьев соответственно.

[math]x_i[/math] — набор признаков i-го элемента обучающей выборки.

[math]f_t[/math] — функция (в нашем случае дерево), которую мы хотим обучить на шаге t. [math]f_t(x_i)[/math] — предсказание на i-ом элементе обучающей выборки.

[math]\Omega(f)[/math] — регуляризация функции [math]f[/math] . [math]\Omega(f) = \gamma T + \frac \lambda \lVert w \rVert ^2[/math] , где T — количество вершин в дереве, [math]w[/math] — значения в листьях, а [math]\gamma[/math] и [math]\lambda[/math] — параметры регуляризации.

Дальше с помощью разложения Тейлора до второго члена можем приблизить оптимизируемую функцию [math]\mathcal^[/math] следующим выражением:

[math]\mathcal^ = \sum_^n l(y_i,\hat^ + g_i f_t(x_i) + 0.5 h_i f_t^2(x_i)) + \Omega(f_t)[/math] , где

Поскольку мы хотим минимизировать ошибку модели на обучающей выборке, нам нужно найти минимум [math]\mathcal^[/math] для каждого t.

Минимум этого выражения относительно [math]f_t(x_i)[/math] находится в точке [math]f_t(x_i) = \frac[/math] .

Каждое отдельное дерево ансамбля [math]f_t(x_i)[/math] обучается стандартным алгоритмом. Для более полного описания см. Дерево решений и случайный лес.

Возможности XGBoost

Особенности модели

XGBoost поддерживает все возможности таких библиотек как scikit-learn с возможностью добавлять регуляризацию. Поддержаны три главные формы градиетного бустинга:

Стандартный градиентный бустинг с возможностью изменения скорости обучения(learning rate).
Стохастический градиентный бустинг [8] с возможностью семплирования по строкам и колонкам датасета.
Регуляризованный градиентный бустинг [9] с L1 и L2 регуляризацией.

Системные функции

Библиотека предоставляет систему для использования в различных вычислительных средах:

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

Особенности алгоритма

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

Различные стратегии обработки пропущенных данных.
Блочная структура для поддержки распараллеливания обучения деревьев.
Продолжение обучения для дообучения на новых данных.

Основные параметры

n_estimators — число деревьев.
eta — размер шага. Предотвращает переобучение.
gamma — минимальное изменение значения loss функции для разделения листа на поддеревья.
max_depth — максимальная глубина дерева.
lambda/alpha — L2/L1 регуляризация.

Для более полного описания параметров модели см. документацию [10] .

Поддерживаемые интерфейсы

Интерфейс командной строки (CLI).
C++ (язык, на котором написана библиотека).
Интерфейс Python, а также модель в Scikit-Learn.
R интерфейс, а также модель в пакете карета.
Julia.
JVM языки, такие как Java, Scala, и платформы, такие как Hadoop.

Пример использования с помощью библиотеки xgboost

from sklearn import datasets iris = datasets.load_iris() X = iris.data y = iris.target

Разделение датасета на обучающую/тестовую выборку.

from sklearn.cross_validation import train_test_split X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

Импорт XGBoost и создание необходимых объектов.

import xgboost as xgb dtrain = xgb.DMatrix(X_train, label=y_train) dtest = xgb.DMatrix(X_test, label=y_test)

Задание параметров модели.

param = < 'max_depth': 3, 'eta': 0.3, 'silent': 1, 'objective': 'multi:softprob', 'num_class': 3>num_round = 20

bst = xgb.train(param, dtrain, num_round) preds = bst.predict(dtest)

Определение качества модели на тестовой выборке.

import numpy as np from sklearn.metrics import precision_score best_preds = np.asarray([np.argmax(line) for line in preds]) print precision_score(y_test, best_preds, average='macro')

Как работает регуляризация в решающих деревьях какие параметры мы штрафуем в данных алгоритмах

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

Похожие статьи

Метод определения весов параметров из набора входящих.

Сравнительный анализ алгоритмов нейронной сети и деревьев.

Анализ эффективности применения методов классификации

Предсказание уходов пользователей сервиса с помощью.

Применение модели градиентного бустинга для прогнозирования.

Развитие машинного обучения в фармакологии

Контролируемые методы машинного обучения как средство.

Подход к систематическому выбору и обоснованию алгоритмов