Локальный фактор выброса

Алгоритм обнаружения аномалий

В обнаружении аномалий локальный фактор выброса ( LOF ) — это алгоритм, предложенный Маркусом М. Бройнигом, Хансом-Петером Кригелем , Рэймондом Т. Нгом и Йоргом Сандером в 2000 году для поиска аномальных точек данных путем измерения локального отклонения заданной точки данных относительно ее соседей. ^[1]

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

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

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

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

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

Формальный

Пусть k -distance( 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 является истинным расстоянием двух объектов, но по крайней мере k -расстоянием B. Объекты, которые принадлежат k ближайшим соседям B («ядру» B , см. кластерный анализ DBSCAN ), считаются одинаково удаленными. Причина этого в том, чтобы уменьшить статистические колебания между всеми точками A, близкими к B , где увеличение значения k увеличивает эффект сглаживания. ^[1] Обратите внимание, что это не расстояние в математическом определении, поскольку оно не симметрично. (Хотя распространенной ошибкой ^[4] является всегда использование k -расстояния(A) , это дает немного другой метод, называемый Simplified-LOF ^[4] )

Локальная плотность достижимости объекта A определяется как

лрд _к (А):=1 /( ⁠Σ _{B ∈ N k (A)} достижимость-расстояние _k (A, B)/| Н _к (А) |⁠ )

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

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

ЛОФ _k (A):= ⁠Σ _{B ∈ N k (A)} ⁠лрд _к (Б)/лрд _к (А)⁠/| Н _к (А) |⁠ = ⁠Σ _{B ∈ N k (A)} лрд _k (B)/| Н _к (А) | · лрд _к (А)⁠

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

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

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

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

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

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

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

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

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

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

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

• Feature Bagging for Outlier Detection ^[7] запускает LOF на нескольких проекциях и объединяет результаты для улучшения качества обнаружения в больших измерениях. Это первый подход ансамблевого обучения к обнаружению выбросов, для других вариантов см. ссылку ^{[8] .}
• Вероятность локального выброса (LoOP) ^[9] — это метод, полученный из LOF, но использующий недорогую локальную статистику, чтобы стать менее чувствительным к выбору параметра k . Кроме того, полученные значения масштабируются до диапазона значений [0:1] .
• Интерпретация и унификация оценок выбросов ^[10] предлагает нормализацию оценок выбросов LOF до интервала [0:1] с использованием статистического масштабирования для повышения удобства использования и может рассматриваться как улучшенная версия идей LoOP.
• В работе «Оценка рейтингов и оценок выбросов» ^[11] предлагаются методы измерения сходства и разнообразия методов построения расширенных ансамблей обнаружения выбросов с использованием вариантов LOF и других алгоритмов, а также усовершенствования подхода Feature Bagging, рассмотренного выше.
• Пересмотрено локальное обнаружение выбросов: обобщенный взгляд на локальность с приложениями к пространственному, видео и сетевому обнаружению выбросов ^[4] обсуждает общую схему в различных методах обнаружения локальных выбросов (включая, например, LOF, упрощенную версию LOF и LoOP) и абстрагируется от этого в общую структуру. Затем эта структура применяется, например, к обнаружению выбросов в географических данных, видеопотоках и сетях авторства.

Ссылки

1. Breunig, MM; Kriegel, H.-P .; Ng, RT; Sander, J. (2000). LOF: Определение локальных выбросов на основе плотности (PDF) . Труды Международной конференции ACM SIGMOD 2000 года по управлению данными . SIGMOD . стр. 93–104. doi :10.1145/335191.335388. ISBN 1-58113-217-4.
2. Breunig, MM; Kriegel, H.-P .; Ng, RT; Sander, JR (1999). "OPTICS-OF: Определение локальных выбросов" (PDF) . Принципы добычи данных и обнаружения знаний . Конспект лекций по информатике. Том 1704. С. 262–270. 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.{{cite book}}: CS1 maint: location missing publisher (link)
4. Шуберт, Э.; Зимек, А.; Кригель, Х. -П. (2012). «Пересмотренное обнаружение локальных выбросов: обобщенный взгляд на локальность с приложениями к обнаружению пространственных, видео и сетевых выбросов». Data Mining and Knowledge Discovery . 28 : 190–237. doi :10.1007/s10618-012-0300-z. S2CID  19036098.
5. Лазаревич, А.; Озгур, А.; Эртоз, Л.; Шривастава, Дж.; Кумар, В. (2003). «Сравнительное исследование схем обнаружения аномалий в обнаружении сетевых вторжений» (PDF) . Труды 3-й Международной конференции SIAM по интеллектуальному анализу данных : 25–36. Архивировано из оригинала (PDF) 2013-07-17 . Получено 2010-05-14 .
6. Кампос, Гильерме О.; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж. ГБ.; Миценкова, Барбора; Шуберт, Эрих; Ассен, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Data Mining and Knowledge Discovery . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.
7. Лазаревич, А.; Кумар, В. (2005). «Объединение признаков для обнаружения выбросов». Труды одиннадцатой международной конференции ACM SIGKDD по обнаружению знаний в добыче данных . стр. 157–166. doi :10.1145/1081870.1081891. ISBN 159593135X. S2CID  2054204.
8. Zimek, A.; Campello, RJGB; Sander, JR (2014). «Ансамбли для неконтролируемого обнаружения выбросов». ACM SIGKDD Explorations Newsletter . 15 : 11–22. doi :10.1145/2594473.2594476. S2CID  8065347.
9. Кригель, Х.-П .; Крёгер, П.; Шуберт, Э.; Зимек, А. (2009). LoOP: Вероятности локальных выбросов (PDF) . Труды 18-й конференции ACM по управлению информацией и знаниями . CIKM '09. стр. 1649–1652. doi :10.1145/1645953.1646195. ISBN 978-1-60558-512-3.
10. Кригель, HP ; Крёгер, P.; Шуберт, E.; Зимек, A. (2011). Интерпретация и унификация оценок выбросов . Труды Международной конференции SIAM 2011 года по интеллектуальному анализу данных. С. 13–24. CiteSeerX 10.1.1.232.2719 . doi :10.1137/1.9781611972818.2. ISBN  978-0-89871-992-5.
11. Шуберт, Э.; Войдановски, Р.; Зимек, А.; Кригель, Х. П. (2012). Об оценке рейтингов и оценок выбросов . Труды Международной конференции SIAM 2012 года по интеллектуальному анализу данных. С. 1047–1058. CiteSeerX 10.1.1.300.7205 . doi : 10.1137/1.9781611972825.90. ISBN  978-1-61197-232-0.