论文部分内容阅读
谱聚是聚类的一个重要分支。谱聚类算法不同于其他传统聚类算法,它将聚类问题转化成图的最优划分问题。谱聚类算法不关心数据集的形状,能处理复杂、高维非球形的数据样本。同时,谱聚类算法实现简单,计算复杂度小,非常适合处理大型数据集,可应用到分布式系统中去,并能获得全局最优解,改善聚类效果。谱聚类算法的难点之一是聚类簇数k值的检测。大多数聚类算法都需要人工提前来设定聚类簇数,而不合适的聚类簇数会导致不理想的聚类效果,甚至会使聚类过程失去意义。另外,谱聚类算法的另一个研究热点是分布式谱聚。集中式的谱聚类算法不能直接适用于分布式系统。对此,本文对传统的谱聚类算法作出了如下改进:首先,本文提出了一种基于特征间隙的簇数检测(Identifying Clustering Number based on Eigengap,ICNE)算法。通过构建基于邻接矩阵的规范拉普拉斯矩阵,顺序求解拉普拉斯矩阵的特征解,计算矩阵相邻特征值的间隙,判断出特征间隙的所在位置,确定簇数k,ICNE方法只需求解出前k个特征解,从而减少了特征求解的计算量,实现了快速有效地确定聚类簇数k。其次,提出了一种基于ICNE方法的分布式谱聚类(Decentralized Spectral Clustering with Identifying Clustering Number based on Eigengap,DSC-ICNE)方法,以分布式方式完成自动谱聚类,使得谱聚类方法可以应用于分布式系统,提高谱聚类算法的可扩展性。最后,提出了基于特征间隙检测簇数的谱聚类(Spectral Clustering with Identifying Clustering Number based on Eigengap,SC-ICNE)算法,在ICNE算法的基础上快速有效地确定聚类簇数k,完成谱聚类算法。并对SC-ICNE算法在UCI数据库上进行了仿真,仿真结果表明,SC-ICNE算法能够快速有效地实现聚类,而且相对于k-means算法,SC-ICNE算法对非球形数据集的聚类效果更好。