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[уреди]

Glavna ideja LOF: poređenje lokalne gustine jedne tačke sa gustinama svojih komšija. A ima dosta manju gustinu nego njegove komšije.

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[уреди]

  1. ^ Breunig, M. M.; Kriegel, H. -P.; Ng, R. T.; Sander, J. (2000). „LOF: Identifying Density-based Local Outliers“. 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“. Proc. 3rd SIAM International Conference on Data Mining: 25–36. 
  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“. 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“. Proc. 11th SIAM International Conference on Data Mining. 
  6. ^ Erich Schubert, Remigius Wojdanowski, Hans-Peter Kriegel, Arthur Zimek (2012). „On Evaluation of Outlier Rankings and Outlier Scores“. Proc. 12 SIAM International Conference on Data Mining.