Factor de valor atípico local

El factor de valores atípicos locales ( LOF ) es un algoritmo para la detección de valores atípicos basados ​​en la densidad . Fue propuesto por Markus M. Breunig, Hans-Peter Kriegel , Raymond T. Ng y Jörg Sander en 2000. La idea central de LOF es comparar la densidad de un punto con las densidades de sus vecinos. Un punto que es "más denso" que sus vecinos está en un grupo. Un punto con una densidad significativamente menor que sus vecinos, por otro lado, es un valor atípico.

LOF tiene muchos conceptos en común con los algoritmos de análisis de conglomerados DBSCAN y OPTICS .

Principio básico

La idea central de LOF: comparar la densidad local de un punto con la de sus vecinos.

LOF define el "entorno local" de un punto a través de sus vecinos más cercanos. La distancia a estos se usa para estimar una densidad local . En un segundo paso, el cociente se forma a partir de las densidades locales de sus vecinos y la densidad local del propio punto. Este valor se acerca a cuando un punto está en un área de densidad uniforme. Para los objetos que están aislados de tal área, el valor es significativamente más alto y, por lo tanto, indica valores atípicos. ${\ Displaystyle k}$${\ displaystyle 1.0}$

Formalmente

Esta es la distancia entre el objeto y su k vecino -nearest. Este conjunto puede contener más de k objetos si hay varios objetos con la misma distancia. Denotamos este " barrio k " aquí . ${\ displaystyle {\ mbox {k-distancia}} (A)}$${\ Displaystyle A}$${\ Displaystyle N_ {k} (A)}$

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

La "distancia de accesibilidad" se define en función de esta distancia:

${\ displaystyle {\ mbox {Distancia de accesibilidad}} _ {k} (A, B) = \ max \ {{\ mbox {k-distancia}} (B), d (A, B) \}}$

La distancia alcanzable de un objeto desde es la distancia real, pero al menos la de . Por tanto, los objetos que pertenecen a los k -vecinos más cercanos de se consideran equidistantes. La motivación para esta definición de distancia es obtener resultados más estables. (Sin embargo, esta ya no es una función de distancia en el sentido matemático, ya que no es simétrica). ${\ Displaystyle A}$ ${\ Displaystyle B}$${\ displaystyle {\ mbox {k-distancia}}}$${\ Displaystyle B}$${\ Displaystyle B}$

La densidad de accesibilidad local (" densidad de accesibilidad local ", " lrd ") de un objeto se define como ${\ Displaystyle A}$

${\ displaystyle {\ mbox {lrd}} _ {k} (A): = 1 / \ left ({\ frac {\ sum _ {B \ in N_ {k} (A)} {\ mbox {Distancia de accesibilidad }} _ {k} (A, B)} {| N_ {k} (A) |}} \ derecha)}$

Por tanto, esta densidad es el recíproco de la distancia media alcanzable del objeto de sus vecinos, y no al revés de la distancia media alcanzable de los vecinos desde , que sería por definición . Si hay duplicados en un registro de datos, la accesibilidad de estos objetos se vuelve infinita. ${\ Displaystyle A}$ ${\ Displaystyle A}$${\ displaystyle {\ mbox {k-distancia}} (A)}$${\ Displaystyle k + 1}$

La densidad de accesibilidad local se compara ahora con la de los vecinos:

${\ Displaystyle {\ mbox {LOF}} _ {k} (A): = {\ frac {\ sum _ {B \ in N_ {k} (A)} {\ frac {{\ mbox {lrd}} ( B)} {{\ mbox {lrd}} (A)}}} {| N_ {k} (A) |}} = {\ frac {\ sum _ {B \ in N_ {k} (A)} { \ mbox {lrd}} (B)} {| N_ {k} (A) |}} / {\ mbox {lrd}} (A)}$

El "Factor de valor atípico local" (LOF) es la " densidad de accesibilidad promedio de los vecinos" dividida por la densidad de accesibilidad de la propiedad en sí. Un valor de aproximadamente significa que la propiedad tiene una densidad comparable a la de sus vecinos (es decir, no es un valor atípico). Un valor menor que par significa una región más densa (que sería un "inlier"), mientras que los valores significativamente más altos indican un valor atípico. ${\ Displaystyle 1}$${\ Displaystyle 1}$${\ Displaystyle 1}$

beneficios

Valores de LOF visualizados con ELKI . Aunque el grupo superior derecho tiene una densidad comparable a los valores atípicos de la parte inferior izquierda, se clasifican correctamente.

A diferencia de muchos métodos de detección de valores atípicos globales, LOF puede tratar áreas de diferente densidad en el mismo conjunto de datos. Los puntos con una densidad "media" en un entorno "alto" se clasifican como valores atípicos por la LOF, mientras que un punto con una densidad "media" en un entorno "delgado" no se reconoce explícitamente como tal.

Si bien la intuición geométrica de LOF solo tiene sentido en espacios vectoriales de baja dimensión, el método se puede aplicar a cualquier dato en el que se pueda definir una "disimilitud". No tiene que ser una función de distancia en el sentido estrictamente matemático; la desigualdad del triángulo , por ejemplo, no es necesaria. El algoritmo se utilizó con éxito en una amplia variedad de conjuntos de datos, por ejemplo, para detectar ataques en redes informáticas , donde proporcionó mejores tasas de detección que los métodos de comparación.

desventaja

Una desventaja importante de LOF es que los valores de los resultados son difíciles de interpretar. Los valores alrededor y menos ciertamente no son valores atípicos, pero no existe una regla clara sobre el valor a partir del cual un punto es un valor atípico significativo . En un conjunto de datos muy uniforme, los valores de son conspicuos; en un conjunto de datos con fuertes fluctuaciones de densidad, un valor puede ser como un punto de datos completamente normal. En el peor de los casos, estas diferencias se producen incluso en diferentes partes del mismo conjunto de datos. ${\ Displaystyle 1}$${\ Displaystyle 1.1}$${\ Displaystyle 2}$

Extensiones

• El ensacado de características para la detección de valores atípicos aplica LOF en múltiples proyecciones y combina los resultados para obtener mejores resultados en datos de alta dimensión.
• La probabilidad de valores atípicos locales (LoOP) es un método derivado de LOF que estima estadísticamente la densidad para volverse menos dependiente del valor exacto de k . Además, el resultado se normaliza estadísticamente en el rango de valores para proporcionar valores que sean más fáciles de interpretar.${\ Displaystyle [0,1]}$
• La interpretación y unificación de las puntuaciones de valores atípicos introduce una normalización de la LOF y otros procedimientos que normalizan estadísticamente las puntuaciones en el intervalo para mejorar la usabilidad del resultado.${\ Displaystyle [0,1]}$

Disponibilidad

Una implementación de referencia está disponible en el paquete de software ELKI , que incluye implementaciones de métodos de comparación.

Evidencia individual

1. ^ MM Breunig, Hans-Peter Kriegel , RT Ng, J. Sander: LOF: Identificación de valores atípicos locales basados ​​en la densidad . En: Registro ACM SIGMOD . No. 29 , 2000, págs. 93 , doi : 10.1145 / 335191.335388 ( PDF en línea ). 
2. ↑ Ar Lazarevic, Aysel Ozgur, Levent Ertoz, Jaideep Srivastava, Vipin Kumar: Un estudio comparativo de esquemas de detección de anomalías en la detección de intrusiones en la red . En: Proc. 3er Congreso Internacional SIAM sobre Minería de Datos . 2003, pág. 25-36 ( PDF en línea ). Línea ( Memento de la original, del 17 de julio, 2013, en el Archivo de Internet ) Información: El archivo de enlace se inserta de forma automática y sin embargo no ha sido comprobado. Verifique el enlace original y de archivo de acuerdo con las instrucciones y luego elimine este aviso.   @ 1@ 2Plantilla: Webachiv / IABot / www.siam.org
3. ^ A. Lazarevic, V. Kumar: Embolsado de características para la detección de valores atípicos . En: Proc. XI Congreso Internacional ACM SIGKDD sobre Descubrimiento de Conocimiento en Minería de Datos . 2005, pág. 157-166 , doi : 10.1145 / 1081870.1081891 . 
4. ↑ Hans-Peter Kriegel , P. Kröger, E. Schubert, A. Zimek: LoOP: Local Outlier Probabilities . En: Proc. 18ª Conferencia ACM sobre Gestión de la Información y el Conocimiento (CIKM) . 2009, pág. 1649 , doi : 10.1145 / 1645953.1646195 ( PDF en línea ). 
5. ↑ Hans-Peter Kriegel , Peer Kröger, Erich Schubert, Arthur Zimek: Interpretación y unificación de puntajes atípicos . En: Proc. XI Congreso Internacional SIAM sobre Minería de Datos . 2011 ( PDF en línea ).