大规模数据集下谱聚类算法的求解  

Computation of Spectral Clustering Algorithm for Large-scale Data Set

作　　者：史卫亚[1,2] 郭跃飞[3] 

机构地区：[1]粮食信息处理与控制教育部重点实验室,郑州450001 [2]河南工业大学信息科学与工程学院,郑州450001 [3]复旦大学计算机科学与技术系,上海200433

出　　处：《计算机科学》2012年第B06期312-314,330,共4页Computer Science

基　　金：国家自然基金项目(60875003);河南省教育厅自然科学研究计划项目(2010B520005);河南工业大学博士基金项目(2009BS013);河南省科技厅重点科技攻关项目(112102210190);郑州市科技发展计划项目(2010SFXM470)资助

摘　　要：谱聚类算法是一种流行的数据聚类方法,该算法使用特征分解技术计算邻接矩阵的特征解,但是在大规模数据集的情况下,因储存和计算的问题而无法进行求解。基于线性代数中对称矩阵的性质,提出使用邻接矩阵的每一列作为迭代算法的输入样本,通过迭代计算出邻接矩阵的特征解。所提算法的空间复杂度只有Ο(m),时间复杂度也降低为Ο(pkm)。实验结果验证了算法的有效性。Spectral clustering algorithm is a popular data clustering method.It uses eigen-decomposition technique to extract the eigenvectors of the affinity matrix.But the method is infeasible for large-scale data set because of the store and computational problem.Motivated by the property of symmetric matrix,in this paper each column of the affinity matrix was used as the input sample for the iterative algorithm.The eigenvectors of the affinity matrix could be iteratively computed.The space complexity of proposed method was only Ο（m）,the time complexity was reduced to Ο（pkm）.The effectiveness of proposed method was validated from experimental results.

关 键 词：谱方法 邻接矩阵 大数据集 特征分解 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]