本文摘要：譜嵌入聚類是建立在譜圖理論基礎(chǔ)上，該算法主要應(yīng)用于計(jì)算機(jī)視覺(jué)，目前此種算法正在迅速成為國(guó)際機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)，其中數(shù)據(jù)聚類有良好的應(yīng)用前景，小編推薦關(guān)于在譜嵌入聚類在計(jì)算機(jī)應(yīng)用的論文。 摘要：譜嵌入聚類(SEC算法要求樣本滿足流形假設(shè)，樣本
譜嵌入聚類是建立在譜圖理論基礎(chǔ)上，該算法主要應(yīng)用于計(jì)算機(jī)視覺(jué)，目前此種算法正在迅速成為國(guó)際機(jī)器學(xué)習(xí)領(lǐng)域的研究熱點(diǎn)，其中數(shù)據(jù)聚類有良好的應(yīng)用前景，小編推薦關(guān)于在譜嵌入聚類在計(jì)算機(jī)應(yīng)用的論文。
摘要：譜嵌入聚類(SEC算法要求樣本滿足流形假設(shè)，樣本標(biāo)簽總是可以嵌入到一個(gè)線性空間中去，這為線性可分?jǐn)?shù)據(jù)的譜嵌入聚類問(wèn)題提供了新的思路，但該算法使用的線性映射函數(shù)不適用于處理高維非線性數(shù)據(jù)。針對(duì)這一問(wèn)題，通過(guò)核化線性映射函數(shù)，建立了基于核函數(shù)的譜嵌入聚類(KSEC模型，該模型既能解決線性映射函數(shù)不能處理非線性數(shù)據(jù)的問(wèn)題，又實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)的核降維。在真實(shí)數(shù)據(jù)集上的實(shí)驗(yàn)分析結(jié)果表明，使用所提算法后聚類正確率平均提高了13.11%，最高可提高31.62%，特別在高維數(shù)據(jù)上平均提高了16.53%，而且在算法關(guān)于參數(shù)的敏感度實(shí)驗(yàn)中發(fā)現(xiàn)算法的穩(wěn)定性更好。所以改進(jìn)后的算法對(duì)高維非線性數(shù)據(jù)具有很好的聚類效果，獲得了比傳統(tǒng)譜嵌入聚類算法更高的聚類準(zhǔn)確率和更好的聚類性能。所提方法可以用于諸如遙感影像這類復(fù)雜圖像的處理領(lǐng)域。
關(guān)鍵詞：譜聚類;譜嵌入;核函數(shù);高維數(shù)據(jù)
0引言
譜聚類算法(Spectral Clustering Algorithm， SCA是近幾年來(lái)機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘領(lǐng)域研究的熱點(diǎn)算法之一，它是聚類算法引入譜圖理論之后誕生的一類新算法[1]。與傳統(tǒng)的聚類算法相比，它能夠不受凸集樣本的特性限制而獲得全局最優(yōu)解，得到更好的聚類結(jié)果。
在譜聚類算法的研究過(guò)程中，文獻(xiàn)[2]提出了用大于k個(gè)特征向量去構(gòu)建特征空間來(lái)進(jìn)行譜聚類，獲得了比傳統(tǒng)的kway方法更好的聚類結(jié)果;文獻(xiàn)[3]則從親和度矩陣的構(gòu)造和特征分解過(guò)程出發(fā)，提出了非負(fù)稀疏譜聚類算法，在時(shí)間和空間雜度上改善了譜聚類算法的性能;文獻(xiàn)[4]將實(shí)例約束泛化到空間約束，使用半監(jiān)督方法大大提高了譜聚類性能。譜聚類算法發(fā)展至今，雖然在大多數(shù)數(shù)據(jù)集上能夠得到好的聚類結(jié)果，但是在將它擴(kuò)展到海量數(shù)據(jù)時(shí)仍然困難重重，尤其是在解決高維數(shù)據(jù)的問(wèn)題上。Wu等[5]提出在面對(duì)高維數(shù)據(jù)時(shí)可以利用稀疏向量來(lái)構(gòu)造親和度矩陣，避免了海量數(shù)據(jù)聚類時(shí)高昂的計(jì)算代價(jià);Nie等[6]則在2011年提出了譜嵌入聚類(Spectral Embedded Clustering， SEC算法框架，指出高維數(shù)據(jù)的類別標(biāo)簽矩陣總是可以嵌入到一個(gè)線性空間中去，數(shù)據(jù)樣本按照類別在這個(gè)空間中跨度開(kāi)來(lái)，即所有的數(shù)據(jù)在C維空間中都有自己的類標(biāo)簽，C代表N個(gè)數(shù)據(jù)樣本的類別總數(shù)目，這便解決了高維數(shù)據(jù)因不具備低維的流形結(jié)構(gòu)而造成的聚類困難，相比傳統(tǒng)的SCA較好地解決了高維數(shù)據(jù)的譜聚類問(wèn)題;2012年Jiao 等[7]將成對(duì)點(diǎn)約束監(jiān)督信息引入到SEC框架中，增強(qiáng)了數(shù)據(jù)譜嵌入的能力，取得了較好的聚類效果。
由于譜嵌入聚類算法在聚類時(shí)選用線性的映射函數(shù)，所以它對(duì)線性可分?jǐn)?shù)據(jù)具有較好的聚類效果，但對(duì)非線性數(shù)據(jù)并不適用。針對(duì)這一問(wèn)題本文提出了一種基于核函數(shù)的譜嵌入聚類(Spectral Embedded Clustering based on Kernel function， KSEC算法，將核函數(shù)引入到SEC框架中去，很好地改善了高維非線性數(shù)據(jù)的譜聚類性能。通過(guò)在真實(shí)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，與傳統(tǒng)的一些譜聚類算法進(jìn)行比較后發(fā)現(xiàn)改進(jìn)后的算法效果更為良好。
1譜聚類算法
譜圖理論是圖論領(lǐng)域經(jīng)典的知識(shí)體系，它通過(guò)矩陣論方法來(lái)研究圖的鄰接矩陣，挖掘其潛在的結(jié)構(gòu)信息，這里的結(jié)構(gòu)信息在數(shù)據(jù)上便體現(xiàn)為類別信息，它的基礎(chǔ)是圖的Laplacian矩陣，是由Fiedler[8]在1973年提出來(lái)的。將數(shù)據(jù)的聚類問(wèn)題轉(zhuǎn)化為對(duì)圖的劃分問(wèn)題的求解，這便是建立在譜圖理論基礎(chǔ)之上的譜聚類算法的核心思想。
譜聚類算法實(shí)現(xiàn)的基本流程[9]描述如下：1數(shù)據(jù)預(yù)處理。將數(shù)據(jù)轉(zhuǎn)化為一個(gè)無(wú)向加權(quán)圖，采用高斯核函數(shù)(式(1計(jì)算兩個(gè)樣本點(diǎn)之間的相似性[10]，得到這個(gè)圖的鄰接矩陣。2譜映射。對(duì)Laplacian矩陣進(jìn)行特征分解，在得到的特征向量中選擇一個(gè)或者多個(gè)合適的向量構(gòu)造特征空間。3對(duì)數(shù)據(jù)進(jìn)行聚類。使用經(jīng)典聚類算法，例如Kmeans算法在新的數(shù)據(jù)空間進(jìn)行聚類，將聚類結(jié)果映射回原始數(shù)據(jù)空間，算法結(jié)束。圖1展示了Iris數(shù)據(jù)的類別分布與它的Laplacian矩陣結(jié)構(gòu)間的關(guān)系，其中Laplacian矩陣圖是對(duì)稱結(jié)構(gòu)，每一個(gè)像素點(diǎn)代表兩個(gè)樣本之間的相似度大小，取值在0～1。
Aij=exp-d(si，sj2σ2(1
2譜嵌入聚類算法框架
給定一個(gè)數(shù)據(jù)樣本集合X={x1，x2，…，xn}∈Rd×n;定義X的簇分配矩陣Y=[y1，y2，…，yn]T∈Bn×c，c代表簇的個(gè)數(shù)，定義它的擴(kuò)展簇分配矩陣為F[6]1798：
F=D12Z=D12Y(YTDY12=f(Y(2
其中：Z=Y(YTDY- 12，D為度矩陣，將其進(jìn)行放松連續(xù)化處理后F∈Rn×c。為方便計(jì)算，假設(shè)數(shù)據(jù)都是中心化的，即X1n=0，這時(shí)定義數(shù)據(jù)的總體散布矩陣為St，類間散布矩陣為Sb，類內(nèi)散布矩陣為Sw：
St=XXT
Sb=XGGTXT
Sw=XXT-XGGTXT(3
其中：G=Y(YTY- 12。
文獻(xiàn)[6]證明了如果rank(Sb=c-1且rank(St=rank(Sw+rank(Sb，那么簇分配矩陣便能夠由一個(gè)低維的線性空間來(lái)描述，這時(shí)存在W∈Rd×c，b∈Rc×1使得Y=XTW+1nbT。
基于以上矩陣定義和理論支持，文獻(xiàn)[6]提出了SEC算法將線性正則化方法引入到SCA算法當(dāng)中，提出目標(biāo)函數(shù)為式(4
minF，W，bFTF=IcJ(F+u(‖XTW+1nbT-F‖2+γgtr(WTW(4其中，u和γg是兩個(gè)正則化參數(shù)，第一個(gè)參數(shù)描述簇分配矩陣與低維空間的線性關(guān)系的強(qiáng)弱，第二個(gè)參數(shù)描述簇分配矩陣被放松處理后的F與低維線性空間的不匹配程度;J(F=tr(FTLF指的是傳統(tǒng)譜聚類算法的目標(biāo)函數(shù)。在式(4上對(duì)W和b分別進(jìn)行求導(dǎo)，使其結(jié)果等于0得：
W=(XXT+γgId-1XF
b=1nFT1n(5
將式(5代入式(4后進(jìn)行化簡(jiǎn)，優(yōu)化問(wèn)題便轉(zhuǎn)化為：
minFTF=IcJ(F+uP(F(6
其中
P(F=tr(FTLgF。
Lg=Hn-XT(XXT+γgId-1X(7
其中
Hn=In-1n1n1Tn。
這時(shí)，與傳統(tǒng)的譜聚類算法同理，對(duì)簇分配矩陣的求解進(jìn)行放松處理便轉(zhuǎn)化為對(duì)L+uLg的特征分解問(wèn)題了，取前c個(gè)最小特征值對(duì)應(yīng)的特征向量構(gòu)建特征空間，在新的特征空間中對(duì)數(shù)據(jù)進(jìn)行劃分，就成功地實(shí)現(xiàn)了對(duì)高維數(shù)據(jù)的準(zhǔn)確聚類。
3基于核函數(shù)的譜嵌入聚類算法
3.1核函數(shù)
經(jīng)典的核學(xué)習(xí)理論指出，低維空間中線性不可分的模式通過(guò)一種非線性映射到高維特征空間后，就能夠?qū)崿F(xiàn)線性可分。但是，如果直接采用這種非線性映射技術(shù)在高維空間進(jìn)行分類或者回歸，就必然面臨著映射函數(shù)的形式和參數(shù)的確定問(wèn)題，而且很有可能引發(fā)“維數(shù)災(zāi)難”，這時(shí)采用核函數(shù)可以有效地解決這一問(wèn)題。設(shè)x，z∈X，X屬于R(n空間，非線性函數(shù)Φ實(shí)現(xiàn)了低維空間中數(shù)據(jù)X到高維的特征空間F的映射，其中F屬于R(m，(nm空間，則核函數(shù)[11]定義為：
k(x，z=〈Φ(x，Φ(z〉(8
其中
〈〉表示內(nèi)積，k(x，z表示核函數(shù)。
式(8表明核函數(shù)將m維(高維空間里的內(nèi)積運(yùn)算轉(zhuǎn)化成了n維(低維空間里的核函數(shù)計(jì)算，從而解決了數(shù)據(jù)的“高維”帶來(lái)的維數(shù)災(zāi)難問(wèn)題，而且核函數(shù)不需要知道非線性變換函數(shù)Φ的形式和參數(shù)，引入方便。本文選用高斯核函數(shù)來(lái)完成非線性數(shù)據(jù)到高維的映射過(guò)程，同時(shí)該函數(shù)也是在譜聚類算法開(kāi)始時(shí)構(gòu)造親和度矩陣的徑向基函數(shù)。
3.2KSEC算法
根據(jù)以上分析，基于核函數(shù)的譜嵌入聚類算法(KSEC引入一個(gè)非線性的核函數(shù)yi=f(xi=∑nj=1αik(xi，xj，將非線性的不可分?jǐn)?shù)據(jù)映射到高維的特征空間實(shí)現(xiàn)可分，這里的核函數(shù)選用高斯核函數(shù)，與式(1定義相同。
KSEC算法使用核化的映射函數(shù)將高維非線性數(shù)據(jù)X映射后，將其簇分配矩陣嵌入到一個(gè)線性低維空間，設(shè)置目標(biāo)函數(shù)為：
minF，W，bFTF=IcJ(F+u(‖Kα-F‖2+γgtr(ααT(9
在目標(biāo)函數(shù)式(9上，把對(duì)α的求導(dǎo)結(jié)果置為0可得α=(K+γgIn-1F∈Rn×c。根據(jù)矩陣的2范數(shù)和矩陣跡的關(guān)系，式(9可以轉(zhuǎn)化為：
minF，W，bFTF=IcJ(F+u(tr[(Kα-F(Kα-FT]+γgtr(ααT(10
將α代入式(10，目標(biāo)函數(shù)的優(yōu)化問(wèn)題轉(zhuǎn)化為式(6所列形式，其中P(F=tr(FLgFT，注意這里：
Lg=In-(K+γgIn-1(11
至此，KSEC算法的理論推導(dǎo)便轉(zhuǎn)化為了對(duì)Lsym+uLg的特征求解問(wèn)題了。算法1詳細(xì)介紹了KSEC算法的實(shí)現(xiàn)流程。
核化的映射函數(shù)對(duì)數(shù)據(jù)的處理不再局限于線性可分?jǐn)?shù)據(jù)，它對(duì)使用線性映射函數(shù)難以處理的數(shù)據(jù)，例如高維數(shù)據(jù)和稀疏數(shù)據(jù)都能夠很好地進(jìn)行映射以便實(shí)現(xiàn)可分，當(dāng)然對(duì)線性可分?jǐn)?shù)據(jù)它依然適用。對(duì)比式(7和式(11發(fā)現(xiàn)核函數(shù)的引入大大精簡(jiǎn)了待求式的中間量如In和1n，簡(jiǎn)化了Lg的計(jì)算，提高了算法效率。從算法復(fù)雜度上來(lái)分析，算法第1步構(gòu)造親和度矩陣時(shí)的時(shí)間復(fù)雜度為O(n2，第4步進(jìn)行矩陣分解時(shí)的時(shí)間復(fù)雜度為O(n2+1，所以該算法的整體時(shí)間復(fù)雜度為O(n2+1+n2，即O(n2。
算法1KSEC算法。
輸入：數(shù)據(jù)集X={x1，x2，…xn}∈Rd×n，參數(shù)σ，類別數(shù)c，正則化參數(shù)u、γg。
輸出：數(shù)據(jù)的類標(biāo)簽。
小編推薦優(yōu)秀電子期刊 《計(jì)算機(jī)工程與科學(xué)》
《計(jì)算機(jī)工程與科學(xué)》(月刊)創(chuàng)刊于1973年，由國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院主辦。辦刊宗旨是為計(jì)算機(jī)界同行發(fā)表有創(chuàng)見(jiàn)的學(xué)術(shù)論文，介紹有特色的科研成果，探討有新意的學(xué)術(shù)觀點(diǎn)提供理想園地;活躍計(jì)算機(jī)界學(xué)術(shù)氣氛，擴(kuò)大國(guó)內(nèi)外交流，為發(fā)展中國(guó)的計(jì)算機(jī)事業(yè)盡一點(diǎn)微薄之力。
轉(zhuǎn)載請(qǐng)注明來(lái)自發(fā)表學(xué)術(shù)論文網(wǎng)：http:///dzlw/3814.html
