Lokalt emissionsniveau

Det lokale outlier-niveau er en algoritme i anomalidetektion , der blev foreslået af Markus M. Breunig, Hans-Peter Kriegel, Raymond T. Ng og Jörg Sander i 2000 for at finde afvigende datapunkter ved at måle den lokale afvigelse af et givet punkt givet dets naboer [1] .

Det lokale outlier-niveau deler koncepter med DBSCAN og OPTICS , såsom begreberne "grundlæggende afstand" og "opnåelig afstand" [2] , som bruges til at estimere lokal tæthed [3] .

Grundlæggende idé

Det lokale yderniveau er baseret på begrebet lokal tæthed, hvor lokalitet er givet af nærmeste naboer, hvis afstande bruges til at estimere tætheden. Ved at sammenligne et objekts lokale tæthed med dets naboers lokale tæthed er det muligt at identificere områder med en lignende tæthed og punkter, der har en væsentlig lavere tæthed end naboerne. Disse punkter betragtes som outliers . $k$

Lokal tæthed estimeres ved den typiske afstand et punkt kan "nåes" fra nabopunkter. Definitionen af "reachable distance" brugt i algoritmen er en yderligere foranstaltning for at opnå mere robuste resultater inden for klynger.

Formel beskrivelse

Lade være afstanden fra objektet til den k -te nærmeste nabo. Bemærk, at sættet af k nærmeste naboer inkluderer alle objekter på den afstand, og i tilfælde af en "node" kan indeholde mere end k objekter. Vi betegner mængden af k nærmeste naboer som . ${\mbox{k-distance}}(A)$ $EN$ $N_{k}(A)$

Denne afstand bruges til at bestemme den nåelige afstand ( eng. reachability-distance ):

${\mbox{reachability-distance}}_{k}(A,B)=\max\{{\mbox{k-distance}}(B),d(A,B)\}$

Med andre ord er den nåelige afstand for et objekt fra den sande afstand mellem de to objekter. Funktioner, der hører til punktets k nærmeste naboer (punktets "kernepunkter" , se DBSCAN ) anses for at være i samme afstand for mere stabile resultater. Bemærk, at denne afstand ikke er en afstand i matematisk forstand, da den ikke er symmetrisk. (En almindelig fejl er at anvende altid, så dette giver en lidt anderledes metode, kaldet den forenklede lokale outlier-metode [4] ) $EN$ $B$ $B$ $B$ ${\mbox{k-distance))$

Den lokale nåbarhedstæthed for et objekt er defineret som $EN$

${\mbox{lrd}}_{k}(A):=1/\left({\frac {\sum _{B\in N_{k}(A)}{\mbox{reachability-distance }}_{k}(A,B)}{|N_{k}(A)|}}\right)$ ,

som er det gensidige af den gennemsnitlige tilgængelighedsafstand for et objekt fra dets naboer. Bemærk, at dette ikke er naboernes gennemsnitlige tilgængelighedsafstand fra punktet (hvilket pr. definition skulle være ), men afstanden, hvormed A kan "nås" fra sine naboer. Med dublerede punkter kan denne værdi blive uendelig. $EN$ $EN$ ${\mbox{k-distance}}(A)$

De lokale nåbarhedstætheder sammenlignes derefter med naboernes lokale nåbarhedstætheder

${\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)$

som er den gennemsnitlige lokale nåbarhedstæthed for naboer divideret med den lokale nåbarhedstæthed for selve objektet. En værdi omtrent lig med , betyder, at objektet er sammenligneligt med dets naboer (og så er det ikke en outlier). En værdi mindre end betyder et tæt område (som kan være det indre), mens værdier væsentligt større end , angiver afvigelser. $en$ $en$ $en$

Fordele

På grund af tilgangens lokalitet er den lokale outlier-algoritme i stand til at detektere outliers i datasættet, som måske ikke er outliers i andre områder af datasættet. For eksempel er et punkt i en "lille" afstand til enhver tæt klynge en outlier, mens et punkt i en sparsom klynge kan have lignende afstande til sine naboer.

