皋 军, 黄欣辰, 邵 星

(1.江苏科技大学 计算机学院, 镇江 212003)(2.盐城工学院 信息工程学院, 盐城 224002)

聚类分析的目的是依据对象之间的相似度将数据对象分组,使得簇内对象相似度尽量高,而簇间对象相似度尽量低,簇内相似性越大,簇间差别越大,聚类就越好[1].常用的聚类分析方法分为:基于划分的聚类方法[2],将数据对象集划分成不重叠的簇,使得每个数据对象仅在一个簇中;基于层次的聚类方法[3],允许簇有子簇,嵌套簇的集群,组织成一棵树;基于密度的聚类方法[4],将高密度与低密度区域分离来进行分类;谱聚类方法[5],依据谱图理论将聚类问题转化为图划分问题.

单个的聚类方法不能产生令人满意的结果,因此促进了聚类集成的研究. 文献[6]将多个不同的聚类结果进行合并,从而获得比传统聚类算法更好的聚类结果. 作为传统聚集算法的重要扩展,聚类集成能取得更加优越的聚类结果,且在处理数据样本时采用并行的方式进行合并,但缺点是若产生了结构不同的初始聚类成员,因此如何取舍对最终的聚类结果产生极大的影响[7]. 文献[8]提出了聚类集成选择(Cluster Ensemble Selection)的思想,即从初始聚类成员集中选择满足某些规则的部分聚类成员用于集成,进而产生最终聚类结果，该方法可以选择出差异度大的聚类成员参与集成,以确保最终聚类结果质量.

目前聚类集成和聚类集成选择技术的研究主要集中在无监督学习领域中,没有考虑到用户或者专家提供的先验知识. 半监督聚类集成将少量带有标签的数据带入到聚类集成中,监督与指导集成过程,最终会获得更加优越的聚类结果,使得整个过程更具稳定性、准确性和鲁棒性[9-11].文献[12]提出了一种基于成对约束的判别型半监督聚类分析算法,利用成对约束和线性判别分析对数据同时进行聚类和降维,并在算法目标函数中增加惩罚项，以解决约束违反问题,取得了满意的聚类结果.

与现有聚类集成算法不同,文中将选择聚类与半监督聚类结合,首先通过基于成员质量和差异度的选择方法选出一部分初始聚类成员[13],然后借鉴半监督聚类集成的关键思想,利用成对约束等先验知识,将半监督信息带入到选择聚类集成过程,选择出最终聚类成员集,设计了一种半监督选择聚类集成方法(semi-supervised selective cluster ensemble,SSCES). 并在多组基准数据集上进行实验,表明SSCES能够提升聚类质量,取得更好的聚类结果.

1 相关技术介绍

选择性聚类集成是在传统聚类集成的框架上[6],增加了聚类成员选择的步骤. 一般分为3步：第一步，聚类成员生成输入数据集,运行常用聚类分析算法,输出聚类成员集P={p1,p2,…,pH};第二步,聚类成员选择将输入聚类成员集P,对聚类成员进行选择,得到集成成员集P′={P′1,P′2,…,P′k};第三步，共识函数设计输入集成成员集P′,对集成成员集进行融合,输出最终结果Pf.

1.1 聚类成员生成

常用的聚类成员生成方法有以下几种：第一种方法是对原始数据集进行处理,如对数据集采用不同的采样方法得到多个样本数据集；第二种方法是输入不同的输入特征,如设置不同的k值；第三种方法是对同一数据集多次执行同一种算法,由于选择的初值不同,可以获得不同的聚类结果[14].

因为k-means算法简单、实用,且对初始化、参数及其特征的变动极为敏感. 一般选择k-means算法作为聚类成员的生成算法. 假设有N个数据对象的数据集X={x1,x2,…,xN},令k值固定,通过随机化初始聚类中心来得到初始聚类成员pi(i=1,2,…,H).运行H次,得到聚类成员集P={p1,p2,…,pH}.

