图论划分准则下聚类性能分析.docx

摘要:数据的分类是模式识别，机器学习等领域的基本问题，在没有先验知识的条件下，仅凭数据在样本空间中的分布情况将其分门别类，凸显出样本间的共性与异性。分类的效果评价在于同类个体之间的相似度高，不同类个体之间的相异度大，对于外来的新样本能够保持分类的稳定性。

本文首先介绍了关于图论的一些概念，基于图论划分准则下的谱聚类算法。然后在matlab中选取了数据点，基于聚类的紧密度与分离度两个维度作为评价指标，通过编程实验得出在PF算法，SM算法，以及SLH算法中，SM达到了较好的聚类效果，即SM算法既能最大化的使类内数据保持较高的相似性，又能使类间数据相似度较低。

关键词：数据分类；图论；图论划分准则；谱聚类算法 

目录

摘要

Abstract

第1节 引言（引入谱聚类算法的定义，介绍国内外研究现状，及论文的意义或目标）-2

第2节 基本理论-2

2.1图的定义和基本概念-2

2.2谱图划分准则-4

2.2.1 最小割集准则(Minimum cut)-4

2.2.2 规范割集准则(Normalized cut)-4

2.2.3 比例割集准则(Ratio cut)-4

2.2.4 平均割集准则(Average cut)-4

2.2.5 最小最大割集准则(Min-max cut)-5

2.3 相似矩阵、度矩阵和拉普拉斯矩阵-5

2.4 势函数、Fiedler向量及谱-5

第3节 谱聚类算法-6

3.1 PF算法-6

3.2 SM算法-6

3.3 SLH算法-7

第4节 实验和结果分析-8

4.1 数据集的选取-8

4.2 实验结果分析-9

4.2.1 PF算法结果-9

4.2.2 SLH算法结果-10

4.2.3 SM算法结果-11

4.3 聚类效果分析-12

第5节 结论-13

参考文献-14