Дисбаланс классов от SMOTE до SMOTE-NC и SMOTE-N

Class imbalance from SMOTE to SMOTE-NC and SMOTE-N

Исследование трех алгоритмов для решения проблемы несбалансированности классов

В предыдущей статье мы объяснили, как работают алгоритмы наивного случайного повторного выбора и случайного повторного выбора примеров (ROSE). Более важно то, что мы также определили проблему несбалансированности классов и произвели интуитивные решения для ее решения. Я настоятельно рекомендую ознакомиться с этой статьей, чтобы обеспечить ясное понимание несбалансированности классов.

В этой статье мы продолжим рассмотрение алгоритмов SMOTE, SMOTE-NC и SMOTE-N. Но перед этим стоит отметить, что два алгоритма, рассмотренные в предыдущей статье, соответствуют следующей структуре реализации:

1. Определите, как алгоритм берет данные, принадлежащие классу X, которому требуется Nx примеров, и вычисляет такие примеры путем повторного выбора
2. Исходя из некоторого гиперпараметра-отношения, вычислите количество точек, которые нужно добавить для каждого класса
3. Для каждого класса запустите алгоритм, а затем объедините все вновь добавленные точки вместе с исходными данными, чтобы сформировать окончательный набор данных, полученный путем повторного выбора

Для обоих алгоритмов случайного повторного выбора и ROSE также было верно, что для генерации Nx примеров для класса X алгоритм делает следующее:

• Выбирает Nx точек случайным образом с возвращением из данных, принадлежащих классу X
• Выполняет логику для каждой выбранной точки для генерации новой точки (например, репликация или размещение гауссиана, а затем выбор из него)

Остальные алгоритмы, которые мы рассмотрим в этой статье, также соответствуют этой же структуре.

• Как неопределенность принципа ограничивает анализ временных рядов?
• Геопространственная инженерия данных пространственный индексирование
• 5 навыков, которыми должны обладать все профессионалы в области маркетингового анализа и науки о данных сегодня

SMOTE (Synthetic Minority Oversampling Technique)

Таким образом, чтобы объяснить, что делает SMOTE, нам нужно ответить только на один вопрос: Какая логика выполняется для каждого из Nx случайно выбранных с повторением примеров из класса X, чтобы сгенерировать Nx новых примеров?

Ответ таков:

• Находим k-ближайших соседей данной точки (k – гиперпараметр алгоритма)
• Выбираем одного из них случайным образом
• Проводим отрезок прямой от точки к этому случайно выбранному соседу
• Случайным образом выбираем точку на этом отрезке
• Возвращаем ее в качестве новой точки

Математически,

• Если точка x_i имеет ближайших соседей z_i1, z_i2, …, z_ik
• И если j – случайное число из [1, k]
• И r – случайное число из [0, 1]

тогда для каждой точки x_i SMOTE генерирует новую точку x_i’, просто применяя:

Это действительно все, что делает алгоритм SMOTE. Из точки x_i перемещайтесь на расстояние r вдоль вектора z_ij — x_i и разместите новую точку.

Небольшое примечание состоит в том, что есть небольшая разница в том, как алгоритм работает по сравнению с тем, как алгоритм представлен в статье. В частности, авторы предполагают, что отношения являются целыми числами (и округляют их, если это не так). Если отношение для класса X является целым числом C, то для каждой точки в нем выбирается случайный сосед с повторением C раз, а затем применяется логика SMOTE, которую мы описали. На практике, когда SMOTE реализуется, обычно он обобщается для работы с числами с плавающей запятой, как мы описали, а именно, случайным образом выбираются Nx точек, а затем на каждую применяется SMOTE. Для целых отношений, таких как C=2, следует, что каждая точка в среднем выбирается дважды, и мы возвращаемся к исходному алгоритму. Это должно иметь смысл, так как это та же самая переходная стадия от повторного выбора с использованием целых отношений до случайного повторного выбора, которая была объяснена в предыдущей статье.

Эта анимация показывает, как меняются области принятия решений SVM при изменении отношения повторного выбора для класса versicolor на несбалансированном подмножестве набора данных Iris. Отношение здесь относительно размера класса-большинства. То есть, отношение 1,0 устанавливает Nx так, чтобы класс versicolor имел столько же примеров, сколько класс virginica.

