杜淑穎 ,丁世飛 ,邵長龍

（1.中國礦業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院，徐州，221116；2.徐州生物工程職業(yè)技術(shù)學(xué)院信息管理學(xué)院，徐州，221000）

聚類是數(shù)據(jù)挖掘領(lǐng)域中熱門的研究課題之一，其研究目的是根據(jù)相似性的大小把數(shù)據(jù)分到不同的簇中，使簇內(nèi)數(shù)據(jù)之間的相似性盡可能大，簇間數(shù)據(jù)之間的相似性盡可能小［1］.目前聚類已被運用在各種領(lǐng)域，如圖像處理［2］、社區(qū)發(fā)現(xiàn)［3］、數(shù)據(jù)挖掘等等［4］.過去幾十年中，人們開發(fā)了大量的聚類算法，比較具有代表性的有譜聚類［5-6］、密度峰值聚類［7-8］、自適應(yīng)聚類等［9-10］，每種聚類算法都有其自身的優(yōu)點.但目前的聚類算法仍然存在一些問題，如聚類結(jié)果很大程度上取決于參數(shù)及其初始化、聚類結(jié)果不夠穩(wěn)健等.為了解決這些問題，研究者提出了聚類集成算法.

與通常使用單個算法生成單個聚類結(jié)果的傳統(tǒng)做法不同，聚類集成是整合多個不同的聚類結(jié)果來生成更好更穩(wěn)健聚類結(jié)果的過程.聚類集成算法的有效性使其越來越受到關(guān)注，許多相關(guān)算法被提出.這些算法可分為三大類，即基于共關(guān)聯(lián)矩陣的算法、基于圖分區(qū)的算法和基于中值聚類的算法.

基于共關(guān)聯(lián)矩陣的算法根據(jù)數(shù)據(jù)點與數(shù)據(jù)點之間在相同簇中共現(xiàn)的頻率得到一個共關(guān)聯(lián)矩陣，以該矩陣作為相似度矩陣，采用層次聚類的算法得到最終結(jié)果.Fred and Jain［11］首次提出共關(guān)聯(lián)矩陣的概念，并據(jù)此設(shè)計了證據(jù)集聚聚類（Evidence Accumulate Clustering，EAC）算法.Wang et al［12］對EAC 算法進行擴展，考慮到簇的大小，提出概率集聚算法.Rathore et al［13］利用隨機投影對高維數(shù)據(jù)進行降維，并利用共關(guān)聯(lián)矩陣設(shè)計了一種針對于模糊聚類的聚類集成算法.Zhong et al［14］認(rèn)為刪除共關(guān)聯(lián)矩陣值較小的項可以提高聚類效果，并猜想哪些項中可能包含大量噪聲.

基于圖分區(qū)的算法將聚類集成的信息構(gòu)成一個圖結(jié)構(gòu)，再利用圖分割算法將圖分割成若干塊，進而得到最終的聚類結(jié)果.Strehl and Ghosh［15］將聚類成員里的每個簇都作為一個超邊緣，構(gòu)造了三種超圖結(jié)構(gòu)，再用METIS 算法對其進行圖分割，得到最終的聚類結(jié)果.Fern and Brodley［16］將聚類成員構(gòu)造成二部圖，其中對象和簇都表示為圖節(jié)點，只有當(dāng)其中一個節(jié)點是對象，另一個節(jié)點是包含它的簇時，二部圖的值才不為0，并用Ncut算法對其進行分割.Huang et al［17］提出一種針對大規(guī)模數(shù)據(jù)的基于采樣的譜聚類算法，并設(shè)計了一個二部圖對其進行聚類集成.

基于中值聚類的算法將聚類集成問題建模成一個最優(yōu)化問題，其優(yōu)化目標(biāo)是尋找一個與所有聚類成員最相似的聚類結(jié)果，這個聚類結(jié)果被視為所有聚類成員的中值點.這個問題已經(jīng)被證明是一個NP 難問題，所以在全局聚類空間里尋找最優(yōu)解在較大的數(shù)據(jù)集上是不可行的.為此，Cristofor and Simovici［18］利用遺傳算法求聚類集成的近似解，其中聚類被視為染色體.Topchy et al［19］將中值聚類問題轉(zhuǎn)化為極大似然問題，并用EM（Expectation Maximization）算法求解.Huang et al［20］將聚類集成問題轉(zhuǎn)化為二元線性規(guī)劃問題，通過因子圖模型進行求解.