1.2 基于质量和差异度的聚类成员选择

聚类成员选择的目的是为了从聚类成员集中选出部分聚类成员组成集成成员集P′={P′1,P′2,…,P′k}.使用适用的成员选择方法,选出差异度大的聚类成员参加聚类集成,能够使聚类集成质量提高.文献[15]设计了一种联合聚类质量和差异度的聚类成员选择方法，该方法使用聚类评价指标对聚类成员进行评价,然后按照评价结果的高低排序,选择出质量好且差异度大的聚类成员参与集成,很好地降低了劣质成员的影响.

其中联合聚类质量和差异度的目标函数为:

SE(Pi)=αQi+(1-α)Di

(1)

式中：α为平衡因子,满足0<α<1,α值默认为0.5;Qi为聚类成员集P中第i个聚类成员的质量；Di为聚类成员集P中第i个聚类成员的的差异度.SE值越大,聚类成员质量越好,差异度越大.

1.3 共识函数设计

共识函数Γ可以定义为RN×H→RN的函数,即将多个聚类成员融合得到最终聚类结果：

Γ:{pi|i∈{1,2,…,H}}→Pf

(2)

文献[16]提出了一种基于谱聚类的聚类集成算法,该方法实现简单,聚类结果稳定,不存在局部极值问题. 聚类成员选择出来的前K个聚类成员形成一个N×K的矩阵P′={P′1,P′2,…,P′k}N×K,两个数据点xi和xj之间的相似性即P′中第i行和第j行的相似性用归一化互信息(normalized mutual information,NMI)方法来评价.

数据点xi和xj之间的相似性矩阵S为:

S=(s(xi,xj))N×K

(3)

式中：s(xi,xj)=NMI(P′(i,:),P′(j,:))

求解拉普拉斯矩阵L的最小特征值(λ1,λ2,…,λk)和对应的特征向量(μ1,μ2,…,μk),将特征向量组成的特征空间用F表示.

F=(μ1,μ2,…,μk)N×K

(4)

谱聚类算法将聚类成员映射到特征向量空间F中,对特征向量空间F使用k-means算法,就能得到最终的聚类结果Pf.

2 SSCES方法

选择性聚类集成研究集中在无监督学习领域,未考虑到现实中用户能通过某些手段或途径收集到数据的少量真实信息,因此文中将半监督信息添加到选择聚类集成中,以提高聚类性能. 具体过程如图1.

图1 SSCES算法流程Fig.1 Algorithm flowchart of SSCES

2.1 半监督信息的添加

受到文献[12]的启发,利用成对约束的方法来指导半监督信息的添加.

定义1Must-link集合M={(xi,xj)},若(xi,xj)∈M,则表明数据xi和xj必属于同类,即xi和xj满足正关联约束关系.

