Factor de valor atípico local

En la detección de anomalías , el factor de valor atípico local ( 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 dado con respecto a sus vecinos. ^[1]

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

Idea básica

El factor de valor atípico local se basa en un concepto de densidad local, donde la localidad está dada por los 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. Estos se consideran valores atípicos .

La densidad local se calcula a partir de la distancia típica a la que se puede "alcanzar" un punto desde sus vecinos. La definición de "distancia de alcance" utilizada en LOF es una medida adicional para producir resultados más estables dentro de los clústeres. La "distancia de alcance" 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. Nótese que el conjunto de los k vecinos más cercanos incluye todos los objetos a esta distancia, que en el caso de un "empate" puede 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 alcance. Los objetos B y C tienen la misma distancia de alcance ( $k=3$ ), mientras que $D$ no es un vecino más cercano k

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

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

En palabras, la distancia de alcance de un objeto A desde 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 clústeres 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 esto 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 -distancia(A)$ , esto produce un método ligeramente diferente, conocido como LOF simplificado ^[4] )

La densidad de accesibilidad local de un objeto A se define por

$lrd k (A):=1 /(⁠ Σ B \in N k (A) distancia de alcance k (A, B) / | N k (A) | ⁠)$

que es la inversa de la distancia de alcance promedio del objeto A desde sus vecinos. Nótese que no es la distancia de alcance promedio de los vecinos desde 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.

Luego se comparan las densidades de accesibilidad local con las de los vecinos que utilizan

$LOF k (A):= ⁠ Σ B \in N k (A) ⁠ lrd k (B) / k (a) ⁠ / | N k (A) | ⁠ = ⁠ Σ B \in N k (A) lrd k (B) / | N 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 atípico), mientras que los 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 la de los valores atípicos cercanos al grupo inferior izquierdo, se detectan correctamente.

Gracias al enfoque local, LOF puede identificar valores atípicos en un conjunto de datos que no lo serían en otra área del conjunto de datos. Por ejemplo, un punto a una distancia "pequeña" de un grupo muy denso es un valor atípico, mientras que un punto dentro de un grupo 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 los competidores, 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 varios 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 de cociente y difíciles de interpretar. Un valor de 1 o incluso menos indica un valor atípico claro, pero no hay una regla clara para determinar 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 podría seguir siendo un valor atípico. Estas diferencias también pueden darse dentro de un conjunto de datos debido a la localidad del método. Existen extensiones de LOF que intentan mejorar LOF en estos aspectos:

Feature Bagging for Outlier Detection ^[7] ejecuta LOF en múltiples proyecciones y combina los resultados para mejorar las cualidades de detección en dimensiones altas. Este es el primer enfoque de aprendizaje por conjuntos para la detección de valores atípicos; para otras variantes, consulte la referencia ^[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 escala estadística para aumentar la usabilidad y puede verse como una versión mejorada de las ideas de LoOP.
En Sobre la evaluación de clasificaciones y puntuaciones de valores atípicos ^[11] se proponen 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 Feature Bagging analizado anteriormente.
Reconsideración de la detección de valores atípicos locales: una visión generalizada de la localidad con aplicaciones para la detección de valores atípicos espaciales, de video y de red ^[4] analiza el patrón general en varios métodos de detección de valores atípicos locales (incluidos, por ejemplo, LOF, una versión simplificada de LOF y LoOP) y los abstrae en un marco general. Este marco se aplica luego, por ejemplo, a la detección de valores atípicos en datos geográficos, transmisiones de video 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 de 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, RT; Sander, JR (1999). "OPTICS-OF: Identificación de valores atípicos locales" (PDF) . Principios de minería de datos y descubrimiento de conocimiento . Apuntes de clase en 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 edición). 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 para la detección de valores atípicos espaciales, de video y de red". Minería de datos y descubrimiento de conocimiento . 28 : 190–237. doi :10.1007/s10618-012-0300-z. S2CID 19036098.
^ Lazarevic, A.; Ozgur, 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. 3rd SIAM International Conference on Data Mining : 25–36. Archivado desde el original (PDF) el 2013-07-17 . Consultado el 2010-05-14 .
^ Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Assent, 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 conocimiento . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN 1384-5810. S2CID 1952214.
^ Lazarevic, A.; Kumar, V. (2005). "Feature bagging for outlier detection" (Embolsado de características 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.S2CID2054204 .
^ 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: Local Outlier Probabilities (PDF) . Actas de la 18.ª Conferencia de la 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 de 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.

[orig_paper-1] 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 de 2000 sobre gestión de datos . SIGMOD . págs. 93–104. doi :10.1145/335191.335388. ISBN 1-58113-217-4.

[2] Breunig, MM; Kriegel, H.-P .; Ng, RT; Sander, JR (1999). "OPTICS-OF: Identificación de valores atípicos locales" (PDF) . Principios de minería de datos y descubrimiento de conocimiento . Apuntes de clase en informática. Vol. 1704. págs. 262–270. doi :10.1007/978-3-540-48247-5_28. ISBN 978-3-540-66490-1.

[3] Alpaydin, Ethem (2020). Introducción al aprendizaje automático (cuarta edición). Cambridge, Massachusetts. ISBN 978-0-262-04379-3.OCLC 1108782604 .{{cite book}}: CS1 maint: location missing publisher (link)

[generalized-4] 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 para la detección de valores atípicos espaciales, de video y de red". Minería de datos y descubrimiento de conocimiento . 28 : 190–237. doi :10.1007/s10618-012-0300-z. S2CID 19036098.

[5] Lazarevic, A.; Ozgur, 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. 3rd SIAM International Conference on Data Mining : 25–36. Archivado desde el original (PDF) el 2013-07-17 . Consultado el 2010-05-14 .

[CamposZimek2016-6] Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; Assent, 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 conocimiento . 30 (4): 891–927. doi :10.1007/s10618-015-0444-8. ISSN 1384-5810. S2CID 1952214.

[7] Lazarevic, A.; Kumar, V. (2005). "Feature bagging for outlier detection" (Embolsado de características 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.S2CID2054204 .

[8] 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.

[9] Kriegel, H.-P. ; Kröger, P.; Schubert, E.; Zimek, A. (2009). LoOP: Local Outlier Probabilities (PDF) . Actas de la 18.ª Conferencia de la 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.

[10] 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 de 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.

[11] 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.