Anomaly Detection, Recommender Systems

https://www.coursera.org/course/ml

После линейной регрессии была логистическая регрессия.

А потом начались нейросети — Neural Networks.

Потом нас учили правильно применять изученные алгоритмы (Advice for Applying Machine Learning).

А потом нам рассказали про Support Vector Machines (SVMs) и Kernels.

А потом была неделя посвященная темам Clustering (K-Means) и Dimensionality Reduction (PCA).

А после были рассмотрены алгоритмы систем Anomaly Detection и, отдельно, Recommender Systems.

Сегодня посмотрим на Детектор Аномалий.

Детектор аномалий — Anomaly Detection, это довольно просто. К примеру, испытывая авиадвигатели и снимая с датчиков разные показатели (температура, вибрация, …) мы получаем массив данных. Задача детектора аномалий заключается в том, чтобы, обучившись на данных испытаний заведомо исправных двигателей, переваривать результаты испытаний новых двигателей и определять — данные в норме или найдена аномалия, суть — возможный дефект.

Или, к примеру, детектор аномалий может питаться данными о активности клиентов банка. После стадии обучения на массиве сведений о заведомо законопослушных и лояльных клиентов, детектор будет нам показывать клиентов, выходящих за пределы нормы — возможных мошенников.

Еще пример: мониторинг нагрузки на компьютеры датацентра, состояние компьютеров. Температура, ввод/вывод, нагрузка на процессор, сетевой трафик, … Обучаем детектор и оставляем его следить за порядком в датацентре. если что — он пришлет СМС-ку.

Модель, применяемая в детекторе аномалий, довольно простая. Вычисляется вероятность наличия аномалии путем оценки плотности. Эту мудрость лучше всего постигать глядя на картинку.

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

Установив пороговое значение эпсилон, мы отсекаем аномалии от нормальных значений.

Многие уже догадались, что в основе вычислений здесь находится Нормальное aka Гауссово распределение со средним значением мю и распределением сигма^2.

Соответственно, мю и сигма это параметры модели. Их надо вычислять для каждой фичи тренировочного датасета.

И весь алгоритм детектора аномалий тогда выглядит так: выбрать фичи наиболее явно отражающие аномалии; для каждой фичи обработать записи и найти параметры распределения — мю и сигма; вычислить произведение (продукт) вероятностей по каждой фиче интересующей записи. Если результат меньше порога эпсилон — мы имеем аномалию.

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

Чтобы получить такие метрики, мы разделим тренировочные данные на три датасета — трен.набор, набор кросс-валидации и тестовый набор.

В трен.наборе будут только нормальные записи, в наборах кросс-валидации и тестовом будут и нормальные и аномальные записи.

Используя разные фичи, разные пороговые значения эпсилон мы тестируем разные модели используя технику кросс-валидации и применяя метрики типа F1-score.

Возникает вопрос, если мы используем labeled данные для обучения машины, почему бы нам не использовать техники Supervised Learning? Ответ: детектор аномалий применяется там, где в наборах данных слишком мало записей о ненормальностях. При этом ненормальности бывают разных типов. Короче — недостаточно данных для четкого различения нормы от аномалии. Skewed classes.

Про правильный выбор фич для скармливания детектору аномалий.

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

Другой случай — значения фич могут коррелировать между собой. Например загрузка процессора и сетевой трафик. Тогда аномалия может детектироваться, если привнести в модель синтетическую фичу = CPU load / Network traffic.

Multivariate Gaussian Distribution.

В рассмотренном выше решении есть одна проблема. Распределения фич получаются сфероидными, грубо говоря. Вот иллюстрация проблемы

Чтобы сузить области нормального распределения придумали Multivariate Gaussian Distribution.

В этой модели используется вектор мю и матрица Сигма. С их помощью можно отражать корреляцию между фичами:

Учитывая такую математическую модель, алгоритм детектора аномалий получается такой

В принципе, оригинальная модель это просто частный случай мультивариативной модели

Значит ли это, что нужно всегда использовать мультивариативную модель? Нет. Если надо экономить вычислительльные ресурсы, или если количество фич больше чем количество записей трен.сета — необходимо использовать оригинальную модель детектора.

Вот и вся история про Anomaly Detection. По известным «правильным» записям данных мы вычисляем параметры гауссовых распределений. Потом смотрим, в какое место гауссового «колокола» попадают новые данные. Если выходят за пределы пороговых значений — имеем аномалию. Великое искусство заключается в том, чтобы выбрать и собрать нужные показания — фичи. Они должны быть способны отражать наличие аномалий. 

P.S.
А на практических занятиях мы писали программу, определяющую аномалии в состоянии серверов в датацентре.
Звучит, конечно, круто, но на практике все несколько проще, чем кажется. Всего-то реализовали модель и прогнали через нее заранее заготовленные данные

original post http://vasnake.blogspot.com/2014/07/anomaly-detection-recommender-systems.html