Возможно, вы задаетесь вопросом, почему SMOTE может быть лучше, чем ROSE. В конце концов, логика генерации точек в SMOTE не была обоснована в статье, в то время как выборка из оценки P(x|y), как в ROSE, намного более рациональна и интуитивна. Одной из проблем может быть то, что получение хорошей оценки P(x|y) требует большого объема данных, однако мы знаем, что у миноритарных классов обычно мало данных. Если у нас нет большого объема данных, у нас есть два варианта:

1. Выбрать слишком маленькую ширину полосы, при которой мы вернемся к возможному переобучению, как в случае случайной пересборки
2. Выбрать слишком большую ширину, которая в крайнем случае эквивалентна просто равномерному добавлению случайных точек из пространства признаков (т.е. нереалистичных примеров)

Если подумать об этом, мы должны менее беспокоиться об этой проблеме в SMOTE. Если гиперплоскость, которая идеально разделяет данные, существует, то это решение по-прежнему существует после применения SMOTE. Фактически, способ, которым SMOTE генерирует точки, может привести к более линейной гиперповерхности, поэтому он кажется на гораздо меньшем риске вызвать переобучение модели.

SMOTE-NC (SMOTE-Nominal Continuous)

Хотя и ROSE, и SMOTE, кажется, предлагают значительное улучшение по сравнению с наивной случайной пересборкой, они имеют недостаток потери возможности обработки категориальных переменных, что не было проблемой для наивной случайной пересборки. Авторы SMOTE были достаточно сообразительны, чтобы придумать способ обойти это, разработав расширение для алгоритма SMOTE, чтобы обрабатывать случаи, когда также присутствуют категориальные признаки.

Возможно, вы думаете, что кодирование категориальных признаков было бы способом обойти это все равно; однако вы не совсем правы, потому что SMOTE или ROSE затем будут рассматривать их как непрерывные и генерировать недопустимые значения для них. Например, если признак бинарный, то выбранная точка на линии может быть равной 0,57 для новой точки, что не является 0 и 1. Округление – плохая идея, потому что это эквивалентно случайному выбору, будет это 0 или 1.

Напомним, что следующее – так SMOTE генерирует новую точку:

• Предположим, что точка x_i имеет ближайшие соседи z_i1, z_i2, …, z_ik
• пусть j будет случайным числом в [1, k]
• пусть r будет случайным числом в [0, 1]

тогда для каждой точки x_i SMOTE просто применяет

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

1. Как находятся k-ближайшие соседи? Евклидово расстояние работает только с непрерывными признаками.
2. Как генерируется новая точка? Мы не можем применять уравнение SMOTE для генерации категориальной части x_i’

Для первого вопроса авторы предложили модификацию евклидового расстояния, чтобы учитывать категориальную часть. Предположим, что каждый из x_i и z_ij включает m непрерывных признаков и n категориальных признаков, тогда в модифицированной метрике непрерывные признаки естественно вычитаются и возводятся в квадрат, а затем добавляется постоянное наказание за каждую различающуюся пару категориальных признаков. Это наказание, в частности, является медианой дисперсий всех непрерывных признаков, которые могут быть вычислены в начале алгоритма.

К примеру, для измерения расстояния между двумя точками x_1 и x_2

тогда, если медиана стандартных отклонений равна m, расстояние задается следующим образом

последние два члена учитывают то, как различаются последние два категориальных признака.

Хотя авторы не обосновывают метрику, она может иметь смысл после наблюдения, что одним из наиболее распространенных способов измерения расстояний между категориальными признаками является расстояние Хэмминга. Оно просто добавляет 1 за каждую различающуюся пару категориальных признаков. Расстояние Хэмминга 6 говорит о том, что у двух точек разные значения в 6 категориальных признаках. В нашем случае очевидно, что установка наказания в 1, как в расстоянии Хэмминга, не интуитивна, потому что если непрерывные признаки часто сильно отличаются, то единицы будут очень незначительными в сумме, что эквивалентно игнорированию категориальных признаков в измерении. Логично использовать среднеквадратичную разность между любыми двумя непрерывными признаками в качестве штрафа, чтобы обойти эту проблему, потому что тогда, если дисперсия непрерывных признаков часто большая, штраф будет таким же большим и будет значимым. Единственный момент состоит в том, что авторы использовали медиану дисперсий, а не их среднее значение, что может быть обосновано его устойчивостью к выбросам.

