一种适宜于子空间聚类的离群点检测算法

doi:10.3969/j.issn.1006-2475.2015.12.008

计算机与现代化

一种适宜于子空间聚类的离群点检测算法

1.南京南瑞集团公司,江苏南京210003；
2.南京信息工程大学电子与信息工程学院,江苏南京210044；
3.北京国电通网络技术有限公司，北京100070；
4.国网浙江省电力公司信息通信分公司，浙江杭州310007

收稿日期:2015-10-28 出版日期:2015-12-23 发布日期:2015-12-30
作者简介:杨维永(1978-)，男，江苏宿迁人，南京南瑞集团公司高级工程师，硕士，研究方向：信息安全及大数据分析；何军(1978-)，男，南京信息工程大学电子与信息工程学院副教授，研究方向：机器学习与大数据分析；郑生军(1977-)，男，北京国电通网络技术有限公司高级工程师，硕士，研究方向：电力信息系统安全；张旭东（1969-），男，国网浙江省电力公司信息通信分公司高级工程师，硕士，研究方向：网络、通信及公司运营监测。
基金资助:
国家自然科学基金资助项目（61203273）；国家电网公司科技项目（524681140009)

An Outlier Detection Algorithm for Subspace Clustering

1. NARI Group Corporation， Nanjing 210003, China；

2. School of Electronic and Information Engineering， Nanjing University of Information Science and Technology, 
Nanjing 210044, China； 3. Guodiantong Corporation, Beijing 100070, China；
4. State Grid Information & Telecommunication Branch of Zhejiang Province Electric Co., Hangzhou 310007, China

Received:2015-10-28 Online:2015-12-23 Published:2015-12-30

摘要/Abstract

摘要：

大数据处理面临数据信息缺失、信息杂乱、数据污染等诸多挑战，而离群点的检测与剔除是大数据分析中一个重要的预处理过程。本文针对数据分析中的子空间聚类问题，在数据受到离群点污染

的情况下，基于离群点稀疏性的先验知识，对经典的ksubspace子空间聚类算法融入1范数正则化，并采用随机梯度下降优化方法进行子空间聚类，以克服大数据处理计算量大和内存需求高的困难

。通过数值仿真，本文方法能够保证在数据受到严重离群点污染的条件下，可以精确检测并剔除离群异常数据，从而获得准确的子空间聚类结果。

关键词: 大数据处理, 离群点检测, 子空间聚类

Abstract:

There are several challenging difficulties in modern big data analytics, such as missing data, unstructured data, and outlier corruption, etc. The foremost important

preprocess is outlier detection and removal. In this paper, for tackling the popular subspace clustering problem in data analytics, we consider the more challenging scenario in

which the data set is corrupted by sparse outliers. Based on the sparsity assumption, the classic ksubspace algorithm is adapted to incorporate the 1 norm regularization

to alleviate outlier sideeffect. In order to overcome the huge requirements of computation and memory in big data, the modified ksubspace clustering algorithm exploits

stochastic gradient descent (SGD) for fast computation and memory efficiency. Simulation experiments show that even the data set is heavily corrupted by outliers the proposed

approach can guarantee to accurately detect and remove outliers, and furthermore achieves the accurate subspace clustering results.

Key words: big data analytics, outlier detection, subspace clustering

中图分类号:

TP312

杨维永1，何军2，郑生军3，张旭东4. 一种适宜于子空间聚类的离群点检测算法[J]. 计算机与现代化, doi: 10.3969/j.issn.1006-2475.2015.12.008.

YANG Weiyong1, HE Jun2, ZHENG Shengjun3，ZHANG Xudong4. An Outlier Detection Algorithm for Subspace Clustering[J]. Computer and Modernization, doi: 10.3969/j.issn.1006-2475.2015.12.008.

参考文献［16］

	［1］
	LaValle Steve, Eric Lesser, Rebecca Shockley, et al. Big data, analytics and the path from insights to value［J］. MIT Sloan Management Review (Winter 2011), 2011,52(2).
［2］	Gubbi Jayavardhana, Rajkumar Buyya, Slaven Marusic, et al. Internet of Things (IoT): A vision, architectural elements, and future directions［J］. Future Generation
	Computer Systems, 2013,29(7):1645-1660.
