基于重構誤差的深度聚類方法

鄧 祥，俞 璐，謝 鈞，呂昊遠，姚昌華

(1.陸軍工程大學，江蘇 南京 210001；2.南京信息工程大學，江蘇 南京 210044)

0 引 言

聚類本質(zhì)上是一個物以類聚的過程,通常在無監(jiān)督條件下,依靠發(fā)掘數(shù)據(jù)潛在的結構、性質(zhì)和規(guī)律實現(xiàn)聚類目的?，F(xiàn)有的聚類模型以是否使用深度學習可以劃分為傳統(tǒng)聚類和深度聚類兩類。傳統(tǒng)聚類可以劃分為原型聚類、密度聚類、圖聚類、層次聚類等。原型聚類算法用原型作為每個簇的代表,通過度量樣本與原型之間的距離確定樣本的歸屬,典型的算法有k-means[1]、高斯混合模型(GMM)[2]等。密度聚類的主要目標是尋找被低密度區(qū)域分離的高密度區(qū)域，典型的算法是Density-Based Spatial Clustering of Applications with Noise (DBSCAN)[3]。從圖論中演化而來的圖聚類模型通過構建一個基于相似度的無向加權圖把聚類問題轉化為圖的最優(yōu)劃分問題,典型的算法是spectral clustering(SC)[4]。層次聚類通過度量數(shù)據(jù)節(jié)點之間的相似性或者距離構建一個樹形結構在不同層面上對數(shù)據(jù)集進行劃分,典型的算法是AGglomerative NESting (AGNES)。傳統(tǒng)聚類算法從不同的角度出發(fā)挖掘數(shù)據(jù)簇的聚類規(guī)律,針對這個規(guī)律設計明確的聚類過程實現(xiàn)聚類簇的劃分。傳統(tǒng)聚類算法獨立地進行特征提取與數(shù)據(jù)聚類,聚類算法的輸入特征完全依賴于特征預處理,而多數(shù)特征提取算法是非目標導向算法,提取的特征未必是利于聚類的特征,這些特征提取算法包括線性的PCA[5]、非線性的核方法(kernel methods)[6]等。近些年深度學習因其強大的非線性擬合能力和特征表示能力可以很好地緩解傳統(tǒng)聚類算法的缺陷,將深度學習引入無監(jiān)督聚類領域形成的深度聚類模型已經(jīng)顯示出了優(yōu)越性。在深度聚類領域尚在探索階段的今天,該文提出一種全新的深度聚類模型,該模型從不同的角度出發(fā)探索深度聚類的可行性方案。

1 相關工作

用于聚類的深度模型有多種選擇,較為常用的包括自編碼器[7]、圖神經(jīng)網(wǎng)絡和生成模型等。近年來,圖卷積神經(jīng)網(wǎng)絡提取特征考慮到數(shù)據(jù)的結構,能夠提取利于聚類的特征,故用圖卷積神經(jīng)網(wǎng)絡完成聚類任務成為新興的研究方向之一,基于圖神經(jīng)網(wǎng)絡的深度聚類模型中較成功的有Embedding Graph Auto-Encoder (EGAE)[8]、Deep Attentional Embedded Graph Clustering (DAEGC)[9]、Structural Deep Clustering Network (SDCN)[10]、Adaptive Graph Convolution (AGC)[11]、Adversarial Graph Auto-Encoders (AGAE)[12]。其中AGAE的輸入是相似性矩陣,利用圖卷積神經(jīng)網(wǎng)絡處理相似性矩陣提取特征,并把它與特征先驗分布中得到的特征一同進行對抗性訓練,得到一個能完成聚類的概率分布。生成模型因其能夠使用神經(jīng)網(wǎng)絡捕獲數(shù)據(jù)分布并產(chǎn)生真實的未見樣本而受到人們廣泛關注,其中GAN[13]和VAE[14]是最成功的生成模型。將生成模型用于聚類任務是深度聚類的研究方向之一?；谏赡Ｐ偷木垲惙譃椋夯谧兎肿跃幋a器(VAE)的聚類和基于生成對抗模型(GAN)的聚類。變分自編碼器假設樣本服從高斯分布,通過變分推斷法求出樣本后驗概率。將變分自編碼器引入聚類中成功的模型有Variational Deep Embedding (VaDE)[15]、Gaussian Mixture Variational AutoEncoder (GMVAE)[16]。VaDE在變分自編碼器的基礎上加上Mixture-of-Gaussians,使用變分推斷法推斷出樣本所屬簇的后驗概率,進而對數(shù)據(jù)樣本進行簇推斷?；谏蓪咕W(wǎng)絡的深度聚類模型借助GAN網(wǎng)絡捕獲數(shù)據(jù)分布的能力尋找樣本的后驗概率。這方面突出的模型有ClusteringGAN[17]、Categorical Generative Adversarial Networks (CatGAN)[18]、InfoGAN[19]等。InfoGAN利用變分法推斷出生成器輸入與判別器輸出之間的互信息,用于GAN的對抗性訓練中。當訓練完成后，判別器可以輸出輸入樣本屬于各簇的概率,從而完成聚類任務。

