Riepilogo Tecnico: Foreste PCA Randomizzate per il Rilevamento Non Supervisionato di Anomalie

Enunciato del Problema

Il rilevamento di anomalie è un compito fondamentale nel data mining e nell'apprendimento automatico, critico per applicazioni quali il rilevamento di intrusioni, la diagnosi di guasti e il rilevamento di frodi. Nonostante la proliferazione di nuovi algoritmi, valutazioni complete indicano che i metodi classici come il Vicino Più Vicino K (KNN) e il Fattore di Anomalia Locale (LOF) spesso rimangono lo stato dell'arte. Questi metodi affrontano efficacemente sfide quali i confini imprecisi tra dati normali e anomali e la presenza di rumore, ma soffrono di un'alta complessità computazionale dovuta alla necessità di ricerche esatte del vicino più vicino. Sebbene i metodi basati su alberi come la Foresta di Isolamento (iForest) offrano efficienza, si basano sulla selezione casuale delle caratteristiche, che potrebbe non catturare sempre in modo efficace la struttura sottostante dei dati ad alta dimensionalità. È necessario un metodo che bilanci l'efficienza computazionale con la robustezza, sfruttando la riduzione della dimensionalità senza sacrificare la capacità di rilevare sia anomalie globali che locali.

Metodologia

Gli autori propongono un nuovo metodo non supervisionato per il rilevamento di anomalie basato su Foreste PCA Randomizzate (RPCA). L'approccio adatta la Foresta RPCA, originariamente progettata per la ricerca approssimata del Vicino Più Vicino K (KNN), per il rilevamento di anomalie derivando un punteggio specifico per le anomalie dalle proprietà intrinseche della foresta.

Componenti Principali

1. Costruzione della Foresta RPCA:

   • Il metodo costruisce un ensemble di alberi. A differenza di iForest, che seleziona casualmente le caratteristiche, le Foreste RPCA utilizzano la PCA Randomizzata (Halko et al., 2011) a ogni nodo.
   • Alla radice e ai nodi successivi, i punti dati vengono proiettati in un sottospazio a dimensionalità inferiore utilizzando un piccolo numero di componenti principali ($p$). Questo preserva il valore informativo dello spazio delle caratteristiche originale riducendo al contempo la dimensionalità.
   • Criterio di Divisione: Invece di tagli casuali, l'algoritmo campiona i punti di divisione per ogni componente principale da una distribuzione di Laplace centrata sulla media. I punti dati vengono assegnati ai figli sinistro o destro sulla base di una votazione a maggioranza tra i $p$ componenti.
   • Criterio di Arresto: La crescita dell'albero continua fino a quando i nodi foglia contengono un numero di punti inferiore o uguale a una dimensione di vicinato predefinita ($k$).

2. Formulazione del Punteggio di Anomalia:
   Il metodo proposto definisce un punteggio di anomalia ($RPCAForestScore$) per un punto di query $q$ combinando due criteri distinti:

   • Anomalia basata sulla Profondità ($P(q)$): Basata sull'osservazione che le anomalie sono spesso isolate più precocemente nell'albero (profondità minore). Questo è calcolato come l'inverso normalizzato della profondità del nodo foglia contenente $q$ attraverso la foresta.
   • Anomalia basata sulla Distanza ($\mu_{dist}(q)$): Calcolata come la distanza euclidea media tra il punto di query $q$ e tutti gli altri punti all'interno dello stesso nodo foglia nello spazio delle caratteristiche originale.
   • Punteggio Finale: Il punteggio finale è il prodotto di questi due componenti:
     $$RPCAForestScore(q) = P(q) \times \mu_{dist}(q)$$
     Questa combinazione garantisce che anche se un'anomalia viene raggruppata con punti normali in una foglia (a causa della proiezione), la sua grande distanza dal centro del cluster nello spazio originale risulterà in un alto punteggio di anomalia.

3. Classificazione:
   Una soglia di anomalia è determinata utilizzando un parametro di contaminazione ($\alpha$), che rappresenta la percentuale attesa di anomalie. I punti con punteggi che superano il quantile $(1-\alpha)$ della distribuzione dei punteggi sono etichettati come anomalie.

Contributi Chiave

