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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритмы борьбы с выбросами)
(Постановка задачи)
Строка 43: Строка 43:
 
Пусть задано пространство объектов 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>. <br>
 
Пусть задано пространство объектов 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>. <br>
 
Также стоит определить следующее. Для вычисления <math>a(x) = \alpha</math> при <math>\forall x \in 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>, называемую ядром, и представить <math>\omega_i</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-ого объекта. Веса \omega_i разумно задать так, чтобы они убывали по мере увеличения расстояния <math>\rho(x,x_i)</math>. Для этого можно ввести невозрастающую, гладкую, ограниченную функцию <math>K:[0, \infty) \rightarrow [0, \infty)</math>, называемую ядром, и представить <math>\omega_i</math> в следующем виде :
 
 
<math>\omega_i(x) = K\left(\frac{\rho(x,x_i)}{h} \right )</math>, где h — ширина окна.
 
<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>,получаем формулу Надарая-Ватсона :
 
Приравняв нулю производную <math>\frac{\partial Q}{\partial \alpha} = 0</math>, и, выразив <math>\alpha</math>,получаем формулу Надарая-Ватсона :
 
<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>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>X^\ell</math> - обучающая выборка;
 
  ВХОД: <math>X^\ell</math> - обучающая выборка;

Версия 04:28, 25 января 2019

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

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

Виды выбросов

Выбросы могут быть двух видов: одномерные и многомерные. Одномерные выбросы можно найти при рассмотрении распределения значений объектов в одном пространстве. Многомерные выбросы можно найти в n-мерном пространстве (из n-объектов). Рассмотрение распределений в n-мерных пространствах может быть очень сложным для человеческого мозга, поэтому необходимо обучить модель, чтобы сделать это.
Выбросы также могут отличаться в зависимости от окружающей среды: точечные выбросы, контекстуальные выбросы или коллективные выбросы. Точечные выбросы - это единичные точки данных, расположенные далеко от остальной части распределения. Контекстные выбросы могут представлять собой шум в данных, например, знаки препинания при выполнении анализа текста или сигнал фонового шума при распознавании речи. Коллективные выбросы могут быть подмножествами новшеств в данных, таких как сигнал, который может указывать на открытие новых явлений.

Причины возникновения выбросов

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

Примеры

Рис 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^*: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].
Также стоит определить следующее. Для вычисления [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], называемую ядром, и представить [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],получаем формулу Надарая-Ватсона : [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]X^\ell[/math] - обучающая выборка;
ВЫХОД: коэффиценты [math]\gamma_i, i = 1,...,\ell[/math];
________________________________________________________
1: инициализация: [math]\gamma_i := 1, i = 1,...,\ell[/math];
2: повторять
3:   для всех объектов [math]i = 1,...,\ell[/math];
4:     вычислить оценки скользящего контроля:
       [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];
6:     [math]\gamma_i := \widetilde{K}\left (\left | a_i-y_i \right | \right );[/math]
7: пока коэффиценты [math]\gamma_i[/math] не стабилизируются;

Пример

Допустим мы пытаемся восстановить зависимость, используя формулу Надарая-Ватсона[5] по некоторым данным из 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]. Таким образом выбросы будут нивелироваться автоматически при использовании данного подхода.
В статистике методы, устойчивые к нарушениям модельных предположений о данных, называются робастными. Метод локально взвешенного сглаживания относится к робастным методам, так как он устойчив к наличию небольшого количества выбросов.

  • Дерево принятия решения (англ. 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