超簇加權(quán)的集成聚類算法

薛紅艷，錢雪忠，周世兵

江南大學(xué) 人工智能與計(jì)算機(jī)學(xué)院，江蘇 無(wú)錫 214122

集成聚類通過(guò)對(duì)基聚類實(shí)施組合策略以得到更好的結(jié)果，在發(fā)現(xiàn)奇異聚類、處理噪聲和集成來(lái)自多個(gè)分布式源的聚類上具有較好的優(yōu)勢(shì)[1]。現(xiàn)有集成聚類算法的研究主要集中在兩方面：一是如何生成性能好且有差異性的基聚類[2-5]；二是如何設(shè)計(jì)一致性函數(shù)，如共協(xié)矩陣[6-9]、圖分割[8]等方法得到集成聚類結(jié)果。

目前，大多數(shù)集成聚類算法仍存在三個(gè)局限性。第一，由于K-means 算法實(shí)現(xiàn)簡(jiǎn)單，計(jì)算復(fù)雜度不高且執(zhí)行速度快，故大多集成聚類算法均使用Kmeans 方法生成基聚類[8-9]。但對(duì)于結(jié)構(gòu)復(fù)雜尤其是邊界不易區(qū)分、非球形分布或高維數(shù)據(jù)的數(shù)據(jù)集，使用K-means 算法無(wú)法產(chǎn)生較好的聚類結(jié)果，而質(zhì)量較低的基聚類會(huì)影響共協(xié)矩陣的聚類結(jié)構(gòu)，降低集成聚類的性能[8,10-11]。第二，大多數(shù)集成聚類算法忽視了基聚類多樣性的不同，平等地對(duì)待每個(gè)基聚類[12]。第三，現(xiàn)有的集成聚類算法通常將數(shù)據(jù)對(duì)象作為生成共協(xié)矩陣的基本操作單元[8,11-12]，當(dāng)樣本數(shù)目或集成規(guī)模較大時(shí)，計(jì)算負(fù)擔(dān)明顯增加。針對(duì)該問(wèn)題，有研究者提出以相交簇作為操作單元[13-14]來(lái)降低算法的復(fù)雜度，但隨著集成規(guī)模的增長(zhǎng)，相交簇的數(shù)目顯著增加，復(fù)雜度隨之增加。

鑒于以上三個(gè)問(wèn)題，本文提出了超簇加權(quán)的集成聚類算法（ensemble clustering algorithm based on weighted super cluster，ECWSC）。該算法首先提出一種新的生成基聚類的算法，即基于地標(biāo)點(diǎn)的譜聚類算法。在對(duì)數(shù)據(jù)集使用基于地標(biāo)點(diǎn)的譜聚類算法得到基聚類后，以信息熵為依據(jù)計(jì)算基聚類的不確定性，賦予基聚類相應(yīng)的權(quán)重，并使用加權(quán)的方式得到基于超簇的共協(xié)矩陣。最后對(duì)共協(xié)矩陣使用層次聚類[4]算法進(jìn)行聚類，得到最終結(jié)果。

1 基本技術(shù)

1.1 聚類集成

聚類集成主要分為兩個(gè)步驟：生成基聚類和集成基聚類。假設(shè)數(shù)據(jù)集X={x1,x2,…,xN}是包含N個(gè)數(shù)據(jù)對(duì)象的樣本集，對(duì)X執(zhí)行M次聚類算法得到M個(gè)基聚類，將其標(biāo)記為基聚類集合Π={π1,π2,…,πM}。其中，表示第m個(gè)基聚類，表示πm中第i個(gè)類簇，nm表示πm中類簇的總數(shù)。以為例，n1表示對(duì)數(shù)據(jù)集X執(zhí)行一次聚類算法所得類簇的數(shù)目，是基聚類π1中的第一個(gè)類簇。將基聚類集合Π中所有的類簇用集合C={C1,C2,…,Cnc} 表示，則nc=n1+n2+…+nM，Ci是基聚類集合中的第i個(gè)類簇。若Cj∈πm且xi∈Cj，則Clsm(xi)=Cj。

集成基聚類的方法有共協(xié)矩陣[6-9]、圖分割[8]等方法。本文主要使用共協(xié)矩陣進(jìn)行集成。

1.2 基于相交簇的共協(xié)矩陣組合策略

得到基聚類集合后，大多集成聚類算法通過(guò)計(jì)算兩兩樣本出現(xiàn)在同一個(gè)類簇中的次數(shù)，得到基于樣本的共協(xié)矩陣[15-17]。但隨著樣本數(shù)目的增加，算法的復(fù)雜度顯著提升。

為改進(jìn)上述問(wèn)題，有學(xué)者提出使用相交簇作為操作單元[13-14]。相交簇集合IO={IO1,IO2,…,IONˉ}是類簇相交的集合，IOi表示相交簇集合中第i個(gè)相交簇，Nˉ表示在基聚類集合中相交簇的總數(shù)。相交簇兩兩互不相交，且相交簇的集合即為樣本的集合。?xi,xj∈IO,?πm∈Π,Clsm(xi)=Clsm(xj)且?xi∈IO,xj?IO,?πm∈Π,Clsm(xi)≠Clsm(xj)。如圖1 所示，樣本x1與x2在3 個(gè)基聚類中均聚類到一個(gè)簇中，故Clsm(x1)=Clsm(x2)?；谙嘟淮氐墓矃f(xié)矩陣可表示為：

其中，Aij表示相交簇IOi和相交簇IOj出現(xiàn)在同一類簇中的次數(shù)與集成規(guī)模M的比值。若相交簇IOi與相交簇IOj在第m個(gè)基聚類中聚類在同一個(gè)類簇中，則=1，否則=0。

如圖1（a）～（c）所示，基聚類集合Π由3 個(gè)基聚類組成，分別為π1、π2和π3。其中基聚類π1、π2均有4 個(gè)類簇，π3有3 個(gè)類簇，通過(guò)對(duì)基聚類疊加處理，生成了圖1（e）所示的7 個(gè)相交簇，在以簇為操作單元的共協(xié)矩陣中，元素A13=2/3。

1.3 超簇

超簇[18]是使用碎片整理策略對(duì)相交簇處理后得到的類簇。在相交簇集合IO的基礎(chǔ)上，先定義閾值λ(λ＞0)判斷類簇IOi是否為碎片對(duì)象，若IOi中數(shù)據(jù)樣本的數(shù)目低于λ，則稱IOi為碎片對(duì)象，需要對(duì)其使用碎片整理策略進(jìn)行碎片整理。碎片整理策略是通過(guò)計(jì)算相交簇與相交簇之間的相似度，迭代地將每個(gè)碎片對(duì)象合并到與之相似度最高的類簇中，從而得到超簇集合。相交簇IOi與IOj之間的相似度計(jì)算如下：

Fig.1 Demo of generating super cluster圖1 超簇生成的演示

其中，Akl=，nkl表示xk和xl在M次基聚類中出現(xiàn)在同一個(gè)簇的次數(shù)。如圖1（f），當(dāng)λ=1 時(shí)，使用碎片整理策略對(duì)相交簇進(jìn)行整理，得到5 個(gè)超簇。

1.4 相關(guān)工作對(duì)比

大多數(shù)集成聚類算法使用K-means 算法生成基聚類[8-9]，但用K-means 算法生成的基聚類效果不太理想。針對(duì)該問(wèn)題，本文提出基于地標(biāo)點(diǎn)的譜聚類算法生成基聚類。該算法先從數(shù)據(jù)集中隨機(jī)選取部分候選點(diǎn)，對(duì)候選點(diǎn)使用譜聚類算法得到候選點(diǎn)的聚類結(jié)果，最后將樣本點(diǎn)映射到最近鄰地表點(diǎn)上，得到最終的基聚類結(jié)果，使用該方法可以提高基聚類的質(zhì)量。

對(duì)生成的基聚類進(jìn)行集成時(shí)，集成聚類算法通常以樣本作為操作單元[15-17]得到共協(xié)矩陣，當(dāng)樣本數(shù)目較多時(shí)，算法的復(fù)雜度顯著提高。針對(duì)該問(wèn)題，有研究者提出使用相交簇[13-14]來(lái)降低共協(xié)矩陣的規(guī)模，但相交簇的數(shù)目會(huì)隨著集成規(guī)模的增長(zhǎng)而顯著增加，共協(xié)矩陣規(guī)模仍較高。為解決上述問(wèn)題，本文使用超簇作為操作單元，并根據(jù)基聚類的不確定性對(duì)基聚類賦予對(duì)應(yīng)的權(quán)重，得到基于超簇加權(quán)的共協(xié)矩陣。至此，超簇加權(quán)的集成聚類算法得以提出。

2 超簇加權(quán)的集成聚類算法

針對(duì)大多數(shù)集成聚類算法使用聚類效果較差的K-means 算法生成基聚類，使用共協(xié)矩陣對(duì)基聚類進(jìn)行集成時(shí)，忽略了基聚類多樣性的不同，平等地對(duì)待基聚類，且以樣本為操作單元生成共協(xié)矩陣，導(dǎo)致算法效果差，復(fù)雜度高。本章對(duì)所提超簇加權(quán)的集成聚類算法進(jìn)行詳細(xì)介紹。

2.1 基于地標(biāo)點(diǎn)采樣的譜聚類算法

當(dāng)前，很多集成聚類算法使用K-means 算法生成基聚類，但該算法在初始化聚類中心時(shí)易受初始值的影響。雖然譜聚類算法的準(zhǔn)確度比較高，但也具有較高的時(shí)間和空間復(fù)雜度。文獻(xiàn)[19-23]均采用候選點(diǎn)或類似方法來(lái)提升譜聚類算法的擴(kuò)展性，但在復(fù)雜度或準(zhǔn)確率方面表現(xiàn)欠佳。本節(jié)提出使用隨機(jī)與K-means 結(jié)合的方法選取地標(biāo)點(diǎn)，再對(duì)地標(biāo)點(diǎn)使用譜聚類算法得到其聚類結(jié)果，通過(guò)將樣本映射到與之最近鄰的地標(biāo)點(diǎn)上得到基聚類的結(jié)果。

地標(biāo)點(diǎn)的選取方法如下：先從包含N個(gè)樣本的數(shù)據(jù)集中選出P′個(gè)候選點(diǎn)。由于較大的非球形簇可以視為由多個(gè)較小的球形簇構(gòu)成，且K-means 算法在球形簇上表現(xiàn)佳、速度快，故對(duì)P′個(gè)候選點(diǎn)使用Kmeans 方法得到P個(gè)地標(biāo)點(diǎn)。地標(biāo)點(diǎn)是對(duì)候選點(diǎn)使用K-means 算法得到的K個(gè)中心點(diǎn)，其稀疏線性組合可視為原始數(shù)據(jù)集。如圖2 所示，從圖（a）所示的數(shù)據(jù)集中隨機(jī)選取P′個(gè)候選點(diǎn)得到圖（b），再對(duì)圖（b）中的候選點(diǎn)使用K-means 聚類方法，得到P個(gè)地標(biāo)點(diǎn)。

從數(shù)據(jù)集中隨機(jī)選取P′個(gè)候選點(diǎn)時(shí)，較大的P′通常會(huì)包含較多類別的樣本，但增加了選取地標(biāo)點(diǎn)的復(fù)雜度。P′太小，則無(wú)法包含所有類別的樣本，對(duì)基聚類的質(zhì)量會(huì)有一定的影響。但單個(gè)基聚類的質(zhì)量對(duì)集成聚類的結(jié)果有引導(dǎo)但不起決定作用。為降低隨機(jī)選點(diǎn)對(duì)基聚類質(zhì)量的影響，在集成基聚類時(shí)，若單個(gè)基聚類的質(zhì)量較低，對(duì)應(yīng)的權(quán)重會(huì)有相應(yīng)的變化。此外，在對(duì)相交簇使用碎片整理策略生成超簇，構(gòu)建共協(xié)矩陣時(shí)，會(huì)進(jìn)一步對(duì)不穩(wěn)定的碎片對(duì)象進(jìn)行處理，故對(duì)集成聚類的結(jié)果不會(huì)產(chǎn)生較大的影響。

地標(biāo)點(diǎn)的聚類結(jié)果對(duì)數(shù)據(jù)集中樣本點(diǎn)的聚類結(jié)果有引導(dǎo)作用。在得到地標(biāo)點(diǎn)的聚類結(jié)果后，通過(guò)將樣本映射到與之最近鄰的地標(biāo)點(diǎn)上可得到基聚類的結(jié)果。由于譜聚類算法的復(fù)雜度與樣本數(shù)目呈正相關(guān)，但對(duì)數(shù)據(jù)分布的適應(yīng)性更強(qiáng)，選出地標(biāo)點(diǎn)后，聚類的樣本數(shù)目降低，且地標(biāo)點(diǎn)比小簇中候選點(diǎn)的分布更復(fù)雜，故對(duì)地標(biāo)點(diǎn)采用譜聚類算法可以間接提高基聚類的質(zhì)量。

在得到P個(gè)地標(biāo)點(diǎn)的聚類結(jié)果后，將所有的樣本點(diǎn)映射到與之距離最近的地標(biāo)點(diǎn)上，可以得到全部樣本點(diǎn)的聚類結(jié)果，即基聚類的聚類結(jié)果。一些學(xué)者提出通過(guò)計(jì)算N個(gè)樣本點(diǎn)與P個(gè)地標(biāo)點(diǎn)之間的距離，來(lái)獲得距離樣本點(diǎn)最近的地標(biāo)點(diǎn)[19-23]。為降低算法的時(shí)間和空間復(fù)雜度，本文提出通過(guò)計(jì)算樣本點(diǎn)與之最近鄰地標(biāo)點(diǎn)簇的方式來(lái)獲得與樣本點(diǎn)距離最近的地標(biāo)點(diǎn)。

如圖3 所示，首先使用K-means 方法對(duì)圖（a）中的地標(biāo)點(diǎn)進(jìn)行一次聚類，得到7 個(gè)地標(biāo)點(diǎn)類簇。然后計(jì)算樣本點(diǎn)xi與每個(gè)地標(biāo)點(diǎn)簇中心的距離，選擇與樣本點(diǎn)最近鄰的地標(biāo)點(diǎn)簇，如圖（d）所示。再分別計(jì)算樣本點(diǎn)與最近鄰地標(biāo)點(diǎn)簇中地標(biāo)點(diǎn)之間的距離，從中選擇與樣本點(diǎn)距離最近的地標(biāo)點(diǎn)，如圖（f）所示。將數(shù)據(jù)集中所有的樣本點(diǎn)映射到與其最近的地標(biāo)點(diǎn)上，最終可得到基聚類的聚類結(jié)果。

2.2 基于類簇不確定性的權(quán)重分配

得到基聚類成員后，有部分集成聚類算法根據(jù)聚類指標(biāo)值從基聚類集合中篩選出質(zhì)量較高的基聚類成員進(jìn)行集成聚類[24]。使用指標(biāo)值對(duì)基聚類篩選，增加了算法的計(jì)算負(fù)擔(dān)。針對(duì)上述問(wèn)題，本文提出用類簇的不確定性來(lái)衡量基聚類的質(zhì)量，對(duì)基聚類賦予相應(yīng)的權(quán)重。

為評(píng)估每個(gè)基聚類的不確定性，先計(jì)算基聚類中類簇的不確定性。在基聚類集合Π中，類簇Cm i相對(duì)于基聚類集合Π的不確定性為：

Fig.2 Selection of landmark points圖2 地標(biāo)點(diǎn)的選取

Fig.3 Nearest landmark point of sample point圖3 樣本點(diǎn)的最近鄰地標(biāo)點(diǎn)

用基聚類的平均熵表示基聚類不確定性，給定基聚類集合Π，基聚類成員πm的不確定性為：

其中，nm表示基聚類πm中類簇的數(shù)目。

有研究者發(fā)現(xiàn)，效果更好而多樣性低的基聚類集成效果低于多樣性高的基聚類集合[24]?；垲惖牟淮_定性越高，則該基聚類所包含的信息量越大。為更好地滿足基聚類好而不同的要求，對(duì)該基聚類賦予更高的權(quán)重。通過(guò)對(duì)基聚類的不確定性進(jìn)行歸一化處理得到相應(yīng)的權(quán)重，權(quán)重范圍為[0,1]。至此，基聚類πm的權(quán)重W(πm)可表示如下：

2.3 基于權(quán)重超簇的共協(xié)矩陣

大多集成聚類算法使用共協(xié)矩陣得到樣本之間的相似度時(shí)，平等地對(duì)待每個(gè)基聚類[3-4]，忽略了基聚類多樣性的不同。鑒于此，一些學(xué)者對(duì)該方法進(jìn)行了改進(jìn)，例如使用樣本加權(quán)策略[25]來(lái)改進(jìn)共協(xié)矩陣。為降低以樣本或相交簇為操作單元計(jì)算共協(xié)矩陣帶來(lái)的計(jì)算負(fù)擔(dān)，本文以超簇為操作單元并引入權(quán)重的策略。將基聚類生成相交簇后使用碎片整理策略得到的超簇標(biāo)記為Z={z1,z2,…,zN*}，N*表示超簇的數(shù)目。則基于加權(quán)超簇的共協(xié)矩陣WECA可表示如下：

2.4 超簇加權(quán)的集成聚類算法步驟

超簇加權(quán)的集成聚類算法流程簡(jiǎn)單描述如下：

輸入：數(shù)據(jù)集X，候選點(diǎn)數(shù)P′，地標(biāo)點(diǎn)的個(gè)數(shù)P(N＞＞P′＞＞P)，聚類數(shù)K，碎片對(duì)象的閾值λ，基聚類的數(shù)目M。

輸出：集成聚類結(jié)果C。

步驟1從數(shù)據(jù)集X中選取P′個(gè)候選點(diǎn)，使用Kmeans 的方法將P′個(gè)候選點(diǎn)聚類成P個(gè)簇，P個(gè)簇的中心點(diǎn)即為地標(biāo)點(diǎn)。

步驟2將數(shù)據(jù)集中的每個(gè)樣本點(diǎn)分配到與其點(diǎn)距離最近的地標(biāo)點(diǎn)。

步驟3對(duì)P個(gè)地標(biāo)點(diǎn)使用譜聚類的方法，生成K個(gè)簇，得到P個(gè)地標(biāo)點(diǎn)的聚類結(jié)果。

步驟4將數(shù)據(jù)集中的樣本點(diǎn)映射到地標(biāo)點(diǎn)上，得到全部樣本點(diǎn)的聚類結(jié)果。

步驟5重復(fù)M次步驟1、2、3 和4，得到基聚類集合Π。

步驟6根據(jù)式（4）和式（5）計(jì)算基聚類的權(quán)重W。

步驟7根據(jù)式（2）對(duì)步驟5 中生成的相交簇使用碎片化策略處理，得到超簇Z。

步驟8根據(jù)式（6）以超簇Z為操作單元，W為基聚類權(quán)重，生成WECA矩陣。

步驟9在WECA矩陣上執(zhí)行層次聚類算法[26]得到最終結(jié)果C。

3 實(shí)驗(yàn)驗(yàn)證

為驗(yàn)證超簇加權(quán)的集成聚類算法的有效性和優(yōu)良性能，本章從人工數(shù)據(jù)集和真實(shí)數(shù)據(jù)集兩方面對(duì)所提集成算法進(jìn)行驗(yàn)證，本文實(shí)驗(yàn)的環(huán)境為Intel Core i7-8565U CPU@1.80 GHz 1.99 GHz，Windows10，Matlab2019a等。

3.1 基于人造數(shù)據(jù)集的驗(yàn)證

本節(jié)在表1 所示的4 組人造數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)驗(yàn)證。Smile2 數(shù)據(jù)集是由2 個(gè)團(tuán)狀簇、1 個(gè)環(huán)狀簇和1個(gè)流行簇組成，2d-4c-2 數(shù)據(jù)集由4 個(gè)團(tuán)狀簇組成，Dartboard1 數(shù)據(jù)集由4 個(gè)環(huán)狀簇組成，Banana 數(shù)據(jù)集則是由2 個(gè)流行簇組成。概率軌跡累積（probability trajectory accumulation，PTA）算法[14]是基于相交簇的集成聚類算法，本節(jié)使用PTA 算法與所提ECWSC 算法進(jìn)行對(duì)比。

Table 1 Artificial datasets表1 人工數(shù)據(jù)集

為保證實(shí)驗(yàn)的公平，圖4 和圖5 中集成規(guī)模M的值均設(shè)置為10，均采用不同的顏色來(lái)區(qū)分聚類的結(jié)果，同一類簇中的樣本用同一顏色表示。在PTA 與ECWSC 算法中，數(shù)據(jù)集Smile2、2d-4c-2 和Dartboard1的類簇?cái)?shù)目均設(shè)置為4，Banana 數(shù)據(jù)集的類簇?cái)?shù)目設(shè)置為2。圖5 中紅色的點(diǎn)表示集成規(guī)模M為10 時(shí)，使用ECWSC 算法生成第10 個(gè)基聚類成員時(shí)選擇的地標(biāo)點(diǎn)。數(shù)據(jù)集Smile2、2d-4c-2 和Banana 地標(biāo)點(diǎn)的數(shù)目均設(shè)置為300，Dartboard1 地標(biāo)點(diǎn)的數(shù)目設(shè)置為600。

從圖4 可見(jiàn)，PTA 算法在4 個(gè)人工數(shù)據(jù)集上均無(wú)法得到正確的聚類結(jié)果。圖5 中，ECWSC 算法將Smile2、2d-4c-2、Dartboard1 數(shù)據(jù)集聚為4類，將Banana數(shù)據(jù)集聚為2 類，且都得到了正確的聚類結(jié)果。

3.2 基于真實(shí)數(shù)據(jù)集的驗(yàn)證

為進(jìn)一步驗(yàn)證ECWSC 算法的性能，本節(jié)將ECWSC 算法在表2中的7個(gè)真實(shí)數(shù)據(jù)集上，與6 種實(shí)驗(yàn)方法進(jìn)行對(duì)比。對(duì)比實(shí)驗(yàn)分別為PTA、概率軌跡圖劃分（probability trajectory based graph partitioning，PTGP）[14]、局部加權(quán)證據(jù)累積（locally weighted evidence accumulation，LWEA）[9]、局部加權(quán)圖劃分（locally weighted graph partitioning，LWGP）[9]、傳播聚類相似性（propagating cluster-wise similarities，ECPCS-HC）[15]、證據(jù)累積聚類（evidence accumulation clustering，EAC）[6]。

Fig.4 Clustering result of PTA on artificial datasets圖4 PTA 算法在人工數(shù)據(jù)集聚類表現(xiàn)

Fig.5 Clustering result of ECWSC on artificial datasets圖5 ECWSC 算法在人工數(shù)據(jù)集聚類表現(xiàn)

Table 2 Real datasets表2 真實(shí)數(shù)據(jù)集

真實(shí)數(shù)據(jù)集分別是Semeion、Landsat、IS（image segmentation）、Isolet、PD（pen digit）、Usps、Letters。其中，Letters、Usps 數(shù)據(jù)集來(lái)自文獻(xiàn)[5]，其他來(lái)自UCI數(shù)據(jù)集，數(shù)據(jù)集的詳細(xì)信息可見(jiàn)表2。

實(shí)驗(yàn)采用標(biāo)準(zhǔn)化互信息（normalized mutual information，NMI）和調(diào)整蘭德系數(shù)（adjusted Rand index，ARI）兩個(gè)指標(biāo)對(duì)聚類結(jié)果進(jìn)行評(píng)價(jià)。NMI 從信息論的角度評(píng)估兩個(gè)類之間的相似性，取值范圍為[0,1]，ARI 指標(biāo)則可以衡量?jī)蓚€(gè)數(shù)據(jù)分布的吻合程度，取值范圍為[-1,1]。二者的結(jié)果均為越接近1，效果越好。

當(dāng)P過(guò)大時(shí)，對(duì)地標(biāo)點(diǎn)使用譜聚類算法會(huì)增加生成基聚類的復(fù)雜度，P過(guò)小時(shí)，地標(biāo)點(diǎn)將無(wú)法包含所有類別的樣本。當(dāng)數(shù)據(jù)集的樣本非常多或非常少時(shí)，可以適當(dāng)?shù)販p少或者增加P值的設(shè)置，為保證實(shí)驗(yàn)的公平，且考慮到本文的數(shù)據(jù)集樣本數(shù)均在103～105之間，故本實(shí)驗(yàn)在使用基于地標(biāo)點(diǎn)采樣的譜聚類算法生成基聚類時(shí)，地標(biāo)點(diǎn)參數(shù)P設(shè)置為1 000。為減少參數(shù)的設(shè)置，隨機(jī)候選點(diǎn)的數(shù)目P′=10P，當(dāng)P′的值超出數(shù)據(jù)集的樣本數(shù)時(shí)，P′默認(rèn)設(shè)置為樣本數(shù)的大小。碎片對(duì)象λ的閾值大小參照文獻(xiàn)[18]的設(shè)置，閾值的大小為5。6 個(gè)對(duì)比實(shí)驗(yàn)均使用隨機(jī)Kmeans 算法生成基聚類，其范圍為[1,K]，聚類數(shù)目K值的大小與數(shù)據(jù)集的類別數(shù)目一致，集成規(guī)模的尺寸M=20。實(shí)驗(yàn)結(jié)果如表3 所示，表中數(shù)據(jù)是運(yùn)行20次所得結(jié)果的平均值和標(biāo)準(zhǔn)差，均采用百分?jǐn)?shù)的形式表示，表中每個(gè)數(shù)據(jù)集對(duì)應(yīng)效果最好的兩個(gè)算法的數(shù)據(jù)均已加粗顯示。

相比于將樣本視為操作單元的LWEA、LWGP、EAC 算法和將相交簇視為操作單元PTA、PTGP、HC算法，ECWSC 算法將隨機(jī)選點(diǎn)與K-means 選點(diǎn)的方法相結(jié)合來(lái)選取地標(biāo)點(diǎn)，并使用基于地標(biāo)點(diǎn)的譜聚類算法生成基聚類。在此基礎(chǔ)上，使用信息熵的方法計(jì)算基聚類中類簇的不確定性，并賦予基聚類相應(yīng)的權(quán)重，再使用加權(quán)的方式得到基于超簇的共協(xié)矩陣。從實(shí)驗(yàn)結(jié)果可知，ECWSC 在多個(gè)數(shù)據(jù)集上的標(biāo)準(zhǔn)方差低于對(duì)比實(shí)驗(yàn)，這表明相比于對(duì)比算法，ECWSC 算法的穩(wěn)定性較好。

從表3 的實(shí)驗(yàn)結(jié)果可見(jiàn)，在Letters 數(shù)據(jù)集上，LWEA 與LWGP 算法在對(duì)樣本實(shí)施加權(quán)策略時(shí)，算法運(yùn)行超出內(nèi)存無(wú)法得到聚類結(jié)果，故將其指標(biāo)值用“N/A”標(biāo)記。與使用樣本為操作單元相比，ECWSC算法使用了超簇作為操作單元，在構(gòu)建共協(xié)矩陣時(shí)，復(fù)雜度顯著降低，故仍可以運(yùn)行出較好的結(jié)果。這表明ECWSC 算法在空間復(fù)雜度上占據(jù)了一定的優(yōu)勢(shì)。此外，從數(shù)據(jù)集在算法上的表現(xiàn)可知，ECWSC算法相比于其他幾個(gè)對(duì)比實(shí)驗(yàn)，在NMI 和ARI 指標(biāo)上值均有顯著提升。其中，ECWSC 算法相比于對(duì)比實(shí)驗(yàn)，NMI 的值提高了5%～25%，ARI 的值則提高了3%～25%。提升最為顯著的是Usps 數(shù)據(jù)集，其NMI指標(biāo)值提高了24.25%，ARI 指標(biāo)值提升了24.14%，這表明使用超簇加權(quán)的集成聚類算法相比于其他算法在準(zhǔn)確度上有一定的優(yōu)勢(shì)。

Table 3 Performance of different algorithms on datasets(M=20)表3 不同算法在數(shù)據(jù)集上的表現(xiàn)（M=20）%

為驗(yàn)證ECWSC 算法在時(shí)間復(fù)雜度上相比于其他算法有所改進(jìn)，將上述的7 個(gè)算法在表2 所示7 個(gè)數(shù)據(jù)集上運(yùn)行的時(shí)間進(jìn)行對(duì)比。集成規(guī)模M為20時(shí)，執(zhí)行20 次算法所用時(shí)間的平均值作為運(yùn)行該算法所用時(shí)間，實(shí)驗(yàn)結(jié)果如圖6 所示。圖中的橫坐標(biāo)表示不同的集成聚類算法，縱坐標(biāo)表示該算法在當(dāng)前數(shù)據(jù)集上運(yùn)行的時(shí)間。在柱狀圖中，同一數(shù)據(jù)集在不同算法上運(yùn)行的時(shí)間使用同一個(gè)顏色的矩形表示。由于LWEA 算法和LWGP 算法在Letters 數(shù)據(jù)集上運(yùn)行超出內(nèi)存，無(wú)法得到聚類結(jié)果，故其運(yùn)行時(shí)間未在圖中標(biāo)記。

將數(shù)據(jù)集在7 個(gè)算法上運(yùn)行的時(shí)間進(jìn)行分析。以Semeion 在7 個(gè)算法上運(yùn)行時(shí)間為例，ECWSC 算法在Semeion 數(shù)據(jù)集上的平均運(yùn)行時(shí)間是0.01 s，6 個(gè)對(duì)比實(shí)驗(yàn)中，平均運(yùn)行時(shí)間最低的算法為L(zhǎng)WGP 算法，運(yùn)行時(shí)間為1.2 s，其運(yùn)行效率遠(yuǎn)低于本文算法。從圖6 可見(jiàn)，當(dāng)樣本數(shù)目較多時(shí)，本文算法的運(yùn)行時(shí)間遠(yuǎn)低于其他6 個(gè)對(duì)比實(shí)驗(yàn)。此外，當(dāng)Letters 數(shù)據(jù)集在對(duì)比實(shí)驗(yàn)上運(yùn)行超出內(nèi)存而無(wú)法得到聚類結(jié)果時(shí)，本文算法依舊可以得到較好的聚類效果。當(dāng)數(shù)據(jù)集中樣本數(shù)目增長(zhǎng)時(shí)，6 個(gè)對(duì)比算法的運(yùn)行時(shí)間會(huì)顯著提高，但ECWSC 算法的運(yùn)行時(shí)間增長(zhǎng)仍比較緩慢。

從7 個(gè)算法在真實(shí)數(shù)據(jù)集上運(yùn)行的時(shí)間和算法準(zhǔn)確度的表現(xiàn)可知，本文所提的ECWSC 算法在生成基聚類時(shí)，采用基于地標(biāo)點(diǎn)的譜聚類算法降低了生成基聚類的復(fù)雜度。在集成基聚類時(shí)，使用超簇作為操作單元且對(duì)基聚類賦予相應(yīng)的權(quán)重，降低了共協(xié)矩陣的規(guī)模。相比于其他算法，上述方式均降低了算法的復(fù)雜度，在運(yùn)行時(shí)間上有一定的優(yōu)勢(shì)。

4 集成規(guī)模與集成結(jié)果

本章評(píng)估ECWSC 算法與其他集成聚類算法在不同集成規(guī)模M下的表現(xiàn)，以獲取集成規(guī)模M與集成聚類結(jié)果之間的關(guān)系，從表2 中選取4 個(gè)真實(shí)數(shù)據(jù)集，分別是Semeion、IS、Isolet、PD 數(shù)據(jù)集進(jìn)行實(shí)驗(yàn)。其中，對(duì)比實(shí)驗(yàn)仍選取以樣本為操作單元的LWEA、LWGP、EAC 算法和以相交簇為操作單元的PTA、PTGP、HC 算法。算法集成規(guī)模M的值均由10 增長(zhǎng)為50，步長(zhǎng)設(shè)置為10。與上章實(shí)驗(yàn)一致，ECWSC 算法地標(biāo)點(diǎn)參數(shù)P設(shè)置為1 000，隨機(jī)候選點(diǎn)的數(shù)目P′=10P，碎片對(duì)象λ大小為5。

為降低實(shí)驗(yàn)結(jié)果的偶然性，所有的實(shí)驗(yàn)值均采用運(yùn)行20 次所求NMI、ARI 的平均值。其中，圖7 和圖8 中的橫坐標(biāo)均表示集成規(guī)模的變化，圖7 中的縱坐標(biāo)表示算法結(jié)果NMI 的值隨集成規(guī)模M的變化。圖8 中的縱坐標(biāo)表示算法結(jié)果ARI 的值隨集成規(guī)模M的變化，其中紅色的線表示超簇加權(quán)的ECWSC 算法集成聚類結(jié)果。

Fig.6 Time cost of 7 methods on different datasets圖6 不同數(shù)據(jù)集上7 種算法的時(shí)間成本

Fig.7 NMI values for different methods under different M圖7 不同集成方法在不同M 下的NMI值

Fig.8 ARI values for different methods under different M圖8 不同集成方法在不同M 下的ARI值

從圖7 和圖8 的實(shí)驗(yàn)結(jié)果可見(jiàn)，對(duì)于同一集成規(guī)模M，無(wú)論是NMI 或是ARI 的比較，ECWSC 算法在Semeion、IS、Isolet、PD 數(shù)據(jù)集上的運(yùn)行效果均高于幾個(gè)對(duì)比實(shí)驗(yàn)，其NMI 和ARI 的值相比于對(duì)比實(shí)驗(yàn)提高0.05～0.30。從圖7 和圖8 可見(jiàn)，隨著集成規(guī)模M的變化，對(duì)比實(shí)驗(yàn)的結(jié)果均有較為顯著的提高或降低，而ECWSC 算法的運(yùn)行效果仍較穩(wěn)定。

5 結(jié)束語(yǔ)

本文提出了超簇加權(quán)的集成聚類算法。該算法提出基于地標(biāo)點(diǎn)的譜聚類算法生成基聚類，在此基礎(chǔ)上計(jì)算基聚類的不確定性，賦予基聚類相應(yīng)權(quán)重，并使用加權(quán)的方式得到基于超簇的共協(xié)矩陣，最后使用層次聚類算法對(duì)超簇進(jìn)行聚類。通過(guò)多組對(duì)比實(shí)驗(yàn)證明超簇加權(quán)的集成聚類方法能夠有效提升聚類集成的聚類效果。在后續(xù)的工作中會(huì)進(jìn)一步考慮自動(dòng)確定聚類數(shù)目，并將所提聚類算法用于實(shí)際應(yīng)用中，如將圖像分割技術(shù)與本文算法相結(jié)合。