白亮,高锦

(山西大学 计算机与信息技术学院,山西 太原 030006)

0 引言

聚类分析是挖掘数据内部结构特征的一个重要的工具,在机器学习、数据挖掘、模式识别等领域有着重要的作用[1]。它与分类的情况不同,是一种无监督的学习,依据无标记对象的相似性对其进行分组,使得划分在同一组中的数据对象尽可能地相似,而与其他组中的数据对象尽可能地相异。

聚类集成[2]是利用集成学习思想,通过合并数据集的多个聚类划分结果,得到一个新的聚类结果,从而提高聚类结果的鲁棒性[3]。聚类集成有两个主要任务:基聚类的生成和一致性函数的设计[4]。目前产生基聚类的方法主要有:(1)使用不同的聚类算法,文献[3]中Gionis等人对同一个数据集使用Single-Link,Complete-Link,Average-Link,K-means等算法对数据集进行处理,生成具有差异度的聚类成员;(2)将数据集的特征空间投射到数据子空间,如Bagging算法;(3)同一个聚类方法设置不同的参数和随机初始化,如K-means算法设置不同的初始中心点。目前存在的一致性函数设计的方法有:(1)基于成对相似性的方法[5-7],文献[5]中Fred等最早提出了基于共协关系矩阵的EAC算法,将该矩阵作为层次聚类算法的输入得到最终聚类结果;(2)基于超图分割的方法[6],文献[6]中Strehl等人将聚类集成中的每一个簇视作一条超边,构造得到一个超图结构,进而用分割算法将其分割为若干块,以得到最终聚类结果;(3)基于特征的方法等[8-11],它是把聚类集成问题转化为分类数据的聚类问题,基聚类中的簇用于表示数据点对象的特征,最后得到统一聚类的结果。

虽然已有研究者提出了一些加权聚类集成的方法,但这些方法往往在集成效果和运算效率上仍有局限性[12],容易受低质量聚类成员的负面影响,并缺乏对聚类成员可靠度的估计。由于聚类集成中个体学习器的准确性和它们之间的差异性是影响集成结果的两个重要因素,所以为了生成具有差异度的聚类成员,在实验中K-Means算法采用随机选择k个数据对象作为初始聚类中心的方式进行聚类,并产生具有差异度的基聚类成员。我们采用聚类指标来度量个体学习器的准确性和差异性,因此提出利用现有的聚类有效性和集体差异性指标融合成一个新的评价指标,我们用这个评价指标对基聚类结果进行评估,并计算在该指标下产生的权值作为其集成的权重。我们通过加权的方式改变了各个聚类成员对集成结果的作用,加强了有利的因素减少了不利因素的影响。

1 相关知识

1.1 背景介绍

2 基聚类结果的加权方式

2.1 聚类准则的融合

根据现有的评价指标,我们给出融合后的新评价指标定义如下:

π(Pm)=π1(Pm)π2(Pm),

(1)

其中,π1(Pm)为基聚类结果Pm在有效性评价指标下的评价值,π2(Pm)为基聚类结果Pm在差异性评价指标下的评价值。

具有代表性的聚类有效性指标包括DBI[13](Davies-Bouldin validity index),Hubert[14](Modified Hubert index),DVI[15](Dunn validity index),CH[16](Calinski-Harabasz index),MB[17](Maulik-Bandyopadhyay index),SF[18](Saitta-Smith index),SI[19](Silhouette index),其中,DBI指标的值越小,表示聚类结果越好,指标Γ,DVI,CH,MB,SF,SI的值越大,表明该聚类结果的类内结构较为紧密,并且其类间距较大,在实验的过程中DBI的值取其倒数。

具有代表性的聚类差异性指标包括NMI[6](Normalized Mutual Information),ARI[20](Adjusted Rand Index),CA[21](Classification Accuracy),JC[22](Jaccard Index),其中NMI,ARI,CA,JC的值越大,则表示基聚类结果之间的差异性越大。

我们把上述介绍的聚类有效性指标和差异性指标进行融合,从而得到新的评价指标π。

(2)

本文提出的权重设计方法是在基聚类整体准确度的前提下,增加了不同聚类结果之间的差异性而形成的。因此根据这个方法设计的权重能更加有利于对集成贡献度较大的基聚类,最终有助于得到更好的集成聚类结果。

2.2 加权相似性矩阵

对于每一个基聚类成员划分Pm都对应着一个隶属矩阵Hm={0,1}N×Km,其中Km是基聚类成员Pm的聚类划分的类个数。在这个隶属矩阵Hm中的行向量代表数据对象,列向量代表数据对象是否属于该列代表的类簇。如果数据对象属于这个簇时,则用1表示;否则用0表示。根据矩阵Hm可以产生数据对象间的相似性矩阵Sm={0,1}N×N,定义如下所示:

