基于类间相似性的聚类集成方法

2023-11-22张栋超蔡江辉杨海峰郑爱宇

计算机技术与发展 2023年11期

张栋超,蔡江辉,杨海峰,郑爱宇

(太原科技大学计算机科学与技术学院,山西太原 030024)

0 引言

聚类是统计多元分析、数据挖掘和机器学习中的一个重要问题。聚类的目标是将一组对象分组成簇,以便同一簇中的对象与其他簇中的对象高度相似但显著不同。在过去几十年中,已经开发了大量聚类算法,包括分区[1]、分层[2]、基于密度[3]和基于网格[4]的聚类等。但没有一种算法能够处理实践中遇到的所有聚类问题,即无法发现具有不同大小、形状和噪声水平的所有聚类。给定一个数据集,不同的算法通常返回不同的结果。事实上,由具有不同初始化和参数的相同算法返回的聚类结果通常是不同的。因此,用户可能会困惑于选择最合适的方法来解决他们的问题。集成聚类方法已成为克服这一问题的有力工具。

集成聚类是聚类的一个重要分支。聚类集成根据多个聚类结果找到一个最终的数据划分,该划分最大程度地共享了所有基聚类的信息。目前已经开发了几种类型的聚类集成方法,其中基于相似性的聚类集成方法受到很多研究者的青睐。很多学者通过寻找初始对象之间的相似性来构建共协矩阵[5],然后通过该矩阵获得最终聚类划分。

在矩阵元素的相似性计算过程中,大部分研究者将基聚类信息看的同等重要,而原始对象中往往会有一些噪声,导致基聚类结果变差,并影响了最终聚类结果,而且传统的共协矩阵空间复杂度往往是O(n2),在数据量较大时内存占用极大。因此,该文提出了一个基于簇间相似性的聚类集成方法。首先,设计了一种基于证据积累模型的相似度计算方法,将相似度大的样本点暂时划分为小簇;然后,提出一种新的相似度计算方法,将划分好的小簇作为相似矩阵的构成对象,构建相似矩阵;最后,通过对相似矩阵的切图,形成最终的聚类划分。

主要贡献如下:

(1)设计了一种基于证据积累模型的相似性计算方法,有效地将初始对象形成初始簇划分。

(2)提出一种簇间相似性计算方法,用簇来构建相似矩阵,该方法相比直接使用原始对象构建共协矩阵,大大节省了空间复杂度。

1 相关知识

目前,聚类集成有两个重要任务:

(1)如何生成不同的基聚类并保证其多样性;

(2)如何将多个不同的基聚类融合生成最终一致聚类。

第一个任务已经提出了几种不同的方法,大致可以分为以下3类:

(1)使用相同的方法(参数不同)来生成基聚类。比如用k-means作为基聚类器用不同的聚类数来生成聚类集[5];随机选择不同的聚类中心使用k-means[6];使用不同的核参数运行谱聚类算法[7]等;

(2)运行不同类型的聚类算法以生成基本聚类。比如使用多个层次聚类和k-均值生成聚类集[8];将具有不同目标函数的多个聚类算法作为基本聚类,并将聚类集成问题转化为多目标优化问题[9];Yu等人研究了如何整合多种类型的模糊聚类[10]等;

(3)在数据集中的不同子空间或子样本上运行一个或多个聚类算法。比如应用bootstrap方法获得了多个数据子集[11];使用随机映射的方法获得多个特征子空间[12];使用不同的核函数来描述数据[13];结合boosting和bagging的优点,提出一种新的簇集合混合采样方法[14]等。

第二个任务开发了几种类型的聚类集成方法,大致可以分为以下4类:

(1)成对相似性方法。利用所有数据对象两两之间的相似关系来聚合多个聚类。比如Fred和Jain[5]提出了一种基于证据积累的集成算法,并构造了一个相似度矩阵;Iam On等人定义了一个基于链接的相似度矩阵,该矩阵充分考虑了集群之间的相似度[15];Huang等人提出了一种增强的共协矩阵[16],该矩阵能够同时捕获聚类中的对象共现关系以及多尺度集群关系。薛红艳等人[17]以及邵长龙等人[18]用信息熵对共协矩阵加权以达到更好的聚类效果。

(2)基于图的方法。将基础聚类信息表达为一个无向图,通过图划分得到集合聚类。比如Strehl和Ghosh提出了3种超图集成算法[19]:基于聚类的相似性划分算法(CSPA)、超图划分算法(HGPA)和元聚类算法(MCLA)。CSPA创建一个相似图(对象视为顶点,相似度做边)。HGPA构建了一个超图,其中顶点代表对象,而相同的加权超边代表簇。MCLA生成一个图,其中顶点代表聚类,而边的权重反映聚类之间的相似性。Bai等人[20]提出了从基聚类中提取可信度标签,通过聚类的关系构建形成图,最后通过归一化谱聚类获得最终聚类结果。

(3)基于重标记的方法。将基本聚类信息表示为标签向量,然后通过标签对齐聚类。其代表性方法有硬标签对齐和软标签对齐。比如将重标记问题转化为最小成本的一对一分配问题[21];使用交替优化策略来解决软标签对齐问题[22];Rathore等人提出了一个有效的模糊集合框架[23],该框架使用累积一致方案来聚集模糊聚类。

