Алгоритмы сэмплирования

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

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

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

Неравномерное распределение может быть следующих типов:

• Недостаточное представление класса в переменной предикторе (независимой переменной);
• Недостаточное представление класса в критериальной переменной (зависимой).

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

Стратегии сэмплирования

• Cубдискретизация (англ. under-sampling) — удаление некоторого количество примеров мажоритарного класса.
• Передискретизации (англ. over-sampling) — увеличение количество примеров миноритарного класса.
• Комбинированние (англ. сombining over- and under-sampling) — последовательное применение субдискретизации и передискретизации.
• Ансамбль сбалансированных наборов (англ. ensemble balanced sets) — Создания ансамбля сбалансированных выборок путем итеративного применения субдискретизации к набору данных.

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

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

Примеры алгоритмов

Cубдискретизация (удаление примеров мажоритарного класса)

Случайное удаление примеров мажоритарного класса (англ. Random Undersampling)

Это самая простая стратегия. Для этого рассчитывается число K – количество мажоритарных примеров, которое необходимо удалить для достижения требуемого уровня соотношения различных классов. Затем случайным образом выбираются K мажоритарных примеров и удаляются. На рис. [math]1[/math] изображены примеры некоторого набора данных в двумерном пространстве признаков до и после использования алгоритма.

Поиск связей Томека (англ. Tomek Links)

Пусть примеры [math]E_i[/math] и [math]E_j[/math] принадлежат к различным классам, [math]d(E_i,E_j)[/math] – расстояние между указанными примерами. Пара [math](E_i,E_j)[/math] называется связью Томека, если не найдется ни одного примера [math]E_l[/math] такого, что будет справедлива совокупность неравенств:

[math] \begin{cases} d(E_i,E_l)\lt d(E_i,E_j),\\ d(E_j,E_l)\lt d(E_i,E_j) \end{cases} [/math]

Согласно данному подходу, все мажоритарные записи, входящие в связи Томека, должны быть удалены из набора данных. Этот способ хорошо удаляет записи, которые можно рассматривать в качестве «зашумляющих». На рис. [math]2[/math] визуально показан набор данных в двумерном пространстве признаков до и после применения стратегии поиска связей Томека.

Правило сосредоточенного ближайшего соседа (англ. Condensed Nearest Neighbor Rule)

Пусть [math]L[/math] – исходный набор данных. Из него выбираются все миноритарные примеры и (случайным образом) один мажоритарный. Обозначим это множество как [math]S[/math]. Все примеры из [math]L[/math] классифицируются по правилу одного ближайшего соседа. Записи, получившие ошибочную метку, добавляются во множество [math]S[/math] (рис. [math]3[/math]). Таким образом, мы будем учить классификатор находить отличие между похожими примерами, но принадлежащими к разным классам.

Односторонний сэмплинг (англ. One-side sampling, one-sided selection)

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

Правило «очищающего» соседа (англ. Neighborhood cleaning rule)

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

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

Передискретизации (увеличение числа примеров миноритарного класса)

Дублирование примеров миноритарного класса (англ. Oversampling)

Самый простой метод – это дублирование примеров миноритарного класса. В зависимости от того, какое соотношение классов необходимо, выбирается количество случайных записей для дублирования.

SMOTE (англ. Synthetic Minority Oversampling Technique)

Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность [math]d=X_b–X_a[/math], где [math]X_a\lt math\gt ,\lt math\gt X_b\lt math\gt – векторы признаков «соседних» примеров \lt math\gt a[/math] и [math]b[/math] из миноритарного класса. Их находят, используя алгоритм ближайшего соседа KNN. В данном случае необходимо и достаточно для примера [math]b[/math] получить набор из [math]k[/math] соседей, из которого в дальнейшем будет выбрана запись [math]b[/math]. Остальные шаги алгоритма KNN не требуются.

Далее из [math]d[/math] путем умножения каждого его элемента на случайное число в интервале [math](0, 1)[/math] получают [math]\hat{d}[/math]. Вектор признаков нового примера вычисляется путем сложения [math]X_a[/math] и [math]\hat{d}[/math]. Алгоритм SMOTE позволяет задавать количество записей, которое необходимо искусственно сгенерировать. Степень сходства примеров [math]a[/math] и [math]b[/math] можно регулировать путем изменения числа ближайших соседей [math]k[/math]. На рис. [math]4[/math] схематично изображено то, как в двумерном пространстве признаков могут располагаться искусственно сгенерированные примеры.

Реализации

Большинство рассмотренных алгоритмов реализованы в

См. также

• %%%%%%%%%%%%%%%%%%%%%%%%5
• %%%%%%%%%%%%%%%%%%%%%%%%%%%%%