盡管取得了重大的進展，但目前的研究仍然存在兩個挑戰(zhàn)性問題：首先，目前的算法大多是在對象級別對集成信息進行研究，往往無法從簇的層面集成更多的信息；其次，多數(shù)聚類集成算法僅僅關(guān)注了聚類成員的直接連接，忽略了聚類成員的間接連接.

在聚類集成的過程中，對象間的直接共現(xiàn)是最容易捕捉的信息，F(xiàn)red and Jain［11］提出共關(guān)聯(lián)矩陣的概念，用兩個對象在同一簇中共現(xiàn)的次數(shù)作為它們的相似度.但是現(xiàn)實情況遠(yuǎn)比此更復(fù)雜，圖1 列出了幾種可能出現(xiàn)的情況.

圖1a 中，兩個對象在同一簇內(nèi)，則這兩個對象可以被認(rèn)為是同一類.圖1b 中，兩個對象分屬于兩個有公共部分的簇，可以用Jaccard 系數(shù)計算兩個簇之間的相似度，這兩個對象也被認(rèn)為有一定的可能性在同一類中.圖1c 中，兩個對象分屬于兩個不相連的簇，但這兩個簇均與第三個簇有聯(lián)系，這種簇間間接相連的情況，很難度量這兩個簇之間的相似性，也很難對這兩個對象進行分類，這就需要對隱藏在簇間的間接關(guān)系進行發(fā)掘利用.針對這個問題，本文提出一種基于簇間連接的元聚類集成算法（Link-Based Meta-Clustering Algorithm，L-MCLA）.

1 相關(guān)工作

1.1 聚類集成聚類集成是通過整合多個聚類結(jié)果來提高聚類效果的算法，通?？梢员硎鋈缦?

給定一個具有n個數(shù)據(jù)對象的數(shù)據(jù)集X={x1，x2，…，xn}，對此數(shù)據(jù)集X使用m次聚類算法，得到m個聚類結(jié)果P={p1，p2，…，pm}，其中，pi(i=1，2，…，m)為第i個聚類算法得到的聚類結(jié)果，又被稱為聚類成員或基聚類.具體地，聚類成員的生成有三種算法：

（1）使用一種聚類算法，每次運行時隨機設(shè)置不同的參數(shù)并隨機初始化.（2）使用不同聚類算法產(chǎn)生不同的聚類成員.（3）對數(shù)據(jù)集進行采樣，得到不同的子集，再對子集進行聚類，得到不同的聚類成員.

每個聚類成員包含若干個簇，記作pi=，其中，j是聚類成員pi里包含簇的個數(shù).聚類集成就是對集合P通過一致性函數(shù)T進行合并，得到數(shù)據(jù)集X的最終聚類結(jié)果P*.聚類集成的具體流程如圖2 所示.

圖2 聚類集成流程示意圖Fig.2 The flowchart of clustering ensemble

1.2 元聚類2003 年，Strehl and Ghosh［15］提出被稱為“元聚類”（Meta-Clustering Algorithm，MCLA）的聚類集成算法，其中心思想是對簇進行分類，而不是對對象進行分類，最后，將對象分配到最有可能歸屬的簇群中.元聚類算法利用Jaccard 系數(shù)計算簇間的相似度，假設(shè)有簇Ci和Cj，它們之間的Jaccard 系數(shù)的計算如下：

其中，| |代表集合中點的個數(shù).

接著，元聚類算法對得到的相似度矩陣?yán)肕ETIS 圖劃分進行分類.METIS 是一種多級的快速圖分割技術(shù)，在元聚類算法里利用它將簇分成若干個簇群［21］，每個簇群被稱作元簇群（Meta-Cluster，MC）.最后，將對象分配到對應(yīng)的元簇群，得到聚類結(jié)果.元聚類算法的四個步驟如下.

（1）構(gòu)造相似度矩陣：將M個聚類成員包含的全部簇都當(dāng)作矩陣節(jié)點，計算簇和簇之間的Jaccard 系數(shù)作為矩陣的值，構(gòu)造相似度矩陣.

（2）生成元圖：將矩陣節(jié)點當(dāng)作圖節(jié)點，將矩陣的值當(dāng)作圖的邊，將上一步的相似度矩陣看作一個無向圖，稱為元圖（Meta-graph）.

（3）劃分元圖：使用METIS 圖劃分算法對上一步的元圖進行劃分，得到K個元簇群，每個元簇群都包含若干簇.

