抽样改进加权核大数据谱聚类算法  

Large Scal Spectral Clustering Based on Sampling Improved Weighted Kernel

作　　者：申锐[1] 吴睿 SHEN Rui;WU Rui(Shanxi Traffical and Technical College,Shanxi Jinzhong030600,China;Xi’an Jiaotong University,Shaanxi Xi’an710061,China)

机构地区：[1]山西交通职业技术学院,山西晋中030600 [2]西安交通大学软件学院,陕西西安710061

出　　处：《机械设计与制造》2021年第1期171-174,共4页Machinery Design & Manufacture

基　　金：国家自然科学基金(No.61271444)。

摘　　要：经典谱聚类算法将数据聚类转为图划分问题,在分析其Normalized Cut函数与传统加权核k-means等价基础上,设计了一种基于抽样改进加权核k-means算法的大规模数据集谱聚类算法,算法通过加权核k-means迭代优化避免Laplacian矩阵特征分解的大量资源占用,通过随机映射得到近似奇异值分解,并由近似奇异向量确定各点数据权重及抽样概率,以此得到快速合理抽样,通过数据抽样并将聚类中心约束到抽样点生成的子空间中,避免全部核矩阵的使用,从而降低经典算法的时间空间复杂度。实验结果表明,改进算法在保持与经典算法相近精度基础上,大幅提高了聚类效率,实验验证了改进算法的有效性。Classical spectral clustering algorithm transforms data clustering into graph partitioning problems,so based on analyzing the equivalence between its Normalized Cut objective function and the weighted nuclear k-means function,a largescale data spectrum based on sampling improved weighted nuclear k-means algorithm is designed,in which,the weighted kernel k-means iterative optimization is used to avoid the large resource consumption of Laplacian matrix feature decomposition,and the use of all nuclear matrices is avoided by through the data sampling and constrain the clustering center to the subspace generated by the sampling point,thereby reducing the time-space complexity of classical algorithms.Theoretical analysis and experimental results show that,the improved algorithm can greatly improve the clustering efficiency on the basis of maintaining similar clustering accuracy with the classic algorithm.

关 键 词：大数据谱聚类 加权核k-means算法 数据抽样 矩阵特征分解 核矩阵 

分 类 号：TH16[机械工程—机械制造及自动化] TP181[自动化与计算机技术—控制理论与控制工程]