Faktor lokalnih neobičnih vrednosti

Faktor lokalnih neobičnih vrednosti (engl. Local outlier factor, LOF, faktor lokalnih autlajera) je algoritam detekcija anomalija prezentovan u "LOF: Identifying Density-based Local Outliers" by Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng and Jörg Sander.^[1] Ideja LOF-a je poređenje lokalne gustine tačke komšiluka sa lokalnom gustinom svojih komšija. LOF deli deo koncepta sa DBSCAN i OPTICS kao sto je koncept „daljina jezgra“ i „dostižnost distance“, koji se koriste za procenu lokalne gustine.

Glavna ideja

Kao što je navedeno u naslovu lokalni outlier faktor je baziran na konceptu lokalne gustine, gde je lokalitet zadan sa $k$ najbližih komšija čija je distanca korišćena da se proceni gustina. Poređenjem lokalne gustine objekta sa lokalnim gustinama svojih komšija moze identifikovati regiju sličnih gustina i tačke koje imaju bitno manju gustinu nego komšije. One se smatraju outlier-ima. Lokalna gustina se procenjuje distancom sa koje jedna tačka moze biti „dohvaćena“ od svog komšije.

Formalno

Ako je ${\mbox{k-distance}}(A)$ distanca objekta $A$ od k najbližeg komšije. Zapazite da komplet „K“ najbližih komšija uključuje sve objekte na ovoj distanci, koji mogu biti više od „K“ objekata. Označavamo ovaj komplet „K“ najbližim komšijama kao $N_{k}(A)$ .

Ilustracija dostizanja distance. Objekti „B“ i „C“ imaju istu dostižnu distancu (k=3), dok „D“ ne postane „k“ najbliži komsija

Ova distanca je korišćena da se definiše „dostiznost distance“: ${\mbox{reachability-distance}}_{k}(A,B)=\max\{{\mbox{k-distance}}(B),d(A,B)\}$ U rečima, „dostiznost distance“ objekta $A$ ’’iz’’ $B$ jeste prava distanca dva objekta, ali najmanje ${\mbox{k-distance}}$ iz $B$ . Objekti koji pripadaju k najbližem komšiji iz $B$ (jezgro $B$ , vidi DBSCAN cluster analiza) su uzete u razmatranje da budu jednako udaljene. Razlog za ovu distancu je da se dobiju stabilniji rezultati. Zapazite da ovo nije distanca u matematičkoj definiciji jer nije simetrična.

Dostiznost lokalne gustine objekta $A$ je definisano sa ${\mbox{lrd}}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{dostiznost-distanca}}_{k}(A,B)}{|N_{k}(A)|}}\right)$ Koji je količnik prosečne dostiznosti distance objekta $A$ „od“ svojih komšija. Zapazite da to nije prosečna dostiznost komšija od $A$ (koji po definiciji su ${\mbox{k-distance}}(A)$ ), ali distanca na kojoj mogu biti „dostignuti“ „od“ svojih komšija. Lokalne dostizne gustine se onda upoređuju sa onima koje komšije koriste ${\mbox{LOF}}_{k}(A):={\frac {\sum _{B\in N_{k}(A)}{\frac {{\mbox{lrd}}(B)}{{\mbox{lrd}}(A)}}}{|N_{k}(A)|}}={\frac {\sum _{B\in N_{k}(A)}{\mbox{lrd}}(B)}{|N_{k}(A)|}}/{\mbox{lrd}}(A)$ Koji je „prosek lokalnih gustina svojih komšija“ podeljen sa objektom lokalne gustine. Vrednost približno $1$ indicira da je objekat uporediv sa svojim komšijama. Vrednost ispod $1$ indicira gušću regiju a vrednost znacajno veca od $1$ indicira autlajer.

Prednosti

Dok je geometrijska intuicija LOF-a primenljiva samo na vektorske prostore malih dimenzija, algoritam se može primeniti u bilo kom kontekstu različitosti funkcije. Eksperimentalno je pokazano da radi veoma dobro, često pobeđujuci oponente kao npr. network intrusion detection.^[2]

Nedostaci

Rezultujuće vrednosti su kolicničke vrednosti i teške za interpretaciju. Vrednost od 1 ili manje indicira čisti inlajer, ali nema pravila kada je tačka autlajer. U jednom setu podataka, vrednost 1.1 moze vec biti autlajer, u drugom setu podataka i parametara vrednost 2 moze biti inlajer. Ove razlike se mogu desiti u setu podataka zbog lokalne metode. Postoji produženje LOF-a koje može poboljšati LOF u ovim aspektima:

