Поиск аномалий

Предыдущая заметка закончилась моделями, которые являются плотностями: гауссовская смесь или вероятностный PCA говорят не только, где находятся данные, но и насколько вероятна каждая точка. Мошенническая транзакция, неисправный датчик, испорченная запись или вторжение — обычно точка, которую такая модель считает маловероятной. Поиск аномалий (anomaly detection) превращает это наблюдение в метод: приписать каждой точке оценку аномальности, высокую для точек, которые не вписываются, и отметить точки выше порога. Аномалии редки, разнообразны и часто прежде не встречались, поэтому размеченной обучающей выборки для них почти никогда нет, а у понятия «не вписывается» та же свобода, что была у понятия кластера. Эта заметка проходит по основным семействам оценок, у каждого из которых своё определение необычного: низкая плотность, далеко от соседей, быстро изолируется, вне выученной границы. Заканчивается она вопросом, который решает, полезен ли детектор на практике: как оценить его и выбрать порог, когда аномалий лишь горстка.

Обозначения. $x_1, \dots, x_n \in \mathbb R^d$ — обучающие точки, $s(x)$ — оценка аномальности (больше — аномальнее), $\tau$ — порог: $x$ отмечается, когда $s(x) > \tau$. $y \in \{0, 1\}$ отмечает настоящую аномалию, когда для оценки качества есть разметка. $\epsilon$ — предполагаемая доля аномалий (загрязнённость, contamination); параметр $\nu$ одноклассового SVM ниже — другая величина. $d_k(x)$ — расстояние от $x$ до её $k$-го ближайшего соседа среди обучающих точек.

Три постановки#

Что можно выучить, зависит от того, что размечено.

• С учителем. Размечены и нормальные точки, и аномалии. Это классификация с сильно неравными классами, которую решают инструментами из заметки о метриках классификации: веса классов, повторная выборка (resampling) и метрики, которые не поощряют постоянный ответ «норма». Такой детектор находит аномалии тех видов, которые ему показали, и может пропустить новые.
• С частичным привлечением учителя, или обнаружение новизны (novelty detection). Обучающая выборка содержит только нормальные точки, заведомо чистые. Модель описывает их, и новая точка отмечается, если не подходит под описание. Большинство методов ниже рассчитаны на эту постановку.
• Без учителя, или поиск выбросов (outlier detection). Обучающая выборка не размечена и загрязнена небольшой долей $\epsilon$ аномалий; задача — найти их в тех же данных. Методы те же, но они должны быть устойчивы к аномалиям, на которых обучаются, а порог часто задаёт $\epsilon$.

Большинство методов находят точечные аномалии (point anomalies) — отдельные точки, необычные сами по себе. Контекстная аномалия (contextual anomaly) необычна только в контексте: $-10\,^\circ$C — норма в январе и аномалия в июле. Такие случаи сводят к точечным аномалиям, добавляя контекст в признаки или моделируя условное распределение при данном контексте.

Оценки по плотности#

Самое прямое определение: аномалия — точка малой вероятности при модели нормальных данных. Подгоняем плотность $\hat p$ методом максимального правдоподобия и используем $s(x) = -\log \hat p(x)$.

Одна гауссиана. Для $\hat p = \mathcal N(\hat\mu, \hat\Sigma)$ минус логарифм плотности с точностью до констант равен половине квадрата расстояния Махаланобиса

$$s(x) = (x - \hat\mu)^\top \hat\Sigma^{-1} (x - \hat\mu) ,$$

— расстояния от среднего, измеренного в стандартных отклонениях вдоль каждой главной оси. Если нормальные данные гауссовские, а среднее и ковариация истинные, $s(x)$ имеет распределение хи-квадрат с $d$ степенями свободы, что даёт порог с известной долей ложных тревог. При $d = 2$ квантиль уровня 99% равен $9.21$: отмечая точки с $s(x) > 9.21$, то есть с расстоянием Махаланобиса больше $3.03$, мы отмечаем 1% нормальных точек. С оценёнными $\hat\mu$ и $\hat\Sigma$ закон хи-квадрат — лишь приближение, хорошее, когда $n$ велико по сравнению с $d$. В моделировании с $n = 30$ гауссовскими точками при $d = 2$ и обычной оценке ковариации тот же порог отмечает около 0.4% точек, по которым строились оценки, и 2.3% новых нормальных точек. Порог, откалиброванный на независимых нормальных валидационных данных, как в разделе об оценке качества ниже, снимает этот вопрос. Без гауссовского предположения неравенство Чебышёва всё равно ограничивает долю нормальных точек дальше $k$ стандартных отклонений в одномерном случае величиной $1/k^2$ — гораздо более осторожный порог.