自編碼器重構樣本時可以產(chǎn)生表征數(shù)據(jù)本質(zhì)的非線性映射特征,基于自編碼器模型的聚類方案有K-means-friendly Spaces (DCN)[20]、Adversarial AutoEncoders(AAE)[21]、Deep Embedded Clustering (DEC)[22]等，其中DEC模型在自編碼器的基礎上提出使用神經(jīng)網(wǎng)絡同時學習特征表示和聚類分配。它在潛在的特征空間中設計了一個軟分布和一個輔助概率分布,通過讓兩個分布的KL散度最小化實現(xiàn)聚類目的。DCN模型通過聯(lián)合優(yōu)化特征空間和k-means算法,同步完成了聚類任務和尋找適合k-means聚類的特征子空間。文獻[23]提出的模型在DSC-NET的基礎上引入二元分類模塊用于學習更抽象更具有區(qū)分度的特征,它同時與DSC-NET的自表示層進行協(xié)同訓練達到聚類目的。針對無監(jiān)督聚類領域經(jīng)常出現(xiàn)的錯誤預測和過置信現(xiàn)象,文獻[24]借鑒半監(jiān)督聚類的思想,提出了基于魯棒學習的改進無監(jiān)督圖像聚類模型(Robust learning for Unsupervised Clustering，RUC),有效地解決了上述問題。

目前基于自編碼器的深度聚類模型更關注自編碼器的數(shù)據(jù)壓縮能力,并基于中間特征(編碼器輸出)設計聚類的損失函數(shù)。該文關注自編碼器的重構能力,提出了基于重構誤差(解碼器輸出)設計損失函數(shù),并對中間特征加以約束的端到端深度聚類方案,對自編碼器應用于聚類任務做出了新的探索。

受生成模型和自編碼器的啟發(fā),該文提出一種新的基于自編碼器的深度聚類模型:基于重構誤差的深度聚類方法(Deep Clustering Method Based on Reconstruction Error，DCMBORE)。該模型在自編碼器框架下,通過構建K個不同的聚類子空間,根據(jù)樣本在各子空間的映射獲得K個生成樣本,并利用K個生成樣本的概率加權和樣本重構原始樣本,通過最小化重構誤差同時對子空間加以約束,最終實現(xiàn)對樣本的聚類。主要貢獻如下：

·探索了以重構誤差為聚類目標的深度聚類方案。

·該模型能對同一簇下不同的小簇(MiniCluster)進行區(qū)分。

2 基于重構誤差的深度聚類方法

2.1 重構差異的思想

聚類的目標是通過對無標記樣本的學習來揭示和挖掘數(shù)據(jù)內(nèi)在的結構、性質(zhì)和規(guī)律。對于數(shù)據(jù)內(nèi)蘊規(guī)律不同的先驗和假設將導出不同的聚類模型。假設高維空間數(shù)據(jù)樣本呈現(xiàn)出K個不同的簇,其本質(zhì)原因在于數(shù)據(jù)采樣于高維空間中的K個低維子空間,分別對應K個簇。高維樣本空間和低維子空間之間的非線性映射揭示了數(shù)據(jù)的內(nèi)在規(guī)律和本質(zhì),學習這些映射就是聚類的關鍵。該文提出一種端到端的深度聚類模型,借助神經(jīng)網(wǎng)絡強大的非線性逼近能力,通過學習高維樣本空間和K個低維子空間之間的映射完成聚類任務。

2.2 子空間約束

為保證聚類效果,希望不同簇的子空間盡可能遠離,同時每個簇的子空間盡可能收縮在一定范圍內(nèi)。假定有K個簇,μi是簇i對應的子空間內(nèi)的特征中心,xni是樣本n映射到子空間i的低維特征。Sw表示子空間內(nèi)特征的散度,Sb表示子空間之間的距離。該文對子空間做如下約束：

(1)

(2)

