Статья рассматривает сложности обучения моделей на несбалансированных данных и представляет метод Synthetic Minority Over-sampling Technique (SMOTE) в качестве решения

В этой статье мы обсуждаем, почему проблематично подобрать модели к несбалансированным наборам данных и как обычно решают проблему дисбаланса классов. Мы представляем внутреннюю работу алгоритма SMOTE и показываем простую реализацию SMOTE «с нуля». Мы используем искусственно созданный набор данных о дисбалансе (на основе Iris) для генерации синтетических наблюдений с помощью нашей реализации SMOTE и обсуждаем модификации, которые помогают SMOTE обрабатывать категориальные атрибуты.

Алгоритмам машинного обучения часто приходится обрабатывать сильно несбалансированные наборы данных. Когда мы говорим, что набор классификационных данных несбалансирован, мы обычно имеем в виду, что различные классы, включенные в набор данных, представлены неравномерно. Например, набор данных для обнаружения мошенничества часто может иметь соотношение 100:1, поскольку количество мошеннических транзакций относительно невелико по сравнению с количеством законных платежей. Еще более высокая асимметрия наблюдалась в других областях. Например, задачи классификации физики высоких энергий могут иметь отношение фона к сигналу 100 000:1 (Clearwater and Stern, 1991). Идентичные проблемы встречаются при классификации белков, где количество белков в одном классе часто намного меньше, чем количество белков вне класса (Zhao et al., 2008). Кроме того, несбалансированные данные усугубляют проблемы, возникающие из-за проклятия размерности, часто встречающегося в таких биологических данных.

Работа с сильно несбалансированными данными может быть проблематичной по нескольким причинам:

• Искаженные показатели производительности . В сильно несбалансированном наборе данных, скажем, в двоичном наборе данных с соотношением классов 98:2, алгоритм, который всегда предсказывает класс большинства и полностью игнорирует класс меньшинства, все равно будет на 98% правильным. Это делает бессмысленными такие меры, как точность классификации. Это, в свою очередь, затрудняет оценку производительности классификатора, а также может навредить обучению алгоритма, стремящегося к максимальной точности.
• Недостаточно данных для обучения в классе меньшинства . В областях, где сбор данных обходится дорого, набор данных, содержащий 10 000 примеров, обычно считается довольно большим. Однако если набор данных несбалансирован с соотношением классов 100:1, это означает, что он содержит только 100 примеров класса меньшинства. Этого количества примеров может быть недостаточно для того, чтобы алгоритм классификации установил хорошую границу решения, и может привести к плохому обобщению.

Рисунок 1: Сбалансированные и несбалансированные наборы данных. Левая часть: сбалансированный двоичный набор данных, который содержит примерно равное количество наблюдений двух своих классов (мужчин и женщин); правая часть: несбалансированный набор данных, в котором соотношение законных и мошеннических транзакций составляет 100:1.

Исторически классовый дисбаланс решался посредством недостаточной выборки, суть которой сводится к отбрасыванию наблюдений класса большинства. Это можно сделать наивно, выбрав случайным образом количество наблюдений из класса большинства, идентичное количеству наблюдений в классе меньшинства. Объединение этих двух результатов дает полностью сбалансированный набор данных (50:50). Проблема с этим подходом заключается в том, что в сильно несбалансированных наборах он может легко привести к ситуации, когда большую часть данных придется отбросить, и твердо установлено, что, когда дело доходит до машинного обучения, данные не следует легко выбрасывать (Банко и Брилл, 2001; Халеви и др., 2009). Другие методы включают простую повторную выборку, при которой класс меньшинства непрерывно отбирается до тех пор, пока количество полученных наблюдений не совпадет с размером класса большинства, и целенаправленную недостаточную выборку, когда отброшенные наблюдения из класса большинства тщательно отбираются для последующего использования. от границы решения (Япкович, 2000). Также было показано, что некоторые из рассматриваемых методов можно комбинировать — например, Линг и Ли (1998) демонстрируют одновременную заниженную выборку большинства и завышенную выборку меньшинства. Однако представляется, что, хотя недостаточная выборка класса большинства приводит к лучшим результатам, чем повторная выборка меньшинства, объединение двух методов не приводит к значительным улучшениям.

