基于集成學習的改進深度嵌入聚類算法

黃宇翔，黃 棟+，王昌棟，賴劍煌

1.華南農業(yè)大學 數學與信息學院，廣州 510642

2.廣州市智慧農業(yè)重點實驗室，廣州 510642

3.中山大學 計算機學院，廣州 510006

數據聚類是無監(jiān)督學習的一個重要問題，其目標在于將一組數據樣本劃分為若干個簇，以使得同簇樣本盡可能相似，異簇樣本盡可能不同[1]。傳統(tǒng)聚類算法往往以給定的數據特征作為輸入，再采用不同模型對其進行劃分，但在一些復雜高維數據（例如圖像數據、文本數據等）情況下，則可能因缺乏在高維空間對樣本相似性的有效度量而難以發(fā)現其內在聚類結構，即面臨所謂的“維數災難”（curse of dimensionality）。對于高維數據聚類，常規(guī)應對方法包括子空間聚類（subspace clustering）[2]、特征降維（dimension reduction）[3]、特征抽取（feature selection）[4-5]等；近年來，深度學習因其在特征表示上的獨特優(yōu)勢，也為高維、復雜數據聚類帶來了一個新的解決思路，并已涌現出許多行之有效的深度聚類算法[6-11]。

在初期的深度聚類研究中，Tian 等[6]對自編碼器（autoencoder）與譜聚類（spectral clustering）之間的關聯(lián)進行了分析，提出利用一種稀疏自編碼器，以數據樣本的相似性矩陣作為訓練集，通過深度神經網絡（deep neural network，DNN）學習得到低維數據特征，進而使用K均值（K-means）聚類構建聚類結果。Chen[8]利用一個深度置信網絡（deep belief network，DBN）進行特征學習，進而使用非參最大間隔聚類（nonparametric maximum margin clustering，NMMC）得到最終聚類。Peng 等[9]結合輸入空間的稀疏重構關系，訓練一個兼顧數據局部與全局信息的深度神經網絡，以學習得到低維數據表示并進行數據聚類。這些方法[6,8-9]將深度聚類過程劃分為兩個階段：一是特征表示學習階段，即以一定的深度神經網絡結構來學習得到數據的低維特征表示；二是聚類階段，即采用傳統(tǒng)聚類算法在學習得到的低維特征空間上對數據樣本進行劃分以得最終聚類。

相比于將表示學習與聚類過程劃分為兩個不同階段的做法[6,8-9]，Xie 等[12]通過定義一個基于KL 散度（Kullback-Leibler divergence）的聚類損失函數，對深度神經網絡的參數和聚類分配進行同時優(yōu)化，提出了深度嵌入聚類（deep embedding clustering，DEC）算法。DEC 算法為聚類研究提供了一個有力的工具，但是該算法的一個局限性在于超參數λ的調節(jié)與優(yōu)化問題。在DEC算法中，用于控制退火速度（annealing speed）的超參數λ對聚類效果有著較為敏感的影響，其設置往往依賴人工調節(jié)；但是，在缺乏先驗知識或人工監(jiān)督的情況下，如何在不同數據集下為其選取合適的超參數值仍是一個有待解決的問題。

針對DEC 算法的超參數敏感問題，本文基于集成聚類（ensemble clustering）的思想對其進行解決。集成聚類是一類重要的無監(jiān)督集成學習技術，其目標在于融合多個具有多樣性的基聚類（base clusterings）以得到一個更優(yōu)、更魯棒聚類[13-24]。常規(guī)DEC 算法對超參數λ的敏感性，正好可以為集成聚類過程提供其所需的基聚類“多樣性”因素。具體地，本文提出一種基于集成學習的改進深度嵌入聚類（improved deep embedding clustering method with ensemble learning，IDECEL）算法；區(qū)別于為每一個數據集人工調得一個合適超參數的做法，IDECEL 不尋求超參數的單一最優(yōu)取值，而是令超參數λ在較大范圍內波動以構建一組具有多樣性的基聚類集合。進一步，結合熵理論對各個基聚類的簇不確定性進行評估與加權，進而構建基于局部加權的二部圖模型并將其高效分割，以進行基聚類融合，并得到最終集成聚類結果（其算法流程如圖1 所示）。本文在多個數據集上的實驗結果表明，所提出的IDECEL 算法一方面可以有效應對常規(guī)DEC 算法的超參數敏感問題，另一方面，即使與DEC 算法在最優(yōu)超參數下的性能進行對比，仍可表現出更為魯棒的聚類效果。在后續(xù)章節(jié)中，將對IDECEL 算法進行具體介紹。

