Выброс — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритмы борьбы с выбросами)
м (Правка орфографии)
 
(не показаны 62 промежуточные версии 6 участников)
Строка 1: Строка 1:
 
[[Файл:Outlier_boxplot.png|upright=1.0|thumb|Рис 1.График boxplot населения регионов России в 1990 году, где можно заметить 5 выбросов]]
 
[[Файл:Outlier_boxplot.png|upright=1.0|thumb|Рис 1.График boxplot населения регионов России в 1990 году, где можно заметить 5 выбросов]]
'''Выброс'''(англ. ''outlier'') небольшая доля объектов во входных данных, которая сильно выделяется из общей выборки. Многие алгоритмы машинного обучения чувствительны к разбросу и распределению значений атрибутов во входных данных. Соответственно выбросы во входных данных могут исказить и ввести в заблуждение процесс обучения алгоритмов машинного обучения, что приводит к увеличению времени обучения, снижению точности моделей и, в конечном итоге, к снижению результатов. Даже до подготовки предсказательных моделей на основе обучающих данных выбросы могут приводить к ошибочным представлениям и в дальнейшем к ошибочной интерпретации собранных данных.
+
'''Выброс''' (англ. ''outlier'') {{---}} небольшая доля объектов во входных данных, которая сильно выделяется из общей выборки. Многие алгоритмы машинного обучения чувствительны к разбросу и распределению значений признаков обрабатываемых объектов. Соответственно, выбросы во входных данных могут исказить и ввести в заблуждение процесс обучения алгоритмов машинного обучения, что приводит к увеличению времени обучения, снижению точности моделей и, в конечном итоге, к снижению результатов. Даже до подготовки предсказательных моделей на основе обучающих данных выбросы могут приводить к ошибочным представлениям и в дальнейшем к ошибочной интерпретации собранных данных.
 
===Виды выбросов===
 
===Виды выбросов===
Выбросы могут быть двух видов: одномерные и многомерные. Одномерные выбросы можно найти при рассмотрении распределения значений объектов в одном пространстве. Многомерные выбросы можно найти в n-мерном пространстве (из n-объектов). Рассмотрение распределений в n-мерных пространствах может быть очень сложным для человеческого мозга, поэтому необходимо обучить модель, чтобы сделать это.
+
Выбросы могут быть двух видов: одномерные и многомерные. Одномерные выбросы можно найти при рассмотрении распределения значений объектов в одномерном пространстве. Многомерные выбросы можно найти в <tex>n</tex>-мерном пространстве (из <tex>n</tex> объектов). Рассмотрение распределений в <tex>n</tex>-мерных пространствах может быть очень сложным для человеческого мозга, поэтому необходимо обучить модель, чтобы сделать это.
<br>
+
 
Выбросы также могут отличаться в зависимости от окружающей среды: точечные выбросы, контекстуальные выбросы или коллективные выбросы. Точечные выбросы - это единичные точки данных, расположенные далеко от остальной части распределения. Контекстные выбросы могут представлять собой шум в данных, например, знаки препинания при выполнении анализа текста или сигнал фонового шума при распознавании речи. Коллективные выбросы могут быть подмножествами новшеств в данных, таких как сигнал, который может указывать на открытие новых явлений.
+
Выбросы также могут отличаться в зависимости от окружающей среды: точечные выбросы, контекстуальные выбросы или коллективные выбросы. Точечные выбросы {{---}}
 +
единичные точки данных, расположенные далеко от остальной части распределения. Контекстные выбросы могут представлять собой шум в данных, например, знаки препинания при выполнении анализа текста или сигнал фонового шума при распознавании речи. Коллективные выбросы могут быть подмножествами новшеств в данных, таких как сигнал, который может указывать на открытие новых явлений.
  
 
===Причины возникновения выбросов===
 
===Причины возникновения выбросов===
* Сбой работы оборудования
+
* Сбой работы оборудования;
* Человеческий фактор
+
* Человеческий фактор;
* Случайность
+
* Случайность;
* Уникальные явления
+
* Уникальные явления;
 
* и др.
 
* и др.
 
==Примеры==
 
==Примеры==
Строка 21: Строка 22:
 
==Методы обнаружения и борьбы с выбросами==  
 
==Методы обнаружения и борьбы с выбросами==  
 
===Методы обнаружения выбросов===
 
