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

В машинном обучении нередко возникают ситуации, когда в обучающем наборе данных доля примеров некоторого класса оказывается слишком низкой (такой класс часто называют миноритарным), а другого — слишком большой (такой класс называют мажоритарным). Эта ситуация в теории машинного обучения известна как несбалансированность классов (class imbalance), а классификация в условиях несбалансированности классов называется несбалансированной классификацией (unbalanced classification).

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

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

Действительно, если классификатор в системе кредитного скоринга определит «плохого» заёмщика как «хорошего» и ему будет выдан кредит, то при банкротстве последнего банк потенциально теряет всю сумму кредита. Напротив, если «хороший» заёмщик будет классифицирован как «плохой», банк рискует только упущенной выгодой в виде процентов.

Очевидно, что классификация в условиях несбалансированности классов должна производиться с учётом неравенства издержек классификации. Модель должна быть настроена таким образом, чтобы минимизировать число ошибок классификации, связанных с большими издержками. Такой тип классификации известен как классификация, чувствительная к издержкам (cost-sensitive classification).

При классификации в условиях несбалансированности классов могут быть использованы два подхода: балансировка классов и оптимизация модели (например, выбор дискриминационного порога при определении класса). Данная статья посвящена рассмотрению алгоритмов и методов балансировки классов.

Процесс балансировки классов реализуется с помощью соответствующих алгоритмов сэмплинга, которые можно разделить на случайные и специальные. Ребалансировка классов может происходить путём увеличения числа примеров миноритарного класса (undersampling), либо путём сокращения числа примеров мажоритарного (oversampling). Возможно также и сочетание обоих подходов.

Сокращение числа примеров мажоритарного класса

Существует несколько стратегий балансировки обучающих выборок путём сокращения числа примеров мажоритарного класса.

Случайное удаление (random undesampling). Это самая простая и примитивная стратегия, но понятная и несложная в реализации. Сначала определяется число K примеров доминирующего класса, которое требуется удалить, чтобы достичь требуемого соотношения классов в обучающей выборке. Затем случайным образом выбираются K наблюдений доминирующего класса и удаляются.

Метод привлекателен тем, что прост в реализации. Однако, при его использовании могут быть потеряны наблюдения, несущие полезную информацию. Поэтому предпочтительно сделать стратегию балансировки классов более управляемой, то есть выполняемой в соответствии с некоторыми правилами. Рассмотрим несколько таких стратегий.

Поиск связей Томека (Tomek Links). Пусть в наборе данных имеется пара наблюдений E_i и E_j, принадлежащих различным классам. Обозначим расстояние между векторами этих наблюдений в пространстве признаков как d(E_i,E_j). Пара наблюдений (E_i,E_j) называется связью Томека, если они относятся к разным классам и не существует точки E_k, такой, что d(E_i,E_k)<d(E_i,E_j) или d(E_j,E_k)<d(E_i,E_j).

Несложно увидеть, что связи Томека объединяют близко расположенные наблюдения различных классов. Большое количество связанных таким образом наблюдений вызывает эффект наложения классов в пространстве признаков, как показано на рисунке ниже.

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

Правило соcредточенного ближайшего соседа (Condensed Nearest Neighbor Rule). Из исходного набора данных L извлекаются все примеры миноритарного класса и один мажоритарного (обозначим полученное подмножество как S). Затем производится классификация всех примеров из L по методу одного ближайшего соседа (1-NN), когда каждому, случайно выбранному наблюдению присваивается метка класса ближайшего соседа. При этом, если для наблюдения допущена ошибка классификации (найденный и фактический классы не совпадают), то оно добавляется в S.

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

Односторонний сэмплинг (One-side sampling, one-sided selection — OSS). В основе идеи данного подхода лежит сочетание двух предыдущих. На первом шаге применяется правило сосредоточенного ближайшего соседа, а на втором — удаляются все мажоритарные наблюдения, участвующие в связях Томека. Таким образом, удаляются большие «сгустки» мажоритарных наблюдений, а затем область пространства со скоплением миноритарных очищается от мажоритарных, которые создают эффект шума на границах классов и мешают их распознаванию.

Правило «очищающего» соседа (neighborhood cleaning rule — NCR). Идея здесь такая же, как и у одностороннего сэплинга. Все наблюдения классифицируются по правилу трех ближайших соседей (3-NN). Затем удаляются следующие примеры мажоритарного класса:

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

Преимущество данного подхода в том, что увеличение области соседства позволяет лучше «очищать» данные от шумов.

Теперь рассмотрим другой подход — увеличение числа примеров миноритарного класса.

Увеличение числа примеров миноритарного класса

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

Такой подход к восстановлению баланса не всегда является наиболее эффективным, поэтому был предложен специальный метод увеличения числа наблюдений миноритарного класса – алгоритм SMOTE (Synthetic Minority Oversampling Technique).

Алгоритм SMOTE. В основе алгоритма лежит идея генерации некоторого количества искусственных наблюдений, которые были бы «похожи» на наблюдения, имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания нового примера находят разность d=X_b−X_a, где X_a и X_b — векторы признаков соседних наблюдений a и b из миноритарного класса, которые находят с помощью метода ближайшего соседа.

Для наблюдения b формируется область из k соседей, из которых в дальнейшем выбирается наблюдение. Затем X_a и X_b умножаются на некоторое случайное значение из интервала (0, 1) в результате чего исходное расстояние d преобразуется к \widehat{d} . Затем путём суммирования X_a и \widehat{d} вычисляются координаты вектора нового наблюдения.

Поясним сказанное на следующем примере (рис.4).

На рисунке для примера миноритарного класса X_1 определяются 5 ближайших соседей того же класса X_2, X_3, X_4, X_5 и X_6 . Затем вычисляется расстояние между X_1 и каждым из них: d(X_1,X_2), ..., d(X_1,X_6). Эти расстояния показаны линиями.

