基于局部結構保持的高維數據半監督深度嵌入聚類算法*

曹 超，李夢利，陽樹洪，李春貴

(廣西科技大學電氣電子與計算機科學學院，廣西柳州 545006)

聚類分析利用數據的內在結構將數據劃分為互不相交的子集，是數據分析中的重要課題，長期以來受到機器學習和統計分析領域學者的廣泛關注。真實數據中存在一些先驗知識，這些先驗知識由少量標記數據或專家給出的成對約束表示，但純粹的無監督聚類算法沒有考慮數據中可能存在的先驗約束關系或者監督信息，使得學習難度增大。半監督聚類算法[1-4]在大量的無監督數據中僅引入少量的先驗信息即可顯著提高聚類性能，從而成為近年來的重要研究方向。

半監督聚類算法大體可以分為兩類。第一類半監督聚類可同時利用未標記的、足夠多的數據和一些先驗的知識改進聚類性能。例如，Hong等[5]提出了一種半監督的深度學習框架，可以從小規模的圖像中學習更多的判別信息，并將其轉移到大規模數據的分類任務中。第二類半監督聚類以強監督的方式使用先驗知識，使用標簽信息直接指導聚類中心的學習，并以數據驅動的方式對樣本進行聚類以學習聚類中心，并得到對聚類有效的表示。例如，Chen等[6]提出一種新的半監督聯合學習框架，通過在聯合優化損失函數中集成少量標簽信息來學習特征嵌入空間和集群分配。

傳統的半監督聚類大多通過對譜聚類、非負矩陣分解和典型相關分析等淺層聚類模型進行改進，或將K-means和線性判別分析(Linear Discriminant Analysis,LDA)等算法進行結合以引入監督信息[7]。但這些方法都屬于淺層模型，無法有效表達高維數據間的高層語義信息，如近年來出現的基因信息挖掘，即屬于典型的高維數據分析問題。近年來，深度聚類引起了廣泛關注，研究者通過學習數據的低維表示，有效緩解傳統聚類算法在面對高維輸入數據時的退化問題。例如，Yang等[8]提出的深度聚類網絡(Deep Clustering Network，DCN)將自動編碼器與K-means算法相結合；Peng等[9]提出的深度子空間聚類(Deep Subspace Clustering，DSC)引入一種新穎的自動編碼器架構，學習有利于子空間聚類的非線性映射[10]。為了進一步提高高維數據的聚類性能，有研究者提出了一些端到端的深度聚類方法，將深度神經網絡(Deep Neural Networks,DNN)融合到聚類中。例如，Xie等[11]在2016年提出的深度嵌入聚類(Deep Embedding Clustering，DEC)，可學習數據的聚類特征并以自學習的方式劃分數據。Li等[12]在2018年提出的判別提升聚類(Discriminatively Boosted Image Clustering，DBIC)算法使用卷積自動編碼器改進DEC，由于該算法使用卷積網絡，因此其在圖像數據集上的聚類性能優于DEC。

此外，深度聚類算法之所以取得成功有兩個重要的因素。首先是深度神經網絡強大的特征表示能力以及計算能力，其次是不同的算法在特征學習過程中對特征施加的約束，使得深度神經網絡模型在訓練過程中學習到更適應于聚類任務的深度特征。盡管深度聚類算法取得了很大的突破，但是很多深度聚類算法在特征學習過程中沒有保持特征之間的局部連接結構，導致從原始數據空間到低維特征空間的轉換過程中破壞了數據的特征結構，從而產生沒有表示意義的特征，在一定程度上影響聚類的性能。

Peng等[13]在基于稀疏先驗的深度子空間聚類算法中指出，欠完備自動編碼學習樣本在嵌入空間中特征表達的同時，保持其在原始空間中的局部結構。受此啟發，本文提出基于局部結構保持的改進半監督深度嵌入聚類(Improved Semi-supervised Deep Embedded Clustering,ISDEC)算法。首先，使用欠完備自動編碼器建立輸入樣本及其潛在表示之間的映射關系，從而剔除樣本中的不利因素，以及保留數據生成分布的局部結構。其次，將欠完備自動編碼器納入半監督深度嵌入聚類(Semi-supervised Deep Embedded Clustering,SDEC)框架，使該框架可以在保持局部結構的情況下，聯合進行聚類和特征表達學習的同步優化。最后，本文采用小批量隨機梯度下降(Stochastic Gradient Descent,SGD)和反向傳播算法對所提出的ISDEC算法進行優化。

1 半監督深度嵌入聚類

半監督深度嵌入聚類(SDEC)[14]從預處理自動編碼器開始，然后移除解碼器。其余編碼器通過優化以下目標進行微調：

(1)

其中，qij是嵌入點zi和聚類中心μj之間的相似性，由學生t-SNE分布函數測量：

(2)

并且式(1)中的pij是目標分布，定義為

(3)

