An Improved Stream Data Outlier Mining Algorithm Based on Reverse k Nearest Neighbors

doi:10.3969/j.issn.1006-2475.2016.08.007

Abstract

Abstract: The existing stream data outliers mining algorithms based on the reverse k neighbors need to traverse each data object, so the computational complexity is higher and the stability is lower. In order to solve these problems, this paper puts forward an improved outliers detection algorithm based on reverse k nearest neighbors named OL-ORND. Using the idea of cell neighbors, adding the false k reverse neighbors object concept that does not belong to the reverse k neighborhood. So that it can improve the efficiency and accuracy of the algorithm. Through the experiment, we can see that the algorithm has good performance.

Key words: stream data;reverse k nearest neighbors, cell neighbors, outliers

CLC Number:

TP391

HU Ni, WANG Yong. An Improved Stream Data Outlier Mining Algorithm Based on Reverse k Nearest Neighbors[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2016.08.007.

References

[1] Ng R T, Han Jiawei. Efficient and effective clustering methods for spatial data mining[C]// Proceedings of the 20th International Conference on Very Large Data Bases. 1994:144-155.

[2] He Zengyou, Xu Xiaofei, Huang Zhexue, et al. FP-outlier: Frequent pattern based outlier detection[J]. Computer Science and Information Systems, 2005,2(1):103-118.

[3] Zhang Tian, Ramakrishnan R, Livny M. BIRCH: An efficient data clustering method for very large databases[C]// Proceedings of the 1996 ACM SIGMOD International Conference on Management of Data. 1996:103-114.

[4] Han Jiawei, Kamber M. Data Mining: Concepts and Techniques[M]. 2nd Edition. San Francisco: Morgan Kaufmann, 2006.

[5] Marateb H R, Rojas-Martinez M, Mananas Villanueva M A, et al. Robust outlier detection in high-density surface electromyographic signals[C]// Proceedings of the 2010 Annual International Conference of the IEEE Engineering in Medicine and Biology. 2010:4850-4853.

[6] 杨福萍,王洪国,董树霞,等. 基于聚类划分的两阶段离群点检测算法[J]. 计算机应用研究, 2013,30(7):1942-1945.

[7] Guha S, Mishra N, Motwani R, et al. Clustering data streams[C]// Proceedings of the 41st Annual Symposium on Foundations of Computer Science. 2000:359-366.

[8] O'Callaghan L, Mishra N, Meyerson A, et al. Streaming-data algorithms for high-quality clustering[C]// Proceedings of the 18th IEEE International Conference on Data Engineering. 2002:685-694.

[9] 常建龙,曹锋,周傲英. 基于滑动窗口的进化数据流聚类[J]. 软件学报, 2007,18(4):905-918.

[10] 于彦伟,王沁,邝俊,等. 一种基于密度的空间数据流在线聚类算法[J]. 自动化学报, 2012,38(6):1051-1059.

[11] Zhou Aoying, Cao Feng, Yan Ying, et al. Distributed data stream clustering: A fast EM-based approach[C]// Proceedings of the 23rd IEEE International Conference on Data Engineering. 2007:736-745.

[12] 陈春燕,吕俊龙,郭有强. 基于时间衰减的分布式数据流聚类算法[J]. 太原师范学院学报(自然科学版), 2013,12(2):87-90.

[13] 鲁伟明,杜晨阳,魏宝刚,等. 基于MapReduce的分布式近邻传播聚类算法[J]. 计算机研究与发展, 2012,49(8):1762-1772.

[14] 张忠平,梁永欣. 基于反k近邻的流数据离群点挖掘算法[J]. 计算机工程, 2009,35(12):11-13.

[15] 倪巍伟,陆介平,陈耿,等. 基于k均值分区的数据流离群点检测算法[J]. 计算机研究与发展, 2006,43(9):1639-1643.

[16] 杨风召,朱扬勇,施伯乐. lncLOF:动态环境下局部异常的增量挖掘算法[J]. 计算机研究与发展, 2004,41(3):477-484.

[17] Pokrajac D, Lazarevic A, Latecki L J. Incremental local outlier detection for data streams[C]// Proceedings of the 2007 IEEE Symposium on Computational Intelligence and Data Mining. 2007:504-515.

[18] 揭财明,刘慧君,朱庆生. 基于方形对称邻域的局部离群点检测方法[J]. 计算机应用研究, 2012,29(2):472-474.