Feature Bagging for Outlier Detection^[3] pušta LOF da radi visestruke projekcije i kombinuje rezultat za poboljšanu detekciju kvaliteta u velikim dimenzijama.
Local Outlier Probability (LoOP)^[4] je metod izveden iz LOF-a ali koristi jeftine lokalne statistike da bi postao manje osetljiv na izbor parametra „K“.
Interpreting and Unifying Outlier Scores^[5] predlaze normalizaciju LOF autlajer skora na intervalu $[0:1]$ koristeći statisticko skaliranje da bi se povećala upotrebljivost i moze se sresti kao poboljšanja verzija LoOP ideje.
On Evaluation of Outlier Rankings and Outlier Scores^[6] predlaže metodu za merenje sličnosti i raznovrsnosti metoda za građenje naprednih autlajer detekcija koristeci LOF varijacije i druge algoritme.

Reference

^ Breunig, M. M.; Kriegel, H. -P.; Ng, R. T.; Sander, J. (2000). „LOF: Identifying Density-based Local Outliers” (PDF). ACM SIGMOD Record. 29: 93. doi:10.1145/335191.335388.
^ Ar Lazarevic, Aysel Ozgur, Levent Ertoz, Jaideep Srivastava, Vipin Kumar (2003). „A comparative study of anomaly detection schemes in network intrusion detection” (PDF). Proc. 3rd SIAM International Conference on Data Mining: 25—36. Архивирано из оригинала (PDF) 17. 07. 2013. г. Приступљено 27. 05. 2013.
^ Lazarevic, A.; Kumar, V. (2005). „Feature bagging for outlier detection”. Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining: 157—166. doi:10.1145/1081870.1081891.
^ Kriegel, H. -P.; Kröger, P.; Schubert, E.; Zimek, A. (2009). „LoOP: Local Outlier Probabilities” (PDF). Proc. 18th ACM Conference on Information and Knowledge Management (CIKM): 1649. doi:10.1145/1645953.1646195.
^ Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek (2011). „Interpreting and Unifying Outlier Scores” (PDF). Proc. 11th SIAM International Conference on Data Mining. Архивирано из оригинала (PDF) 22. 01. 2015. г. Приступљено 27. 05. 2013.
^ Erich Schubert, Remigius Wojdanowski, Hans-Peter Kriegel, Arthur Zimek (2012). „On Evaluation of Outlier Rankings and Outlier Scores” (PDF). Proc. 12 SIAM International Conference on Data Mining. Архивирано из оригинала (PDF) 22. 01. 2015. г. Приступљено 27. 05. 2013.

[1] Breunig, M. M.; Kriegel, H. -P.; Ng, R. T.; Sander, J. (2000). „LOF: Identifying Density-based Local Outliers” (PDF). ACM SIGMOD Record. 29: 93. doi:10.1145/335191.335388.

[2] Ar Lazarevic, Aysel Ozgur, Levent Ertoz, Jaideep Srivastava, Vipin Kumar (2003). „A comparative study of anomaly detection schemes in network intrusion detection” (PDF). Proc. 3rd SIAM International Conference on Data Mining: 25—36. Архивирано из оригинала (PDF) 17. 07. 2013. г. Приступљено 27. 05. 2013.

[3] Lazarevic, A.; Kumar, V. (2005). „Feature bagging for outlier detection”. Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining: 157—166. doi:10.1145/1081870.1081891.

[4] Kriegel, H. -P.; Kröger, P.; Schubert, E.; Zimek, A. (2009). „LoOP: Local Outlier Probabilities” (PDF). Proc. 18th ACM Conference on Information and Knowledge Management (CIKM): 1649. doi:10.1145/1645953.1646195.

[5] Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek (2011). „Interpreting and Unifying Outlier Scores” (PDF). Proc. 11th SIAM International Conference on Data Mining. Архивирано из оригинала (PDF) 22. 01. 2015. г. Приступљено 27. 05. 2013.

[6] Erich Schubert, Remigius Wojdanowski, Hans-Peter Kriegel, Arthur Zimek (2012). „On Evaluation of Outlier Rankings and Outlier Scores” (PDF). Proc. 12 SIAM International Conference on Data Mining. Архивирано из оригинала (PDF) 22. 01. 2015. г. Приступљено 27. 05. 2013.

[1]

[2]

[3]

[4]

[5]

[6]