Генерация искусственных примеров

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

Вот упрощенная версия алгоритма SMOTE:

import random import pandas as pd import numpy as np from sklearn.neighbors import NearestNeighbors from random import randrange def get_neigbours(M, k): nn = NearestNeighbors(n_neighbors=k+1, metric="euclidean").fit(M) dist, indices = nn.kneighbors(M, return_distance=True) return dist, indices def SMOTE(M, N, k=5): t = M.shape[0] # number of minority class samplesnumattrs = M.shape[1] N = int(N/100) _, indices = get_neigbours(M, k) synthetic = np.empty((N * t, numattrs)) synth_idx = 0 for i in range(t): for j in range(N): neighbour = randrange(1, k+1) diff = M[indices[i, neighbour]] - M[i] gap = random.uniform(0, 1) synthetic[synth_idx] = M[i] + gap*diff synth_idx += 1 return synthetic

Алгоритм принимает три обязательных аргумента — список наблюдений меньшинства (M, массив Numpy), требуемый объем передискретизации (N) и количество ближайших соседей для рассмотрения (k). Обратите внимание, что значение N интерпретируется как проценты, поэтому передискретизация N = 100 приведет к получению количества синтетических наблюдений, которое соответствует количеству наблюдений в M. N = 200 дает удвоенное количество наблюдений в M и так далее. Обратите внимание, что исходный алгоритм не предписывает определенной процедуры выбора ближайших соседей. Здесь мы используем kNN на основе Евклида, но это не является жестким требованием.

Рисунок 2: Несбалансированный набор данных на основе радужной оболочки Фишера (Fisher, 1936) — шесть наблюдений класса 0 были выбраны случайным образом, и все наблюдения класса 1 остались нетронутыми. Соотношение меньшинства и большинства составляет 12:100.

Давайте рассмотрим случайную несбалансированную выборку набора данных Iris (рис. 2), где рассматриваются только два целевых класса. Класс меньшинства содержит только 6 наблюдений, но мы можем повысить его выборку с помощью SMOTE и получить полностью сбалансированный набор данных, в котором классы 0 и 1 содержат одинаковое количество выборок. На рисунке 3 показано наглядное объяснение того, как в этом случае SMOTE генерирует синтетические наблюдения.

Рисунок 3. Генерация синтетических наблюдений для одного члена класса меньшинства. Начните с класса меньшинства (3a) и выберите члена случайным образом (3b). Определите его k-ближайших соседей (3c). Поместите новое наблюдение между элементом и каждым из его соседей. Конкретное расстояние каждого синтетического наблюдения от выбранного члена меньшинства выбирается случайным образом (3d).

Алгоритм перебирает каждое наблюдение в классе меньшинства. После выбора наблюдения меньшинства SMOTE идентифицирует его k ближайших соседей и случайным образом выбирает набор соседей, которые будут использоваться в процессе генерации. Обратите внимание, что количество используемых соседей зависит от требуемой степени передискретизации. Например, если k = 3 и N = 100, понадобится только один случайно выбранный сосед. Если N = 200, будут выбраны два случайных соседа. В случае, когда ?N/100? > k, SMOTE выполнит выборку набора соседей с заменой, поэтому один и тот же сосед будет использоваться несколько раз.

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

После того, как соседи выбраны, алгоритм учитывает разницу между вектором признаков члена меньшинства и отдельных соседей. Затем каждая разница умножается на случайное число в (0, 1) и добавляется обратно в вектор признаков. При этом создаются синтетические наблюдения в направлении каждого члена, которые расположены на случайном расстоянии от члена меньшинства. Обратите внимание, что из-за случайного характера расчета расстояния повторные итерации с использованием одной и той же комбинации член меньшинства – ближайший сосед по-прежнему дают разные синтетические наблюдения (см. Рисунок 4).

