Выявление аномалий

Выявление аномалий (обнаружение выбросов^[1]) — опознавание во время интеллектуального анализа данных редких данных, событий или наблюдений, которые вызывают подозрения ввиду существенного отличия от большей части данных^[1]. Обычно аномальные данные характеризуют некоторый вид проблемы, такой как мошенничество в банке^[англ.], структурный дефект, медицинские проблемы или ошибки в тексте. Аномалии также упоминаются как выбросы, необычности, шум, отклонения или исключения^[2].

Выявление аномалий в контексте обнаружения злоумышленного использования и вторжения в сеть, интересующие нас объекты часто не являются редкими, но проявляют неожиданную вспышку активности. Это не соответствует обычному статистическому определению выбросов как редких объектов и многие методы обнаружения выбросов (в частности, методы без учителя) терпят неудачу на таких данных, пока данные не будут сгруппированы подходящим образом. Зато алгоритмы кластерного анализа способны заметить микрокластеры, образованные таким поведением^[3].

Существует широкий набор категорий техник выявления аномалий^[4]. Техника выявления аномалий без учителя обнаруживает аномалии в непомеченных наборах тестовых данных при предположении, что большая часть набора данных нормальна, путём поиска представителей, которые меньше подходят к остальному набору данных. Техника выявления аномалий с учителем требует предоставления данных, помеченных как «нормальные» и «ненормальные», и использует обучение классификатора (ключевое отличие от многих других задач классификации заключается в неотъемлемой несбалансированной природе выявления выбросов). Техника выявления аномалий с частичным учителем строит модель, представляющую нормальное поведение из заданного набора нормального тренировочного набора, а затем проверяет правдоподобие полученной модели.

Выявление аномалий применимо к широкому кругу областей, таких как система обнаружения вторжений, обнаружение мошенничества, обнаружение неисправностей, мониторинга здоровья, обнаружение событий в сетях датчиков и обнаружение нарушений в экологической сфере. Часто выявление аномалий используется для предварительной обработки данных с целью удаления аномалий. При обучении с учителем удаление аномальных данных из набора часто приводит к существенному статистическому увеличению точности^[5][6].

В литературе было предложено несколько техник выявления аномалий^[7]. Вот некоторые популярные техники:

• Техники, основанные на плотности (k ближайших соседей^[8][9][10], локальный уровень выброса^[11], изолирующие леса^[12] и многие другие варианты этой концепции^[13]).
• Обнаружение выбросов на основе подпространств^[14] и на основе корреляции^[15] для данных высокой размерности^[16].
• Метод опорных векторов для одного класса^[17].
• Репликатор нейронных сетей^[18].
• Байесовские сети^[18].
• Скрытые марковские модели (СММ) ^[18].
• Выявление выбросов на основе кластерного анализа^[19][20].
• Отклонения от ассоциативных правил и часто встречающихся наборов.
• Выявление выбросов на основе нечёткой логики.
• Техника создания ансамблей, использующая бэггинг признаков^{[англ.][21][22]}, усреднение оценки^[23][24] и различение источников несхожести^[25][26].

Эффективность различных методов зависит от данных и параметров и имеют слабые систематические преимущества один перед другим, если сравнивать по многим наборам данных и параметров^[27][28].

Выявление аномалий предложила для систем обнаружения вторжений Дороти Деннинг в 1986 году^[29]. Выявление аномалий для систем обнаружения вторжений обычно выполняется с заданием порога и статистики, но может быть сделано с помощью мягких вычислений и индуктивного обучения^[30]. Типы статистики, предлагавшиеся в 1999 году, включали профили пользователей, рабочих станций, сетей, удалённых узлов, групп пользователей и программ, основанных на частотах, средних и дисперсиях^[31]. Эквивалентом выявления аномалий в обнаружении вторжений является обнаружение злонамеренного использования^[англ.].

• ELKI^[англ.] является комплектом инструментов с открытым кодом на языке Java для анализа данных, который содержит некоторые алгоритмы выявления аномалий, а также ускорители на основе индексов для них.