Mens algoritmens geometriske intuition kun gælder for lavdimensionelle vektorrum, kan algoritmen anvendes i enhver sammenhæng, hvor en ulighedsfunktion kan defineres. Det er eksperimentelt blevet vist, at algoritmen fungerer godt i en lang række situationer, og den udkonkurrerer ofte konkurrenter, for eksempel i indtrængningsdetektionssystemer [5] og på behandlede klassifikationsdata [6] .

Familien af metoder på lokalt afvigende niveau kan let generaliseres og derefter anvendes på forskellige andre problemer, såsom afvigende detektion i geografiske data, videostreams eller kreditnetværk [4] .

Ulemper og udvidelser

De resulterende værdier er svære at fortolke. En værdi på 1 eller endda mindre end én siger, at punktet er rent internt, men der er ingen klar regel om, at et punkt er en outlier. I et datasæt kan en værdi på 1,1 allerede betyde en outlier, i et andet datasæt og parametrisering (med stærke lokale udsving) kan en værdi på 2 stadig betyde et indre. Disse forskelle kan forekomme inden for det samme datasæt på grund af metodens lokalitet. Der er metodeudvidelser, der forsøger at forbedre algoritmen:

Featurebagging til funktionsdetektering [7] udfører en lokal outlier-algoritme på flere projektioner og kombinerer resultaterne for forbedret detektionskvalitet i høje dimensioner. Dette er den første ensemblebaserede tilgang til isolationsdetektion, for andre muligheder se Zimek, Campello og Sander [8] .
The Local Outlier Probability ( LOOP) [9] er en metode, der er afledt af den lokale outlier-metode, men bruger sparsommelig lokal statistik for at gøre metoden mindre følsom over for valget af parameteren k . Derudover skaleres de resulterende værdier til værdien af . $[0:1]$
At fortolke og forene Outlier Scores [ 10] involverer normalisering af outlier-estimatet til et interval ved hjælp af statistisk skalering for at øge anvendeligheden , og algoritmen kan betragtes som en forbedret version af ideen om den lokale outlier-sandsynlighed. $[0:1]$
On Evaluation of Outlier Rankings and Outlier Scores [ 11] tilbyder et middel til at måle ligheden og forskellen mellem metoder til at opbygge et avanceret ensemble af outlier-detektionsmetoder ved hjælp af varianter af den lokale outlier-niveaualgoritme og andre algoritmer og forbedre feature bagging-tilgangen, som blev diskuteret ovenfor.
Revideret Local Outlier Detection: A Generalized View of Locality with Applications to Spatial Outlier Detection, Video and Network Outlier Detection [4] diskuterer den generelle ramme i forskellige lokale outlier-detektionsmetoder (herunder den lokale outlier-algoritme, dens forenklede version og LLP) og omsætter hensyn til generelle principper. Disse principper anvendes derefter, for eksempel til at identificere outliers i geografiske data, videostreams og tilskrivningsnetværket.

Noter

↑ Breunig, Kriegel, Ng, Sander, 2000 , s. 93-104.
↑ I stedet for "opnåelig afstand" i litteraturen findes også navnet "rækkevidde".
↑ Breunig, Kriegel, Ng, Sander, 1999 , s. 262.
↑ 1 2 3 Schubert, Zimek, Kriegel, 2012 .
↑ Lazarevic, Ozgur, Ertoz, Srivastava, Kumar, 2003 , s. 25-36.
↑ Campos, Zimek, Sander, Campello et al., 2016 .
↑ Lazarevic og Kumar 2005 , s. 157-166.
↑ Zimek, Campello, Sander, 2014 , s. elleve.
↑ Kriegel, Kröger, Schubert, Zimek, 2009 , s. 1649–1652
↑ Kriegel, Kröger, Schubert, Zimek, 2011 , s. 13-24.
↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , s. 1047-1058.

Litteratur