Fig.1 Flowchart of IDECEL圖1 IDECEL 算法流程圖

1 基于集成學習的改進深度嵌入聚類

1.1 由深度嵌入聚類到多樣化基聚類

深度嵌入聚類（DEC）[12]是一個重要的深度聚類算法，該算法主要包括兩部分：一是對自動編碼器進行參數初始化；二是用KL 散度迭代優(yōu)化聚類。DEC使用堆疊自編碼器（stacked autoencoder，SAE），逐層初始化SAE 網絡，每一層都是經過降噪處理的自編碼器[25]。自編碼器訓練好之后，舍棄解碼器部分，在編碼器后添加聚類模塊。為了初始化簇心，DEC 將數據輸入到編碼器中，輸出為嵌入點，然后對這些嵌入點進行標準K均值聚類處理，將聚類結果作為后續(xù)聚類用的初始簇心。

對于嵌入點zi=fθ(xi)∈Z和初始簇心，DEC在兩個步驟間迭代優(yōu)化聚類：一是計算嵌入點和簇心之間的軟分配；二是更新嵌入點，通過最小化軟標簽分布和輔助目標分布之間的KL 散度來優(yōu)化簇心。基于t-SNE 的思想[26]，DEC 使用t 分布來估計嵌入點和簇心之間的相似度，也就是軟分配，如下：

其中，α是t分布的自由度，在DEC 中，該自由度設置為1。此處qij也可以解釋為樣本i屬于聚類j的可能性。然后，DEC 提出了一個輔助目標分布來衡量樣本屬于某個聚類的分布：

有了原始分布和輔助分布之后，DEC 通過KL 散度拉近兩個分布的距離，其損失函數如下：

每次迭代需要更新的參數的梯度為：

此處，式（4）用于優(yōu)化編碼器的網絡參數，式（5）用于優(yōu)化簇心。在此框架下，DEC 可同時優(yōu)化網絡參數與聚類。

為構建所需的基聚類集合，本文沿用DEC 的網絡結構，在優(yōu)化部分對聚類的簇心和深度網絡的參數用梯度下降法進行聯(lián)合優(yōu)化。在優(yōu)化過程中，都在計算輔助目標分布和最小化KL 散度之間迭代；每隔λ次，對軟分布和輔助目標分布進行更新。其中，超參數λ對聚類性能有較大影響，但又難以進行估計。對此，本文基于集成聚類的策略，不尋求單一λ值，而是令其在較大范圍內活動以構建多樣化基聚類。具體地，令λ=2i×10,i=0,1,…,9 以獲取10 個不同λ值，在每個λ值下運行M′次以得M′個基聚類結果（需要注意的是，在相同λ值下運行多次的聚類結果也往往不同），從而可得總共M=10M′個差異化的基聚類，表示為：

其中，πm=表示第i個基聚類，表示基聚類πm中的第i個簇，nm表示該基聚類πm中的簇數量。在基聚類集合中，每一個基聚類包含若干個簇，不妨把各個基聚類中所有簇的集合表示為：

其中，Ci表示基聚類集合中的第i個簇，nc表示其全體簇數量。接下來，在此多樣化基聚類集合的基礎上，下一節(jié)將介紹其集成過程。

1.2 局部加權與基聚類集成

對于所構建的基聚類集合，不同基聚類的可靠度可能各不相同；即使同一基聚類內不同簇的可靠度也不一樣。為得到更優(yōu)集成聚類結果，本文采用局部熵加權策略[19]對基聚類集合中的各個簇進行可靠度評估與加權。具體地，借助于熵（entropy）的概念，來對簇的不確定（uncertainty）作度量。給定一個簇Ci，其相對于該基聚類πm的不確定性計算如下[19]：

其中，?表示兩個簇的交集，|Ci|表示簇Ci中樣本數量。基于基聚類集合Π中M個基聚類具有相互獨立性的假設，簇Ci相對于整個基聚類集合Π的熵（即不確定性）可計算為：

各個簇的不確定性（或不穩(wěn)定性），可視作與其可靠度呈負相關。在其基礎上，計算一個集成驅動的簇指標（ensemble-driven cluster index，ECI）來作為簇可靠性度量，如下：

