基于成对约束的SubKMeans聚类数确定算法①

高 波,何振峰

(福州大学 数学与计算机科学学院,福州 350108)

聚类是一种无监督学习方法,它根据样本间相似度把样本划分到若干簇[1].K-Means 算法是聚类算法的一种典型代表,它因其简单而又有效的特性备受欢迎,并且在十大经典数据挖掘算法中排名第二[2].该算法根据用户指定的K值,基于某种距离度量方式,把样本划分为K个不同的簇,使得簇内样本相似性高,簇间样本相似性低[1].高维数据空间中数据分布稀疏且存在着大量无关属性,数据的重要结构信息会隐藏在海量的噪声数据中,因此使用K-Means 算法在高维数据上进行聚类很难发现数据的内在结构,使得聚类效果差[3,4].然而在现实的聚类分析应用场景中,数据维度通常很高,比如图片视频或文本数据,其维度一般为千万级,甚至更高.针对这一问题,Mautz 等人于2017年提出了SubKMeans 算法[5],该算法能够将数据映射到子空间中进行聚类,降低维度影响,提升K-Means 类算法聚类性能.

SubKMeans 算法将数据空间划分为一个包含有大部分重要信息的子空间和一个基本不包含重要信息的子空间,通过映射矩阵能够把数据投影到包含有大部分重要信息的子空间中进行聚类,从一定程度上减轻“维度灾难”对K-Means 类算法的影响.但是SubKMeans算法只是对经典K-Means 类算法的一种扩展,它依然会受到K-Means 类算法固有缺陷的限制[6].SubKMeans算法是无监督聚类算法,需要用户事先指定K值,而在现实中部分数据集的种类数是未知的,这给使用者带来巨大的困扰,因此SubKMeans 算法的聚类数确定研究具有重要的现实意义.

现有的子空间聚类算法可以划分为硬子空间聚类和软子空间聚类[7,8].硬子空间聚类把所有属性都看成同等重要,按照搜索子空间方式的不同,可以进一步划分为自底向上的子空间聚类算法和自顶向下的子空间聚类算法.软子空间聚类算法认为每个属性对于每个簇的贡献程度不一样,因此给每个属性赋予不同的权重.文献[9]和文献[10]中提出基于惩罚机制的竞争学习来逐步合并聚类簇,消除冗余聚类,最后为子空间聚类确定聚类数目.文献[11]基于类内紧凑性和类间分离性提出了一种新的聚类有效性指标,通过在K的取值范围内得出最佳指标值来为子空间聚类确定K值.文献[12]把现有的K值确定方法分为3 类,分别为传统方法、基于合并分裂方法和基于进化的方法.传统方法把最佳聚类有效性指标对应的K值作为最佳K值.基于合并分裂的方法根据聚类有效性指标的值是否更优来决定是否合并或分裂,达到稳定时的K值即为最佳K值.基于进化的方法使用特定的编码方式将可能的划分方式编码到个体或染色体中,通过遗传变异的方式得到适应性最好的个体,把该个体对应的K值作为最终K值.

为解决SubKMeans 聚类数确定问题,考虑到现实中有时能获取到类似成对约束之类的监督信息,参考文献[13]中成对约束与轮廓系数的结合方法,用成对约束改变轮廓系数计算方式,并用成对约束的满足度给轮廓系数加权.将改进后的轮廓系数作为聚类有效性评价指标,通过尝试不同的K值来找到一个最佳指标值,把该最佳指标值对应的K值作为最佳K值.第1 节介绍SubKMeans 算法,第2 节介绍改进的SubKMeans算法,第3 节对改进算法进行实验并分析实验结果,第4 节对所做工作进行总结.

1 SubKMeans 算法简介

SubKMeans 算法又称子空间K均值算法,它通过寻找数据的最佳子空间来发现数据的隐藏结构,降低维度影响,使得K-Means 类算法在高维数据上也能够有不错的表现[5].它的主要思想是：假设在一个数据集中大部分重要的信息会隐藏在某一个维度更低的子空间中,而其它的子空间能够提供的有用信息很少.根据这一假设把数据空间划分为两个子空间,包含大部分重要信息的子空间称为聚类子空间,基本不包含重要信息的子空间称为噪声子空间[5].为了提高聚类性能,挖掘出数据的内在结构,需要把数据映射到聚类子空间上进行聚类.