Breunig MM, Kriegel H.-P., Ng RT, Sander JR LOF: Identifikation af tæthedsbaserede lokale outliers // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data . - 2000. - ( SIGMOD ). — ISBN 1-58113-217-4 . - doi : 10.1145/335191.335388 .
Breunig MM, Kriegel H.-P., Ng RT, Sander JR OPTICS-OF: Identification Local Outliers // Principles of Data Mining and Knowledge Discovery . - 1999. - T. 1704. - (Lecture Notes in Computer Science). - ISBN 978-3-540-66490-1 . - doi : 10.1007/978-3-540-48247-5_28 .
Lazarevic A., Ozgur A., Ertoz L., Srivastava J., Kumar V. En sammenlignende undersøgelse af anomalidetektionsskemaer i netværksindtrængningsdetektion // Proc. 3. SIAM International Conference on Data Mining . - 2003. Arkiveret 17. juli 2013 på Wayback Machine
Guilherme Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. Om evaluering af uovervåget outlier-detektion: foranstaltninger, datasæt og en empirisk undersøgelse // Data Mining and Knowledge Discovery. - 2016. - ISSN 1384-5810 . - doi : 10.1007/s10618-015-0444-8 .
Lazarevic A., Kumar V. Funktionsposer til afvigende detektering // Proc. 11. ACM SIGKDD internationale konference om Knowledge Discovery in Data Mining. - 2005. - doi : 10.1145/1081870.1081891 .
Zimek A., Campello RJGB, Sander JR Ensembles for unsupervised outlier detection // ACM SIGKDD Explorations Newsletter. - 2014. - T. 15 . - doi : 10.1145/2594473.2594476 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. LoOP: Local Outlier Probabilities // Proceedings of the 18th ACM conference on Information and knowledge management. - 2009. - ISBN 978-1-60558-512-3 . - doi : 10.1145/1645953.1646195 .
Kriegel H.-P., Kröger P., Schubert E., Zimek A. Interpreting and Unifying Outlier Scores // Proceedings of the 2011 SIAM International Conference on Data Mining. - 2011. - ISBN 978-0-89871-992-5 . - doi : 10.1137/1.9781611972818.2 .
Schubert E., Wojdanowski R., Zimek A., Kriegel HP Om evaluering af outlier-rangeringer og outlier-scores // Proceedings of the 2012 SIAM International Conference on Data Mining. - 2012. - ISBN 978-1-61197-232-0 . - doi : 10.1137/1.9781611972825.90 .
Schubert E., Zimek A., Kriegel H.-P. Lokal outlier-detektion genovervejet: En generaliseret visning af lokalitet med applikationer til rumlig, video- og netværksoutlier-detektion // Data Mining og Knowledge Discovery. - 2012. - doi : 10.1007/s10618-012-0300-z .

Machine learning og data mining
Opgaver	Klassifikationsproblem Læring uden lærer Lærerassisteret læring Regressions analyse AutoML Foreningens regler Feature Extraction Træning af træk Ranking træning Grammatisk afledning Online læring
At lære med en lærer	k-nærmeste nabo metode Naiv Bayes Classifier beslutningstræ Support vektor maskine Lineær regression Logistisk regression perceptron Ensembler af modeller Bagning boostning tilfældig skov Relevant vektormetode
klyngeanalyse	k-betyder metode Fuzzy klyngemetode Hierarkisk klyngedannelse EM algoritme BIRKE HELBREDE DBSCAN OPTIK Middel-forskydning
Dimensionalitetsreduktion	Faktoranalyse Hovedkomponentmetode CCA ICA LDA Ikke-negativ matrixudvidelse t-SNE
Strukturel prognose	Graf probabilistisk model Bayesiansk netværk Skjult Markov-model CRF
Anomali detektion	k-nærmeste nabo metode Lokalt emissionsniveau
Grafer sandsynlighedsmodeller	Bayesiansk netværk Markov netværk Skjult Markov-model
Neurale netværk	Begrænset Boltzmann-maskine selvorganiserende kort Aktiveringsfunktion Sigmoid softmax Radial basisfunktion Rygformeringsmetode Dyb læring Flerlagsperceptron Tilbagevendende neurale netværk lang korttidshukommelse Kontrolleret tilbagevendende blokering Konvolutionelt neuralt netværk U-Net Autoencoder
Forstærkende læring	Markov proces Bellmans ligning Grådig algoritme Q-læring SARSA Temporal forskel (TD)
Teori	Vapnik-Chervonenkis teori Bias-Dispersion Dilemma Beregningsmæssig læringsteori Empirisk risikominimering Occams læring PAC læring Statistisk læringsteori
Tidsskrifter og konferencer	NeurIPS ICML ML JMLR ArXiv:cs.LG