Рисунок 5 : Результаты повышения выборки с помощью SMOTE для N = 100 (слева) и N = 600 (справа). Синтетические наблюдения окрашены в пурпурный цвет. Установка N равным 100 дает количество синтетических наблюдений, равное количеству выборок класса меньшинства (6). Установка N равным 600 приводит к 6 x 6 = 36 новым наблюдениям.

На рисунке 5 показаны результаты выполнения SMOTE для класса меньшинства с k = 5 и значениями N, установленными на 100 и 600. Проверка графика показывает, что все синтетические наблюдения лежат вдоль линии, соединяющей две выборки меньшинства. Это очень узнаваемая характеристика повышающей дискретизации на основе SMOTE. Кроме того, интуитивное понимание того, почему повышение выборки дает преимущество, можно объяснить тем фактом, что большее количество наблюдений в классе меньшинства приводит к более широкой границе принятия решений. Изучение более широких регионов улучшает обобщение классификатора, поскольку регион класса меньшинства не так жестко ограничен наблюдениями большинства.
Чавла и др. (2002) провели всестороннюю оценку влияния повышения выборки на основе SMOTE. Они демонстрируют, что сочетание повышения выборки меньшинства с понижением выборки большинства дает наилучшие результаты. Их тесты выполняются с использованием деревьев решений, сгенерированных C4.5 (Quinlan, 1993), сопоставленных с десятью различными несбалансированными наборами данных (например, индийский диабет Пима (Smith et al., 1988), данные E-state (Hall et al., 1991), набор данных по нефти (Кубат и др., 1998) и др.). Производительность комбинации C4.5, повышающей выборки SMOTE и мажоритарной понижающей выборки оценивается по сравнению с двумя другими классификаторами. Первый — это наивный байесовский классификатор, в котором априорные значения корректируются с учетом дисбаланса классов. Второй — это классификатор на основе правил, оснащенный RIPPER2, который также хорошо подходит для наборов данных с несбалансированным распределением классов.

Рисунок 6: Повышение выборки с использованием SMOTE с k = 5 и N = 500. Синтетические наблюдения были объединены с шестью исходными выборками меньшинства, а новый набор данных с повышенной дискретизацией строится с использованием попарных диаграмм рассеяния для каждой возможной комбинации из четырех оригинальные атрибуты Iris.

Результаты показывают, что комбинация SMOTE-C4.5 неизменно превосходит два других классификатора — классификатор SMOTE-C4.5 не показал лучших результатов только в 4 из 48 проведенных экспериментов. Чавла и др. (2002) также объясняют, почему простая избыточная выборка с заменой работает хуже по сравнению с повышающей дискретизацией на основе SMOTE — простое повторение наблюдений меньшинства приводит к сокращению областей принятия решений, что является противоположностью того, что необходимо. для хорошего обобщения. С другой стороны, синтетическая повышающая дискретизация расширяет области принятия решений, что повышает производительность классификатора.

SMOTE и категориальные признаки

Одним из ограничений SMOTE является то, что он не может обрабатывать наборы данных, состоящие исключительно из категориальных признаков. Существует модификация алгоритма под названием «Техника синтетической избыточной выборки меньшинства — номинальный непрерывный» (SMOTE-NE), которая может обрабатывать выборки, которые имеют смесь непрерывных и категориальных признаков. Помимо стандартного SMOTE, SMOTE-NE также выполняет следующее:

