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. 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.

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 pušta LOF da radi visestruke projekcije i kombinuje rezultat za poboljšanu detekciju kvaliteta u velikim dimenzijama.
• Local Outlier Probability (LoOP) 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 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 predlaže metodu za merenje sličnosti i raznovrsnosti metoda za građenje naprednih autlajer detekcija koristeci LOF varijacije i druge algoritme.