• Integrazione Innovativa: Il documento introduce la prima applicazione delle Foreste RPCA specificamente per il rilevamento non supervisionato di anomalie, colmando il divario tra la ricerca approssimata del vicino più vicino e il rilevamento di anomalie.
• Meccanismo di Punteggio Ibrido: Propone un punteggio composito di anomalia che sfrutta sia la profondità di isolamento strutturale (simile a iForest) sia la densità/distanza locale nello spazio delle caratteristiche originale (simile a KNN/LOF), mirando a superare i limiti dell'uso di una sola di queste metriche.
• Efficienza tramite PCA Randomizzata: Utilizzando la SVD randomizzata, il metodo raggiunge un'alta efficienza computazionale, in particolare per dati ad alta dimensionalità, poiché la complessità dipende dal numero di componenti principali piuttosto che dalla piena dimensionalità dei dati.
• Robustezza: Il metodo è progettato per essere robusto rispetto alla sintonizzazione degli iperparametri, richiedendo solo la selezione del numero di alberi, delle componenti principali ($p$) e della dimensione della foglia ($k$).

Risultati Sperimentali

Gli autori hanno valutato il metodo su 22 dataset diversificati provenienti da un repository di benchmark standard, confrontandolo con metodi classici e all'avanguardia tra cui KNN, KNNW, LOF, SLOF, ODIN, DAO e iForest. Le prestazioni sono state misurate utilizzando l'Area Sotto la Curva delle Caratteristiche Operative del Ricevitore (AUC).

• Prestazioni: La Foresta RPCA ha dimostrato prestazioni superiori o di secondo posto su molti dataset e si è mantenuta competitiva su altri. Ha mostrato una forza particolare nei dataset ad alta dimensionalità dove iForest (che utilizza la selezione casuale delle caratteristiche) ha faticato.
• Robustezza: Il metodo ha mantenuto prestazioni competitive utilizzando solo due impostazioni per il numero di componenti principali ($p=1$ e $p=5$), mentre i metodi concorrenti sono stati testati con 100 diverse configurazioni di iperparametri. Ciò suggerisce che il metodo proposto è meno sensibile alla sintonizzazione degli iperparametri.
• Studio di Ablazione: Esperimenti che separavano i componenti basati sulla profondità e basati sulla distanza hanno rivelato che il punteggio combinato ha superato significativamente il componente basato sulla profondità ed è stato generalmente competitivo o superiore al componente basato sulla distanza da solo.
• Efficienza: Sebbene iForest rimanga il metodo più veloce, la Foresta RPCA ha dimostrato una scalabilità significativamente migliore rispetto ai metodi basati su KNN all'aumentare delle dimensioni del dataset, mantenendo tempi di esecuzione efficienti adatti ai big data.
• Limitazioni Osservate: Il metodo ha mostrato prestazioni inferiori su dataset specifici (ad esempio ALOI, InternetAds, Annthyroid, Wilt). Gli autori attribuiscono ciò a:
  • Alta dimensionalità dove poche componenti principali ($p=1, 5$) sono state insufficienti per isolare le anomalie (InternetAds).
  • Anomalie molto simili ai punti normali, richiedendo più informazioni di quanto potesse fornire la $p$ selezionata (Annthyroid, Wilt).
  • La natura delle anomalie locali rispetto a quelle globali in dataset con estrazioni di caratteristiche specifiche (ALOI), dove i metodi basati sulla struttura locale (LOF) hanno superato l'approccio di proiezione globale.

Significato e Affermazioni

Il documento afferma che la Foresta RPCA offre un'alternativa robusta e computazionalmente efficiente per il rilevamento non supervisionato di anomalie. Il suo significato risiede nella capacità di:

1. Bilanciare Efficienza e Accuratezza: Fornisce un approccio "scatola bianca" alla ricerca di vicinato approssimato che utilizza la struttura interna dell'albero (tramite proiezioni PCA) invece di trattare la ricerca come una scatola nera.
2. Generalizzare Bene: Il metodo si comporta in modo competitivo su un'ampia gamma di dataset senza la necessità di un'ottimizzazione esaustiva degli iperparametri, affrontando il problema per cui molti nuovi metodi eccellono solo su istanze specifiche di problemi.
3. Rilevare sia Anomalie Globali che Locali: Teoricamente, il metodo è progettato per rilevare anomalie globali (tramite isolamento precoce nell'albero) e anomalie locali (tramite metriche di distanza nei nodi più profondi), sebbene gli autori riconoscano limitazioni con anomalie raggruppate.

Gli autori concludono che, sebbene il metodo non sia una soluzione universale per tutti i tipi di anomalie (in particolare le anomalie raggruppate), rappresenta una scelta solida per il rilevamento di anomalie a scopo generale, offrendo un compromesso favorevole tra la velocità computazionale dei metodi basati su alberi e l'accuratezza dei metodi basati sulla distanza.