Изменения

== Примеры алгоритмов ==

=== Cубдискретизация (удаление примеров мажоритарного класса) ===

==== '''Случайное удаление примеров мажоритарного класса''' (англ. ''Random Undersampling'') ====

Это самая простая стратегия. Для этого рассчитывается число K – количество мажоритарных примеров, которое необходимо удалить для достижения требуемого уровня соотношения различных классов. Затем случайным образом выбираются K мажоритарных примеров и удаляются.

На рис. <math>1</math> изображены примеры некоторого набора данных в двумерном пространстве признаков до и после использования алгоритма.

==== '''Поиск связей Томека''' (англ. ''Tomek Links'') ====

Пусть примеры <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'') ====

Пусть <math>L</math> – исходный набор данных. Из него выбираются все миноритарные примеры и (случайным образом) один мажоритарный. Обозначим это множество как <math>S</math>. Все примеры из <math>L</math> классифицируются по правилу одного ближайшего соседа. Записи, получившие ошибочную метку, добавляются во множество <math>S</math> (рис. <math>3</math>).

Таким образом, мы будем учить классификатор находить отличие между похожими примерами, но принадлежащими к разным классам.

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

==== '''SMOTE''' (англ. ''Synthetic Minority Oversampling Technique'') ====

Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность <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> схематично изображено то, как в двумерном пространстве признаков могут располагаться искусственно сгенерированные примеры.

==== '''ASMO''' (англ. ''Adaptive Synthetic Minority Oversampling'') ====

Алгоритм ''SMOTE'' имеет недостаток в том, что «вслепую» увеличивает плотность примерами в области слабо представленного класса (рис. <math>5</math>). В случае, если миноритарные примеры равномерно распределены среди мажоритарных и имеют низкую плотность, алгоритм SMOTE только сильнее перемешает классы.

В качестве решения данной проблемы был предложен алгоритм адаптивного искусственного увеличения числа примеров миноритарного класса ''ASMO'':