［3］	Manyika James, Michael Chui, Brad Brown, et al. Big data: The Next Frontier for Innovation, Competition, and Productivity［R］. McKinsey Global Institute, 2011.
［4］	Sagiroglu Seref, Duygu Sinanc. Big data: A review［C］// IEEE 2013 International Conference on Collaboration Technologies and Systems(CTS). 2013:42-47.
［5］	Wu Xindong, Zhu Xingquan, Wu Gongqing, et al. Data mining with big data［J］. IEEE Transactions on Knowledge and Data Engineering, 2014,26(1):97-107.
［6］	Emmanuel J Candès, Li Xiaodong, Ma Yi, et al. Robust principal component analysis?［J］. Journal of the ACM (JACM), 2011,58(3):11.
［7］	Victoria J Hodge, Jim Austin. A survey of outlier detection methodologies［J］. Artificial Intelligence Review, 2004,22(2):85-126.
［8］	Elhamifar Ehsan, Rene Vidal. Sparse subspace clustering: Algorithm, theory, and applications［J］. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013，35
(11)	:2765-2781.
［9］	Liu Guangcan, Lin Zhouchen, Yan Shuicheng, et al. Robust recovery of subspace structures by lowrank representation［J］. IEEE Transactions on Pattern Analysis and Machine
	Intelligence, 2013,35(1):171-184.
［10］	Chen Guangliang, Gilad Lerman. Spectral curvature clustering (SCC)［J］. International Journal of Computer Vision, 2009,81(3):317-330.
［11］	Ho Jason, Yang MingHsuan, Lim Jongwoo, et al. Clustering appearances of objects under varying illumination conditions［C］// Proceedings of 2003 IEEE Computer Society
	Conference on Computer Vision and Pattern Recognition. 2003:1-11.
［12］	Zhang Teng, Arthur Szlam, Yi Wang, et al. Hybrid linear modeling via local bestfit flats［J］. International Journal of Computer Vision, 2012,100(3):217-240.
［13］	Vidal René. A tutorial on subspace clustering［J］. IEEE Signal Processing Magazine, 2010,28(2):52-68.
［14］	Cevher Volkan, Steffen Becker, Martin Schmidt. Convex optimization for big data: Scalable, randomized, and parallel algorithms for big data analytics［J］. IEEE Signal
	Processing Magazine, 2014,31(5):32-43.
［15］	Zaharia Matei, Mosharaf Chowdhury, Michael J Franklin, et al. Spark: Cluster computing with working sets［C］// Proceedings of the 2nd USENIX Conference on Hot Topics
	in Cloud Computing. 2010:10-10.
［16］	Zaharia Matei, Tathagata Das, Li Haoyuan, et al. Discretized streams: Faulttolerant streaming computation at scale［C］// Proceedings of the 24th ACM Symposium on
	Operating Systems Principles. 2013:423-438.

[1]	周明升, 张雯. 一种面向多源数据的智慧园区管理平台[J]. 计算机与现代化, 2023, 0(05): 68-74.
[2]	段珣, 杨志勇, 江峰. 一种基于邻域粒度熵的离群点检测算法[J]. 计算机与现代化, 2022, 0(10): 19-23.
[3]	庄丽丽, 石鸿雁. 基于改进布谷鸟搜索的k-means算法的离群点检测[J]. 计算机与现代化, 2021, 0(10): 15-22.
[4]	陆柳生，余明晖. 基于离群点检测的学生学习状态分析方法[J]. 计算机与现代化, 2016, 0(3): 35-40.
[5]	魏龙1，王勇2. 基于密度划分的离群点检测算法[J]. 计算机与现代化, 2015, 0(3): 26-32.
[6]	刘晴和，杨云，贺兴亚，徐文春，周媛媛. 基于业务分割的并行式大数据迁移策略研究[J]. 计算机与现代化, 2014, 0(11): 86-89.

一种适宜于子空间聚类的离群点检测算法

An Outlier Detection Algorithm for Subspace Clustering

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献［16］

相关文章 6

编辑推荐

Metrics

本文评价

一种适宜于子空间聚类的离群点检测算法

An Outlier Detection Algorithm for Subspace Clustering

可视化

被引次数

摘要/Abstract

引用本文

使用本文

参考文献 ［16］

相关文章 6

编辑推荐

Metrics

本文评价

参考文献［16］