Factor atípico local

En la detección de anomalías , el factor de valores atípicos locales ( LOF ) es un algoritmo propuesto por Markus M. Breunig, Hans-Peter Kriegel , Raymond T. Ng y Jörg Sander en 2000 para encontrar puntos de datos anómalos midiendo la desviación local de un punto de datos determinado. con respecto a sus vecinos. ^[1]

LOF comparte algunos conceptos con DBSCAN y OPTICS , como los conceptos de "distancia central" y "distancia de alcanzabilidad", que se utilizan para la estimación de densidad local. ^[2]

Idea básica

El factor de valores atípicos locales se basa en el concepto de densidad local, donde la localidad viene dada por k vecinos más cercanos, cuya distancia se utiliza para estimar la densidad. Al comparar la densidad local de un objeto con las densidades locales de sus vecinos, se pueden identificar regiones de densidad similar y puntos que tienen una densidad sustancialmente menor que sus vecinos. Éstos se consideran valores atípicos .

La densidad local se estima por la distancia típica a la que se puede "alcanzar" un punto desde sus vecinos. La definición de "distancia de accesibilidad" utilizada en LOF es una medida adicional para producir resultados más estables dentro de los grupos. La "distancia de accesibilidad" utilizada por LOF tiene algunos detalles sutiles que a menudo se encuentran incorrectos en fuentes secundarias, por ejemplo, en el libro de texto de Ethem Alpaydin. ^[3]

Formal

Sea $k -distancia(A)$ la distancia del objeto A al k -ésimo vecino más cercano. Tenga en cuenta que el conjunto de k vecinos más cercanos incluye todos los objetos a esta distancia, que en el caso de un "empate" pueden ser más de k objetos. Denotamos el conjunto de k vecinos más cercanos como $N k (A)$ .

Ilustración de la distancia de accesibilidad. Los objetos B y C tienen la misma distancia de alcance ( $k=3$ ), mientras que $D$ no es un k vecino más cercano

Esta distancia se utiliza para definir lo que se llama distancia de alcanzabilidad :

$distancia de accesibilidad k (A, B) = max {k -distancia (B), d (A, B)}$

En palabras, la distancia de accesibilidad de un objeto A a B es la distancia real de los dos objetos , pero al menos la $k -distancia$ de B. Los objetos que pertenecen a los k vecinos más cercanos de B (el "núcleo" de B , consulte el análisis de conglomerados DBSCAN ) se consideran igualmente distantes. La razón de esto es reducir las fluctuaciones estadísticas entre todos los puntos A cercanos a B , donde aumentar el valor de k aumenta el efecto de suavizado. ^[1] Tenga en cuenta que esta no es una distancia en la definición matemática, ya que no es simétrica. (Si bien es un error común ^[4] usar siempre la $k -distance(A)$ , esto produce un método ligeramente diferente, denominado LOF simplificado ^[4] )

La densidad de accesibilidad local de un objeto A está definida por

$lrd k (A):=1 /(.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num{display:block;line-height:1em;margin:0.0em 0.1em;border-bottom:1px solid}.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0.1em 0.1em}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);clip-path:polygon(0px 0px,0px 0px,0px 0px);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}Σ B ∈ N k (A) distancia de accesibilidad k (A, B)/| norte k (A) |)$

que es la inversa de la distancia promedio de accesibilidad del objeto A desde sus vecinos. Tenga en cuenta que no es la accesibilidad promedio de los vecinos de A (que por definición sería la $k -distancia(A)$ ), sino la distancia a la que se puede "alcanzar" A desde sus vecinos. Con puntos duplicados, este valor puede volverse infinito.

Las densidades de accesibilidad locales se comparan con las de los vecinos utilizando

$LOF k (A):= Σ B \in norte k (A) lrd k (B) / lrd k (A) / | norte k (A) | = Σ B \in N k (A) lrd k (B) / | norte k (A) | \cdot lrd k (A)$

