Détection d'anomalies

Dans l'exploration de données, la détection d'anomalies (en anglais, anomaly detection ou outlier detection^[1]) est l'identification d'éléments, d'événements ou d'observations rares qui soulèvent des suspicions en différant de manière significative de la majorité des autres données^[1].

Généralement, les anomalies indiquent un problème tel qu'une fraude bancaire, un défaut structurel, un problème médical ou une erreur dans un texte. Les anomalies sont également appelées des valeurs aberrantes, du bruit, des écarts ou des exceptions^[2].

Dans le contexte de détection d'intrusions sur un réseau informatique, les objets intéressants ne sont souvent pas des objets rares, mais des pics d'activités inattendus. Ce modèle n'adhère pas à la définition d'une anomalie en tant qu'objet rare et de nombreuses méthodes de détection d'anomalies (en particulier, des méthodes non supervisées) échouent à identifier ces anomalies, à moins que les anomalies aient été agrégées de manière appropriée. Dans de telles situations, un algorithme d'analyse par partitionnement de données peut être capable de détecter ces problèmes^[3].

Il existe trois grandes catégories de techniques de détection d'anomalies^[4] :

• les techniques de détection d'anomalies non supervisées détectent les anomalies dans un ensemble de données non étiquetées en supposant que la majorité des instances de l'ensemble de données sont normales et en recherchant les instances qui ne correspondent pas au reste des données ;
• les techniques de détection d'anomalies supervisées nécessitent un ensemble de données où les données sont étiquetées normales ou anormales et impliquent l'entrainement d'un classificateur (la principale différence par rapport à de nombreux autres problèmes de classification statistique réside dans la nature déséquilibrée de la détection des valeurs aberrantes) ;
• les techniques de détection d'anomalies semi-supervisées construisent un modèle représentant le comportement normal d'un ensemble de données normales, puis testent la probabilité qu'une instance de test soit compatible avec le modèle.

Applications

La détection d'anomalies est applicable dans divers domaines, tels que la détection d'intrusions, la détection de fraudes, la détection de défauts, la surveillance de l'état du système, la détection d'événements dans des réseaux de capteurs et la détection de perturbations d'un écosystème.

La détection d'anomalies est aussi souvent utilisée dans le prétraitement de données pour supprimer des données anormales d'un ensemble de données. Dans l'apprentissage supervisé, la suppression des données anormales de l'ensemble de données entraîne souvent une augmentation statistiquement significative de la précision de l'apprentissage^[5],[6].

Techniques populaires

Plusieurs techniques de détection d'anomalies ont été proposées dans la littérature^[7]. Certaines des techniques populaires sont :