（4）對象分配：將數(shù)據(jù)對象分配到對應(yīng)的元簇群得到最終結(jié)果.具體地，基于投票法，將對象從屬于元簇群中簇的次數(shù)與元簇群中簇的總個數(shù)的比看作對象從屬于這個元簇群的可能性.對于一個對象，將它分配到可能性最大的元簇群中，進而得到最終結(jié)果.

Strehl and Ghosh［15］用一系列實驗證明了元聚類算法的優(yōu)越性和魯棒性，使其成為一個經(jīng)典的聚類集成算法.

1.3 連接三元組元聚類算法雖然優(yōu)越，但仍有一個缺點，就是利用Jaccard 相似度來構(gòu)建的相似度矩陣僅僅能反映簇與簇之間的直接聯(lián)系，無法進一步挖掘其中的間接關(guān)系.對于那些沒有公共部分的簇，它們的相似度只能為0，忽略了它們之間的弱聯(lián)系性.

2011 年，Iam-On et al［22］提出加權(quán)連接三元組（Weighted Connected-Triple，WCT）的概念來挖掘簇與簇之間隱藏的間接關(guān)系，其基本思想是：如果兩個節(jié)點都與第三個節(jié)點有連接，則認(rèn)為這兩個節(jié)點之間也有一定的關(guān)系，第三個節(jié)點被稱為這個三元組的中心.通過這種算法可以找到簇與簇之間的間接連接，進一步豐富原來的相似度矩陣包含的信息，進而得到更好的聚類結(jié)果.

連接三元組因為其較好的特性被運用在許多研究中.周林等［23］將連接三元組運用在譜聚類中，提出一種基于譜聚類的聚類集成算法.張恒山等［24］將其與群體智慧相結(jié)合，提出一種新的聚類集成算法.證明使用連接三元組可以有效地挖掘簇之間隱藏的信息，有利于提高聚類結(jié)果.

2 L-MCLA 算法

2.1 構(gòu)建相似性矩陣本節(jié)利用連接三元組（如圖3 所示）來構(gòu)建細(xì)化的簇相似性矩陣.

圖3 連接三元組的示意圖Fig.3 The schematic diagram of connecting triples

首先，用Jaccard 系數(shù)計算簇與簇之間的相似度，如式（1）所示.

設(shè)Ck與Ci和Cj都有相似度，則Ci和Cj之間的連接三元組定義如下：

簇Ci，Cj之間的相似度SimWCT(i，j)計算如下：

其中，C是簇的總集合.

對于簇集合C中任意的兩個簇Ci和Cj，它們之間的相似度可以定義為：

其中，DC為衰減因子，即為兩個不同事物的相似程度的置信水平.

通過式（4）可以構(gòu)建一個信息更豐富的簇相似度矩陣，有利于后面得到更好的結(jié)果.

2.2 一致性函數(shù)一致性函數(shù)包含圖劃分和對象分配兩個步驟.首先，將優(yōu)化后的相似度矩陣S視為鄰接矩陣，構(gòu)建一個無向圖G，即：

其中，V=C，將全部的簇看作圖像中的點.L=Sim(i，j)，將簇之間的相似度看作無向圖的邊，這樣就構(gòu)建了一個無向圖.

然后，將這個無向圖G通過圖分區(qū)算法分為K個部分.在圖分區(qū)算法的選擇中，由于歸一化割（Normalized Cut，Ncut）［25］的優(yōu)越特性，本研究選擇它作為圖分區(qū)算法.

通過Ncut 可以得到K個元簇群，每個元簇群都由若干個簇構(gòu)成.即：

接著，使用投票法將對象分配到對應(yīng)的元簇群中.對于給定的一個對象xi，xi可能屬于MCj中的零個或多個簇，即可以用對象xi從屬于MCj中簇的次數(shù)與MCj中簇的總個數(shù)的比來定義xi屬于元簇群MCj的可能性.具體地：

其中，|MCj|代表元簇群MCj中 簇的個數(shù).

對MC中的每個元簇群MCj求得一個分?jǐn)?shù)，將點xi分配到得分最高的元簇群里，完成對象分配.

L-MCLA 算法描述如下.

