利用稀疏自編碼的局部譜聚類映射算法*

萬(wàn) 月， 陳秀宏， 何佳佳

(江南大學(xué) 數(shù)字媒體學(xué)院，江蘇 無(wú)錫 214122)

0 引 言

深度學(xué)習(xí)能發(fā)現(xiàn)高維數(shù)據(jù)中深層次復(fù)雜結(jié)構(gòu)特征，并提取數(shù)據(jù)從低維到高維的層次特征，最終提升對(duì)數(shù)據(jù)的分類以及預(yù)測(cè)的準(zhǔn)確性[1]。文獻(xiàn)[2]通過(guò)神經(jīng)網(wǎng)絡(luò)進(jìn)行學(xué)習(xí)，文獻(xiàn)[3]探究了深度學(xué)習(xí)可以幫助特征學(xué)習(xí)獲取更佳的特征表示。

譜聚類算法由于能識(shí)別任意形狀結(jié)構(gòu)數(shù)據(jù)，且收斂于全局最優(yōu)解而被廣泛應(yīng)用[4，5]。傳統(tǒng)譜聚類通過(guò)高斯核函數(shù)建立鄰接矩陣，而高斯核參數(shù)σ均由人工設(shè)置[6]。文獻(xiàn)[7]在基于圖嵌入的半監(jiān)督算法中提出了具有局部差異的圖嵌入算法。文獻(xiàn)[8]將譜聚類應(yīng)用到圖像處理中，提出了一種彩色圖像分割算法。

考慮到深度學(xué)習(xí)和譜聚類算法各自的優(yōu)勢(shì)，本文提出了一種利用稀疏自編碼的局部譜聚類映射算法，利用稀疏自編碼提取數(shù)據(jù)高層特征代替原始數(shù)據(jù)；構(gòu)建鄰接矩陣時(shí)拋棄了傳統(tǒng)高斯核函數(shù)建立方法，避免了參數(shù)調(diào)節(jié)，利用數(shù)據(jù)的流形性質(zhì)建立更能反映數(shù)據(jù)鄰域結(jié)構(gòu)的相似矩陣，算法在聚類同時(shí)引入數(shù)據(jù)映射的協(xié)同訓(xùn)練實(shí)現(xiàn)了映射與聚類的協(xié)同學(xué)習(xí)與訓(xùn)練，并更新類指標(biāo)，進(jìn)而獲得更精確的聚類結(jié)果。

1 稀疏自編碼

1.1 反向傳播算法

稀疏自編碼建立在反向傳播(back propagation,BP)神經(jīng)網(wǎng)絡(luò)基礎(chǔ)上的具有三層的神經(jīng)網(wǎng)絡(luò)模型如圖1所示。

圖1 基本的三層神經(jīng)網(wǎng)絡(luò)模型

(1)

n個(gè)數(shù)據(jù)的樣本集{x1,x2,…,xn}，設(shè)與輸入值xi對(duì)應(yīng)的目標(biāo)值yi，則對(duì)全部n個(gè)樣本數(shù)據(jù)的代價(jià)函數(shù)為

(2)

式中nl為網(wǎng)絡(luò)總層數(shù);sl為第l層的節(jié)點(diǎn)數(shù)(不包括偏置)。第一項(xiàng)為均方差項(xiàng)，第二項(xiàng)為權(quán)重衰減項(xiàng)，用以防止過(guò)擬合。

1.2 稀疏性

(3)

(4)

其中稀疏性參數(shù)ρ為充分小的正數(shù)。于是，稀疏自編碼的目標(biāo)函數(shù)可以表示為

(5)

2 譜聚類

2.1 譜聚類思想與算法

定義Y=[y1,y2,…,yn]T∈{0,1}n×C，其中yi∈{0,1}C為xi的聚類指標(biāo)向量，若xi屬于第C類，則yij=1;否則,yij=0，j=1,2,…,C，i=1,2,…,n。定義標(biāo)量化的聚類指標(biāo)矩陣[9]F=[F1,F2,…,Fn]T=Y(YTY)-1/2，其中Fi為xi的標(biāo)量化聚類指標(biāo)向量，F(xiàn)的第j列為