Среднее и ковариационную матрицу смещают те самые аномалии, которые нужно обнаружить: несколько далёких точек раздувают $\hat\Sigma$ и прячут друг друга (маскировка, masking). Робастные оценки подгоняют ковариационную матрицу по самой сконцентрированной части данных, например оценка минимального определителя ковариации (minimum covariance determinant; Rousseeuw and Van Driessen, 1999). Они предполагают один кластер нормальных точек: на данных из двух кластеров из раздела «Код» робастная подгонка описывает только плотный кластер и отмечает весь второй, и её ROC-AUC падает с 0.886 для обычной гауссианы до 0.738.

Смесь. Нормальным данным с несколькими модами нужна гауссовская смесь с $s(x) = -\log \sum_k \pi_k \mathcal N(x \mid \mu_k, \Sigma_k)$; на тех же данных смесь из двух компонент достигает ROC-AUC 0.911. Другие варианты — ядерные оценки плотности и вероятностный PCA; для PCA ошибка восстановления $\lVert x - WW^\top x \rVert^2$, расстояние до главного подпространства, — распространённая оценка сама по себе.

У оценок по плотности две слабости. Для оценивания плотности нужно много точек на размерность, что ограничивает непараметрические оценки несколькими размерностями. И в высокой размерности высокая плотность не означает типичности: сэмплы стандартной гауссианы в 100 измерениях лежат в тонком сферическом слое далеко от моды, где плотность наибольшая, поэтому точка в моде была бы крайне необычной и всё же получила бы лучшую оценку. Глубокие генеративные модели показывают тот же эффект на изображениях: модели, обученные на CIFAR-10, приписывают номерам домов из SVHN более высокое правдоподобие, чем тестовым изображениям CIFAR-10, — парадокс правдоподобия, обсуждаемый в заметках о моделях, основанных на энергии, и о нормализующих потоках.

Оценки по расстояниям: ближайшие соседи и LOF#

Определение без плотности: аномалия далека от остальных точек. Оценка по $k$ ближайшим соседям — $s(x) = d_k(x)$, расстояние до $k$-го ближайшего соседа (Ramaswamy, Rastogi and Shim, 2000), или среднее расстояние до $k$ ближайших. Ей не нужна модель, она работает с любым расстоянием и подстраивается под кластеры любой формы. Она наследует слабости ближайших соседей: стоимость поиска соседей, зависимость от масштабирования признаков и расстояния, концентрирующиеся в высокой размерности.

К тому же она использует один глобальный масштаб. Рядом с плотным кластером точка на расстоянии 1 явно аномальна; внутри разреженного кластера расстояние 1 обычно. Единый порог на $d_k$ либо пропускает первую, либо отмечает край разреженного кластера. Локальный коэффициент выброса (local outlier factor, LOF) Breunig et al. (2000) сравнивает плотность каждой точки с плотностью её соседей. Пусть $N_k(x)$ — $k$ ближайших соседей $x$:

1. Расстояние достижимости (reachability distance) точки $x$ от соседа $o$ равно $\max\big(d_k(o),\, \lVert x - o \rVert\big)$: настоящее расстояние, но не меньше собственного $k$-расстояния точки $o$, что сглаживает статистику для точек, очень близких к $o$.
2. Локальная плотность достижимости (local reachability density) — величина, обратная среднему расстоянию достижимости от соседей, $\text{lrd}(x) = \Big(\frac1k \sum_{o \in N_k(x)} \max\big(d_k(o), \lVert x - o \rVert\big)\Big)^{-1}$.
3. Локальный коэффициент выброса — отношение плотности соседей к собственной плотности точки:

$$\text{LOF}(x) = \frac{1}{k} \sum_{o \in N_k(x)} \frac{\text{lrd}(o)}{\text{lrd}(x)} .$$

Глубоко внутри кластера, плотного или разреженного, точка так же плотна, как её соседи, и $\text{LOF} \approx 1$. У точки рядом с плотным кластером, но в разреженном месте, соседи гораздо плотнее её самой, и её LOF велик, хотя абсолютные расстояния малы.

