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