基于局部結(jié)構(gòu)保持的高維數(shù)據(jù)半監(jiān)督深度嵌入聚類算法*

曹 超，李夢(mèng)利，陽(yáng)樹洪，李春貴

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

聚類分析利用數(shù)據(jù)的內(nèi)在結(jié)構(gòu)將數(shù)據(jù)劃分為互不相交的子集，是數(shù)據(jù)分析中的重要課題，長(zhǎng)期以來(lái)受到機(jī)器學(xué)習(xí)和統(tǒng)計(jì)分析領(lǐng)域?qū)W者的廣泛關(guān)注。真實(shí)數(shù)據(jù)中存在一些先驗(yàn)知識(shí)，這些先驗(yàn)知識(shí)由少量標(biāo)記數(shù)據(jù)或?qū)＜医o出的成對(duì)約束表示，但純粹的無(wú)監(jiān)督聚類算法沒有考慮數(shù)據(jù)中可能存在的先驗(yàn)約束關(guān)系或者監(jiān)督信息，使得學(xué)習(xí)難度增大。半監(jiān)督聚類算法[1-4]在大量的無(wú)監(jiān)督數(shù)據(jù)中僅引入少量的先驗(yàn)信息即可顯著提高聚類性能，從而成為近年來(lái)的重要研究方向。

半監(jiān)督聚類算法大體可以分為兩類。第一類半監(jiān)督聚類可同時(shí)利用未標(biāo)記的、足夠多的數(shù)據(jù)和一些先驗(yàn)的知識(shí)改進(jìn)聚類性能。例如，Hong等[5]提出了一種半監(jiān)督的深度學(xué)習(xí)框架，可以從小規(guī)模的圖像中學(xué)習(xí)更多的判別信息，并將其轉(zhuǎn)移到大規(guī)模數(shù)據(jù)的分類任務(wù)中。第二類半監(jiān)督聚類以強(qiáng)監(jiān)督的方式使用先驗(yàn)知識(shí)，使用標(biāo)簽信息直接指導(dǎo)聚類中心的學(xué)習(xí)，并以數(shù)據(jù)驅(qū)動(dòng)的方式對(duì)樣本進(jìn)行聚類以學(xué)習(xí)聚類中心，并得到對(duì)聚類有效的表示。例如，Chen等[6]提出一種新的半監(jiān)督聯(lián)合學(xué)習(xí)框架，通過(guò)在聯(lián)合優(yōu)化損失函數(shù)中集成少量標(biāo)簽信息來(lái)學(xué)習(xí)特征嵌入空間和集群分配。

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

此外，深度聚類算法之所以取得成功有兩個(gè)重要的因素。首先是深度神經(jīng)網(wǎng)絡(luò)強(qiáng)大的特征表示能力以及計(jì)算能力，其次是不同的算法在特征學(xué)習(xí)過(guò)程中對(duì)特征施加的約束，使得深度神經(jīng)網(wǎng)絡(luò)模型在訓(xùn)練過(guò)程中學(xué)習(xí)到更適應(yīng)于聚類任務(wù)的深度特征。盡管深度聚類算法取得了很大的突破，但是很多深度聚類算法在特征學(xué)習(xí)過(guò)程中沒有保持特征之間的局部連接結(jié)構(gòu)，導(dǎo)致從原始數(shù)據(jù)空間到低維特征空間的轉(zhuǎn)換過(guò)程中破壞了數(shù)據(jù)的特征結(jié)構(gòu)，從而產(chǎn)生沒有表示意義的特征，在一定程度上影響聚類的性能。

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

1 半監(jiān)督深度嵌入聚類

半監(jiān)督深度嵌入聚類(SDEC)[14]從預(yù)處理自動(dòng)編碼器開始，然后移除解碼器。其余編碼器通過(guò)優(yōu)化以下目標(biāo)進(jìn)行微調(diào)：

(1)

其中，qij是嵌入點(diǎn)zi和聚類中心μj之間的相似性，由學(xué)生t-SNE分布函數(shù)測(cè)量：

(2)

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

(3)

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

2 改進(jìn)的半監(jiān)督深度嵌入聚類

L=Lu+λLs+γLr，

(4)

其中,Lr、Lu、Ls分別為重構(gòu)損失、聚類損失、成對(duì)約束損失，λ是由用戶定義的權(quán)衡參數(shù)，γ>0為控制重構(gòu)程度的參數(shù)。當(dāng)γ=0時(shí)，式(4)降為SDEC的目標(biāo)。

本算法的總體框架如圖1所示，使用預(yù)先訓(xùn)練的堆疊自動(dòng)編碼器(Stacked AutoEncoder,SAE)的編碼層來(lái)初始化DNN結(jié)構(gòu)。將成對(duì)約束添加到嵌入層z，以指導(dǎo)特征表示的學(xué)習(xí)。用重構(gòu)損失保證嵌入空間保持?jǐn)?shù)據(jù)生成分布的局部結(jié)構(gòu)。q表示每個(gè)數(shù)據(jù)點(diǎn)的軟分配，并用于計(jì)算Kullback-Leibler (KL)發(fā)散損失。

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

2.1 聚類損失和參數(shù)初始化

P和Q之間的KL散度被定義為聚類損失，其中Q為軟標(biāo)簽分布,是通過(guò)學(xué)生t-SNE分布測(cè)量得出，P是從Q推導(dǎo)出來(lái)的目標(biāo)分布。也就是說(shuō)，聚類損失被定義為

(5)

其中,KL用于測(cè)量?jī)蓚€(gè)概率分布之間的非對(duì)稱差的散度，通過(guò)式(3)和式(2)定義P和Q。

矩陣A設(shè)計(jì)的思想在于，訓(xùn)練時(shí)施加一個(gè)約束：將相同類別的點(diǎn)在潛在特征空間中彼此接近，而不同類別的點(diǎn)之間彼此遠(yuǎn)離。為此，成對(duì)約束損失定義為

(6)

2.2 局部結(jié)構(gòu)保護(hù)

(7)

為了保證聚類的有效性，用于預(yù)處理的堆疊式去噪自動(dòng)編碼器不再適用。因?yàn)榫垲悜?yīng)該在干凈數(shù)據(jù)的特征上執(zhí)行，而不是在去噪自動(dòng)編碼器中使用噪聲數(shù)據(jù)，所以本文直接去除噪聲，堆疊式去噪自動(dòng)編碼器退化為欠完備自動(dòng)編碼器。

至此，ISDEC 算法的總損失函數(shù)如下：

(8)

其中，Lu和Ls聯(lián)合成為SDEC的總體損失函數(shù)Lc，用以實(shí)現(xiàn)特征數(shù)據(jù)與聚類中心改進(jìn)的分配結(jié)果，Lr用于保持特征數(shù)據(jù)從預(yù)訓(xùn)練特征空間到微調(diào)特征空間的局部結(jié)構(gòu)，使得學(xué)習(xí)到的特征保持固有本征結(jié)構(gòu)，從而進(jìn)一步提升特征學(xué)習(xí)和聚類任務(wù)的性能。λ是由用戶定義的權(quán)衡參數(shù)，γ為控制嵌入空間失真程度的系數(shù)。

2.3 優(yōu)化

利用小批量梯度下降算法結(jié)合反向傳播算法最小化目標(biāo)函數(shù)(8)，同時(shí)對(duì)聚類中心μj，以及深度編碼器參數(shù)θe和θd進(jìn)行優(yōu)化。

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

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

(9)

L損失函數(shù)對(duì)于特征zi的梯度計(jì)算如下：

(10)

注意，上述推導(dǎo)來(lái)自SDEC。然后給定一個(gè)具有m個(gè)樣本和學(xué)習(xí)率η的小批量，μj被更新為

(11)

解碼器的權(quán)重W′通過(guò)以下方式更新:

(12)

編碼器的權(quán)重W通過(guò)以下方式更新:

(13)

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

(14)

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

算法1：基于局部結(jié)構(gòu)保持的改進(jìn)半監(jiān)督深度嵌入聚類

輸入：輸入數(shù)據(jù):X;聚類數(shù):K;目標(biāo)分布更新間隔:T;停止閾值:δ;最大迭代:MaxIter。