Ответ на второй вопрос гораздо проще, теперь, когда мы нашли k-ближайших соседей с использованием модифицированной метрики, мы можем сгенерировать непрерывную часть новой точки, используя уравнение SMOTE, как обычно. Для генерации категориальной части новой точки имеет смысл просто взять моду от категориальных частей k-ближайших соседей. То есть, позволить соседям проголосовать за значения в категориальной части, где наиболее распространенные значения будут доминировать.

Следовательно, то, что делает SMOTE-NC для генерации новой точки, это…

• Найти k-ближайших соседей точки (k – гиперпараметр алгоритма) с использованием модифицированной евклидовой метрики
• Выбрать одного из них случайным образом
• Провести отрезок прямой от точки к этому соседу в пространстве непрерывных признаков
• Случайным образом выбрать точку на этом отрезке
• Пусть это будет непрерывная часть новой точки
• Для категориальной части новой точки взять моду от категориальных частей k-ближайших соседей.

SMOTE-N (SMOTE-Номинальный)

Очевидно, что SMOTE-NC становится SMOTE, когда не участвуют категориальные признаки, потому что тогда штраф равен нулю и пропускается шаг с вычислением моды. Однако, если нет непрерывных признаков, то алгоритм находится в непростом положении, потому что штраф не определен, поскольку нет непрерывных признаков. Вашим временным решением может быть установка его равным 1 или чему-то подобному и работа алгоритма как обычно, но это не идеально, потому что при вычислении ближайших соседей легко возникает много связей. Если расстояние Хэмминга между одной точкой и другими 10 точками равно 7, они действительно одинаково близки к этой точке? Или они просто имеют общее то, что отличаются от этой точки в 7 признаках?

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

Следовательно, достаточно объяснить метрику расстояния, используемую в SMOTE-N для выполнения K-NN. Метрика называется “модифицированная метрика значений” (Cost & Salzberg, 1993) и работает следующим образом для двух векторов признаков с q категориальными значениями и p_1, p_2, …,p_q возможными значениями для каждого из категориальных признаков соответственно.

1. Кодируйте каждое категориальное значение с помощью вектора V длиной K, где K – это количество классов. V[i] должен быть частотой этого значения для i-го класса, деленной на его частоту по всем классам.
2. Теперь любой категориальный вектор представлен тензором из q векторов длиной k
3. Вычислите расстояние между любыми двумя категориальными векторами, представленными этим тензором, вычислив манхэттенское расстояние между каждой парой векторов длиной k, а затем возьмите L2-норму результата

Для примера, предположим, что мы хотим найти расстояние между следующими двумя категориальными векторами

после кодирования их, предположим, что мы получим следующее

После вычисления манхэттенского расстояния между каждой парой векторов у нас есть

что оценивается как 1,428 после взятия L2-нормы.

Чтобы быть точным, в статье указывается, что можно использовать как норму L1, так и L2 для магнитуды, но не принимается решение о том, какую использовать для алгоритма (здесь мы выбрали L2).

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

Здесь расстояние Хэмминга показывает, что x_2 и x_3 так же близки к x_1, так как в обоих случаях расстояние Хэмминга равно 1. Тем временем, измененная метрика различия значений смотрит, как каждое значение распределено по классам, прежде чем решить, что ближе. Предположим, что частоты для класса B2 равны [0.3, 0.2, 0.5], для класса B3 равны [0.1, 0.9, 0], а для класса B1 равны [0.25, 0.25, 0.5]. В этом случае, MVDM будет указывать, что x_3 гораздо ближе к x_1, потому что B1 гораздо ближе к B2, чем B3. С вероятностной точки зрения, если мы собираемся собрать новую точку с неизвестным классом, то знание того, является ли категория B2 или B3, не помогает особо предсказать класс, и с этой точки зрения они похожи или взаимозаменяемы.

Таким образом, вкратце алгоритм SMOTE-N работает следующим образом для генерации новой точки:

• Находим k ближайших соседей точки (k – это гиперпараметр алгоритма) с использованием измененной метрики различия значений
• Возвращаем моду категориальных значений соседей (включая саму точку) для генерации новой точки

Вот и все! Теперь должно быть ясно, как работают SMOTE, SMOTE-N и SMOTE-NC. До следующего раза, au revoir.

Ссылки:

[1] N. V. Chawla, K. W. Bowyer, L. O.Hall, W. P. Kegelmeyer, “SMOTE: synthetic minority over-sampling technique,” Journal of artificial intelligence research, 321–357, 2002.