基于近邻图改进的块对角子空间聚类算法

doi:10.11772/j.issn.1001-9081.2020061005

计算机应用 ›› 2021, Vol. 41 ›› Issue (1): 36-42.DOI: 10.11772/j.issn.1001-9081.2020061005

所属专题：第八届中国数据挖掘会议(CCDM 2020)

• 第八届中国数据挖掘会议(CCDM 2020) • 上一篇下一篇

基于近邻图改进的块对角子空间聚类算法

王丽娟¹, 陈少敏¹, 尹明², 许跃颖³, 郝志峰^1,4, 蔡瑞初¹, 温雯¹

1. 广东工业大学计算机学院, 广州 510006;
2. 广东工业大学自动化学院, 广州 510006;
3. 北京师范大学珠海分校信息技术学院, 广东珠海 519000;
4. 佛山科学技术学院数学与大数据学院, 广东佛山 528000

收稿日期:2020-05-31 修回日期:2020-09-02 出版日期:2021-01-10 发布日期:2021-01-16
通讯作者: 尹明
作者简介:王丽娟(1978-),女,河北邢台人,副教授,博士,主要研究方向:数据挖掘、机器学习;陈少敏(1994-),女,广东汕头人,硕士研究生,主要研究方向:数据挖掘、子空间聚类;尹明(1975-),男,湖南永州人,副教授,博士,主要研究方向:机器学习、模式识别、图像处理;许跃颖(1984-),男,广东汕头人,讲师,硕士,主要研究方向:互联网应用;郝志峰(1968-),男,江苏苏州人,教授,博士,主要研究方向:机器学习、人工智能;蔡瑞初(1983-),男,浙江温州人,教授,博士,主要研究方向:机器学习、数据挖掘;温雯(1981-),女,江西赣州人,副教授,博士,主要研究方向:支持向量机、模式识别。
基金资助:
国家自然科学基金资助项目（61502108，61876042，61876043）；NSFC-广东联合基金资助项目（U1501254）。

Improved block diagonal subspace clustering algorithm based on neighbor graph

WANG Lijuan¹, CHEN Shaomin¹, YIN Ming², XU Yueying³, HAO Zhifeng^1,4, CAI Ruichu¹, WEN Wen¹

1. School of Computers, Guangdong University of Technology, Guangzhou Guangdong 510006, China;
2. School of Automation, Guangdong University of Technology, Guangzhou Guangdong 510006, China;
3. School of Information Technology, Beijing Normal University, Zhuhai, Zhuhai Guangdong 519000, China;
4. School of Mathematics and Big Data, Foshan University, Foshan Guangdong 528000, China

Received:2020-05-31 Revised:2020-09-02 Online:2021-01-10 Published:2021-01-16
Supported by:
This work is partially supported by the National Natural Science Foundation of China (61502108, 61876042, 61876043), the NSFC-Guangdong Joint Found (U1501254).

摘要/Abstract

摘要： 块对角表示（BDR）模型可以通过利用线性表示对数据有效地进行聚类，却无法很好地利用高维数据常见的非线性流形结构信息。针对这一问题，提出了基于近邻图改进的块对角子空间聚类（BDRNG）算法来通过近邻图来线性拟合高维数据的局部几何结构，并通过块对角约束来生成具有全局信息的块对角结构。BDRNG同时学习全局信息以及局部数据结构，从而获得更好的聚类表现。由于模型包含近邻图算子和非凸的块对角表示范数，BDRNG 采用了交替最小化来优化求解算法。实验结果如下：在噪声数据集上，BDRNG能够生成稳定的块对角结构系数矩阵，这说明了BDRNG对于噪声数据具有鲁棒性；在标准数据集上，BDRNG的聚类表现均优于BDR，尤其在人脸数据集上，相较于BDR，BDRNG的聚类准确度提高了8%。

关键词: 近邻图, 块对角表示, 稀疏表示, 子空间聚类, 高维数据

Abstract: Block Diagonal Representation (BDR) model can efficiently cluster data by using linear representation, but it cannot make good use of non-linear manifold information commonly appeared in high-dimensional data. To solve this problem, the improved Block Diagonal Representation based on Neighbor Graph (BDRNG) clustering algorithm was proposed to perform the linear fitting of the local geometric structure by the neighbor graph and generate the block-diagonal structure by using the block-diagonal regularization. In BDRNG algorithm, both global information and local data structure were learned at the same time to achieve a better clustering performance. Due to the fact that the model contains the neighbor graph and non-convex block-diagonal representation norm, the alternative minimization was adopted by BDRNG to optimize the solving algorithm. Experimental results show that:on the noise dataset, BDRNG can generate the stable coefficient matrix with block-diagonal form, which proves that BDRNG is robust to the noise data; on the standard datasets, BDRNG has better clustering performance than BDR, especially on the facial dataset, BDRNG has the clustering accuracy 8% higher than BDR.

