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 ${\displaystyle 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 ${\displaystyle {\mbox{k-distance}}(A)}$ distanca objekta ${\displaystyle 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 ${\displaystyle N_{k}(A)}$.

Ova distanca je korišćena da se definiše „dostiznost distance“: ${\displaystyle {\mbox{reachability-distance}}_{k}(A,B)=\max\{{\mbox{k-distance}}(B),d(A,B)\}}$ U rečima, „dostiznost distance“ objekta ${\displaystyle A}$ ’’iz’’ ${\displaystyle B}$ jeste prava distanca dva objekta, ali najmanje ${\displaystyle {\mbox{k-distance}}}$ iz ${\displaystyle B}$. Objekti koji pripadaju k najbližem komšiji iz ${\displaystyle B}$ (jezgro ${\displaystyle 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 ${\displaystyle A}$ je definisano sa ${\displaystyle {\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 ${\displaystyle A}$ „od“ svojih komšija. Zapazite da to nije prosečna dostiznost komšija od ${\displaystyle A}$ (koji po definiciji su ${\displaystyle {\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 ${\displaystyle {\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 ${\displaystyle 1}$ indicira da je objekat uporediv sa svojim komšijama. Vrednost ispod ${\displaystyle 1}$ indicira gušću regiju a vrednost znacajno veca od ${\displaystyle 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 ${\displaystyle [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