When lookout sees crackle: Anomaly detection via kernel density estimation

Titolo e Contesto

Il paper presenta una versione aggiornata dell'algoritmo Lookout, progettato per il rilevamento di anomalie (outlier) utilizzando la stima della densità di probabilità tramite kernel (KDE). L'approccio originale, proposto da Kandanaarachchi e Hyndman (2022), si basava sulla topologia dei dati (persistent homology) per selezionare la larghezza di banda (bandwidth) del kernel. La nuova versione introduce garanzie teoriche di consistenza, migliora la robustezza e l'efficienza, e supera i limiti dell'algoritmo precedente, specialmente in presenza di distribuzioni con code pesanti.

1. Il Problema

Il rilevamento di anomalie è fondamentale in settori come la frode con carte di credito e la sicurezza. L'algoritmo Lookout originale identificava le anomalie adattando una Distribuzione di Pareto Generalizzata (GPD) ai logaritmi negativi delle stime di densità leave-one-out. Tuttavia, l'approccio originale presentava diverse debolezze teoriche e pratiche:

• Scelta della banda: La selezione della larghezza di banda basata sul massimo salto (gap) nei diametri di morte di Rips non garantiva la consistenza dello stimatore della densità, specialmente per distribuzioni con code pesanti (es. distribuzioni di potenza).
• Robustezza: La scalatura dei dati (min-max) e l'uso del gap massimo erano sensibili agli outlier.
• Correlazioni: La matrice di banda diagonale non teneva conto delle correlazioni tra le variabili.
• Stabilità della GPD: L'adattamento della GPD non sfruttava il fatto che le stime di densità sono limitate, portando a possibili instabilità nella stima dei parametri.

2. Metodologia e Contributi Chiave

Gli autori propongono tre modifiche fondamentali all'algoritmo Lookout, supportate da nuove dimostrazioni teoriche basate sulla teoria dei valori estremi (EVT) e sull'analisi topologica dei dati (TDA).

A. Teoria della Consistenza e Scelta della Banda

Il contributo teorico principale riguarda la selezione della larghezza di banda $h_n$.

• Il problema del "Crackle": Gli autori dimostrano che per distribuzioni con code pesanti, la scelta originale (basata sul massimo salto nei diametri di morte) non garantisce che la banda tenda a zero con la probabilità 1, rendendo lo stimatore inconsistente.
• Nuova Soluzione: Invece di usare il massimo salto, la nuova versione utilizza un quantile superiore dei diametri di morte di Rips ($d_{\gamma(n-1)}$ con $\gamma \in (0,1)$).
• Risultato Teorico: Viene dimostrato che $d_{\gamma(n-1)}$ è una banda ammissibile (consistente) per una vasta gamma di distribuzioni, incluse quelle con code pesanti, garantendo che l'errore quadratico medio integrato (MISE) tenda a zero.

B. Scalatura Robusta Multivariata

Invece della scalatura min-max (che è sensibile agli outlier), il nuovo algoritmo utilizza uno stimatore robusto della covarianza (Gnanadesikan-Kettenring ortogonalizzato).

• I dati vengono ruotati e scalati in modo che la matrice di covarianza trasformata sia approssimativamente l'identità.
• Questo elimina le correlazioni tra le variabili, rendendo la stima della densità più efficiente e robusta.

C. Vincoli sulla GPD

Poiché le stime di densità tramite kernel sono limitate superiormente, i logaritmi negativi di queste stime hanno una distribuzione limite di tipo Weibull (un caso particolare della GEV con parametro di forma $\xi < 0$).

• Il nuovo algoritmo vincola il parametro di forma $\xi$ della GPD a essere non positivo durante l'adattamento. Questo migliora notevolmente la stabilità numerica del fitting.

D. L'Algoritmo Modificato (Lookout v2)

L'algoritmo aggiornato segue questi passaggi:

1. Preprocessing: Scalatura e rotazione robusta dei dati.
2. Topologia: Calcolo dell'omologia persistente di Rips per ottenere i diametri di morte.
3. Banda: Selezione della banda come quantile superiore ($\gamma$) dei diametri di morte.
4. Stima Densità: Calcolo della KDE e dei valori leave-one-out.
5. Modellazione Estrema: Adattamento di una GPD ai logaritmi negativi delle densità, con vincolo $\xi \le 0$.
6. Classificazione: Assegnazione di un punteggio di probabilità; i punti con probabilità inferiore a una soglia $\alpha$ sono classificati come anomalie.

3. Risultati Sperimentali

Gli autori hanno condotto una serie di esperimenti su dati simulati e reali per confrontare la nuova versione (Lookout v2) con la vecchia (Lookout v1) e con altri metodi (HDoutliers, Stray, KDEOS, RDOS).

• Dati Simulati (Gamma e Normale):
  • In scenari con code pesanti (distribuzione Gamma), la nuova versione supera significativamente quella vecchia, specialmente quando le anomalie sono meno evidenti.
  • In scenari normali, le prestazioni sono comparabili o leggermente migliori, con una maggiore capacità di rilevare anomalie vicine alla regione non anomala.
  • La nuova versione mostra tassi di veri positivi più alti e falsi negativi più bassi, specialmente con campioni di dimensioni ridotte.
• Dati Reali:
  • Old Faithful (Geyser): La nuova versione identifica meglio le anomalie nelle regioni a bassa densità, evitando di etichettare erroneamente punti vicini al "nucleo" dei dati.
  • Recensioni di Vini: La nuova versione riduce drasticamente i falsi positivi rispetto alla vecchia, fornendo una selezione più pulita delle anomalie estreme.
• Confronto con altri metodi:
  • In esperimenti multidimensionali (fino a 20 dimensioni), Lookout v2 mantiene prestazioni competitive (misurate tramite AUC, F-measure e G-mean) rispetto ai metodi basati su EVT e KDE, spesso superando la versione precedente.

4. Significato e Conclusioni

Il paper rappresenta un avanzamento significativo nel campo del rilevamento di anomalie basato sulla densità e sulla topologia dei dati.

• Garanzie Teoriche: Fornisce la prima prova di consistenza per un algoritmo di rilevamento anomalie basato su persistent homology, risolvendo l'incertezza sulla scelta della banda per distribuzioni non-Gaussiane.
• Robustezza: L'uso di tecniche di scalatura robusta e di vincoli parametrici rende l'algoritmo più affidabile in scenari reali rumorosi.
• Versatilità: L'algoritmo è adatto per dati multivariati continui e gestisce bene dimensioni moderate (fino a ~20).
• Limitazioni: La complessità computazionale è dominata dal calcolo dell'omologia persistente di Rips (equivalente al clustering single-link), che richiede $O(n \log n)$, potendo diventare proibitiva per dataset molto grandi. Inoltre, soffre della "maledizione della dimensionalità" in spazi ad altissima dimensione senza pre-elaborazione (es. riduzione della dimensionalità).

In sintesi, Lookout v2 trasforma un metodo euristico in uno strumento statisticamente solido, offrendo punteggi di anomalia probabilistici con basi teoriche solide nella teoria dei valori estremi e nell'analisi topologica dei dati. L'implementazione è disponibile nel pacchetto R lookout.