Key words: neighbor graph, Block Diagonal Representation (BDR), sparse representation, subspace clustering, high-dimensional data

中图分类号:

TP181

王丽娟, 陈少敏, 尹明, 许跃颖, 郝志峰, 蔡瑞初, 温雯. 基于近邻图改进的块对角子空间聚类算法[J]. 计算机应用, 2021, 41(1): 36-42.

WANG Lijuan, CHEN Shaomin, YIN Ming, XU Yueying, HAO Zhifeng, CAI Ruichu, WEN Wen. Improved block diagonal subspace clustering algorithm based on neighbor graph[J]. Journal of Computer Applications, 2021, 41(1): 36-42.

参考文献

[1] HONG W,WRIGHT J,HUANG K,et al. Multiscale hybrid linear models for lossy image representation[J]. IEEE Transactions on Image Processing,2006,15(12):3655-3671.
[2] D'HAESELEER P. How does gene expression clustering work?[J]. Nature Biotechnology,2005,23(12):1499-1501.
[3] COSTEIRA J P,KANADE T. A multibody factorization method for independently moving objects[J]. International Journal of Computer Vision,1998,29(3):159-179.
[4] 鲁全茂. 面向高维数据的聚类算法研究[D]. 北京:中国科学院大学,2018:1-4,57-75. (LU Q M. Research on clustering algorithms for high-dimensional data[D]. Beijing:University of Chinese Academy of Sciences,2018:1-4,57-75.)
[5] 王卫卫, 李小平, 冯象初, 等. 稀疏子空间聚类综述[J]. 自动化学报,2015,41(8):1373-1384.(WANG W W,LI X P,FENG X C, et al. A survey on sparse subspace clustering[J]. Acta Automatica Sinica,2015,41(8):1373-1384.)
[6] ELHAMIFAR E, VIDAL R. Sparse subspace clustering:algorithm,theory,and applications[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(11):2765-2781.
[7] LIU G,LIN Z,YU Y. Robust subspace segmentation by low-rank representation[C]//Proceedings of the 27th International Conference on Machine Learning. Madison, WI:Omnipress, 2010:663-670.
[8] FENG J,LIN Z,XU H,et al. Robust subspace segmentation with block-diagonal prior[C]//Proceedings of the 2014 IEEE Conference on Computer Vision and Pattern Recognition. Piscataway,IEEE 2014:3818-3825.
[9] LU C,MIN H,ZHAO Z,et al. Robust and efficient subspace segmentation via least squares regression[C]//Proceedings of the 2012 European Conference on Computer Vision, LNCS 7578. Berlin:Springer,2012:347-360.
[10] LU C,FENG J,LIN Z,et al. Subspace clustering by block diagonal representation[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence,2018,41(2):487-501.
[11] PATEL V M,VIDAL R. Kernel sparse subspace clustering[C]//Proceedings of the 2014 IEEE International Conference on Image Processing. Piscataway:IEEE,2014:2849-2853.
[12] XIAO S, TAN M, XU D, et al. Robust kernel low-rank representation[J]. IEEE Transactions on Neural Networks and Learning Systems,2016,27(11):2268-2281.
[13] JI P,REID I,GARG R,et al. Adaptive low-rank kernel subspace clustering[EB/OL].[2019-11-20]. https://arxiv.org/pdf/1707.04974.pdf.
[14] XIE X,GUO X,LIU G,et al. Implicit block diagonal low-rank representation[J]. IEEE Transactions on Image Processing, 2018,27(1):477-489.
[15] NG A Y,JORDAN M I,WEISS Y. On spectral clustering:analysis and an algorithm[C]//Proceedings of the 14th International Conference on Neural Information Processing Systems. Cambridge:MIT Press,2001:849-856.
[16] ROWEIS S T,SAUL L K. Nonlinear dimensionality reduction by locally linear embedding[J]. Science,2000,290(5500):2323-2326.
[17] 叶东升. 多流形嵌入子空间聚类方法研究[D]. 哈尔滨:哈尔滨工程大学,2019:6-10,12-17(YE D S. Research on multimanifold embedded subspace clustering method[D]. Harbin:Harbin Engineering University,2019:6-10,12-17.)
[18] YANG Y,HU Y,WU F. Sparse and low-rank subspace data clustering with manifold regularization learned by local linear embedding[J]. Applied Sciences,2018,8(11):No. 2175.
[19] MANNING C D,RAGHAVAN P,SCHÜTZE H. Introduction to Information Retrieval[M]. Cambridge:Cambridge University Press,2008:356-360
[20] YEUNG K Y,RUZZO W L. Details of the adjusted rand index and clustering algorithms,supplement to the paper an empirical study on principal component analysis for clustering gene expression data[J]. Bioinformatics,2001,17(9):763-774.
[21] SAMARIA F S,HARTER A C. Parameterisation of a stochastic model for human face identification[C]//Proceedings of 1994 IEEE Workshop on Applications of Computer Vision. Piscataway:IEEE,1994:138-142.
[22] NENE S A,NAYAR S K,MURASE H. Columbia Object Image Library(COIL-20)[R]. New York:Columbia University,1996.
[23] KRIZHEVSHY A. Learning multiple layers of features from tiny images[R]. Toronto:University of Toronto,2009.
[24] RUSSAKOVSKY O,DENG J,SU H,et al. ImageNet large scale visual recognition challenge[J]. International Journal of Computer Vision,2015,115(3):211-252.

基于近邻图改进的块对角子空间聚类算法

Improved block diagonal subspace clustering algorithm based on neighbor graph

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 15

编辑推荐

Metrics

[1]	陈恒恒, 倪志伟, 朱旭辉, 金媛媛, 陈千. 基于聚类分析的差分隐私高维数据发布方法[J]. 计算机应用, 2021, 41(9): 2578-2585.
[2]	裴春阳, 樊宽刚, 马政. 基于边缘保留分解和改进稀疏表示的医学图像融合[J]. 计算机应用, 2021, 41(7): 2092-2099.
[3]	王心, 朱浩华, 刘光灿. 卷积鲁棒主成分分析[J]. 计算机应用, 2021, 41(5): 1314-1318.
[4]	任晓奎, 刘鹏飞, 陶志勇, 刘影, 白立春. 基于单快拍信号到达角估计算法的室内入侵检测[J]. 计算机应用, 2021, 41(4): 1153-1159.
[5]	朱玉娜, 张玉涛, 闫少阁, 范钰丹, 陈韩托. 基于半监督子空间聚类的协议识别方法[J]. 计算机应用, 2021, 41(10): 2900-2904.
[6]	曾梦, 宁彬, 蔡之华, 谷琼. 使用深度对抗子空间聚类实现高光谱波段选择[J]. 计算机应用, 2020, 40(2): 381-385.
[7]	高彦彦, 李莉, 张晶, 贾英茜. 结合梯度投影稀疏重构和复数小波的图像重构[J]. 计算机应用, 2020, 40(2): 486-490.
[8]	宗春梅, 张月琴, 曹建芳, 赵青杉. 基于深度先验及非局部相似性的压缩感知核磁共振成像[J]. 计算机应用, 2020, 40(10): 3054-3059.
[9]	吴宗骏, 吴炜, 杨晓敏, 刘凯, Gwanggil Jeon, 袁皓. 改进的基于稀疏表示的全色锐化算法[J]. 计算机应用, 2019, 39(2): 540-545.
[10]	陶永鹏, 景雨, 顼聪. 基于分组字典与变分模型的图像去噪算法[J]. 计算机应用, 2019, 39(2): 551-555.
[11]	杜凯敏, 康宝生. 基于图像块分类的图像超分辨率重建[J]. 计算机应用, 2019, 39(2): 577-581.
[12]	周立军, 刘凯, 吕海燕. 基于竞争学习的稀疏受限玻尔兹曼机机制[J]. 计算机应用, 2018, 38(7): 1872-1876.
[13]	王丽芳, 董侠, 秦品乐, 高媛. 基于自适应联合字典学习的脑部多模态图像融合方法[J]. 计算机应用, 2018, 38(4): 1134-1140.
[14]	王鑫, 周韵, 宁晨, 石爱业. 自适应融合局部和全局稀疏表示的图像显著性检测[J]. 计算机应用, 2018, 38(3): 866-872.
[15]	邹佳彬, 孙伟. 基于提升静态小波变换与联合结构组稀疏表示的多聚焦图像融合[J]. 计算机应用, 2018, 38(3): 859-865.