Разобранный пример. На прямой возьмём $k = 1$ и точки $0, 1, 2, 10, 11$. У каждой точки, кроме $10$ и $11$, ближайший сосед на расстоянии 1; у $10$ и $11$ тоже (они соседи друг друга). Все $d_1 = 1$, все расстояния достижимости равны 1, все плотности равны 1, и каждый LOF равен 1: две хорошо разделённые группы одинаковой плотности не содержат локальных выбросов. Добавим точку $5$: её ближайший сосед — $2$ на расстоянии 3, поэтому $\text{lrd}(5) = 1/\max(d_1(2), 3) = 1/3$, тогда как $\text{lrd}(2) = 1$, и $\text{LOF}(5) = 1/(1/3) = 3$.

Рисунок

Четыре оценки аномальности на одних данных

Рисунок сопоставляет четыре оценки на данных, построенных так, чтобы их различить: плотный и разреженный кластеры, шесть аномалий вдали от всего и две рядом с плотным кластером. Две локальные аномалии ближе к своим соседям, чем крайние точки разреженного кластера к своим, поэтому расстояние до 10-го соседа ставит крайние точки первыми; LOF, сравнивающий плотности локально, — единственная оценка, которая ставит наверх все восемь аномалий. Сравнение построено, чтобы показать, что добавляет LOF, а не чтобы ранжировать методы в целом: на равномерно распределённых аномалиях из раздела «Код» у LOF наименьший ROC-AUC среди оценок по расстояниям.

Изолирующий лес#

Оценки до сих пор моделировали нормальные данные и измеряли расстояние до них. Изолирующий лес (isolation forest; Liu, Ting and Zhou, 2008) измеряет, насколько легко отделить точку от остальных. Рекурсивно разбиваем данные случайным образом: выбираем случайную координату и порог, равномерно распределённый между минимумом и максимумом текущих точек по этой координате, и продолжаем в каждой части, пока каждая точка не останется одна. Аномалию, немногочисленную и непохожую, обычно отсекают за несколько разрезов; точке в плотной области их нужно много. Число разрезов на пути от корня до листа точки, её длина пути (path length) $h(x)$, и есть оценка, усреднённая по многим случайным деревьям, как в случайных лесах из заметки о бэггинге.

Рисунок

Изоляция случайными разрезами

Длине пути нужен эталонный масштаб, потому что деревья на большем числе точек глубже. Дерево, изолирующее $n$ точек, имеет $n - 1$ внутренних узлов, как двоичное дерево поиска с $n - 1$ ключами, а для случайных двоичных деревьев поиска известна средняя глубина неуспешного поиска, который заканчивается в одном из $n$ листьев (Liu et al., раздел 2, со ссылкой на Preiss). Она даёт нормировку

$$c(n) = 2H(n - 1) - \frac{2(n - 1)}{n}, \qquad H(i) = 1 + \frac12 + \dots + \frac1i ,$$

— среднюю длину пути точки в дереве на $n$ точках. Поскольку $H(n - 1) = H(n) - 1/n$, та же величина равна $c(n) = 2H(n) - 2$. Оценка аномальности равна

$$s(x, n) = 2^{-\mathbb E[h(x)] / c(n)} ,$$

что даёт $0.5$, когда средняя длина пути равна $c(n)$, стремится к 1, когда она уменьшается до 0, и стремится к 0, когда она растёт до $n - 1$. Liu et al. читают оценку так: точки с $s$, близкой к 1, — явные аномалии, точки с $s$ заметно ниже $0.5$ нормальны, а когда у всех точек $s \approx 0.5$, в выборке нет явных аномалий (раздел 2). Это прочтение оценки изоляции, а не откалиброванная вероятность того, что точка аномальна: что означает $s = 0.7$, зависит от данных, и порог по $s$ требует калибровки, как и для любой другой оценки.

Разобранный пример. При $n = 256$ имеем $H(255) = 6.1204$, поэтому $c(256) = 2 \cdot 6.1204 - 2 \cdot 255/256 = 10.249$. Точка, изолируемая в среднем за 3 разреза, получает $2^{-3/10.249} = 0.816$; точка, которой нужно 10.249 разреза, — $0.5$; точка, которой нужно 15, — $2^{-15/10.249} = 0.363$. В статье гармоническое число приближается как $H(i) \approx \ln i + 0.5772$ (постоянная Эйлера), что даёт $c(256) = 10.245$ — пренебрежимая разница. При малых $n$ приближение плохое: $c(3) = 2(1 + \frac12) - \frac43 = 1.667$ точно против $1.207$ с логарифмом. Это важно для поправки ниже, которая применяется к листьям с несколькими точками; scikit-learn использует точные значения $c(1) = 0$ и $c(2) = 1$ и логарифмическое приближение начиная с $n = 3$.