(6)

式中nj為屬于第j類數(shù)據(jù)的個(gè)數(shù)。則譜聚類可表示為以下優(yōu)化問(wèn)題

min tr(FTLF),s.t.F=Y(YTY)-1/2

(7)

傳統(tǒng)譜聚類中，由高斯核建立鄰接矩陣

(8)

式中Nk(·)為數(shù)據(jù)的k近鄰。由于式(7)中的F為離散量，直接求解比較困難，所以需要對(duì)F進(jìn)行松弛轉(zhuǎn)換為連續(xù)量后聚類。

2.2 局部譜聚類

以上譜聚類的鄰接矩陣并未考慮數(shù)據(jù)的流形性質(zhì)，以及局部鄰域結(jié)構(gòu)，文獻(xiàn)[10]以每個(gè)數(shù)據(jù)與其鄰域點(diǎn)的線性組合進(jìn)行線性重構(gòu)，并利用重構(gòu)的權(quán)值矩陣Sl建立數(shù)據(jù)的相似矩陣，其目標(biāo)函數(shù)為

(9)

(10)

(11)

3 局部譜聚類與映射的協(xié)同訓(xùn)練

局部譜聚類雖然考慮了數(shù)據(jù)的局部流形結(jié)構(gòu)，但只是單一聚類，借鑒文獻(xiàn)[11]的思路，本文每個(gè)樣本與其所屬類別可以建立一個(gè)明確的映射關(guān)系，即在聚類過(guò)程中將樣本映射到類指標(biāo)矩陣上修正聚類指標(biāo)。對(duì)于數(shù)據(jù)集X∈Rd×n，通過(guò)XTW將數(shù)據(jù)集映射到類指標(biāo)矩陣F上，誤差最小化的問(wèn)題可以用如下線性回歸模型來(lái)進(jìn)行

(12)

式中 回歸系數(shù)W∈Rd×c;Ω(W)為對(duì)回歸系數(shù)的正則約束；β為約束系數(shù)。使用‖W‖2,1作為W的正則約束項(xiàng)。結(jié)合局部譜聚類，聚類算法與映射可以同時(shí)得到學(xué)習(xí)與調(diào)整，協(xié)同訓(xùn)練算法的目標(biāo)函數(shù)轉(zhuǎn)換為

s.t.FTF=I

(13)

定義一個(gè)d×d的對(duì)角矩陣U，其第j個(gè)對(duì)角元素Ujj為

(14)

則式(13)轉(zhuǎn)換為

s.t.FTF=I

(15)

目標(biāo)函數(shù)關(guān)于W求偏導(dǎo)數(shù)并令其為零得到

W=α(αX(XT)+βU)-1XF

(16)

令A(yù)=α(αX(XT)+βU)-1，則W=AXF，代入式(15)

βtr(FTXTATUAXF)s.t.FTF=I

(17)

式(13)可簡(jiǎn)化為

min tr(FTHF),s.t.FTF=I

(18)

式中H=(L1-αXTAX+αL)。通過(guò)對(duì)H進(jìn)行特征分解，再用k-means對(duì)特征向量聚類即可。

4 利用稀疏自編碼的局部譜聚類映射算法

首先對(duì)數(shù)據(jù)進(jìn)行稀疏自編碼提取高層特征，并以此類特征數(shù)據(jù)作為輸入進(jìn)行局部譜聚類與映射(local spectral clustering mapping,LSCMS)協(xié)同訓(xùn)練。算法的具體過(guò)程如下：

1)預(yù)處理階段：對(duì)于來(lái)自真實(shí)世界的圖片，采用ZCA白化算法對(duì)數(shù)據(jù)X進(jìn)行預(yù)處理，消除數(shù)據(jù)冗余度，得到新的數(shù)據(jù)X1。在X1上進(jìn)行稀疏自編碼訓(xùn)練，選擇合適的隱含層個(gè)數(shù)，得到訓(xùn)練后提取的高層特征trainFeatures。

