Outlier detection algorithm based on graph random walk

doi:10.11772/j.issn.1001-9081.2019101708

Journal of Computer Applications ›› 2020, Vol. 40 ›› Issue (5): 1322-1328.DOI: 10.11772/j.issn.1001-9081.2019101708

• Data science and technology • Previous Articles Next Articles

Outlier detection algorithm based on graph random walk

DU Xusheng¹, YU Jiong^1,2, YE Lele³, CHEN Jiaying²

1.School of Software, Xinjiang University, UrumqiXinjiang 830008, China
2.College of Information Science and Engineering, Xinjiang University, UrumqiXinjiang 830046, China
3.School of Software Engineering, Xi’an Jiaotong University, Xi’an Shannxi 710049, China

Received:2019-10-10 Revised:2019-12-12 Online:2020-05-10 Published:2020-05-15
Contact: YU Jiong, born in 1964, Ph. D., professor. His research interests include green computing, machine learning, data mining.
About author:DU Xusheng, born in 1995, M. S. candidate. His research interests include machine learning, data mining.YU Jiong, born in 1964, Ph. D., professor. His research interests include green computing, machine learning, data mining.YE Lele, born in 1993, M. S. candidate. His research interests include machine learning, data mining.CHEN Jiaying, born in 1988, Ph. D. candidate. Her research interests include recommendation system, data mining.
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61862060,61462079,61562086,61562078).

基于图上随机游走的离群点检测算法

杜旭升¹, 于炯^1,2, 叶乐乐³, 陈嘉颖²

1.新疆大学软件学院,乌鲁木齐 830008
2.新疆大学信息科学与工程学院,乌鲁木齐 830046
3.西安交通大学软件学院, 西安 710049

通讯作者: 于炯（1964—）
作者简介:杜旭升（1995—），男，甘肃庆阳人，硕士研究生，CCF会员，主要研究方向：机器学习、数据挖掘；于炯（1964—），男，北京人，教授，博士生导师，博士，主要研究方向：绿色计算、机器学习、数据挖掘；叶乐乐（1993—），男，湖北随州人，硕士研究生，主要研究方向：机器学习、数据挖掘；陈嘉颖(1988—)，女，新疆沙湾人，博士研究生，主要研究方向：推荐系统、数据挖掘。
基金资助:
国家自然科学基金资助项目（61862060,61462079,61562086,61562078）。

Abstract

Abstract:

Outlier detection algorithms are widely used in various fields such as network intrusion detection, and medical aided diagnosis. Local Distance-Based Outlier Factor (LDOF), Cohesiveness-Based Outlier Factor (CBOF) and Local Outlier Factor (LOF) algorithms are classic algorithms for outlier detection with long execution time and low detection rate on large-scale datasets and high dimensional datasets. Aiming at these problems, an outlier detection algorithm Based on Graph Random Walk (BGRW) was proposed. Firstly, the iterations, damping factor and outlier degree for every object in the dataset were initialized. Then, the transition probability of the rambler between objects was deduced based on the Euclidean distance between the objects. And the outlier degree of every object in the dataset was calculated by iteration. Finally, the objects with highest outlier degree were output as outliers. On UCI （University of California， Irvine） real datasets and synthetic datasets with complex distribution, comparison between BGRW and LDOF, CBOF, LOF algorithms about detection rate, execution time and false positive rate were carried out. The experimental results show that BGRW is able to decrease execution time and false positive rate, and has higher detection rate.

Key words: data mining, outlier detection, Markov chain, random walk, Local Distance-based Outlier Factor (LDOF), Cohesiveness-Based Outlier Factor (CBOF), Local Outlier Factor (LOF)

摘要：

离群点检测算法在网络入侵检测、医疗辅助诊断等领域具有十分广泛的应用。针对LDOF、CBOF及LOF算法在大规模数据集和高维数据集的检测过程中存在的执行时间长及检测率较低的问题，提出了基于图上随机游走(BGRW)的离群点检测算法。首先初始化迭代次数、阻尼因子以及数据集中每个对象的离群值；其次根据对象之间的欧氏距离推导出漫步者在各对象之间的转移概率；然后通过迭代计算得到数据集中每个对象的离群值；最后将数据集中离群值最高的对象判定为离群点并输出。在UCI真实数据集与复杂分布的合成数据集上进行实验，将BGRW算法与LDOF、CBOF和LOF算法在执行时间、检测率和误报率指标上进行对比。实验结果表明，BGRW算法能够有效降低执行时间并在检测率及误报率指标上优于对比算法。