其中,矩陣A用來描述成對約束中必須鏈接約束(Must-Link,ML)和不能鏈接約束(Cannot-Link,CL)，j和j′表示k個聚類中心u的索引,aik是矩陣A的第i行k列的元素。當xi和xk被分配給同一簇時，aik=1。如果xi和xk滿足不能鏈接的約束，aik=-1。此矩陣中的其他元素均為零。

2 改進的半監督深度嵌入聚類

L=Lu+λLs+γLr，

(4)

其中,Lr、Lu、Ls分別為重構損失、聚類損失、成對約束損失，λ是由用戶定義的權衡參數，γ>0為控制重構程度的參數。當γ=0時，式(4)降為SDEC的目標。

本算法的總體框架如圖1所示，使用預先訓練的堆疊自動編碼器(Stacked AutoEncoder,SAE)的編碼層來初始化DNN結構。將成對約束添加到嵌入層z，以指導特征表示的學習。用重構損失保證嵌入空間保持數據生成分布的局部結構。q表示每個數據點的軟分配，并用于計算Kullback-Leibler (KL)發散損失。

圖1 ISDEC算法框架Fig.1 Framework of ISDEC algorithm

2.1 聚類損失和參數初始化

P和Q之間的KL散度被定義為聚類損失，其中Q為軟標簽分布,是通過學生t-SNE分布測量得出，P是從Q推導出來的目標分布。也就是說，聚類損失被定義為

(5)

其中,KL用于測量兩個概率分布之間的非對稱差的散度，通過式(3)和式(2)定義P和Q。

矩陣A設計的思想在于，訓練時施加一個約束：將相同類別的點在潛在特征空間中彼此接近，而不同類別的點之間彼此遠離。為此，成對約束損失定義為

(6)

2.2 局部結構保護

(7)

為了保證聚類的有效性，用于預處理的堆疊式去噪自動編碼器不再適用。因為聚類應該在干凈數據的特征上執行，而不是在去噪自動編碼器中使用噪聲數據，所以本文直接去除噪聲，堆疊式去噪自動編碼器退化為欠完備自動編碼器。

至此，ISDEC 算法的總損失函數如下：

(8)

其中，Lu和Ls聯合成為SDEC的總體損失函數Lc，用以實現特征數據與聚類中心改進的分配結果，Lr用于保持特征數據從預訓練特征空間到微調特征空間的局部結構，使得學習到的特征保持固有本征結構，從而進一步提升特征學習和聚類任務的性能。λ是由用戶定義的權衡參數，γ為控制嵌入空間失真程度的系數。

2.3 優化

利用小批量梯度下降算法結合反向傳播算法最小化目標函數(8)，同時對聚類中心μj，以及深度編碼器參數θe和θd進行優化。

由于局部保持損失只對特征數據進行約束，而沒有涉及聚類中心的計算，因此總體損失函數L對聚類中心μj具有梯度：

(pij-qij)(zi-μj)。

(9)

L損失函數對于特征zi的梯度計算如下：

(10)

注意，上述推導來自SDEC。然后給定一個具有m個樣本和學習率η的小批量，μj被更新為

(11)

解碼器的權重W′通過以下方式更新:

(12)

編碼器的權重W通過以下方式更新:

(13)

更新目標分布，目標分布P用作“基本事實”軟標簽，但也依賴于預測的軟標簽。因此，為避免不穩定，不應僅使用一批數據在每次迭代中更新P。在實踐中，本文在每T次迭代中使用所有嵌入點更新目標分布。更新規則見式(2)和式(3)。更新目標分布時，以最大概率的qij為xi的標簽計算如下：

(14)

其中,qij由式(2)計算。如果目標分布的兩次連續更新之間的標簽分配變化(百分比)小于閾值ε，將停止訓練。以下算法1總結了整個算法。

算法1：基于局部結構保持的改進半監督深度嵌入聚類

輸入：輸入數據:X;聚類數:K;目標分布更新間隔:T;停止閾值:δ;最大迭代:MaxIter。

輸出：雙自動編碼器的權重W和W′；聚類中心μ和標簽s。

①根據3.1節初始化μ、W和W′

②for iter∈{0,1,…,MaxIter} do

③ if iter%T== 0 then

⑥ 保存上次標簽分配:sold=s

⑦ 通過式(14)計算新標簽分配s

⑧ if sum(sold≠s)/n<εthen

⑨ 停止訓練

⑩選擇一批樣本S∈X

3 驗證實驗

3.1 數據集

為了驗證所提方法的聚類性能，本文在4個大規模數據集(MNIST、USPS、REUTERS-10K和Fashion-MNIST)和2個基因數據集(LUNG和GLIOMA)上進行實驗。MNIST由70 000個28×28像素大小的手寫數字組成；USPS包含9 298張灰度圖像；REUTERS-10K包含大約810 000個用分類樹標注的英語新聞故事[15]，本文使用4個根類別：公司/工業、政府/社會、市場和經濟作為標簽，排除了所有帶有多個標簽的文檔，隨機抽樣10 000個例子的子集，并計算2 000個最常見單詞的tf-idf特征；Fashion-MNIST包含60 000個訓練圖像和10 000個測試圖像，每張圖片都以28×28像素的灰度顯示。LUNG包含5類共203個樣本，每個樣本有12 600個基因，去除標準差小于50個表達單元的基因，得到203個樣本3 312個基因的數據集；GLIOMA包含4類共50個樣本，每個樣本有12 625個基因，經過預處理得到了一個包含50個樣本和4 434個基因的數據集。