輸出：雙自動(dòng)編碼器的權(quán)重W和W′；聚類中心μ和標(biāo)簽s。

①根據(jù)3.1節(jié)初始化μ、W和W′

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

③ if iter%T== 0 then

⑥ 保存上次標(biāo)簽分配:sold=s

⑦ 通過(guò)式(14)計(jì)算新標(biāo)簽分配s

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

⑨ 停止訓(xùn)練

⑩選擇一批樣本S∈X

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

3.1 數(shù)據(jù)集

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

表1 數(shù)據(jù)集的統(tǒng)計(jì)數(shù)據(jù)Table 1 Statistics for dataset

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

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

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

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

3.3 結(jié)果與分析

對(duì)比方法的結(jié)果分別來(lái)自對(duì)應(yīng)的論文公開發(fā)布的代碼，如果某個(gè)算法不適用于特定數(shù)據(jù)集，聚類結(jié)果就用N/A 代替。由表2和表3可以看出，本文所提出的方法優(yōu)于其他6種先進(jìn)方法。

表2 ACC 測(cè)量的聚類結(jié)果Table 2 Clustering results of ACC measurements

表3 NMI 測(cè)量的聚類結(jié)果Table 3 Clustering results of NMI measurements

續(xù)表

Continued table

具體而言，KM-CST的性能優(yōu)于K-means，表明結(jié)合成對(duì)信息提高了聚類性能。與傳統(tǒng)的 K-means 和 SMKL相比，深度網(wǎng)絡(luò)可以學(xué)習(xí)更具表示能力的特征。雖然 DEC 和 IDEC 也利用了數(shù)據(jù)的深層特征，但它們忽略了隱藏在少量標(biāo)簽數(shù)據(jù)中的信息。SDEC使用成對(duì)約束來(lái)指導(dǎo)聚類過(guò)程，但沒在特征學(xué)習(xí)過(guò)程中保持特征之間的局部連接結(jié)構(gòu)。以上結(jié)果表明本算法的局部結(jié)構(gòu)保持與成對(duì)約束相結(jié)合對(duì)聚類的效果有更好的改進(jìn)作用。

為了進(jìn)一步說(shuō)明所提方法的優(yōu)越性，在圖2中清晰地顯示了ISDEC和SDEC在MNIST數(shù)據(jù)集上訓(xùn)練過(guò)程中的準(zhǔn)確性，可見ISDEC優(yōu)于SDEC。

圖2 ISDEC和SDEC在MNIST訓(xùn)練期間的準(zhǔn)確性Fig.2 Accuracy of ISDEC and SDEC during MNIST training

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

The differences between clusters are shown in different colors

圖3 訓(xùn)練過(guò)程中MNIST子集聚類結(jié)果的可視化

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

4 結(jié)論

針對(duì)高維數(shù)據(jù)的半監(jiān)督聚類問題，本文提出了一種改進(jìn)半監(jiān)督深度嵌入聚類(ISDEC)算法，即在現(xiàn)有算法的基礎(chǔ)上，著重考慮了高維數(shù)據(jù)的內(nèi)在局部保持問題。ISDEC首先通過(guò)優(yōu)化基于KL散度的聚類損失和半監(jiān)督的成對(duì)約束損失來(lái)實(shí)現(xiàn)數(shù)據(jù)從原始高維空間到特征空間的映射，并通過(guò)引入一個(gè)基于自編碼的局部保持損失來(lái)保持深度特征學(xué)習(xí)過(guò)程中數(shù)據(jù)表達(dá)之間的局部結(jié)構(gòu)。然后，將深度聚類網(wǎng)絡(luò)融合到一個(gè)統(tǒng)一的框架中，對(duì)潛在空間的特征進(jìn)行聚類，從而有效利用樣本之間的關(guān)系。本文在包括基因數(shù)據(jù)在內(nèi)的若干高維數(shù)據(jù)集上進(jìn)行了大量的實(shí)驗(yàn)研究，定性分析和定量指標(biāo)都表明，本算法在學(xué)習(xí)數(shù)據(jù)的深層特征表達(dá)的同時(shí)，能有效保持?jǐn)?shù)據(jù)的局部結(jié)構(gòu)，從而取得較好的半監(jiān)督聚類性能。