2.3 算法的復(fù)雜度分析首先看時間復(fù)雜度.因為第一步生成聚類成員的時間復(fù)雜度與基聚類算法有關(guān)，在此不做分析.第二步生成相似度矩陣Z的時間復(fù)雜度為O()，其中，NC為聚類成員包含的簇的總數(shù).第三步用連接三元組對相似度矩陣Z進行細(xì)化，時間復(fù)雜度是O()，其中，m為聚類成員的規(guī)模.第四步將相似度矩陣WCTZ看作一個無向圖G，無向圖G包含2NC個節(jié)點，使用Ncut 算法進行分割的時間復(fù)雜度是，其中，K是圖分割的塊數(shù).第五步對對象進行分配，時間復(fù)雜度是O(KNNC)，其中，N為對象個數(shù).所以，本文算法的總的時間復(fù)雜度最大為：

生成相似度矩陣的空間復(fù)雜度為O()，這也是本文算法空間復(fù)雜度的主要來源，其余步驟所占空間遠(yuǎn)小于這個值.故可以認(rèn)為本文算法的空間復(fù)雜度為O().

3 實驗結(jié)果與分析

在多個實際數(shù)據(jù)集中與現(xiàn)有的聚類集成算法進行對比實驗來驗證本文算法的有效性，并通過對不同聚類成員規(guī)模的比較來證明本文算法的魯棒性.

3.1 數(shù)據(jù)集和評價標(biāo)準(zhǔn)使用UCI（University of California Irvine）機器學(xué)習(xí)數(shù)據(jù)庫中的八個數(shù)據(jù)集為實驗數(shù)據(jù)集進行對比實驗.表1 列出了數(shù)據(jù)集的詳細(xì)信息.

選擇ARI（Adjusted Rand Index）和NMI（Normalized Mutual Information）來評價聚類結(jié)果.

ARI通過計算樣本點對位于同一類簇和不同類簇的數(shù)目來度量聚類結(jié)果之間的相似程度，計算如下：

其中，a表示在真實情況下和實驗中都屬于一個簇的點對數(shù)目，b表示在真實情況下是一個簇而在實驗中不是一個簇的點對數(shù)目，c表示在真實情況下不是一個簇而在實驗中是一個簇的點對數(shù)目，d表示在真實情況下和實驗中都不屬于同一個簇的點對數(shù)目.ARI的取值范圍為[-1，1]，值越大表明和真實結(jié)果越吻合，即聚類效果更好.

NMI是常見的聚類有效性的外部評價指標(biāo)，從信息論的角度評估兩個聚類結(jié)果的相似性.設(shè)實驗結(jié)果為X，真實結(jié)果為Y，NMI的計算如下：

其中，I(X，Y)表示X和Y之間的互信息，H(X)和H(Y)表示變量X和Y的熵.NMI的取值范圍為[0，1]，值越大表明和真實結(jié)果的共享信息越多，即聚類效果越好.

3.2 對比實驗和實驗設(shè)置使用七種聚類集成算法與L-MCLA 算法作對比：EAC（Evidence Accumulation Clustering）［11］，HBGF（Hybird Bipartite Graph Formulation）［16］，WEAC（Weighted Evidence Accumulation Clustering）［26］，GP-MGLA（Graph Partitioning with Multi-Granularity Link Analysis）［26］，CSPA（Cluster-Based Similarity Partitioning Algorithm）［15］，HGPA（Hypergraph Partitioning Algorithm）［15］，MCLA（Meta-Clustering Algorithm）［15］

對比算法的選擇，首先是本文改進的元聚類算法MCLA 以及與其相關(guān)的CSPA，HGPA，還有聚類集成領(lǐng)域的經(jīng)典算法EAC，HBGF 以及近年來的新算法WEAC，GP-MGLA，這些對比算法使實驗結(jié)果具有一定的說服力.對比算法的參數(shù)按文獻給出的參考值進行設(shè)置.

實驗環(huán)境：Windows 7 64 位操作系統(tǒng)，英特爾i5 雙核 1.7 GHz 中央處理器，8 G 內(nèi)存，在MATLAB R2016a 中實現(xiàn).

實驗中首先要生成包含m個聚類成員的聚類集合，使用k-means 算法生成聚類成員，每個聚類成員的生成均采用隨機初始化，并在中隨機選取k-means 的聚類個數(shù)k.稱聚類成員個數(shù)m為聚類集成規(guī)模，固定聚類集成規(guī)模m=50，分別將本文算法與其他聚類集成算法進行比較，再在不同聚類集成規(guī)模下測試本文算法的聚類表現(xiàn).