Три конструктивных решения делают метод быстрым и устойчивым (раздел 4). Каждое дерево строится на подвыборке из $\psi$ точек, взятых без возвращения, по умолчанию $\psi = 256$, при $t = 100$ деревьях. Маленькие подвыборки помогают: вокруг аномалий теснится меньше нормальных точек (затопление, swamping), и меньше аномалий заслоняют друг друга (маскировка). Деревья строятся только до ограничения высоты (height limit) $\lceil \log_2 \psi \rceil = 8$, средней глубины, потому что важны только короткие пути; точка, дошедшая до листа, в котором ещё $m > 1$ точек, получает $h(x) = e + c(m)$ — свою глубину $e$ плюс среднюю глубину недостроенного поддерева. И оценка использует только сравнения, без расстояний, поэтому обучение стоит $O(t \psi \log \psi)$, вычисление оценки — $O(t \log \psi)$ на точку, независимо от $n$, а метод нечувствителен к масштабу каждого признака. Его слабость — разрезы вдоль осей: аномалии, которые отличаются от данных только вдоль диагонали или сидят в дыре, окружённой нормальными точками, трудно изолировать разрезами, параллельными осям, а карта оценок показывает артефакты, выровненные по осям. Рисунок сравнения выше показывает и глобальный взгляд: как и расстояние до соседа, изолирующий лес пропускает две локальные аномалии.

Одноклассовый SVM#

Одноклассовый SVM (one-class SVM; Schölkopf et al., 2001) выучивает не оценку, а границу вокруг нормальных данных. В пространстве признаков ядра он отделяет отображённые точки от начала координат с наибольшим отступом (margin), допуская часть точек по неверную сторону:

$$\min_{w,\, \xi,\, \rho}\ \frac12 \lVert w \rVert^2 + \frac{1}{\nu n} \sum_{i=1}^n \xi_i - \rho \quad \text{при условии} \quad w^\top \varphi(x_i) \ge \rho - \xi_i,\quad \xi_i \ge 0 .$$

Решающая функция — $f(x) = w^\top \varphi(x) - \rho$, отрицательная для аномалий, и, как у метода опорных векторов, двойственная задача зависит от данных только через ядро: $f(x) = \sum_i \alpha_i k(x_i, x) - \rho$ с $0 \le \alpha_i \le 1/(\nu n)$ и $\sum_i \alpha_i = 1$. У параметра $\nu \in (0, 1]$ прямой смысл, ν-свойство (ν-property): это верхняя граница доли обучающих точек вне границы и нижняя граница доли опорных векторов. В разделе «Код» при $\nu = 0.2$ вне границы оказываются 18.7% обучающих точек, а опорными векторами являются 21.4%. Поэтому $\nu$ — настройка оптимизации, а не истинная доля аномалий: он определяет, сколько обучающих точек граница оставляет снаружи, каким бы ни был их статус, а настоящая загрязнённость $\epsilon$ может быть больше или меньше. Положить $\nu = \epsilon$ разумно, когда $\epsilon$ известна, но это выбор, а не тождество. С гауссовским ядром $f$ — взвешенная сумма «горбов» вокруг опорных векторов минус порог; при $\nu = 1$ ограничения заставляют все $\alpha_i = 1/n$, и $f$ становится ядерной оценкой плотности с порогом. Метод описывает границы любой формы, но ширину ядра и $\nu$ приходится выбирать без разметки, стоимость растёт быстрее, чем линейно по $n$, и, как всем ядерным методам, ему нужны масштабированные признаки.

Оценка качества при редкой разметке#

Даже если при обучении разметка не используется, для оценки качества она нужна: набор точек с известным статусом, часто несколько сотен нормальных точек и несколько десятков аномалий, собранных по инцидентам. Три обстоятельства отличают такую оценку от обычной классификации.

Доля правильных ответов бессмысленна. При 1% аномалий детектор, который ничего не отмечает, даёт 99% правильных ответов (accuracy). Детекторы сравнивают по тому, как они ранжируют точки, поскольку порог выбирается позже: по ROC-AUC, вероятности того, что случайная аномалия получит оценку выше случайной нормальной точки, как выведено в заметке о метриках классификации, и по средней точности (average precision, AP) — площади под кривой точности–полноты.

