Фактор локального выброса - Local outlier factor

Часть серии по
Машинное обучение
и интеллектуальный анализ данных
Многослойная нейронная сеть-Vector-Blank.svg
Проблемы
Обучение с учителем
( классификация  • регрессия )
Кластеризация
Снижение размерности
Структурированный прогноз
Обнаружение аномалий
Искусственная нейронная сеть
Обучение с подкреплением
Теория
Площадки для машинного обучения
Статьи по Теме

В обнаружении аномалий , то фактор локального останца ( МВА ) представляет собой алгоритм , предложенный Markus M. Breunig, Hans-Peter Кригель , Raymond T. Ng и Йорг Sander в 2000 году для нахождения аномальных точек данных пути измерения локального отклонения заданной точки данных по отношению к своим соседям.

LOF разделяет некоторые концепции с DBSCAN и OPTICS, такие как понятия «базовое расстояние» и «расстояние достижимости», которые используются для оценки локальной плотности.

Основная идея

Основная идея LOF: сравнение локальной плотности точки с плотностями ее соседей. А имеет гораздо меньшую плотность, чем его соседи.

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

Локальная плотность оценивается типичным расстоянием, на котором точка может быть «достигнута» от ее соседей. Определение «расстояния достижимости», используемое в LOF, является дополнительной мерой для получения более стабильных результатов в кластерах. «Расстояние достижимости», используемое LOF, имеет некоторые тонкие детали, которые часто обнаруживаются неверными во вторичных источниках, например, в учебнике Этхема Алпайдина.

Формальный

Пусть k- расстояние ( A ) будет расстоянием от объекта A до k-го ближайшего соседа. Обратите внимание, что набор из k ближайших соседей включает в себя все объекты на этом расстоянии, которое в случае «привязки» может быть больше, чем k объектов. Обозначим множество k ближайших соседей как N k (A) .

Иллюстрация расстояния достижимости. Объекты B и C имеют одинаковое расстояние достижимости ( k = 3 ), в то время как D не является k ближайшим соседом

Это расстояние используется для определения того, что называется расстоянием достижимости :

расстояние достижимости k ( A , B ) = max { k -расстояние ( B ), d ( A , B )}

На словах достижимости расстояние от объекта A от B является истинным расстоянием между двумя объектов, но , по крайней мере, к -расстоянию из B . Объекты, которые принадлежат k ближайшим соседям B («ядро» B , см. Кластерный анализ DBSCAN ), считаются одинаково удаленными. Причина такого расстояния - получение более стабильных результатов . Обратите внимание, что это не расстояние в математическом определении, поскольку оно не симметрично. (Хотя использование k- расстояния (A) является распространенной ошибкой , это дает немного другой метод, называемый Simplified-LOF)

Плотность локальной достижимости объекта A определяется выражением

lrd k (A): = 1 / ( Σ B ∈ N k (A) расстояние достижимости k (A, B)/| N k (A) |)

которое является обратным среднему расстоянию достижимости объекта A от его соседей. Обратите внимание, что это не средняя достижимость соседей от A (которая по определению будет k- расстоянием (A) ), а расстояние, на котором A может быть «достигнут» от своих соседей. При дублировании точек это значение может стать бесконечным.

Затем локальные плотности достижимости сравниваются с плотностями соседей, используя

LOF k (A): =Σ B ∈ N k (A)lrd k (B)/lrd k (А)/| N k (A) | знак равно Σ B ∈ N k (A) lrd k (B)/| N k (A) | · Lrd k (А)

которая представляет собой среднюю локальную плотность достижимости соседей , деленную на собственную локальную плотность достижимости объекта. Значение приблизительно 1 указывает, что объект сопоставим со своими соседями (и, следовательно, не является выбросом). Значение ниже 1 указывает на более плотную область (которая может быть выпадением), тогда как значения, значительно превышающие 1, указывают на выбросы.

LOF (k) ~ 1 означает такую ​​же плотность, как у соседей,

LOF (k) <1 означает более высокую плотность, чем у соседей (Inlier),

LOF (k)> 1 означает более низкую плотность, чем у соседей (выброс)

Преимущества

Показатели LOF, визуализированные ELKI . Хотя верхний правый кластер имеет сопоставимую плотность с выбросами вблизи нижнего левого кластера, они обнаруживаются правильно.

Благодаря локальному подходу LOF может идентифицировать выбросы в наборе данных, которые не были бы выбросами в другой области набора данных. Например, точка на «маленьком» расстоянии от очень плотного кластера является выбросом, в то время как точка в разреженном кластере может иметь аналогичные расстояния до своих соседей.

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

Семейство методов LOF можно легко обобщить и затем применить к различным другим задачам, таким как обнаружение выбросов в географических данных, видеопотоках или авторских сетях.

Недостатки и расширения

