Detección de anomalías (IV): enfoque basado en similitudes
En el procesamiento de datos normal, normalmente retenemos los datos normales e ignoramos las características del ruido y los valores atípicos. Pero en la detección de anomalías, debilitamos la distinción entre "ruido" y "datos normales" y nos centramos en valores atípicos que tienen propiedades valiosas. En los métodos basados en similitud, la idea principal es que los puntos atípicos son diferentes de los puntos normales.
El método basado en la distancia es un algoritmo común de detección de valores atípicos, que define los valores atípicos en función de la distancia del vecino más cercano. Estos métodos no sólo son adecuados para datos numéricos multidimensionales, sino que también tienen amplias aplicaciones en otros campos, como datos categóricos, datos de texto y datos de series temporales.
La detección de anomalías basada en distancia supone que la distancia del vecino más cercano de un valor atípico es mucho mayor que la de un punto normal. La forma más sencilla de resolver el problema es utilizar bucles anidados. El primer bucle atraviesa cada punto de datos y el segundo bucle realiza un juicio de excepción. Necesita calcular la distancia entre el punto actual y otros puntos una vez que se determina que la distancia entre el punto de datos adicional y el punto actual está dentro del rango. , el punto marcado es un punto no atípico y se marca automáticamente como un valor no atípico. La complejidad temporal de este cálculo es muy alta y, cuando la cantidad de datos es grande, este cálculo no es rentable. Por lo tanto, se necesitan métodos de poda para acelerar el cálculo de la distancia.
En las técnicas basadas en celdas, el espacio de datos se divide en celdas y el ancho de la celda es función del umbral D y la dimensionalidad de los datos. En concreto, cada dimensión se divide en las celdas más anchas. Los puntos de datos en una celda determinada y en las celdas adyacentes satisfacen ciertas propiedades, por lo que los datos se pueden procesar de manera más eficiente
Por ejemplo, en el caso bidimensional, la distancia entre las cuadrículas es, debería Cabe señalar Un punto es que el número de celdas de la cuadrícula se basa en la división del espacio de datos y no tiene nada que ver con el número de puntos en los datos. Este es un factor importante para determinar la eficiencia del método en datos de baja dimensión, donde el número de celdas de la cuadrícula puede ser pequeño. Por otro lado, este método no es adecuado para datos de alta dimensión. Para una celda determinada, sus vecinas se definen como el conjunto de celdas accesibles desde la celda a través de como máximo 1 límite entre celdas. Tenga en cuenta que dos celdas adyacentes en una esquina también son vecinas. Las celdas adyacentes son celdas a las que se puede llegar cruzando 2 o 3 fronteras. La imagen de arriba muestra una celda específica y su conjunto de vecinos. Al parecer, la celda interior tiene 8 vecinos y 40 vecinos. Luego podemos observar inmediatamente las siguientes propiedades:
El primer paso en este proceso es etiquetar directamente ciertos puntos de datos como no atípicos si sus celdas contienen más de uno debido al primer punto de la regla). Además, todas las celdas vecinas de estas celdas contienen sólo valores no atípicos. Para aprovechar al máximo el poder de poda de la primera regla, determine la suma de los puntos en cada celda y sus celdas vecinas. Si la suma es mayor que , todos estos puntos también se marcarán como valores no atípicos.
A continuación, utilice las capacidades de poda de la segunda regla. Para cada celda que contenga al menos un punto de datos, calcule la cantidad de puntos que contiene más la cantidad de puntos en las celdas adyacentes. Si el número de puntos no excede , todos los puntos de la celda se marcan como valores atípicos. En este punto, muchas celdas pueden estar marcadas como valores atípicos o no atípicos.
Los puntos de datos en las celdas que no están marcados como valores atípicos o no atípicos en este momento deben tener sus distancias vecinas más cercanas calculadas explícitamente. Incluso para estos puntos de datos, la distancia del vecino más cercano se puede calcular más rápido utilizando la estructura de celda. Considere las celdas que aún no se han marcado como valores atípicos o no atípicos. Estas celdas pueden contener tanto valores atípicos como no atípicos. La incertidumbre de los puntos de datos de una celda existe principalmente en el conjunto de puntos vecinos de la celda. No es posible saber mediante una regla si los puntos vecinos en una celda están dentro de un umbral de distancia, por lo que se requiere un cálculo de distancia explícito para determinar la cantidad de puntos entre un punto de datos de celda y su conjunto de puntos vecinos que están dentro de un umbral. distancia. Los puntos de datos con no más de una distancia menor que la distancia umbral se consideran valores atípicos. Tenga en cuenta que sólo se requieren cálculos explícitos de distancia entre puntos de la celda y puntos en la vecindad de la celda.
Esto se debe a que se sabe que todos los puntos de la vecindad están más cerca que cualquier punto en , y , y se sabe que todos los puntos en , y se sabe que están al menos . Por tanto, se pueden conseguir más ahorros de costes a la hora de calcular distancias.
Para un conjunto de datos determinado, los métodos basados en índices utilizan estructuras de índice multidimensionales (por ejemplo, en forma de árbol, en forma de árbol) para buscar puntos vecinos dentro del radio de cada objeto de datos. Dado que el número de objetos permitidos en la vecindad de un valor atípico ha alcanzado el límite superior, si se encuentran incluso más puntos adyacentes en la vecindad de un objeto de datos, se determina que el objeto no es un valor atípico. En el peor de los casos, la complejidad temporal de este algoritmo es: la dimensionalidad del conjunto de datos es y la cantidad de objetos en el conjunto de datos es. El algoritmo se escala bien a medida que aumenta la dimensionalidad del conjunto de datos, pero la estimación de la complejidad del tiempo solo tiene en cuenta el tiempo de búsqueda, y la tarea de crear el índice en sí requiere muchos cálculos complejos.
Los algoritmos basados en densidad incluyen principalmente factores de valores atípicos locales (LocalOutlierFactor, LOF) y algoritmos mejorados basados en LOF, como LOCI y CLOF. Aquí, tomamos LOF como ejemplo para presentarlo y practicarlo en detalle.
La detección basada en la distancia es adecuada para situaciones en las que la densidad de grupos individuales es relativamente uniforme. En la imagen siguiente, el valor atípico B se detecta fácilmente, mientras que para detectar valores atípicos más cercanos al valor atípico A, algunos puntos en el borde del grupo pueden descartarse como valores atípicos. Los algoritmos basados en densidad, como LOF, son más adecuados para grupos con diferentes densidades.
Entonces, ¿de dónde viene esta medida basada en la densidad? Todavía comienza con el cálculo de la distancia. De manera similar al concepto de "k-vecino más cercano", primero debemos definir una "k-distancia".
Para un objeto o en el conjunto de datos D, la distancia más alejada de los k puntos vecinos más cercanos se expresa como k-distancia(p), que se define como la relación entre un punto dado p y el objeto. o en el conjunto de datos D. La distancia d(p,o) entre , satisface:
Desde k-distancia, la extendemos - - al conjunto de puntos del objeto o.
Cuando se muestra en un plano bidimensional, la k vecindad del objeto o es en realidad un área circular con el objeto o como centro y k distancia como radio. En otras palabras, el concepto de k vecindad se amplía de "distancia" a "espacio".
Utilizando el concepto de vecindad, podemos dividir los puntos del conjunto de datos D en dos categorías según la distancia desde el objeto o:
La distancia alcanzable entre el punto dado p y el objeto o Se puede expresar matemáticamente de la siguiente manera:
La distancia alcanzable entre un punto dado p y el objeto o se puede expresar matemáticamente de la siguiente manera:
La distancia alcanzable entre un punto dado El punto p y el objeto o se pueden expresar matemáticamente. El método se expresa de la siguiente manera:
La distancia alcanzable entre un punto dado p y el objeto o se puede expresar matemáticamente de la siguiente manera: .
Este proceso de clasificación simplifica los cálculos posteriores y hace que los resultados del cálculo sean más precisos.
Podemos entender vívidamente "densidad" como el grado de agrupación de puntos, es decir, cuanto más corta es la distancia entre puntos, mayor es la densidad. Aquí, definimos la densidad de alcanzabilidad local usando el recíproco (nota, no la derivada) de la distancia de alcanzabilidad promedio de todos los puntos en la vecindad k de un punto p dado en el conjunto de datos D al objeto o.
?La fórmula de cálculo para la densidad local alcanzable de un punto p dado es:
Como puede verse en la fórmula, aquí hay una medida del punto p dado, y su La vecindad se calcula La distancia promedio alcanzable de todos los objetos o en un punto dado p. Cuanto mayor sea la densidad de accesibilidad local de un punto p determinado, más probable será que pertenezca al mismo grupo que los puntos de su vecindad; cuanto menor sea la densidad, más probable será que sea un valor atípico;
Representa la relación promedio entre la densidad de accesibilidad local de otros puntos cercanos al punto p y la densidad de accesibilidad local del punto p. Si la relación está más cerca de 1, la densidad de los puntos vecinos de o es aproximadamente la misma, y o puede pertenecer al mismo grupo que sus puntos vecinos si la relación es menor que 1, entonces la densidad de o es mayor que la densidad; de sus puntos vecinos, y o es un punto denso. Si la relación es mayor que 1, la densidad de o es menor que la densidad de sus puntos vecinos y o puede ser un valor atípico;
El valor LOF resultante es la puntuación atípica que necesitamos.
Hay una biblioteca LocalOutlierFactor en sklearn a la que se puede llamar directamente. A continuación se muestra una visualización de la imagen LOF.
La biblioteca LocalOutlierFactor se puede utilizar para la detección de valores atípicos no supervisados en un único conjunto de datos o para la detección de novedades en nuevos conjuntos de datos basados en conjuntos de datos normales existentes. Aquí realizaremos una detección de valores atípicos no supervisados en un único conjunto de datos.
Primero cree un conjunto de datos que contenga clústeres y valores atípicos. El conjunto de datos contiene dos grupos distribuidos normalmente con diferentes densidades y algunos valores atípicos. Sin embargo, nuestro etiquetado manual de puntos de datos aquí es en realidad inexacto. Puede haber algunos puntos aleatorios dispersos dentro de los grupos y, debido a las características de la distribución normal, algunos puntos del grupo estarán relativamente lejos de otros puntos. Aquí no podemos distinguirlos, por lo que los etiquetamos como "puntos dentro del grupo" o "valores atípicos" según cómo se generan.
Luego, el conjunto de datos construido se entrena utilizando la biblioteca LocalOutlierFactor para obtener etiquetas de entrenamiento y puntuaciones de entrenamiento (valores atípicos locales). Para facilitar la visualización gráfica, se realizan algunas transformaciones en las puntuaciones de entrenamiento.
Se puede ver que el modelo distingue con éxito la mayoría de los valores atípicos. Algunos "valores atípicos" dispersos dentro del grupo debido a razones aleatorias también se identifican como valores atípicos dentro del grupo, pero algunos "puntos del grupo" se desvían ligeramente de ellos. el grupo se identifican como valores atípicos.
? También se puede ver que el modelo tiene una buena discriminación entre grupos de diferentes densidades y utiliza diferentes umbrales de densidad para grupos de baja densidad y grupos de alta densidad para distinguir valores atípicos.
Por lo tanto, podemos sentir intuitivamente que en algunos casos, la identificación de valores atípicos basada en el modelo LOF puede ser más consistente con la situación real que la identificación basada en alguna regla de distribución estadística.