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