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

Antecedentes

Estoy trabajando en el Centro de operaciones de red, supervisamos los sistemas informáticos y su rendimiento. Una de las métricas clave para monitorear es una cantidad de visitantes \ clientes actualmente conectados a nuestros servidores. Para hacerlo visible, nosotros (el equipo de Ops) recopilamos métricas como datos de series temporales y dibujamos gráficos. Graphite nos permite hacerlo, tiene una API bastante rica que utilizo para construir un sistema de alerta 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 promedio pero no funciona muy bien (hay muchos falsos positivos) debido a la carga diferente 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 estoy tratando de lograr

Creé un script de Python que recibe puntos de datos recientes, los compara con el promedio histórico y alerta si hay un cambio o caída repentina. Debido a la estacionalidad, el umbral "estático" no funciona bien y el script genera alertas de falsos positivos. Quiero mejorar un algoritmo de alerta para ser más preciso y hacerlo funcionar sin ajustar constantemente el umbral de alerta.

Que consejo necesito y cosas que descubrí

Al buscar en Google, me di cuenta de que estoy buscando algoritmos de aprendizaje automático para la detección de anomalías (no supervisados). La investigación adicional mostró que hay toneladas de ellos y es muy difícil entender cuál es aplicable en mi caso. Debido a mi conocimiento matemático limitado, no puedo leer documentos académicos sofisticados y estoy buscando algo simple para un principiante en el campo.

Me gusta Python y estoy un poco familiarizado con R, por lo que me alegrará ver ejemplos de estos lenguajes. Recomiende un buen libro o artículo que me ayude a resolver mi problema. Gracias por su tiempo y disculpe por una descripción tan larga.

Enlaces útiles

Preguntas similares:

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

Recursos externos:

• Aprendizaje automático: lista de reproducción de detección de anomalías en YouTube
• Algoritmos de detección para biovigilancia: un tutorial

Creo que la clave es un calificador "inesperado" en su gráfico. Para detectar lo inesperado necesita tener una idea de lo que se espera .

$y_{t}=c+\phi y_{t-1}+\Phi_{24}y_{t-24}+\Phi_{25}y_{t-25}+\varepsilon_t$$t$$e_t=y_t-\hat y_t$ es "demasiado grande" lanzas una alerta.

$\sigma_\varepsilon$$\varepsilon_t$$|e_t|<3\sigma_\varepsilon$$e_t>3\sigma_\varepsilon$

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

En el blog de tecnología de Netflix hay un artículo sobre su herramienta Robust Anomaly Detection (RAD). http://techblog.netflix.com/2015/02/rad-outlier-detection-on-big-data.html

Se ocupa de la estacionalidad y los conjuntos de datos de muy alto volumen, por lo que puede ajustarse a sus requisitos. 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 un PCA robusto; consulte el documento original aquí: http://statweb.stanford.edu/~candes/papers/RobustPCA.pdf

La mayoría de los algoritmos de detección atípicos en el paquete de código abierto son para datos de series de tiempo de negocios 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 desviación de código abierto fuera útil sería útil. Podría intentar adaptar estos enfoques a sus datos.

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

1. tsoutliers : implementa el algoritmo de detección de valores atípicos de Chen y Liu en el marco de arima. vea mi pregunta anterior en este sitio. Enfoque fantástico, pero muy lento, no estoy seguro de si podrá manejar datos de alta frecuencia como el suyo. Tiene la ventaja de detectar todo tipo de valores atípicos como se menciona en mi pregunta / publicación anterior.
2. Detección de anomalías en Twitter : utiliza el algoritmo de Rosner para detectar anomalías basadas en series de tiempo. El algoritmo descompone series de tiempo y luego detecta anomalías. En mi opinión personal, esto no es eficiente ni preciso para detectar valores atípicos en series de tiempo.
3. tsoutlier en el paquete de pronóstico: similar al algoritmo de twitter en términos de descomposición de series de tiempo y luego detección de valores atípicos. Solo detectará valores atípicos o pulsos aditivos.

Hay paquetes comerciales que tienen enfoques dedicados para tratar de detectar anomolias. Otro enfoque clásico es el algoritmo de detección de valores atípicos de la serie temporal de Tsay , similar al enfoque de Chen y Liu que 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 adecuada para sus datos.

Espero que esto sea útil

$m$

$y_1,\dots,y_n$$1 < \tau_1 <\dots<\tau_m<n$$p$$\theta_i$$i$$m$changepoint paquete para R. Si desea obtener más información, puede consultar las siguientes publicaciones y las referencias que proporcionan:

Rebecca Killick e Idris A. Eckley. (2013) changepoint: un paquete R para el análisis del punto de cambio. (papel en línea)