que es la densidad de accesibilidad local promedio de los vecinos dividida por la densidad de accesibilidad local del propio objeto. Un valor de aproximadamente $1$ indica que el objeto es comparable a sus vecinos (y por lo tanto no es un valor atípico). Un valor inferior a $1$ indica una región más densa (que sería un valor interior), mientras que valores significativamente mayores que $1$ indican valores atípicos.

$LOF(k) ~ 1$ significa densidad similar a la de los vecinos,

$LOF(k) <1$ significa mayor densidad que los vecinos (Inlier),

$LOF(k) > 1$ significa menor densidad que los vecinos (valor atípico)

Ventajas

Puntuaciones LOF visualizadas por ELKI . Si bien el grupo superior derecho tiene una densidad comparable a los valores atípicos cercanos al grupo inferior izquierdo, se detectan correctamente.

Debido al enfoque local, LOF puede identificar valores atípicos en un conjunto de datos que no serían valores atípicos en otra área del conjunto de datos. Por ejemplo, un punto a una distancia "pequeña" de un cúmulo muy denso es un valor atípico, mientras que un punto dentro de un cúmulo disperso puede presentar distancias similares a sus vecinos.

Si bien la intuición geométrica de LOF solo es aplicable 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 funciona muy bien en numerosas configuraciones, a menudo superando a la competencia, por ejemplo en la detección de intrusiones en la red ^[5] y en datos de referencia de clasificación procesados. ^[6]

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

Desventajas y extensiones

Los valores resultantes son valores cocientes y difíciles de interpretar. Un valor de 1 o incluso menos indica un valor interior claro, pero no existe una regla clara sobre cuándo un punto es un valor atípico. En un conjunto de datos, un valor de 1,1 puede ser ya un valor atípico, en otro conjunto de datos y parametrización (con fuertes fluctuaciones locales) un valor de 2 aún podría ser un valor atípico. Estas diferencias también pueden ocurrir dentro de un conjunto de datos debido a la localidad del método. Existen extensiones de LOF que intentan mejorar respecto a LOF en estos aspectos:

Feature Bagging para la detección de valores atípicos ^[7] ejecuta LOF en múltiples proyecciones y combina los resultados para mejorar las cualidades de detección en grandes dimensiones. Este es el primer enfoque de aprendizaje conjunto para la detección de valores atípicos; para otras variantes, consulte la ref. ^[8]
La probabilidad de valores atípicos locales (LoOP) ^[9] es un método derivado de LOF pero que utiliza estadísticas locales económicas para volverse menos sensible a la elección del parámetro k . Además, los valores resultantes se escalan a un rango de valores de $[0:1]$ .
Interpretación y unificación de puntuaciones de valores atípicos ^[10] propone una normalización de las puntuaciones de valores atípicos de LOF al intervalo $[0:1]$ utilizando una escala estadística para aumentar la usabilidad y se puede ver una versión mejorada de las ideas de LoOP.
Sobre la evaluación de clasificaciones de valores atípicos y puntuaciones de valores atípicos ^[11] propone métodos para medir la similitud y diversidad de métodos para construir conjuntos avanzados de detección de valores atípicos utilizando variantes LOF y otros algoritmos y mejorando el enfoque de ensacado de características discutido anteriormente.
Reconsideración de la detección de valores atípicos locales: una visión generalizada de la localidad con aplicaciones a la detección de valores atípicos espaciales, de vídeo y de red ^[4] analiza el patrón general en varios métodos de detección de valores atípicos locales (incluido, por ejemplo, LOF, una versión simplificada de LOF y LoOP) y se abstrae de esto en un marco general. Este marco se aplica luego, por ejemplo, para detectar valores atípicos en datos geográficos, transmisiones de vídeo y redes de autoría.

Referencias

