4 algoritmos para la detección de anomalías en series de tiempo

El problema de detección de anomalías en Ciencia de Datos es uno de los más complicados que existen, la razón principal de esta dificultad es la calidad elusiva de una definición formal de las anomalías. Si bien es cierto que fijado un problema concreto en Ciencia de Datos el contexto dicta con relativa precisión lo que significa una anomalía, dar una definición matemática es muy complicado pues hay diferentes razones por las que un punto dentro de una base de datos se considera una anomalía.

En este trabajo expondremos las ideas generales de 4 algoritmos para la detección de anomalías en series de tiempo, esta lista no es exhaustiva y efectivamente existen muchos otros métodos ampliamente utilizados. Los algoritmos que expondremos son los siguientes:

• Envolvente elíptica
• Alisamiento exponencial y Brutlag
• El algoritmo de Elastic Search
• El algoritmo de Azure, Microsoft

Referimos al lector a los artículos para más detalles, el objetivo de esta sección es proveer al lector de algunos detalles que lo ayuden a comprender mejor su funcionamiento.

Envolvente elíptica

El algoritmo de la envolvente elíptica se basa en el trabajo de Rousseeuw y está ideado para encontrar anomalías que satisfagan la primera de las cláusulas en la definición.

Distancia de Mahalanobis

La distancia de Mahalanobis es una función que nos permite calcular la distancia entre un punto y un conjunto de datos. Existen algunos casos particulares que explican el significado de esta noción:

• Supongamos que S es un conjunto generado de manera independiente por un vector aleatorio con coordenadas independientes, entonces la distancia de Mahalanobis corresponde con la distancia euclidiana entre el punto y el promedio de los puntos
• Ahora como un caso opuesto, supongamos que X es la probabilidad conjunta de variables dependientes, en ese caso la distancia de Mahalanobis será pequeña.

La siguiente proposición resume las principales propiedades de la distancia de Mahalanobis utilizadas en el algoritmo de la envolvente elíptica:

• Si fijamos un valor c en los reales, todos los valores x en los reales tales que D_M(x, S) = c tienen la misma ley de probabilidad de acuerdo a la ley gaussiana con esperanza μ_S y covarianza en función de c.
• Si S es un muestreo aleatorio obtenido vía una distribución normal, la distancia de Mahalanobis sigue una ley de probabilidad chi-cuadrada.

Algoritmo de la envolvente elítpica

El algoritmo de Elliptic Envelope hace uso de la segunda observación anterior. En búsqueda de una anomalía, suponiendo (nuestra hipótesis nula) que la variable aleatoria X que genera a S es gaussiana, se compara la distribución empírica de las distancias (D_M(x, S)) con la distribución chi-cuadrada que deberían de tener. Aquellos puntos que traspasen cierto límite estarán fuera de la elipse y por tanto serán considerados anomalías. Es importante mencionar que algunas veces estos cálculos pueden ser prohibitivos y por eso es necesario implementar algoritmos más veloces tal y como se hace en el artículo de Rousseeuw.

Alisamiento exponencial y Brutlag

Las técnicas de alisamiento exponencial son comúnmente utilizadas en la predicción de series de tiempo y se basan en la siguiente premisa:

• En una serie de tiempo la importancia de los coeficientes decrece exponencialmente respecto a la lejanía en el tiempo.

Dada una serie de tiempo {x₁, x₂, ..., xT} y un parámetro 1 > β > 0, definimos la predicción del alisamiento exponencial para el tiempo T+k (k en los naturales) con parámetro β utilizando la siguiente ecuación:

xₓ+k' = (1 - β) Σ (β^j xₓ-j)

Este método depende fuertemente de una elección adecuada de β y del cumplimiento de la siguiente hipótesis:

xₓ ~ Xₓ

Donde Xₓ es una familia de variables aleatorias equidistribuidas en el tiempo tales que E[Xₓ] = 0, Var[Xₓ] = 1 y Cov[Xₓ, Xₓ+k] = ρ^k.

En este caso si conocemos el valor de ρ, es posible aproximar por mínimos cuadrados el valor ideal de β. Notemos que en general es deseable suponer que β es independiente de k.

No es muy difícil convencerse de la equivalencia entre la definición anterior de la predicción xₓ+k' y alguna de las siguientes dos definiciones recursivas si iniciamos con x₁' = x₁:

