Anomali upptäckt

Anomalidetektering (även känd som outlier-detektion [1] ) är identifiering under datautvinning av sällsynta data, händelser eller observationer som är misstänkta på grund av att de skiljer sig väsentligt från huvuddelen av data [1] . Vanligtvis kännetecknar avvikande data någon form av problem, såsom bankbedrägerier en strukturell defekt, medicinska problem eller fel i text. Anomalier hänvisas också till som extremvärden , konstigheter, brus, avvikelser eller undantag [2] .

Allmän diskussion

Avvikelseupptäckt i samband med upptäckt av skadlig användning och nätverksintrång, föremål av intresse är ofta inte sällsynta , men visar en oväntad aktivitet . Detta passar inte in i den vanliga statistiska definitionen av extremvärden som sällsynta objekt, och många metoder för detektering av extremvärden (särskilt oövervakade metoder ) misslyckas med sådana data tills data grupperas på lämpligt sätt. Å andra sidan kan klusteranalysalgoritmer lägga märke till mikrokluster som bildas av sådant beteende [ 3] .

Det finns ett brett utbud av kategorier av anomalidetekteringstekniker [4] . Den oövervakade anomalidetekteringstekniken upptäcker anomalier i omärkta testdatauppsättningar, under antagandet att det mesta av datauppsättningen är normal, genom att leta efter representanter som passar mindre bra med resten av datauppsättningen. Tekniken för detektering av övervakade anomalier kräver tillhandahållande av data märkta som "normala" och "onormala" och använder klassificerareträning (en nyckelskillnad från många andra klassificeringsproblem ligger i den inneboende obalanserade naturen hos avvikande detektering). Tekniken för detektering av partiellt övervakad anomali bygger en modell som representerar normalt beteende från en given uppsättning normal träningsuppsättning och testar sedan den resulterande modellen för rimlighet.

Applikationer

Avvikelsedetektering är tillämplig på ett brett spektrum av områden som intrångsdetektering , bedrägeridetektering , feldetektering, hälsoövervakning, händelsedetektering i sensornätverk och detektering av miljöstörningar. Ofta används anomalidetektering för att förbehandla data för att ta bort anomalier. Vid övervakat lärande leder borttagning av onormala data från en uppsättning ofta till en signifikant statistisk ökning av noggrannheten [5] [6] .

Populära tekniker

Flera anomalidetekteringstekniker har föreslagits i litteraturen [7] . Här är några populära tekniker:

• Densitetsbaserade tekniker ( k-närmaste grannar [8] [9] [10] , lokal extremnivå [11] , isolerande skogar [12] och många andra varianter av detta koncept [13] ).
• Underrymdsbaserad [14] och korrelationsbaserad [15] avvikelsedetektering för högdimensionella data [16] .
• Stöd vektormaskin för en klass [17] .
• Replikator av neurala nätverk [18] .
• Bayesianska nätverk [18] .
• Dolda Markov-modeller (HMM) [18] .
• Identifiering av extremvärden baserad på klusteranalys [19] [20] .
• Avvikelser från föreningens regler och täta set.
• Identifiering av extremvärden baserad på luddig logik .
• En ensembleteknik som använder feature bagging [21] [22] , poänggenomsnitt [23] [24] och dissimilarity source diskrimination [25] [26] .

Prestanda för olika metoder är data- och parameterberoende och har små systematiska fördelar gentemot varandra vid jämförelse mellan flera data och parameteruppsättningar [27] [28] .

Ansökan om dataskydd

Anomalidetektering föreslogs för system för intrångsdetektering av Dorothy Denning 1986 [29] . Anomalidetektering för intrångsdetekteringssystem görs vanligtvis med ett tröskelvärde och statistik, men kan göras med soft computing och induktiv inlärning [30] . De typer av statistik som erbjöds 1999 inkluderade profiler för användare, arbetsstationer , nätverk, fjärrvärdar, användargrupper och program baserade på frekvenser, medel och varianser [31] . Motsvarigheten till avvikelsedetektering vid intrångsdetektering är upptäckt av skadlig användning .

