Valor atípico local

En la detección de anomalías, el valor atípico local (en inglés, local outlier factor, 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]

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

Idea básica

El valor atípico local 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. Comparando 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 últimos se consideran valores atípicos.

La densidad local se estima mediante la distancia típica a la que se puede "llegar" a 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 conglomerados. La "distancia de alcanzabilidad" 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 -distance(A)$ la distancia del objeto A al k-ésimo vecino más cercano. Obsérvese que el conjunto de los k vecinos más próximos 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 próximos como $N k (A)$ .

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

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

$reachability-distance k (A, B)=max{k -distance(B), d(A, B)}$

En otras palabras, la distancia de alcanzabilidad de un objeto A con respecto a B es la distancia real de los dos objetos, pero al menos la $k -distance$ de B. Los objetos que pertenecen a los k vecinos más cercanos de B (el "núcleo" de B, véase 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 el aumento del valor de k aumenta el efecto de suavizado.^[1] Nótese que no se trata de una distancia en la definición matemática, ya que no es simétrica. (Aunque es un error común^[4] utilizar siempre la $k -distance(A)$ , esto da lugar a un método ligeramente diferente, denominado Simplified-LOF^[4])

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

$lrd k (A):=1/(Σ B \in N k (A) reachability-distance k (A, B) / N k (A))$

que es la inversa de la distancia media de alcanzabilidad del objeto A desde sus vecinos. Nótese que no se trata de la alcanzabilidad media de los vecinos desde A (que por definición sería la k-distancia(A)), sino de la distancia a la que se puede "llegar" a A desde sus vecinos. Con puntos duplicados, este valor puede llegar a ser infinito.

A continuación, se comparan las densidades de accesibilidad locales con las de los vecinos mediante

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

que es la densidad de accesibilidad local media de los vecinos dividida por la densidad de accesibilidad local del propio objeto. Un valor aproximado de 1 indica que el objeto es comparable a sus vecinos (y, por 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 valores significativamente superiores a 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 (valor típico),

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

Ventajas

Puntuaciones LOF visualizadas por ELKI. Aunque el clúster superior derecho tiene una densidad comparable a la de los valores atípicos cercanos al clúster inferior izquierdo, éstos se detectan correctamente.

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

Aunque la intuición geométrica de LOF sólo es aplicable a espacios vectoriales de baja dimensión, el algoritmo puede aplicarse en cualquier contexto en el que pueda definirse 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 puede generalizarse fácilmente y aplicarse a otros problemas, como la detección de valores atípicos en datos geográficos, flujos de vídeo o redes de autoría.^[4]

Desventajas y ampliaciones

Los valores resultantes son cocientes y difíciles de interpretar. Un valor de 1 o incluso inferior indica un valor anómalo claro, pero no existe una regla clara para determinar cuándo un punto es un valor anómalo. En un conjunto de datos, un valor de 1,1 puede ser ya un valor atípico, mientras que 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 mismo conjunto de datos debido a la localidad del método. Existen extensiones de LOF que intentan mejorar LOF en estos aspectos:

Agrupación de características para la detección de valores atípicos (en inglés: 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 elevadas. Este es el primer enfoque de aprendizaje conjunto para la detección de valores atípicos; para otras variantes, véase la ref.^[8]
Probabilidad local de valores atípicos (en inglés: Local Outlier Probability, LoOP)^[9] es un método derivado de LOF pero que utiliza estadísticas locales baratas para ser 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 las puntuaciones de valores atípicos (en inglés: Interpreting and Unifying Outlier Scores)^[10] propone una normalización de las puntuaciones de valores atípicos de LOF al intervalo $[0:1]$ utilizando un escalado estadístico para aumentar la usabilidad y puede considerarse una versión mejorada de las ideas de LoOP.
Evaluación de clasificaciones de valores atípicos y puntuaciones de valores atípicos (en inglés: On Evaluation of Outlier Rankings and Outlier Scores)^[11] se proponen métodos para medir la similitud y la diversidad de métodos para construir conjuntos avanzados de detección de valores atípicos utilizando variantes de LOF y otros algoritmos y mejorando el enfoque de Feature Bagging comentado anteriormente.
Detección de valores atípicos locales reconsiderada: una visión generalizada de la localidad con aplicaciones a la detección de valores atípicos espaciales, de vídeo y de redes (en inglés: Local outlier detection reconsidered: a generalized view on locality with applications to spatial, video, and network outlier detection)^[4] analiza el patrón general de varios métodos de detección de valores atípicos locales (incluidos, por ejemplo, LOF, una versión simplificada de LOF y LoOP) y lo abstrae en un marco general. Este marco se aplica, por ejemplo, a la detección de valores atípicos en datos geográficos, secuencias de vídeo y redes de autoría.

Véase también

Detección de anomalías

Referencias

↑ ^a ^b Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. (2000). «LOF: Identifying Density-based Local Outliers». SIGMOD. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (en inglés): 93-104. ISBN 1-58113-217-4. doi:10.1145/335191.335388.
↑ Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. R. (1999). «OPTICS-OF: Identifying Local Outliers». Principles of Data Mining and Knowledge Discovery. Lecture Notes in Computer Science (en inglés) 1704. p. 262. ISBN 978-3-540-66490-1. doi:10.1007/978-3-540-48247-5_28.
↑ Alpaydin, Ethem (2020). Introduction to machine learning (en inglés). Cambridge, Massachusetts: Fourth. ISBN 978-0-262-04379-3. OCLC 1108782604.
↑ ^a ^b ^c ^d Schubert, E.; Zimek, A.; Kriegel, H. -P. (2012). «Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection». Data Mining and Knowledge Discovery 28: 190-237. doi:10.1007/s10618-012-0300-z.
↑ Lazarevic, A.; Ozgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V. (2003). «A comparative study of anomaly detection schemes in network intrusion detection». Proc. 3rd SIAM International Conference on Data Mining (en inglés): 25-36. Archivado desde el original el 17 de julio de 2013. Consultado el 14 de mayo de 2010.
↑ Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo J. G. B.; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). «On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study». Data Mining and Knowledge Discovery (en inglés) 30 (4): 891-927. ISSN 1384-5810. doi:10.1007/s10618-015-0444-8.
↑ Lazarevic, A.; Kumar, V. (2005). «Feature bagging for outlier detection». Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (en inglés): 157-166. ISBN 159593135X. doi:10.1145/1081870.1081891.
↑ Zimek, A.; Campello, R. J. G. B.; Sander, J. R. (2014). «Ensembles for unsupervised outlier detection». ACM SIGKDD Explorations Newsletter (en inglés) 15: 11-22. doi:10.1145/2594473.2594476.
↑ Kriegel, H.-P.; Kröger, P.; Schubert, E.; Zimek, A. (2009). «LoOP: Local Outlier Probabilities». CIKM '09. Proceedings of the 18th ACM Conference on Information and Knowledge Management (en inglés): 1649-1652. ISBN 978-1-60558-512-3. doi:10.1145/1645953.1646195.
↑ Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2011). «Interpreting and Unifying Outlier Scores». Proceedings of the 2011 SIAM International Conference on Data Mining (en inglés): 13-24. ISBN 978-0-89871-992-5. doi:10.1137/1.9781611972818.2.
↑ Schubert, E.; Wojdanowski, R.; Zimek, A.; Kriegel, H. P. (2012). «On Evaluation of Outlier Rankings and Outlier Scores». Proceedings of the 2012 SIAM International Conference on Data Mining (en inglés): 1047-1058. ISBN 978-1-61197-232-0. doi:10.1137/1.9781611972825.90.

[:0-1] Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. (2000). «LOF: Identifying Density-based Local Outliers». SIGMOD. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data (en inglés): 93-104. ISBN 1-58113-217-4. doi:10.1145/335191.335388.

[2] Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J. R. (1999). «OPTICS-OF: Identifying Local Outliers». Principles of Data Mining and Knowledge Discovery. Lecture Notes in Computer Science (en inglés) 1704. p. 262. ISBN 978-3-540-66490-1. doi:10.1007/978-3-540-48247-5_28.

[3] Alpaydin, Ethem (2020). Introduction to machine learning (en inglés). Cambridge, Massachusetts: Fourth. ISBN 978-0-262-04379-3. OCLC 1108782604.

[:1-4] Schubert, E.; Zimek, A.; Kriegel, H. -P. (2012). «Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection». Data Mining and Knowledge Discovery 28: 190-237. doi:10.1007/s10618-012-0300-z.

[5] Lazarevic, A.; Ozgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V. (2003). «A comparative study of anomaly detection schemes in network intrusion detection». Proc. 3rd SIAM International Conference on Data Mining (en inglés): 25-36. Archivado desde el original el 17 de julio de 2013. Consultado el 14 de mayo de 2010.

[6] Campos, Guilherme O.; Zimek, Arthur; Sander, Jörg; Campello, Ricardo J. G. B.; Micenková, Barbora; Schubert, Erich; Assent, Ira; Houle, Michael E. (2016). «On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study». Data Mining and Knowledge Discovery (en inglés) 30 (4): 891-927. ISSN 1384-5810. doi:10.1007/s10618-015-0444-8.

[7] Lazarevic, A.; Kumar, V. (2005). «Feature bagging for outlier detection». Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining (en inglés): 157-166. ISBN 159593135X. doi:10.1145/1081870.1081891.

[8] Zimek, A.; Campello, R. J. G. B.; Sander, J. R. (2014). «Ensembles for unsupervised outlier detection». ACM SIGKDD Explorations Newsletter (en inglés) 15: 11-22. doi:10.1145/2594473.2594476.

[9] Kriegel, H.-P.; Kröger, P.; Schubert, E.; Zimek, A. (2009). «LoOP: Local Outlier Probabilities». CIKM '09. Proceedings of the 18th ACM Conference on Information and Knowledge Management (en inglés): 1649-1652. ISBN 978-1-60558-512-3. doi:10.1145/1645953.1646195.

[10] Kriegel, H. P.; Kröger, P.; Schubert, E.; Zimek, A. (2011). «Interpreting and Unifying Outlier Scores». Proceedings of the 2011 SIAM International Conference on Data Mining (en inglés): 13-24. ISBN 978-0-89871-992-5. doi:10.1137/1.9781611972818.2.

[11] Schubert, E.; Wojdanowski, R.; Zimek, A.; Kriegel, H. P. (2012). «On Evaluation of Outlier Rankings and Outlier Scores». Proceedings of the 2012 SIAM International Conference on Data Mining (en inglés): 1047-1058. ISBN 978-1-61197-232-0. doi:10.1137/1.9781611972825.90.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]