Fattore anomala locale - Local outlier factor
| Parte di una serie su |
|
Apprendimento automatico e data mining |
|---|
 |
Nel rilevamento delle anomalie , il fattore anomala locale ( LOF ) è un algoritmo proposto da Markus M. Breunig, Hans-Peter Kriegel , Raymond T. Ng e Jörg Sander nel 2000 per trovare punti dati anomali misurando la deviazione locale di un dato punto dati rispetto ai suoi vicini.
LOF condivide alcuni concetti con DBSCAN e OPTICS come i concetti di "distanza centrale" e "distanza di raggiungibilità", utilizzati per la stima della densità locale.
Idea base
Il fattore outlier locale si basa su un concetto di densità locale, dove la località è data da k vicini più prossimi, la cui distanza viene utilizzata per stimare la densità. Confrontando la densità locale di un oggetto con le densità locali dei suoi vicini, è possibile identificare regioni di densità simile e punti che hanno una densità sostanzialmente inferiore rispetto ai loro vicini. Questi sono considerati valori anomali .
La densità locale è stimata dalla distanza tipica alla quale un punto può essere "raggiunto" dai suoi vicini. La definizione di "distanza di raggiungibilità" utilizzata in LOF è una misura aggiuntiva per produrre risultati più stabili all'interno dei cluster. La "distanza di raggiungibilità" utilizzata da LOF ha alcuni dettagli sottili che spesso si trovano errati in fonti secondarie, ad esempio nel libro di testo di Ethem Alpaydin.
Formale
Sia k -distance( A ) la distanza dell'oggetto A dal k -esimo vicino più prossimo. Si noti che l'insieme dei k vicini più prossimi include tutti gli oggetti a questa distanza, che nel caso di un "vincolo" può essere maggiore di k oggetti. Indichiamo l'insieme di k vicini più prossimi come N k (A) .
Questa distanza viene utilizzata per definire quella che viene chiamata distanza di raggiungibilità :
distanza-raggiungibilità k ( A , B )=max{ k -distanza( B ), d( A , B )}
In parole povere , la distanza di raggiungibilità di un oggetto A da B è la vera distanza dei due oggetti, ma almeno la k -distanza di B . Gli oggetti che appartengono ai k vicini più prossimi di B (il "nucleo" di B , vedi analisi cluster DBSCAN ) sono considerati ugualmente distanti. Il motivo di questa distanza è ottenere risultati più stabili . Nota che questa non è una distanza nella definizione matematica, poiché non è simmetrica. (Anche se è un errore comune usare sempre k -distance(A) , questo produce un metodo leggermente diverso, denominato Simplified-LOF)
La densità di raggiungibilità locale di un oggetto A è definita da
lrd k (A):=1 /( Σ B ∈ N k (A) raggiungibilità-distanza k (A, B)/| N k (A) |)
che è l'inverso della distanza media di raggiungibilità dell'oggetto A dai suoi vicini. Si noti che non è la raggiungibilità media dei vicini da A (che per definizione sarebbe la k -distance(A) ), ma la distanza alla quale A può essere "raggiunto" dai suoi vicini. Con punti duplicati, questo valore può diventare infinito.
Le densità di raggiungibilità locali vengono poi confrontate con quelle dei vicini utilizzando
LOF k (A):=Σ B ∈ N k (A)lrd k (B)/lrd k (A)/| N k (A) | = Σ B ∈ N k (A) lrd k (B)/| N k (A) | · lrd k (A)
che è la densità di raggiungibilità locale media dei vicini divisa per la densità di raggiungibilità locale dell'oggetto. Un valore di circa 1 indica che l'oggetto è paragonabile ai suoi vicini (e quindi non un valore anomalo). Un valore inferiore a 1 indica una regione più densa (che sarebbe un inlier), mentre valori significativamente maggiori di 1 indicano valori anomali.
LOF(k) ~ 1 significa densità simile a quella dei vicini,
LOF(k) < 1 significa Densità maggiore rispetto ai vicini (Inlier),
LOF(k) > 1 significa Densità inferiore rispetto ai vicini (Outlier)
Vantaggi
Grazie all'approccio locale, LOF è in grado di identificare valori anomali in un set di dati che non sarebbero valori anomali in un'altra area del set di dati. Ad esempio, un punto a una distanza "piccola" da un ammasso molto denso è un outlier, mentre un punto all'interno di un ammasso sparso potrebbe presentare distanze simili ai suoi vicini.
Mentre l'intuizione geometrica di LOF è applicabile solo a spazi vettoriali a bassa dimensionalità, l'algoritmo può essere applicato in qualsiasi contesto è possibile definire una funzione di dissomiglianza. È stato sperimentalmente dimostrato che funziona molto bene in numerose configurazioni, spesso superando i concorrenti, ad esempio nel rilevamento delle intrusioni di rete e sui dati di benchmark di classificazione elaborati.
La famiglia di metodi LOF può essere facilmente generalizzata e quindi applicata a vari altri problemi, come il rilevamento di valori anomali nei dati geografici, flussi video o reti di autori.
Svantaggi ed estensioni
I valori risultanti sono valori- quoziente e difficili da interpretare. Un valore di 1 o anche meno indica un inlier chiaro, ma non esiste una regola chiara per quando un punto è un outlier. In un set di dati, un valore di 1.1 potrebbe già essere un outlier, in un altro set di dati e parametrizzazione (con forti fluttuazioni locali) un valore di 2 potrebbe ancora essere un inlier. Queste differenze possono verificarsi anche all'interno di un set di dati a causa della località del metodo. Esistono estensioni di LOF che cercano di migliorare rispetto a LOF in questi aspetti:
- Feature Bagging for Outlier Detection esegue LOF su più proiezioni e combina i risultati per migliorare le qualità di rilevamento in dimensioni elevate. Questo è il primo approccio di apprendimento di insieme al rilevamento di valori anomali, per altre varianti vedere rif.
- Local Outlier Probability (LoOP) è un metodo derivato da LOF ma che utilizza statistiche locali poco costose per diventare meno sensibile alla scelta del parametro k . Inoltre, i valori risultanti vengono scalati in un intervallo di valori di [0:1] .
- Interpretare e unificare i punteggi anomali propone una normalizzazione dei punteggi anomali LOF all'intervallo [0:1] utilizzando il ridimensionamento statistico per aumentare l' usabilità e si può vedere una versione migliorata delle idee LoOP.
- On Evaluation of Outlier Rankings and Outlier Scores propone metodi per misurare la somiglianza e la diversità dei metodi per costruire insiemi avanzati di rilevamento degli outlier utilizzando varianti LOF e altri algoritmi e migliorare l'approccio Feature Bagging discusso sopra.
- Riconsiderazione del rilevamento degli outlier locali: una vista generalizzata sulla località con applicazioni per il rilevamento degli outlier spaziali, video e di rete discute il modello generale in vari metodi di rilevamento degli outlier locali (tra cui, ad esempio, LOF, una versione semplificata di LOF e LoOP) e ne astrae in un quadro generale. Questa struttura viene quindi applicata, ad esempio, per rilevare valori anomali in dati geografici, flussi video e reti di autori.
Riferimenti
- ^ Breunig, MM; Kriegel, H.-P. ; Ng, RT; Sander, J. (2000). LOF: identificazione dei valori anomali locali basati sulla densità (PDF) . Atti 2000 ACM SIGMOD International Conference on Management of Data . SIGMOD . pp. 93-104. doi : 10.1145/335191.335388 . ISBN 1-58113-217-4.
- ^ Breunig, MM; Kriegel, H.-P. ; Ng, RT; Sander, JR (1999). "OPTICS-OF: Identificazione dei valori anomali locali" (PDF) . Principi di data mining e scoperta della conoscenza . Appunti delle lezioni di Informatica. 1704 . pag. 262. doi : 10.1007/978-3-540-48247-5_28 . ISBN 978-3-540-66490-1.
- ^ Alpaydin, Ethem (2020). Introduzione al machine learning (quarta ed.). Cambridge, Massachusetts. ISBN 978-0-262-04379-3. OCLC 1108782604 .
- ^ a b c d Schubert, E.; Zimek, A.; Kriegel, H.-P. (2012). "Riconsiderazione del rilevamento degli outlier locali: una visione generalizzata della località con applicazioni per il rilevamento degli outlier spaziali, video e di rete". Data mining e scoperta della conoscenza . 28 : 190-237. doi : 10.1007/s10618-012-0300-z . S2CID 19036098 .
- ^ Lazarevic, A.; Ozgur, A.; Ertoz, L.; Srivastava, J.; Kumar, V. (2003). "Uno studio comparativo degli schemi di rilevamento delle anomalie nel rilevamento delle intrusioni di rete" (PDF) . Proc. 3a Conferenza Internazionale SIAM sul Data Mining : 25–36. Archiviato dall'originale (PDF) il 17/07/2013 . Estratto il 14/05/2010 .CS1 maint: utilizza il parametro autori ( link )
- ^ Campos, Guilherme O.; Zimek, Arthur; Sander, Jorg; Campello, Ricardo JGB; Micenková, Barbora; Schubert, Erich; assenso, Ira; Houle, Michael E. (2016). "Sulla valutazione del rilevamento outlier senza supervisione: misure, set di dati e uno studio empirico". Data mining e scoperta della conoscenza . 30 (4): 891–927. doi : 10.1007/s10618-015-0444-8 . ISSN 1384-5810 . S2CID 1952214 .
- ^ Lazarevic, A.; Kumar, V. (2005). "Insaccamento di funzionalità per il rilevamento di valori anomali". Proc. 11a Conferenza internazionale ACM SIGKDD sulla scoperta della conoscenza nel data mining : 157-166. doi : 10.1145/1081870.1081891 . ISBN 159593135X. S2CID 2054204 .
- ^ Zimek, A.; Campello, RJGB; Sander, JR (2014). "Ensemble per il rilevamento di valori anomali senza supervisione". ACM SIGKDD Newsletter esplorazioni . 15 : 11-22. doi : 10.1145/2594473.2594476 . S2CID 8065347 .
- ^ Kriegel, H.-P. ; Kröger, P.; Schubert, E.; Zimek, A. (2009). LoOP: probabilità anomale locali (PDF) . Atti del 18° Convegno ACM su Information and Knowledge Management . CIKM '09. pp. 1649–1652. doi : 10.1145/1645953.1646195 . ISBN 978-1-60558-512-3.
- ^ Kriegel, HP ; Kröger, P.; Schubert, E.; Zimek, A. (2011). Interpretazione e unificazione dei punteggi anomali . Atti della SIAM International Conference on Data Mining 2011. pp. 13-24. CiteSeerX 10.1.1.232.2719 . doi : 10.1137/1.9781611972818.2 . ISBN 978-0-89871-992-5.
- ^ Schubert, E.; Wojdanowski, R.; Zimek, A.; Kriegel, HP (2012). Sulla valutazione delle classifiche anomale e dei punteggi anomali . Atti della SIAM International Conference on Data Mining 2012. pp. 1047-1058. CiteSeerX 10.1.1.300.7205 . doi : 10.1137/1.9781611972825.90 . ISBN 978-1-61197-232-0.