1. Вычисление медианы — алгоритм вычисляет стандартное отклонение для всех непрерывных атрибутов в классе меньшинства, а затем вычисляет медианное значение стандартных отклонений;
2. Идентификация ближайшего соседа — метрика, используемая для выбора k-ближайших соседей, рассчитывается с использованием евклидова расстояния с добавленной поправкой на любые несовпадающие категориальные атрибуты. Для каждого категориального атрибута, который различается между выбранным членом меньшинства и потенциальным соседом, предварительно вычисленная медиана добавляется в качестве компонента к расчету евклидова расстояния;
3. Коррекция синтетической выборки — непрерывные характеристики синтетической выборки вычисляются с помощью стандартного SMOTE. Синтетические категориальные атрибуты задаются с использованием наиболее частых значений категориальных атрибутов k-ближайших соседей;

Чавла и др. (2002) приводят пример, иллюстрирующий изменения.

Пример 1. Пусть набор меньшинства содержит следующие наблюдения:

$$
O1 = {1,2,3,A,B,C}^T
O2 = {4,6,5,A,D,E}^T
O3 = {3, 5,6,A,B,K}^T $$

Пусть медиана стандартных отклонений непрерывных атрибутов равна (Med = SD(1,4,3), SD(2,6,5), SD(3,5,6)), а выбранный член меньшинства для этой итерации будет (O1). Тогда евклидово расстояние между (O1) и (O2) будет:

$$egin{equation*}
d(O1,O2) = sqrt{(4-1)^2 + (6-2)^2 + (5-3)^2 + Med^2 + Med^2}
end{equation*}$$

Медианная поправка применяется дважды для двух категориальных атрибутов, которые различаются между (O1) и (O2), а именно: (B ightarrow D), (C ightarrow E). Расстояние между (O1) и (O3) рассчитывается одинаково как:

$$egin{equation*}
d(O1,O3) = sqrt{(3-1)^2 + (5-2)^2 + (6-3)^2 + Med^2}
end{equation *}$$

с единственной поправкой на изменение (C ightarrow K).

Слово предостережения. Чавла и др. (2002) не представили строгого математического объяснения этой модификации, и предлагаемая медианная поправка, по-видимому, является чисто эмпирической. Это сопряжено с риском того, что эта модификация будет работать хуже, чем более простые подходы, такие как занижение выборки большинства. Действительно, в оригинальной статье Chawla et al. обратите внимание, что этот вариант «работает хуже, чем простая заниженная выборка на основе AUC» при тестировании на наборе данных для взрослых (Dua & Graff, 2017).

Другая модификация SMOTE, называемая SMOTE-N (для номинальных объектов), пытается обойти ограничение SMOTE-NE, согласно которому набор данных не может состоять только из категориальных объектов. Вариант SMOTE-N использует модифицированную версию метрики расстояния значения (VDM), которая была предложена Костом и Зальцбергом (1993) для алгоритмов ближайшего соседа, работающих в символических областях (т.е. признаки больше не числовые, а действительные расстояния). между наблюдениями все еще необходимы). Для набора данных, в котором все объекты являются категориальными, VDM вычисляет расстояние между двумя соответствующими значениями объектов (v1) и (v2) как

$$delta (v1, v2) = sum_{c=1}^C | p(c|v1_f) - p(c|v2_f) |^k, kin{1,2}$$

где (C) — количество классов в наборе данных, (p(c|v1_f)) — условная вероятность класса (c) при условии, что признак (f) имеет значение (v1 ), а (p(c|v2_f)) — условная вероятность класса (c) при условии, что признак (f) имеет значение (v2), а (k) — константа установлена на 1 (k=1 соответствует манхэттенскому расстоянию, k=2 соответствует евклидову расстоянию).

Расстояние между двумя наблюдениями (O1) и (O2) далее определяется как

$$Delta (O1, O2) = sum_{f=1}^{F} delta (O1_f, O2_f)^r, rin{1,2} ext{ (1)}$$

Пример 2 : Предположим, (mathcal{D}) — набор данных двоичной классификации, состоящий из следующих трех
наблюдений и соответствующих им классов.

$$O1 = {A,B,C,D,E,}^T, 0
O2 = {A,F,C,G,N,}^T, 0
O3 = { Ч,Б,С,Д,Н,}^Т, 1$$