(4)基于特征的聚类方法,将聚类集成问题作为分类数据的聚类。比如整合信息论和遗传算法来寻找最一致的聚类[24];Topchyet 等人提出了一个概率框架[25],并使用EM算法来寻找共识聚类等。

除了以上4种,近年来也有部分学者提出使用加权的方法。与现有的方法不同,笔者研究的对象被指定用k-means算法做基聚类器。首先,对原始对象进行相似度计算,形成多个小簇;然后,用另一种方法计算簇与簇之间的相似度;最后,通过NCUT[26]切图的方式得到最终聚类划分,来实现多弱等于强的目的。

2 文中算法

2.1 相关定义

设X={X1,X2,…,Xn}是对象的集合,其中,

xi={xi1,xi2,…,xid}

d为维度,n为数据对象的个数。聚类集成方法首先要在数据集X上产生M个聚类结果,即:

∏={π1,π2,…,πM}

其中,

πh={Ch1,Ch2,…,Chl}

是第h个基聚类,Chl表示第h个基聚类的第l个簇。该文主要使用的符号如表1所示。

表1 常用符号

2.2 聚类集成方法

(1)

其中,vhl表示第h个基分区中第l个簇的中心点,d(xi,vhl)是目标点(xi)到聚类中心点(vhl)的欧氏距离。

基于证据积累模型,该文提出一个相似度计算方法,用来将相似度高的一些对象预先划分为簇,随后将剩余的相似度较低等异常点进行归并处理。

(2)

相似度量方法如公式(2)所示,其中,

部分对象的基聚类结果如图1所示。

π1π2π3π4π5π6x1111111x2222232x3111111x4111113x5222222x6221222x7333323x8232321

图1中,x1～x8是数据集中的8个对象,π1～π6是6次基聚类结果,表中元素代表x属于第几类。以图1中的对象为例,通过公式(2)计算相似度得知x1与x3的相似度为1,x1与x4相似度为5/6,因此S1={x1,x3,x4}将3个对象划分为1个簇;同理S2={x2,x5,x6},x7,x82个对象与其他对象间相似度较小,因此暂设为异常点S3={x7},S4={x8}。该过程每个对象只经过1次运算,其时间复杂度为O(N)。使用数据集(S)设置得到以下相似矩阵,如图2所示。

2）激励机制缺乏。虽然我国已对绿色建筑提出了各类政策，但建设单位对绿色建筑的落实的积极性不高，难以推动绿色建筑的发展。例如，政府虽然制定了鼓励绿色建筑发展的各项策略，但是由于成本及运营维护等方面的经济与技术问题的制约，导致其激励作用难以发挥，使建设单位及施工方的积极性不高[2]。

S1S2S3S4S111/271/181/9S211/97/18S311/2S41

簇间相似度计算如公式(3)所示,其中p,q为簇(S)中对象的个数。

(3)

其中,

接着以图1为例,S1={x1,x3,x4},S4={x8}。x1和x8在π6同属一类,x3和x8在π6同属一类,所以按公式(3)所得,S1和S4的相似度为2/(1×3×6)=1/9,其余相似度同理可得。该过程的时间复杂度为O(pqTN),qpT

3 实验结果与分析

3.1 实验数据集

该方法在8个数据集上进行了测试,其中4个是合成的数据集,4个是真实的数据集,合成数据集可从https://github.com/deric/clustering下载,真实数据集为UCI,其下载地址也在下方给出(http://www.ics.uci.edu/mlearn/MLRepository.html)。这8个数据集的详细说明如表2所示:数据对象数(N)、维度数(D)、集群数(K)。

表2 数据集描述

3.2 评价标准

采用CA和NMI来衡量聚类结果与真实数据分区之间的相似性。

(4)

CA是通过计算错误率来衡量聚类结果的另一个外部标准。

(5)

3.3 对比实验

为了正确检验所提算法的性能,将其与以下几种经典的聚类集成算法进行了比较。这些比较算法的代码是开放的和可访问的。选择了基于链接的相似性方法和基于图的集成方法。

基于链路的相似性方法:由Iam On等人提出的[15]加权链接三元组(WCT),加权三重质量(WTQ),组合相似性度量(CSM)。

表3和表4分别展示了不同算法在8个数据集上的CA和NMI结果,每列最好的结果进行了加粗显示。

表3 不同方法在8个不同数据集的CA结果

表4 不同方法在8个不同数据集的NMI结果

3.4 时间效率分析

在这部分,将分析文中算法与对比算法的时间效率。选用KDD-CUP’99数据集进行本次时间效率分析,该数据集共有500万条数据,41个特征,从中选取了一部分进行时间效率分析实验。选用基于链接的聚类集成算法(WCT)、基于图的聚类集成算法(CSPA)与CSCE进行比较,参数设置与对比实验部分相同。不断增加数据集,记录不同算法的运行时间,结果如图3所示。其中X轴为对象数量,Y轴为运行时间(s)。从实验结果可以看出,与其他算法相比,文中算法非常有效。这表明CSCE在对大规模数据集进行聚类时有很好的效果。