Skip to content
Назад к результатам поиска

Локальный фактор выбросов (Local Outlier Factor, LOF)

Автор метода
Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
Год
2000
Тип
Density-based anomaly detection (unsupervised)

Этот текст переведён машинным способом и ещё не проверен. Читать оригинал на английском

Размер шрифта

Что он делает?

Локальный фактор выбросов (LOF) — это основанный на плотности, неконтролируемый алгоритм обнаружения аномалий, представленный Бреунигом, Кригелем, Нг и Сандером в 2000 году.

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

Интуиция метода

Представьте карту города, где большинство людей живут в густонаселенных городских районах. Дом, стоящий в одиночестве в сельской местности, очевидно изолирован. Но LOF идет дальше: он может также пометить дом, расположенный в умеренно плотном пригороде, когда все его непосредственные соседи упакованы в еще более плотный кластер. Вместо того чтобы спрашивать «находится ли эта точка далеко от всего?», LOF спрашивает «является ли соседство этой точки намного разреженнее, чем соседства ее собственных соседей?» Точка, чьи соседи живут намного ближе друг к другу, чем сама точка, получает высокий балл LOF — сигнализируя о том, что это локальный выброс, даже если глобально она не находится в пустой области.

История

LOF был представлен Маркусом Бреунигом, Хансом-Петером Кригелем, Рэймондом Нг и Йоргом Сандером на конференции ACM SIGMOD 2000. Он решал признанное ограничение существующих методов обнаружения выбросов — то, что они полагались на глобальные пороговые значения расстояния и поэтому путали локальные аномалии с нормальными точками в менее плотных областях. В статье была представлена концепция локальной плотности достижимости и оценка LOF, которая быстро стала краеугольным камнем в обнаружении аномалий. С тех пор она была расширена многочисленными вариантами, включая LoOP (вероятности локальных выбросов), LOCI и COF, и включена в основные библиотеки машинного обучения. Статья ACM SIGMOD 2000 получила тысячи цитирований и считается одной из основополагающих работ в области интеллектуального анализа данных на основе плотности.

Когда применять

LOF подходит, когда ожидается, что аномалии будут возникать в кластерах различной плотности, и когда глобальный порог расстояния либо пропустит выбросы, скрытые в разреженных областях, либо ошибочно отметит точки в законно разреженных, но согласованных кластерах. Он работает в любом непрерывном признаковом пространстве со значимой метрикой расстояния и не требует размеченных примеров аномалий (полностью неконтролируемый). Он подходит для таких приложений, как обнаружение мошенничества, обнаружение сетевых вторжений, контроль качества производства и скрининг медицинских аномалий. Основные предположения заключаются в том, что нормальные точки образуют достаточно связные локальные соседства и что можно вычислить значимые попарные расстояния. LOF работает лучше всего, когда n составляет по крайней мере от десятков до нескольких сотен; для данных с очень высокой размерностью (проклятие размерности) расстояния становятся менее различительными, и сначала рекомендуется снижение размерности или отбор признаков.

Ограничения и замечания

  • Квадратичная временная сложность в наивной реализации делает его медленным на больших наборах данных без индексации приближенных ближайших соседей.
  • Чувствителен к выбору k: слишком малое k дает шумные оценки; слишком большое k размывает локальную структуру.
  • Производительность снижается в пространствах с очень высокой размерностью из-за проклятия размерности.
  • Не масштабируется естественным образом для потоковых или онлайн-данных без пересчета.
  • Не предоставляет модель, которую можно напрямую применить для оценки новых точек без доступа к обучающему набору.

Условия из источника не заменяют независимую научную проверку или валидацию аналитическим движком.

Сильные стороны

  • Обнаруживает локальные выбросы в наборах данных с кластерами различной плотности, где глобальные методы терпят неудачу.
  • Производит непрерывную, интерпретируемую оценку, а не жесткую бинарную метку, что позволяет гибко выбирать порог.
  • Полностью неконтролируемый: не требуются размеченные данные об аномалиях.
  • Применим к любому признаковому пространству с вычислимой метрикой расстояния, включая неевклидовы расстояния.
  • Устойчив к масштабу отдельных признаков при вычислении расстояний на стандартизированных данных.

Применение

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

Как это работает

Как это работает

1

