基于近邻图分析的谱聚类算法的研究

作     者：郭梅梅 

作者单位：陕西师范大学 

学位级别：硕士

导师姓名：王晅

授予年度：2019年

学科分类：12[管理学] 1201[管理学-管理科学与工程(可授管理学、工学学位)] 

主      题：欧氏距离 高斯核函数 K邻域 最短路径 k-means 

摘      要：谱聚类算法(Spectral clustering)是基于谱图理论的经典聚类算法之一,而属于K-way谱聚类算法的NJW(Ng-Jordan-Weiss)算法因其框架简单而广受关注。该算法可通过欧氏距离建立样本间的相似性度量矩阵W;虽然欧氏距离的度量方式简单,容易理解,可用于大多数据类型。但是,欧氏距离是基于每个独立的样本,样本间的关系都是直接获取,所建立的样本度量也是基于样本全局。样本之间的关联比较单一,不能充分描述样本间的局部特征,使建立的相似性特征描述不完整,不能完全反映样本之间的关系。除此之外,传统的K近邻算法中的K值都是通过多次实验获得的经验值,很难证明其为最佳值,所以容易陷入局部最优。为了解决以上问题,本文基于近邻图分析,对谱聚类算法进行研究,主要作了以下工作:第一,针对欧氏距离相似性度量方法的不足,提出一种基于K阈值的相似性度量的谱聚类算法;算法充分参考了各种样本区域的特性,利用K阈值的方式建立局部样本之间的联系,并在这些局部关联的基础上用最短路径建立全局连通图,然后以局部样本标准差作为高斯核的取值。该算法很好的克服了以欧氏距离建立联系时,对样本局部细节特征的忽视。第二,针对基于K阈值的相似性度量的谱聚类算法中K值的选取问题,提出一种基于自定义K值的聚类算法。在基于K阈值的相似性度量的谱聚类算法中,起始的K值选取来自于实验;为了避免人为主观性对实验结果的影响,该算法通过循环迭代的方式选取构建谱图的最佳K值,对于不同的样本集合,迭代循环次数也不同。我们将提出的方法与已存在的几种聚类算法进行比较,通过人工数据集和UCI数据集的实验结果可以得出,提出的新算法不但在离散的数据样本上有很好的聚类效果,还克服了几种对比实验对流行数据不敏感的缺点。