Nivel de emisión local

El nivel de valores atípicos locales es un algoritmo en la detección de anomalías propuesto por Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng y Jörg Sander en 2000 para encontrar puntos de datos de valores atípicos midiendo la desviación local de un punto dado dado sus vecinos. [1] .

El nivel de valores atípicos locales comparte conceptos con DBSCAN y OPTICS , como los conceptos de "distancia básica" y "distancia alcanzable" [2] , que se utilizan para estimar la densidad local [3] .

Idea básica

El nivel de valores atípicos locales se basa en el concepto de densidad local, donde la localidad viene dada por los vecinos más cercanos, cuyas distancias se utilizan para estimar la densidad. Al comparar la densidad local de un objeto con la densidad local de sus vecinos, es posible identificar áreas con una densidad similar y puntos que tienen una densidad significativamente menor que sus vecinos. Estos puntos se consideran valores atípicos .

La densidad local se estima por la distancia típica a la que se puede "alcanzar" un punto desde los puntos vecinos. La definición de "distancia alcanzable" utilizada en el algoritmo es una medida adicional para obtener resultados más sólidos dentro de los clústeres.

Descripción formal

Sea la distancia del objeto al k -ésimo vecino más cercano. Tenga en cuenta que el conjunto de k vecinos más cercanos incluye todos los objetos a esa distancia y, en el caso de un "nodo", puede contener más de k objetos. Denotamos el conjunto de k vecinos más cercanos como .

Esta distancia se utiliza para determinar la distancia alcanzable ( eng.  reachability-distance ):

En otras palabras, la distancia alcanzable de un objeto es la verdadera distancia de los dos objetos. Las características que pertenecen a los k vecinos más cercanos del punto (los "puntos centrales" del punto , consulte DBSCAN ) se consideran a la misma distancia para obtener resultados más estables. Tenga en cuenta que esta distancia no es una distancia en el sentido matemático, ya que no es simétrica. (Un error común es aplicar siempre, por lo que esto da un método ligeramente diferente, llamado método de valor atípico local simplificado [4] )

La densidad de accesibilidad local de un objeto se define como

,

que es el recíproco de la distancia de accesibilidad promedio de un objeto de sus vecinos. Tenga en cuenta que esta no es la distancia de accesibilidad promedio de los vecinos desde el punto (que por definición tendría que ser ), sino la distancia a la que se puede "alcanzar" A desde sus vecinos. Con puntos duplicados, este valor puede llegar a ser infinito.

Las densidades de accesibilidad locales se comparan luego con las densidades de accesibilidad locales de los vecinos.

que es la densidad de accesibilidad local promedio de los vecinos dividida por la densidad de accesibilidad local del objeto en sí. Un valor aproximadamente igual a , significa que el objeto es comparable a sus vecinos (y entonces no es un valor atípico). Un valor menor que significa una región densa (que puede ser el interior), mientras que valores significativamente mayores que , indican valores atípicos.

Beneficios

Debido a la localidad del enfoque, el algoritmo de nivel de valor atípico local puede detectar valores atípicos en el conjunto de datos que podrían no serlo en otras áreas del conjunto de datos. Por ejemplo, un punto a una distancia "pequeña" de cualquier grupo denso es un valor atípico, mientras que un punto dentro de un grupo disperso puede tener distancias similares a sus vecinos.

Si bien la intuición geométrica del algoritmo solo se aplica a espacios vectoriales de baja dimensión, el algoritmo se puede aplicar en cualquier contexto en el que se pueda definir una función de disimilitud. Se ha demostrado experimentalmente que el algoritmo funciona bien en una gran cantidad de situaciones, a menudo superando a sus rivales, por ejemplo, en sistemas de detección de intrusos [5] y en datos de clasificación procesados ​​[6] .

La familia de métodos de niveles de valores atípicos locales se puede generalizar fácilmente y luego aplicar a varios otros problemas, como la detección de valores atípicos en datos geográficos, transmisiones de video o redes de crédito [4] .

Desventajas y extensiones

Los valores resultantes son difíciles de interpretar. Un valor de 1 o incluso menor que uno indica que el punto es puramente interno, pero no existe una regla clara de que un punto sea un valor atípico. En un conjunto de datos, un valor de 1,1 ya puede significar un valor atípico, en otro conjunto de datos y parametrización (con fuertes fluctuaciones locales), un valor de 2 aún puede significar un interior. Estas diferencias pueden ocurrir dentro del mismo conjunto de datos debido a la localidad del método. Hay extensiones de método que intentan mejorar el algoritmo:

Notas

  1. Breunig, Kriegel, Ng, Sander, 2000 , pág. 93–104.
  2. En lugar de "distancia alcanzable" en la literatura, también se encuentra el nombre "alcance".
  3. Breunig, Kriegel, Ng, Sander, 1999 , pág. 262.
  4. 1 2 3 Schubert, Zimek, Kriegel, 2012 .
  5. Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , pág. 25–36.
  6. Campos, Zimek, Sander, Campello et al., 2016 .
  7. Lazarevic y Kumar 2005 , pág. 157–166.
  8. Zimek, Campello, Sander, 2014 , p. once.
  9. Kriegel, Kröger, Schubert, Zimek, 2009 , pág. 1649-1652
  10. Kriegel, Kröger, Schubert, Zimek, 2011 , pág. 13–24.
  11. Schubert, Wojdanowski, Zimek, Kriegel, 2012 , pág. 1047-1058.

Literatura