2)協(xié)同訓(xùn)練階段：用提取的數(shù)據(jù)高層特征trainFeatures作為輸入數(shù)據(jù)X進(jìn)行局部譜聚類和協(xié)同訓(xùn)練。

b.由式(16)計(jì)算對(duì)角矩陣U，計(jì)算A=α(αX(XT)+βU)-1和H=(L1-αXTAX+αI)；

c.利用H的前C個(gè)特征向量來(lái)更新F；

d.由W=AXF更新W，若某收斂條件滿足則停止迭代;否則,轉(zhuǎn)步驟(b)；

4)對(duì)得到的F的每一行進(jìn)行k-means聚類，得到最終聚類結(jié)果。

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

5.1 數(shù)據(jù)集以及實(shí)驗(yàn)設(shè)置

實(shí)驗(yàn)中所使用的數(shù)據(jù)集包括6個(gè)UCI(University of California，Irvine)數(shù)據(jù)集、MNIST手寫數(shù)據(jù)集以及ORL和Yale人臉數(shù)據(jù)集，如表1所示。參數(shù)α和β取值均為1，并將本文算法與k-means算法[12]、模糊c均值[13](fuzzyc-means，F(xiàn)CM，隸屬度值為2)算法、傳統(tǒng)譜聚類(spectral clustering,SC)算法[14]以及通過(guò)高斯核建立鄰接矩陣的本文算法(spectral clustering and mapping algorithm using sparse autoencoders，SCMSA)進(jìn)行對(duì)比。每種算法均重復(fù)20次后取平均結(jié)果。實(shí)驗(yàn)硬件為Interl(R)Xeon(R)CPU E5-4607,2.60GHz(2)處理器，內(nèi)存為32GB，軟件為Win764位操作系統(tǒng)和MATLAB2014b。

表1 數(shù)據(jù)集描述

5.2 零相位成分分析白化

零相位成分分析(zero-phase component analysis,ZCA)白化處理即將圖像相鄰像素間的冗余除去，使得白化后數(shù)據(jù)的特征之間相關(guān)性較低，并具有相同的方差。

5.3 評(píng)價(jià)指標(biāo)

為了評(píng)價(jià)聚類效果，采用了以下兩種標(biāo)準(zhǔn)評(píng)價(jià)方法,兩個(gè)指標(biāo)均值越大效果越好。

1)F-measure

(19)

式中P為精確率(precision);R為召回率(recall)；TP為正類被判定為正類的個(gè)數(shù)；FP為負(fù)類被判定為正類的個(gè)數(shù)；FN為正類判定為負(fù)類的個(gè)數(shù)。

2)歸一化互信息

兩個(gè)隨機(jī)向量X與Y間的歸一化互信息(normalized mutual information,NMI)為

(20)

式中I(X,Y)為X和Y之間的互信息;H(X)和H(Y)分別為X和Y的熵。

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

表2、表3分別為數(shù)據(jù)集在不同算法中的F-measure值與NMI值的對(duì)比結(jié)果；圖2為在鄰域k的不同取值下，相關(guān)數(shù)據(jù)F-measure值與NMI值的變化情況，由于Wine和Seeds的鄰域選擇較少時(shí)聚類效果很差，所以，k從5開(kāi)始，Olivetti 研究室(Olivetti research laboratory,ORL)與Yale人臉庫(kù)則從2開(kāi)始取值。圖3為在k=5，α,β分別取10-4～104，間隔102時(shí)人臉數(shù)據(jù)ORL與Yale的聚類結(jié)果。

圖2 鄰域k的取值對(duì)NMI與F-measure的影響

圖3 α和β的取值對(duì)NMI與F-measure的影響