ROC-AUC льстит редким положительным примерам. Доля ложноположительных срабатываний делится на большое число нормальных точек, поэтому у детектора может быть малая доля ложноположительных срабатываний, и всё же его настоящие тревоги будут погребены среди ложных. Точность показывает это прямо, по расчёту с базовой частотой: при 1% аномалий у детектора, который находит 90% из них при доле ложноположительных срабатываний 1%, точность равна

$$\frac{0.9 \cdot 0.01}{0.9 \cdot 0.01 + 0.01 \cdot 0.99} = 0.476 ,$$

так что половина его тревог ложные. На 513 точках из раздела «Код», среди которых 13 аномалий, значения ROC-AUC методов лежат между 0.74 и 0.92 и выглядят похожими; их значения AP лежат между 0.15 и 0.69 и различают методы гораздо сильнее. Для редких аномалий стоит приводить кривую точности–полноты и AP (Saito and Rehmsmeier, 2015; раздел о кривой точности–полноты заметки о метриках), а при фиксированном бюджете тревог — точность среди $k$ первых тревог.

Мало меток — широкие доверительные интервалы. При 13 аномалиях полнота меняется шагами по 7.7%, и разница в одно-два обнаружения между методами — это шум. Насколько велик этот шум, показывает бутстрэп по размеченным точкам, как в заметке о доверительных интервалах.

Выбор порога. Оценка ранжирует; порог решает, сколько точек станут тревогами. Три распространённых способа:

• По загрязнённости. В постановке без учителя отметить долю $\epsilon$ обучающих точек с наибольшими оценками. Это делает параметр contamination в scikit-learn; ему нужна догадка о величине $\epsilon$.
• По доле ложных тревог. В постановке обнаружения новизны вычислить оценки на чистых валидационных данных и поставить $\tau$ на их квантиль уровня $1 - \alpha$; тогда будет отмечаться примерно доля $\alpha$ будущих нормальных точек. В разделе «Код» квантиль уровня 99% по 10 000 оценок чистых валидационных данных даёт долю ложных тревог 0.9% на свежих нормальных данных при целевом 1%.
• По стоимости или пропускной способности. Если аналитик может проверить 50 тревог в день, порог — оценка 50-й точки; если пропущенная аномалия стоит ста ложных тревог, применимо правило стоимостей из заметки о метриках классификации, но этому правилу нужна откалиброванная вероятность аномальности, а оценки выше вероятностями не являются. Либо сначала откалибруйте оценку на размеченных валидационных данных, либо переберите пороги на таких данных и выберите порог с наименьшей суммарной стоимостью.

Что изменилось#

	Плотность (гауссиана, смесь)	Расстояние kNN	LOF	Изолирующий лес	Одноклассовый SVM
Аномалия — это точка	маловероятная при модели	далёкая от соседей	более разреженная, чем соседи	быстро изолируемая	вне выученной границы
Масштаб	глобальный	глобальный	локальный	глобальный	глобальный
Нужно	семейство плотностей	расстояние	расстояние, $k$	только сравнения	ядро, $\nu$
Стоимость оценки	дёшево	поиск соседей	поиск соседей	$O(t \log \psi)$	сумма ядер по опорным векторам
Порог	квантиль хи-квадрат, правдоподобие	квантиль	LOF заметно больше 1	$s$ около 1	$f(x) < 0$, долю ограничивает $\nu$
Слабое место	высокая размерность, мультимодальные данные	разная плотность	высокая размерность, стоимость	диагональная структура, локальные аномалии	выбор ядра, большое $n$

Ограничения#

• Ни одно определение не подходит для всех аномалий. Каждая оценка закладывает одно представление о необычном; аномалии другого рода проходят незамеченными. Практический ответ — комбинировать оценки или выбирать по размеченным инцидентам.
• Высокая размерность. Плотности нельзя оценить, расстояния концентрируются, а нерелевантные признаки прячут релевантные; оценки обычно вычисляют на нескольких главных компонентах или на выученных представлениях.
• Загрязнённые обучающие данные. Модели, обученные на данных с аномалиями, выучивают их как норму, а робастные оценки предполагают структуру (один кластер), которой может не быть.
• Редкая и меняющаяся разметка. Оценка качества опирается на несколько десятков известных аномалий, доверительные интервалы широки, а после внедрения появляются новые виды аномалий. Детектор нуждается в мониторинге, как любая модель, у которой дрейфует распределение входов.
• Оценка — не объяснение. Аналитику нужно знать, почему точка отмечена; LOF и изолирующий лес дают число, а не причину.

