O-LDS: оптимизация пространства поиска для ускорения алгоритма оценки локальной плотности (Local Density Score)
Журнал: Труды Московского физико-технического института @trudy-mipt
Рубрика: Информатика, вычислительная техника и упровление
Статья в выпуске: 3 (31) т.8, 2016 года.
Бесплатный доступ
Обнаружение аномалий - это одна из самых важных задач технологии интеллектуального анализа данных (DataMining) и обнаружения знаний в базах данных. Эта задача решается во многих важных прикладных областях, таких как обнаружение атак (Intrusion Detection), обнаружения мошенничества (Fraud Detection), в том числе с кредитными картами, обнаружения аномалий в медицине (Medical Anomaly Detection), обнаружение злоупотреблений и др. В настоящее время проводится много исследований по решению этой задачи, но большинство полученных решений имеет высокую вычислительную сложность, что затрудняет использование таких решений в задачах с большим количеством данных [1]. В данной работе предложен новый алгоритм O-LDS, который имеет значительно меньшую вычислительную сложность по сравнению с известными - алгоритмом оценки локальной плотности (Local density score, LDS) [2] и алгоритмом фактора локального отклонения (Local Outlier Factor, LOF) [3]. Для оценки производительности алгоритма O-LDS использовался набор данных CHAMELEON [4], [5], содержащий данные сложной формы в двухмерном пространстве. Алгоритм O-LDS применяется для обнаружения аномалий в задаче обнаружения атак на информационные ресурсы с использованием реальных наборов данных ADFA [6]. Практические исследования показывают, что предложенный алгоритм не только реализует точное обнаружение аномалий, но и работает быстрее до 20 раз и более, чем алгоритмы LDS, LOF.
Похожие статьи в разделе Специальные определители для вычислительной техники
Короткий адрес: https://sciup.org/142186149
IDS: 142186149 | УДК: 004.021
Список литературы O-LDS: оптимизация пространства поиска для ускорения алгоритма оценки локальной плотности (Local Density Score)
- Chandola V., Banerjee A., Kumar V. Anomaly detection: A survey//ACM Comput. Surv. 2009. V. 41, N 3. P. 1-58
- Duy-Dinh Le, Shin’ichi Satoh. Unsupervised Face Annotation by Mining the Web//ICDM. 2008. P. 383-392
- Breunig M.M., Kriegel H.-P., Ng R.T., Sander J. LOF: identifying density-based local outliers//Proceedings of the ACM SIGMOD International Conference on Management of Data. 2000
- Ester M., Kriegel H.-P., Sander J., Xu X. A Density-Based Algorithm for Discovering Clusters in Large Spatial Databases with Noise//Proceedings of 2nd International Conference on Knowledge Discovery and Data Mining (KDD). 1996
- Karypis G., Han E.-H., Kumar V. Chameleon: Hierarchical Clustering Using Dynamic Modeling//IEEE Computer. 1999. V. 32, N 8. P. 68-75. (1999)
- Creech G., Hu J. A Semantic Approach to Host-Based Intrusion Detection Systems Using Contiguous and Discontiguous System Call Patterns//IEEE Transactions on Computers. 2014. V. 63. P. 807-819
- 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, 2014. V. 28, N 1. P. 190-237
- Ertoz L., Steinbach M., Kumar V. Finding Clusters of Different Sizes, Shapes, and Densities in Noisy, High Dimensional Data//SDM. 2003. P. 47-58
- Tang J., Chen Z., Fu A., Cheung D. Enhancing effectiveness of outlier detections for low density patterns//Adv. in KDDM. 2002. V. 2336. P. 535-548
- Kriegel H.-P., Kroger P., Schubert E., Zimek A. Loop: local outlier probabilities//Proc. of the 18th ACM CIKM. 2009. P. 1649-1652
- Jin W., Tung A., Han J., Wang W. Ranking outliers using symmetric neighborhood relationship//Advances in KDD. 2006. V. 3918. P. 577-593
- Papadimitriou S., Kitagawa H. LOCI: Fast outlier detection using the local correlation integral//Int. Conf. on Data Engineering. 2003. P 315-326
- Jain A.K. Data clustering: 50 years beyond K-means//Pattern Recognition Letters (PRL). 2010. V. 31, N 8. P. 651-666
- Thang V.V., Pantiukhin D.V., Galushkin A.I. A Hybrid Clustering Algorithm: The FastDBSCAN//Proc. IEEE International Conference on Engineering and Telecommunication (EnT). 2015
- Kim S., Cho N.W., Kang B., Kang S.-H. Fast outlier detection for very large log data//Expert Syst. Appl. 2011. V. 38, N 8. P. 9587-9596
- Caiming Zhong, Mikko I. Malinen, Duoqian Miao, Pasi Franti. A fast minimum spanning tree algorithm based on K-means//Inf. Sci. Journal. 2015. N 295. P. 1-17
- Gu G., Fogla P., Dagon D., Lee W., Skoric B. Measuring Intrusion Detection Capability: An Information-Theoretic Approach//ASIACCS’06. March 21-24, 2006. Taipei, Taiwan
- https://kdd.ics.uci.edu/databases/kddcup99/task.html
- http://www.ll.mit.edu/mission/communications/cyber/CSTcorpora/ideval/data/
- http://www.cs.unm.edu/immsec/systemcalls.htm
- Stavroulakis P., Stamp M. Handbook of information and communication security. Springer, 2010
- Creech G., Hu J. Generation of a new IDS test dataset: Time to retire the KDD collection//IEEE Wireless Communications and Networking Conference (WCNC). P. 4487-4492
- IBM. Writing SVC Routines. IBM System/360. Operating System Programmer’s Guide (PDF). Third Edition. P. 32-36. C28-6550-2
- Xie M., Hu J., Yu X., Chang E.Evaluating Host-Based Anomaly Detection Systems: Application of the Frequency-Based Algorithms to ADFA-LD//Network and System Security. Springer, 2014. P. 542-549
- Hinton G.E., Salakhutdinov R. Reducing the dimensionality of data with neural networks//Science. 2006. V. 313, N 5786. P. 504-507
- Hawkins S., He H., Williams G., Baxter R. Outlier detection using replicator neural networks//Proceedings of the 4th International Conference on Data Warehousing and Knowledge Discovery. Springer-Verlag, 2002. P. 170-180
- Goldstein M. FastLOF: An Expectation-Maximization based Local Outlier detection algorithm//Proceedings of the 21st International Conference on Pattern Recognition (ICPR), 2012