• des techniques basées sur la densité (méthode des k plus proches voisins^[8],[9],[10], facteur local aberrant (en anglais, Local outlier factor (en))^[11], isolation forests^[12], et bien d'autres variantes de ce concept^[13]) ;
• subspace^[14], correlation-based^[15] and tensor-based^[16] outlier detection for high-dimensional data^[17] ;
• les machines à vecteurs de support à une classe^[18] ;
• les réseaux de neurones récurrents^[19], les auto-encodeurs ;
• les réseaux bayésiens^[19] ;
• les modèles de Markov cachés^[19] ;
• les analyses par partitionnement de données^[20],[21] ;
• la déviation des règles d'association ;
• la logique floue ;
• l'apprentissage ensembliste, en utilisant du feature bagging (en)^[22],[23], de la normalisation d'un score^[24],[25] ou l'introduction de diversité dans les modèles de l'ensemble^[26],[27].

Les performances des différentes méthodes dépendent beaucoup du jeu de données et des paramètres, et les méthodes présentent peu d'avantages systématiques par rapport aux autres lorsqu'elles sont comparées entre plusieurs jeux de données et de paramètres^[28],[29].

Application à la sécurité des données

La détection d'anomalies a été proposée par Dorothy Denning (en) en 1986 pour les systèmes de détection d'intrusion^[30]. La détection d'anomalies pour les systèmes de détection d'intrusion est normalement réalisée avec des seuils et des statistiques, mais peut également être réalisée avec le soft computing et l'apprentissage par induction (en anglais inductive learning)^[31].

Logiciel

ELKI (en) est un logiciel Java d'exploration de données open source qui contient plusieurs algorithmes de détection d'anomalies.

Références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Anomaly detection » (voir la liste des auteurs).

1. Arthur Zimek et Erich Schubert, Encyclopedia of Database Systems, Springer New York, 2017, 1–5 p. (ISBN 978-1-4899-7993-3, DOI 10.1007/978-1-4899-7993-3_80719-1), « Outlier Detection »
2. V. J. Hodge et J. Austin, « A Survey of Outlier Detection Methodologies », Artificial Intelligence Review, vol. 22, n^o 2,‎ 2004, p. 85–126 (DOI 10.1007/s10462-004-4304-y, CiteSeer^x 10.1.1.318.4023, lire en ligne)
3. Paul Dokas, Levent Ertoz, Vipin Kumar, Aleksandar Lazarevic, Jaideep Srivastava et Pang-Ning Tan, « Data mining for network intrusion detection », Proceedings NSF Workshop on Next Generation Data Mining,‎ 2002 (lire en ligne)
4. V. Chandola, A. Banerjee et V. Kumar, « Anomaly detection: A survey », ACM Computing Surveys, vol. 41, n^o 3,‎ 2009, p. 1–58 (DOI 10.1145/1541880.1541882)
5. Ivan Tomek, « An Experiment with the Edited Nearest-Neighbor Rule », IEEE Transactions on Systems, Man, and Cybernetics, vol. 6, n^o 6,‎ 1976, p. 448–452 (DOI 10.1109/TSMC.1976.4309523)
6. M. R. Smith et T. Martinez, The 2011 International Joint Conference on Neural Networks, 2011, 2690 p. (ISBN 978-1-4244-9635-8, DOI 10.1109/IJCNN.2011.6033571, lire en ligne), « Improving classification accuracy by identifying and removing instances that should be misclassified »
7. Arthur Zimek et Peter Filzmoser, « There and back again: Outlier detection between statistical reasoning and data mining algorithms », Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery, vol. 8, n^o 6,‎ 2018, e1280 (ISSN 1942-4787, DOI 10.1002/widm.1280)
8. E. M. Knorr, R. T. Ng et V. Tucakov, « Distance-based outliers: Algorithms and applications », The VLDB Journal the International Journal on Very Large Data Bases, vol. 8, n^os 3–4,‎ 2000, p. 237–253 (DOI 10.1007/s007780050006, CiteSeer^x 10.1.1.43.1842)
9. S. Ramaswamy, R. Rastogi et K. Shim « Efficient algorithms for mining outliers from large data sets » (2000) (DOI 10.1145/342009.335437)
   —Proceedings of the 2000 ACM SIGMOD international conference on Management of data – SIGMOD '00
10. F. Angiulli et C. Pizzuti « Fast Outlier Detection in High Dimensional Spaces » (2002) (DOI 10.1007/3-540-45681-3_2)
    —Principles of Data Mining and Knowledge Discovery
11. M. M. Breunig, H.-P. Kriegel, R. T. Ng et J. Sander « LOF: Identifying Density-based Local Outliers » (2000) (DOI 10.1145/335191.335388, lire en ligne)
    — « (ibid.) », Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data,‎ 2000, p. 93–104
12. (en) Fei Tony Liu, Kai Ming Ting et Zhi-Hua Zhou, Isolation Forest (2008 Eighth IEEE International Conference on Data Mining), décembre 2008, 413–422 p. (ISBN 978-0-7695-3502-9, DOI 10.1109/ICDM.2008.17, lire en ligne)
13. E. Schubert, A. Zimek et H. -P. Kriegel, « Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection », Data Mining and Knowledge Discovery, vol. 28,‎ 2012, p. 190–237 (DOI 10.1007/s10618-012-0300-z)
14. H. P. Kriegel, P. Kröger, E. Schubert et A. Zimek « Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data » (2009) (DOI 10.1007/978-3-642-01307-2_86)
    —Advances in Knowledge Discovery and Data Mining
15. H. P. Kriegel, P. Kroger, E. Schubert et A. Zimek « Outlier Detection in Arbitrarily Oriented Subspaces » (2012) (DOI 10.1109/ICDM.2012.21)
    —2012 IEEE 12th International Conference on Data Mining
16. H. Fanaee-T et J. Gama, « Tensor-based anomaly detection: An interdisciplinary survey », Knowledge-Based Systems, vol. 98,‎ 2016, p. 130–147 (DOI 10.1016/j.knosys.2016.01.027)
17. A. Zimek, E. Schubert et H.-P. Kriegel, « A survey on unsupervised outlier detection in high-dimensional numerical data », Statistical Analysis and Data Mining, vol. 5, n^o 5,‎ 2012, p. 363–387 (DOI 10.1002/sam.11161)
18. B. Schölkopf, J. C. Platt, J. Shawe-Taylor, A. J. Smola et R. C. Williamson, « Estimating the Support of a High-Dimensional Distribution », Neural Computation, vol. 13, n^o 7,‎ 2001, p. 1443–71 (PMID 11440593, DOI 10.1162/089976601750264965, CiteSeer^x 10.1.1.4.4106)
19. Simon Hawkins, Hongxing He, Graham Williams et Rohan Baxter, Data Warehousing and Knowledge Discovery, vol. 2454, coll. « Lecture Notes in Computer Science », 2002, 337 p. (ISBN 978-3-540-44123-6, DOI 10.1007/3-540-46145-0_17, lire en ligne), « Outlier Detection Using Replicator Neural Networks »
20. Z. He, X. Xu et S. Deng, « Discovering cluster-based local outliers », Pattern Recognition Letters, vol. 24, n^os 9–10,‎ 2003, p. 1641–1650 (DOI 10.1016/S0167-8655(03)00003-5, CiteSeer^x 10.1.1.20.4242)
21. R. J. G. B. Campello, D. Moulavi, A. Zimek et J. Sander, « Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection », ACM Transactions on Knowledge Discovery from Data, vol. 10, n^o 1,‎ 2015, p. 5:1–51 (DOI 10.1145/2733381)
22. A. Lazarevic et V. Kumar, Feature bagging for outlier detection (Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining), 2005, 157–166 p. (ISBN 978-1-59593-135-1, DOI 10.1145/1081870.1081891)
23. H. V. Nguyen, H. H. Ang et V. Gopalkrishnan « Mining Outliers with Ensemble of Heterogeneous Detectors on Random Subspaces » (2010) (DOI 10.1007/978-3-642-12026-8_29)
    —Database Systems for Advanced Applications
24. H. P. Kriegel, P. Kröger, E. Schubert et A. Zimek « Interpreting and Unifying Outlier Scores » (2011) (DOI 10.1137/1.9781611972818.2, CiteSeer^x 10.1.1.232.2719)
    —Proceedings of the 2011 SIAM International Conference on Data Mining
25. E. Schubert, R. Wojdanowski, A. Zimek et H. P. Kriegel « On Evaluation of Outlier Rankings and Outlier Scores » (2012) (DOI 10.1137/1.9781611972825.90)
    —Proceedings of the 2012 SIAM International Conference on Data Mining
26. A. Zimek, R. J. G. B. Campello et J. R. Sander, « Ensembles for unsupervised outlier detection », ACM SIGKDD Explorations Newsletter, vol. 15,‎ 2014, p. 11–22 (DOI 10.1145/2594473.2594476)
27. A. Zimek, R. J. G. B. Campello et J. R. Sander « Data perturbation for outlier detection ensembles » (2014) (DOI 10.1145/2618243.2618257)
    —Proceedings of the 26th International Conference on Scientific and Statistical Database Management – SSDBM '14
28. Guilherme O. Campos, Arthur Zimek, Jörg Sander, Ricardo J. G. B. Campello, Barbora Micenková, Erich Schubert, Ira Assent et Michael E. Houle, « On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study », Data Mining and Knowledge Discovery, vol. 30, n^o 4,‎ 2016, p. 891 (ISSN 1384-5810, DOI 10.1007/s10618-015-0444-8)
29. Anomaly detection benchmark data repository of the Ludwig-Maximilians-Universität München; Mirror at University of São Paulo.
30. D. E. Denning, « An Intrusion-Detection Model », IEEE Transactions on Software Engineering, vol. SE-13, n^o 2,‎ 1987, p. 222–232 (DOI 10.1109/TSE.1987.232894, CiteSeer^x 10.1.1.102.5127, lire en ligne)
31. H. S. Teng, K. Chen et S. C. Lu, Adaptive real-time anomaly detection using inductively generated sequential patterns (Proceedings of the IEEE Computer Society Symposium on Research in Security and Privacy), 1990, 401 p. (ISBN 978-0-8186-2060-7, DOI 10.1109/RISP.1990.63857, lire en ligne)

• Portail de l’informatique