進一步，以樣本集合X與簇集合C的并集作為節(jié)點集，以ECI 作為邊的權值，構建一個加權二部圖（bipartite graph），表示如下：

其中，V=X?C表示節(jié)點的集合，L表示邊的集合。對于節(jié)點vi和vj之間的邊，其權值定義如下：

在此二部圖中，當且僅當一個節(jié)點為數據樣本節(jié)點，另一個節(jié)點為簇節(jié)點，且該樣本“屬于”這個簇時，這兩個節(jié)點之間存在連接邊，且其邊的權值取決于這個簇的可靠度，即由其ECI值決定。對此二部圖結構，進一步可以通過Tcut算法[27]將其劃分為若干個節(jié)點子集，并將劃為同一子集的樣本節(jié)點歸為同一個簇，從而得到最終的集成聚類結果。

2 實驗結果與分析

在本章中，將在5 個數據集上進行實驗，并對IDECEL 算法與其他多個深度聚類及集成聚類算法進行對比與分析。

2.1 實驗設置

在本文實驗中，深度神經網絡[12]由完全連接層組成，大小設置為d-500-500-2 000-10，其中d是輸入數據的維度。初始化網絡權重為零均值高斯分布（標準差為0.01）的隨機數；各層的激活函數均為ReLU；minibatch size為256。在最小化KL散度階段，本文使用SGD 優(yōu)化器進行優(yōu)化，其學習率λ=0.01，β=0.9。判斷收斂的閾值為tol=0.1% 。對于超參數λ，令λ=2i×10,i=0,1,…,9，獲取10 個不同λ值，在每個λ值下生成M'個基聚類，以構建總共M=10M'個差異化的基聚類。在實驗中，本文默認使用集成規(guī)模M=50（即對應于M'=5）。在第2.5 節(jié)中，本文將進一步進行實驗，測試所提出算法在不同集成規(guī)模下的性能。

2.2 數據集與評價指標

本文實驗將在5 個數據集上進行，分別是：MNIST[12]、FMNIST[28]、Reuters10K[12]、Gisette[29]以 及Cifar10[30]。在這些數據集中，Reuters10K 為文本數據集，其余4 個則為圖像數據集。各個數據集的具體情況如表1 所示。

Table 1 Dataset of experiment表1 實驗數據集

為對比不同聚類算法的性能，本文采用了三種常用的聚類評價指標，分別是NMI（normalized mutual information）[13]、ARI（adjusted Rand index）[9]以及ACC（accuracy）[9]。在實驗對比中，每個聚類算法將分別運行20次，然后取其平均NMI/ARI/ACC得分進行比較。

2.3 與常規(guī)DEC 算法在不同超參數下的對比

針對常規(guī)DEC 算法[12]的敏感超參數問題，本文提出了IDECEL 算法，以集成學習的策略對其解決。本節(jié)實驗將對所提出的IDECEL 算法與DEC 算法在不同超參數λ下的性能進行對比（如圖2、圖3 和圖4所示）。需要注意的是，IDECEL 使用多樣化超參數以構建一組基聚類集合，并不需要選取單一的超參數值。由圖2、圖3 與圖4 可以看出，本文提出的IDECEL 算法不僅比DEC 算法在不同超參數下的平均NMI、ARI、ACC 得分有顯著提升，即使與DEC 在最佳超參數下的性能進行對比，也可以得到更優(yōu)聚類效果，這也驗證了IDECEL 算法在應對敏感超參數、得到更魯棒聚類方面的有效性。

Fig.2 Comparison of NMI scores at different hyperparameters λ圖2 在不同超參數λ下的NMI得分對比

Fig.3 Comparison of ARI scores at different hyperparameters λ圖3 在不同超參數λ下的ARI得分對比

Fig.4 Comparison of ACC scores at different hyperparameters λ圖4 在不同超參數λ下的ACC 得分對比

2.4 與其他深度聚類及集成聚類算法的對比

本節(jié)實驗將所提出的IDECEL 算法與6 個其他聚類算法進行性能對比。這些算法分別是：Kmeans、KCC(K-means-based consensus clustering)[31]、SEC(spectral ensemble clustering)[32]、LWGP(locally weighted graph partitioning)[19]、DEC(deep embedded clustering)[12]以及IDEC(improved deep embedded clustering with local structure preservation)[33]。在這些對比算法中，KCC、SEC 以 及LWGP 是集成聚類算法，DEC 與IDEC 是深度聚類算法。

