Бутстрап-агрегирование

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

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

Описание техники

Учитывая стандартный обучающий набор размера n , пакетирование генерирует m новых обучающих наборов , каждый размером n' , путем равномерной выборки из D с заменой . Путем выборки с заменой некоторые наблюдения могут повторяться в каждом из них . Если n ′ = n , то при больших n ожидается, что в наборе будет доля (1 - 1/ e ) (≈63,2%) уникальных примеров D , остальные будут дубликатами. ^[1] Этот тип выборки известен как бутстрап- выборка. Выборка с заменой гарантирует, что каждый бутстрап независим от своих аналогов, поскольку он не зависит от предыдущих выбранных выборок при выборке. Затем m моделей подбираются с использованием m приведенных выше бутстрап-выборок и объединяются путем усреднения выходных данных (для регрессии) или голосования (для классификации). ${\displaystyle D}$ ${\displaystyle D_{i}}$ ${\displaystyle D_{i}}$ ${\displaystyle D_{i}}$

Иллюстрация концепции бутстрап-агрегирования

Бэггинг приводит к «улучшениям нестабильных процедур», ^[2] которые включают, например, искусственные нейронные сети , деревья классификации и регрессии , а также выбор подмножества в линейной регрессии . ^[3] Было показано, что упаковка в пакеты улучшает обучение прообразам. ^{[4] [5]} С другой стороны, это может слегка ухудшить производительность стабильных методов, таких как K-ближайшие соседи. ^[2]

Процесс алгоритма

Ключевые термины

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

Создание набора данных начальной загрузки

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

Предположим, исходный набор данных представляет собой группу из 12 человек. Их зовут Эмили, Джесси, Джордж, Константин, Лекси, Теодор, Джон, Джеймс, Рэйчел, Энтони, Элли и Джамал.

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

Создание готового набора данных

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

Важность

Создание наборов данных начальной загрузки и исходных данных имеет решающее значение, поскольку оно используется для проверки точности алгоритма случайного леса. Например, модель, которая создает 50 деревьев с использованием наборов данных начальной загрузки/из пакета, будет иметь лучшую точность, чем если бы она создавала 10 деревьев. Поскольку алгоритм генерирует несколько деревьев и, следовательно, несколько наборов данных, вероятность того, что объект останется вне набора данных начальной загрузки, невелика. В следующих нескольких разделах более подробно рассказывается о том, как работает алгоритм случайного леса.

Создание деревьев решений

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

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

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

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

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

Из-за своих свойств случайные леса считаются одним из наиболее точных алгоритмов интеллектуального анализа данных, с меньшей вероятностью переопределяют свои данные и работают быстро и эффективно даже для больших наборов данных. ^[6] Они в первую очередь полезны для классификации, а не для регрессии , которая пытается выявить наблюдаемые связи между статистическими переменными в наборе данных. Это делает случайные леса особенно полезными в таких областях, как банковское дело, здравоохранение, фондовый рынок и электронная коммерция, где важно иметь возможность прогнозировать будущие результаты на основе прошлых данных. ^[7] Одним из их применений может стать полезный инструмент для прогнозирования рака на основе генетических факторов, как видно из приведенного выше примера.

При проектировании случайного леса следует учитывать несколько важных факторов. Если деревья в случайных лесах расположены слишком глубоко, переобучение все равно может произойти из-за чрезмерной специфичности. Если лес слишком велик, алгоритм может стать менее эффективным из-за увеличения времени выполнения. Случайные леса также обычно неэффективны при наличии скудных данных с небольшой изменчивостью. ^[7] Тем не менее, они по-прежнему имеют многочисленные преимущества перед аналогичными алгоритмами классификации данных, такими как нейронные сети , поскольку их гораздо легче интерпретировать и, как правило, требуется меньше данных для обучения. ^{[ нужна цитата ]} Будучи неотъемлемым компонентом случайных лесов, бутстреп-агрегирование очень важно для алгоритмов классификации и обеспечивает критический элемент изменчивости, который позволяет повысить точность при анализе новых данных, как обсуждается ниже.

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

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

