When lookout sees crackle: Anomaly detection via kernel density estimation

1. El Problema

La detección de anomalías es crucial en dominios como la detección de fraude con tarjetas de crédito y estafas. El algoritmo anterior, denominado Lookout (propuesto por Kandanaarachchi y Hyndman, 2022), utilizaba estimación de densidad de núcleo (KDE) con un ancho de banda (bandwidth) basado en la homología persistente (diámetros de muerte de Rips) para identificar puntos con baja densidad.

Sin embargo, el algoritmo original presentaba varias limitaciones teóricas y prácticas:

1. Falta de consistencia teórica: No estaba garantizado que el estimador de densidad de núcleo fuera consistente (convergencia a la densidad real) para distribuciones con colas pesadas (heavy-tailed).
2. Robustez: El escalado min-max y la selección del ancho de banda basada en la "mayor brecha" (gap) en los diámetros de muerte eran sensibles a la presencia de anomalías extremas.
3. Correlaciones: El uso de una matriz de ancho de banda diagonal ignoraba las correlaciones entre variables, lo que podía degradar el rendimiento.
4. Estabilidad del ajuste: El ajuste de la Distribución Generalizada de Pareto (GPD) a los valores de "sorpresa" (surprisals) carecía de restricciones teóricas sobre la forma de la distribución límite.

2. Metodología Propuesta (Lookout v2)

Los autores proponen una versión modificada del algoritmo Lookout, fundamentada en nuevos resultados teóricos sobre la homología persistente y la teoría de valores extremos. Las tres modificaciones principales son:

A. Estándarización Robusta (Escalado)

En lugar del escalado min-max, el nuevo algoritmo utiliza un estimador robusto de covarianza (el estimador de Gnanadesikan-Kettenring ortogonalizado).

• Proceso: Se calcula la descomposición de Cholesky de la inversa de la matriz de covarianza robusta ($\hat{\Sigma}^{-1} = U'U$) y se transforman los datos: $z_i = U(y_i - m)$, donde $m$ es el vector de medianas.
• Beneficio: Esto elimina las correlaciones entre variables (rotación) y escala los datos para tener varianza unitaria, haciendo el estimador de densidad más eficiente y robusto a outliers.

B. Selección de Ancho de Banda Basada en Cuantiles

El algoritmo original seleccionaba el ancho de banda ($h_n$) basándose en el punto inferior de la mayor brecha en los diámetros de muerte de Rips ($d^*$).

• Nuevo enfoque: Se utiliza un cuantil superior de los diámetros de muerte de Rips, denotado como $d_{\gamma(n-1)}$ (donde $\gamma \in (0,1)$ es alto, ej. 0.98).
• Fundamento Teórico: Se demuestra que $d^*$ puede no converger a cero para distribuciones con colas pesadas (violando la condición de ancho de banda admisible). En cambio, se prueba que $d_{\gamma(n-1)}$ converge a cero y satisface las condiciones para la consistencia del estimador de densidad de núcleo incluso en presencia de colas pesadas.

C. Restricción del Parámetro de Forma en GPD

El algoritmo ajusta una Distribución Generalizada de Pareto (GPD) a los valores de sorpresa ($-\log \hat{f}(y_i)$).

• Restricción: Se fuerza al parámetro de forma ($\xi$) de la GPD a ser no positivo ($\xi \le 0$).
• Justificación: Dado que las estimaciones de densidad de núcleo están acotadas, la distribución límite de los extremos (según el teorema de Fisher-Tippett-Gnedenko) debe ser una distribución de Weibull, que tiene un parámetro de forma negativo. Esto mejora la estabilidad del ajuste.

3. Contribuciones Clave

1. Garantías Teóricas de Consistencia: Se demuestra que el estimador de densidad de núcleo utilizando el ancho de banda basado en cuantiles de diámetros de muerte es consistente bajo condiciones generales (incluyendo distribuciones con colas pesadas), resolviendo una incertidumbre teórica del trabajo anterior.
2. Análisis de "Crackle": Se adapta el concepto de "crackle" (introducido por Adler et al.) para analizar la homología persistente de ruido en distribuciones no gaussianas, demostrando que los métodos anteriores fallan en ciertos escenarios teóricos.
3. Mejora de Robustez: La combinación de escalado robusto y selección de ancho de banda basada en cuantiles hace que el algoritmo sea menos sensible a la presencia de anomalías extremas que distorsionan la estructura topológica global.
4. Implementación Práctica: Se proporciona una implementación en el paquete R lookout (versión actualizada) con valores predeterminados optimizados ($\alpha=0.001, \beta=0.90, \gamma=0.98$).

4. Resultados Experimentales

Los autores realizaron una serie de experimentos comparativos:

• Comparación con la versión anterior (Lookout v1):

  • En distribuciones Gamma con diferentes tasas de anomalía, la nueva versión mostró un mejor rendimiento promedio, especialmente cuando las anomalías eran más difíciles de distinguir (tasas bajas).
  • En distribuciones normales, ambos algoritmos fueron estadísticamente indistinguibles, pero la nueva versión mantuvo un rendimiento sólido.
  • En escenarios con grandes volúmenes de datos ($N$ creciente), la nueva versión logró tasas de verdaderos positivos más altas y falsos negativos más bajos, especialmente en tamaños de muestra pequeños.
  • En ejemplos de visualización (conjuntos de datos sintéticos y reales como "Old Faithful" y "Wine Reviews"), la nueva versión identificó anomalías en regiones de baja densidad de manera más coherente, aunque a veces detectó ligeramente más falsos positivos en zonas de baja densidad (lo cual es consistente con la definición de anomalía).

• Comparación con otros métodos (Ej. 5-7):

  • Se comparó con métodos basados en Teoría de Valores Extremos (HDoutliers, stray) y KDE (KDEOS, RDOS).
  • La nueva versión de Lookout superó o igualó a los otros métodos en métricas como F-measure, G-mean y AUC (Área bajo la curva ROC), demostrando ser competitiva y a menudo superior en la detección de anomalías sutiles en espacios de alta dimensión (hasta 20 dimensiones).

5. Significado y Conclusión

El artículo representa un avance significativo en la intersección entre el análisis topológico de datos (TDA) y la detección de anomalías estadística.

• Validación Teórica: Transforma un algoritmo heurístico en uno con garantías matemáticas de consistencia, lo cual es raro en el campo de la detección de anomalías basada en topología.
• Versatilidad: El algoritmo es adecuado para datos multivariados continuos y puede manejar dimensiones moderadas (hasta ~20).
• Limitaciones: La complejidad computacional está dominada por el cálculo de la homología persistente de Vietoris-Rips (equivalente a clustering de enlace simple), con una complejidad de $O(n \log n)$, lo que puede ser costoso para conjuntos de datos masivos. Además, la "maldición de la dimensionalidad" puede afectar el rendimiento en dimensiones muy altas sin reducción previa de dimensionalidad.

En resumen, la versión actualizada de Lookout ofrece una herramienta más robusta, teóricamente fundamentada y eficiente para la detección de anomalías, superando las limitaciones de su predecesor y estableciendo un nuevo estándar para el uso de la homología persistente en este contexto.