定义2Cannot-link集合C={(xi,xj),若(xi,xj)∈C，则表明数据xi和xj必属于不同类,即xi和xj满足负关联约束关系.

故可用aij来表示样本点i和样本点j之间的相似度:

(5)

即样本点i和j满足Must-link约束aij=1，否则aij=0.

根据公式(5),可以得到包含Must-link约束继续的矩阵M和包含Cannot-link约束信息的矩阵C. 矩阵M和矩阵C的维度与数据集X的相似性矩阵S相同.

加入半监督信息后的相似性矩阵用D表示：

D=S-C+M

(6)

因为矩阵S、M和C的取值范围都在0～1,所以矩阵D的取值范围在-1～2之间,因此需要对矩阵D继续优化. 若两个样本的相似度大于1则必属于同一类,相似度取1即可;若两个样本的相似度小于0,1则必属于不同类,相似度取0即可. 因此用式(7)来优化矩阵D,获得半监督相似性矩阵S′：

(7)

2.2 算法实现

半监督选择性聚类集成算法(表1)实现如下:首先选择简单实用的k-means算法作为基础算法,生成初始聚类集成成员,将结果保存在成员集P中；然后根据联合聚类质量和差异度的选择策略,形成集成成员集P′，利用归一化互信息NMI计算获得相似性矩阵S;接着根据成对约束原理,获得约束信息矩阵M和C;输入相似性矩阵S,得到半监督相似性矩阵S′；最后使用谱聚类算法进行集成,得到最终聚类结果.

表1 半监督选择性聚类集成算法Table 1 Semi-supervised selective clustering ensemble

3 实验

3.1 实验数据集和评价标准

实验中共选用了9组数据集(表2),其中5组UCI数据集,2组手写体图像数据集,2组人脸数据集. 样本数从98～2 500不等,特征数从4～1 024不等,类别数从2～40不等.

表2 实验数据集Table 2 Experimental Data Setse

因为所选的数据集类别标签已知,真实的类别标签可以为各类评价指标使用. 实验采用宏查准率(Mp)和纯度(Pu)两种常见的聚类性能评价指标来判断聚类效果.

宏查准率具体公式为:

(8)

式中：k为数据集的类别数；n为数据集中对象的总数；ai为聚类结果中正确分到第i个类的个数. 显然Mp值越大,聚类结果和真实类别标签越匹配,当聚类结果和真实类别标签一一对应时,Mp值达到最大值1.

纯度是簇中单个类的对象的一种度量方式,反映了算法的簇划分能力．具体公式为:

(9)

式中：B={B1，B2,…,Bk}为聚类子簇集，Bk为聚类子簇集B中第k个子簇；C={C1,C2,…,Ci}为真实类簇集,Ci为真实类簇集C中第i个类别；n为数据集C数据总数；纯度值越接近1,纯度越高,聚类效果越好.

3.2 实验设计

通过实验验证提出的SSCES算法能否取得较好的聚类效果. 实验分为两个部分：第一部分测试所提算法的基本聚类能力,SSCES算法是半监督算法,集成过程中,选择多少带标签的数据参与集成特别重要，文中选取了比例10%～20%的约束信息进行实验；第二部分与其他聚类集成算法进行对比. 对比算法包括:无监督聚类集成算法CSPA、HGPA[6],联合质量和差异度的选择聚类集成算法JPsel[17],半监督聚类集成算法SDPE[11]. 为了实验具有可对比性,实验以k-means算法生成初始聚类成员P={p1,p2,…,pH},作为几种聚类集成算法的输入.

3.3 实验结果

3.3.1 测试算法基本聚类能力

UCI数据集常用来测试聚类算法的聚类效果. 通过测试UCI数据集的5个数据子集:IRIS数据集、lymphography数据集、ZOO数据集、Ionosphere数据集和Segment数据集来表明所提方法的基本聚类能力. 表3为选取10%～20%的有标签数据时,得到的成对约束数量.表4为SSCES算法分别在10%、12%、14%、16%、18%、20%不同比例有标签数据下的Mp值(算法用SSCES1、SSCES2、SSCES3、SSCES4、SSCES5、SSCES6表示). 表5为SSCES算法在不同比例有标签数据下的Pu值.为了更直观的将算法不同比例下的Mp值和Pu值进行比较,将表4和表5中的数据以柱形图的方式,展现在图2和图3中.

从表3、4、5，图2和3可以得到出:

(1) 表3显示随着带标签数据比例的增加,约束信息对的个数也大幅增加,其中负关联约束个数多于正正关联约束对个数

(2) 从表4中可以看出,SSCES算法在实验所选的5个数据集上的最大Mp值超过0.420. 在IRIS、ZOO、Ionosphere、Segment等4个数据集上最大Mp值超过0.620. 表明SSCES算法在这些数据集上能取得较好的聚类效果.从表5可以看出SSCES算法在所选5个数据集上的Pu值均超过0.7, 说明算法得到的子簇内部类别较为单一,算法具有较好的聚类性能.

(3) 从图2可以发现,当半监督比例为10%时,SSCES算法在4个数据集IRIS、lymphography、ZOO、Segment上取得了较高Mp值. 当半监督比例为14%时,SSCES算法在IRIS数据集上取得了较高Mp值. 当半监督比例为20%时,SSCES在数据集Ionosphere上可以取得较高值.

(4) 结合表3和图2,可以发现随着约束信息对的增加,聚类算法在Ionosphere数据集上的Mp值一定值在增加,但在其他数据集上不总是在增加.

综上可以得出,文中所提出的SSCES算法在实验所选的5个UCI数据集上能取得较好的聚类效果,但随着约束信息对的增多,聚类性能不一定得到提升,这可能与过多的负关联约束引起的约束违反有关,当带标签的数据比例为10%时,所获得聚类效果最佳.

表3 SSCES算法获得的约束对Table 3 Constraint pairs obtained by SSCES algorithm

表4 SSCES算法的宏查准率Table 4 Micro-p of SSCES algorithm

表5 SSCES算法的纯度值Table 5 Purity value of SSCES algorithm

图2 宏查准率Fig.2 Micro-p

图3 纯度Fig.3 Purity

3.3.2 与其他聚类算法进行对比

在大容量数据集上进行实验,能更好的验证聚类算法性能. 在大容量数据集USPS、MNIST、ORL和Yale上,将文中提出的算法SSCES与CSPA、HGPA、 JPsel、SDPE进行比较.

表6为大容量数据集上SSCES算法在不同比例参数下的Mp值.从中可以发现当半监督比例参数为10%时,SSCES算法取得了最高Mp值.将表6中SSCES算法的最高Mp值加入到表7中,得到表8，以此验证所提算法的聚类性能.

表6 SSCES算法在大容量数据集上的实验结果Table 6 Results of SSCES algorithm on data sets

表7 其他算法在大容量数据集上的实验结果Table 7 Results of different algorithms on data sets

表8 文中算法与其他算法的结果比较Table 8 Results of SSCES and other different algorithms

同时为了更直观地比较SSCES算法和其他几种聚类算法的Mp值,将表8中不同聚类算法的Mp值以柱形图展示在图4中.

图4 文中算法与其他算法的结果比较Fig.4 Results of SSCES and other different algorithms

观察表8和图4,可以更直观的发现:

(1) 在实验所取得4个大容量数据集上,SSCES、JPsel、SDPE 3种改进算法的Mp值都普遍高于传统的聚类集成算法CSPA和GSPA,在数据集USPS、MNIST、Yale上,SSCES算法取得了最高Mp值. 在数据集ORL上,JPsel算法取得了最高Mp值. 说明SCES算法在这些数据集上有较好的聚类效果,但无法保证一定能提升原有模型的聚类效果.

(2) 从图4可以发现，SSCES的柱状图在大多数数据集上比其他聚类算法更占据优势,且优势较为明显. 说明在加入半监督信息后,半监督选择聚类集成取得了较好的聚类效果.

总体来看,SSCES算法相比较传统的聚类集成算法、选择性聚类集成算法和半监督聚类集成算法更具有优势,在多数组数据集上都获得了最好的聚类结果,因此文中提出的半监督选择聚类集成方法能提高选择性聚类集成的聚类效果.

4 结论

文中在选择性聚类集成算法的基础上,将半监督的信息添加到选择性聚类集成中,提出一种半监督选择性聚类集成方法(SSCES),提高了聚类算法的性能. 实验结果表明,基于成对约束的半监督信息加入的SSCES算法能够改善选择聚类集成算法的表现,在一定条件下,SSCES算法取得的聚类效果优于其他聚类集成算法. 同时实验也显示在某些数据集上,SSCES算法没能取得较高的聚类结果,起到了相反的作用. 如何消除半监督信息添加后带来的消极作用,获得更加优越的结果,将是今后研究的重点.