(3)

其中Sm中的每个元素(Sm)ij表示矩阵Hm中的i行和j行的数据对象是否属于同一个簇。如果元素(Sm)ij=1,则表示数据对象i和数据对象j被划分到同一个簇中。

(4)

加权的相似性矩阵Sπ刻画了基聚类矩阵P对于所有数据对象在新评价准则π下的基聚类成员Pm之间的关系,一个加权的相似性矩阵是对不同的基聚类成员不同的对待,因此往往是一系列聚类结果评估的证据累积。

Fig.1 Framework of the proposed algorithm图1 算法框架

3 加权聚类集成算法

基于聚类准则融合,本文提出一种加权聚类集成算法,主要分为3个阶段:第1阶段首先在数据集上多次执行K-Means聚类算法产生一系列基聚类结果构成基聚类矩阵P;第2阶段利用融合的评价准则π对基聚类矩阵P进行有效性评估并作为权值,得到一个融合的加权相似性矩阵Sπ;第3阶段对融合的加权相似性矩阵Sπ用Average-link聚类算法进行聚类得到最终的聚类结果。算法的框架示意图如图1所示。

4 实验分析

4.1 实验数据

为了验证本文提出算法的有效性,从UCI真实数据集中分别选取了不同的数据集进行了测试。数据集的信息描述如表1所示。

表1 数据集描述Table 1 Description of UCI Data sets

4.2 评价指标

本文采用F1值[24](F-Measure)对聚类集成结果进行评价,其定义如下:

(5)

4.3 实验结果分析

在实验中,K-Means算法采用随机选择k个数据对象作为初始聚类中心的方式，进行聚类生成具有差异度的聚类成员,并在每个数据集上产生一聚类矩阵,最后实验结果的F1值是在每个数据集上运行了20次实验结果的平均值。每个数据集上不同方法的最优值用黑色粗体进行标识。

我们在UCI数据集上测试了7个真实数据集,不同有效性指标和差异性指标相互融合成新指标下的加权聚类集成的实验结果如表2所示。通过表2中的实验结果可知,我们选用的4个差异性指标在与不同的有效性指标进行融合时,其给出的实验结果大致相同,所以本文选择NMI指标作为提出算法的差异性指标。在实验中可以看出，有效性指标Hubert,MB,SF与差异性指标NMI融合后的实验效果是大致相同的;指标DBI,DVI,CH,SI与差异性指标NMI融合的实验结果也大致相同,并优于与指标Hubert,MB,SF之间相结合的实验结果。

表2 不同指标下的F1值比较Table 2 Clustering Results of Proposed Algorithms with Respect to F1

在实验中,我们观察到有效性指标MB,SF在数据集Glass,Wine中的RE值较低。以及SI,DBI指标在数据集Image Segmentation中的RE值也比较低,由于SI，DBI不适合处理差异性较大的聚类结果,所以它们在表2中数据集Image Segmentation,Glass,Wine上的F1值也相较于其它数据集上的集成效果没有优势,但它们的PE值都是比较高的。而指标SI在数据集Wine,Seeds中的PE,RE,F1值都比较高,是由于SI指标适合具有最佳聚类划分的基聚类结果。所以它们相结合地指标在这两个数据集上都可以得到较好的集成聚类结果。Hubert指标适合数据分布较为特殊的结构,比如流形分布的数据,所以Hubert指标在表2中数据集Seeds,WDBC,Iris上的集成效果不是很理想。

从表2不同指标下的实验结果中分析出在差异性指标NMI分别和DVI,CH有效性指标相结合下的PE,RE,F1值在所有的数据集上都有较好的集成效果,所以我们选用它们其中具有最好集成效果的CH和NMI指标相融合作为新的评价准则,对基聚类矩阵进行有效性评估并给出相应的权值,然后进行加权聚类集成。

本文提出的加权聚类集成算法和其它的集成聚类方法进行了实验分析比较,CSPA[6]、MCLA[6]、HGPA[6]、Voting[10]、W-voting[10]、Sel-w-voting[10],其实验结果如表3所示。从表3中可以看出本文提出的加权聚类集成算法的F1值和其他算法相比较几乎是最优的,并且在实验中本文提出的基于指标融合的加权聚类集成算法的聚类精确率和回收率也是优于其他算法的。

5 结束语

本文提出了基于聚类准则融合的加权聚类集成算法,是利用现有的聚类指标产生新的评价准则对基聚类结果进行评估加权,进而通过层次聚类方法集成得到最终的聚类结果。在UCI真实数据集上与已有的聚类集成算法相比较,实验结果表明本文提出的算法可以获得较好的聚类集成结果。

参考文献：