如表2 所示，本文提出的IDECEL 算法在5 個數據集中均取得了最高的NMI 得分。值得一提的是，在本文實驗中，對每一個數據集，DEC 算法的超參數λ均由人工調至最優(yōu)，而IDECEL 算法則無需針對數據集進行調參（dataset-specific tuning）；即便如此，IDECEL 算法也仍能夠在這些數據集上取得與DEC（在最優(yōu)超參數下）相當或更高的NMI 得分。與此同時，表3 及表4 的ARI 及ACC 得分對比也同樣顯示出本文IDECEL 算法在各個數據集上的顯著優(yōu)勢（表2～表4 中最高分以粗體表示）。

Table 2 NMI scores of different clustering algorithms表2 不同聚類算法的NMI得分對比

Table 3 ARI scores of different clustering algorithms表3 不同聚類算法的ARI得分對比

Table 4 ACC scores of different clustering algorithms表4 不同聚類算法的ACC 得分對比

進一步，本文在表2～表4 的末兩行給出了各個算法的平均得分（average score）和平均排名（average rank）信息。平均得分表示每個算法在5 個數據集上的平均NMI/ARI/ACC 得分；平均排名則表示在一個表格的得分結果之中，每個算法在多個數據集中排名的平均情況。如表2 所示，所提出的IDECEL 算法在5 個數據集中均取得最高NMI 得分，平均排名為1；在5 個數據集中的平均NMI 得分為54.49，高于DEC（在最優(yōu)超參數下）的平均得分，也高于其他5個聚類算法的平均得分。在表3 及表4 的ARI 及ACC 得分中，IDECEL 算法也表現出其在平均得分與平均排名上的優(yōu)勢。

2.5 集成規(guī)模對性能的影響

在本節(jié)實驗中，將測試本文算法以及3 個其他集成聚類算法在不同集成規(guī)模下的性能對比。

Fig.5 Performance of different ensemble clustering algorithms at varying ensemble sizes(NMI)圖5 各集成聚類算法在不同集成規(guī)模下的性能表現(NMI)

Fig.6 Performance of different ensemble clustering algorithms at varying ensemble sizes(ARI)圖6 各集成聚類算法在不同集成規(guī)模下的性能表現(ARI)

Fig.7 Performance of different ensemble clustering algorithms at varying ensemble sizes(ACC)圖7 各集成聚類算法在不同集成規(guī)模下的性能表現(ACC)

在集成聚類中，集成規(guī)模M表示基聚類集合中的成員個數。圖5～圖7 分別給出了各個集成聚類算法在不同集成規(guī)模下的NMI、ARI 和ACC 得分。如圖所示，當集成規(guī)模增加時，各個集成聚類算法的性能往往隨之提升；而本文所提出的IDECEL 算法在不同集成規(guī)模下表現出相當穩(wěn)定的聚類效果。在Gisette 數據集中，雖然LWGP 算法在集成規(guī)模較小時得分高于IDECEL，但是在集成規(guī)模增長到大于20之后，IDECEL 性能則持續(xù)優(yōu)于LWGP。除Gisette 數據集之外，IDECEL 算法在其他4 個數據集上的性能得分均始終優(yōu)于其他對比算法，其中IDECEL 算法在MNIST 和Cifar10 數據集上的優(yōu)勢尤為明顯（如圖5～圖7 所示）。

3 結束語

本文針對常規(guī)DEC算法的敏感超參數問題，提出一種基于集成學習的改進深度嵌入聚類（IDECEL）算法。相比于人工調參以尋求單個最優(yōu)超參數λ的常規(guī)做法，本文利用多樣化超參數λ以構建一組具有差異性的基聚類，進而基于熵理論對基聚類的局部不確定性進行度量，然后結合二部圖構建與分割策略將多個基聚類融合為一個更優(yōu)聚類結果。本文在5 個數據集上進行了實驗，實驗結果驗證了本文算法相比于其他深度聚類和集成聚類算法的性能優(yōu)勢。本文的集成策略不僅可用于改進DEC 算法，未來也可推廣至其他包含敏感超參數的深度或非深度聚類算法，以超參數多樣化再聚類融合的方式緩解其敏感超參數問題，由此提升相關算法的聚類魯棒性。