Что нужно запомнить#

• Поиск аномалий с учителем — несбалансированная классификация; обнаружение новизны учится на чистых нормальных данных; поиск выбросов находит аномалии в загрязнённых данных без разметки.
• Оценки по плотности используют $-\log \hat p(x)$; для одной гауссианы это расстояние Махаланобиса с порогом по хи-квадрат, точным при известных параметрах и приближённым при оценённых. В высокой размерности высокая плотность не означает типичности.
• Расстояние до $k$-го ближайшего соседа отмечает точки, далёкие от соседей, в глобальном масштабе; LOF сравнивает локальную плотность точки с плотностью её соседей и находит локальные выбросы.
• Изолирующий лес даёт оценку $s = 2^{-\mathbb E[h(x)]/c(n)}$ с $c(n) = 2H(n - 1) - 2(n - 1)/n = 2H(n) - 2$; короткие пути означают аномалии, $s = 0.5$ — средний случай. Подвыборки по 256 точек и ограничение высоты 8 делают его быстрым.
• Одноклассовый SVM отделяет данные от начала координат в пространстве признаков; $\nu$ ограничивает долю обучающих точек вне границы сверху, а долю опорных векторов — снизу.
• При редких аномалиях детекторы сравнивают по средней точности, а не по доле правильных ответов или одному ROC-AUC; точностью управляет базовая частота.
• Порог выбирают по загрязнённости, по целевой доле ложных тревог на чистых данных или по стоимости и пропускной способности проверки тревог.

Код#

Нормировка изолирующего леса, порог по хи-квадрат, семь оценок на загрязнённых данных, ν-свойство, базовая частота и порог по квантилю:

import numpy as np
from scipy import stats
from sklearn.covariance import EmpiricalCovariance, MinCovDet
from sklearn.mixture import GaussianMixture
from sklearn.neighbors import NearestNeighbors, LocalOutlierFactor
from sklearn.ensemble import IsolationForest
from sklearn.svm import OneClassSVM
from sklearn.metrics import roc_auc_score, average_precision_score

# нормировка изолирующего леса c(n) = 2 H(n - 1) - 2 (n - 1) / n, точно и с H(i) ~ ln i + 0.5772
H = lambda m: sum(1 / i for i in range(1, m + 1))
c = lambda n: 2 * H(n - 1) - 2 * (n - 1) / n
c_ln = lambda n: 2 * (np.log(n - 1) + np.euler_gamma) - 2 * (n - 1) / n
print([round(c(n), 4) for n in (3, 256)], [round(float(c_ln(n)), 4) for n in (3, 256)], round(2 * H(256) - 2, 4))
# [1.6667, 10.2487] [1.2074, 10.2448] 10.2487: c(n) = 2 H(n) - 2

# гауссовский порог: квадрат расстояния Махаланобиса против квантиля хи-квадрат, d = 2
print(round(stats.chi2(2).ppf(0.99), 2), round(np.sqrt(stats.chi2(2).ppf(0.99)), 2))    # 9.21 3.03

# загрязнённые данные: плотный и разреженный кластеры, 13 равномерных аномалий (2.5%); метки только для оценки качества
rng = np.random.default_rng(0)
X = np.vstack([rng.normal([0, 0], 0.3, (300, 2)), rng.normal([4, 3], 1.2, (200, 2)), rng.uniform([-4, -4], [9, 8], (13, 2))])
y = np.r_[np.zeros(500), np.ones(13)]
d10 = NearestNeighbors(n_neighbors=11).fit(X).kneighbors(X)[0][:, 10]          # расстояние до 10-го соседа
scores = {
    'gaussian': EmpiricalCovariance().fit(X).mahalanobis(X),
    'robust gaussian': MinCovDet(random_state=0).fit(X).mahalanobis(X),
    'gmm, K=2': -GaussianMixture(2, random_state=0).fit(X).score_samples(X),
    '10-nn distance': d10,
    'lof': -LocalOutlierFactor(n_neighbors=10).fit(X).negative_outlier_factor_,
    'isolation forest': -IsolationForest(random_state=0).fit(X).score_samples(X),
    'one-class svm': -OneClassSVM(nu=0.05, gamma=0.5).fit(X).decision_function(X),
}
for name, s in scores.items():
    print(f'{name:17s} ROC-AUC {roc_auc_score(y, s):.3f}  AP {average_precision_score(y, s):.3f}')
