Изменения

Перейти к: навигация, поиск

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

1036 байт добавлено, 02:43, 17 марта 2020
Нет описания правки
* '''Передискретизации''' (англ. ''over-sampling'') {{---}} увеличение количество примеров миноритарного класса.
* '''Комбинированние''' (англ. ''сombining over- and under-sampling'') {{---}} последовательное применение субдискретизации и передискретизации.
* '''Ансамбль сбалансированных наборов''' (англ. ''ensemble balanced sets'') {{---}} Создания ансамбля сбалансированных выборок путем итеративного применения субдискретизации к набору данныхансамбли классификаторов, использующие сэмплирование внутри.
Также все методы можно разделить на две группы: случайные (недетерминированные) и специальные (детерминированные).
=== Cубдискретизация (удаление примеров мажоритарного класса) ===
==== '''Случайное удаление примеров мажоритарного класса''' (англ. ''Random Undersampling'') ====
[[Файл:Random_undersampling.png|thumb|right|upright=1.7|Рис. <math>1</math>. Случайное удаление примеров мажоритарного класса]]
Это самая простая стратегия. Для этого рассчитывается число K – количество мажоритарных примеров, которое необходимо удалить для достижения требуемого уровня соотношения различных классов. Затем случайным образом выбираются K мажоритарных примеров и удаляются.
На рис. <math>1</math> изображены примеры некоторого набора данных в двумерном пространстве признаков до и после использования алгоритма.
==== '''Поиск связей Томека''' (англ. ''Tomek Links'') ====
[[Файл:Tomek_links.png|thumb|right|upright=1.7|Рисунок 2 – Удаление мажоритарных примеров, участвующих в связях Томека]]
Пусть примеры <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>2</math> визуально показан набор данных в двумерном пространстве признаков до и после применения стратегии поиска связей Томека.
==== '''Правило сосредоточенного ближайшего соседа''' (англ. ''Condensed Nearest Neighbor Rule'') ====
[[Файл:Condensed_nearest_neighbor_rule.png|thumb|right|upright=1.7|Рисунок 3 – Удаление примеров мажоритарного класса правилом сосредоточенного ближайшего соседа]]
Пусть <math>L</math> – исходный набор данных. Из него выбираются все миноритарные примеры и (случайным образом) один мажоритарный. Обозначим это множество как <math>S</math>. Все примеры из <math>L</math> классифицируются по правилу одного ближайшего соседа. Записи, получившие ошибочную метку, добавляются во множество <math>S</math> (рис. <math>3</math>).
Таким образом, мы будем учить классификатор находить отличие между похожими примерами, но принадлежащими к разным классам.
* получившие верную метку класса;
* являющиеся соседями миноритарных примеров, которые были неверно классифицированы.
==== Дополнительно Дополнительные ====
* Under-sampling with Cluster Centroids<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* NearMiss <math>(1 \And 2 \And 3)</math><ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
Самый простой метод – это дублирование примеров миноритарного класса. В зависимости от того, какое соотношение классов необходимо, выбирается количество случайных записей для дублирования.
==== '''SMOTE''' (англ. ''Synthetic Minority Oversampling Technique'') ====
[[Файл:Random_undersampling.png|thumb|right|upright=1.7|Рис. <math>1</math>. Случайное удаление примеров мажоритарного класса]]
Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность <math>d=X_b–X_a</math>, где <math>X_a</math>,<math>X_b</math> – векторы признаков «соседних» примеров <math>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> схематично изображено то, как в двумерном пространстве признаков могут располагаться искусственно сгенерированные примеры.
[[Файл:Random_undersampling.png|thumb|right|upright=1.7|Рис. <math>1</math>. Случайное удаление примеров мажоритарного класса]]
==== '''ASMO''' (англ. ''Adaptive Synthetic Minority Oversampling'') ====
[[Файл:Random_undersampling.png|thumb|right|upright=1.7|Рис. <math>1</math>. Случайное удаление примеров мажоритарного класса]]
Алгоритм ''SMOTE'' имеет недостаток в том, что «вслепую» увеличивает плотность примерами в области слабо представленного класса (рис. <math>5</math>). В случае, если миноритарные примеры равномерно распределены среди мажоритарных и имеют низкую плотность, алгоритм SMOTE только сильнее перемешает классы.
В качестве решения данной проблемы был предложен алгоритм адаптивного искусственного увеличения числа примеров миноритарного класса ''ASMO'':
# Сгенерировать искусственные записи в пределах отдельных кластеров на основе всех классов. Для каждого примера миноритарного класса находят <math>m</math> ближайших соседей, и на основе них (также как в ''SMOTE'') создаются новые записи.
Такая модификация алгоритма ''SMOTE'' делает его более адаптивным к различным наборам данных с несбалансированными классами. Общее представление идеи алгоритма показано на рис. <math>6</math>.
==== Дополнительно Дополнительные ====
* SMOTENC - SMOTE for Nominal Continuous<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* bSMOTE <math>(1 \And 2)</math> - Borderline SMOTE of types <math>1</math> and <math>2</math><ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
=== Комбинированние ===
* SMOTE <math>+</math> Tomek links<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* SMOTE <math>+ </math> ENN<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
=== Ансамбль классификаторов, использующие сэмплирование внутрисбалансированных наборов ===
* Easy Ensemble classifier<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Balanced Random Forest<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
302
правки

Навигация