• 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 V. J., Austin J. A Survey of Outlier Detection Methodologies // Artificial Intelligence Review. — 2004. — Т. 22, вып. 2. — doi:10.1007/s10462-004-4304-y.
• Paul Dokas, Levent Ertoz, Vipin Kumar, Aleksandar Lazarevic, Jaideep Srivastava, Pang-Ning Tan. Data mining for network intrusion detection // Proceedings NSF Workshop on Next Generation Data Mining. — 2002.
• Chandola V., Banerjee A., Kumar V. Anomaly detection: A survey // ACM Computing Surveys. — 2009. — Т. 41, вып. 3. — doi:10.1145/1541880.1541882.
• Ivan Tomek. An Experiment with the Edited Nearest-Neighbor Rule // IEEE Transactions on Systems, Man, and Cybernetics. — 1976. — Т. 6, вып. 6. — doi:10.1109/TSMC.1976.4309523.
• Smith M. R., Martinez T. Improving classification accuracy by identifying and removing instances that should be misclassified // 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. There and back again: Outlier detection between statistical reasoning and data mining algorithms // Wiley Interdisciplinary Reviews: Data Mining and Knowledge Discovery. — 2018. — Т. 8, вып. 6. — ISSN 19424787. — doi:10.1002/widm.1280.
• Knorr E. M., Ng R. T., Tucakov V. Distance-based outliers: Algorithms and applications // The VLDB Journal the International Journal on Very Large Data Bases. — 2000. — Т. 8, вып. 3–4. — doi:10.1007/s007780050006.
• Ramaswamy S., Rastogi R., Shim K. Efficient algorithms for mining outliers from large data sets // 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. — Т. 2431. — (Lecture Notes in Computer Science). — ISBN 978-3-540-44037-6. — doi:10.1007/3-540-45681-3_2.
• Breunig M. M., Kriegel H.-P., Ng R. T., Sander J. LOF: Identifying Density-based Local 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.
• Fei Tony Liu, Kai Ming Ting, Zhi-Hua Zhou. Isolation Forest // 2008 Eighth IEEE International Conference on Data Mining. — 2008. — ISBN 9780769535029. — doi:10.1109/ICDM.2008.17.
• Schubert E., Zimek A., Kriegel H. -P. Local outlier detection reconsidered: A generalized view on locality with applications to spatial, video, and network outlier detection // Data Mining and Knowledge Discovery. — 2012. — Т. 28. — doi:10.1007/s10618-012-0300-z.
• Kriegel H. P., Kröger P., Schubert E., Zimek A. Outlier Detection in Axis-Parallel Subspaces of High Dimensional Data // Advances in Knowledge Discovery and Data Mining. — 2009. — Т. 5476. — (Lecture Notes in Computer Science). — ISBN 978-3-642-01306-5. — doi:10.1007/978-3-642-01307-2_86.
• Kriegel H. P., 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. A survey on unsupervised outlier detection in high-dimensional numerical data // Statistical Analysis and Data Mining. — 2012. — Т. 5, вып. 5. — doi:10.1002/sam.11161.
• Schölkopf B., Platt J. C., Shawe-Taylor J., Smola A. J., Williamson R. C. Estimating the Support of a High-Dimensional Distribution // Neural Computation. — 2001. — Т. 13, вып. 7. — doi:10.1162/089976601750264965. — PMID 11440593.
• Simon Hawkins, Hongxing He, Graham Williams, Rohan Baxter. Outlier Detection Using Replicator Neural Networks // Data Warehousing and Knowledge Discovery. — 2002. — Т. 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. Discovering cluster-based local outliers // Pattern Recognition Letters. — 2003. — Т. 24, вып. 9–10. — doi:10.1016/S0167-8655(03)00003-5.
• Campello R. J. G. B., Moulavi D., Zimek A., Sander J. Hierarchical Density Estimates for Data Clustering, Visualization, and Outlier Detection // ACM Transactions on Knowledge Discovery from Data. — 2015. — Т. 10, вып. 1. — doi:10.1145/2733381.
• Lazarevic A., Kumar V. Feature bagging for outlier detection // Proc. 11th ACM SIGKDD International Conference on Knowledge Discovery in Data Mining. — 2005. — ISBN 978-1-59593-135-1. — doi:10.1145/1081870.1081891.
• Nguyen H. V., Ang H. H., Gopalkrishnan V. Mining Outliers with Ensemble of Heterogeneous Detectors on Random Subspaces // Database Systems for Advanced Applications. — 2010. — Т. 5981. — (Lecture Notes in Computer Science). — ISBN 978-3-642-12025-1. — doi:10.1007/978-3-642-12026-8_29.
• 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 H. P. On Evaluation of Outlier Rankings and 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.
• Zimek A., Campello R. J. G. B., Sander J. R. Ensembles for unsupervised outlier detection // ACM SIGKDD Explorations Newsletter. — 2014. — Т. 15. — doi:10.1145/2594473.2594476.
• Zimek A., Campello R. J. G. B., Sander J. R. Data perturbation for outlier detection ensembles // 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 J. G. B. Campello, Barbora Micenková, Erich Schubert, Ira Assent, Michael E. Houle. On the evaluation of unsupervised outlier detection: measures, datasets, and an empirical study // Data Mining and Knowledge Discovery. — 2016. — Т. 30, вып. 4. — ISSN 1384-5810. — doi:10.1007/s10618-015-0444-8.
• Denning D. E. An Intrusion-Detection Model // IEEE Transactions on Software Engineering. — 1987. — Т. SE-13, вып. 2. — doi:10.1109/TSE.1987.232894.
• Teng H. S., Chen K., Lu S. C. Adaptive real-time anomaly detection using inductively generated sequential patterns // 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. Computer System Intrusion Detection: A Survey // Technical Report, Department of Computer Science,. — University of Virginia, Charlottesville, VA, 1999.

• Архив данных для сравнения алгоритмов выявления аномалий Мюнхенского университета; Зеркало в Университете Сан-Паулу.
• ODDS — ODDS: Большая коллекция публично доступных наборов данных для выявления выбросов с реальными ситуациями в различных областях.

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.