给定数据集D={x1,x2,···,xn}∈Rd×n,其中n是数据集D的规模,d是样本的维度.假设要把数据聚为K个簇在经典K-Means 算法中,最优化目标是使得每个样本到其聚类中心点的距离总和最小[1,5],即优化下式：

其中,ui为第i个簇的簇中心,‖·‖表示欧几里得范数.SubKMeans 算法需要将样本映射到聚类子空间中进行聚类,两个样本在聚类子空间中的距离可以通过式(2)计算.

其中,PC∈Rm×d,m为聚类子空间维度且m＜d,V∈Rd×d是一个维度为d的正交矩阵.通过能够将样本x映射到聚类子空间中,PC定义为：

其中,Im是维度为m的单位矩阵,Od−m,m∈Rm×(d−m)为零矩阵.重新定义样本间距离计算公式后,SubKMeans优化目标可以表示为：

其中,PN∈R(d−m)×d,(d−m)为噪声子空间维度,uD∈Rd×1为数据集D的列均值.将式(4)展开,利用矩阵迹的特性,可以表示为：

其中,Tr表示矩阵的迹,V是一个正交矩阵,根据正交矩阵的特性,可知VTSDV相乘后,只改变矩阵SD特征向量的方向,不改变其特征值本身.因此对于任意的正交矩阵V,VTSDV的特征值是常量.矩阵的迹是其所有特征值之和,所以是一个常量,在式(5)中可以忽略.令矩阵V为SiD特征分解后的特征向量,并且这些特征向量按照特征值的大小进行升序排序,最小的m个特征值对应的特征向量将数据映射到聚类子空间中,其它(d−m)个特征值对应的特征向量将数据映射到噪声子空间中,令m为SiD特征分解后特征值中小于0 的个数,可解决(4)的最优化问题.使用式(2)计算样本距离,不断迭代更新簇中心,更新矩阵V和子空间维度m,算法最终趋于稳定得到固定维度的聚类子空间和聚类簇.SubKMeans 算法框架如算法1 所示.

算法1.SubKMeans 算法输入：数据集D,聚类数量K{C1,C2,···,CK}输出：聚类簇,正交变换矩V,聚类子空间维度m m=■d/2」■」1)初始化聚类子空间维度 // 表示向下取整2)计算数据集列平均uD 3)采用式(8)计算数据集的散列矩阵ui,i=1,2,···,K S D 4)随机产生初始聚类中心5)随机矩阵执行QR 分解产生正交矩阵V 6)While(簇中心改变)x∈D 7)for each 8)采用式(2)计算样本到簇中心的距离9)将样本划分到距离最近的簇10)end for ui 11)更新簇中心12)采用式(7)计算簇的散列矩阵V,ε=eig(S iD)ε S i 13)更新矩阵 // eig 表示特征分解,V 为特征分解后的特征向量,为特征值m=|{e|e∈ε,e＜0}| ||14)更新维度 // 表示取集合中元素个数15)end while

虽然SubKMeans 算法能够自动确定聚类子空间维度,但需要用户指定聚类数量K.聚类数的确定是实际应用中的一个重大问题,因为在实际的应用场景中,需要聚类的数据往往是未知数据,我们不知道哪些数据应该分配到同一类中,对于给出的K值,我们也无法验证其是否是当前数据的准确K值.

2 基于成对约束的SubKMeans 聚类数确定算法

轮廓系数是一种常用的聚类有效性指标,可用于确定K值.在轮廓系数的计算方式中,聚类的轮廓系数为数据集中所有样本的轮廓系数的平均值,其把每个样本看成同等重要,把该指标作为聚类有效性指标用于确定聚类数量时,往往效果不好.而在实际的聚类过程中,存在部分样本对簇的贡献程度不一样的情况.为了体现这种差异,基于文献[13],本文引入成对约束,用轮廓系数的满足度给单个样本和整个聚类进行加权,并将违反的成对约束作为惩罚项,改进轮廓系数的计算方式,为SubKMeans 算法提出一种成对约束与轮廓系数结合的K值确定方法,称为Constrained Weighted SubKMeans,简称CSWKM.CSWKM 算法把改进后的轮廓系数作为一种新的聚类有效性指标,在K的取值范围内,计算出各个K值时的指标值,把最佳指标值对应的K值作为最佳K值.CSWKM 算法框架如下算法2所示.