关键词: 数据挖掘, 离群点检测, 马尔可夫链, 随机游走, LDOF, CBOF, LOF

CLC Number:

TP311.1

DU Xusheng, YU Jiong, YE Lele, CHEN Jiaying. Outlier detection algorithm based on graph random walk[J]. Journal of Computer Applications, 2020, 40(5): 1322-1328.

杜旭升, 于炯, 叶乐乐, 陈嘉颖. 基于图上随机游走的离群点检测算法[J]. 计算机应用, 2020, 40(5): 1322-1328.

References

1 HAWKINS D M . Identification of Outliers[M]. London: Chapman and Hall, 1980: 1-45.
2 PAULHEIM H , MEUSEL R . A decomposition of the outlier detection problem into a set of supervised learning problems[J]. Machine Learning, 2015, 100(2/3): 509-531.
3 TERZI D S , TERZI R , SAGIROGLU S . Big data analytics for network anomaly detection from netflow data[C]// Proceedings of the 2017 International Conference on Computer Science and Engineering. Piscataway: IEEE, 2017: 592-597.
4 LI W , MO W , ZHANG X , et al . Burn injury diagnostic imaging device’s accuracy improved by outlier detection and removal[C]// Proceedings of SPIE 9472, Algorithms and Technologies for Multispectral, Hyperspectral, and Ultraspectral Imagery XXI. Bellingham, WA: SPIE, 2015: No.947206.
5 WEST J , BHATTACHARYA M . Intelligent financial fraud detection: a comprehensive review[J]. Computers and Security, 2016, 57: 47-66.
6 GUO J , HUANG W , WILLIAMS B M . Real time traffic flow outlier detection using short-term traffic conditional variance prediction[J]. Transportation Research Part C: Emerging Technologies, 2015, 50: 160-172.
7 SILVA A P D , FILZMOSER P , BRITO P . Outlier detection in interval data[J]. Advances in Data Analysis and Classification, 2018, 12(3): 785-822.
8 PIEPEL G F . Robust regression and outlier detection[J]. Technometrics, 1989, 31(2):260-261.
9 KIRNER E , SCHUBERT E , ZIMEK A . Good and bad neighborhood approximations for outlier detection ensembles[C]// Proceedings of the 2017 International Conference on Similarity Search and Applications, LNCS 10609. Cham: Springer, 2017: 173-187.
10 HAN J , KAMBER M , PEI J . Mining frequent patterns, associations , and correlations: basic concepts and methods[M]// Data Mining: Concepts and Techniques. 3rd ed. San Francisco, CA: Morgan Kaufmann, 2012: 243-278.
11 AHMED M , MAHMOOD A N , HU J . A survey of network anomaly detection techniques[J]. Journal of Network and Computer Applications, 2016, 60: 19-31.
12 AMER M , GOLDSTEIN M , ABDENNADHER S . Enhancing one-class support vector machines for unsupervised anomaly detection[C]// Proceedings of the 2013 ACM SIGKDD Workshop on Outlier Detection and Description. New York: ACM, 2013: 8-15.
13 BREUNIG M M , KRIEGEL H P , NG R T, et al . LOF: identifying density-based local outliers[C]// Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2000: 93-104.
14 SCHREYER M , SATTAROV T , BORTH D , et al . Detection of anomalies in large scale accounting data using deep autoencoder networks[EB/OL].[2018-08-01].https://arxiv.org/pdf/1709.05254.pdf.
15 LIU F T , TING K , ZHOU Z . Isolation-based anomaly detection[J]. ACM Transactions on Knowledge Discovery from Data, 2012, 6(1):No.3.
16 ZHANG K , HUTTER M , JIN H . A new local distance-based outlier detection approach for scattered real-world data[C]// Proceedings of the 2009 Pacific-Asia Conference on Knowledge Discovery and Data Mining, LNCS 5476. Berlin: Springer, 2009: 813-822.
17 JOSHI V , BHATNAGAR R . CBOF: cohesiveness-based outlier factor A novel definition of outlier-ness[C]// Proceedings of the 2014 International Workshop on Machine Learning and Data Mining in Pattern Recognition, LNCS 8556. Cham: Springer, 2014: 175-189.
18 袁钟,冯山 . 基于邻域值差异度量的离群点检测算法[J]. 计算机应用, 2018, 38(7): 1905-1909. (YUAN Z, FENG S. Outlier detection algorithm based on neighborhood value difference metric[J]. Journal of Computer Applications, 2018, 38(7): 1905-1909.)
19 王习特,申德荣,白梅,等 . BOD:一种高效的分布式离群点检测算法[J]. 计算机学报, 2016, 39(1): 36-51. WANG X T , SHEN D R , BAI M , et al . BOD: an efficient algorithm for distributed outlier detection[J]. Chinese Journal of Computers, 2016, 39(1): 36-51.
20 SCHIFF G D , VOLK L A , VOLODARSKAYA M , et al . Screening for medication errors using an outlier detection system[J]. Journal of the American Medical Informatics Association, 2017, 24(2): 281-287.
21 HUANG A . A risk detection system of e-commerce: researches based on soft information extracted by affective computing Web texts[J]. Electronic Commerce Research, 2018, 18(1): 143-157.
22 ALAVERDYAN Z , JUNG J , BOUET R , et al . Regularized siamese neural network for unsupervised outlier detection on brain multiparametric magnetic resonance imaging: application to epilepsy lesion screening[J]. Medical Image Analysis, 2020, 60: No.101618.