Полученные значения являются частными, и их трудно интерпретировать. Значение 1 или даже меньше указывает на явный выброс, но нет четкого правила, когда точка является выбросом. В одном наборе данных значение 1,1 может уже быть выбросом, в другом наборе данных и параметризации (с сильными локальными колебаниями) значение 2 все еще может быть выбросом. Эти различия также могут возникать в наборе данных из-за местоположения метода. Существуют расширения LOF, которые пытаются улучшить LOF в следующих аспектах:

  • Функция сбора данных для обнаружения выбросов запускает LOF на нескольких проекциях и объединяет результаты для улучшения качества обнаружения в больших измерениях. Это первый подход к ансамблевому обучению для обнаружения выбросов, другие варианты см.
  • Вероятность локального выброса (LoOP) - это метод, полученный из LOF, но использующий недорогую локальную статистику, чтобы стать менее чувствительным к выбору параметра k . Кроме того, полученные значения масштабируются до диапазона значений [0: 1] .
  • Интерпретация и унификация оценок выбросов предлагает нормализацию оценок выбросов LOF к интервалу [0: 1] с использованием статистического масштабирования для повышения удобства использования и может быть замечена как улучшенная версия идей LoOP.
  • On Evaluation of Outlier Rankings и Outlier Scores предлагает методы для измерения сходства и разнообразия методов для построения расширенных ансамблей обнаружения выбросов с использованием вариантов LOF и других алгоритмов и улучшения подхода Feature Bagging, описанного выше.
  • Пересмотрено обнаружение локальных выбросов: в обобщенном представлении о местности с приложениями к пространственному, видео и обнаружению выбросов в сети обсуждается общая закономерность в различных методах обнаружения локальных выбросов (включая, например, LOF, упрощенную версию LOF и LoOP) и отрывки из этого в общие рамки. Затем эта структура применяется, например, для обнаружения выбросов в географических данных, видеопотоках и авторских сетях.

Рекомендации

  1. ^ Breunig, MM; Кригель, Х.-П. ; Ng, RT; Сандер, Дж. (2000). LOF: Определение локальных выбросов на основе плотности (PDF) . Материалы Международной конференции ACM SIGMOD 2000 по управлению данными . SIGMOD . С. 93–104. DOI : 10.1145 / 335191.335388 . ISBN 1-58113-217-4.
  2. ^ Breunig, MM; Кригель, Х.-П. ; Ng, RT; Сандер, младший (1999). «ОПТИКА-ОФ: Выявление локальных выбросов» (PDF) . Принципы интеллектуального анализа данных и обнаружения знаний . Конспект лекций по информатике. 1704 . п. 262. DOI : 10.1007 / 978-3-540-48247-5_28 . ISBN 978-3-540-66490-1.
  3. ^ Alpaydin, Ethem (2020). Введение в машинное обучение (Четвертое изд.). Кембридж, Массачусетс. ISBN 978-0-262-04379-3. OCLC  1108782604 .
  4. ^ a b c d Schubert, E .; Зимек, А .; Кригель, Х. -П. (2012). «Обнаружение локальных выбросов пересмотрено: обобщенное представление о местности с приложениями для пространственного, видео и сетевого обнаружения выбросов». Интеллектуальный анализ данных и обнаружение знаний . 28 : 190–237. DOI : 10.1007 / s10618-012-0300-Z . S2CID  19036098 .
  5. ^ Lazarevic, A .; Озгур, А .; Эртоз, Л .; Srivastava, J .; Кумар, В. (2003). «Сравнительное исследование схем обнаружения аномалий при обнаружении сетевых вторжений» (PDF) . Proc. 3-я Международная конференция SIAM по интеллектуальному анализу данных : 25–36. Архивировано из оригинального (PDF) 17 июля 2013 года . Проверено 14 мая 2010 .CS1 maint: использует параметр авторов ( ссылка )
  6. ^ Campos, Guilherme O .; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж.Б. Миченкова, Барбора; Шуберт, Эрих; Согласие, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Интеллектуальный анализ данных и обнаружение знаний . 30 (4): 891–927. DOI : 10.1007 / s10618-015-0444-8 . ISSN  1384-5810 . S2CID  1952214 .
  7. ^ Lazarevic, A .; Кумар, В. (2005). «Функция упаковки для обнаружения выбросов». Proc. 11-я Международная конференция ACM SIGKDD по открытию знаний в интеллектуальном анализе данных : 157–166. DOI : 10.1145 / 1081870.1081891 . ISBN 159593135X. S2CID  2054204 .
  8. ^ Zimek, A .; Кампелло, RJGB; Сандер, младший (2014). «Ансамбли для неконтролируемого обнаружения выбросов». Информационный бюллетень ACM SIGKDD Explorations . 15 : 11–22. DOI : 10.1145 / 2594473.2594476 . S2CID  8065347 .
  9. ^ Kriegel, H.-P. ; Kröger, P .; Schubert, E .; Зимек, А. (2009). LoOP: Вероятности локальных выбросов (PDF) . Материалы 18-й конференции ACM по управлению информацией и знаниями . ЦИКМ '09. С. 1649–1652. DOI : 10.1145 / 1645953.1646195 . ISBN 978-1-60558-512-3.
  10. ^ Kriegel, HP ; Kröger, P .; Schubert, E .; Зимек, А. (2011). Интерпретация и объединение результатов выбросов . Материалы Международной конференции SIAM 2011 по интеллектуальному анализу данных. С. 13–24. CiteSeerX  10.1.1.232.2719 . DOI : 10.1137 / 1.9781611972818.2 . ISBN 978-0-89871-992-5.
  11. ^ Шуберт, E .; Wojdanowski, R .; Зимек, А .; Кригель, HP (2012). Об оценке резко отклоняющихся рейтингов и резко отклоняющихся оценок . Материалы Международной конференции SIAM 2012 по интеллектуальному анализу данных. С. 1047–1058. CiteSeerX  10.1.1.300.7205 . DOI : 10.1137 / 1.9781611972825.90 . ISBN 978-1-61197-232-0.