谱聚类算法的改进

《谱聚类算法的改进》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、分类号：密级：UDC：编号：工学硕士学位论文谱聚类算法的改进硕士研究生：杨朋指导教师：卢志茂教授学科、专业：信号与信息处理学位论文主审人：毕晓君教授哈尔滨工程大学2014年3月万方数据万方数据分类号：密级：UDC：编号：工学硕士学位论文谱聚类算法的改进硕士研究生：杨朋指导教师：卢志茂教授学位级别：工学硕士学科、专业：信号与信息处理所在单位：信息与通信工程学院论文提交日期：2014年01月13日论文答辩日期：2014年03月10日学位授予单位：哈尔滨工程大学万方数据万方数据ClassifiedIndex:U.D.C:ADissertationfort

2、heDegreeofM.EngTheImprovementoftheSpectralClusteringAlgorithmCandidate:YangPengSupervisor:Prof.LuZhimaoAcademicDegreeAppliedfor:MasterofEngineeringSpecialty:SignalandInformationProcessingDateofSubmission:Jan.13,2014DateofOralExamination:Mar.10,2014University:HarbinEngineeringU

3、niversity万方数据万方数据哈尔滨工程大学学位论文原创性声明本人郑重声明：本论文的所有工作，是在导师的指导下，由作者本人独立完成的。有关观点、方法、数据和文献的引用已在文中指出，并与参考文献相对应。除文中已注明引用的内容外，本论文不包含任何其他个人或集体已经公开发表的作品成果。对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。作者（签字）：日期：年月日哈尔滨工程大学学位论文授权使用声明本人完全了解学校保护知识产权的有关规定，即研究生在校攻读学位期间论文工作的知识产权属于哈尔滨工程大学。哈

4、尔滨工程大学有权保留并向国家有关部门或机构送交论文的复印件。本人允许哈尔滨工程大学将论文的部分或全部内容编入有关数据库进行检索，可采用影印、缩印或扫描等复制手段保存和汇编本学位论文，可以公布论文的全部内容。同时本人保证毕业后结合学位论文研究课题再撰写的论文一律注明作者第一署名单位为哈尔滨工程大学。涉密学位论文待解密后适用本声明。本论文（□在授予学位后即可□在授予学位12个月后□解密后）由哈尔滨工程大学送交有关部门进行保存、汇编等。作者（签字）：导师（签字）：日期：年月日年月日万方数据万方数据谱聚类算法的改进摘要当前，聚类分析是国际数据挖掘和机器学习

5、领域中的研究热点之一。作为一种较新的聚类分析方法的谱聚类方法具有传统聚类方法不具有的许多优点，如谱聚类方法简单直观、容易实现、能得到全局最优解和能对任意形状的数据空间进行聚类分析等等。传统谱聚类方法以关联矩阵为基础，构建Laplacian矩阵，从而计算出矩阵的特征值和特征向量，接下来根据某种规则选取一个或多个特征向量进行聚类分析。然而，上述过程至少存在两个亟需解决的问题，一是，如何设置构造关联矩阵所需的尺度参数；二是，直接对Laplacian矩阵进行特征值分解的计算复杂度高达O(n3)。这两个问题制约了传统谱聚类方法在实际中的应用。为了改进谱聚类算

6、法，本文作了如下工作：（1）研究表明，低秩逼近技术和采样技术一样可以解决矩阵的特征值分解的计算复杂度高的问题，而且低秩逼近技术的逼近误差要低于采样技术。为此，本文将低秩逼近技术与传统谱聚类算法结合起来提出了一个新的谱聚类算法，命名为基于低秩逼近技术的谱聚类算法。实验结果表明，新的算法能够在降低算法的逼近误差的同时，取得较高的执行效率和较好的聚类效果。（2）虽然低秩逼近技术和采样技术可以大大的降低谱聚类算法的计算复杂度，但是二者均基于抽样技术。众所周知，在抽样技术中无论样本点是被随机抽取或是采用其它较复杂的方法抽取，这些样本点均不能够完全地代表整个数

7、据集合且不能正确地捕获到整个数据集合的几何结构。因而，需要引入不涉及采样技术的其它手段来获得谱聚类的特征空间。为此，本文将通勤时间与传统谱聚类算法结合起来提出了一个新的谱聚类算法，命名为基于通勤时间的谱聚类算法。实验结果表明，新的算法能够在保证有较高的执行效率的同时取得更好的聚类效果。（3）本文对一个基于Nyström逼近技术的谱聚类算法作了改进，使其理论基础更加完善，执行效率更高。关键字：聚类分析；数据挖掘；机器学习；谱聚类万方数据万方数据谱聚类算法的改进ABSTRACTAtpresent,clusteringanalysisisoneofthe

8、veryactiveresearchfocusesintheinternationalfieldofDataMininga