其中，d1、d2是超參數(shù)，[x]+=max(0,x)表示正部函數(shù)。最小化Sw將使每個子空間內(nèi)的低維特征都收縮在半徑為d1的超球內(nèi),以此保證同一簇內(nèi)高維空間樣本具有一定程度的多樣性。最小化Sb將使任意兩個子空間的特征中心的距離超過d2,以此保證不同簇子空間的分離性。

2.3 基于重構誤差的深度聚類方法

L=R+Sw+Sb=

α≥1

(3)

在模型中引入加權指數(shù)用來控制融合樣本與原始樣本的重構速度,增加聚類模型的靈活性和自由度。

3 實驗結果與討論

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

(1)MNIST數(shù)據(jù)集[25]包含了70 000張手寫數(shù)字的圖像，其中60 000個訓練樣本,10 000個測試樣本，該圖像的像素大小為28×28。該數(shù)據(jù)集包含了10個大類別(0～9),幾百個小類別(每個數(shù)字不同形態(tài)的寫法)。

(2)USPS數(shù)據(jù)集與MNIST類似,包含了10個類別的手寫數(shù)字,訓練集共7 291個樣本,測試集共2 007個樣本，每個樣本都是16×16的灰度圖像。

(3)Fashion-MNIST數(shù)據(jù)集是10類不同風格衣服的數(shù)據(jù)集,該數(shù)據(jù)集包含60 000個訓練樣本,10 000個測試樣本,每個樣本都是28×28的灰度圖像。

3.2 評估指標

選用互信息(NMI)[26]和Homogeneiy[27]指數(shù)來評估不同聚類簇K下的聚類性能。其中NMI能夠評估一個變量包含另一個變量的信息量。NMI取值范圍是[0,1],越接近1說明變量Y包含變量X的信息量越小,變量X確定性越大。

(4)

Homogeneiy指數(shù)用來評估聚類簇的同質(zhì)性,即一個聚類簇中的樣本是否只屬于某一個單獨類。Homogeneiy的取值范圍為[0,1],其值越接近1則表明聚類簇中同類樣本越多。假設真實樣本標簽為C={Ci|i=1,2,…,n}，預測簇標簽為K={Kj|j=1,2,…,m}，則Homogeneiy計算方法如公式5。該公式表明預測簇標記K的條件信息熵越小，K的不確定性越小,Homogeneiy的數(shù)值越接近于1,預測簇K的同質(zhì)性越強。

(5)

由于該模型能夠聚類不同的模態(tài),故在選擇NMI指標的同時選擇了Homogeneiy指標來評估模型的細致劃分能力。

3.3 假設驗證

如前所述,該文的主要工作基于如下假設:原始樣本在K個子空間的映射特征上所生成的K個樣本中只有對應簇的生成樣本接近給定的原始樣本,且這K個生成樣本在概率向量的加權融合下能夠逼近原始樣本。為說明假設的合理性,進行了實驗驗證，結果如圖1所示。

圖1在超參數(shù)α=2,K=10,d1=5的模型上展示了三種不同的手寫數(shù)字的融合過程。從圖1(a)可以看出原始樣本0在10個子空間上的投影特征所生成的樣本中只有簇5對應的樣本與原始樣本接近,且原始樣本對應的概率推斷向量也逼近one-hot向量,其結果基本符合預定的假設。

3.4 模型實現(xiàn)

該文對神經(jīng)網(wǎng)絡的設計分為共享層網(wǎng)絡F、子空間映射網(wǎng)絡P、概率推斷網(wǎng)絡Q、生成網(wǎng)絡G。網(wǎng)絡結構如圖2所示。采用圖像數(shù)據(jù)集，故神經(jīng)網(wǎng)絡選用卷積神經(jīng)網(wǎng)絡和反卷積神經(jīng)網(wǎng)絡。網(wǎng)絡F設計了3層卷積網(wǎng)絡;概率推斷網(wǎng)絡Q設計了兩層卷積網(wǎng)絡加一個Softmax層，其輸入來源于共享層網(wǎng)絡F(或者單獨設計一個網(wǎng)絡Q，獨立于共享層網(wǎng)絡F，其輸入為樣本y);K個映射網(wǎng)絡P與概率推斷網(wǎng)絡Q并列,用于提取具有區(qū)分度的特征，其輸入來自于共享層網(wǎng)絡F,每個映射網(wǎng)絡P都設計兩層卷積神經(jīng)網(wǎng)絡;生成網(wǎng)絡G用于生成對應簇的樣本,其輸入特征來自映射網(wǎng)絡P,該網(wǎng)絡設計了四層反卷積神經(jīng)網(wǎng)絡加Sigmoid函數(shù)用于輸出灰度圖像。優(yōu)化函數(shù)選著帶動量的隨機梯度下降法Adam[28],學習率lr=0.001,迭代周期epoch=200。該模型實際聚類結果隨聚類簇個數(shù)K，類內(nèi)距離d1的變化而呈現(xiàn)不同的聚類現(xiàn)象。模型中超參數(shù)d2控制著不同簇低維子空間的分離性,d2的取值只要能夠保持子空間相互分離即可,在此條件下,d2取值的差異對聚類結果影響不顯著。模型中包含如下超參數(shù)K、d1、d2、α。

