引入局部向量点积密度的数据流离群点快速检测算法

doi:10.19678/j.issn.1000-3428.0056453

计算机工程 ›› 2020, Vol. 46 ›› Issue (11): 132-138,147. doi: 10.19678/j.issn.1000-3428.0056453

引入局部向量点积密度的数据流离群点快速检测算法

毛亚琼¹, 田立勤^1,2, 王艳¹, 毛亚萍³, 王志刚¹

1. 青海师范大学计算机学院, 西宁 810008;
2. 华北科技学院计算机学院, 北京 065201;
3. 青海省基础测绘院, 西宁 810000

收稿日期:2019-10-30 修回日期:2020-01-04 发布日期:2020-02-10
作者简介:毛亚琼(1991-),女,硕士研究生,主研方向为数据挖掘;田立勤(通信作者),教授、博士生导师;王艳,博士;毛亚萍,硕士;王志刚,博士。
基金资助:
国家重点研发计划（2017YFC0804108，2018YFC0808306）；中央高校基本科研业务费专项资金（3142019043）；河北省重点研发计划（19270318D）；青海省物联网重点实验室资助项目（2017-ZJ-Y21）；青海省应用基础研究项目（2017-ZJ-752）；河北省物联网监控工程技术研究中心项目（3142016020）。

Fast Outlier Detection Algorithm in Data Stream with Local Density of Vector Dot Product

MAO Yaqiong¹, TIAN Liqin^1,2, WANG Yan¹, MAO Yaping³, WANG Zhigang¹

1. School of Computer, Qinghai Normal University, Xining 810008, China;
2. School of Computer, North China Institute of Science and Technology, Beijing 065201, China;
3. Qinghai Basic Surveying and Mapping Institute, Xining 810000, China

Received:2019-10-30 Revised:2020-01-04 Published:2020-02-10

摘要/Abstract

摘要： 现有数据流离群点检测算法在面对海量高维数据流时普遍存在运算时间过长的问题。为此，提出一种引入局部向量点积密度的高维数据流离群点快速检测算法。以保存少量中间结果的方式只对窗口内受影响的数据点进行增量计算，同时设计2种优化策略和1条剪枝规则，减少检测过程中各点之间距离的计算次数，降低算法的时空开销，从而提高检测效率。理论分析和实验结果表明，该算法可以在保证检测准确性的情况下有效提高数据流的离群点检测效率，并且可扩展至并行环境进行并行加速。

关键词: 离群点检测, 高维数据流, 局部向量点积密度, 增量计算, 剪枝规则

Abstract: Existing outlier detection algorithms are generally time-consuming to deal with massive high-dimensional data streams.To address the problem,this paper proposes a Fast outlier detection algorithm in data stream with Local Density of Vector dot Product(FASTLDVP).It carries out incremental calculation only for the affected data points in the window,and keeps a small amount of intermediate results.Meanwhile,two optimization strategies and one pruning rule are designed to reduce the number of distance calculation times and the space-time overhead of the algorithm,so as to improve the detection efficiency.Theoretical analysis and experimental results show that this algorithm can effectively improve the detection efficiency of outliers in data stream while ensuring the detection accuracy,and can be extended to parallel environments for parallel acceleration.

Key words: outlier detection, high-dimensional data stream, Local Density of Vector dot Product(LDVP), incremental calculation, pruning rule

中图分类号:

TP391

毛亚琼, 田立勤, 王艳, 毛亚萍, 王志刚. 引入局部向量点积密度的数据流离群点快速检测算法[J]. 计算机工程, 2020, 46(11): 132-138,147.

MAO Yaqiong, TIAN Liqin, WANG Yan, MAO Yaping, WANG Zhigang. Fast Outlier Detection Algorithm in Data Stream with Local Density of Vector Dot Product[J]. Computer Engineering, 2020, 46(11): 132-138,147.

http://www.ecice06.com/CN/Y2020/V46/I11/132

图/表 5

20201124085442

20201124085445

20201124085448

20201124085451

20201124085454

参考文献