Programvara

• ELKI är en Java -verktygssats med öppen källkodför dataanalys som innehåller vissa algoritmer för upptäckt av anomalier samt indexbaserade acceleratorer för dem.

Dataset

• Dataarkiv för jämförelse av anomalidetekteringsalgoritmer vid universitetet i München ; Spegel vid universitetet i São Paulo .
• ODDS – ODDS: En stor samling offentligt tillgängliga datauppsättningar för upptäckt av extremvärden med verkliga situationer inom olika områden.

Se även

• Outliers i statistik
• Ändringsdetektering
• Nyhetsdetektering
• Hierarkiskt temporärt minne

Anteckningar

1. ↑ 1 2 Zimek, Schubert, 2017 , sid. 1–5.
2. ↑ Hodge, Austin, 2004 , sid. 85–126.
3. ↑ Dokas, Ertoz, Kumar et al., 2002 .
4. ↑ Chandola, Banerjee, Kumar, 2009 , sid. 1–58.
5. ↑ Tomek, 1976 , sid. 448–452.
6. ↑ Smith och Martinez, 2011 , sid. 2690.
7. ↑ Zimek, Filzmoser, 2018 , sid. e1280.
8. ↑ Knorr, Ng, Tucakov, 2000 , sid. 237–253.
9. ↑ Ramaswamy, Rastogi, Shim, 2000 , sid. 427.
10. ↑ Angiulli, Pizzuti, 2002 , sid. femton.
11. ↑ Breunig, Kriegel, Ng, Sander, 2000 , sid. 93–104.
12. ↑ Liu, Ting, Zhou, 2008 , sid. 413–422.
13. ↑ Schubert, Zimek, Kriegel, 2012 , sid. 190–237.
14. ↑ Kriegel, Kröger, Schubert, Zimek, 2009 , sid. 831.
15. ↑ Kriegel, Kroger, Schubert, Zimek, 2012 , sid. 379.
16. ↑ Zimek, Schubert, Kriegel, 2012 , sid. 363–387.
17. ↑ Schölkopf, Platt, Shawe-Taylor, Smola, Williamson, 2001 , sid. 1443–71.
18. ↑ 1 2 3 Hawkins, He, Williams, Baxter, 2002 , sid. 170–180.
19. ↑ He, Xu, Deng, 2003 , sid. 1641–1650
20. ↑ Campello, Moulavi, Zimek, Sander, 2015 , sid. 5:1-51.
21. ↑ Lazarevic och Kumar 2005 , sid. 157–166.
22. ↑ Nguyen, Ang, Gopalkrishnan, 2010 , sid. 368.
23. ↑ Kriegel, Kröger, Schubert, Zimek, 2011 , sid. 13–24.
24. ↑ Schubert, Wojdanowski, Zimek, Kriegel, 2012 , sid. 1047–1058.
25. ↑ Zimek, Campello, Sander (1), 2014 , sid. 11–22.
26. ↑ Zimek, Campello, Sander (2), 2014 , sid. ett.
27. ↑ Campos, Zimek, Sander et al., 2016 , sid. 891.
28. ↑ Se datauppsättningar nedan
29. ↑ Denning, 1987 , sid. 222–232.
30. ↑ Teng, Chen, Lu, 1990 , sid. 278–284.
31. ↑ Jones, Sielken, 1999 .

Litteratur

• Arthur Zimek, Erich Schubert. Outlier Detection // Encyclopedia of Database Systems . - Springer New York, 2017. - ISBN 9781489979933 . - doi : 10.1007/978-1-4899-7993-3_80719-1 .
• Hodge VJ, Austin J. A Survey of Outlier Detection Methodologies  // Artificial Intelligence Review. - 2004. - T. 22 , nr. 2 . - doi : 10.1007/s10462-004-4304-y .
• Paul Dokas, Levent Ertoz, Vipin Kumar, Aleksandar Lazarevic, Jaideep Srivastava, Pang-Ning Tan. Datautvinning för nätverksintrångsdetektering  // Proceedings NSF Workshop on Next Generation Data Mining. – 2002.
• Chandola V., Banerjee A., Kumar V. Anomaly detection: A survey // ACM Computing Surveys . - 2009. - T. 41 , nr. 3 . - doi : 10.1145/1541880.1541882 .
• Ivan Tomek. Ett experiment med den redigerade regeln för närmaste granne // IEEE-transaktioner på system, människa och cybernetik . - 1976. - T. 6 , nr. 6 . - doi : 10.1109/TSMC.1976.4309523 .
• Smith MR, Martinez T. Förbättra klassificeringsnoggrannheten genom att identifiera och ta bort instanser som borde vara felklassificerade // The 2011 International Joint Conference on Neural Networks . - 2011. - ISBN 978-1-4244-9635-8 . - doi : 10.1109/IJCNN.2011.6033571 .
• Arthur Zimek, Peter Filzmoser. Dit och tillbaka igen: Outlier-detektion mellan statistiska resonemang och datautvinningsalgoritmer // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. - 2018. - V. 8 , nr. 6 . — ISSN 19424787 . - doi : 10.1002/widm.1280 .
• Knorr EM, Ng RT, Tucakov V. Avståndsbaserade extremvärden: Algoritmer och applikationer // The VLDB Journal the International Journal on Very Large Data Bases. - 2000. - T. 8 , nr. 3–4 . - doi : 10.1007/s007780050006 .
• Ramaswamy S., Rastogi R., Shim K. Effektiva algoritmer för utvinning av extremvärden från stora datamängder // Proceedings of the 2000 ACM SIGMOD international conference on Management of data – SIGMOD '00. - 2000. - ISBN 1-58113-217-4 . - doi : 10.1145/342009.335437 .
• Angiulli F., Pizzuti C. Fast Outlier Detection in High Dimensional Spaces // Principles of Data Mining and Knowledge Discovery. - 2002. - T. 2431. - (Lecture Notes in Computer Science). — ISBN 978-3-540-44037-6 . - doi : 10.1007/3-540-45681-3_2 .
• Breunig MM, Kriegel H.-P., Ng RT, Sander J. LOF: Identifiering av densitetsbaserade lokala extremvärden // Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data . - 2000. - ( SIGMOD ). — ISBN 1-58113-217-4 . - doi : 10.1145/335191.335388 .
• Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou. Isolation Forest  // 2008 åttonde IEEE internationella konferens om datautvinning. - 2008. - ISBN 9780769535029 . - doi : 10.1109/ICDM.2008.17 .
• Schubert E., Zimek A., Kriegel H.-P. Lokal avvikandedetektering omprövat: En generaliserad syn på lokalitet med applikationer för rumslig, video- och nätverksavvikandedetektering // Data Mining och Knowledge Discovery. - 2012. - T. 28 . - doi : 10.1007/s10618-012-0300-z .
• Kriegel HP, Kröger P., Schubert E., Zimek A. Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data // Framsteg i Knowledge Discovery and Data Mining. - 2009. - T. 5476. - (Lecture Notes in Computer Science). - ISBN 978-3-642-01306-5 . - doi : 10.1007/978-3-642-01307-2_86 .
• Kriegel HP, Kroger P., Schubert E., Zimek A. Outlier Detection in Arbitrarily Oriented Subspaces // 2012 IEEE 12th International Conference on Data Mining. - 2012. - ISBN 978-1-4673-4649-8 . - doi : 10.1109/ICDM.2012.21 .
• Zimek A., Schubert E., Kriegel H.-P. En undersökning om oövervakad upptäckt av extremvärden i högdimensionell numerisk data // Statistical Analysis and Data Mining. - 2012. - V. 5 , nr. 5 . - doi : 10.1002/sam.11161 .
• Schölkopf B., Platt JC, Shawe-Taylor J., Smola AJ, Williamson R.C. Uppskattning av stödet för en högdimensionell distribution // Neural Computation. - 2001. - T. 13 , nr. 7 . doi : 10.1162 / 089976601750264965 . — PMID 11440593 .
• Simon Hawkins, Hongxing He, Graham Williams, Rohan Baxter. Outlier-detektion med hjälp av replikatorns neurala nätverk // Datalager och kunskapsupptäckt. - 2002. - T. 2454. - (Lecture Notes in Computer Science). - ISBN 978-3-540-44123-6 . - doi : 10.1007/3-540-46145-0_17 .
• He Z., Xu X., Deng S. Upptäcker klusterbaserade lokala extremvärden // Mönsterigenkänningsbrev. - 2003. - T. 24 , nr. 9–10 . - doi : 10.1016/S0167-8655(03)00003-5 .
• Campello RJGB, Moulavi D., Zimek A., Sander J. Hierarkiska densitetsuppskattningar för datakluster, visualisering och avvikande upptäckt // ACM-transaktioner på kunskapsupptäckt från data. - 2015. - T. 10 , nr. 1 . - doi : 10.1145/2733381 .
• Lazarevic A., Kumar V. Funktionspåsar för avvikande upptäckt // Proc. 11:e ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. - 2005. - ISBN 978-1-59593-135-1 . - doi : 10.1145/1081870.1081891 .
• Nguyen HV, Ang HH, Gopalkrishnan V. Mining Outliers with Ensemble of Heterogeneous Detectors on Random Subspaces // Databas Systems for Advanced Applications. - 2010. - T. 5981. - (Lecture Notes in Computer Science). - ISBN 978-3-642-12025-1 . - doi : 10.1007/978-3-642-12026-8_29 .
• Kriegel HP, 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 utvärdering av outlier-rankningar och outlier-poäng // Proceedings of the 2012 SIAM International Conference on Data Mining . - 2012. - ISBN 978-1-61197-232-0 . - doi : 10.1137/1.9781611972825.90 .
• Zimek A., Campello RJGB, Sander JR Ensembler för oövervakad detektering av extremvärden // ACM SIGKDD Explorations Newsletter. - 2014. - T. 15 . - doi : 10.1145/2594473.2594476 .
• Zimek A., Campello RJGB, Sander JR Datastörning för ensembler för detektering av extremvärden // Proceedings of the 26th International Conference on Scientific and Statistical Database Management – ​​SSDBM '14. - 2014. - ISBN 978-1-4503-2722-0 . - doi : 10.1145/2618243.2618257 .
• Guilherme O. Campos, Arthur Zimek, Jörg Sander, Ricardo JGB Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. Om utvärdering av oövervakad upptäckt av extremvärden: mått, datauppsättningar och en empirisk studie // Data Mining and Knowledge Discovery. - 2016. - T. 30 , nr. 4 . - ISSN 1384-5810 . - doi : 10.1007/s10618-015-0444-8 .
• Denning DE An Intrusion-Detection Model  // IEEE-transaktioner på mjukvaruteknik . - 1987. - T. SE-13 , nr. 2 . - doi : 10.1109/TSE.1987.232894 .
• Teng HS, Chen K., Lu SC Adaptiv anomalidetektering i realtid med hjälp av induktivt genererade sekventiella mönster  // Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy. - 1990. - ISBN 978-0-8186-2060-7 . - doi : 10.1109/RISP.1990.63857 .
• Anita K. Jones, Robert S. Sielken. Datasystemintrångsdetektion: En undersökning // Teknisk rapport, Institutionen för datavetenskap,. — University of Virginia, Charlottesville, VA, 1999.