2
правки
Изменения
Дополнена информация в двух разделах, добавлены 4 раздела: 1 метод сэмплирования и 3 алгоритма.
Неравномерное распределение может быть следующих типов:
* Недостаточное представление класса в ''независимой '' переменной;* Недостаточное представление класса в ''зависимой '' переменной.
Многие модели машинного обучения, например, нейронные сети, дают более надежные прогнозы на основе обучения со сбалансированными данными. Однако некоторые аналитические методы, в частности [[Линейная_регрессия|линейная регрессия]] и [[Логистическая_регрессия|логистическая регрессия]], не получают дополнительного преимущества.
Также все методы можно разделить на две группы: случайные (недетерминированные) и специальные (детерминированные).
* '''Случайное сэмплирование''' (англ. ''random sampling'') {{---}} для этого типа сэмплирования существует равная вероятность выбора любого конкретного элемента. Например, выбор 10 чисел в промежутке от 1 до 100. Здесь каждое число имеет равную вероятность быть выбранным.
** '''Сэплирование с заменой''' (англ. ''sampling with replacement'') {{---}} здесь элемент, который выбирается первым, не должен влиять на вторую или любую другую выборку. Математически, ковариация равна нулю между двумя выборками. Мы должны использовать выборку с заменой, когда у нас большой набор данных. Потому что, если мы используем выборку без замены, то вероятность для каждого предмета, который будет выбран, будет изменяться, и она будет слишком сложной после определенного момента. Выборка с заменой может сказать нам, что чаще встречается в наших данных.
** '''Сэмплирование без замены''' (англ. ''sampling without replacement'') {{---}} здесь то, что мы выбираем первым, повлияет на второе. Выборка без замены полезна, если набор данных мал. Математически, ковариация между двумя выборками не равна нулю.
* '''Стратифицированное сэмплирование''' (англ. ''stratified sampling'') {{---}} в этом типе техники мы выбираем из определенной группы объектов из всей выборки. Из каждой группы извлекается одинаковое количество объектов, хотя группы имеют разные размеры. Кроме того, существует вариант, когда количество объектов, выбранных из каждой группы, пропорционально размеру этой группы.
== Метод Uncertainty Sampling ==
'''Идея:''' выбирать <math>x_i</math> с наибольшей неопределенностью <math>a(x_i)</math>.
Задача многоклассовой классификации:
<math>a(x)=\arg\max\limits_{y\in Y}P(y \mid x)</math>
<math>p_k(x), k=1\ldots\left | Y \right |</math> {{---}} ранжированные по убыванию <math>P(y \mid x), y\in Y</math>.
* Принцип наименьшей достоверности (англ. ''least confidence''):
:<math>x_i=\arg\min\limits_{u\in X^k}p_1(u)</math>
* Принцип наименьшей разности отступов (англ. ''margin sampling''):
:<math>x_i=\arg\min\limits_{u\in X^k}(p_1(u)-p_2(u))</math>
* Принцип максимума энтропии (англ. ''maximum entropy''):
:<math>x_i=\arg\min\limits_{x\in X^k}\sum_{k} {p_k(u)\ln p_k(u)}</math>
В случае двух классов эти три принципа эквивалентны. В случае многих классов появляются различия.
== Примеры алгоритмов ==
* NearMiss <math>(1 \And 2 \And 3)</math><ref>I. Mani, J. Zhang. “kNN approach to unbalanced data distributions: A case study involving information extraction,” In Proceedings of the Workshop on Learning from Imbalanced Data Sets, pp. 1-7, 2003.</ref> {{---}} удаляет примеры мажоритарного класса, для которых среднее расстояние до ближайших соседей ([[Метрический_классификатор_и_метод_ближайших_соседей|KNN]]) миноритарного класса является наименьшим. Также может использоваться расстояние до самых дальних соседей, либо среднее расстояние до всех соседей.
* Edited Nearest Neighbours<ref>D. Wilson, “Asymptotic Properties of Nearest Neighbor Rules Using Edited Data,” IEEE Transactions on Systems, Man, and Cybernetrics, vol. 2(3), pp. 408-421, 1972.</ref> {{---}} удаляет примеры мажоритарного класса, если при классификации методом [[Метрический_классификатор_и_метод_ближайших_соседей|KNN]] они определяются как примеры миноритарного класса.
=== Передискретизации (увеличение числа примеров миноритарного класса) ===
Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность <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> схематично изображено то, как в двумерном пространстве признаков могут располагаться искусственно сгенерированные примеры.
В SMOTE (техника избыточной выборки синтетического меньшинства) мы синтезируем элементы для класса меньшинства в непосредственной близости от уже существующих элементов.<br /><code>from imblearn.over_sampling import SMOTE<br />smote = SMOTE(ratio='minority')<br />X_sm, y_sm = smote.fit_sample(X, y)</code><br />В библиотеке ''imblearn'' есть множество других методов как для недостаточной выборки (Cluster Centroids, NearMiss и т.д.), так и для избыточной выборки (ADASYN и bSMOTE).
[[Файл:Smote_overgeneralization.png|thumb|right|upright=1.2|Рис. <math>5</math>. Негативное влияние алгоритма SMOTE]]
==== '''ASMO''' (англ. ''Adaptive Synthetic Minority Oversampling'') ====
Такая модификация алгоритма ''SMOTE'' делает его более адаптивным к различным наборам данных с несбалансированными классами. Общее представление идеи алгоритма показано на рис. <math>6</math>.
==== Дополнительные ====
* SMOTENC - SMOTE for Nominal Continuous<ref> [httpsN. V. Chawla, K. W. Bowyer, L. O. Hall, W. P. Kegelmeyer, “SMOTE://enSynthetic minority over-sampling technique,” Journal of Artificial Intelligence Research, vol.wikipedia16, pp. 321-357, 2002.org Sampling_(statistics)]</ref>{{---}} в отличие от ''SMOTE'', работает с непрерывными признаками у примеров обучающей выборки.* bSMOTE Borderline-SMOTE <math>(1 \And 2)</math> <ref>H. Han, W.-Y. Wang, B.-H. Mao, “Borderline-SMOTE: A new over-sampling method in imbalanced data sets learning,” In Proceedings of the 1st International Conference on Intelligent Computing, pp. 878-887, 2005.</ref> {{---}} в отличие от ''SMOTE'', для создания новых синтетических примеров используются только примеры на границе классов.* SVM SMOTE - Borderline Support Vectors SMOTE <ref>H. M. Nguyen, E. W. Cooper, K. Kamei, “Borderline over-sampling for imbalanced data classification,” In Proceedings of types the 5th International Workshop on computational Intelligence and Applications, pp. 24-29, 2009.</ref> {{---}} вариант алгоритма ''SMOTE'', который использует алгоритм [[Метод_опорных_векторов_(SVM)|SVM]] для обнаружения примеров, рядом с которыми будут создаваться новые синтетические примеры. === '''Алгоритм Метрополиса — Гастингса''' ===Алгоритм позволяет семплировать любую функцию распределения. Он основан на создании цепи Маркова, то есть на каждом шаге алгоритма новое выбранное значение зависит только от предыдущего.* Очередная итерация начинается с состояния <math>x^{(i)}</math>* Выбираем <math>x^{\prime}</math> по распределению <math>q(x^\prime; x^{(i)})</math>* Вычисляем::<math>a(x^{\prime}, x)=\frac{p^{*}(x^{\prime})}{p^{*}(x^{(i)})} \frac{q(x^{(i)}; x^{\prime})}{q(x^{\prime}; x^{(i)})}</math>* С вероятностью <math>a(x^{\prime}, x)</math> (<math>1</math> and , если <math>2a\geq 1</math>) <refmath> [httpsx^{(i+1)}:=x^{\prime}</math>, иначе <math>x^{(i+1)}:=x^{(i)}</enmath> === '''Сэмплирование по Гиббсу''' ===Этот алгоритм является частным случаем алгоритма Метрополиса — Гастингса и назван в честь физика Джозайи Гиббса. Он замечателен тем, что для него не требуется явно выраженное совместное распределение, а нужны лишь условные вероятности для каждой переменной, входящей в распределение.wikipediaАлгоритм на каждом шаге берет одну случайную величину и выбирает её значение при условии фиксированных остальных.<br/><math>x_{i}^{t+1}</math> выбираем по распределению <math>p(x_{i}\mid x_{1}^{t+1},\ldots,x_{i-1}^{t+1},x_{i+1}^{t},\ldots,x_{n}^{t})</math> и повторяем.org Sampling_<br/>Это частный случай алгоритма Метрополиса для распределений <math>q(statisticsx^{\prime}; x)]=p(x_{i}^{\prime}\mid x_{-i})</math>, и вероятность принятия каждого сэмпла полается равна <math>1</refmath>. Поэтому сэмплирование по Гиббсу сходится, и, так как это такое же случайное блуждание по сути, верна та же квадратичная оценка. В больших размерностях может оказаться эффективнее сэмплить по несколько переменных сразу, а не по одной — например, часто бывает, что у нас двудольный граф из переменных, в которых все переменные из одной доли связаны со всеми переменными из другой доли (ну или со многими), а между собой не связаны. В такой ситуации следует зафиксировать все переменные одной доли и просэмплировать все переменные в другой доле одновременно (это можно понимать буквально — поскольку при такой структуре все переменные одной доли условно независимы при условии другой, их можно сэмплировать независимо и параллельно), потом зафиксировать все переменные второй доли и так далее.* SVM SMOTE === '''Slice sampling''' ===Выборка среза представляет собой тип алгоритма Монте Карло по схеме марковских цепей для выборки псевдослучайных чисел, т.е. для отбора случайных выборок из статистического распределения. Метод основан на наблюдении, что для выборки случайной величины можно равномерно выбирать из области под графиком ее функции плотности. Slice sampling, в его самой простой форме, равномерно выбирается из- Support Vectors SMOTEпод кривой <math>f(x)<ref/math> [httpsбез необходимости отбрасывать какие-либо точки следующими действиями:* Выберите начальное значение <math>x_{0}<//en.wikipedia.org Sampling_math>, для которого <math>f(statisticsx_{0})]>0</refmath>* ADASYN - Adaptive synthetic sampling approach for imbalanced learningВыберите значение <refmath> [https:y</math> равномерно между <math>0</en.wikipedia.org Sampling_math> и <math>f(statisticsx_{0})]</refmath>* Repeated Edited Nearest NeighboursПроведите горизонтальную линию через кривую в этой координате <refmath> [https:y<//en.wikipedia.org Sampling_math>* Выберите точку <math>(statisticsx, y)]</refmath>на отрезке в пределах кривой* KMeansПовторите с шага <math>2</math>, используя новое значение <math>x</math> Суть здесь заключается в том, что один из способов равномерной выборки точки из произвольной кривой — это сначала нарисовать тонкие горизонтальные срезы одинаковой высоты по всей кривой. Затем мы можем сэмплировать точку внутри кривой путем случайного выбора среза, который находится в точке или ниже кривой в позиции <math>x</math> на предыдущей итерации, а затем случайным образом выбрать позицию <math>x</math> где-SMOTEнибудь вдоль среза. Используя позицию <refmath> [https:x</math> из предыдущей итерации алгоритма, в долгосрочной перспективе мы выбираем срезы с вероятностями, пропорциональными длине их сегментов в пределах кривой. Самая сложная часть этого алгоритма — это поиск границ горизонтального среза, который включает в себя инвертирование функции, описывающей распределение, из которого производится выборка. Это особенно проблематично для мультимодальных распределений, где срез может состоять из нескольких прерывистых частей. Часто можно использовать форму выборки отклонения, чтобы преодолеть это, когда мы производим выборку из более крупного среза, который, как известно, включает в себя требуемый рассматриваемый срез, а затем отбрасываем точки за пределами желаемого среза. Этот алгоритм можно использовать для выборки из области под любой кривой, независимо от того, интегрируется ли функция в <math>1</enmath>.wikipedia.org Sampling_(statistics)]Фактически, масштабирование функции по константе не влияет на выборочные <math>x</refmath>—позиции. Это означает, что алгоритм может использоваться для выборки из распределения, функция плотности вероятности которого известна только с точностью до константы.
=== Комбинирование ===
* SMOTE <math>+</math> Tomek links<ref> [httpsG. E. A. P. A. Batista, A. L. C. Bazzan, M. C. Monard, “Balancing training data for automated annotation of keywords://enA case study,” In Proceedings of the 2nd Brazilian Workshop on Bioinformatics, pp.wikipedia10-18, 2003.org Sampling_(statistics)]</ref>{{---}} сначала выполняет передискретизацию с использованием ''SMOTE'', а потом субдискретизацию используя ''Tomek Links''.* SMOTE <math>+</math> ENN<ref> [https://enG. E. A. P. A. Batista, R. C. Prati, M. C.wikipediaMonard, “A study of the behavior of several methods for balancing machine learning training data,” ACM Sigkdd Explorations Newsletter, vol.org Sampling_6(statistics1)], pp. 20-29, 2004.</ref>{{---}} последовательно использует ''SMOTE'' и ''Edited Nearest Neighbours''.
=== Ансамбль сбалансированных наборов ===
* Easy Ensemble classifier<ref> [https://enX.-Y. Liu, J. Wu and Z.-H.wikipediaZhou, “Exploratory undersampling for class-imbalance learning,” IEEE Transactions on Systems, Man, and Cybernetics, vol.org Sampling_39(statistics2)], pp. 539-550, 2009.</ref>{{---}} независимые классификаторы обучаются на случайных подвыборках, из которых постепенно удаляются правильно классифицирующиеся примеры мажоритарных классов.* Balanced Random Forest<ref> [https://enC. Chao, A. Liaw, and L. Breiman.wikipedia"Using random forest to learn imbalanced data.org Sampling_" University of California, Berkeley 110 (statistics2004)]: 1-12.</ref>{{---}} в отличие от классического [[Дерево_решений_и_случайный_лес|случайного леса]], может работать на несбалансированных данных. * Balanced Bagging<ref> [https:Hido, Shohei & Kashima, Hisashi. (2008). Roughly Balanced Bagging for Imbalanced Data. 143-152. 10.1137//en1.9781611972788.wikipedia13.org Sampling_(statistics)]</ref>* RUSBoost<ref> {{---}} в отличие от классического [[https://enВиды_ансамблей#.D0.91.D1.8D.D0.B3.D0.B3.D0.B8.D0.BD.wikipediaD0.org Sampling_(statistics)B3|бэггинга]]</ref>, имеет дополнительный шаг субдискретизации обучающей подвыборки.
== Реализации ==
