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

doi:10.11772/j.issn.1001-9081.2019101708

计算机应用 ›› 2020, Vol. 40 ›› Issue (5): 1322-1328.DOI: 10.11772/j.issn.1001-9081.2019101708

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

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

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

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

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).

摘要/Abstract

摘要：

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

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

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)

中图分类号:

TP311.1

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

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.

参考文献

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]	汤安迪, 韩统, 徐登武, 谢磊. 混沌精英哈里斯鹰优化算法[J]. 计算机应用, 2021, 41(8): 2265-2272.
[2]	余敦辉, 张蕗怡, 张笑笑, 毛亮. 基于知识图谱和重启随机游走的跨平台用户推荐方法[J]. 计算机应用, 2021, 41(7): 1871-1877.
[3]	刘世泽, 秦艳君, 王晨星, 苏琳, 柯其学, 罗海勇, 孙艺, 王宝会. 基于深度残差长短记忆网络交通流量预测算法[J]. 计算机应用, 2021, 41(6): 1566-1572.
[4]	尹飞, 龙玲莉, 孔峥, 邵涵, 李鑫, 钱柱中. 面向动态负载的集群容器部署方法[J]. 计算机应用, 2021, 41(6): 1581-1588.
[5]	李旭娟, 皮建勇, 黄飞翔, 贾海朋. 基于自生成深度神经网络的4D航迹预测[J]. 计算机应用, 2021, 41(5): 1492-1499.
[6]	陈凯, 于彦伟, 赵金东, 宋鹏. 基于城市交通监控大数据的工作位置推理方法[J]. 计算机应用, 2021, 41(1): 177-184.
[7]	律睿慜, 梅莉琳, 邢红姹, 孟磊, 昃跃峰. 基于马尔可夫链的书画时序感量化方法[J]. 计算机应用, 2021, 41(1): 295-299.
[8]	宁进, 陈雷霆, 罗子娟, 周川, 曾慧茹. 离群点检测算法的评价指标[J]. 计算机应用, 2020, 40(9): 2622-2627.
[9]	龙洋洋, 陈玉玲, 辛阳, 豆慧. 基于联盟区块链的安全能源交易方案[J]. 计算机应用, 2020, 40(6): 1668-1673.
[10]	孙建军, 徐岩. 基于加权改进模糊C均值聚类的欠定混合矩阵估计[J]. 计算机应用, 2020, 40(6): 1769-1773.
[11]	徐周波, 杨健, 刘华东, 黄文文. 基于XGBoost与拓扑结构信息的蛋白质复合物识别算法[J]. 计算机应用, 2020, 40(5): 1510-1514.
[12]	马董, 陈红梅, 王丽珍, 肖清. 空间亚频繁co-location模式的主导特征挖掘[J]. 计算机应用, 2020, 40(2): 465-472.
[13]	陈曦, 梅广, 张金金, 许维胜. 融合知识图谱和协同过滤的学生成绩预测方法[J]. 计算机应用, 2020, 40(2): 595-601.
[14]	郭景峰, 董慧, 张庭玮, 陈晓. 主题关注网络的表示学习[J]. 计算机应用, 2020, 40(2): 441-447.
[15]	郑文萍, 岳香豆, 杨贵. 基于随机游走的改进标签传播算法[J]. 计算机应用, 2020, 40(12): 3423-3429.

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

Outlier detection algorithm based on graph random walk

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics