福州大学本科生毕业设计（论文）开题报告
学生姓名 专业 杨清 数学与应用数学 学 号 班 级 浅谈谱聚类算法及应用 职 称 031301316 论文（设计）题目 指导老师姓名 一、论文（设计）选题的依据（选题的目的和意义、该选题国内外的研究现状及发展趋势、主要参考文献等） （一）选题的目的与意义 选题目的： 在这个大数据时代，数据分析是一个很重要的问题，聚类技术的发展，大大缓解了这种情况。在模式识别领域，谱聚类的出现成为了学者研究的焦点。由于谱聚类算法复杂程度低，实现比较容易等特点，在各个领域受到了许多专家的肯定，成为一个重要的研究对象。经过国内外专家学者不断研究和探索，谱聚类算法得到了很大的发展，但是也存在一些问题，随着研究的深入，出现各种各样的谱聚类算法，但是这些算法的实现方法都是十分相似的。 研究意义： 谱聚类算法大致上可以分为以PF算法为代表的二路谱聚类算法和以NJW算法为代表的多路谱聚类算法两种类型。二路谱聚类算法使用的主要是图的二路划分准则，多路谱聚类算法使用的主要是图的多路划分准则。 应用比较广泛的谱聚类算法主要包括二路谱聚类算法中的PF算法，SM算法，SLH算法和多路谱聚类算法中的NJW算法。谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题, 是一种点对聚类算法,对数据聚类具有很好的应用前景。 （二）国内外的研究现状以及发展趋势 谱聚类的诞生可以追溯到1973年，donath和hoffman 首次基于邻接矩阵构造了图的划分。在同一年，fieldler发现图的二划分与laplacian图的第二小特征向量有密切关系，并且建议使用该特征向量进行图的划分。从此以后，许多研究者加入到谱聚类方法的研究队伍中。
国外研究现状：对于特征向量的选取，Jenssen等人通过对Renyi熵的研究，推导出该熵的最大化的近似解就是相似矩阵取得较大值的前k个特征向量。Tao Xiang, Shaogang Gong认为最优的聚类结果不一定是最大的K个特征值对应的特征向量，他提出了一个新的的概念为向量相关度，用向量的相关度来区分向量的重要性，这样对于特征向量的选取我们就得到一个准则，选取向量相关度高的特征向量。对于聚类数目的选取，Azran，Ghahramani认为K值得选择对聚类结果起到关键的作用，应该参照随机游走后的概率矩阵，原始概率矩阵P确定的k值通常和实际值有着很大出入。 国内研究现状：赵凤，焦李成等将半监督信息引入到谱聚类特征向量的选取上，为了可以体现数据的内部结构；田铮，小斌等认为聚类数目不应该由认为确定，他们为了避免了聚类数目的人为确定，设计了一种谱聚类算法，这种算法根据矩阵的扰动理论，可以更好的解决聚类数目的人为确定问题。孙昌思核等人，认为聚类数目应该可以自动确定，比人为确定可以减少误差，他们利用特征值之间的差值提出了一种自动确定聚类数目的谱聚类算法。 发展趋势：为了提高谱聚类算法的性能，许多专家学者也做了很多其他方面的研究，Dhillon提出了处理海量数据的计算]的办法，将谱聚类与核K-Means相结合。高倩为了提高了算法效率，节省时间成本，采用了抽样的方法，先推导出样本的特征向量，然后去估算原始数据的特征向量。 （三）主要参考文献 [1] Distell, Graph theory [M]. Beijing: World Publishing Corporation, 2008. [2] Weifu Che, Guocan Feng. Spectral clustering: A semi-supervised approach. Neuro computing [J].2012,77(1).119-228. [3]Zhao F, Liu H, Jiao L. Spectral clustering with fuzzy similarity measure [J]. Digital Signal Processing.2011,21(6):56-63. [4] Carlos Alzate, Johan A K, Suykens. Hierarchical kernel spectral 1
clustering [J]. Pattern Recognition 2012,35(3):24-35. [5] Xia T., Cao J., Zhang Y., et al. On defining affinity graph for spectral clustering through ranking on manifolds. Neurocomputing, 2009, 72(13-15), 3203-3211. [6]L. Zelnik-Manor, P. Perona. Self-tuning spectral clustering. Advances in Neural Information Processing Systems. Cambridge, MA: MIT Press, 2004. [7] 王玲，薄列峰，焦李成.密度敏感的半监督谱聚类.软件学报，2007，18（10），2412-2422 . [8] 陈应良，王士同.权重马氏距离高斯核在谱分割中的应用.计算机应用，2008，28（07），1738-1741. [9] 郑吉，苗夺谦，王睿智等.一种基于粗糙集理论的谱聚类算法.计算机科学，2009，36 （05），193-196. [10] M. Filipponea, F. Camastrab, F. Masullia, S. Rovetta. A survey of kernel and spectral methods for clustering. Pattern Recognition. 2008, 41(1):176-190. [11] Xiang T., Gong S. Spectral clustering with eigenvector selection. Pattern Recognition, 2008, 41(3), 1012-1029 . [12] 赵凤，焦李成，刘汉强等.半监督谱聚类特征向量选择法.模式识别与人工智能，2011，24(01)，48-55. [13] 田铮，李小斌，句彦伟.谱聚类的扰动分析.中国科学，2007，37(04)，527-543. [14] 孙昌思核，孔万增，戴国骏.一种自动确定类个数的谱聚类算法.2010，30(02)，53-56 . [15] ] Ulrike von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, 2007 17(4). [16]朱强生，何华灿，周延泉.谱聚类算法对输入数据顺序的敏感性.计算机应用研究，2007，24（04），62-63. [17]马秀丽，焦李成.联合模型初始化独立谱聚类算法.西安电子科技大学学报（自然科学版），2007，34（05），768-808 . 1
浅谈谱聚类算法及应用开题报告