===Методы обнаружения выбросов===
[[Файл:Outlier_normal_distribution.png|upright=1.0|thumb|[http://work.thaslwanter.at/Stats/html/statsDistributions.html Так как t-распределение имеет более длинный хвост, нежели у нормального распределения, поэтому t-распределение менее чувствительно к выбросам.]]]
+
[[Файл:Outlier_normal_distribution.png|upright=1.0|thumb|[http://work.thaslwanter.at/Stats/html/statsDistributions.html Рис 4. Так как t-распределение имеет более длинный хвост, нежели у нормального распределения, поэтому t-распределение менее чувствительно к выбросам.]]]
 
# Экстремальный анализ данных(англ. ''extreme value analysis''). При таком анализе не применяются какие-либо специальные статистические методы. Обычно этот метод применим для одномерного случая. Алгоритм использования таков:
 
# Экстремальный анализ данных(англ. ''extreme value analysis''). При таком анализе не применяются какие-либо специальные статистические методы. Обычно этот метод применим для одномерного случая. Алгоритм использования таков:
#* Визуализировать данные, используя диаграммы и гистограммы для нахождения экстремальных значений.
+
#* Визуализировать данные, используя диаграммы и гистограммы для нахождения экстремальных значений;
#* Задействовать распределение, например Гауссовское, и найти значения, чье стандартное отклонение отличается в 2-3 раза от математического ожидания или в полтора раза от первой либо третьей квартилей.
+
#* Задействовать распределение, например Гауссовское, и найти значения, чье стандартное отклонение отличается в 2-3 раза от математического ожидания или в полтора раза от первой либо третьей квартилей;
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели.
+
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели;
# Апроксимирующий метод (англ. ''proximity method''). Чуть более сложный метод, заключающийся в применении кластеризующих методов.
+
# Аппроксимирующий метод (англ. ''proximity method''). Чуть более сложный метод, заключающийся в применении кластеризующих методов;
#* Использовать метод кластеризации для определения кластеров для данных.
+
#* Использовать метод кластеризации для определения кластеров в данных;
#* Идентифицировать и отметить центроиды каждого кластера.
+
#* Идентифицировать и отметить центроиды каждого кластера;
#* Соотнести кластеры с экземплярами данных, находящимися на фиксированном расстоянии или на процентном удалении от центроиды соответствующего кластера.
+
#* Соотнести кластеры с экземплярами данных, находящимися на фиксированном расстоянии или на процентном удалении от центроида соответствующего кластера;
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели.
+
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели;
# Проецирующие методы (англ. ''projections methods''). Эти методы довольно быстро и просто определяют выбросы в выборке.
+
# Проецирующие методы (англ. ''projections methods''). Эти методы довольно быстро и просто определяют выбросы в выборке;
#* Использовать один из проецирующих методов, например метод главных компонент (англ. ''principal component analysis'', ''PCA''<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Метод главных компонент]</ref>) или самоорганизующиеся карты Кохонена(англ. ''self-organizing map'', ''SOM''<ref>[https://habr.com/post/338868/ Самоорганизующиеся карты Кохонена]</ref>) или проекцию Саммона(англ. ''Sammon mapping'', ''Sammon projection''<ref>[https://en.wikipedia.org/wiki/Sammon_mapping Проекция Саммона]</ref>), для суммирования обучающих данных в двух измерениях.
+
#* Использовать один из проецирующих методов, например, метод главных компонент (англ. ''principal component analysis'', ''PCA''<ref>[https://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B3%D0%BB%D0%B0%D0%B2%D0%BD%D1%8B%D1%85_%D0%BA%D0%BE%D0%BC%D0%BF%D0%BE%D0%BD%D0%B5%D0%BD%D1%82 Метод главных компонент]</ref>) или самоорганизующиеся карты Кохонена(англ. ''self-organizing map'', ''SOM''<ref>[https://habr.com/post/338868/ Самоорганизующиеся карты Кохонена]</ref>) или проекцию Саммона(англ. ''Sammon mapping'', ''Sammon projection''<ref>[https://en.wikipedia.org/wiki/Sammon_mapping Проекция Саммона]</ref>), для суммирования обучающих данных в двух измерениях;
#* Визуализировать отображение
+
#* Визуализировать отображение;
#* Использовать критерий близости от проецируемых значений или от вектора таблицы кодирования (англ. ''codebook vector'') для идентифицирования выбросов.
+
#* Использовать критерий близости от проецируемых значений или от вектора таблицы кодирования (англ. ''codebook vector'') для идентифицирования выбросов;
 
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели.
 
#* Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели.
  
===Алгоритмы борьбы с выбросами===
+
===Локально взвешенное сглаживание===
* Локально взвешенное сглаживание(англ. ''LOcally WEighted Scatter plot Smoothing'', ''LOWESS'')<ref>[http://www.aliquote.org/cours/2012_biomed/biblio/Cleveland1979.pdf Локально взвешенное сглаживание]</ref>.
+
Локально взвешенное сглаживание (англ. ''LOcally WEighted Scatter plot Smoothing'', ''LOWESS'')<ref>[http://www.aliquote.org/cours/2012_biomed/biblio/Cleveland1979.pdf Локально взвешенное сглаживание]</ref>. Данная методика была предложена Кливлендом (Cleveland) в 1979 году для моделирования и сглаживания двумерных данных <math>X^m={(x_i, y_i)}_{i=1}^m</math>. Эта техника предоставляет общий и гибкий подход для приближения двумерных данных. Локально-линейная модель может быть записана в виде: <math>y_t=\alpha_t+\beta_t x_t + \varepsilon_t</math>. Эта модель может быть расширена на случай локально-квадратичной зависимости и на модель с большим числом независимых переменных. Параметры <math>\alpha_t</math> и <math>\beta_t</math> локально линейной модели оцениваются с помощью локально взвешенной регрессии, которая присваивает объекту тем больший вес, чем более близок он к объекту t. Степень сглаживания определяется параметром сглаживания <math>f</math>, который выбирает пользователь. Параметр <math>f</math> указывает какая доля (англ. ''fraction'') данных используется в процедуре. Если <math>f = 0.5</math>, то только половина данных используется для оценки и влияет на результат, и тогда мы получим умеренное сглаживание. С другой стороны, если <math>f = 0.8</math>, то используются восемьдесят процентов данных, и сглаживание намного сильнее. Во всех случаях веса данных тем больше, чем они ближе к объекту <math>t</math>.
Пусть задано пространство объектов X и множество возможных ответов <math>Y = \mathbb{R}</math>. Существует неизвестная зависимость <math>y^*:X \rightarrow Y</math>, значения которой известны только на объектах обучающией выборки <math>X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i)</math>. Требуется построить алгоритм <math>a:\ X\rightarrow Y</math>, аппроксимирующий неизвестную зависимость <math>y^*</math>. Предполагается, что на множестве X задана метрика <math>\rho(x,x')</math>
+
====Постановка задачи====
+
Пусть задано пространство объектов $X$ и множество возможных ответов <math>Y = \mathbb{R}</math>. Существует неизвестная зависимость <math>y^*\colon X \to Y</math>, значения которой известны только на объектах обучающией выборки <math>X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i)</math>. Требуется построить алгоритм <math>a\colon X\to Y</math>, аппроксимирующий неизвестную зависимость <math>y^*</math>. Предполагается, что на множестве $X$ задана метрика <math>\rho(x,x')</math>.
  ВХОД: <math>X^\ell</math> - обучающая выборка;
+
 
  ВЫХОД: коэффиценты <math>\gamma_i, i = 1,...,\ell</math>;
+
Также стоит определить следующее. Для вычисления <math>a(x) = \alpha</math> для <math>\forall x \in X</math> воспользуемся методом наименьших квадратов:
 +
<math>Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}</math>, где <math>\omega_i</math> {{---}} это вес $i$-ого объекта.
 +
 
 +
Веса <math>\omega_i</math> разумно задать так, чтобы они убывали по мере увеличения расстояния <math>\rho(x,x_i)</math>. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию <math>K:[0, \infty) \rightarrow [0, \infty)</math>, называемую [[Ядра|ядром]]<sup>[на 28.01.19 не создан]</sup>, и представить <math>\omega_i</math> в следующем виде:
 +
 
 +
 
 +
<math>\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )</math>, где $h$ {{---}} ширина окна.
 +
 
 +
 
 +
Приравняв равной нулю производную <math>\frac{\partial Q}{\partial \alpha} = 0</math> и выразив <math>\alpha</math>, получаем ''формулу Надарая-Ватсона''<ref>[http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D1%86%D0%B5%D0%BD%D0%BA%D0%B0_%D0%9D%D0%B0%D0%B4%D0%B0%D1%80%D0%B0%D1%8F-%D0%92%D0%B0%D1%82%D1%81%D0%BE%D0%BD%D0%B0 Формула Надарая-Ватсона]</ref> :
 +
<math>a_h(x;X^l) = \frac{\sum_{i=1}^{l} y_i\omega_i(x)}{\sum_{i=1}^{l} \omega_i(x)} = \frac{\sum_{i=1}^{l} y_iK\left(\frac{\rho(x,x_i)}{h} \right )}{\sum_{i=1}^{l} K\left(\frac{\rho(x,x_i)}{h} \right )}</math>.
 +
 
 +
====Проблема выбросов в этой задаче====
 +
Большие случайные ошибки в значениях <math>y_i</math> сильно искажают оценку Надарая-Ватсона.
 +
 
 +
====Идея====
 +
Чем больше величина невязки <math>\varepsilon_i = \left | a_h\left (x_i;X^\ell\backslash\left \{x_i\right \} \right )-y_i\right |</math>, тем меньше должен быть вес i-го объекта <math>\omega_i(x)</math>.
 +
====Эвристика====
 +
Домножить веса <math>\omega_i(x)</math> на коэффициенты <math>\gamma_i = \widetilde{K}\left ( \varepsilon_i \right )</math>, где <math>\widetilde{K}\left ( \varepsilon \right )</math> — ещё одно ядро, вообще говоря, отличное от <math>K\left ( \rho \right )</math>.
 +
 
 +
====Псевдокод====
 +
  INPUT: <math>X^\ell</math> - training sample;
 +
  OUTPUT: coefficents <math>\gamma_i, i = 1,...,\ell</math>;
 
  ________________________________________________________
 
  ________________________________________________________
  1: инициализация: <math>\gamma_i := 1, i = 1,...,\ell</math>;
+
  1: initialization: <math>\gamma_i := 1, i = 1,...,\ell</math>; <span style="color:green">//инициализация коэффициентов</span>
  2: повторять
+
  2: do
  3:  для всех объектов <math>i = 1,...,\ell</math>;
+
  3:  for each object <math>i = 1,...,\ell</math>;
  4:    вычислить оценки скользящего контроля:
+
  4:    calculate cross-validation estimates: <span style="color:green">//вычислить оценки скользящего контроля</span>
 
         <math>a_i := a_h(x_i;X^\ell\setminus{x_i}) = \frac{\sum\limits^{\ell}_{j=1,j\ne i} {y_j\gamma_j K \left ( \tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i \right)} \right )}}{\sum\limits^{\ell}_{j=1,j\ne i}{\gamma_j K\left(\tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i\right )}\right )} }</math>
 
         <math>a_i := a_h(x_i;X^\ell\setminus{x_i}) = \frac{\sum\limits^{\ell}_{j=1,j\ne i} {y_j\gamma_j K \left ( \tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i \right)} \right )}}{\sum\limits^{\ell}_{j=1,j\ne i}{\gamma_j K\left(\tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i\right )}\right )} }</math>
  5:  для всех объектов <math>i = 1,...,\ell</math>;