[1] MANDHARE H C,IDATE S R.A comparative study of cluster based outlier detection,distance based outlier detection and density based outlier detection techniques[C]//Proceedings of 2017 International Conference on Intelligent Computing and Control Systems.Washington D.C.,USA:IEEE Press,2017:931-935.
[2] GENG Juncheng,ZHANG Xiaofei,ZHOU Qingjie,et al.A low voltage electricity theft identification method based on improved LOF[J].Advances of Power System & Hydroelectric Engineering,2019,35(11):30-36.(in Chinese) 耿俊成,张小斐,周庆捷,等.基于局部离群点检测的低压台区用户窃电识别[J].电网与清洁能源,2019,35(11):30-36.
[3] MAO Jiali,JIN Cheqing,ZHANG Zhigang,et al.Anomaly detection for trajectory big data:advancements and framework[J].Journal of Software,2017,28(1):17-34.(in Chinese). 毛嘉莉,金澈清,章志刚,等.轨迹大数据异常检测:研究进展及系统框架[J].软件学报,2017,28(1):17-34.
[4] FU Peiguo,HU Xiaohui.Anomaly detection algorithm based on the local distance of density-based sampling data[J].Journal of Software,2017,28(10):2625-2639.(in Chinese). 付培国,胡晓惠.基于密度偏倚抽样的局部距离异常检测方法[J].软件学报,2017,28(10):2625-2639.
[5] STONE-GROSS B,COVA M,CAVALLARO L,et al.Your botnet is my botnet:analysis of a botnet takeover[C]//Proceedings of 2009 ACM Conference on Computer and Communications Security.New York,USA:ACM Press,2009:635-647.
[6] KRIEGEL H P,SCHUBERT M,ZIMEK A.Angle-based outlier detection in high-dimensional data[C]//Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2008:444-452.
[7] SHOU Zhaoyu,ZOU Fengbo,TIAN Hao,et al.Outlier detection based on local density of vector dot product in data stream[C]//Proceedings of International Conference on Security with Intelligent Computing and Big-data Services.Berlin,Germany:Springer,2018:1-5.
[8] STALMANS E,IRWIN B.A framework for DNS based detection and mitigation of malware infections on a network[C]//Proceedings of IEEE Information Security South Africa Conference.Washington D.C.,USA:IEEE Press,2011:1-5.
[9] YU Liping,LI Yunfei,ZHU Shixing.Anomaly detection algorithm based on high-dimensional data stream[J].Computer Engineering,2018,44(1):51-55.(in Chinese) 余立苹,李云飞,朱世行.基于高维数据流的异常检测算法[J].计算机工程,2018,44(1):51-55.
[10] NI Weiwei,LU Jieping,CHEN Geng,et al.An efficient data stream outliers detection algorithm based on k-means partitioning[J].Journal of Computer Research and Development,2006,43(9):1639-1643.(in Chinese) 倪巍伟,陆介平,陈耿,等.基于k均值分区的数据流离群点检测算法[J].计算机研究与发展,2006,43(9):1639-1643.
[11] CAO Lei,YANG Di,WANG Qingyang,et al.Scalable distance-based outlier detection over high-volume data streams[C]//Proceedings of the 30th IEEE International Conference on Data Engineering.Washington D.C.,USA:IEEE Press,2014:76-87.
[12] POKRAJAC D,LAZAREVIC A,LATECKI L J.Incremental local outlier detection for data streams[C]//Proceedings of 2007 IEEE Symposium on Computational Intelligence and Data Mining.Washington D.C.,USA:IEEE Press,2007:1-10.
[13] YE H,KITAGAWA H,XIAO J.Continuous angle-based outlier detection on high-dimensional data streams[C]//Proceedings of the 19th International Database Engineering and Applications Symposium.New York,USA:ACM Press,2015:647-652.
[14] BREUNIG M M,KRIEGEL H P,NG R T,et al.LOF:identifying density-based local outliers[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York,USA:ACM Press,2000:1-5.
[15] GAO K,SHAO F J,SUN R C.n-INCLOF:a dynamic local outlier detection algorithm for data streams[C]//Proceedings of International Conference on Signal Processing Systems.Washington D.C.,USA:IEEE Press,2010:179-183.
[16] THAKRAN Y,TOSHNIWAL D.Unsupervised outlier detection in streaming data using weighted clustering[C]//Proceedings of International Conference on Intelligent Systems Design and Applications.Washington D.C.,USA:IEEE Press,2012:947-952.
[17] KRIEGEL H P,KRÖGER P,ZIMEK A.Outlier detection techniques[C]//Proceedings of ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York,USA:ACM Press,2010:1-5.
[18] PHAM N,PAGH R.A near-linear time approximation algorithm for angle-based outliner detection in high dimensional data[C]//Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.New York:ACM Press,2012:877-885.
[19] ZHANG Ji,GAO Qigang,WANG Hai.Outlier detection for high-dimensional data streams[C]//Proceedings of ACM SIGMOD International Conference on Management of Data.New York:ACM Press,2015:37-46.
[20] HAN J W,MICHELINE K.Data mining:concepts and techniques[M].2nd edition.[S.l.]:Elsevier,2006.

选择文件类型/文献管理软件名称

选择包含的内容

引入局部向量点积密度的数据流离群点快速检测算法

Fast Outlier Detection Algorithm in Data Stream with Local Density of Vector Dot Product

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	余立苹,李云飞,朱世行. 基于高维数据流的异常检测算法[J]. 计算机工程, 2018, 44(1): 51-55.
[2]	董雷刚,刘国华. 组合Skyline的求解与更新算法[J]. 计算机工程, 2017, 43(6): 195-201,206.
[3]	俞庆英,罗永龙,陈付龙,郑孝遥. 一种保护私有信息的空间离群点检测方法[J]. 计算机工程, 2017, 43(3): 163-171.
[4]	刘耀宗, 张宏, 孟锦, 韩法旺. 基于小波密度估计的数据流离群点检测[J]. 计算机工程, 2013, 39(2): 178-181.
[5]	岳立廷, 于明, 于洋, 阎刚, 薛翠红. 一种基于面片的三维重建算法[J]. 计算机工程, 2012, 38(14): 199-202.
[6]	孙金花, 胡健, 李向阳. 基于分形理论的离群点检测[J]. 计算机工程, 2011, 37(3): 33-35.
[7]	胡云, 潘祝山, 施珺. 基于近邻关系的离群约简搜索算法[J]. 计算机工程, 2011, 37(21): 38-39,42.
[8]	肖艳芹;李俊;黄炜. What-if分析中的Max数据方体增量计算[J]. 计算机工程, 2010, 36(9): 29-31.
[9]	刘学军;胡平;徐宏炳;董逸生. 基于滑动窗口的在线数据流增量聚集查询[J]. 计算机工程, 2007, 33(21): 45-46,4.

模态框（Modal）标题

选择文件类型/文献管理软件名称

选择包含的内容

引入局部向量点积密度的数据流离群点快速检测算法

Fast Outlier Detection Algorithm in Data Stream with Local Density of Vector Dot Product

RichHTML

PDF

可视化

被引次数

摘要/Abstract

引用本文

使用本文

图/表 5

参考文献

相关文章 9

编辑推荐

Metrics

本文评价