1. xₓ' = β xₓ-1' + (1 - β) xₓ
2. xₓ' = xₓ-1' + (1 - β) (xₓ - xₓ-1')

Holt-Winters

Notemos que la primera ecuación recursiva de la observación anterior define una predicción en el tiempo t utilizando una combinación convexa del dato observado xₓ y nuestra predicción xₓ-1', eso significa que estamos aproximando mediante una línea horizontal alrededor del tiempo t.

Una manera más general de hacer lo anterior es mediante una recta con pendiente diferente de cero:

Dada una serie de tiempo {x₁, x₂, ...} y 1 > α, β > 0, definimos la predicción de Holt-Winters para el tiempo T+k (k en los naturales) con parámetros α, β utilizando la siguiente ecuación:

xₓ+k' = a₁(T)' + k a₂(T)'

Donde:

a₁(T)' = (1 - α) xT + α (a₁(T-1)' + a₂(T-1)') a₂(T)' = (1 - β) (a₁(T)' - a₂(T-1)') + β a₂(T-1)'

Nuevamente es posible calcular los parámetros α, γ utilizando mínimos cuadrados.

Brutlag

El algoritmo propuesto por Brutlag en el artículo define una banda alrededor de la serie de tiempo predicha por Holt-Winters cuando variamos el parámetro γ de temporalidad:

Dada una serie de tiempo {x₁, x₂, ...} y parámetros fijos 1 > α, β, γ > 0 y un parámetro de temporalidad m, definimos la desviación absoluta en el tiempo t:

dₓ = γ |xₓ - xₓ'| + (1 - γ) dₓ-m

Ahora definimos la banda a escala δ de Holt-Winters como la familia de los intervalos

(xₓ' - δ dₓ-m, xₓ' + δ dₓ-m)

Una anomalía de acuerdo a este algoritmo será un punto que sale de nuestras bandas de Holt-Winters.

El algoritmo de Elastic

A pesar de ser open-source y que es posible encontrar en línea diversos documentos audiovisuales sobre el algoritmo que detecta anomalías en Elastic Search, no existe un documento escrito que sea público con los detalles formales del algoritmo. Por tanto, aquello que se presenta aquí no pretende en lo absoluto ser una explicación completa del algoritmo, sino algunas suposiciones sobre el algoritmo basadas en tres fuentes fundamentales:

• El artículo escrito por dos autores de la compañía Prelert, la cual fue adquirida por Elastic Search junto a su algoritmo de detección de anomalías.
• El video de la exposición de Thomas Veasey disponible en la página de Elastic Net.
• El reporte técnico "Prelert Analytics vs. Holt-Winters Filtering" disponible en línea donde precisamente se hace una comparación entre Holt-Winters y el que era su algoritmo en ese tiempo.

Determinista y probabilístico

La ecuación del modelo que utiliza Elastic para predecir anomalías en series de tiempo es la siguiente:

Xₓ = xₓ + sₓ + cₓ + Mₓ ⋅ 1_cambio

Donde:

• xₓ es la componente de la tendencia,
• sₓ es la componente de la temporalidad,
• cₓ la componente de un calendario,
• la componente xₓ + sₓ + cₓ es una función lisa, sus parámetros incluyen características como la curvatura del modelo, entre otras,
• Mₓ es una familia de variables aleatorias cuyos valores esperados y varianzas cambian a través del tiempo,
• 1_cambio es una variable aleatoria que mide cambios en el modelo tal que en el caso multivariado sus coordenadas son independientes.

A diferencia del caso de Holt-Winters, el modelo de Elastic permite que las variables aleatorias varíen a través del tiempo en sus valores esperados y sus varianzas. Estos serán parámetros que el modelo irá aprendiendo.

La observación anterior implica en particular que la clase de anomalías que permite este algoritmo incluye aquellas que son generadas por una distribución diferente.

P-valor extendido

El siguiente concepto fue introducido en el artículo.

Sea X una variable aleatoria, si x es una observación, definimos la función q(x) = P({y en los reales: P_X(y) ≤ P_X(x)}).

Definimos el orden lineal de anomalías x <ₐ z si y solo si qₓ < qz.

Notemos que la definición anterior generaliza el concepto usual de p-valor: p(x) = P({y: y ≥ x} | H₀). De hecho, este concepto funciona correctamente incluso para el ejemplo que mencionamos en el segundo punto de la definición, es decir, puntos poco probables tendrán un pequeño p-valor generalizado incluso cuando no sean valores extremos.

Es bastante probable que el algoritmo de Elastic Search incluya este concepto de p-valor en sus detalles.

El Algoritmo de Azure

El algoritmo para la detección de anomalías de Azure está explicado con detalle en el artículo. Se basa en dos partes fundamentales: primero el cálculo del residuo espectral y después en una red convolucional que detecte los patrones proclives a ser anomalías.

Residuo espectral

A continuación definimos la noción de residuo espectral en el caso de funciones, para ello utilizaremos construcciones clásicas provenientes del análisis de Fourier. Es importante mencionar que las definiciones que daremos a continuación son para una señal f, sin embargo, el algoritmo de Azure utiliza solo una cantidad finita de puntos (nuestra base de datos) y en ese caso, en lugar de la transformada de Fourier, es necesario utilizar la transformada discreta de Fourier. El residuo espectral de una señal f se calcula de la siguiente manera:

Sea f una señal y (f_n) su espectro de amplitudes.

Definimos su espectro logarítmico de amplitudes como L(f) = log(f_n).

Definimos el espectro promediado de f como A(f) = h_n * L(f), donde 1/h_n² es una matriz de n×n con todas sus entradas iguales a uno.

Definimos el residuo espectral de f como la diferencia:

R(f) = L(f) - A(f)

Aplicando de nuevo la transformada inversa de Fourier a R(f) (su versión compleja de hecho) definimos la función de prominencia S(f) de f, que vuelve a ser una función en el dominio espacial.

A partir de ahí es posible definir un algoritmo para la detección de anomalías una vez que encontremos un parámetro τ tal que si S(f)(x) > τ, entonces x será considerado una anomalía. En general no se considerará la cantidad S(f)(x), sino un promedio ponderado tal como se hace en Holt-Winters.

El método anterior es similar al método propuesto para la detección de anomalías utilizando wavelets.

Redes neuronales convolucionales

Algunas veces el método que define a una anomalía únicamente si rebasa el factor τ es demasiado pobre. Por ello, el algoritmo de Azure añade un segundo paso para la detección de anomalías que consiste en generar datos sintéticos que por definición son anomalías respecto a la base de datos estudiada. Estos puntos los etiqueta como anomalías y, a partir de ahí, utilizando una red convolucional es capaz de predecir las anomalías en nuestro conjunto de datos.

¿Dónde aprender sobre series de tiempo y detección de anomalías?

En el Colegio de Matemáticas Bourbaki enseñamos con detalle las matemáticas y las bases para que nuestros estudiantes estén listos para aprender los modelos más avanzados de Inteligencia Artificial, Ciencia de Datos y Finanzas Cuantitativas. Estos son los dos cursos que están por comenzar y durarán todo el 2025‍

• Track de Ciencia de Datos. (49 semanas).
• Machine Learning & AI for the Working Analyst ( 12 semanas).
• Matemáticas para Ciencia de Datos ( 24 semanas).
• Especialización en Deep Learning. (12 semanas).
• Track de Finanzas Cuantitativas (49 semanas)
• Aplicaciones Financieras De Machine Learning E IA ( 12 semanas).
• Las matemáticas de los mercados financieros (24 semanas).
• Deep Learning for Finance (12 semanas).

Referencias

• Peter Rousseeuw and Katrien Driessen. A Fast Algorithm for the Minimum Covariance. Technometrics, 41(3):212–223, 1999
• JakeD. Brutlag. 14th Systems Administration Conference Aberrant Beha- vior Detection in Time Series for Network Monitoring. Proceedings of the 14th Systems Administration Conference (LISA 2000), (14):139–146, 2000
• Hansheng Ren, Bixiong Xu, Yujing Wang, Chao Yi, Congrui Huang, Xiao- yu Kou, Tony Xing, Mao Yang, Jie Tong, and QiZhang. Time-series ano- maly detection service at Microsoft. Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, 3330680(c):3009–3017, 2019.
• ThomasJ. Veasey and StephenJ. Dodson. Anomaly Detection in Application Performance Monitoring Data. International Journal of Machine Learning and Computing, 4(2):120–126, 2014.

‍