算法2.CSWKM 算法输入：数据集D,成对约束Cst,最大迭代次数Count{C1,C2,···,CK}输出：聚类簇,正交变换矩V,聚类子空间维度m,聚类数量K 1)for to 2)SubKMeans 算法 //迭代时需判断迭代次数是否超过限制3)if (簇迭代次数小于Count)4)采用式(13)计算出此次划分的轮廓系数5)if(计算得出的轮廓系数小于0)6)令轮廓系数为0 7)else 8)令此次划分的轮廓系数为0 9)end for K=Kmin Kmax

CSWKM 需要分别计算出各个K值时的轮廓系数值,把最大轮廓系数对应的K值作为最终K值.在计算单个K值的轮廓系数时,需要迭代更新簇中心点、更新矩阵V和子空间维度m,同时在进行迭代时需要先判断当前迭代次数是否超过最大迭代次数,若超过,则停止迭代.Kmin一般取2,Kmax根据经验为样本数量的平方根取整,算法输出部分中,簇 {C1,C2,···,CK}、V和m对应于最佳K值的簇、V和m.与SubKMeans算法相比,CSWKM 算法对簇的迭代次数进行了限制,计算了每次簇划分后对应的轮廓系数值.

2.1 簇迭代次数限制

CSWKM 算法不同于SubKMeans 算法,CSWKM算法需要尝试K值范围内的每个K值.由于CSWKM算法中对簇的个数进行了限制,强制每个簇里面的样本个数必须大于5,在实验中发现当给出的K值与实际的K值相差较大时,会出现划分簇的迭代次数过多或者不收敛的现象.为了解决这一问题,给簇的迭代加上次数限制,使得超过迭代次数的K值划分认为是不合适的划分,直接令此次K值划分的簇轮廓系数为0,一般情况下令迭代次数为50.

2.2 轮廓系数

轮廓系数是目前使用最为频繁的聚类有效性评价指标之一,其要求同一个簇内样本间距离小,相似性高,不同簇间距离大,相似性低[13,14].聚类的轮廓系数为数据集中所有样本的轮廓系数平均值,单个样本x的轮廓系数计算公式如式(9)所示：

其中,a(x)表示样本x与其所属簇的其他样本之间的平均距离,为类内距离,b(x)表示样本x到其他簇的平均距离中的最小值,为类间距离.

单独使用轮廓系数作为聚类有效性评价指标效果并不理想,基于样本对簇的贡献程度不同,本文引入监督信息对轮廓系数进行改进.监督信息可以分为两类,一类是数据样本类别标签,另一类是数据样本之间的成对约束信息.成对约束一般是指must-link与cannotlink两种关联约束关系,正关联约束关系must-link(x,y)表示样本x和样本y属于同一类,负关联约束关系cannotlink(x,y)表示样本x和样本y属于不同类.由于成对约束信息获取成本低,容易得到,因此本文使用的监督信息为成对约束.为了体现出各个样本对簇的贡献大小,我们认为成对约束满足程度高的样本对簇的贡献程度更大,应该赋予更高的权重.但是当两个样本成对约束满足程度一致时,其对簇的贡献程度也可能不一样.文献[15]认为不同的成对约束的包含的信息不一样,应该区分对待.因此我们把未得到满足的成对约束之间的平均距离作为一个惩罚项,用来体现当成对约束满足程度一致时,样本对簇的贡献程度.

在must-link约束关系中,距离更大的约束包含的信息更多,违反后应该受到更大惩罚,应使得其轮廓系数更小.根据轮廓系数计算方式,通常类内距离越大轮廓系数越小.在不考虑权重的情况下,对同一个样本来说,违反约束后,其轮廓系数值应该更小,因此改进后的类内距离不应该比原先的类内距离小.所以令改进后的类内距离为a(x)与惩罚项两者中的最大值[13],如式(10)所示,a(x)表示为改进时的类内距离.

其中,xML表示与样本x具有正关联约束关系但在实际划分簇的过程中没有划分到同一个簇的样本集合,avg(x,xML) 表示样本x到集合xML的平均距离.

在cannot-link约束关系中,距离更小的约束包含的信息更多,违反后应该受到更大惩罚.根据轮廓系数计算方式,一般类间距离越小轮廓系数越小,同理,应该使得改进后的类间距离为b(x)与惩罚项两者中的最小值[13],如式(11)所示,b(x)表示未改进前的类间距离.

其中,xCL表示与样本x具有负关联约束关系但在实际划分簇的过程中划分到同一个簇的样本集合,avg(x,xCL)表示样本x到集合xCL的平均距离.

改进后的单个样本轮廓系数如式(12)所示.此时可能会出现轮廓系数为负数的情况,而轮廓系数不为负数,因此令小于0 的轮廓系数为0.