3.3 聚類集成算法的對比實驗在每個數(shù)據(jù)集中每個聚類集成算法均運行20 次，每次運行根據(jù)3.2 隨機生成聚類成員，得到聚類結(jié)果后計算ARI和NMI的均值及其標(biāo)準(zhǔn)差.實驗結(jié)果如表2和表3 所示，表中黑體字表示結(jié)果最優(yōu).

表2 不同算法的聚類結(jié)果的ARI 比較Table 2 ARI of clustering results by different algorithms

表3 不同算法的聚類結(jié)果的NMI 比較Table 3 NMI of clustering results by different algorithms

由表2 可見，L-MCLA 算法在八個數(shù)據(jù)集上的聚類結(jié)果的ARI都是最高的.由表3 可見，LMCLA 算法在六個數(shù)據(jù)集上聚類結(jié)果的NMI也都是最高的，僅僅在CTG 和Ionosphere 上略有遜色，不過數(shù)值相差不大.

通過以上實驗可以證明，本文提出的算法在聚類集成上的優(yōu)勢，和其他的聚類集成算法相比，性能更優(yōu).

3.4 聚類集成規(guī)模對聚類結(jié)果的影響研究不同的聚類集成規(guī)模對L-MCLA 算法聚類結(jié)果的影響.在八個數(shù)據(jù)集上取不同數(shù)量的聚類成員進行集成.聚類成員規(guī)模為[10，100]，以10 遞增.聚類成員的生成設(shè)置與3.2 相同，取10 次實驗結(jié)果的平均值作為最終的結(jié)果.圖4 和圖5 顯示了在不同聚類集成規(guī)模下L-MCLA 算法的ARI和NMI的變化情況.

圖4 當(dāng)聚類集成規(guī)模不同時L-MCLA 算法在八個數(shù)據(jù)集上的ARIFig.4 ARI of L-MCLA on eight datasets with different scales of the clustering ensemble

圖5 當(dāng)聚類集成規(guī)模不同時L-MCLA 算法在八個數(shù)據(jù)集上的NMIFig.5 NMI of L-MCLA on eight datasets with different scales of the clustering ensemble

圖4 展示了在聚類集成規(guī)模不同時，LMCLA 算法在八個數(shù)據(jù)集上聚類結(jié)果的ARI.由圖可見，在大部分?jǐn)?shù)據(jù)集上，L-MCLA 算法的聚類結(jié)果僅有小幅波動，并在集成規(guī)模達到40 以后逐漸趨于平穩(wěn)，只在Thyroid 數(shù)據(jù)集和Soybean 數(shù)據(jù)集上存在不同.在Thyroid 數(shù)據(jù)集上，L-MCLA算法的聚類結(jié)果的ARI在集成規(guī)模為10～20 時急劇上升，隨后，隨著聚類成員的增加呈現(xiàn)一種波動上升的狀態(tài).在Soybean 數(shù)據(jù)集上，隨著基聚類的增多，L-MCLA 算法的聚類結(jié)果的ARI緩慢下降，但幅度較小.

圖5 展示了在聚類集成規(guī)模不同時，LMCLA 算法在八個數(shù)據(jù)集上聚類結(jié)果的NMI.由圖可見，除了Thyroid 數(shù)據(jù)集外，L-MCLA 算法的聚類結(jié)果在大部分?jǐn)?shù)據(jù)集上的NMI均趨于平穩(wěn).在Thyroid 數(shù)據(jù)集上，L-MCLA 算法的聚類結(jié)果的NMI在基聚類為10～40 時大幅上升，在40～50時略微下降，隨后又上升且逐漸平穩(wěn).

通過以上的實驗結(jié)果和分析可知，聚類集成的規(guī)模對L-MCLA 算法的聚類結(jié)果的影響不大，在大多數(shù)數(shù)據(jù)集中，L-MCLA 算法可以僅僅依靠較少的聚類成員就得到較穩(wěn)健的結(jié)果.

4 結(jié)論

本文提出基于簇間連接的元聚類集成算法，利用連接三元組來探尋簇間相似度，進一步豐富了相似度矩陣的信息，再通過Ncut 算法和對象分配得到最終的結(jié)果.

本文提出的算法的優(yōu)勢如下.

（1）從簇的級別考慮集成信息，充分考慮了簇與簇之間的關(guān)系.

（2）利用連接三元組增加相似度矩陣中的信息，使聚類結(jié)果更準(zhǔn)確.

將本文提出的算法與七種聚類集成算法進行了對比實驗，證明本文算法和其他聚類集成算法相比，性能存在優(yōu)勢.