谱聚类广义模型与典型算法分析  

Analysis of General Model and Classical Algorithms for Spectral Clustering

作　　者：管涛[1] 杨婷[1] 

机构地区：[1]郑州航空工业管理学院计算机科学与应用系,郑州450015

出　　处：《模式识别与人工智能》2014年第11期1015-1025,共11页Pattern Recognition and Artificial Intelligence

基　　金：国家自然科学基金项目(No.41171341);教育部新世纪优秀人才支持计划项目(No.NCET-09-0126);河南省科技厅项目(No.122102210227;092300410140;102102210447)资助

摘　　要：谱聚类能发现数据的非线性低秩结构,在模式识别等领域应用广泛.谱聚类与图模型、流形嵌入、积分算子理论等紧密相关,存在着潜在的联系,但相关理论尚缺乏系统的研究.文中首先从谱聚类的研究现状出发,介绍它的一般性问题,即再生核空间中的积分算子特征函数学习问题.然后讨论谱聚类与核主成分、核k-means算法、Laplacian特征映射、流形学习、判别分析之间的内在联系.进而简要分析NJW算法、Ncut算法、基于Nystrm方法的谱聚类算法、多尺度谱聚类算法以及多层谱聚类算法.最后总结存在的问题和未来的发展趋势.Spectral clustering is able to find the nonlinear low-rank structure of data, and it is widely applied to pattern recognition. Besides, spectral clustering has some internal relations with graph models, manifold embedding and integral operator theory from the theoretical view. However, it is lack of systematically theoretical research in these aspects. The general model of spectral clustering is introduced from the latest research outcomes, that is, eigenfunctions learning of integral operators in reproducing kernel Hilbert space（RKHS）. Subsequently, the internal relations of spectral clustering with KPCA, kernel k-means, Laplacian eigenmap, manifold learning, and discriminant analysis are discussed. Then, some classical spectral clustering algorithms are introduced, such as NJW algorithm, Ncut, spectral clustering based on Nystrom method, muhiscale spectral clustering algorithm. At last, trends and possible difficulties in spectral clustering are summarized.

关 键 词：谱聚类 Laplacian特征映射 核函数 核主成分分析 积分算子 

分 类 号：TP311.13[自动化与计算机技术—计算机软件与理论]