数据挖掘中如何根据数据之间的相似度确定簇(Cluster)数一直是聚类算法中需要解决的难题。文中在经典谱聚(Spectral Clustering)算法的基础上提出了一种基于特征间隙检测簇数的谱聚类算法(Spectral Clustering with Identifying Cluster...
详细信息
数据挖掘中如何根据数据之间的相似度确定簇(Cluster)数一直是聚类算法中需要解决的难题。文中在经典谱聚(Spectral Clustering)算法的基础上提出了一种基于特征间隙检测簇数的谱聚类算法(Spectral Clustering with Identifying Clustering Number based on Eigengap,SC-ICNE)。通过构建规范的拉普拉斯矩阵,顺序求解其特征值和相应特征向量,并得到矩阵相邻特征值的间隙,通过判断特征间隙的位置来确定簇数k。最后,通过对前k个特征向量的k-means算法实现数据集的聚类。文中通过仿真分析了高斯相似度函数对SC-ICNE聚类性能的影响,在非凸球形数据集和UCI数据集上进行了性能仿真,并和k-means聚类算法进行了对比,在检测簇数和聚类准确性方面,验证了SC-ICNE算法的有效性。
谱聚是聚类的一个重要分支。谱聚类算法不同于其他传统聚类算法,它将聚类问题转化成图的最优划分问题。谱聚类算法不关心数据集的形状,能处理复杂、高维非球形的数据样本。同时,谱聚类算法实现简单,计算复杂度小,非常适合处理大型数据集,可应用到分布式系统中去,并能获得全局最优解,改善聚类效果。谱聚类算法的难点之一是聚类簇数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算法对非球形数据集的聚类效果更好。
暂无评论