表1 數據集的統計數據Table 1 Statistics for dataset

3.2 實驗設置

將編碼器網絡設置為一個全連接的多層感知器(MLP)，除基因數據以外的數據集的維數為d-500-500-2 000-10，基因數據由于樣本少而特征多，故采用維數為d-1 000-100，其中d為輸入數據(特征)的維數。解碼器網絡的數據集維數與編碼器網絡的數據集維數是顛倒的，即相應的解碼器網絡的數據集維數分別為10-2 000-500-500-d和100-1 000-d。深度編碼器的所有內層除了輸入層、輸出層和嵌入層外，所使用的激活函數都是ReLU非線性函數[16]。使用與SDEC相同的參數設置對自動編碼器進行預訓練和微調，最大限度地減少參數調整的影響，以確保實驗結果的改進是本文提出方法的貢獻。

對于每個數據集，根據真實標簽隨機生成成對約束矩陣A。本文從數據集中隨機選擇兩個數據點:如果兩個數據點共享同一個標簽，將生成一個必須鏈接約束；否則，將生成一個不可鏈接的約束。SGD的學習率為0.01。收斂閾值tol%設置為0.1%。對于所有算法，本文將聚類的數量K設為真實標簽類別的數量。參數λ設置為10-5。為了評價聚類結果，本文采用兩個標準評價指標:準確度(ACC)和歸一化互信息(NMI)。

本文算法與K-means[1]、深度嵌入聚類(DEC)[5]、成對約束K-means (KM-CST)[17]、改進的深度嵌入聚類(IDEC)[18]、自加權多核學習(SMKL)[10]、半監督深度嵌入聚類(SDEC)[14]算法作聚類性能對比，以此證明本文算法在聚類方面的有效性。

3.3 結果與分析

對比方法的結果分別來自對應的論文公開發布的代碼，如果某個算法不適用于特定數據集，聚類結果就用N/A 代替。由表2和表3可以看出，本文所提出的方法優于其他6種先進方法。

表2 ACC 測量的聚類結果Table 2 Clustering results of ACC measurements

表3 NMI 測量的聚類結果Table 3 Clustering results of NMI measurements

續表

Continued table

具體而言，KM-CST的性能優于K-means，表明結合成對信息提高了聚類性能。與傳統的 K-means 和 SMKL相比，深度網絡可以學習更具表示能力的特征。雖然 DEC 和 IDEC 也利用了數據的深層特征，但它們忽略了隱藏在少量標簽數據中的信息。SDEC使用成對約束來指導聚類過程，但沒在特征學習過程中保持特征之間的局部連接結構。以上結果表明本算法的局部結構保持與成對約束相結合對聚類的效果有更好的改進作用。

為了進一步說明所提方法的優越性，在圖2中清晰地顯示了ISDEC和SDEC在MNIST數據集上訓練過程中的準確性，可見ISDEC優于SDEC。

圖2 ISDEC和SDEC在MNIST訓練期間的準確性Fig.2 Accuracy of ISDEC and SDEC during MNIST training

通過在訓練過程中對嵌入的特征空間進行可視化，可進一步顯示本算法在特征學習過程中的局部保持效果。圖3顯示了從MNIST數據集中隨機選擇1 000個樣本的學生t-SNE可視化，并將潛在表示z映射到 2D 空間。從聚類結果的變化趨勢可以看出，隨著訓練次數的增加，不同簇中的樣本更容易區分，同一簇中的樣本也更接近，這表明學習到的特征空間更適合聚類任務。

The differences between clusters are shown in different colors

圖3 訓練過程中MNIST子集聚類結果的可視化

Fig.3 Visualization of MNIST sub-cluster class results during training

4 結論

針對高維數據的半監督聚類問題，本文提出了一種改進半監督深度嵌入聚類(ISDEC)算法，即在現有算法的基礎上，著重考慮了高維數據的內在局部保持問題。ISDEC首先通過優化基于KL散度的聚類損失和半監督的成對約束損失來實現數據從原始高維空間到特征空間的映射，并通過引入一個基于自編碼的局部保持損失來保持深度特征學習過程中數據表達之間的局部結構。然后，將深度聚類網絡融合到一個統一的框架中，對潛在空間的特征進行聚類，從而有效利用樣本之間的關系。本文在包括基因數據在內的若干高維數據集上進行了大量的實驗研究，定性分析和定量指標都表明，本算法在學習數據的深層特征表達的同時，能有效保持數據的局部結構，從而取得較好的半監督聚類性能。