圖2看出，UCI數(shù)據(jù)集中，當(dāng)k值從5開(kāi)始增加，Wine和Seeds的聚類效果逐漸提升，k=25時(shí)達(dá)最大值，k超過(guò)25后聚類效果下降。人臉數(shù)據(jù)集中，k=5時(shí)，Yale與ORL數(shù)據(jù)庫(kù)聚類效果達(dá)到最佳，k超過(guò)25后，Yale數(shù)據(jù)集的聚類效果略下降，ORL數(shù)據(jù)集基本保持不變。所以k的選取對(duì)最終聚類效果有很大的影響。

圖3中當(dāng)α,β過(guò)大時(shí)聚類效果很差，當(dāng)α=1,β=100時(shí)兩個(gè)數(shù)據(jù)集的NMI與F-measure值均最佳，由此看出數(shù)據(jù)映射對(duì)聚類效果有一定程度影響。

從表2,表3可以看出LSCMS算法效果相較于其他聚類算法有明顯提高。證實(shí)了局部譜聚類與數(shù)據(jù)映射的協(xié)同訓(xùn)練有助于提升最終聚類效果。

6 結(jié)束語(yǔ)

提出了利用稀疏自編碼的局部譜聚類映射算法。首先對(duì)圖片進(jìn)行ZCA白化處理消除圖片的冗余信息，然后進(jìn)行稀疏自編碼特征提取代替原始數(shù)據(jù)，通過(guò)鄰域重構(gòu)相似矩陣，并結(jié)合數(shù)據(jù)映射的協(xié)同訓(xùn)練進(jìn)行聚類，驗(yàn)證了本文算法的有效性與可行性。

[1] 余 凱,賈 磊,陳雨強(qiáng),等.深度學(xué)習(xí)的昨天,今天和明天[J].計(jì)算機(jī)研究與發(fā)展,2013,50(9):1799-1804.

表2 相關(guān)算法的F-measure值

表3 相關(guān)算法的的NMI

[2] Hinton G E,Salakhutdinov R R.Reducing the dimensionality of data with neural networks[J].Science,2006,313(5786):504-507.

[3] Bengio Y,Courville A,Vincent P.Representation learning:A review and new perspectives[J].IEEE Transactions on Pattern Analysis and Machine Intelligence,2013,35(8):1798-1828.

[4] Jia H,Ding S,Xu X,et al.The latest research progress on spectral clustering[J].Neural Computing and Applications,2014,24(7-8):1477-1486.

[5] 李昌興,黃艷虎,支曉斌,等.基于加速k均值的譜聚類圖像分割算法改進(jìn)[J].傳感器與微系統(tǒng),2016，35(9)：137-140.

[6] Ng A Y,Jordan M I,Weiss Y.On spectral clustering:Analysis and an algorithm[J].Advances in Neural Information Processing Systems,2002,2:849-856.

[7] 梁興柱,林玉娥,林玉榮.半監(jiān)督有局部差異的圖嵌入算法[J].傳感器與微系統(tǒng),2014,33(7):144-146.

[8] 張 琦,盧志茂,徐 森,等.基于相似度矩陣的譜聚類集成圖像分割[J].傳感器與微系統(tǒng),2013,32(10):21-23.

[9] Ye J,Zhao Z,Wu M,et al.Discriminativek-means for cluste-ring[C]∥Proceedings of the Annual Conference on Advances in Neural Information Processing Systems,2007:1649-1656.

[10] Wang F,Zhang C.Label propagation through linear neighborhood-s[J].IEEE Transactions on knowledge and Data Engineering,2008,20(1):55-67.

[11] 汪荊琪,徐林莉.一種基于多視圖數(shù)據(jù)的半監(jiān)督特征選擇和聚類算法[J].數(shù)據(jù)采集與處理,2015,30(1):106-116.

[12] Jain A K.Data clustering:50 years beyondk-means[J].Pattern recognition letters,2010,31(8):651-666.

[13] Bezdek J C,Ehrlich R,Full W.FCM:The fuzzyc-means clustering algorithm[J].Computers & Geosciences,1984,10(2-3):191-203.

[14] Ng A Y,Jordan M I,Weiss Y.On spectral clustering:Analysis and an algorithm[J].Advances in Neural Information Processing Systems,2002,2:849-856.