Расстояние между (O1) и (O2) можно рассчитать как

$$egin{equation*}
egin{aligned}
Delta (O1, O2) & = sum_{f=0}^{F} delta (O1_f, O2_f)^1 = delta (A, A) + delta (B, F) + delta (C, C) + delta (D, G) + delta (E, N)
&= sum_{c=0}^1 | p(c|A_0) - p(c|A_0)|^1 + sum_{c=0}^1 | p(c|B_1) - p(c|F_1)|^1 + sum_{c=0}^1 | p(c|C_2) - p(c|C_2) |^1
&+ sum_{c=0}^1 | p(c|D_3) - p(c|G_3) |^1 + sum_{c=0}^1 | p(c|E_4) - p(c|N_4) |^1
end{aligned}
end{equation*}$$

Условную вероятность в (1) можно вычислить, используя тот факт, что

$$p(c|v_f) = |v_f|_c div |v_f|_mathcal{D}$$

где (|v_f|_c) — количество вхождений значения признака (v_f) для класса (c), а (|v_f|_mathcal{D}) — общее количество вхождений (v_f) в наборе данных. Затем мы можем получить попарные расстояния между объектами следующим образом:

$$egin{equation*}
egin{aligned}
delta (A, A) = sum_{c=0}^1 | p(c|A_0) - p(c|A_0) |^1 &= | |A|_0 div |A|_mathcal{D} - |A|_0 div |A|_mathcal{D} | + | |A|_1 div |A|_mathcal{D} - |A|_1 div |A|_mathcal{D} |
&= | 2 div 2 - 2 div 2 | + | 0 div 2 - 0 div 2 | = 0
delta (B, F) = sum_{c=0}^1 | p(c|B_1) - p(c|F_1) |^1 &= | |B|_0 div |B|_mathcal{D} - |F|_0 div |F|_mathcal{D} | + | |B|_1 div |B|_mathcal{D} - |F|_1 div |F|_mathcal{D} |
&= | 1 div 2 - 1 div 1 | + | 1 div 2 - 0 div 1 | = 1
end{aligned}
end{equation*}$$

Аналогично мы получаем

$$egin{equation*}
egin{aligned}
delta (C, C) &= | 2 div 3 - 2 div 3 | + | 1 div 3 - 1 div 3 | = 0
delta (D, G) &= | 1 div 2 - 1 div 1 | + | 1 div 2 - 0 div 1 | = 1
delta (E, N) &= | 1 div 1 - 1 div 2 | + | 0 div 1 - 1 div 2 | = 1
end{aligned}
end{equation*}$$

Окончательно

$$egin{equation*}
egin{aligned}
Delta (O1, O2) & = sum_{f=0}^{F} delta (O1_f, O2_f)^1 = delta (A, A) + delta (B, F) + delta (C, C) + delta (D, G) + delta (E, N)
&= 0 + 1 + 0 + 1 + 1 = 3
end{ выровнено}
end{equation*}$$

Аналогично (Delta (O1, O3) = 5) и (Delta (O2, O3) = 6). Обратите внимание: поскольку (delta) симметричен, также имеет место (Delta (O1, O2) = Delta (O2, O1)), (Delta (O2, O3) = Delta (O3, O2)) и т. д.

После выбора соответствующих (k) ближайших соседей через VDM, SMOTE-N создает новые наблюдения, просто принимая большинство голосов на основе соседей, чтобы получить значения для синтетического вектора признаков. Имейте в виду, что в оригинальной статье не приводится сравнение производительности SMOTE-N, поэтому не рекомендуется использовать его в качестве основного метода без изучения альтернативных подходов и оценки их производительности. Кроме того, в исходном описании SMOTE-N не обсуждается устранение ничьей в процессе голосования, однако простой эвристикой было бы случайно выбрать один из связанных вариантов.

Источник: domino.ai

Комментарии: