В этом видео мы продолжим
разговор о вероятностном подходе к обнаружению аномалий
и поговорим про непараметрические методы восстановления плотности.
В прошлом видео мы говорили про параметрический подход,
когда мы вводим некоторое параметрическое семейство распределений, например,
нормальное, и пытаемся подобрать такие его параметры,
при которых объекты обучающей выборки получают наибольшие возможные вероятности.
Это называется методом максимального правдоподобия.
Непараметрический подход имеет немножко другую идею.
Мы не будем вводить никаких семейств распределений,
а будем пытаться восстановить вид распределения, вид плотности,
глядя непосредственно на данные.
Давайте рассмотрим это на одном простом примере.
У нас есть одномерная выборка,
объекты которой обозначены черными засечками по оси X.
Этих объектов шесть штук.
Видно, что здесь, скорее всего, две компоненты.
Одна компонента слева имеет три или четыре точки,
вторая компонента справа имеет две точки.
Поместим с центром в каждой точке обучающей выборки небольшую гауссиану,
которая присваивает всем точкам на оси некоторые вероятности.
Чем ближе точка на оси к данной точке обучающей выборки,
тем больше будет вероятность.
А далее, в каждой точке просуммируем эти гауссианы.
Тогда мы получим вот такую оценку на плотность распределения.
Видно, что она вполне адекватная.
Она имеет пики с центрами в этих двух компонентах, и чем меньше объектов
концентрируется в данной точке, тем ниже будет там значение плотности.
Формально это можно сделать с помощью формулы Парзена-Розенблатта,
которая записывается вот так.
Такая непараметрическая оценка на плотность распределения — это по сути
сумма вот чего.
В каждой точке обучающей выборки xi мы
вычисляем разность между новым объектом, в котором мы хотим оценить плотность x,
и данной точкой обучающей выборки, x − xi, и делим на ширину окна,
на некоторый параметр h, про который мы поговорим чуть позже.
Далее от этой дроби мы вычисляем ядро K, которое по сути характеризует
вероятность того, что эти точки похожи друг на друга.
По идее, чем дальше точка x от точки xi,
тем меньше должно быть значение этого ядра K.
Дальше мы просто усредняем значения этих ядер по всей обучающей
выборке и еще делим на ширину окна h.
Итак, у нас K — это некий параметр метода, это ядро.
Ядром называется четная функция, то есть функция,
симметричная относительно оси ординат,
и к ней еще одно требование: интеграл от этой функции должен быть равен 1.
Если это требование не выполнено, то мы будет получать ненормированные плотности,
плотности, интеграл под которыми не равен 1.
Кстати, здесь, как вы уже поняли, мы говорим про одномерные выборки,
То есть x и xi — это просто вещественные числа.
Ядра можно выбирать самые разные.
Здесь нарисованы некоторые из них и представлены формулы для этих ядер.
Например, мы уже с вами употребляли гауссовское ядро,
которое обозначено красной кривой и, собственно,
записывается как гауссиана через экспоненту от минус квадрата аргумента.
Еще один параметр оценки Парзена-Розенблатта — это ширина окна h.
Давайте посмотрим, на что она влияет.
Как я уже говорил, чем больше значение аргумента ядра,
тем меньше будет значение самого ядра, потому что чем больше расстояние между
этими точками, тем меньшую вероятность мы хотим приписать.
Соответственно, если мы делим разницу между x и xi на какое-то
очень маленькое число h, то значение дроби будет большим.
Таким образом, если ширина окна маленькая,
то даже точки x, близкие к данной точке xi,
будут получать низкие значения вероятности, низкие значения ядра.
Если же значение h большое, то даже если разность x − xi большая,
то мы поделим ее на большое число, и в итоге вероятность, которую присвоим,
будет не такой уж маленькой.
Давайте посмотрим это на примере.
Есть некоторая выборка, которая обозначена синими засечками,
которая сгененерирована из нормального распределения.
И красной, черной и зеленой кривыми показаны непараметрические оценки с
гауссовским ядром для разных значений ширины окна.
Красная кривая соответствует очень маленькой ширине окна.
Из-за того, что ширина окна маленькая,
эта плотность очень чувствительна ко всем точкам.
Даже если в каком-то месте есть всего одна точка обучающей выборки,
плотность будет иметь всплеск.
Она получается не очень гладкой и скорее всего переобученной.
Черная кривая соответствует чуть более высокому значению ширины окна.
Видно, что оно скорее всего оптимально.
Эта плотность очень неплохо восстанавливает нормальное распределение,
из которого эти данные были сгенерированы.
Зеленая кривая соответствует оценки плотности с очень большой шириной окна.
Из-за того, что ширина окна большая,
эта плотность получается с очень большой дисперсией.
Даже точки на прямой, которые очень далеки от объектов обучающей выборки, получают
довольно большое значение плотности из-за того, что окно очень широкое.
Данный подход с непараметрическим оценивание
плотности хорошо обобщается на многомерный случай.
Нам нужно всего лишь заменить разность между точкой x и точкой xi на значение
метрики для этих двух точек, ρ от x и xi.
Ну, например, это может быть евклидова метрика или какая-то другая,
которая лучше подходит под данную задачу.
Также всю формулу нужно уже делить не на h, а на V от h.
Это некоторая нормировочная константа, которая нужна для того,
чтобы интеграл от этой плотности все еще был равен 1.
На самом деле, у многомерного непараметрического подхода к
восстановлению плотности есть одна большая проблема.
Давайте рассмотрим двумерную выборку.
Если бы эта выборка была спроецирована всего на одну ось, если бы мы оставили
только первый признак, то объектов было бы очень много, и мы по ним легко могли бы
восстановить плотность, потому что если бы мы разбили ось x на некоторые корзинки,
то в каждую корзинку попадало бы довольно много объектов этой выборки.
Если мы переходим в двумерное пространство и разбиваем все двумерное пространство
тоже на такие корзинки-клеточки,
то в каждую клеточку уже попадает в среднем гораздо меньше объектов выборки.
Из-за этого оценка плотности, скорее всего,
будет более шумной и менее репрезентативной.
Понятно, что если мы с таким же количеством объектов будем переходить в
еще более высокоразмерные пространства,
мы будем получать еще менее надежные оценки плотности.
На самом деле, число объектов, которое необходимо для того,
чтобы качественно оценить плотность непараметрическим методом,
растет экспоненциально по мере роста размерности.
То есть если, например, мы хотим восстановить такую плотность в
пространстве размерностью тысяча, нам понадобится очень и очень много объектов.
Таким образом, подход с непараметрическим восстановлением, скорее всего, будет
хорошо работать только в пространствах не очень высокой размерности.
Но если мы все-таки смогли восстановить плотность этим методом,
то дальше находить аномалии можно так же, как и с параметрическим подходом.
Мы объявляем аномалиями те объекты,
вероятность которых меньше некоторого порога t.
При этом порог t выбирается либо из каких-то определенных соображений,
либо на основе размеченных аномалий.
Итак, мы обсудили непараметрический подход к восстановлению плотности,
который можно использовать для восстановления очень сложных плотностей
с большим количеством пиков.
У формулы Парзена-Розенблатта, с помощью которой делается это восстановление,
есть два параметра — ядро и ширина окна.
Мы обсудили, на что влияют эти параметры и как их можно выбирать.
И также мы отметили одну проблему такого подхода.
Для того чтобы непараметрически восстановить плотность в многомерном
пространстве, может понадобиться очень большая выборка, что не всегда доступно.
В следующем видео мы поговорим о немножко другом подходе к поиску аномалий,
который основан на классификации выборки с помощью метода опорных векторов.
Evgeniy Riabenko
Evgeny Sokolov
Victor Kantor
Emeli Dral
Константин Воронцовдоктор физико-математических наук, профессор
