前言：以前只是調(diào)用過譜聚類算法，我也不懂為什么各家公司都問我一做文字檢測的這個算法具體咋整的，沒整明白還給我掛了哇擦嘞？訊飛還以這個理由刷本寶，今天一怒把它給整吧清楚了，下次誰再問來！說不暈?zāi)闼阄逸?#xff01;

一、解釋：

?? 譜聚類是一種基于圖論的算法，主要思想是把所有的數(shù)據(jù)看做空間中的點，這些點之間用帶權(quán)邊連接，距離越近權(quán)重越大，通過對這些點組成的圖進行切割，讓切圖后的子圖間的權(quán)重和盡可能小，子圖內(nèi)的權(quán)重盡可能大，從而達到聚類的目的。

?? 切圖的過程是：定義一個子圖與其他子圖間的權(quán)重和，同時要求每個子圖的個數(shù)不能太少，這樣圖切問題就轉(zhuǎn)換為了最小化這個權(quán)重和/子圖個數(shù)的過程。優(yōu)化這個過程我們定義一個指示矩陣h，要分為的類別是（A1,A2...Ak）,i屬于Aj類則hij≠0，否則等于0，這樣優(yōu)化式子得到h之后我們就能知道各個節(jié)點的類別。根據(jù)分析得知，這個h的解與拉普拉斯矩陣L和權(quán)重矩陣D有關(guān)，具體來說是D^-1/2LD^-1/2的k個最小的特征值對應(yīng)的特征向量，這樣我們就得到了h，也將維度從n降到了k。一般來說需要對h進行按行進行標(biāo)準(zhǔn)化，然后再對這個n*k的矩陣按行進行kmeans聚類，就得到了最終的聚類結(jié)果。

二、推導(dǎo)：

??

????

三、步驟：????

??? 輸入：樣本集D=(x1,x2,...,xn)，相似矩陣的生成方式, 降維后的維度k1, 聚類方法，聚類后的維度k2

　　輸出： 簇劃分C(c1,c2,...ck2).　

　　　　1) 根據(jù)輸入的相似矩陣的生成方式構(gòu)建樣本的相似矩陣S。

　　　　2）根據(jù)相似矩陣S構(gòu)建鄰接矩陣W，構(gòu)建度矩陣D。

　　　　3）計算出拉普拉斯矩陣L。

　　　　4）構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣D^?1/2LD^?1/2

　　　　5）計算D^?1/2LD^?1/2最小的k1個特征值所各自對應(yīng)的特征向量f。

　　　　6) 將各自對應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化，最終組成n×k1維的特征矩陣F。

　　　　7）對F中的每一行作為一個k1維的樣本，共n個樣本，用輸入的聚類方法進行聚類，聚類維數(shù)為k2。

　　　　8）得到簇劃分C(c1,c2,...ck2)。

四、優(yōu)缺點：

?? 優(yōu)點：只需要相似度矩陣，方便處理稀疏數(shù)據(jù)的聚類；使用了降維，處理高維數(shù)據(jù)效果比傳統(tǒng)聚類方法好。

?? 缺點：如果降維的幅度不夠，效果和效率均不夠好；依賴于相似度矩陣。

五、鏈接：

?? https://www.cnblogs.com/pinard/p/6221564.html

轉(zhuǎn)載于:https://www.cnblogs.com/EstherLjy/p/9432651.html

總結(jié)

以上是生活随笔為你收集整理的【谱聚类算法总结】的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。