1. Укажите максимальную глубину деревьев: вместо того, чтобы позволять вашему случайному лесу продолжаться до тех пор, пока все узлы не станут чистыми, лучше отрезать его в определенной точке, чтобы еще больше уменьшить вероятность переобучения.
2. Сократите набор данных. Использование чрезвычайно большого набора данных может привести к получению результатов, которые менее показательны для предоставленных данных, чем меньший набор, который более точно представляет то, на чем сосредоточено внимание.
   • Продолжайте сокращать данные на каждом узле, а не только в исходном процессе упаковки.
3. Решите, точность или скорость: в зависимости от желаемых результатов может помочь увеличение или уменьшение количества деревьев в лесу. Увеличение количества деревьев обычно дает более точные результаты, а уменьшение количества деревьев дает более быстрые результаты.

Алгоритм (классификация)

Блок-схема алгоритма упаковки при использовании для классификации

Для классификации используйте обучающий набор , Inducer и количество бутстрап-выборок в качестве входных данных. Создайте классификатор в качестве вывода ^[12] ${\displaystyle D}$ ${\displaystyle I}$ ${\displaystyle m}$ ${\displaystyle C^{*}}$

1. Создание новых обучающих наборов с заменой ${\displaystyle m}$ ${\displaystyle D_{i}}$ ${\displaystyle D}$
2. Классификатор строится из каждого набора с использованием для определения классификации набора ${\displaystyle C_{i}}$ ${\displaystyle D_{i}}$ ${\displaystyle I}$ ${\displaystyle D_{i}}$
3. Наконец, классификатор генерируется с использованием ранее созданного набора классификаторов в исходном наборе данных . Классификация, прогнозируемая чаще всего подклассификаторами, является окончательной классификацией. ${\displaystyle C^{*}}$ ${\displaystyle C_{i}}$ ${\displaystyle D}$ ${\displaystyle C_{i}}$

для я = 1 до м { D' = бутстреп-выборка из D (выборка с заменой) Ci = I(D')}C*(x) = argmax #{i:Ci(x)=y} (чаще всего прогнозируемая метка y) yεY 

Пример: данные по озону

Чтобы проиллюстрировать основные принципы упаковки в мешки, ниже приводится анализ взаимосвязи между озоном и температурой (данные Руссеу и Лероя ^{[ необходимы пояснения ]} (1986), анализ выполнен в R ).

Судя по диаграмме рассеяния, в этом наборе данных взаимосвязь между температурой и озоном выглядит нелинейной. Для математического описания этой зависимости используются сглаживатели LOESS (с шириной полосы 0,5). Вместо построения одного сглаживателя для всего набора данных было взято 100 бутстрап- выборок. Каждая выборка состоит из случайного подмножества исходных данных и сохраняет подобие распределения и изменчивости основного набора. Для каждого образца бутстрепа подходил сглаживатель LOESS. Затем на основе этих 100 сглаживателей были сделаны прогнозы по всему диапазону данных. Черные линии представляют эти первоначальные прогнозы. Линии не согласуются в своих предсказаниях и имеют тенденцию переопределять свои точки данных, о чем свидетельствует шаткое течение линий.

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

Преимущества и недостатки

Преимущества:

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

Недостатки:

• Для слабого учащегося с высокой предвзятостью сбор также будет привносить высокую предвзятость в его совокупность ^[13].
• Потеря интерпретируемости модели.
• Может быть дорогостоящим в вычислительном отношении в зависимости от набора данных

История

Концепция бутстреп-агрегации основана на концепции бутстреп-агрегации, разработанной Брэдли Эфроном. ^[15] Бутстрап-агрегирование было предложено Лео Брейманом , который также ввёл сокращенный термин «бэггинг» ( bootstrap agg regating ) . Брейман разработал концепцию упаковки в 1994 году, чтобы улучшить классификацию путем объединения классификаций случайно сгенерированных обучающих наборов. Он утверждал: «Если возмущение обучающего набора может привести к значительным изменениям в построенном предикторе, то объединение в пакеты может повысить точность». ^[3]

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

• Бустинг (мета-алгоритм)
• Начальная загрузка (статистика)
• Перекрестная проверка (статистика)
• Ошибка «нет в сумке»
• Случайный лес
• Метод случайного подпространства (пакетирование атрибутов)
• Изменена эффективная граница
• Прогнозный анализ: деревья классификации и регрессии

