Изворни код странице Faktor lokalnih neobičnih vrednosti

'''Faktor lokalnih neobičnih vrednosti''' ({{jez-eng-lat|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.<ref>{{Cite journal
| doi = 10.1145/335191.335388
| title = LOF: Identifying Density-based Local Outliers
|year=2000
|last1=Breunig| first1 = M. M.
|last2=Kriegel| first2 = H. -P. 
|last3=Ng| first3 = R. T.
|last4=Sander| first4 = J.
| journal = ACM SIGMOD Record
| volume = 29
|pages=93
| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/LOF.pdf
}}</ref> 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 algoritmom|OPTICS]] kao sto je koncept „daljina jezgra“ i „dostižnost distance“, koji se koriste za procenu lokalne gustine.

== Glavna ideja ==
[[Датотека:LOF-idea.svg|thumb|right|250px|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 <math>k</math> 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 <math>\mbox{k-distance}(A)</math> distanca objekta <math>A</math> 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 <math>N_k(A)</math>.

[[Датотека:Reachability-distance.svg|thumb|right|250px| 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“:
<math>\mbox{reachability-distance}_k(A,B)=\max\{\mbox{k-distance}(B), d(A,B)\}</math>
U rečima, „dostiznost distance“ objekta <math>A</math> ’’iz’’ <math>B</math> jeste prava distanca dva objekta, ali najmanje <math>\mbox{k-distance}</math> iz <math>B</math>. Objekti koji pripadaju ''k'' najbližem komšiji iz <math>B</math> (jezgro <math>B</math>, vidi [[DBSCAN|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 <math>A</math> je definisano sa
<math>\mbox{lrd}(A):=1/\left(\frac{\sum_{B\in N_k(A)}\mbox{dostiznost-distanca}_k(A, B)}{|N_k(A)|}\right)</math>
Koji je količnik prosečne dostiznosti distance objekta <math>A</math> „od“ svojih komšija. Zapazite da to nije prosečna dostiznost komšija od <math>A</math> (koji po definiciji su <math>\mbox{k-distance}(A)</math>), ali distanca na kojoj mogu biti „dostignuti“ „od“ svojih komšija.
Lokalne dostizne gustine se onda upoređuju sa onima koje komšije koriste
<math>
\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)
</math>
Koji je „prosek lokalnih gustina svojih komšija“ podeljen sa objektom lokalne gustine. Vrednost približno <math>1</math> indicira da je objekat uporediv sa svojim komšijama. Vrednost ispod <math>1</math> indicira gušću regiju a vrednost znacajno veca od <math>1</math> 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 system|network intrusion detection]].<ref>{{cite journal | title=A comparative study of anomaly detection schemes in network intrusion detection | year=2003 | authors=Ar Lazarevic, Aysel Ozgur, Levent Ertoz, Jaideep Srivastava, Vipin Kumar | journal=Proc. 3rd SIAM International Conference on Data Mining | url=http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf | pages=25–36 | access-date=27. 05. 2013 | archive-url=https://web.archive.org/web/20130717233143/http://www.siam.org/proceedings/datamining/2003/dm03_03LazarevicA.pdf | archive-date=17. 07. 2013 |url-status=dead | df= }}</ref>

== 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''<ref>{{Cite journal
| doi = 10.1145/1081870.1081891
| title = Feature bagging for outlier detection
|year=2005
|last1=Lazarevic| first1 = A.
|last2=Kumar| first2 = V.
|pages=157–166
| journal = Proc. 11th ACM SIGKDD international conference on Knowledge Discovery in Data Mining
}}</ref> pušta LOF da radi visestruke projekcije i kombinuje rezultat za poboljšanu detekciju kvaliteta u velikim dimenzijama.
* ''Local Outlier Probability'' (LoOP)<ref>{{Cite journal
| doi = 10.1145/1645953.1646195
| title = LoOP: Local Outlier Probabilities
|year=2009
|last1=Kriegel| first1 = H. -P. 
|last2=Kröger| first2 = P.
|last3=Schubert| first3 = E.
|last4=Zimek| first4 = A.
|pages=1649
| journal = Proc. 18th ACM Conference on Information and Knowledge Management (CIKM)
| url = http://www.dbs.ifi.lmu.de/Publikationen/Papers/LoOP1649.pdf
}}</ref> 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''<ref>{{cite journal | title=Interpreting and Unifying Outlier Scores | year=2011 | authors=Hans-Peter Kriegel, Peer Kröger, Erich Schubert, Arthur Zimek | journal=Proc. 11th SIAM International Conference on Data Mining | url=http://siam.omnibooksonline.com/2011datamining/data/papers/018.pdf | access-date=27. 05. 2013 | archive-url=https://web.archive.org/web/20150122172510/http://siam.omnibooksonline.com/2011datamining/data/papers/018.pdf | archive-date=22. 01. 2015 |url-status=dead | df= }}</ref> predlaze normalizaciju LOF autlajer skora na intervalu <math>[0:1]</math> 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''<ref>{{cite journal | title=On Evaluation of Outlier Rankings and Outlier Scores | year=2012 | authors=Erich Schubert, Remigius Wojdanowski, Hans-Peter Kriegel, Arthur Zimek | journal=Proc. 12 SIAM International Conference on Data Mining | url=http://siam.omnibooksonline.com/2012datamining/data/papers/107.pdf | access-date=27. 05. 2013 | archive-url=https://web.archive.org/web/20150122171603/http://siam.omnibooksonline.com/2012datamining/data/papers/107.pdf | archive-date=22. 01. 2015 |url-status=dead | df= }}</ref> predlaže metodu za merenje sličnosti i raznovrsnosti metoda za građenje naprednih autlajer detekcija koristeci LOF varijacije i druge algoritme.

== Reference ==
{{reflist}}

{{normativna kontrola}}

[[Категорија:Алгоритми машинског учења]]