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

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

При обнаружении аномалий локальный коэффициент выбросов ( 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 -distance ( B ), d ( A , B )}

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

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

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

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

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

LOF _k (А):= ⁠Σ _{B ∈ N k (A)} ⁠лрд _к (Б)/лрд _к (А)⁠/| Н _к (А) |⁠ = ⁠Σ _{B ∈ N k (A)} lrd _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 в следующих аспектах:

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

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

1. Бройниг, ММ; Кригель, Х.-П. ; Нг, РТ; Сандер, Дж. (2000). LOF: Идентификация локальных выбросов на основе плотности (PDF) . Материалы Международной конференции ACM SIGMOD 2000 года по управлению данными . СИГМОД . стр. 93–104. дои : 10.1145/335191.335388. ISBN 1-58113-217-4.
2. Бройниг, ММ; Кригель, Х.-П. ; Нг, РТ; Сандер, младший (1999). «OPTICS-OF: выявление локальных выбросов» (PDF) . Принципы интеллектуального анализа данных и обнаружения знаний . Конспекты лекций по информатике. Том. 1704. стр. 262–270. дои : 10.1007/978-3-540-48247-5_28. ISBN 978-3-540-66490-1.
3. Алпайдин, Этем (2020). Введение в машинное обучение (Четвертое изд.). Кембридж, Массачусетс. ISBN 978-0-262-04379-3. ОСЛК  1108782604.{{cite book}}: CS1 maint: location missing publisher (link)
4. Шуберт, Э.; Зимек, А.; Кригель, Х.-П. (2012). «Переосмысление обнаружения локальных выбросов: обобщенный взгляд на местность с приложениями для обнаружения пространственных, видео и сетевых выбросов». Интеллектуальный анализ данных и обнаружение знаний . 28 : 190–237. doi : 10.1007/s10618-012-0300-z. S2CID  19036098.
5. Лазаревич, А.; Озгур, А.; Эртоз, Л.; Шривастава, Дж.; Кумар, В. (2003). «Сравнительное исследование схем обнаружения аномалий при обнаружении сетевых вторжений» (PDF) . Учеб. 3-я Международная конференция SIAM по интеллектуальному анализу данных : 25–36. Архивировано из оригинала (PDF) 17 июля 2013 г. Проверено 14 мая 2010 г.
6. Кампос, Гильерме О.; Зимек, Артур; Сандер, Йорг; Кампелло, Рикардо Дж.Г.Б.; Миценкова, Барбора; Шуберт, Эрих; Согласен, Ира; Хоул, Майкл Э. (2016). «Об оценке неконтролируемого обнаружения выбросов: меры, наборы данных и эмпирическое исследование». Интеллектуальный анализ данных и обнаружение знаний . 30 (4): 891–927. дои : 10.1007/s10618-015-0444-8. ISSN  1384-5810. S2CID  1952214.
7. Лазаревич, А.; Кумар, В. (2005). «Объединение функций для обнаружения выбросов». Материалы одиннадцатой международной конференции ACM SIGKDD по обнаружению знаний в области интеллектуального анализа данных . стр. 157–166. дои : 10.1145/1081870.1081891. ISBN 159593135X. S2CID  2054204.
8. Зимек, А.; Кампелло, RJGB; Сандер, младший (2014). «Ансамбли для неконтролируемого обнаружения выбросов». Информационный бюллетень об исследованиях ACM SIGKDD . 15 :11–22. дои : 10.1145/2594473.2594476. S2CID  8065347.
9. Кригель, Х.-П. ; Крегер, П.; Шуберт, Э.; Зимек, А. (2009). LoOP: Вероятности локальных выбросов (PDF) . Материалы 18-й конференции ACM по управлению информацией и знаниями . ЦИКМ '09. стр. 1649–1652. дои : 10.1145/1645953.1646195. ISBN 978-1-60558-512-3.
10. Кригель, HP ; Крегер, П.; Шуберт, Э.; Зимек, А. (2011). Интерпретация и унификация выбросов . Материалы Международной конференции SIAM 2011 по интеллектуальному анализу данных. стр. 13–24. CiteSeerX 10.1.1.232.2719 . дои : 10.1137/1.9781611972818.2. ISBN  978-0-89871-992-5.
11. Шуберт, Э.; Войдановский Р.; Зимек, А.; Кригель, HP (2012). Об оценке рейтингов выбросов и оценок выбросов . Материалы Международной конференции SIAM 2012 по интеллектуальному анализу данных. стр. 1047–1058. CiteSeerX 10.1.1.300.7205 . дои : 10.1137/1.9781611972825.90. ISBN  978-1-61197-232-0.