Для каждой точки p алгоритм сначала вычисляет k-расстояние: расстояние до k-го ближайшего соседа точки p. Это определяет радиус локального соседства точки p. Все точки в пределах этого расстояния образуют k-соседство N_k(p). Выбор k контролирует масштаб, в котором оценивается локальность — малое k улавливает мелкозернистую локальную структуру, большее k сглаживает ее.

Формула
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } p
2

Расстояние достижимости от p до соседа o определяется как максимум k-расстояния точки o и фактического евклидова (или другого метрического) расстояния между p и o. Это сглаживание предотвращает нестабильность, когда две точки находятся чрезвычайно близко друг к другу: оно заменяет крошечные расстояния более широким охватом собственного соседства точки o, делая оценки плотности более надежными.

Формула
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}
3

Локальная плотность достижимости точки p (lrd) является обратной величиной среднего расстояния достижимости от p до всех ее k соседей. Точка, окруженная плотно упакованными соседями, имеет малое среднее расстояние достижимости и, следовательно, высокую lrd. Точка в разреженной области имеет большое среднее расстояние достижимости и низкую lrd.

Формула
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}
4

Балл LOF для точки p представляет собой среднее отношение значений lrd ее соседей к собственной lrd точки p. Если все соседи точки p имеют существенно более высокие значения lrd, чем сама точка p — что означает, что они находятся в более плотных подрегионах — отношение превышает 1, указывая на то, что p является локальным выбросом. Балл, близкий к 1, указывает на то, что p имеет примерно такую же плотность, как и ее окружение. Баллы, значительно превышающие 1, отмечают все более аномальные точки. Это сравнение с учетом локальности отличает LOF от методов, основанных только на расстоянии.

Формула
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}

Частые ошибки

  • Забывание стандартизировать или нормализовать признаки перед вычислением расстояний, что приводит к доминированию признаков с высокой дисперсией.
  • Использование единственного значения k без анализа чувствительности; лучшая практика — оценить несколько значений k.
  • Рассмотрение оценки LOF как вероятности — это относительная мера без фиксированной вероятностной интерпретации.
  • Игнорирование проклятия размерности в данных с высокой размерностью и ожидание, что LOF будет работать без предварительного снижения размерности.
  • Установка произвольного порога LOF (например, оценка > 1,5) без проверки распределения оценок для конкретного набора данных.

Часто задаваемые вопросы

Как выбрать правильное значение k?

Универсально оптимального k не существует. Общепринятая практика — оценить диапазон значений — обычно от 5 до 50 — и проверить, как изменяется распределение оценок и отмеченные выбросы. Анализ чувствительности по значениям k дает уверенность в том, что обнаруженные аномалии устойчивы к выбору. Знания предметной области о минимальном ожидаемом размере кластера также могут помочь определить нижнюю границу.

Что означает оценка LOF 1 по сравнению с 3?

Оценка, близкая к 1, означает, что точка имеет примерно такую же локальную плотность, как и ее соседи, и считается нормальной. Оценка, значительно превышающая 1 — часто интерпретируемая как выше 1,5 или 2 в зависимости от набора данных — указывает на то, что соседство точки намного разреженнее, чем соседства ее соседей. Универсального порогового значения не существует; порог должен выбираться путем изучения распределения оценок LOF для конкретного набора данных.

Может ли LOF оценивать новые, невиданные точки без переобучения?

LOF является трансдуктивным методом: он требует наличия обучающего набора для вычисления соседств и плотностей для любой новой точки. Для оценки новых наблюдений необходимо сохранить обучающий набор, и каждая новая точка должна быть вставлена для пересчета ее k-соседства относительно сохраненных точек обучения. Некоторые реализации предлагают эту функциональность, но она принципиально отличается от параметрических моделей, которые обучают компактную функцию оценки.

Как LOF сравнивается с Isolation Forest для обнаружения аномалий?

LOF использует оценку плотности на основе локальных соседств и сильнее, когда аномалии кластеризуются в локально разреженных областях неоднородного пространства. Isolation Forest использует случайное разделение и, как правило, быстрее и более масштабируем для больших наборов данных. Для высокоразмерных или очень больших наборов данных часто предпочтительнее Isolation Forest; для данных умеренной размерности с вариациями плотности LOF часто обеспечивает более тонкую дискриминацию.

Похожие методы

Источники

  1. Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.

    Открыть ссылку DOI
    Скопировано.
  2. Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.

    ISBN: 978-3-319-47577-6
    Скопировано.
  3. Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.

    ISBN: 978-0-387-84857-0
    Скопировано.