一种基于自适应相似矩阵的谱聚类算法(3)
【作者】网站采编
【关键词】
【摘要】4)构建规范化Laplacian矩阵L=D-1/2WD-1/2,其中 5)计算矩阵L的前k个最大特征值及其对应的特征向量v1,v2,…,vk,可以得到特征矩阵V=[v1,v2,…,vk]∈Rn×k; 6)将矩阵V的
4)构建规范化Laplacian矩阵L=D-1/2WD-1/2,其中
5)计算矩阵L的前k个最大特征值及其对应的特征向量v1,v2,…,vk,可以得到特征矩阵V=[v1,v2,…,vk]∈Rn×k;
6)将矩阵V的行向量规范为单位向量,得到新矩阵为U,则
7)将矩阵U的每一行对应回原数据集中的相应点,利用k-means算法将其聚成k类C1,C2,…,Ck。
3 实验与分析
为了验证本研究算法的性能,对比算法为k-均值算法(k-means)和基于规范化拉普拉斯矩阵的谱聚类算法(NJW),实验数据集为5个人工数据集和5个真实UCI数据集。
实验的操作平台为64位win7系统、CPU为Intel(R) Core(TM)i5-2450M(2.50 GHz)、4G内存的计算机和Matlab R2014a。
3.1 评价指标
对聚类结果的评价是检验聚类算法结果好坏的重要环节,不同的评价标准会突出聚类算法不同的特性。本研究选取Rand指标[16]作为评价标准,即根据本研究算法得到的决策数的正确率来评价算法的性能。定义决策数的正确率如下:
假设待聚类数据集有n个样本,任意2个样本可组成一个样本对,则有n(n-1)/2个样本对,即有n(n-1)/2个决策数目。式中:a表示同一类的样本对被聚类到同一簇中;b表示不同类的样本对被聚类到同一簇中;c表示同一类的样本对被聚类到不同簇中;d表示不同类的样本对被聚类到不同类的簇中,即a+d表示聚类正确的决策数,a+b+c+d表示总决策数n(n-1)/2。可知RI ∈(0,1),当RI的值越大,则说明决策数的正确率越高。当RI=1时,则说明聚类算法的聚类结果完全正确。
3.2 数据集及实验结果分析
3.2.1 人工数据集
5个人工实验二维数据集的详细信息如下:
Twomoons数据集:由2个弧形结构构成,1 502个样本,2个类。
LineBlobs数据集:笑脸形,包含266个样本,3个类。
Spiral数据集:螺旋形,包含944个样本,2个类。
Sticks数据集:由4个线形结构构成,包含512个样本,4个类。
Threecircles数据集:由同心圆构成,包含299个样本,3个类。
实验结果在图4中给出,本研究所提算法在密度分布不均和非块状(弧形、圆圈形、线形等)数据集上都得到最优划分,证明了基于自适应相似度矩阵的谱聚类算法的强大聚类功能。而k-means算法和NJW 算法都或多或少的出现了不同程度的聚类错误。试验中NJW算法中σ的取值为数据点距离差值Δd的10%~20%时较理这里的D为欧式距离矩阵),统一取σ=0.1Δd。
图4 3种算法在5个人工数据集上的聚类结果Fig.4 Clustering results of 3 algorithms on 5 manual datasets
3.2.2 标准UCI数据集
5个真实实验数据集来自UCI数据库,分别是:
鸢尾花数据集——Iris Data Set,后文简称Iris;
葡萄酒数据集——Wine Data Set,后文简称Wine;
玻璃鉴定数据集——Glass Identification Data Set,后文简称Glass;
澳大利亚信贷审批数据集——Statlog (Australian Credit Approval) Data Set,后文简称Acd;
钞票验证数据集——Banknote Authentication Data Set,后文简称Bna。
数据特征如表1所示。
表1 UCI数据集的数据特征Tab.1 Data characteristics of UCI datasets数据集样本数维数类数IrisWineGlassAcdBna
表2给出的是k-means、NJW和本研究算法的聚类准确率,在NJW算法中的最后一步会用到k-means算法划分,而在应用该算法时,不同的初始类中心会产生不同的聚类结果,为了降低此影响,本研究的k-means和NJW算法的取值都是程序运行20次的平均值。上节提到NJW算法中σ的取值为数据点距离差值的10%~20%较理想,不失一般性,取δ=0.1d和δ=0.2d两种情况下进行验证实验。
从表2给出的准确率的对比分析可知,在Wine数据集和Bna数据集上的聚类效果k-means算法优于NJW算法,在Iris数据集和Acd数据集上的聚类结果,不论NJW算法取哪个参数都要比k-means算法高,而在Glass数据集上,k-means算法的聚类结果则介于NJW算法的2个不同参数得到的聚类准确率之间,这表明对具有不同结构的数据集,不同算法都有其优缺点。而本研究所提算法在这5个实际数据集上的聚类准确率都是最高的,再一次证明了本研究算法的鲁棒性。
表2 3种算法在UCI数据集上的RI正确率Tab.2 RI correct rate of three algorithms in UCI dataset %数据集本研究算法
4 结 语
聚类结果对高斯核函数中尺度参数的选取极其敏感,距离函数在相似矩阵的构建中同样占据至关重要的地位,没有一种距离函数适合所有类型的数据集。本研究在充分分析数据聚类一致性特征的基础上,选用测地距离函数表征数据间的距离度量,同时引入共享近邻的定义来表征两点间的局部密度,进而构建了一种自适应的相似矩阵,更好地刻画数据集的本征结构,应用到谱聚类算法后,在密度分布不均以及非块状(弧形、圆圈形、线形等)的人工数据集上、通用国际UCI实际数据集上进行实验,表明了本文算法对复杂分布数据有很强的自适应能力,且准确率较高。下一步的研究重心将放在运行效率的提高以及在高维数据集上的准确性研究方面。
文章来源:《应用数学和力学》 网址: http://www.yysxhlx.cn/qikandaodu/2021/0311/385.html