[1] 陈新泉,周灵晶,刘耀中.聚类算法研究综述[J].集成技术,2017(3):41-49.

[2] 杨草原,刘大有,杨博,等.聚类集成方法研究[J].计算机科学,2011,38(2):166-170.DOI: 10.3969/j.issn.1002-137X.2011.02.038.

[3] Gionis A,Mannila H,Tsaparas P.Clustering Aggregation[J].AcmTransactionsonKnowledgeDiscoveryfromData,2005,1(1):341-352.DOI:10.1109/ICDE.2005.34.

[4] Ghosh J,Acharya A.Cluster Ensembles[J].WileyInterdisciplinaryReviews:DataMiningandKnowledgeDiscovery,2011,1(4):305-315.DOI:10.1002/widm.32.

[5] Fred A L,Jain A K.Combining Multiple Clusterings using Evidence Accumulation[J].IEEETransonPatternAnalysisandMachineIntelligence,2005,27(6):835-850.DOI:10.1109/TPAMI.2005.113.

[6] Strehl A,Ghosh J.Cluster Ensembles:A Knowledge Reuse Framework for Combining Multiple Partitions[J].JournalofMachineLearningResearch,2002,3:583-617.DOI:10.1162/153244303321897735.

[7] Topchy A,Jain A K,Punch W.Clustering Ensembles:Models of Consensus and Weak Partitions[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2005,27(12):1866-1811.DOI:10.1109/TPAMI.2005.237.

[8] Dudoit S,Fridlyand J.Bagging to Improve the Accuracy of a Clustering Procedure[J].Bioinformatics,2003,19(9):1090-9.DOI:10.1093/bioinformatics/btg038.

[9] Topchy A P,Law M H C,Jain A K,etal.Analysis of Consensus Partition in Cluster Ensemble[C]∥IEEE International Conference on Data Mining.2004:225-232.DOI:10.1109/ICDM.2004.10100.

[10] 唐伟,周志华.基于Bagging的选择性聚类集成[J].软件学报 2005,16(4):496-502.

[11] 黄建宇,周爱武,肖云,等.基于特征空间的文本聚类[J].计算机技术与发展,2017,27(8):75-77.

[12] 黄栋,王昌栋,赖剑煌,等.基于决策加权的聚类集成算法[J].智能系统学报,2016,11(3):418-425.

[13] Davies D L,Bouldin D W.A Cluster Separation Measure[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,1979,1(2):224-7.DOI:10.1109/TPAMI.1979.4766909.

[14] 洪志令,姜青山,董槐林.模糊聚类中判别聚类有效性的新指标[C]∥中国数据库学术会议.2004:121-125.

[15] Halkidi M,Batistakis Y,Vazirgiannis M.On Clustering Validation Techniques[J].JournalofIntelligentInformationSystems,2001,17(2):107-145.DOI:10.1023/A:1012801612483.

[17] Maulik U,Bandyopadhyay S.Performance Evaluation of Some Clustering Algorithms and Validity Indices[J].IEEETransactionsonPatternAnalysis&MachineIntelligence,2002,24(12):1650-1654.DOI:10.1109/TPAMI.2002.1114856.

[18] Saitta S,Raphael B,Smith I F C.A Comprehensive Validity Index for Clustering[J].IntelligentDataAnalysis,2008,12(6):529-548.

[19] Kaufman L,Rousseeuw P J.Finding Groups in Data:An Introduction to Cluster Analysis [M].DBLP,1990.DOI:10.1002/9780470316801.

[20] Hubert L,Arabie P.Comparing Partitions[J].JournaofClassification,1985,2(1):193-218.DOI:10.1007/BF01908075.

[21] Anguelov D,Gavrilov M,Indyk P,etal.Mining the Stock Market:Which Measure is Best[C]∥6 Th Acm Intl Conference on Knowledge Discovery & Data Mining,2000:487-496.DOI:10.1145/347090.347189.

[22] Halkidi M,Batistakis Y,Vazirgiannis M.On Clustering Validation Techniques[J].JournalofIntelligentInformationSystems,2001,17(2):107-145.DOI:10.1023/A:1012801612483.

[23] Yang Y,Chen K.Temporal Data Clustering via Weighted Clustering Ensemble with Different Representations[J].IEEETransactionsonKnowledge&DataEngineering,2011,23(2):307-320.DOI:10.1109/TKDE.2010.112.

[24] 孙爱香,杨鑫华.关于文本聚类有效性评价的研究[J].山东理工大学学报(自然科学版),2007,21(5):65-68.

[25] Liang J,Bai L,Dang C,etal.The-Means-Type Algorithms Versus Imbalanced Data Distributions[J].FuzzySystemsIEEETransactionson,2012,20(4):728-745.DOI:10.1109/TFUZZ.2011.2182354.