Local Outlier Factor (LOF)
- Introdotto da
- Breunig, M. M.; Kriegel, H.-P.; Ng, R. T.; Sander, J.
- Anno
- 2000
- Tipo
- Density-based anomaly detection (unsupervised)
Questo testo è una traduzione automatica e non è ancora stato revisionato. Leggi l’originale in inglese
A cosa serve?
Local Outlier Factor (LOF) è un algoritmo di rilevamento di anomalie non supervisionato basato sulla densità, introdotto da Breunig, Kriegel, Ng e Sander nel 2000.
Assegna a ciascun punto dati un punteggio di outlier continuo che quantifica quanto quel punto sia isolato rispetto al suo vicinato locale, consentendo il rilevamento di anomalie che i metodi globali non riescono a cogliere perché si fondono in cluster densi altrove nello spazio.
L’intuizione alla base del metodo
Immaginate una mappa cittadina dove la maggior parte delle persone vive in quartieri urbani densi. Una casa isolata in campagna è ovviamente tale. Ma LOF va oltre: può anche segnalare una casa situata in un sobborgo moderatamente denso quando tutti i suoi vicini immediati sono raggruppati in un cluster ancora più denso. Invece di chiedere 'questo punto è lontano da tutto?', LOF chiede 'il vicinato di questo punto è molto più sparso dei vicinati dei suoi stessi vicini?' Un punto i cui vicini vivono tutti più vicini tra loro rispetto al punto stesso ottiene un punteggio LOF elevato, segnalando che è un outlier locale anche se globalmente non si trova in una regione vuota.
Storia
LOF è stato introdotto da Markus Breunig, Hans-Peter Kriegel, Raymond Ng e Jörg Sander alla conferenza ACM SIGMOD 2000. Affrontava una limitazione riconosciuta dei metodi di outlier esistenti: che si basavano su soglie di distanza globali e quindi confondevano le anomalie locali con punti normali in regioni meno dense. L'articolo introdusse il concetto di densità locale di raggiungibilità e il punteggio LOF, che divenne rapidamente un riferimento fondamentale nel rilevamento di anomalie. Da allora è stato esteso da numerose varianti, tra cui LoOP (local outlier probabilities), LOCI e COF, ed è incluso nelle principali librerie di machine learning. L'articolo ACM SIGMOD 2000 ha accumulato migliaia di citazioni ed è considerato uno dei lavori fondamentali nel data mining basato sulla densità.
Quando usarlo
LOF è appropriato quando ci si aspetta che le anomalie si verifichino in cluster di densità variabile e quando una soglia di distanza globale mancherebbe gli outlier nascosti in regioni sparse o segnalerebbe erroneamente punti in cluster legittimamente sparsi ma coerenti. Funziona su qualsiasi spazio di feature continuo con una metrica di distanza significativa e non richiede esempi di anomalie etichettati (completamente non supervisionato). È adatto per applicazioni come il rilevamento di frodi, il rilevamento di intrusioni di rete, il controllo di qualità nella produzione e lo screening di anomalie mediche. Le principali ipotesi sono che gli inlier formino vicinati locali ragionevolmente coesi e che si possano calcolare distanze pairwise significative. LOF offre prestazioni migliori quando n è almeno nell'ordine delle decine o centinaia; per dati ad altissima dimensionalità (la maledizione della dimensionalità) le distanze diventano meno discriminanti ed è consigliabile prima la riduzione della dimensionalità o la selezione delle feature.
Limiti e considerazioni
- La complessità temporale quadratica nell'implementazione naive lo rende lento su dataset di grandi dimensioni senza indicizzazione approssimata dei vicini più prossimi.
- Sensibile alla scelta di k: un k troppo piccolo produce punteggi rumorosi; un k troppo grande sfuma la struttura locale.
- Le prestazioni degradano in spazi ad altissima dimensionalità a causa della maledizione della dimensionalità.
- Non scala naturalmente a dati in streaming o online senza ricalcolo.
- Non fornisce un modello che possa essere direttamente applicato per valutare nuovi punti senza accesso al set di addestramento.
Le condizioni della fonte non sostituiscono una revisione scientifica indipendente né la validazione da parte di un motore di analisi.
Punti di forza
- Rileva outlier locali in dataset con cluster di densità variabile, dove i metodi globali falliscono.
- Produce un punteggio continuo e interpretabile anziché un'etichetta binaria rigida, consentendo una scelta flessibile della soglia.
- Completamente non supervisionato: non sono richiesti dati di anomalie etichettati.
- Applicabile a qualsiasi spazio di feature con una metrica di distanza calcolabile, incluse distanze non euclidee.
- Robusto alla scala delle singole feature quando le distanze sono calcolate su dati standardizzati.
Applicazioni
- Rilevamento di frodi nelle transazioni finanziarie dove l'attività fraudolenta crea pattern localmente sparsi.
- Rilevamento di intrusioni di rete segnalando record di traffico il cui vicinato locale è molto più sparso dei suoi dintorni.
- Controllo di qualità nella produzione per identificare articoli difettosi in dati di produzione ricchi di sensori.
- Screening di anomalie mediche: rilevamento di profili paziente insoliti rispetto a coorti di pazienti simili.
- Rilevamento di anomalie spaziali in dati geografici e ambientali con densità eterogenea.
Come funziona
Come funziona
Per ogni punto p, l'algoritmo calcola innanzitutto la k-distanza: la distanza dal k-esimo vicino più prossimo di p. Questo definisce la portata del vicinato locale di p. Tutti i punti entro tale distanza formano il k-vicinato N_k(p). La scelta di k controlla la scala alla quale viene valutata la località: un k piccolo cattura la struttura locale fine, un k più grande la smussa.
Formula
k\text{-dist}(p) = \text{distance to the } k\text{-th nearest neighbor of } pLa distanza di raggiungibilità da p a un vicino o è definita come il massimo tra la k-distanza di o e la distanza euclidea effettiva (o altra metrica) tra p e o. Questa smussatura previene instabilità quando due punti sono estremamente vicini: sostituisce distanze minuscole con l'impronta più ampia del vicinato di o, rendendo le stime di densità più robuste.
Formula
\text{reach-dist}_k(p, o) = \max\{k\text{-dist}(o),\, d(p, o)\}La densità locale di raggiungibilità di p (lrd) è l'inverso della distanza media di raggiungibilità da p a tutti i suoi k vicini. Un punto circondato da vicini strettamente raggruppati ha una piccola distanza media di raggiungibilità e, di conseguenza, un lrd elevato. Un punto in una regione sparsa ha una grande distanza media di raggiungibilità e un lrd basso.
Formula
\text{lrd}_k(p) = \left(\frac{\sum_{o \in N_k(p)} \text{reach-dist}_k(p,o)}{|N_k(p)|}\right)^{-1}Il punteggio LOF di p è il rapporto medio tra i valori lrd dei suoi vicini e l'lrd di p stesso. Se i vicini di p hanno tutti un lrd sostanzialmente più elevato di p stesso, il che significa che vivono in sotto-regioni più dense, il rapporto supera 1, indicando che p è un outlier locale. Un punteggio vicino a 1 indica che p ha una densità approssimativamente uguale ai suoi dintorni. Punteggi molto maggiori di 1 segnalano punti sempre più anomali. Questo confronto consapevole della località è ciò che distingue LOF dai metodi basati solo sulla distanza.
Formula
\text{LOF}_k(p) = \frac{\sum_{o \in N_k(p)} \frac{\text{lrd}_k(o)}{\text{lrd}_k(p)}}{|N_k(p)|}Errori comuni
- Dimenticare di standardizzare o normalizzare le feature prima di calcolare le distanze, causando la dominanza di feature ad alta varianza.
- Utilizzare un singolo valore di k senza analisi di sensibilità; la best practice è valutare diversi valori di k.
- Trattare il punteggio LOF come una probabilità: è una misura relativa senza un'interpretazione probabilistica fissa.
- Ignorare la maledizione della dimensionalità nei dati ad alta dimensionalità e aspettarsi che LOF funzioni senza una precedente riduzione della dimensionalità.
- Impostare una soglia LOF arbitraria (es. punteggio > 1.5) senza ispezionare la distribuzione dei punteggi per il dataset specifico.
Domande frequenti
Come scelgo il valore corretto di k?
Non esiste un k universalmente ottimale. La pratica comune è valutare un intervallo di valori, tipicamente da 5 a 50, e ispezionare come cambiano la distribuzione dei punteggi e gli outlier segnalati. Un'analisi di sensibilità sui valori di k dà la certezza che le anomalie rilevate siano robuste alla scelta. La conoscenza del dominio sulla dimensione minima attesa del cluster può anche guidare il limite inferiore.
Cosa significa un punteggio LOF di 1 rispetto a 3?
Un punteggio vicino a 1 significa che il punto ha una densità locale approssimativamente uguale ai suoi vicini ed è considerato un inlier. Un punteggio significativamente maggiore di 1, spesso interpretato come superiore a 1.5 o 2 a seconda del dataset, indica che il vicinato del punto è molto più sparso dei vicinati dei suoi vicini. Non esiste un cutoff universale; la soglia dovrebbe essere scelta ispezionando la distribuzione dei punteggi LOF per il dataset specifico.
LOF può valutare punti nuovi e non visti senza riaddestramento?
LOF è un metodo trasduttivo: richiede la presenza del set di addestramento per calcolare vicinati e densità per qualsiasi nuovo punto. Per valutare nuove osservazioni, il set di addestramento deve essere conservato e ogni nuovo punto deve essere inserito per ricalcolare il suo k-vicinato rispetto ai punti di addestramento memorizzati. Alcune implementazioni offrono questa funzionalità, ma differisce fondamentalmente dai modelli parametrici che apprendono una funzione di punteggio compatta.
Come si confronta LOF con Isolation Forest per il rilevamento di anomalie?
LOF utilizza la stima della densità basata sui vicinati locali ed è più efficace quando le anomalie si raggruppano in regioni localmente sparse di uno spazio eterogeneo. Isolation Forest utilizza il partizionamento casuale ed è generalmente più veloce e scalabile a dataset di grandi dimensioni. Per dataset ad alta dimensionalità o molto grandi, Isolation Forest è spesso preferito; per dati a dimensionalità moderata con variazioni di densità, LOF offre frequentemente una discriminazione più fine.
Metodi correlati
Fonti
Breunig, M. M., Kriegel, H.-P., Ng, R. T., & Sander, J. (2000). LOF: Identifying density-based local outliers. Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, 93–104.
Apri il riferimento DOICopiato.Aggarwal, C. C. (2017). Outlier Analysis (2nd ed., Ch. 4). Springer.
ISBN: 978-3-319-47577-6Copiato.Hastie, T., Tibshirani, R., & Friedman, J. (2009). The Elements of Statistical Learning (2nd ed., Ch. 14). Springer.
ISBN: 978-0-387-84857-0Copiato.