Рекомендации

1. Аслам, Джавед А.; Попа, Ралука А.; и Ривест, Рональд Л. (2007); Об оценке размера и достоверности статистического аудита, Труды семинара по технологиям электронного голосования (EVT '07), Бостон, Массачусетс, 6 августа 2007 г. В более общем плане, при рисовании с заменой значений n' из набора n ( разные и одинаково вероятны), ожидаемое количество уникальных розыгрышей равно . ${\displaystyle n(1-e^{-n'/n})}$
2. Брейман, Лео (1996). «Предсказатели мешков». Машинное обучение . 24 (2): 123–140. CiteSeerX  10.1.1.32.9399 . дои : 10.1007/BF00058655. S2CID  47328136.
3. Брейман, Лео (сентябрь 1994 г.). «Предсказатели мешков» (PDF) . Технический отчет (421). Статистический факультет Калифорнийского университета в Беркли . Проверено 28 июля 2019 г.
4. Саху, А., Рангер, Г., Апли, Д., Шумоподавление изображений с помощью многофазного подхода основных компонентов ядра и ансамблевой версии, Семинар по распознаванию образов прикладных изображений IEEE, стр. 1–7, 2011.
5. Шинде, Амит, Аншуман Саху, Дэниел Апли и Джордж Рангер. «Прообразы для вариационных шаблонов из ядра PCA и упаковки». ИИЭ Сделки, Том 46, Выпуск 5, 2014
6. «Случайные леса - описание классификации» . stat.berkeley.edu . Проверено 9 декабря 2021 г.
7. «Введение в случайный лес в машинном обучении». Программа инженерного образования (EngEd) | Раздел . Проверено 9 декабря 2021 г.
8. «Плюсы и минусы случайного леса» . HolyPython.com . Проверено 26 ноября 2021 г.
9. К, Дирадж (22 ноября 2020 г.). «Преимущества и недостатки алгоритма случайного леса». Середина . Проверено 26 ноября 2021 г.
10. Команда, На пути к ИИ. «Зачем выбирать случайный лес, а не деревья решений – На пути к искусственному интеллекту – ведущее в мире издание по искусственному интеллекту и технологиям» . Проверено 26 ноября 2021 г.
11. «Случайный лес». Институт корпоративных финансов . Проверено 26 ноября 2021 г.
12. Бауэр, Эрик; Кохави, Рон (1999). «Эмпирическое сравнение алгоритмов классификации голосования: объединение, повышение и варианты». Машинное обучение . 36 : 108–109. дои : 10.1023/А:1007515423169 . S2CID  1088806.
13. «Что такое пакетирование (агрегация начальной загрузки)?». КФИ . Институт корпоративных финансов . Проверено 5 декабря 2020 г.
14. Зогни, Рауф (5 сентября 2020 г.). «Бэггинг (бутстрап-агрегирование), обзор». Стартап – через Medium.
15. Эфрон, Б. (1979). «Методы начальной загрузки: еще один взгляд на складной нож». Анналы статистики . 7 (1): 1–26. дои : 10.1214/aos/1176344552 .

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

• Брейман, Лео (1996). «Предсказатели мешков». Машинное обучение . 24 (2): 123–140. CiteSeerX  10.1.1.32.9399 . дои : 10.1007/BF00058655. S2CID  47328136.
• Альфаро Э., Гамес М. и Гарсия Н. (2012). «adabag: пакет R для классификации с помощью AdaBoost.M1, AdaBoost-SAMME и Baging». {{cite journal}}: Требуется цитировать журнал |journal=( помощь )CS1 maint: multiple names: authors list (link)
• Коциантис, Сотирис (2014). «Варианты объединения и повышения качества для решения проблем классификации: обзор». Знания англ. Обзор . 29 (1): 78–100. дои : 10.1017/S0269888913000313. S2CID  27301684.
• Бёмке, Брэдли; Гринвелл, Брэндон (2019). «Бэггинг». Практическое машинное обучение с помощью R . Чепмен и Холл. стр. 191–202. ISBN 978-1-138-49568-5.