Eckley, IA, Fearnhead, P. y Killick, R. (2011) Análisis de modelos de punto de cambio. [en:] Modelos de series temporales bayesianas , eds. D. Barber, AT Cemgil y S. Chiappa, Cambridge University Press.

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

Los uso para datos de series de tiempo, a menudo con un toque de intuición sobre los datos, para evaluar si los datos van a algún lugar al que no quiero que vayan. Al igual que su ejemplo, estas reglas dicen que si el delta / cambio es consistente en varios puntos de datos, señala que puede haber un problema.

También el Control Estadístico de Procesos (SPC) puede ser bueno para hacer ejercicio si está mejorando o empeorando que antes.

Un problema con SPC es que gran parte depende de una distribución normal que probablemente no se adapte a sus datos que no pueden ir por debajo de cero. Otros mejores que yo con SPC pueden sugerir opciones aquí. Me gusta usarlo para marcar un problema, pero, como todos los modelos, se usa mejor con una gran cantidad de conocimiento sobre los datos en sí (y la fuente).

Dado que la periodicidad de las series de tiempo debe entenderse bien, se puede idear un algoritmo simple pero efectivo basado en la diferenciación.

Una simple diferencia de un paso detectará una caída repentina de un valor anterior

pero si la serie tiene un fuerte componente periódico, esperaría que esa caída sea considerable de manera regular. En este caso, sería mejor comparar cualquier valor con su contraparte en el mismo punto del ciclo anterior, es decir, hace un período.

En el caso de la pregunta publicada, sería natural esperar dos componentes periódicos significativos, uno la duración de un día, el otro la duración de una semana. Pero esto no es una gran complicación, ya que la duración del período más largo puede dividirse claramente por la duración del período más corto.

$n$$24*7 = 168$

Si las gotas son más de un carácter proporcional, una simple diferencia no podrá detectar una caída repentina cuando la actividad es baja. En tales circunstancias, el algoritmo se puede modificar para calcular las relaciones en su lugar.

Hice algunas pruebas en R usando un conjunto de datos simulado. En él, los datos se muestrean 6 veces al día y hay fuertes períodos diarios y semanales, junto con otros ruidos y fluctuaciones. Las gotas se agregaron en lugares aleatorios y con duraciones entre 1 y 3.
Para aislar las gotas, primero se calcularon las relaciones a la distancia 42, luego un umbral establecido en 0.6, ya que solo un cambio negativo de cierto tamaño es de interés. Luego se calculó una diferencia de un paso y un umbral establecido en -0.5. Al final, un falso positivo parece haberse deslizado (el que está al final de la semana 16). Los gráficos a la izquierda y a la derecha muestran los mismos datos, solo que de diferentes maneras.

¿Sería más útil pensar en los cambios en las series de tiempo como el comienzo de una nueva tendencia en lugar de una anomalía? Tomar la diferencia entre los puntos adyacentes ayudaría a saber cuándo está cambiando la pendiente (derivada) y podría indicar el comienzo de una nueva tendencia en la fecha. También podría ser útil tomar las diferencias de los valores de diferencia (la segunda derivada). Hacer una búsqueda en Google sobre el "comienzo de la tendencia de series de tiempo) puede dar buenas sugerencias para los métodos. En los datos financieros se presta un retraso en la atención a las nuevas tendencias (¿compra o vende?) Por lo que hay documentos sobre este tema.

Una buena introducción a wavelet es "El mundo según las wavelets" de Hubbard, creo que es el autor.

Pude obtener algunos buenos resultados para series temporales de estacionalidad múltiple (diaria, semanal) usando dos algoritmos diferentes:

• Descomposición de tendencia estacional usando loess (o STL) para establecer la serie de punto medio.
• Regresión no lineal para establecer umbrales alrededor de ese punto medio, basado en la relación entre la varianza y el nivel.

STL realiza una descomposición en el dominio del tiempo de sus series de tiempo en un componente de tendencia, un único componente estacional y un resto. El componente estacional es su estacionalidad de alta frecuencia (p. Ej., Diaria), mientras que la tendencia incluye tanto la estacionalidad de baja frecuencia (p. Ej., Semanal) como la tendencia propiamente dicha. Puede separar los dos simplemente ejecutando STL nuevamente en la tendencia. De todos modos, una vez que aísle la serie restante de los otros componentes, puede realizar su detección de anomalías contra esa serie.

Hice una reseña más detallada aquí:

https://techblog.expedia.com/2016/07/28/applying-data-science-to-monitoring/

Inspirado por David, ¿has intentado usar FFT? Es posible que pueda detectar caídas repentinas porque están indicando sus anomalías. Las anomalías pueden aparecer en un espectro estrecho. Para que pueda capturarlos fácilmente.