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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Локальный уровень выброса является алгоритмом в выявлении аномалий, который предложили Маркус М. Бройниг, Ганс-Петер Кригель, Реймонд Т. Нг и Ёрг Сандер в 2000 году для нахождения аномальных точек данных путём измерения локального отклонения данной точки данных с учётом её соседей[1].

Локальный уровень выброса имеет общие концепции с DBSCAN и OPTICS[en], такие как понятия «основное расстояние» и «достижимое расстояние»[2], которые используются для оценки локальной плотности[3].

Базовая идея[править | править код]

Базовая идея метода «Локального уровня выброса» — сравнение локальной плотности точки с плотностями её соседей. Точка A имеет меньшую плотность по сравнению с соседями

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

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

Формальное описание[править | править код]

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

Это расстояние используется для определения достижимого расстояния (англ. reachability-distance):

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

Говоря словами, достижимое расстояние объекта из является истинным расстоянием двух объектов. Объекты, которые принадлежат к k ближайшим соседям точки («основные точки» точки , см. DBSCAN), считаются находящимися на одинаковом расстоянии для получения более стабильных результатов. Заметим, что это расстояние не является расстоянием в математическом смысле, поскольку оно не симметрично. (Общей ошибкой является применение всегда, так что это даёт слегка другой метод, называемый упрощённым методом локального уровня выброса[4])

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

,

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

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

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

Преимущества[править | править код]

Оценки алгоритма «Локальный уровень выброса», визуализированные ELKI[en]. В то время как верхний правый кластер имеет сравнимую плотность с выбросом, близком к левому нижнему кластеру, они определяются корректно.

Вследствие локальности подхода алгоритм локального уровня выброса способен выявить выбросы в наборе данных, которые могли бы не быть выбросами в других областях набора данных. Например, точка на «малом» расстоянии до любого плотного кластера является выбросом, в то время как точка внутри редкого кластера может иметь похожие расстояния с её соседями.

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

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

Недостатки и расширения[править | править код]

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

  • Бэггинг признаков для обнаружения обособленностей[7] выполняет алгоритм локального уровня выброса на нескольких проекциях и комбинирует результаты для улучшенного качества обнаружения в высоких размерностях. Это первый подход на основе ансамбля методов для обнаружения обособления, для других вариантов см. статью Зимека, Кампелло и Сандера[8].
  • Локальная вероятность выброса (ЛВВ, англ. Local Outlier Probability, LoOP)[9] является методом, полученным из метода локального уровня выброса, но использующий экономную локальную статистику, чтобы сделать метод менее чувствительным к выбору параметра k. Кроме того, результирующие значения масштабируются к значению .
  • Интерпретация и Унификация Степени Выброса (англ. Interpreting and Unifying Outlier Scores)[10] предполагает нормализацию оценки выброса к интервалу с помощью статистического масштабирования с целью увеличения удобства использования и можно рассматривать алгоритм как улучшенную версию идеи локальной вероятности выброса.
  • Оценка Распределения Выбросов и Степени Выброса (англ. On Evaluation of Outlier Rankings and Outlier Scores)[11] предлагает средства измерения похожести и отличия методов для построения продвинутого ансамбля методов выявления выбросов с помощью вариантов алгоритма локального уровня выброса и других алгоритмов и улучшения подхода бэггинга признаков, который обсуждался выше.
  • Пересмотренное локальное выявление выбросов: обобщённый взгляд на локальность с приложениями в пространственное выявление выбросов, в выявлении выбросов в видео и сетях[4] обсуждает общую схему в различных методах локального выявления выбросов (включая алгоритм локального уровня выброса, его упрощённую версию и ЛЛВ) и переводит рассмотрение в общие принципы. Эти принципы применяются затем, например, к выявлению выбросов в географических данных, видеопотоках и сети ссылок на авторство.

Примечания[править | править код]

  1. Breunig, Kriegel, Ng, Sander, 2000, с. 93–104.
  2. Вместо «достижимое расстояние» в литературе встречается также название «досягаемость»
  3. Breunig, Kriegel, Ng, Sander, 1999, с. 262.
  4. 1 2 3 Schubert, Zimek, Kriegel, 2012.
  5. Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003, с. 25–36.
  6. Campos, Zimek, Sander, Campello и др., 2016.
  7. Lazarevic, Kumar, 2005, с. 157–166.
  8. Zimek, Campello, Sander, 2014, с. 11.
  9. Kriegel, Kröger, Schubert, Zimek, 2009, с. 1649–1652.
  10. Kriegel, Kröger, Schubert, Zimek, 2011, с. 13–24.
  11. Schubert, Wojdanowski, Zimek, Kriegel, 2012, с. 1047–1058.

Литература[править | править код]