浅谈谱聚类算法及应用开题报告

1、浅谈谱聚类算法及应用开题报告 福州大学本科生毕业设计（论文）开题报告 学生姓名 杨清 学 号 031301316 专业 数学与应用数学 班 级 论文（设计）题目 浅谈谱聚类算法及应用 指导老师姓名 职 称 一、论文（设计）选题的依据（选题的目的和意义、该选题国内外的研究现状及发展趋势、主要 _等） （一）选题的目的与意义 选题目的： 在这个大数据时代，数据分析是一个很重要的问题，聚类技术的发展，大大缓解了这种情况。在模式识别领域，谱聚类的出现成为了学者研究的焦点。由于谱聚类算法复杂程度低，实现比较容易等特点，在各个领域受到了许多专家的肯定，成为一个重要的研究对象。经过国内外专家学者不断研究和探

2、索，谱聚类算法得到了很大的发展，但是也存在一些问题，随着研究的深入，出现各种各样的谱聚类算法，但是这些算法的实现方法都是十分相似的。 研究意义： 谱聚类算法大致上可以分为以 PF 算法为代表的二路谱聚类算法和以 NJW算法为代表的多路谱聚类算法两种类型。二路谱聚类算法使用的主要是图的二路划分准则，多路谱聚类算法使用的主要是图的多路划分准则。 应用比较广泛的谱聚类算法主要包括二路谱聚类算法中的 PF 算法，SM 算法，SLH 算法和多路谱聚类算法中的 NJW 算法。谱聚类算法建立在图论中的谱图理论基础上, 其本质是将聚类问题转化为图的最优划分问题, 是一种点对聚类算法,对数据聚类具有很好的应用前

3、景。 （二）国内外的研究现状以及发展趋势 谱聚类的诞生可以追溯到 1973 年，donath 和 hoffman 首次基于邻接矩阵构造了图的划分。在同一年，fieldler 发现图的二划分与 laplacian 图的第二小特征向量有密切关系，并且建议使用该特征向量进行图的划分。从此以后，许多研究者加入到谱聚类方法的研究队伍中。 国外研究现状：对于特征向量的选取，Jenssen 等人通过对 Renyi 熵的研究，推导出该熵的最大化的近似解就是相似矩阵取得较大值的前 k 个特征向量。Tao Xiang, Shaogang Gong 认为最优的聚类结果不一定是最大的 K 个特征值对应的特征向量，他提

4、出了一个新的的概念为向量相关度，用向量的相关度来区分向量的重要性，这样对于特征向量的选取我们就得到一个准则，选取向量相关度高的特征向量。对于聚类数目的选取，Azran，Ghahramani 认为 K值得选择对聚类结果起到关键的作用，应该参照随机游走后的概率矩阵，原始概率矩阵 P 确定的 k 值通常和实际值有着很大出入。 国内研究现状：赵凤，焦李成等将半监督信息引入到谱聚类特征向量的选取上，为了可以体现数据的内部结构；田铮，小斌等认为聚类数目不应该由认为确定，他们为了避免了聚类数目的人为确定，设计了一种谱聚类算法，这种算法根据矩阵的扰动理论，可以更好的解决聚类数目的人为确定问题。孙昌思核等人，认

5、为聚类数目应该可以自动确定，比人为确定可以减少误差，他们利用特征值之间的差值提出了一种自动确定聚类数目的谱聚类算法。 发展趋势：为了提高谱聚类算法的性能，许多专家学者也做了很多其他方面的研究，Dhillon 提出了处理海量数据的计算的办法，将谱聚类与核K-Means 相结合。高倩为了提高了算法效率，节省时间成本，采用了抽样的方法，先推导出样本的特征向量，然后去估算原始数据的特征向量。 （三）主要 _ 1 Dis _, Graph theory M. Bei _g: World Publishing Corporation, xx. 2 Weifu Che, Guocan Feng. Spect

6、ral clustering: A semi-supervised approach. Neuro puting J.xx,77(1).119-228. 3Zhao F, Liu H, Jiao L. Spectral clustering with fuzzy similarity measure J. Digital Signal Processing.xx,21(6):56-63. 4 Carlos Alzate, Johan A K, Suykens. Hierarchical kernel spectral clustering J. Pattern Recognition xx,3

7、5(3):24-35. 5 Xia T., Cao J., Zhang Y., et al. On defining affinity graph for spectral clustering through ranking on manifolds. Neuroputing, xx, 72(13-15), 3203-3211. 6L. Zelnik-Manor, P. Perona. Self-tuning spectral clustering. Advances in Neural Information Processing Systems. Cambridge, MA: MIT P

8、ress, xx. 7 王玲，薄列峰，焦李成.密度敏感的半监督谱聚类.软件学报，xx，18（10），2412-2422 . 8 陈应良，王士同.权重马氏距离高斯核在谱分割中的应用.计算机应用，xx，28（07），1738-1741. 9 郑吉，苗夺谦，王睿智等.一种基于粗糙集理论的谱聚类算法.计算机科学，xx，36 （05），193-196. 10 M. Filipponea, F. Camastrab, F. Masullia, S. Rovetta. A survey of kernel and spectral methods for clustering. Pattern Recogn

