Алгоритмы сэмплирования

2020-03-17T00:39:59Z

Kirill.vakhrushev:

'''Сэмплирование''' (англ. ''data sampling'') {{---}} метод корректировки обучающей выборки с целью балансировки распределения классов в исходном наборе данных. Нужно отличать этот метод от [[Активное обучение#Методы отбора объектов |сэмплирования в активном обучении]] для отбора кандидатов и от сэмплирования в статистике<ref> [https://en.wikipedia.org/wiki/Sampling_(statistics) Sampling_(statistics)]</ref> для создания подвыборки с сохранением распределения классов.

Когда в обучающем наборе данных доля примеров некоторого класса слишком мала, такие классы называются '''миноритарными''' (англ. ''minority''), а другие, сильно представленные, — '''мажоритарными''' (англ. ''majority'')). Подобные тенденции хорошо заметны в кредитном скоринге, в медицине, в директ-маркетинге.

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

Неравномерное распределение может быть следующих типов:
* Недостаточное представление класса в переменной предикторе (независимой переменной);
* Недостаточное представление класса в критериальной переменной (зависимой).

Многие модели машинного обучения, например, нейронные сети, дают более надежные прогнозы на основе обучения со сбалансированными данными. Однако некоторые аналитические методы, в частности [[Линейная_регрессия|линейная регрессия]] и [[Логистическая_регрессия|логистическая регрессия]], не получают дополнительного преимущества.

== Стратегии сэмплирования ==
* '''Cубдискретизация''' (англ. ''under-sampling'') {{---}} удаление некоторого количество примеров мажоритарного класса.
* '''Передискретизации''' (англ. ''over-sampling'') {{---}} увеличение количество примеров миноритарного класса.
* '''Комбинированние''' (англ. ''сombining over- and under-sampling'') {{---}} последовательное применение субдискретизации и передискретизации.
* '''Ансамбль сбалансированных наборов''' (англ. ''ensemble balanced sets'') {{---}} ансамбли классификаторов, использующие сэмплирование внутри.

Также все методы можно разделить на две группы: случайные (недетерминированные) и специальные (детерминированные).

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

== Примеры алгоритмов ==
[[Файл:Random_undersampling.png|thumb|right|upright=1.7|Рис. <math>1</math>. Случайное удаление примеров мажоритарного класса]]
=== Cубдискретизация (удаление примеров мажоритарного класса) ===
==== '''Случайное удаление примеров мажоритарного класса''' (англ. ''Random Undersampling'') ====
Это самая простая стратегия. Для этого рассчитывается число K – количество мажоритарных примеров, которое необходимо удалить для достижения требуемого уровня соотношения различных классов. Затем случайным образом выбираются K мажоритарных примеров и удаляются.
На рис. <math>1</math> изображены примеры некоторого набора данных в двумерном пространстве признаков до и после использования алгоритма.
==== '''Поиск связей Томека''' (англ. ''Tomek Links'') ====
[[Файл:Tomek_links.png|thumb|right|upright=1.7|Рис. <math>2</math>. Удаление мажоритарных примеров, участвующих в связях Томека]]
Пусть примеры <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>
\begin{cases}
d(E_i,E_l)<d(E_i,E_j),\\
d(E_j,E_l)<d(E_i,E_j)
\end{cases}
</math>

Согласно данному подходу, все мажоритарные записи, входящие в связи Томека, должны быть удалены из набора данных. Этот способ хорошо удаляет записи, которые можно рассматривать в качестве «зашумляющих». На рис. <math>2</math> визуально показан набор данных в двумерном пространстве признаков до и после применения стратегии поиска связей Томека.
==== '''Правило сосредоточенного ближайшего соседа''' (англ. ''Condensed Nearest Neighbor Rule'') ====
[[Файл:Condensed_nearest_neighbor_rule.png|thumb|right|upright=1.7|Рис. <math>3</math>. Удаление примеров мажоритарного класса правилом сосредоточенного ближайшего соседа]]
Пусть <math>L</math> – исходный набор данных. Из него выбираются все миноритарные примеры и (случайным образом) один мажоритарный. Обозначим это множество как <math>S</math>. Все примеры из <math>L</math> классифицируются по правилу одного ближайшего соседа. Записи, получившие ошибочную метку, добавляются во множество <math>S</math> (рис. <math>3</math>).
Таким образом, мы будем учить классификатор находить отличие между похожими примерами, но принадлежащими к разным классам.
==== '''Односторонний сэмплинг''' (англ. ''One-side sampling, one-sided selection'') ====
Главная идея этой стратегии – это последовательное сочетание предыдущих двух, рассмотренных выше.
Для этого на первом шаге применяется правило сосредоточенного ближайшего соседа, а на втором – удаляются все мажоритарные примеры, участвующие в связях Томека.
Таким образом, удаляются большие «сгустки» мажоритарных примеров, а затем область пространства со скоплением миноритарных очищается от потенциального шума.
==== '''Правило «очищающего» соседа''' (англ. ''Neighborhood cleaning rule'') ====
Эта стратегия также направлена на то, чтобы удалить те примеры, которые негативно влияют на исход классификации миноритарных классов.
Для этого все примеры классифицируются по правилу трех ближайших соседей. Удаляются следующие мажоритарные примеры:
* получившие верную метку класса;
* являющиеся соседями миноритарных примеров, которые были неверно классифицированы.
==== Дополнительные ====
* Under-sampling with Cluster Centroids<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* NearMiss <math>(1 \And 2 \And 3)</math><ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Edited Nearest Neighbours<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Instance Hardness Threshold<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Repeated Edited Nearest Neighbours<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* AllKNN<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>

=== Передискретизации (увеличение числа примеров миноритарного класса) ===
==== '''Дублирование примеров миноритарного класса''' (англ. ''Oversampling'') ====
Самый простой метод – это дублирование примеров миноритарного класса. В зависимости от того, какое соотношение классов необходимо, выбирается количество случайных записей для дублирования.
==== '''SMOTE''' (англ. ''Synthetic Minority Oversampling Technique'') ====
[[Файл:Smote.png|thumb|right|upright=1.7|Рис. <math>4</math>. Искусственно созданные новые примеры миноритарного класса]]
Этот алгоритм основан на идее генерации некоторого количества искусственных примеров, которые были бы похожи на имеющиеся в миноритарном классе, но при этом не дублировали их. Для создания новой записи находят разность <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_overgeneralization.png|thumb|right|upright=1.7|Рис. <math>5</math>. Негативное влияние алгоритма SMOTE]]
==== '''ASMO''' (англ. ''Adaptive Synthetic Minority Oversampling'') ====
[[Файл:Asmo.png|thumb|right|upright=1.7|Рис. <math>6</math>. Основная идея алгоритма ASMO]]
Алгоритм ''SMOTE'' имеет недостаток в том, что «вслепую» увеличивает плотность примерами в области слабо представленного класса (рис. <math>5</math>). В случае, если миноритарные примеры равномерно распределены среди мажоритарных и имеют низкую плотность, алгоритм SMOTE только сильнее перемешает классы.
В качестве решения данной проблемы был предложен алгоритм адаптивного искусственного увеличения числа примеров миноритарного класса ''ASMO'':
# Если для каждого <math>i</math>-ого примера миноритарного класса из <math>k</math> ближайших соседей <math>g, (g≤k)</math> принадлежит к мажоритарному, то набор данных считается «рассеянным». В этом случае используют алгоритм ASMO, иначе применяют SMOTE (как правило, <math>g</math> задают равным <math>20</math>).
# Используя только примеры миноритарного класса, выделить несколько кластеров (например, алгоритмом [[K-средних|<tex>\mathrm{k}</tex>-средних]]k-means).
# Сгенерировать искусственные записи в пределах отдельных кластеров на основе всех классов. Для каждого примера миноритарного класса находят <math>m</math> ближайших соседей, и на основе них (также как в ''SMOTE'') создаются новые записи.
Такая модификация алгоритма ''SMOTE'' делает его более адаптивным к различным наборам данных с несбалансированными классами. Общее представление идеи алгоритма показано на рис. <math>6</math>.
==== Дополнительные ====
* SMOTENC - SMOTE for Nominal Continuous<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* bSMOTE <math>(1 \And 2)</math> - Borderline SMOTE of types <math>1</math> and <math>2</math><ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* SVM SMOTE - Support Vectors SMOTE<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* ADASYN - Adaptive synthetic sampling approach for imbalanced learning<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Repeated Edited Nearest Neighbours<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* KMeans-SMOTE<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>

