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