9、ition. xx, 41(1):176-190. 11 Xiang T., Gong S. Spectral clustering with eigenvector selection. Pattern Recognition, xx, 41(3), 1012-1029 . 12 赵凤，焦李成，刘汉强等.半监督谱聚类特征向量选择法.模式识别与人工智能，xx，24(01)，48-55. 13 田铮，李小斌，句彦伟.谱聚类的扰动分析.中国科学，xx，37(04)，527-543. 14 孙昌思核，孔万增，戴国骏.一种自动确定类个数的谱聚类算法.xx，30(02)，53-56 . 15 Ulrik

10、e von Luxburg. A Tutorial on Spectral Clustering. Statistics and Computing, xx 17(4). 16朱强生，何华灿，周延泉.谱聚类算法对输入数据顺序的敏感性.计算机应用研究，xx，24（04），62-63. 17马秀丽，焦李成.联合模型初始化独立谱聚类算法.西安电子科技大学学报（自然科学版），xx，34（05），768-808 . 18高倩.基于模糊理论的谱聚类算法.硕士学位论文，江南大学，xx . 19Dhillon S, Guan Y, Kulis B. A unified view of kernel K-Mea

11、ns, spectral clustering and graph cuts. University of Texas at Austin UTCS Technical Report TR-04-25. xx. 20Kamvar S D, Klein D, Manning C D. Spectral Learning. IJCAI-03, xx . 21 金慧珍，赵辽英.多层自动确定类别的谱聚类算法.计算机应用，xx，28（05），1229-1231 . 3 二、论文（设计）的主要研究内容及预期目标 （一）论文的主要研究内容 第 1 章 绪论 1.1 谱聚类算法概述 1.2 国内外研究状况 1

12、.3 论文结构 第 2 章 理论基础 2.1 聚类分析概述及分类 2.1.1 聚类分析 2.2 图和矩阵的表示 2.2.1 图的基本知识 2.2.2 图的矩阵表示 2.2.3 相似性测度 2.2.4 拉普拉斯矩阵及其性质 2.3 相似图的构造方法 2.4 谱图划分准则 2.5 本章小结 第 3 章 谱聚类算法原理 3.1 谱聚类算法介绍 3.1.1 PF 算法 3.1.2 SM 算法 3.1.3 SLH 算法 3.1.4 NJW 算法 3.2 算法实例 第 4 章 谱聚类算法在图像分割中的应用 4.1 谱聚类算法在图像分割中的应用基础 4.2 应用实例 4.3 本章小节 结论 4 (二)论文研

13、究的预期目标 通过撰写这篇论文，充分应用平时所学的相关理论，使理论联系实际，提高理论应用及解决实际问题的能力。同时，本文主要介绍了谱聚类算法的基础以及算法原理和实现步骤，谱聚类算法的实质是对高维数据进行降维， 所以在复杂度上要比传统的 k-means 算法要简单，并通过实例说明了可以完成一些传统算法所不能的分类。在文章最后也给出了谱聚类算法在图像分割上的应用，但是也存在着耗时长，占用内存大的缺点，给未来的研究提供方向。 5 三、论文（设计）的主要研究方案（拟采用的研究方法、准备工作情况及主要措施） （一）拟采用的研究方法 （1）文献研究法：利用中国知网、维普、万方等数据库完成与毕业论文相关内容

14、的论文的检索；利用图书馆的图书资源查阅相关的理论内容；充分的利用互联网进行资料的检索收集。 （3）实例分析法：将谱聚类算法应用到一个世纪图像中，来看其分割效果。从处理结果可以看出谱聚类算法在图像分割上的应用是可行的，是可以进一步进步发展的。 （二）准备的工作情况 (1) 了解国内外关于论文课题相关领域的学术研究状况，充分占有资料。 (2) 对资料进行深入分析，为确立论点打下基础。 (3) 初步确定材料的取舍、论证方法的选取、结构层次的安排等，编写提纲，做好写作前的准备工作。 （三）研究过程中可能遇到的问题 （1）相似矩阵的构造存在很多困难 （2）选择特征向量的方法有很多种，如何计算这些特征向量就成为谱聚类算法一个重要的问题。 （3）聚类数目的确认，聚类结果的成功与否和聚类数目有着很大的关系。但是，聚类数目的获取是十分困难的。 （4） 拉普拉斯矩阵的选择，目前没有合适的理论指导该如何在三种拉普拉斯矩阵中，选择出最正确的一种。 （四）主要措施 （1）查阅相关资料，确立论文内容。 （2）询问老师相关方面的问题，找指导老师指导。 （3）通过应用实例，进行分析。 6 四、论文（设计）研究工作进展安排 第一阶段：确定毕业论文的选题，收集资料，资料，完成论文的任务书。 第二阶段