[1]聂飞平,王成龙,王榕.基于二部图的快速聚类算法[J].深圳大学学报理工版,2019,36(1):18-23.[doi:10.3724/SP.J.1249.2019.01018]
　NIE Feiping,WANG Chenglong,and WANG Rong.Fast clustering with bipartite graph[J].Journal of Shenzhen University Science and Engineering,2019,36(1):18-23.[doi:10.3724/SP.J.1249.2019.01018]
点击复制

基于二部图的快速聚类算法()
分享到：

《深圳大学学报理工版》[ISSN:1000-2618/CN:44-1401/N]

卷:
第36卷
期数:
2019年第1期
页码:
18-23
栏目:
电子与信息科学
出版日期:
2019-01-20

文章信息/Info

Title:
Fast clustering with bipartite graph
作者:
聂飞平; 王成龙; 王榕
西北工业大学计算机学院，西北工业大学光学影像分析与学习中心，陕西西安 710072
Author(s):
NIE Feiping;  WANG Chenglong;  and WANG Rong
School of Computer Science and Center for Optical Imagery Analysis and Learning (OPTIMAL), Northwestern Polytechnical University, Xi’an 710072, P.R.China
关键词:
计算机应用技术; 聚类; 大数据; 谱图理论; 二部图; 秩约束
Keywords:
technology of computer application; clustering; large-scale; spectral graph theory; bipartite graph; rank constraint
分类号:
TP 181
DOI:
10.3724/SP.J.1249.2019.01018
摘要:
谱聚类算法是一种可有效学习数据流形分布和非凸状分布的聚类算法，但其过程涉及构建相似图、特征分解等高计算复杂度步骤，难以直接用于大规模聚类．本研究提出一种基于二部图的快速聚类算法（fast clustering with bipartite graph，FCBG），通过对数据采样降低原有数据结构规模，然后基于二部图学习采样数据和原有数据关系．通过对二部图对应的拉普拉斯矩阵施加秩约束，FCBG算法可在优化二部图的边的权重的同时，保持二部图的类簇结构，最终直接给出聚类结果，不依赖构图时每条边的初始权重分配．算法计算复杂度与数据大小呈线性关系．实验分析表明，FCBG算法可有效学习二部图的权重，并在较小的时间消耗下获得高质量的聚类结果．
Abstract:
Spectral clustering can effectively learn from data manifold distribution and non-convex distribution. However, the spectral clustering process which involves graph construction and eigen-decomposition has high computational complexity. It is difficult to apply spectral clustering for large-scale clustering directly. The fast clustering with bipartite graph (FCBG) algorithm reduces the size of the original data structure by sampling and learns the relationship between the selection data and the original data. The algorithm can optimize the weights of the edge of bipartite graph while maintaining the cluster structure of the bipartite graph. The computational complexity of the algorithm is linear with the data size. Experimental analysis shows that the algorithm can effectively learn the data relationship and obtain better clustering results under comparable time cost．

相似文献/References:

[1]刘宗香,谢维信,黄敬雄.分布式异类传感器网Hough变换航迹起始算法[J].深圳大学学报理工版,2007,24(2):111.
　LIU Zong-xiang,XIE Wei-xin,and HUANG Jin-xiong.Hough transform track initiation algorithm for distributed heterogeneous sensor network[J].Journal of Shenzhen University Science and Engineering,2007,24(1):111.
[2]明勇,张文斌,黄哲学,等.基于RFM购买树的客户分群[J].深圳大学学报理工版,2017,34(3):306.[doi:10.3724/SP.J.1249.2017.03306]
　Ming Yong,Zhang Wenbin,Huang Zhexue,et al.Customer segmentation based on RFM purchase tree[J].Journal of Shenzhen University Science and Engineering,2017,34(1):306.[doi:10.3724/SP.J.1249.2017.03306]
[3]何玉林,等.大规模数据集聚类算法的研究进展[J].深圳大学学报理工版,2019,36(1):4.[doi:10.3724/SP.J.1249.2019.01004]
　HE Yulin,and HUANG Zhexue,A review on clustering algorithms for large-scale data sets[J].Journal of Shenzhen University Science and Engineering,2019,36(1):4.[doi:10.3724/SP.J.1249.2019.01004]
[4]王馨月,景丽萍.基于分层抽样的不均衡数据集成分类[J].深圳大学学报理工版,2019,36(1):24.[doi:10.3724/SP.J.1249.2019.01024]
　WANG Xinyue and JING Liping.Stratified sampling based ensemble classification for imbalanced data[J].Journal of Shenzhen University Science and Engineering,2019,36(1):24.[doi:10.3724/SP.J.1249.2019.01024]
[5]韩迪,等.增量学习的优化算法在app使用预测中的应用[J].深圳大学学报理工版,2019,36(1):43.[doi:10.3724/SP.J.1249.2019.01043]
　HAN Di,LI Wenting,et al.The application of optimization algorithm based on incremental learning in app usage prediction[J].Journal of Shenzhen University Science and Engineering,2019,36(1):43.[doi:10.3724/SP.J.1249.2019.01043]
[6]王电钢,黄林,常健,等.基于ARIMA和CART的负载预测模型[J].深圳大学学报理工版,2019,36(3):245.[doi:10.3724/SP.J.1249.2019.03229]
　WANG Diangang,HUANG Lin,CHANG Jian,et al.Load forecasting model based on ARIMA and CART[J].Journal of Shenzhen University Science and Engineering,2019,36(1):245.[doi:10.3724/SP.J.1249.2019.03229]
[7]黄林,常健,杨帆,等.基于改进k-means的电力信息系统异常检测方法[J].深圳大学学报理工版,2020,37(2):214.[doi:10.3724/SP.J.1249.2020.02214]
　HUANG Lin,CHANG Jian,YANG Fan,et al.An anomaly detection method for electric power information system based on improved k-means[J].Journal of Shenzhen University Science and Engineering,2020,37(1):214.[doi:10.3724/SP.J.1249.2020.02214]

更新日期/Last Update: 2019-01-30