3.5 實驗結果

從生成網(wǎng)絡G的生成圖(圖5)和聚類評估指標Homogeneity、NMI的數(shù)值變化(表1～表5)來看(實驗結果取自多次實驗的最優(yōu)值),提出的模型具有把數(shù)據(jù)集進行簇劃分的能力。

表1 DCMBORE在超參數(shù)α=1時MNIST數(shù)據(jù)集上的聚類指標

在表1中可以看出，d1的變化對NMI指標影響不大,排除d1對NMI的影響之后,對比表1和表2,不難看出隨著α變大,模型的NMI指標上升。這是因為超參數(shù)α變大,融合樣本與原始樣本之間的重構速度變快,模型對樣本間差異的區(qū)分力度變小,因此模型將學得不同數(shù)字之間的差異,而忽略同一數(shù)字下不同寫法之間的差異。故評估聚類結果相似度的NMI指標上升,而評估聚類簇樣本同質(zhì)性的Homogeneity指標略有下降。

表2 DCMBORE在超參數(shù)α=2時MNIST數(shù)據(jù)集上的聚類指標

超參數(shù)α控制著樣本間差異的區(qū)分力度，觀察在α=1時表1的Homogeneity指標和網(wǎng)絡G的生成圖(圖5),可以看出模型對樣本差異的區(qū)分力度變大,不同簇之間學得的差異是同一數(shù)字下不同寫法之間的差異,此時模型得到的每一簇分別表示同一數(shù)字不同形態(tài)的寫法(如圖5(n)和(o)所示),可視為0～9十個類別下的不同小簇(MiniCluster)。所以聚類簇數(shù)目K越大,模型對樣本的劃分越細致。

在超參數(shù)α=1固定時,觀察表1在d1取值較大時Homogeneity指標略有提升,這是因為d1取值較大,不同簇的低維子空間變大, 對應的高維生成空間樣本多樣性變大,可以包含更多變化的同質(zhì)性樣本.因此超參數(shù)d1控制著高維生成空間的樣本多樣性.

該模型聚類效果對參數(shù)α,K,d1的變化較敏感。當K的數(shù)值越大,α、d1數(shù)值越小時,聚類劃分越細致。同時需要注意,在加權指數(shù)α=1且d1和K都變小時,高維樣本多樣性減少,類別劃分得細致,而K的數(shù)目較小,則現(xiàn)有的聚類簇數(shù)目難以包含所有類別,所以會出現(xiàn)難以區(qū)分不同類別的樣本(如圖5(d)和(e)所示)。此外在K值較小時,實驗結果受隨機性影響較大。

就實驗結果而言,相較于傳統(tǒng)聚類算法,該模型的聚類效果有顯著的提高。相比較于最先進的深度聚類算法,該模型具有可調(diào)節(jié)的簇區(qū)分能力,功能更靈活。模型的參數(shù)規(guī)模隨著聚類簇的增加而變大,因此,該模型的時間復雜度較高。同時由于該模型是在自編碼器的框架下設計的聚類算法,因此該模型的泛化能力較弱。

表3 DCMBORE在α=1.6、d1=13、d2=200、K=15時USPS數(shù)據(jù)集上的Homogeneity、NMI指標

表4 DCMBORE在α=1.4、d1=10、d2=200、K=10時Fashion-MNIST數(shù)據(jù)集上的Homogeneity、NMI指標

表5 DCMBORE與不同聚類模型在給定數(shù)據(jù)集上的NMI聚類指標

4 結束語

該文以一種新的方式將自編碼器引入聚類領域,借助自編碼器的特征表示和樣本重構能力，通過設置基于重構誤差的聚類損失項,并加以子空間約束項,實現(xiàn)有效聚類。模型可通過調(diào)節(jié)聚類簇個數(shù)，得到不同粒度的聚類結果，以滿足數(shù)據(jù)分析的不同需要。雖然該模型的聚類性能相比前沿的深度聚類模型優(yōu)勢并不明顯,但卻對自編碼器用于深度聚類任務做出了一個全新的探索。