一种改进的基于反k近邻的流数据离群点检测算法

doi:10.3969/j.issn.1006-2475.2016.08.007

计算机与现代化

一种改进的基于反k近邻的流数据离群点检测算法

(西北工业大学理学院，陕西西安 710114)

收稿日期:2015-12-29 出版日期:2016-08-18 发布日期:2016-08-11
作者简介:呼妮(1990-)，女，陕西延安人，西北工业大学理学院硕士研究生，研究方向：离群点检测; 通信作者：王勇(1973-)，男，副教授，硕士生导师，博士，研究方向：运筹学，数据挖掘，人工智能。
基金资助:
西北工业大学基础研究基金资助项目(JC201273)

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

(School of Natural and Applied Sciences, Northwestern Polytechnical University, Xi’an 710114, China)

Received:2015-12-29 Online:2016-08-18 Published:2016-08-11

摘要/Abstract

摘要： 现有反k邻域的流数据离群点挖掘算法存在一些不足之处，即需要遍历每个数据对象，计算复杂度较高，稳定性较差。为了解决这些问题，本文提出一种改进的基于反k近邻的离群点检测算法OL-ORND。该算法采用细胞邻域思想，加入伪反k邻域点概念（反k邻域为空集的点对象），增加了算法的严密性，从而大大提高了算法的效率和准确率。实验表明，算法具有较好的性能。

关键词: 流数据, 反k近邻, 细胞邻域, 离群点

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

中图分类号:

TP391

呼妮，王勇. 一种改进的基于反k近邻的流数据离群点检测算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2016.08.007.

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.

参考文献

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

一种改进的基于反k近邻的流数据离群点检测算法

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

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 9

编辑推荐

Metrics

本文评价

[1]	段珣, 杨志勇, 江峰. 一种基于邻域粒度熵的离群点检测算法[J]. 计算机与现代化, 2022, 0(10): 19-23.
[2]	庄丽丽, 石鸿雁. 基于改进布谷鸟搜索的k-means算法的离群点检测[J]. 计算机与现代化, 2021, 0(10): 15-22.
[3]	袁焦, 王珣, 潘兆马, 杨学锋, 邹文露. 基于机器学习的列车设备故障预测模型研究[J]. 计算机与现代化, 2020, 0(12): 49-54.
[4]	侯博,聂颖. 动目标数据实时分析技术研究与实现[J]. 计算机与现代化, 2020, 0(01): 17-.
[5]	陈冲,蒋夏军. 一种支持通配符查询的XML模式匹配算法[J]. 计算机与现代化, 2016, 0(4): 65-73.
[6]	陆柳生，余明晖. 基于离群点检测的学生学习状态分析方法[J]. 计算机与现代化, 2016, 0(3): 35-40.
[7]	梅孝辉，龙渊，张健博. 基于聚类合并的局部离群点挖掘算法在入侵检测中的应用[J]. 计算机与现代化, 2015, 0(8): 67-70.
[8]	魏龙1，王勇2. 基于密度划分的离群点检测算法[J]. 计算机与现代化, 2015, 0(3): 26-32.
[9]	杨维永1，何军2，郑生军3，张旭东4. 一种适宜于子空间聚类的离群点检测算法[J]. 计算机与现代化, 2015, 0(12): 39-.