Эти расстояния умножаются на случайное число из диапазона (0..1) и результат откладывается от X_1 вдоль линии, соединяющей его с соседом, на конце соответствующего отрезка формируется искусственный пример. Проще говоря, алгоритм формирует новые наблюдения, выбирая случайно место на прямой между объектом и его ближайшим соседом. Благодаря такому подходу искусственные наблюдения всегда будут формироваться вблизи существующих объектов, но не совпадать с ними.

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

Недостатком данного подхода является то, что алгоритм просто увеличивает плотность наблюдений в областях векторного пространства, «населённых» преимущественно миноритарным классом. Т.е. работает эффективно, когда такие области имеются. Если же примеры миноритарного класса расположены равномерно, то в результате только увеличивается перемешивание классов, что затрудняет классификацию. Это проиллюстрировано на рисунке 5.

На рисунке видно, что генерация искусственных наблюдений имеет место в основном в области, выделенной прямоугольником, где и изначально был паритет классов. В менее населённых областях пространства признаков генерации новых примеров практически нет.

Решить данную проблему позволяет модификация SMOTE, которая получила название ASMO (Adaptive Synthetic Minority Oversampling). Алгоритм ASMO состоит из следующих шагов:

• Если для каждого i-ого примера миноритарного класса из k ближайших соседей g≤k принадлежит к мажоритарному, то набор данных считается «рассеянным». В этом случае используют алгоритм ASMO, иначе применяют SMOTE (как правило, g задают равным 20).
• Используя только примеры миноритарного класса, выделить несколько кластеров (например, с помощью алгоритма k-средних), как показано на рисунке 6.

• Сгенерировать искусственные записи в пределах отдельных кластеров на основе всех классов. Для каждого примера миноритарного класса находят m ближайших соседей, и на основе них (также как в SMOTE) создаются новые записи.

Такая модификация алгоритма SMOTE делает его более адаптивным к различным наборам данных с несбалансированными классами. Недостаток подхода в том, что фактически приходится решать две задачи — кластеризации и сэмплинга. При этом, если выраженная кластерная структура в исходных данных отсутствует, то и алгоритм окажется неэффективным.

Алгоритм ADASYN. Ещё одним недостатком алгоритма SMOTE является то, что он для каждого примера миноритарного класса создаёт одно и то же количество искусственных примеров. Это не вполне оптимально, поскольку не все примеры одинаково «просты» в обучении. Например, наблюдения, расположенные вблизи границ классов обычно «перемешаны» с наблюдениями соседнего класса, поэтому алгоритму обучения сложнее их распознать. Тогда при оверсэмплинге для таких примеров логично генерировать больше искусственных наблюдений, чтобы сделать границу класса более чёткой. На этом принципе и основана работа алгоритма ADASYN.

Путь имеется выборка S, содержащая m наблюдений x_i,y_i, i=1..m . Здесь x_i — n-мерный вектор признаков, y_i — метка класса. Обозначим m_r и m_x — число объектов миноритарного и мажоритарного класса соответственно, так что m_r<m_x и m_r+m_x=m.

Алгоритм состоит из следующих шагов.

1. Вычислить показатель несбалансированности классов: d=m_r/m_x.
2. Задать порог максимально допустимого показателя несбалансированности d_{max} и проверить, выполняется ли условие d<d_{max}. Если дисбаланс превышает допустимый, то продолжаем работу алгоритма.
3. Определить число искусственных наблюдений, которое должно быть сгенерировано из миноритарного класса: G=(m_x−m_r)⋅β, где β — уровень баланса выборки. Так, β=1 означает, что выборка полностью сбалансирована.
4. Для каждого наблюдения x_i из миноритарного класса найти k ближайших соседей на основе расстояния Евклида и вычислить отношение r_i=Δ_i/k, где Δ_i — количество из k ближайших соседей вектора x_i , которые принадлежат к мажоритарному классу, т.е. r_i∈[0,1].
5. Нормализовать r_i в соответствии с выражением:
   \widehat{r}_{i}={r}_{i}/\sum\limits_{j=1}^{m}r_{j}.
6. Вычислить количество искусственных примеров, которые нужно сгенерировать для каждого примера миноритарного класса x_i: g_{i}=\widehat{r}_{i}\cdot G, где G — общее число искусственных примеров, которое должно быть сгенерировано для миноритарного класса.
7. Для каждого примера миноритарного класса x_i генерировать искусственные примеры g_i в процессе выполнения следующего цикла:
   • случайно выбрать один пример миноритарного класса x_{zi} из k ближайших соседей x_i;
   • сгенерировать искусственный пример s_{i}=x_{i}+(x_{zi}-x_{i})\cdot \lambda, где λ — случайное число из диапазона [0, 1].

Таким образом, ключевая идея алгоритма ADASYN заключается в использовании \widehat{r}_{i} в качестве критерия для автоматического определения количества искусственных примеров, которые необходимо сгенерировать для каждого миноритарного примера. Фактические, \widehat{r}_{i} это показатель распределения весов для различных примеров миноритарного класса в соответствии с их уровнем сложности для обучения.

Результирующий набор данных после применения алгоритма ADASYN не только обеспечит сбалансированное представление данных в соответствии с желаемым уровнем баланса, определяемым коэффициентом β, но и также заставит алгоритм обучения сосредоточиться на наиболее сложных для обучения примерах. В этом и заключается главное отличие алгоритма ADASYN от SMOTE, в котором для каждого примера миноритарного класса генерируется одинаковое количество искусственных примеров.

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

Другие материалы по теме:

Алгоритмы кластеризации на службе Data Mining

Loginom Community Edition - аналитика, доступная каждому