+
  5:  for each object <math>i = 1,...,\ell</math>;
 
  6:    <math>\gamma_i := \widetilde{K}\left (\left | a_i-y_i \right | \right );</math>
 
  6:    <math>\gamma_i := \widetilde{K}\left (\left | a_i-y_i \right | \right );</math>
  7: пока коэффиценты <math>\gamma_i</math> не стабилизируются;
+
  7: while coefficents <math>\gamma_i</math> not stabilized; <span style="color:green">//пока коэффициенты не стабилизируются</span>
Пример. Допустим мы пытаемся восстановить зависимость, используя ''формулу Надарая-Ватсона''<ref>[http://www.machinelearning.ru/wiki/index.php?title=%D0%9E%D1%86%D0%B5%D0%BD%D0%BA%D0%B0_%D0%9D%D0%B0%D0%B4%D0%B0%D1%80%D0%B0%D1%8F-%D0%92%D0%B0%D1%82%D1%81%D0%BE%D0%BD%D0%B0 Формула Надарая-Ватсона]</ref> по некоторым данным из n наблюдений, 2 из которых имеют излишне высокое и излишне низкое значения соответственно. Большие ошибки, вызванные этими выбросами, довольно заметно исказят полученный результат по формуле. В методе локально взвешенного сглаживания мы домножаем веса объектов <math>w_i</math> на коэффиценты <math>\gamma_i=\widetilde{K}\left(\varepsilon_i\right)</math>, значения которых тем меньше, чем величина ошибки <math>\varepsilon_i</math>. Для этого мы возьмём квартическое ядро (не обязательно совпадающее с основным ядром) <math>\widetilde{K}\left(\varepsilon\right)=K_Q\left(\frac{\varepsilon}{6Me\left\{\varepsilon_i\right\}}\right)</math>, где <math>Me\left \{\varepsilon_i\right \}</math> — медиана множества значений <math>\varepsilon_i</math>.  
+
 
Таким образом выбросы будут нивелироваться автоматически при использовании данного подхода. <br>
+
====Пример на языке R====
 +
В этом примере мы попытаемся локально регрессировать и сгладить среднюю продолжительность безработицы на основе набора экономических данных из пакета $ggplot2$ языка $R$. Мы рассматриваем только первые 80 строк для этого анализа, чтобы легче было наблюдать степень сглаживания на приведенных ниже графиках.<br>
 +
data(economics, package="ggplot2")      <span style="color:green"># загрузка данных</span>
 +
economics$index <- 1:nrow(economics)    <span style="color:green"># создание индексной переменной</span>
 +
economics <- economics[1:80, ]         <span style="color:green"># усечение до 80 строк для более наглядного демонстрирования</span>
 +
loessMod10 <- loess(uempmed ~ index, data=economics, span=0.10) <span style="color:green"># 10% параметр сглаживания span</span>
 +
loessMod25 <- loess(uempmed ~ index, data=economics, span=0.25) <span style="color:green"># 25% параметр сглаживания span</span>
 +
loessMod50 <- loess(uempmed ~ index, data=economics, span=0.50) <span style="color:green"># 50% параметр сглаживания span</span>
 +
 
 +
<span style="color:green"># получить сглаженный результат</span>
 +
smoothed10 <- predict(loessMod10)
 +
smoothed25 <- predict(loessMod25)
 +
smoothed50 <- predict(loessMod50)
 +
 
 +
<span style="color:green"># Нарисовать</span>
 +
plot(economics''$''uempmed, x=economics''$''date, type="l", main="Локально взвешенное сглаживание", xlab="Дата", ylab="Длительность безработицы")
 +
lines(smoothed10, x=economics''$''date, col="red")
 +
lines(smoothed25, x=economics''$''date, col="green")
 +
lines(smoothed50, x=economics''$''date, col="blue")
 +
{|align="center"
 +
|-valign="top"
 +
|[[Файл:LOWESS.png|400px|thumb|Рис 5. На приведенном графике показано, что чем больше параметр сглаживания span, тем более сглаженной выглядит восстановленная регрессия]]
 +
|}
 +
 
 +
===Другие алгоритмы борьбы с выбросами===
 
В статистике методы, устойчивые к нарушениям модельных предположений о данных, называются ''робастными''. Метод локально взвешенного сглаживания относится к ''робастным'' методам, так как он устойчив к наличию небольшого количества выбросов.  
 
В статистике методы, устойчивые к нарушениям модельных предположений о данных, называются ''робастными''. Метод локально взвешенного сглаживания относится к ''робастным'' методам, так как он устойчив к наличию небольшого количества выбросов.  
* Дерево принятия решения (англ. ''decision tree''<ref>[https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9 Дерево принятия решения]</ref>). Это дерево, как и уже описанный алгоритм локально взвешенного сглаживания, относится ''робастным'' методам.
+
* [[Дерево решений и случайный лес|Дерево принятия решения]] (англ. ''decision tree''<ref>[https://ru.wikipedia.org/wiki/%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D1%80%D0%B5%D1%88%D0%B5%D0%BD%D0%B8%D0%B9 Дерево принятия решения]</ref>). Это дерево, как и уже описанный алгоритм локально взвешенного сглаживания, относится к ''робастным'' методам;
* Робастная регрессия (англ. ''robust regression''<ref>[https://en.wikipedia.org/wiki/Robust_regression Робастная регрессия]</ref>). В отличии от регрессии, использующей, например, метод наименьших квадратов, в этом алгоритме не строится идеализированное предположение, что вектор ошибок <math>\varepsilon</math> распределен согласно нормальному закону. Однако на практике зачастую имеют место отклонения от этого предположения. Тогда можно применить метод наименьших модулей (англ. ''Least Absolute Deviation, LAD ''<ref>[https://en.wikipedia.org/wiki/Least_absolute_deviations Метод наименьших модулей]</ref>) в случае, если распределение ошибок измерений подчиняется распределению Лапласа (англ. Laplace distribution <ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B0%D0%BF%D0%BB%D0%B0%D1%81%D0%B0 Распределение Лапласа]</ref>).
+
* [[Вариации регрессии|Робастная регрессия]] (англ. ''robust regression''<ref>[https://en.wikipedia.org/wiki/Robust_regression Робастная регрессия]</ref>). В отличие от регрессии, использующей, например, метод наименьших квадратов, в этом алгоритме не строится идеализированное предположение, что вектор ошибок <math>\varepsilon</math> распределен согласно нормальному закону. Однако на практике зачастую имеют место отклонения от этого предположения. Тогда можно применить метод наименьших модулей (англ. ''Least Absolute Deviation, LAD ''<ref>[https://en.wikipedia.org/wiki/Least_absolute_deviations Метод наименьших модулей]</ref>) в случае, если распределение ошибок измерений подчиняется распределению Лапласа (англ. Laplace distribution <ref>[https://ru.wikipedia.org/wiki/%D0%A0%D0%B0%D1%81%D0%BF%D1%80%D0%B5%D0%B4%D0%B5%D0%BB%D0%B5%D0%BD%D0%B8%D0%B5_%D0%9B%D0%B0%D0%BF%D0%BB%D0%B0%D1%81%D0%B0 Распределение Лапласа]</ref>).
  
 
==См.также==
 
==См.также==
* [[Аномалия]]
+
* [[Общие понятия]]
 
* [[Переобучение]]
 
* [[Переобучение]]
 +
* [[Дерево решений и случайный лес]]
  
 
==Примечания==
 
==Примечания==

Текущая версия на 19:40, 5 сентября 2019

Рис 1.График boxplot населения регионов России в 1990 году, где можно заметить 5 выбросов

Выброс (англ. outlier) — небольшая доля объектов во входных данных, которая сильно выделяется из общей выборки. Многие алгоритмы машинного обучения чувствительны к разбросу и распределению значений признаков обрабатываемых объектов. Соответственно, выбросы во входных данных могут исказить и ввести в заблуждение процесс обучения алгоритмов машинного обучения, что приводит к увеличению времени обучения, снижению точности моделей и, в конечном итоге, к снижению результатов. Даже до подготовки предсказательных моделей на основе обучающих данных выбросы могут приводить к ошибочным представлениям и в дальнейшем к ошибочной интерпретации собранных данных.

Виды выбросов[править]

Выбросы могут быть двух видов: одномерные и многомерные. Одномерные выбросы можно найти при рассмотрении распределения значений объектов в одномерном пространстве. Многомерные выбросы можно найти в [math]n[/math]-мерном пространстве (из [math]n[/math] объектов). Рассмотрение распределений в [math]n[/math]-мерных пространствах может быть очень сложным для человеческого мозга, поэтому необходимо обучить модель, чтобы сделать это.

Выбросы также могут отличаться в зависимости от окружающей среды: точечные выбросы, контекстуальные выбросы или коллективные выбросы. Точечные выбросы —

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

Причины возникновения выбросов[править]

  • Сбой работы оборудования;
  • Человеческий фактор;
  • Случайность;
  • Уникальные явления;
  • и др.

Примеры[править]

Рис 2. Хорошо обученная модель с выбросами
Рис 3. Переобученная модель на выбросах

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

Методы обнаружения и борьбы с выбросами[править]

Методы обнаружения выбросов[править]

  1. Экстремальный анализ данных(англ. extreme value analysis). При таком анализе не применяются какие-либо специальные статистические методы. Обычно этот метод применим для одномерного случая. Алгоритм использования таков:
    • Визуализировать данные, используя диаграммы и гистограммы для нахождения экстремальных значений;
    • Задействовать распределение, например Гауссовское, и найти значения, чье стандартное отклонение отличается в 2-3 раза от математического ожидания или в полтора раза от первой либо третьей квартилей;
    • Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели;
  2. Аппроксимирующий метод (англ. proximity method). Чуть более сложный метод, заключающийся в применении кластеризующих методов;
    • Использовать метод кластеризации для определения кластеров в данных;
    • Идентифицировать и отметить центроиды каждого кластера;
    • Соотнести кластеры с экземплярами данных, находящимися на фиксированном расстоянии или на процентном удалении от центроида соответствующего кластера;
    • Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели;
  3. Проецирующие методы (англ. projections methods). Эти методы довольно быстро и просто определяют выбросы в выборке;
    • Использовать один из проецирующих методов, например, метод главных компонент (англ. principal component analysis, PCA[1]) или самоорганизующиеся карты Кохонена(англ. self-organizing map, SOM[2]) или проекцию Саммона(англ. Sammon mapping, Sammon projection[3]), для суммирования обучающих данных в двух измерениях;
    • Визуализировать отображение;
    • Использовать критерий близости от проецируемых значений или от вектора таблицы кодирования (англ. codebook vector) для идентифицирования выбросов;
    • Отфильтровать предполагаемые выбросы из обучающей выборки и оценить работу модели.

Локально взвешенное сглаживание[править]

Локально взвешенное сглаживание (англ. LOcally WEighted Scatter plot Smoothing, LOWESS)[4]. Данная методика была предложена Кливлендом (Cleveland) в 1979 году для моделирования и сглаживания двумерных данных [math]X^m={(x_i, y_i)}_{i=1}^m[/math]. Эта техника предоставляет общий и гибкий подход для приближения двумерных данных. Локально-линейная модель может быть записана в виде: [math]y_t=\alpha_t+\beta_t x_t + \varepsilon_t[/math]. Эта модель может быть расширена на случай локально-квадратичной зависимости и на модель с большим числом независимых переменных. Параметры [math]\alpha_t[/math] и [math]\beta_t[/math] локально линейной модели оцениваются с помощью локально взвешенной регрессии, которая присваивает объекту тем больший вес, чем более близок он к объекту t. Степень сглаживания определяется параметром сглаживания [math]f[/math], который выбирает пользователь. Параметр [math]f[/math] указывает какая доля (англ. fraction) данных используется в процедуре. Если [math]f = 0.5[/math], то только половина данных используется для оценки и влияет на результат, и тогда мы получим умеренное сглаживание. С другой стороны, если [math]f = 0.8[/math], то используются восемьдесят процентов данных, и сглаживание намного сильнее. Во всех случаях веса данных тем больше, чем они ближе к объекту [math]t[/math].

Постановка задачи[править]

Пусть задано пространство объектов $X$ и множество возможных ответов [math]Y = \mathbb{R}[/math]. Существует неизвестная зависимость [math]y^*\colon X \to Y[/math], значения которой известны только на объектах обучающией выборки [math]X^l = (x_i\ ,\ y_i)^l_{i=1},\ y_i = y^*(x_i)[/math]. Требуется построить алгоритм [math]a\colon X\to Y[/math], аппроксимирующий неизвестную зависимость [math]y^*[/math]. Предполагается, что на множестве $X$ задана метрика [math]\rho(x,x')[/math].

Также стоит определить следующее. Для вычисления [math]a(x) = \alpha[/math] для [math]\forall x \in X[/math] воспользуемся методом наименьших квадратов: [math]Q(\alpha;X^l) = \sum_{i=1}^l \omega_i(x)(\alpha-y_i)^2 \rightarrow \underset{\alpha \in \mathbb{R}}{min}[/math], где [math]\omega_i[/math] — это вес $i$-ого объекта.

Веса [math]\omega_i[/math] разумно задать так, чтобы они убывали по мере увеличения расстояния [math]\rho(x,x_i)[/math]. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию [math]K:[0, \infty) \rightarrow [0, \infty)[/math], называемую ядром[на 28.01.19 не создан], и представить [math]\omega_i[/math] в следующем виде:


[math]\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )[/math], где $h$ — ширина окна.


Приравняв равной нулю производную [math]\frac{\partial Q}{\partial \alpha} = 0[/math] и выразив [math]\alpha[/math], получаем формулу Надарая-Ватсона[5] : [math]a_h(x;X^l) = \frac{\sum_{i=1}^{l} y_i\omega_i(x)}{\sum_{i=1}^{l} \omega_i(x)} = \frac{\sum_{i=1}^{l} y_iK\left(\frac{\rho(x,x_i)}{h} \right )}{\sum_{i=1}^{l} K\left(\frac{\rho(x,x_i)}{h} \right )}[/math].

Проблема выбросов в этой задаче[править]

Большие случайные ошибки в значениях [math]y_i[/math] сильно искажают оценку Надарая-Ватсона.

Идея[править]

Чем больше величина невязки [math]\varepsilon_i = \left | a_h\left (x_i;X^\ell\backslash\left \{x_i\right \} \right )-y_i\right |[/math], тем меньше должен быть вес i-го объекта [math]\omega_i(x)[/math].

Эвристика[править]

Домножить веса [math]\omega_i(x)[/math] на коэффициенты [math]\gamma_i = \widetilde{K}\left ( \varepsilon_i \right )[/math], где [math]\widetilde{K}\left ( \varepsilon \right )[/math] — ещё одно ядро, вообще говоря, отличное от [math]K\left ( \rho \right )[/math].

Псевдокод[править]

INPUT: [math]X^\ell[/math] - training sample;
OUTPUT: coefficents [math]\gamma_i, i = 1,...,\ell[/math];
________________________________________________________
1: initialization: [math]\gamma_i := 1, i = 1,...,\ell[/math]; //инициализация коэффициентов
2: do
3:   for each object [math]i = 1,...,\ell[/math];
4:     calculate cross-validation estimates: //вычислить оценки скользящего контроля
       [math]a_i := a_h(x_i;X^\ell\setminus{x_i}) = \frac{\sum\limits^{\ell}_{j=1,j\ne i} {y_j\gamma_j K \left ( \tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i \right)} \right )}}{\sum\limits^{\ell}_{j=1,j\ne i}{\gamma_j K\left(\tfrac{\rho\left (x_i,x_j \right )}{h\left (x_i\right )}\right )} }[/math]
5:   for each object [math]i = 1,...,\ell[/math];
6:     [math]\gamma_i := \widetilde{K}\left (\left | a_i-y_i \right | \right );[/math]
7: while coefficents [math]\gamma_i[/math] not stabilized; //пока коэффициенты не стабилизируются

Пример на языке R[править]

В этом примере мы попытаемся локально регрессировать и сгладить среднюю продолжительность безработицы на основе набора экономических данных из пакета $ggplot2$ языка $R$. Мы рассматриваем только первые 80 строк для этого анализа, чтобы легче было наблюдать степень сглаживания на приведенных ниже графиках.

data(economics, package="ggplot2")      # загрузка данных
economics$index <- 1:nrow(economics)    # создание индексной переменной
economics <- economics[1:80, ]          # усечение до 80 строк для более наглядного демонстрирования
loessMod10 <- loess(uempmed ~ index, data=economics, span=0.10) # 10% параметр сглаживания span
loessMod25 <- loess(uempmed ~ index, data=economics, span=0.25) # 25% параметр сглаживания span
loessMod50 <- loess(uempmed ~ index, data=economics, span=0.50) # 50% параметр сглаживания span
# получить сглаженный результат
smoothed10 <- predict(loessMod10) 
smoothed25 <- predict(loessMod25) 
smoothed50 <- predict(loessMod50)
# Нарисовать
plot(economics$uempmed, x=economics$date, type="l", main="Локально взвешенное сглаживание", xlab="Дата", ylab="Длительность безработицы")
lines(smoothed10, x=economics$date, col="red")
lines(smoothed25, x=economics$date, col="green")
lines(smoothed50, x=economics$date, col="blue")
Рис 5. На приведенном графике показано, что чем больше параметр сглаживания span, тем более сглаженной выглядит восстановленная регрессия

Другие алгоритмы борьбы с выбросами[править]

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

  • Дерево принятия решения (англ. decision tree[6]). Это дерево, как и уже описанный алгоритм локально взвешенного сглаживания, относится к робастным методам;
  • Робастная регрессия (англ. robust regression[7]). В отличие от регрессии, использующей, например, метод наименьших квадратов, в этом алгоритме не строится идеализированное предположение, что вектор ошибок [math]\varepsilon[/math] распределен согласно нормальному закону. Однако на практике зачастую имеют место отклонения от этого предположения. Тогда можно применить метод наименьших модулей (англ. Least Absolute Deviation, LAD [8]) в случае, если распределение ошибок измерений подчиняется распределению Лапласа (англ. Laplace distribution [9]).

См.также[править]

Примечания[править]

Источники информации[править]

  1. https://machinelearningmastery.com/how-to-identify-outliers-in-your-data/
  2. https://ru.coursera.org/lecture/vvedenie-mashinnoe-obuchenie/obnaruzhieniie-vybrosov-t9PG4