^ ab Breunig, MM; Kriegel, H.-P. ; Ng, RT; Sander, J. (2000). LOF: Identificación de valores atípicos locales basados en la densidad (PDF) . Actas de la Conferencia Internacional ACM SIGMOD 2000 sobre Gestión de Datos . SIGMOD . págs. 93-104. doi :10.1145/335191.335388. ISBN 1-58113-217-4.
^ Breunig, MM; Kriegel, H.-P. ; Ng, TA; Sander, JR (1999). "ÓPTICA DE: Identificación de valores atípicos locales" (PDF) . Principios de minería de datos y descubrimiento de conocimientos . Apuntes de conferencias sobre informática. vol. 1704, págs. 262–270. doi :10.1007/978-3-540-48247-5_28. ISBN 978-3-540-66490-1.
^ Alpaydin, Ethem (2020). Introducción al aprendizaje automático (Cuarta ed.). Cambridge, Massachusetts. ISBN 978-0-262-04379-3. OCLC 1108782604.{{cite book}}: CS1 maint: location missing publisher (link)
^ abcd Schubert, E.; Zimek, A.; Kriegel, H.-P. (2012). "Reconsideración de la detección de valores atípicos locales: una visión generalizada de la localidad con aplicaciones a la detección de valores atípicos espaciales, de vídeo y de red". Minería de datos y descubrimiento de conocimientos . 28 : 190–237. doi :10.1007/s10618-012-0300-z. S2CID 19036098.
^ Lazarevic, A.; Özgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V. (2003). "Un estudio comparativo de esquemas de detección de anomalías en la detección de intrusiones en la red" (PDF) . Proc. Tercera Conferencia Internacional SIAM sobre Minería de Datos : 25–36. Archivado desde el original (PDF) el 17 de julio de 2013 . Consultado el 14 de mayo de 2010 .
^ Campos, Guilherme O.; Zimek, Arturo; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Asentimiento, Ira; Houle, Michael E. (2016). "Sobre la evaluación de la detección de valores atípicos no supervisados: medidas, conjuntos de datos y un estudio empírico". Minería de datos y descubrimiento de conocimientos . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN 1384-5810. S2CID 1952214.
^ Lazarevic, A.; Kumar, V. (2005). "Embolsado de funciones para la detección de valores atípicos". Actas de la undécima conferencia internacional ACM SIGKDD sobre descubrimiento de conocimiento en minería de datos . págs. 157-166. doi :10.1145/1081870.1081891. ISBN 159593135X. S2CID 2054204.
^ Zimek, A.; Campello, RJGB; Sander, JR (2014). "Conjuntos para la detección de valores atípicos no supervisados". Boletín de exploraciones de ACM SIGKDD . 15 : 11–22. doi :10.1145/2594473.2594476. S2CID 8065347.
^ Kriegel, H.-P. ; Kröger, P.; Schubert, E.; Zimek, A. (2009). LoOP: probabilidades de valores atípicos locales (PDF) . Actas de la 18ª Conferencia ACM sobre Gestión de la Información y el Conocimiento . CIKM'09. págs. 1649-1652. doi :10.1145/1645953.1646195. ISBN 978-1-60558-512-3.
^ Kriegel, HP ; Kröger, P.; Schubert, E.; Zimek, A. (2011). Interpretación y unificación de puntuaciones de valores atípicos . Actas de la Conferencia Internacional SIAM 2011 sobre Minería de Datos. págs. 13-24. CiteSeerX 10.1.1.232.2719 . doi :10.1137/1.9781611972818.2. ISBN 978-0-89871-992-5.
^ Schubert, E.; Wojdanowski, R.; Zimek, A.; Kriegel, HP (2012). Sobre la evaluación de clasificaciones y puntuaciones de valores atípicos . Actas de la Conferencia Internacional SIAM de 2012 sobre Minería de Datos. págs. 1047-1058. CiteSeerX 10.1.1.300.7205 . doi :10.1137/1.9781611972825.90. ISBN 978-1-61197-232-0.