[1]	MENG Fan, CHEN Guang, WANG Yong, GAO Yang, GAO Dequn, JIA Wenlong. Multi-granularity temporal structure representation based outlier detection method for prediction of oil reservoir [J]. Journal of Computer Applications, 2021, 41(8): 2453-2459.
[2]	TANG Andi, HAN Tong, XU Dengwu, XIE lei. Chaotic elite Harris hawks optimization algorithm [J]. Journal of Computer Applications, 2021, 41(8): 2265-2272.
[3]	LU Guoqing, SUN Hao. Two-dimensional mapping of swarm robot based on random walk [J]. Journal of Computer Applications, 2021, 41(7): 2121-2127.
[4]	YU Dunhui, ZHANG Luyi, ZHANG Xiaoxiao, MAO Liang. User recommendation method of cross-platform based on knowledge graph and restart random walk [J]. Journal of Computer Applications, 2021, 41(7): 1871-1877.
[5]	LIU Shize, QIN Yanjun, WANG Chenxing, SU Lin, KE Qixue, LUO Haiyong, SUN Yi, WANG Baohui. Traffic flow prediction algorithm based on deep residual long short-term memory network [J]. Journal of Computer Applications, 2021, 41(6): 1566-1572.
[6]	YIN Fei, LONG Lingli, KONG Zheng, SHAO Han, LI Xin, QIAN Zhuzhong. Deployment method of dockers in cluster for dynamic workload [J]. Journal of Computer Applications, 2021, 41(6): 1581-1588.
[7]	LI Xujuan, PI Jianyong, HUANG Feixiang, JIA Haipeng. Self-generated deep neural network based 4D trajectory prediction [J]. Journal of Computer Applications, 2021, 41(5): 1492-1499.
[8]	CHEN Kai, YU Yanwei, ZHAO Jindong, SONG Peng. Work location inference method with big data of urban traffic surveillance [J]. Journal of Computer Applications, 2021, 41(1): 177-184.
[9]	LYU Ruimin, MEI Lilin, XING Hongcha, MENG Lei, ZE Yuefeng. Sequentiality perception quantification method of painting and calligraphy based on Markov chain [J]. Journal of Computer Applications, 2021, 41(1): 295-299.
[10]	NING Jin, CHEN Leiting, LUO Zijuan, ZHOU Chuan, ZENG Huiru. Evaluation metrics of outlier detection algorithms [J]. Journal of Computer Applications, 2020, 40(9): 2622-2627.
[11]	LONG Yangyang, CHEN Yuling, XIN Yang, DOU Hui. Secure energy transaction scheme based on alliance blockchain [J]. Journal of Computer Applications, 2020, 40(6): 1668-1673.
[12]	SUN Jianjun, XU Yan. Estimation of underdetermined mixing matrix based on improved weighted fuzzy C-means clustering [J]. Journal of Computer Applications, 2020, 40(6): 1769-1773.
[13]	XU Zhoubo, YANG Jian, LIU Huadong, HUANG Wenwen. Protein complex identification algorithm based on XGboost and topological structural information [J]. Journal of Computer Applications, 2020, 40(5): 1510-1514.
[14]	CHEN Xi, MEI Guang, ZHANG Jinjin, XU Weisheng. Student grade prediction method based on knowledge graph and collaborative filtering [J]. Journal of Computer Applications, 2020, 40(2): 595-601.
[15]	MA Dong, CHEN Hongmei, WANG Lizhen, XIAO Qing. Dominant feature mining of spatial sub-prevalent co-location patterns [J]. Journal of Computer Applications, 2020, 40(2): 465-472.

Outlier detection algorithm based on graph random walk

基于图上随机游走的离群点检测算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics