薛紅艷，錢雪忠，周世兵

江南大學 人工智能與計算機學院，江蘇 無錫 214122

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

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

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

1 基本技術

1.1 聚類集成

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

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

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

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

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

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

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

1.3 超簇

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

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

其中，Akl=，nkl表示xk和xl在M次基聚類中出現在同一個簇的次數。如圖1（f），當λ=1 時，使用碎片整理策略對相交簇進行整理，得到5 個超簇。

1.4 相關工作對比

大多數集成聚類算法使用K-means 算法生成基聚類[8-9]，但用K-means 算法生成的基聚類效果不太理想。針對該問題，本文提出基于地標點的譜聚類算法生成基聚類。該算法先從數據集中隨機選取部分候選點，對候選點使用譜聚類算法得到候選點的聚類結果，最后將樣本點映射到最近鄰地表點上，得到最終的基聚類結果，使用該方法可以提高基聚類的質量。

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

2 超簇加權的集成聚類算法

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

2.1 基于地標點采樣的譜聚類算法

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

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

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

地標點的聚類結果對數據集中樣本點的聚類結果有引導作用。在得到地標點的聚類結果后，通過將樣本映射到與之最近鄰的地標點上可得到基聚類的結果。由于譜聚類算法的復雜度與樣本數目呈正相關，但對數據分布的適應性更強，選出地標點后，聚類的樣本數目降低，且地標點比小簇中候選點的分布更復雜，故對地標點采用譜聚類算法可以間接提高基聚類的質量。

在得到P個地標點的聚類結果后，將所有的樣本點映射到與之距離最近的地標點上，可以得到全部樣本點的聚類結果，即基聚類的聚類結果。一些學者提出通過計算N個樣本點與P個地標點之間的距離，來獲得距離樣本點最近的地標點[19-23]。為降低算法的時間和空間復雜度，本文提出通過計算樣本點與之最近鄰地標點簇的方式來獲得與樣本點距離最近的地標點。

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

2.2 基于類簇不確定性的權重分配

得到基聚類成員后，有部分集成聚類算法根據聚類指標值從基聚類集合中篩選出質量較高的基聚類成員進行集成聚類[24]。使用指標值對基聚類篩選，增加了算法的計算負擔。針對上述問題，本文提出用類簇的不確定性來衡量基聚類的質量，對基聚類賦予相應的權重。

為評估每個基聚類的不確定性，先計算基聚類中類簇的不確定性。在基聚類集合Π中，類簇Cm i相對于基聚類集合Π的不確定性為：

Fig.2 Selection of landmark points圖2 地標點的選取

Fig.3 Nearest landmark point of sample point圖3 樣本點的最近鄰地標點

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

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

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

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

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

2.4 超簇加權的集成聚類算法步驟

超簇加權的集成聚類算法流程簡單描述如下：

輸入：數據集X，候選點數P′，地標點的個數P(N＞＞P′＞＞P)，聚類數K，碎片對象的閾值λ，基聚類的數目M。

輸出：集成聚類結果C。

步驟1從數據集X中選取P′個候選點，使用Kmeans 的方法將P′個候選點聚類成P個簇，P個簇的中心點即為地標點。

步驟2將數據集中的每個樣本點分配到與其點距離最近的地標點。

步驟3對P個地標點使用譜聚類的方法，生成K個簇，得到P個地標點的聚類結果。

步驟4將數據集中的樣本點映射到地標點上，得到全部樣本點的聚類結果。

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

步驟6根據式（4）和式（5）計算基聚類的權重W。

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

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

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

3 實驗驗證

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

3.1 基于人造數據集的驗證

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

Table 1 Artificial datasets表1 人工數據集

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

從圖4 可見，PTA 算法在4 個人工數據集上均無法得到正確的聚類結果。圖5 中，ECWSC 算法將Smile2、2d-4c-2、Dartboard1 數據集聚為4類，將Banana數據集聚為2 類，且都得到了正確的聚類結果。

3.2 基于真實數據集的驗證

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

Fig.4 Clustering result of PTA on artificial datasets圖4 PTA 算法在人工數據集聚類表現

Fig.5 Clustering result of ECWSC on artificial datasets圖5 ECWSC 算法在人工數據集聚類表現

Table 2 Real datasets表2 真實數據集

真實數據集分別是Semeion、Landsat、IS（image segmentation）、Isolet、PD（pen digit）、Usps、Letters。其中，Letters、Usps 數據集來自文獻[5]，其他來自UCI數據集，數據集的詳細信息可見表2。

實驗采用標準化互信息（normalized mutual information，NMI）和調整蘭德系數（adjusted Rand index，ARI）兩個指標對聚類結果進行評價。NMI 從信息論的角度評估兩個類之間的相似性，取值范圍為[0,1]，ARI 指標則可以衡量兩個數據分布的吻合程度，取值范圍為[-1,1]。二者的結果均為越接近1，效果越好。

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

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

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

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

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

將數據集在7 個算法上運行的時間進行分析。以Semeion 在7 個算法上運行時間為例，ECWSC 算法在Semeion 數據集上的平均運行時間是0.01 s，6 個對比實驗中，平均運行時間最低的算法為LWGP 算法，運行時間為1.2 s，其運行效率遠低于本文算法。從圖6 可見，當樣本數目較多時，本文算法的運行時間遠低于其他6 個對比實驗。此外，當Letters 數據集在對比實驗上運行超出內存而無法得到聚類結果時，本文算法依舊可以得到較好的聚類效果。當數據集中樣本數目增長時，6 個對比算法的運行時間會顯著提高，但ECWSC 算法的運行時間增長仍比較緩慢。

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

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

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

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

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

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 的實驗結果可見，對于同一集成規(guī)模M，無論是NMI 或是ARI 的比較，ECWSC 算法在Semeion、IS、Isolet、PD 數據集上的運行效果均高于幾個對比實驗，其NMI 和ARI 的值相比于對比實驗提高0.05～0.30。從圖7 和圖8 可見，隨著集成規(guī)模M的變化，對比實驗的結果均有較為顯著的提高或降低，而ECWSC 算法的運行效果仍較穩(wěn)定。

5 結束語

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