加权的方式分为划分权重与样本权重.划分权重是从整个聚类划分的角度出发,为在此次K值划分中满足的约束关系个数占总约束关系个数的比例.样本权重是从单个样本的角度出发,若样本x具有约束关系,则其样本权重为样本x满足的约束关系个数占样本x总约束关系个数的比例.若样本x没有约束关系但其所在的簇里面其它样本具有约束关系,那么其样本权重为簇中满足的约束关系个数占簇中总约束关系个数的比例.若样本x本身没有约束关系并且其所在的簇中其它样本也没有约束关系,那么其样本权重为1.

把划分权重与样本权重结合起来,聚类的轮廓系数计算公式如式(13)所示,其中SI(D)表示聚类轮廓系数,S i(x)′为单个样本x的轮廓系数,w(x)为样本权重,|D|为数据集D中的样本个数,weight为划分权重.

3 实验与分析

实验阶段使用6 个UCI 数据集和1 个UCR 数据集,如表1所示.Wdbc、Seeds、Iris、Wine、Vertebral column、Glass Identification、Breast Tissue 来自于UCI 数据集,Plane 来自于UCR 数据集,Wdbc 表示的是Breast Cancer Wisconsin (Diagnostic)数据集.每组数据都采用了标准化(将一组数的每个数都减去这组数的平均值后再除以这组数的均方差)的预处理方式,采用结合成对约束的轮廓系数作为聚类有效性评价指标,聚类准确性使用标准互信息(NMI).

表2是CSWKM 算法对比实验的结果,在CSWKM算法对比实验中,迭代次数Count取50,聚类数量K的最大取值范围为向下取整,n表示数据集的规模,Pre_K 表示实验重复100 次时,算法选出的最佳聚类数与原数据集中种类数一致的次数,“无”表示算法迭代10 000 次后未收敛,括号中的数字为成对约束的对数,NMI 的值为10 次十折交叉验证的平均值.把仅仅使用轮廓系数而不加成对约束作为聚类有效性评价指标,用来为SubKMeans 确定K值的算法称为SIKM.

表1 数据集相关信息

表2 CSWKM、SIKM 和SubKMeans 算法对比

从表2中CSWKM 与SIKM 算法的对比实验数据中可以明显看到CSWKM 算法的K值确定准确率不论在成对约束对数为10 或100 时,均要高于SIKM 算法,预测K值更加精准,使得NMI 系数也要高于SIKM算法.这一结果表明结合成对约束后的轮廓系数更能够表示聚类性能,验证了CSWKM 算法在确定K值上的有效性.在Glass 数据集上,由于有一类只有9 个样本,在进行十折交叉验证的时候会出现有的簇中无法满足样本数大于5 的要求,导致不收敛,而CSWKM 算法对簇的迭代次数进行了限制,因此不会出现不收敛的现象.从10 对成对约束与100 对成对约束的实验结果中可以看到,CSWKM 算法的NMI 系数随着预测K值准确率的提高而提升,由于在大多数的数据集中预测的K值准确率不能达到百分百,因而NMI 系数普遍要比SubKMeans 算法低.当K值预测准确率达到百分百时,CSWKM 算法的NMI 系数不低于SubKMeans算法,可以从Wdbc 和Seeds 数据集的实验结果中看出.在部分数据集上,可能聚为其它簇的效果要更好,因而预测K值准确率虽然没有达到百分百,但是CSWKM算法的NMI 系数还是要高于SubKMeans 算法.

4 总结与展望

针对SubKMeans 算法需要用户指定K值的问题,提出了一种基于成对约束的SubKMeans 聚类数确定算法.将成对约束运用到轮廓系数中,首先用成对约束改进轮廓系数的计算方式,其次用成对约束的满足程度给轮廓系数加权,将改进后的轮廓系数作为聚类有效性评价指标,在K的取值范围内根据最佳指标值挑选出对应的最佳K值,有效的解决了SubKMeans 算法在确定聚类数量方面的难题.最后,通过在UCI 和UCR数据集上进行实验,对比没有使用成对约束改进轮廓系数的SIKM 算法和SubKMeans 算法.实验结果表明,CSWKM 算法的K值确定准确率和聚类效果优于SIKM算法,验证了CSWKM 算法的有效性.并且CSWKM算法在给出100 对成对约束时,聚类效果优于SubKMeans算法.未来的工作将致力于如何把子空间信息作为确定K值的一个考虑因素.