# gaussian          ROC-AUC 0.886  AP 0.512
# robust gaussian   ROC-AUC 0.738  AP 0.145
# gmm, K=2          ROC-AUC 0.911  AP 0.644
# 10-nn distance    ROC-AUC 0.915  AP 0.693
# lof               ROC-AUC 0.871  AP 0.515
# isolation forest  ROC-AUC 0.915  AP 0.636
# one-class svm     ROC-AUC 0.893  AP 0.516

# nu-свойство одноклассового SVM при жёстком допуске: доля вне границы <= nu <= доля опорных векторов
for nu in (0.05, 0.2):
    oc = OneClassSVM(nu=nu, gamma=0.5, tol=1e-7).fit(X)
    print(nu, round((oc.decision_function(X) < -1e-6).mean(), 3), round(len(oc.support_) / len(X), 3))
# 0.05 0.023 0.086 | 0.2 0.187 0.214

# редкие аномалии: точность детектора с полнотой 0.9 и долей ложных тревог 0.01 при базовой частоте 1%
print(round(0.9 * 0.01 / (0.9 * 0.01 + 0.01 * 0.99), 3))         # 0.476

# порог для целевой доли ложных тревог: квантиль уровня 99% оценок на чистых валидационных данных
normal = lambda m: np.vstack([rng.normal([0, 0], 0.3, (m // 2, 2)), rng.normal([4, 3], 1.2, (m // 2, 2))])
iso = IsolationForest(random_state=0).fit(normal(1000))
tau = np.quantile(-iso.score_samples(normal(10000)), 0.99)
print(round((-iso.score_samples(normal(20000)) > tau).mean(), 4))   # 0.0087: доля ложных тревог на свежих нормальных данных

score_samples изолирующего леса в scikit-learn возвращает $-s(x, \psi)$, поэтому его значение со знаком минус — оценка из статьи.

Дальше#

Каждый детектор в этой заметке заканчивается оценкой для каждой точки, и на практике аналитик читает список точек сверху: важно, чтобы настоящие аномалии шли первыми, а не само значение оценки. Это задача ранжирования, решённая здесь без разметки. Следующая заметка решает её с учителем: поисковые системы, каталоги и поисковые модели учатся упорядочивать объекты по меткам релевантности, с метриками и функциями потерь, построенными для верха списка.

Литература#

• V. Chandola, A. Banerjee, V. Kumar. Anomaly detection: A survey. ACM Computing Surveys, 41(3), 1–58, 2009.
• P. J. Rousseeuw, K. Van Driessen. A Fast Algorithm for the Minimum Covariance Determinant Estimator. Technometrics, 41(3), 212–223, 1999.
• S. Ramaswamy, R. Rastogi, K. Shim. Efficient algorithms for mining outliers from large data sets. SIGMOD, 427–438, 2000.
• M. M. Breunig, H.-P. Kriegel, R. T. Ng, J. Sander. LOF: Identifying Density-Based Local Outliers. SIGMOD, 93–104, 2000.
• F. T. Liu, K. M. Ting, Z.-H. Zhou. Isolation Forest. ICDM, 413–422, 2008. Раздел 2 (длина пути, $c(n)$ и оценка), раздел 3 (затопление и маскировка), раздел 4 (обучение и оценка, $\psi = 256$, $t = 100$, ограничение высоты).
• F. T. Liu, K. M. Ting, Z.-H. Zhou. Isolation-Based Anomaly Detection. ACM Transactions on Knowledge Discovery from Data, 6(1), 1–39, 2012.
• B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola, R. C. Williamson. Estimating the Support of a High-Dimensional Distribution. Neural Computation, 13(7), 1443–1471, 2001.
• E. Nalisnick, A. Matsukawa, Y. W. Teh, D. Gorur, B. Lakshminarayanan. Do Deep Generative Models Know What They Don’t Know? ICLR, 2019.
• T. Saito, M. Rehmsmeier. The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets. PLOS ONE, 10(3), e0118432, 2015.
• E. Sokolov et al. Машинное обучение (HSE), конспекты лекций, лекция 16: одноклассовые методы и поиск аномалий (2025).