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

1.華南農(nóng)業(yè)大學(xué) 數(shù)學(xué)與信息學(xué)院，廣州 510642

2.廣州市智慧農(nóng)業(yè)重點(diǎn)實(shí)驗(yàn)室，廣州 510642

3.中山大學(xué) 計(jì)算機(jī)學(xué)院，廣州 510006

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

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

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

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

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

1 基于集成學(xué)習(xí)的改進(jìn)深度嵌入聚類

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

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

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

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

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

每次迭代需要更新的參數(shù)的梯度為：

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

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

其中，πm=表示第i個(gè)基聚類，表示基聚類πm中的第i個(gè)簇，nm表示該基聚類πm中的簇?cái)?shù)量。在基聚類集合中，每一個(gè)基聚類包含若干個(gè)簇，不妨把各個(gè)基聚類中所有簇的集合表示為：

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

1.2 局部加權(quán)與基聚類集成

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

其中，?表示兩個(gè)簇的交集，|Ci|表示簇Ci中樣本數(shù)量?；诨垲惣夕爸蠱個(gè)基聚類具有相互獨(dú)立性的假設(shè)，簇Ci相對(duì)于整個(gè)基聚類集合Π的熵（即不確定性）可計(jì)算為：

各個(gè)簇的不確定性（或不穩(wěn)定性），可視作與其可靠度呈負(fù)相關(guān)。在其基礎(chǔ)上，計(jì)算一個(gè)集成驅(qū)動(dòng)的簇指標(biāo)（ensemble-driven cluster index，ECI）來作為簇可靠性度量，如下：

進(jìn)一步，以樣本集合X與簇集合C的并集作為節(jié)點(diǎn)集，以ECI 作為邊的權(quán)值，構(gòu)建一個(gè)加權(quán)二部圖（bipartite graph），表示如下：

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

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

2 實(shí)驗(yàn)結(jié)果與分析

在本章中，將在5 個(gè)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，并對(duì)IDECEL 算法與其他多個(gè)深度聚類及集成聚類算法進(jìn)行對(duì)比與分析。

2.1 實(shí)驗(yàn)設(shè)置

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

2.2 數(shù)據(jù)集與評(píng)價(jià)指標(biāo)

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

Table 1 Dataset of experiment表1 實(shí)驗(yàn)數(shù)據(jù)集

為對(duì)比不同聚類算法的性能，本文采用了三種常用的聚類評(píng)價(jià)指標(biāo)，分別是NMI（normalized mutual information）[13]、ARI（adjusted Rand index）[9]以及ACC（accuracy）[9]。在實(shí)驗(yàn)對(duì)比中，每個(gè)聚類算法將分別運(yùn)行20次，然后取其平均NMI/ARI/ACC得分進(jìn)行比較。

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

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

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

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

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

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

本節(jié)實(shí)驗(yàn)將所提出的IDECEL 算法與6 個(gè)其他聚類算法進(jìn)行性能對(duì)比。這些算法分別是：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]。在這些對(duì)比算法中，KCC、SEC 以 及LWGP 是集成聚類算法，DEC 與IDEC 是深度聚類算法。

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

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

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

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

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

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

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

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

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

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

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

3 結(jié)束語

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