Геометрический подход варианта SMOTE
На графике выше очевидно, что красные точки составляют большинство, а зеленые - меньшинство. Наличие данных меньшинства имеет решающее значение для изучения обнаружения аномалий, атак и вторжений, медицинской области [прогнозирование рака] и киберфизических настроек. Но количество присутствия меньшинства в выборке данных имеет решающее значение. Скажем, если имеется только 0,01% полезных данных меньшинства, обычно алгоритмы будут рассматривать это как шум или аномалию и будут пытаться повысить точность, игнорируя это. Как упоминалось выше, во многих случаях важно не учитывать выборки данных меньшинств, чем их удаление или игнорирование из-за их недопредставленности.
Обычные алгоритмы машинного обучения работают лучше всего, когда количество образцов классов примерно одинаково и часто согласовано с целью повышения точности и минимизации ошибок [1]
Следовательно, исходя из этого утверждения, необходимо обрабатывать дисбаланс данных, поскольку алгоритмы работают лучше, когда данные почти сбалансированы, и существует множество способов, которыми технический мир справляется с этим распространенным явлением.
Обработка несбалансированных данных
Мы можем решить эту тривиальную проблему машинного обучения несбалансированных данных с помощью алгоритмов и фреймворков, которые в целом распадаются на две основные области; Предварительная обработка и обучение с учетом затрат. Повторная выборка и выбор признаков - основные способы методологии предварительной обработки.
Повторная выборка данных:
Эта методология изменяет количество выборок данных и, таким образом, устраняет неблагоприятные последствия асимметричного распределения классов или несбалансированных данных.
- Передискретизация: передискретизация добавляет больше копий класса меньшинства. Передискретизация может быть хорошим выбором, когда у вас мало данных для работы. Но чрезмерная передискретизация может привести к чрезмерной подгонке. Но мы никогда не теряем полезную информацию или функции.
- Недостаточная выборка: недостаточная выборка - это удаление копий большинства классов. Недостаточная выборка может возникнуть при наличии огромного набора данных. Но главная проблема здесь в том, что мы удаляем ценную информацию. Это может привести к недостаточной подгонке и плохому обобщению тестового набора.
- Гибрид: правильное сочетание передискретизации и недостаточной выборки.
- SMOTE: Техника, аналогичная передискретизации, но здесь мы синтезируем новые образцы данных меньшинства.
SMOTE
Алгоритм SMOTE был предложен Чавлой, Бойером, Холлом и Кегельмейером в 2002 году в качестве альтернативы случайной передискретизации. Идея синтетической техники передискретизации меньшинства (SMOTE) состоит в том, чтобы выполнить интерполяцию среди соседних экземпляров класса меньшинства. Задача SMOTE заключалась в том, чтобы преодолеть проблему чрезмерной подгонки путем случайной повторной выборки данных и перейти к обобщению. SMOTE может увеличивать количество экземпляров классов меньшинств, синтезируя новые образцы классов меньшинств в окрестности, тем самым помогая классификаторам улучшить обобщение.
SMOTE генерирует новые образцы меньшинства между экземплярами меньшинства. Рассмотрим две точки меньшинства, и алгоритм генерирует новую выборку меньшинства вдоль линии, соединяющей эти точки меньшинства. Это абстрактный вид алгоритма SMOTE.
k = nearest neighbours n = no. of samples to be generated based on Imbalanced Ratio.
Алгоритм SMOTE (k, n):
Шаг 1. Установите набор класса меньшинства A. Для каждого x принадлежит A найдите k-ближайших соседей x (вычислив евклидово расстояние между x и каждым другие меньшинства в наборе A)
A = {x1, x2,… xt} & k-ближайшие соседи x1 = {x6, x7,… xk} и т.п.
Шаг 2: для каждого x принадлежит A, выберите n точек меньшинства среди его k-ближайших соседей и они составляют множество A1.
A1 of x1= {x7,x4,…xn}
Шаг 3: для каждой точки p в A создайте новый образец
новая точка = p + rand (0, 1) * | p-x1 |
в котором rand (0, 1) представляет случайное число от 0 до 1
SMOTE по-прежнему является интересной работой, и многие исследовательские работы представили варианты SMOTE, которые имеют разные подходы к синтезу новых точек меньшинства по-своему. На оригинальную статью SMOTE цитируется более 5000 ссылок, и исследования по разработке расширений SMOTE все еще свежи. Borderline-SMOTE (Han et al., 2005), Safe-Level-SMOTE (Bunkhumpornpat et al., 2009), DBSMOTE (Bunkhumpornpat et al., 2012), ROSE (Menardi & Torelli, 2014), MWMOTE (Barua et al. ., 2014), MDO (Abdi & Hashemi, 2016), Geometric SMOTE (Георгиос Дузас и др., 2017) - довольно много примеров.
Мне показалось, что Geometric SMOTE интересен тем, как он использует геометрию для элегантной разработки решения, выявления и устранения потенциальных проблем, которые могут возникнуть. Хотя это и называется вариантом SMOTE, но не настоящим расширением. Он подражает основной идеологии синтеза новых образцов меньшинств. Геометрический SMOTE также является алгоритмом, основанным на этом принципе и интерполяции. Давайте углубимся в суть геометрического SMOTE.
Геометрический SMOTE
Существующий SMOTE и его варианты имеют различные проблемы, которые необходимо решить при синтезе образцов меньшинств, и Geometric SMOTE выявила проблемы, как показано ниже.
- Генерация шумных примеров
При синтезе новых сэмплов меньшинства существует более высокая вероятность синтеза конкретного сэмпла в пространстве мажоритарного кластера. Такие данные называются зашумленными точками. Они вписываются в кластер только как шум.
На приведенном выше Рис.3. зашумленный образец генерируется в результате выбора x’
в качестве ближайшей точки для применения SMOTE.
Существует еще одна возможность генерации зашумленных сэмплов из-за выбора точек. Здесь на рис.4. поскольку x
уже является зашумленной точкой, а выбранная также зашумлена, сгенерированный сэмпл также оказывается зашумленным.
Здесь на рис.5 выше. также путем случайного выбора x
и x’
сгенерированная точка хорошо попадает в основной кластер и приводит к формированию зашумленной выборки.
2. Генерация выборок, принадлежащих одним и тем же подкластерам, что приводит к переобучению и неправильному представлению.
Хотя здесь нет проблемы зашумленных выборок, генерация новых выборок, принадлежащих одному субкластеру меньшинства, вносит «внутрикластерный дисбаланс» и приводит к искаженному представлению исходных данных. А также создание новых образцов сильно плотных субкластеров привело бы к
Основные цели G-SMOTE
Smote после выявления потенциальных утечек определяет свои основные задачи по решению некоторых проблем и механизмы их решения.
- G-SMOTE хочет определить безопасную зону для синтеза новых точек. Это необходимо для того, чтобы не генерировать синтетические точки, которые будут зашумленными сэмплами.
- G-SMOTE хочет увеличить разнообразие генерируемых сэмплов класса меньшинства. Это предотвратит создание одного и того же подкласса сэмплов меньшинства, что приведет к асимметрии внутри кластера.
Параметры G-SMOTE
Smaj: набор образцов большинства классов.
Smin: набор образцов из представителей меньшинств.
N: общее количество синтетических образцов, которые будут созданы.
k: количество ближайших соседей.
α_trunc: коэффициент усечения с −1 ≤ α_trunc ≤ 1.
α_def: коэффициент деформации при 0 ≤ α_def ≤ 1.
α_sel: стратегия выбора соседей с α_sel ∈ n {меньшинство, большинство, вместе}
S_gen: Набор сгенерированных синтетических примеров. (Выход)
Алгоритм
Пожалуйста, обратитесь к статье G-SMOTE для получения полного алгоритма и объяснения. Здесь я хочу объяснить алгоритм на примерах и абстрагироваться.
1. Элементы Smin перемешиваются, и инициализируется пустой набор Sgen.
Smaj = {smaj1,smaj2,smaj3,.......} Smin = {smin1,smin2,smin3,........} -> after being shuffled Sgen = {}
2. Повторяйте, пока в Sgen не будет создано N экземпляров меньшинства:
N = 0 - Have to run the procedure till N number of samples are generated
2.1. Пусть x_center ∈ Smin выбранный экземпляр класса меньшинства из p компонентов.
- A minority point from Smin is chosen as the center of a geometric region x_center = smin1 - The order of choosing the minority point will be the order of shuffled data points and in case of N > size of Smin, continue to re-run from the beginning again.
2.2. Если α_sel = меньшинство:
In G-SMOTE algorithm they defined 3 neighbor selection strategies ; minority,majority and mixed. - Find the k nearest neighbors of x_center from the set of Smin k_nearest_neighbors = {smin6,smin5......} - randomly select x_surface from the k_nearest_neighbors x_surface = smin5 - Calculate a radius from the relation R ← d(x_center, x_surface)
2.3. Если α_sel = большинство:
- choose the nearest majority neighbor (from Smaj) of x_center x_surface = smaj3 - Calculate a radius from the relation R ← d(x_center, x_surface)
2.4. Если α_sel = смешанный:
- Find the k nearest neighbors of x_center from Smin. k_nearest_neighbors = {smin6,smin5......} - randomly choose one from k_nearest_neighbors smin6 - Calculate the euclidean distance dmin ← d(x_center, smin6) ---------------------------------------------------------------- - Find nearest majority neighbor of x_center from Smaj xmaj= smaj3 - Calculate the euclidean distance dmaj ← d(x_center, xmaj) ---------------------------------------------------------------- - Calculate a radius from the relation x_surface ← argmin (dmin, dmaj) R ← d(x_center, x_surface) ---------------------------------------------------------------- Note: Since d ≤ R ≤ dmaj; where d is distance from x_center to the generated sample => Generation of noisy samples is avoided
2.5. Создайте синтетический образец x_gen ← гипербол (центр = 0, радиус = 1)
hyberball: - function is meant for creating the e-sphere - e_sphere is generated on the surface of a unit hyper-sphere
2.6. Преобразуйте1 синтетический образец с помощью x_gen ← truncate (x_gen, x_center, x_surface, α_trunc).
Truncation: - defined with bit of complex mathematics. But intuitively tells us which side of the hyper-sphere to be truncated to secure a safe space to generate a minority sample. - When α_trunc > 0, the area that is opposite to the x_surface is truncated from the interior of the hyper-sphere. - When α_trunc < 0, the truncation occurs in the area that includes the x_surface point. - α_trunc value is generally -1 to 1. If it is -1.0, it truncates the exact semi-hyper sphere on the same side of surface point and truncates the opposite side of semi-hyper sphere if α_trunc equals 1.0
2.7. Преобразуйте2 синтетический образец, используя x_gen ← deform (xgen, xcenter, xsurface, α_def).
Deformation: - corresponds to the deformation of the hyper-sphere in to a hyper-spheroid - α_def relates the story of hyper-plane that to be chosen on which the new minority sample will be synthesized - α_def typically takes value 0 to 1 allowing the Deformation method to choose the proper plane to place generated sample.
2.8. Transform3 синтетический образец с помощью x_gen ← translate (xgen, xcenter, R).
Translation: - translation of the generated point by the x_center vector and the resealing by the value of the radius R - return (x_center + R * x_gen)
2.9. Добавьте сгенерированный сэмпл x_gen к набору сгенерированных сэмплов S_gen.
S_gen {x_gen} N = N+1
Спасибо, что дочитали G-SMOTE до этого момента. Блог предназначен для представления обзора проблем в SMOTE и его вариантах, алгоритма G-SMOTE и основных целей. Интересно увидеть недостатки и в алгоритме G-SMOTE, и давайте обсудим их в отдельном блоге.
использованная литература
[1] Джонсон, Дж. М., Хошгофтаар, Т. М. Опрос о глубоком обучении с классовым дисбалансом. J Big Data 6, 27 (2019). Https://doi.org/10.1186/s40537-019-0192-5
[2] Н. В. Чавла , К. В. Бойер , Л. О. Холл , В. П. Кегельмейер (2011). SMOTE: метод передискретизации синтетических меньшинств
[3] Дузас, Георгиос и Басао, Фернандо. (2017). Геометрический SMOTE: эффективная передискретизация для несбалансированного обучения за счет геометрического расширения SMOTE.
[4] Дж. Дузас и Ф. Бакао, «Geometric SMOTE - геометрически улучшенная замена для SMOTE», Информационные науки, т. 501. С. 118–135, 2019. Доступно: 10.1016 / j.ins.2019.06.007.
[5] Реализация G-SMOTE - https://github.com/AlgoWit/geometric-smote