¿Qué algoritmo debo utilizar para detectar anomalías en las series temporales?

Question

Antecedentes

Trabajo en el Centro de Operaciones de Red, donde supervisamos los sistemas informáticos y su rendimiento. Una de las métricas clave a supervisar es el número de visitantes \customers actualmente conectado a nuestros servidores. Para hacerlo visible, nosotros (el equipo de operaciones) recopilamos métricas como datos de series temporales y dibujamos gráficos. Grafito nos permite hacerlo, tiene una API bastante rica que utilizo para construir un sistema de alertas para notificar a nuestro equipo si se producen caídas repentinas (en su mayoría) y otros cambios. Por ahora he establecido un umbral estático basado en el valor medio, pero no funciona muy bien (hay muchos falsos positivos) debido a la diferente carga durante el día y la semana (factor de estacionalidad).

Se parece a esto:

Los datos reales (un ejemplo para una métrica, rango de tiempo de 15 minutos; el primer número es un número de usuarios, el segundo - sello de tiempo ):

[{"target": "metric_name", "datapoints": [[175562.0, 1431803460], [176125.0, 1431803520], [176125.0, 1431803580], [175710.0, 1431803640], [175710.0, 1431803700], [175733.0, 1431803760], [175733.0, 1431803820], [175839.0, 1431803880], [175839.0, 1431803940], [175245.0, 1431804000], [175217.0, 1431804060], [175629.0, 1431804120], [175104.0, 1431804180], [175104.0, 1431804240], [175505.0, 1431804300]]}]

Lo que intento conseguir

He creado un script en Python que recibe puntos de datos recientes, los compara con la media histórica y alerta si hay un cambio o una caída repentina. Debido a la estacionalidad, el umbral "estático" no funciona bien y el script genera alertas falsas. Quiero mejorar un algoritmo de alerta para que sea más preciso y que funcione sin necesidad de ajustar constantemente el umbral de alerta.

Qué consejos necesito y qué cosas he descubierto

Buscando en Google me di cuenta de que estoy buscando algoritmos de aprendizaje automático para la detección de anomalías (no supervisados). Investigando un poco más, me di cuenta de que hay montones de ellos y es muy difícil entender cuál es el aplicable en mi caso. Debido a mis limitados conocimientos de matemáticas no puedo leer sofisticados artículos académicos y estoy buscando algo sencillo para un principiante en el campo.

Me gusta Python y estoy un poco familiarizado con R, así que estaré encantado de ver ejemplos para estos lenguajes. Por favor, recomiende un buen libro o artículo que me ayude a resolver mi problema. Gracias por su tiempo y discúlpenme por una descripción tan larga

Enlaces útiles

Preguntas similares:

• Series temporales y detección de anomalías
• Detección de anomalías en series temporales con Python
• Anomalías de las series temporales
• Algoritmos para la detección de anomalías en las series temporales
• Aplicación de wavelets a algoritmos de detección de anomalías basados en series temporales
• ¿Qué algoritmo debo utilizar?

Recursos externos:

• Aprendizaje automático - Lista de reproducción de detección de anomalías en YouTube
• Algoritmos de detección para la biovigilancia: Un tutorial

Answer 1

Creo que la clave está en el calificativo "inesperado" de tu gráfico. Para detectar el inesperado necesitas tener una idea de lo que es esperado .

Yo empezaría con un modelo de serie temporal simple como AR(p) o ARMA(p,q). Ajústelo a los datos y añada la estacionalidad necesaria. Por ejemplo, su modelo SAR(1)(24) podría ser: $y_{t}=c+\phi y_{t-1}+\Phi_{24}y_{t-24}+\Phi_{25}y_{t-25}+\varepsilon_t$ , donde $t$ es el tiempo en horas. Así, estarías prediciendo el gráfico para la siguiente hora. Siempre que el error de predicción $e_t=y_t-\hat y_t$ es "demasiado grande" se lanza una alerta.

Cuando estimes el modelo obtendrás la varianza $\sigma_\varepsilon$ del error $\varepsilon_t$ . Dependiendo de sus supuestos de distribución, como la normalidad, puede establecer el umbral basado en la probabilidad, como $|e_t|<3\sigma_\varepsilon$ para el 99,7% o un lado $e_t>3\sigma_\varepsilon$ .

El número de visitantes es probablemente bastante persistente, pero súper estacional. Podría funcionar mejor probar con dummies estacionales en lugar de la estacionalidad multiplicativa, entonces probaría con ARMAX donde X representa variables exógenas, que podrían ser cualquier cosa como dummy de vacaciones, dummies de horas, dummies de fin de semana, etc.

Answer 2

En el blog tecnológico de Netflix hay un artículo sobre su herramienta de detección robusta de anomalías (RAD). http://techblog.netflix.com/2015/02/rad-outlier-detection-on-big-data.html

Se ocupa de la estacionalidad y de conjuntos de datos de gran volumen, por lo que puede ajustarse a sus necesidades. El código es de código abierto Java y Apache Pig https://github.com/Netflix/Surus/blob/master/resources/examples/pig/rad.pig

El algoritmo subyacente se basa en el ACP robusto - véase el documento original aquí: http://statweb.stanford.edu/~candes/papers/RobustPCA.pdf

Answer 3

La mayoría de los algoritmos de detección de valores atípicos de los paquetes de código abierto son para datos de series temporales empresariales con baja frecuencia, datos de frecuencia diaria/semanal/mensual. Estos datos parecen ser para un área especializada que se captura en minutos, por lo que no estoy seguro de si la detección de valores atípicos de código abierto sería útil. Podría intentar adaptar estos enfoques a sus datos.

A continuación, expongo algunos enfoques de paquetes disponibles en código abierto R :

1. tsoutliers : Implementos Chen y Liu algoritmo de detección de valores atípicos en el marco de arima. véase mi anterior pregunta en este sitio. Fantástico enfoque, pero muy lento, no estoy seguro de si será capaz de manejar los datos de alta frecuencia como la suya. Tiene la ventaja de detectar todos los tipos de valores atípicos, como mencioné en mi pregunta/post anterior.
2. Twitter's Detección de anomalías : Utiliza Rosner's algoritmo para detectar anomalías basadas en series temporales. El algoritmo descompone las series temporales y luego detecta las anomalías. En mi opinión personal, esto no es eficiente y preciso en la detección de anomalías en las series temporales.
3. tsoutlier en el paquete de previsión: Similar al algoritmo de Twitter en cuanto a la descomposición de las series temporales y la posterior detección de valores atípicos. Solo detectará los valores atípicos aditivos o los pulsos.

Hay paquetes comerciales que tienen enfoques dedicados a tratar de detectar anomalias. Otro enfoque clásico es Tsay's algoritmo de detección de valores atípicos de series temporales, similar al enfoque de Chen y Liu, detecta diferentes tipos de valores atípicos. Recientemente también me topé con esta solución de software comercial llamada metafor que podría ser más adecuado para sus datos.

Espero que esto sea útil

Answer 4

Lo que otras respuestas no parecen mencionar es que su problema suena como un detección de puntos de cambio . La idea de la detección de puntos de cambio es que usted está buscando segmentos en sus datos que difieren significativamente en términos de propiedades (por ejemplo, la media, la varianza). Esto se puede conseguir utilizando la estimación de máxima verosimilitud, donde para $m$ la función de probabilidad es

$$ L(m, \tau_{1:m}, \theta_{1:(m+1)}) = \prod_{i=1}^{m+1} p(y_{(\tau_{i-1} + 1):\tau_i}\mid \theta_i) $$

donde $y_1,\dots,y_n$ son sus datos, $1 < \tau_1 <\dots<\tau_m<n$ son los puntos límite que marcan los cambios, y las distribuciones de probabilidad $p$ están parametrizados por $\theta_i$ para cada $i$ -segundo segmento. Esto se puede generalizar fácilmente a una variedad de situaciones. Existen varios algoritmos para encontrar los parámetros, incluyendo la búsqueda de la incógnita $m$ . También existen programas informáticos para estimar estos modelos, por ejemplo changepoint para R. Si quieres saber más, puedes consultar las siguientes publicaciones y las referencias que proporcionan:

Rebecca Killick e Idris A. Eckley. (2013) punto de cambio: Un paquete de R para el análisis de puntos de cambio. (documento en línea)

Eckley, I.A., Fearnhead, P. y Killick, R. (2011) Análisis de modelos de puntos de cambio. [en:] Modelos bayesianos de series temporales , eds. D. Barber, A.T. Cemgil y S. Chiappa, Cambridge University Press.

Answer 5

¿Ha probado a utilizar reglas de control estadístico de procesos (por ejemplo, Western Electric http://en.wikipedia.org/wiki/Western_Electric_rules )?

Los utilizo para los datos de las series temporales -a menudo con un toque de intuición sobre los datos- para evaluar si los datos están yendo a algún sitio que no quiero que vayan. Como en tu ejemplo, estas reglas dicen que si el delta / el cambio es consistente a lo largo de varios puntos de datos, señala que puede haber un problema.

También el Control Estadístico de Procesos (CEP) puede ser bueno para saber si se está mejorando o empeorando.

Uno de los problemas del CEP es que gran parte de él se basa en una distribución normal que probablemente no se adapte a sus datos, que no pueden ser inferiores a cero. Otros mejores que yo con SPC pueden sugerir opciones aquí. Me gusta utilizarlo para señalar un problema, pero, como todos los modelos, es mejor utilizarlo con un grano de conocimiento sobre los propios datos (y la fuente).