=== Комбинированние ===
* SMOTE <math>+</math> Tomek links<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* SMOTE <math>+</math> ENN<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>

=== Ансамбль сбалансированных наборов ===
* Easy Ensemble classifier<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Balanced Random Forest<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* Balanced Bagging<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>
* RUSBoost<ref> [https://en.wikipedia.org Sampling_(statistics)]</ref>

== Реализации ==

Большинство рассмотренных алгоритмов реализованы в

== См. также ==

*[[%%%%%%%%%%%%%%%%%%%%%%%%5]]
*[[%%%%%%%%%%%%%%%%%%%%%%%%%%%%%]]

== Примечания ==
<references/>

[[Категория: Машинное обучение]]
[[Категория: Классификация и регрессия]]

Файл:Asmo.png

2020-03-17T00:38:28Z

Kirill.vakhrushev:

Файл:Smote overgeneralization.png

2020-03-17T00:37:33Z

Kirill.vakhrushev:

Файл:Smote.png

2020-03-17T00:36:32Z

Kirill.vakhrushev:

Алгоритмы сэмплирования

2020-03-16T23:43:05Z

Алгоритмы сэмплирования

2020-03-16T22:43:40Z

Kirill.vakhrushev:

Алгоритмы сэмплирования

2020-03-16T02:52:56Z

Kirill.vakhrushev:

Алгоритмы сэмплирования

2020-03-16T02:42:05Z

Kirill.vakhrushev:

2018-09-30T17:01:43Z

Kirill.vakhrushev: /* Критическая секция */

==Определения==
{{Определение
|definition=
'''Взаимное исключение''' (англ. ''mutual exclusion'') — свойство построения параллельных программ, которое используется в целях предотвращения состояния гонки (англ. ''race condition''); Оно требует, чтобы один поток исполнения никогда не входил в критическую секцию одновременно с тем, как другой параллельный поток выполнения вошел в свою критическую секцию.
}}
То есть критические секции не могут выполняться параллельно: <tex>\forall i,j:i \neq j \Rightarrow CS_i \rightarrow CS_j \vee CS_j \rightarrow CS_i </tex>. Это значит, что выполнение критических секций будет линеаризуемо. Это требование корректности протокола взаимной блокировки.

{{Определение
|definition=
'''Критическая секция''' (англ. ''critical section'') — участок исполняемого кода программы, в котором производится доступ к общему ресурсу (данным или устройству), который не должен быть одновременно использован более чем одним потоком исполнения.
}}
==Проблема==
Проблема, с которой связаны взаимные исключения, является проблемой совместного использования ресурсов: как можно управлять доступом нескольких процессов к общему ресурсу, когда каждый процесс нуждается в исключительном контроле над этим ресурсом при выполнении своей работы? Решение — делать доступным общий ресурс только тогда, когда процесс находится в определенном сегменте кода, называемом критической секцией. И контролировать доступ к общему ресурсу, контролируя каждое взаимное выполнение той части программы, в которой будет использоваться ресурс.

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

Условие корректности:
#'''Взаимное исключение''' (англ. ''mutual exclusion''): только один поток может быть в критической секции.
Условия прогресса:
#'''Отсутствие взаимоблокировок''' (англ. ''deadlocks''): если несколько потоков пытаются войти в критическую секцию, то хотя бы один из них должен войти в критическую секцию за конечное время.
#'''Отсутствие голодания''' (англ. ''starvation-freedom''): если какой-то поток пытается войти в критическую секцию, то он войдет в критическую секцию за конечное время. Может быть последовательно усиленно, превращаясь в условие честности (англ. ''fairness'').
#*Квадратичное ожидание (англ. ''quadratic wait'') — <tex>O(n^2)</tex> операций.
#*Линейное ожидание (англ. ''linear wait'') — <tex>O(n)</tex> операций.
#*Первый пришел, первый обслужен (англ. ''first come first served'')

Требование <tex>First Come First Served (FCFS)</tex> формализуется так:
#Метод <tex>lock</tex> должен состоять из двух последовательных секций.
'''def''' lock():
'''doorway'''
'''waitnig'''
#Секция <tex>doorway</tex> должны быть <tex>wait free</tex>, то есть выполняться за конечное число шагов, независимо от других потоков.
#Секция <tex>waiting</tex> должна выполнять условие: Если <tex>DW_i \Rightarrow DW_j</tex>, то <tex>res(WT_i) \Rightarrow res(WT_j)</tex>.

Каждая программа может быть разделена на четыре секции, что приводит к четырем состояниям. [[Файл: State_graph2.png|thumb|right|Порядок перехода между состояниями]]
;Non-Critical Section: Операция находится вне критической секции; этот процесс не использует или не запрашивает общий ресурс.
;Trying: Процесс пытается войти в критический раздел.
;Critical Section: В этом разделе разрешен доступ к общему ресурсу.
;Exit :Процесс выходит из критического раздела и делает доступный общий ресурс другим процессам.

Если процесс хочет войти в критический раздел, он должен сначала выполнить раздел <tex>try</tex> и подождать, пока он не получит доступ к критическому разделу. После того, как процесс выполнил свой критический раздел и завершился с общими ресурсами, ему необходимо выполнить раздел выхода, чтобы освободить их для использования другими процессами. Затем процесс возвращается в некритический раздел.

==Алгоритмы взаимного исключения==

===Алгоритм Петерсона для <tex>2</tex> потоков===
Простейший алгоритм параллельного программирования для взаимного исключения потоков исполнения кода, разработанный Гарри Петерсоном в <tex>1981</tex> г. Хотя изначально был сформулирован для 2-поточного случая, алгоритм может быть обобщён для произвольного количества потоков. Гарантирует взаимное исключение, отсутствие взаимной блокировки и отсутствие голодания.

Принцип работы: перед тем как начать исполнение критической секции кода, поток должен вызвать процедуру <tex>lock()</tex> со своим номером в качестве параметра. Она должна организовать ожидание потоком своей очереди входа в критическую секцию. После исполнения критической секции и выхода из неё поток вызывает другую процедуру <tex>unlock()</tex>, после чего уже другие потоки смогут войти в критическую область. Посмотрим, как реализуется этот общий принцип алгоритмом Петерсона для двух потоков.

'''threadlocal int''' id // 0 or 1
'''shared int''' want[2]
'''shared int''' victim
'''def''' lock:
want[id] = true
victim = id
'''while''' want[1-id] '''and'''
victim == id:
'''pass'''

'''def''' unlock:
want[id] = false

===Корректность алгоритма===
=====Взаимное исключение=====
Потоки <tex>0</tex> и <tex>1</tex> никогда не могут попасть в критическую секцию в один момент времени: если <tex>0</tex> вошёл в секцию, он установил <tex>want[0]</tex> в <tex>true</tex>. Тогда либо <tex>want[1] = false</tex> (тогда поток <tex>1</tex> не в критической секции), либо <tex>waiting = 1</tex> (тогда поток <tex>1</tex> пытается войти в критическую секцию и крутится в цикле), либо поток <tex>1</tex> пытается войти в критическую секцию после установки <tex>want[1] = true</tex>, но до установки <tex>waiting</tex> и цикла. Таким образом, если оба процесса находятся в критической секции, должно быть <tex> want[0] \space and \space want[1] \space and \space waiting = 0 \space and \space waiting = 1 </tex>, но такого не может быть одновременно и мы пришли к противоречию.

=====Отсутствие взаимной блокировки=====
Для того, чтобы оба процесса находились в ожидании, необходимы противоположные значения переменной <tex>waiting</tex>, что невозможно.
=====Отсутствие голодания=====
Возможна ситуация, когда один процесс будет несколько раз подряд захватывать себе критическую секцию, а другой, изъявивший желание попасть туда, будет ждать. В алгоритме Петерсона процесс не будет ждать дольше, чем один вход в критическую секцию: после выполнения <tex>unlock()</tex> и повторного захода в <tex>lock()</tex> процесс установит себя как ждущего и попадёт в цикл, который не завершится, пока не отработает другой процесс.

===Алгоритм Петерсона для <tex>N</tex> потоков===
Обобщение Алгоритм Петерсона для <tex>N</tex> потоков. Гарантирует взаимное исключение, отсутствие блокировки и отсутствие голодания. Но алгоритм не очень честный. Невезучий поток может ждать пока другие потоки <tex>O(N^2)</tex> раз войдут в критическую секцию (квадратичное ожидание).

'''threadlocal int''' id // 0 to N-1
'''shared int''' level[N]
'''shared int''' victim[N]
'''def''' lock:
'''for''' j = 1..N-1: //Для входа в CS надо пройти на N-1 уровней
level[id] = j //Обобщаем want на уровень j: level[id] >= j
victim[j] = id //Своя жертва на каждом уровне
'''while''' '''exist''' k: k != id '''and''' //Для прохода на следующий уровень соревнуемся со всеми другими потоками
level[k] >= j '''and'''
victim[j] == id:
'''pass'''

'''def''' unlock:
level[id] = 0

===Алгоритм Лампорта (вариант <tex>1</tex>)===
Алгоритм пекарни Лампорта алгоритм разделения общих ресурсов между несколькими потоками путём взаимного исключения. Опубликован Лесли Лампортом в 1974 году.
=====Аналогия=====
Лампорт предлагает рассмотреть пекарню с устройством, выдающим номерки у входа. Каждому входящему покупателю выдаётся номерок на единицу больше предыдущего. Общий счётчик показывает номер обслуживаемого в данный момент клиента. Все остальные покупатели ждут, пока не закончат обслуживать текущего клиента и табло покажет следующий номер. После того как клиент сделает покупку и сдаст свой номерок, служащий увеличивает на единицу допустимые для выдачи устройством у входа номера. Если совершивший покупку клиент захочет снова что-нибудь купить, он должен будет снова взять номерок у входа и встать в общую очередь.

Пусть покупатели это потоки, получившие номера <tex>i</tex> от глобальной переменной. При наличии нескольких потоков, получивших номер <tex>n</tex> при входе в критическую секцию, поток с меньшим номером <tex>i</tex> будет иметь больший приоритет при обслуживании (входе в критическую секцию).
=====Критическая секция=====
Когда поток хочет войти в критическую секцию, он должен проверить номера <tex>n</tex>, полученные другими потоками, и убедиться, что у него меньший номер. В случае совпадения <tex>n</tex> у двух или нескольких потоков, в критическую секцию входит поток с наименьшим номером потока<tex>i</tex>.
(na, ia) < (nb, ib),
что эквивалентно:
(na < nb) or ((na == nb) and (ia < ib))
Когда поток заканчивает работу в критической секции, он освобождает номер ''n'' и выходит из критической секции.

Ключевое свойство: если поток <tex>P</tex> выполнил <tex>doorway (DW)</tex> до потока <tex>Q</tex>, то у него более ранний номер очереди.

'''threadlocal int''' id // 0 to N-1
'''shared boolean''' want[N] '''init''' false
'''shared int''' label[N] '''init''' 0
'''def''' lock:
want[id] = true
label[id] = '''max'''(label) + 1
'''while''' '''exists''' k: k != id '''and'''
want[k] '''and'''
(label[k], k) < (label[id], id) :
'''pass'''
'''def''' unlock:
want[id] = false

Обладает свойством первый пришел, первый обслужен (FCFS). Это сильнее чем линейное ожидание, cамое сильное свойство прогресса.

===Алгоритм Лампорта (вариант <tex>2</tex>)===
Обладает всеми свойствами классического варианта, но дополнительно позволяет решить проблему с бесконечными метками.

'''threadlocal int''' id // 0 to N-1
'''shared boolean''' want[N] '''init''' false
'''shared int''' label[N] '''init''' 0
'''def''' lock:
choosing[id] = true
label[id] = '''max'''(label!='''inf''') + 1
choosing[id] = false
'''while''' '''exists''' k: k != id '''and'''
(choosing[k] '''or'''
(label[k], k) < (label[id], id)) :
'''pass'''
'''def''' unlock:
label[id] = '''inf'''

==См. также==
* [[Алгоритм_Лампорта_взаимного_исключения]]

== Источники информации ==
* [https://en.wikipedia.org/wiki/Mutual_exclusion Mutual exclusion]

[[Категория: Параллельное программирование]]