基于属性关系矩阵的AP子空间聚类算法

J4 ›› 2016, Vol. 33 ›› Issue (6): 653-661.

基于属性关系矩阵的AP子空间聚类算法

朱红丁世飞

1.徐州医科大学医学信息学院，江苏徐州 221005； 2.中国矿业大学计算机科学与技术学院，江苏徐州 221116

收稿日期:2016-05-31 修回日期:2016-07-17 出版日期:2016-11-28 发布日期:2016-11-28
通讯作者: 朱红（1970-），女，江苏徐州人，副教授，博士，主要研究方向为数据挖掘、粒度计算。 E-mail:zhuhongwin@126.com

AP Subspace Clustering Algorithm Based on Attributes Relation Matrix

Zhu Hong, Ding Shifei

1.School of Medical Information, Xuzhou Medical University, Xuzhou 221005, China; 2.School of Computer Science and Technology, China University of Mining and Technology, Xuzhou 221116,China

Received:2016-05-31 Revised:2016-07-17 Published:2016-11-28 Online:2016-11-28

摘要/Abstract

摘要： Affinity Propagation（AP）聚类算法将所有数据点作为潜在的聚类中心，在相似度矩阵的基础上通过消息传递进行聚类, 但却不适用于子空间聚类。基于属性关系矩阵的AP子空间聚类算法（AP clustering algorithm based on attributes relation matrix, ARMAP）是一种异步软子空间聚类算法，首先通过计算属性a的邻域得到属性的关系矩阵，然后通过查找极大全1子矩阵得到数据集的兴趣度子空间，最后在各兴趣度子空间使用AP算法聚类，完成子空间聚类的任务。ARMAP算法将子空间的查找转换成查找矩阵的极大全1子矩阵，在正确查找子空间的同时，降低了时间复杂度。算法既保留了AP聚类算法的优点，又克服了AP算法不能进行子空间聚类的不足。

关键词: 聚类分析；子空间聚类；AP聚类；关系矩阵

Abstract: AP algorithm takes all data as potential clustering centers. But it is not appropriate for subspace clustering. AP subspace clustering algorithm based on attributes relation matrix(ARMAP) is asynchronous soft subspace clustering algorithm. This algorithm first calculates attribute relation matrix through neighborhood of attribute a. The candidate of all interesting subspaces is achieved by looking for the maximum sub-matrixes of attribute relation matrix which contain only 1. Finally, all subspace clusters can be gotten through AP clustering on interesting subspaces. The method obtains interesting subspaces correctly and reduces time and space complexity at the same time. It keeps the advantages of AP clustering and overcome the shortage of it.

Key words: clustering analysis; subspace clustering; AP clustering; relation matrix

中图分类号:

TP181

朱红丁世飞. 基于属性关系矩阵的AP子空间聚类算法[J]. J4, 2016, 33(6): 653-661.

Zhu Hong, Ding Shifei. AP Subspace Clustering Algorithm Based on Attributes Relation Matrix [J]. J4, 2016, 33(6): 653-661.

参考文献

[1] Agrawal R, Gehrke J, Gunopulos D, Raghavan P. Automatic subspace clustering of high dimensionating data for data mining applications[C]. Proceedings of the 1998 ACM SIGMOD international conference on Management of data. ACM Press, 1998: 94-105.
[2] Hu Zhengping, Li Jing. Face recognition of joint sparse representation based on low-rank subspace recovery [J].Acta Electronica Sinica, 2013, 5 (05):987-991. (in Chinese)
[3] Wang Jun, Wang Shitong, Dengzhao. A novel textclustering algorithm based on feature weighting distance and soft subspace learning[J]. Chinese Journal Of Computrs, 2012, 8(08): 1655-1665. (in Chinese)
[4] Li tao, Wang Weiwei, Zhai Dong, Jia Xixi. Weighted-sparse subspace clustering method for image segmentation[J]. Systems Engineering and Electronics, 2014, 36(3): 580-585(in Chinese)
[5] DENG Zhaohong,CHOI K S,CHUNG F L. Enhanced soft subspace clustering integrating withincluster and between-cluster information[J].Pattern Recognition,2012,3(03):767-781.
[6] Frey J, Dueck D. Clustering by passing messages between data points[J]. Science, 2007, 315(5814): 972-976.
[7] Jia S, Qian Y t, and Ji Z. Band selection for hyperspectral imagery using affinity Propagation[C]. Proceedings of the 2008 Digital Image Computing:Techniques and Applications, Canberra, ACT: IEEE, 2008:137-141.
[8] Li G , Guo L, and Liu T M, et al. Grouping of brain MR images via affinity propagation[C]. IEEE International Symposium on Circuits and Systems, 2009(ISCAS 2009), Taipei: IEEE, 2009: 2425-2428.
[9] Dueck D, Frey B J, and Jojic N, et al. Constructing treatment portfolios using affinity propagation[C]. Proceedings of 12th Annual International Conference, RECOMB 2008, Berlin: Springer, 2008: 360-371.
[10] Shi Lin, Wang Defeng, Liu Wen. Automatic detection of arterial input function in dynamic contrast enhanced MRI based on affinity propagationclustering: Detection of AIF in DCE-MRI Using AP Clustering[J]. Journal of Magnetic Resonance Imaging, 2015,39(5):27-37
[11] Lu Cheng, Song Shiji, Wu Cheng. Nearest neighbor intervals based AP clustering algorithm for large incomplete data[J]. Mathematical Problems in Engineering, 2015, 2015(1):1-9.
[12] Li Qiang, Shen Dong, Wang Fei. MQAM modulation recognition based on AP clustering method. MATEC Web of Conferences, 2016, 44(1):01002-p1-p5.
[13] Agrawal R, Gehrke J, Gunopulos D,et al. Automatic subspace clustering of high Dimensional data[J]. Data Mining and Knowledge Discovery, 2005,11(11): 5-33.