譜聚類|機(jī)器學(xué)習(xí)推導(dǎo)系列(二十)

一、概述

對(duì)于下圖所示的數(shù)據(jù)進(jìn)行聚類废酷,可以采用GMM或者K-Means的方法:

數(shù)據(jù)

然而對(duì)于下圖所示的數(shù)據(jù)瘟檩,單純的GMM和K-Means就無(wú)效了,可以通過(guò)核方法對(duì)數(shù)據(jù)進(jìn)行轉(zhuǎn)換澈蟆,然后再進(jìn)行聚類:

數(shù)據(jù)

如果直接對(duì)上圖所示的數(shù)據(jù)進(jìn)行聚類的話可以考慮采用譜聚類(spectral clustering)的方法墨辛。

總結(jié)來(lái)說(shuō),聚類算法可以分為兩種思路:

①Compactness趴俘,這類有 K-means睹簇,GMM 等,但是這類算法只能處理凸集寥闪,為了處理非凸的樣本集太惠,必須引?核技巧。
②Connectivity疲憋,這類以譜聚類為代表凿渊。

二、基礎(chǔ)知識(shí)

  1. 無(wú)向權(quán)重圖

譜聚類的方法基于帶權(quán)重的無(wú)向圖缚柳,圖的每個(gè)節(jié)點(diǎn)是一個(gè)樣本點(diǎn)埃脏,圖的邊有權(quán)重,權(quán)重代表兩個(gè)樣本點(diǎn)的相似度秋忙。

假設(shè)總共N個(gè)樣本點(diǎn)彩掐,這些樣本點(diǎn)構(gòu)成的圖可以用G=(V,E)表示,其中V=\left \{v_1,v_2,\cdots ,v_N\right \}灰追,圖中的每個(gè)點(diǎn)v_i也就代表了一個(gè)樣本x_i堵幽,E是邊,用鄰接矩陣(也是相似度矩陣)W_{N\times N}來(lái)表示弹澎,W=[w_{ij}],1\leq i,j\leq N朴下,由于是無(wú)向圖,因此w_{ij}=w_{ji}裁奇。

另外還有度的概念桐猬,這里可以類比有向圖中的出度和入度的概念,不過(guò)圖中的點(diǎn)v_i的度d_i并不是和該點(diǎn)相連的點(diǎn)的數(shù)量刽肠,而是和其相連的邊的權(quán)重之和溃肪,也就是鄰接矩陣的每一行的值加起來(lái)免胃,即:

d_{i}=\sum_{j=1}^{N}w_{ij}

而圖的度矩陣(對(duì)角矩陣)D_{N\times N}可以表示如下:

D=\begin{bmatrix} d_{1} & & &\\ & d_{2} & & \\ & & & \\ & & & d_{N} \end{bmatrix}

另外我們定義,對(duì)于點(diǎn)集V的一個(gè)子集A\subset V惫撰,我們定義:

|A|:=子集A中點(diǎn)的個(gè)數(shù)\\ vol(A):=\sum _{i\in A}d_{i}

  1. 鄰接矩陣

構(gòu)建鄰接矩陣W一共有三種方法羔沙,分別是\epsilon-近鄰法、k近鄰法和全連接法厨钻。

  • \epsilon-近鄰法

首先需要設(shè)置一個(gè)閾值\epsilon扼雏,比較任意兩點(diǎn)x_ix_j之間的距離s_{ij}=||x_{i}-x_{j}||_{2}^{2}\epsilon的大小,定義鄰接矩陣如下:

w_{ij}=\left\{\begin{matrix} 0,s_{ij}>\epsilon\\ \epsilon ,s_{ij}\leq \epsilon \end{matrix}\right.

這種方法表示如果兩個(gè)樣本點(diǎn)之間的歐氏距離的平方小于閾值\epsilon夯膀,則它們之間是有邊的诗充。

使用這種方法,兩點(diǎn)相似度只有\epsilon0兩個(gè)值诱建,這種度量很不精確蝴蜓,因此在實(shí)際應(yīng)用中很少使用\epsilon-近鄰法。

  • k近鄰法

使用KNN算法遍歷所有樣本點(diǎn)俺猿,取每個(gè)樣本點(diǎn)最近的k個(gè)點(diǎn)作為近鄰茎匠。這種方法會(huì)造成構(gòu)造的鄰接矩陣不對(duì)稱,而譜聚類算法需要一個(gè)對(duì)稱的鄰接矩陣押袍。因此有以下兩種方法來(lái)構(gòu)造一個(gè)對(duì)稱的鄰接矩陣:

①只要一個(gè)點(diǎn)在另一個(gè)點(diǎn)的k近鄰內(nèi)诵冒,則w_{ij}>0,否則為0谊惭,相似度w_{ij}可以使用徑向基函數(shù)來(lái)度量:

w_{ij}=w_{ji}=\left\{\begin{matrix} exp\left \{-\frac{||x_{i}-x_{j}||_{2}^{2}}{2\sigma ^{2}}\right \},x_{i}\in KNN(x_{j})\; or \; x_{j}\in KNN(x_{i})\\ 0,x_{i}\notin KNN(x_{j})\; and\; x_{j}\notin KNN(x_{i}) \end{matrix}\right.

②只有兩個(gè)點(diǎn)互為k近鄰汽馋,才會(huì)有w_{ij}>0,否則為0

w_{ij}=w_{ji}=\left\{\begin{matrix} exp\left \{-\frac{||x_{i}-x_{j}||_{2}^{2}}{2\sigma ^{2}}\right \},x_{i}\in KNN(x_{j})\; and\; x_{j}\in KNN(x_{i})\\ 0,x_{i}\notin KNN(x_{j})\; or\; x_{j}\notin KNN(x_{i}) \end{matrix}\right.

上述方法是不用先建立圖而直接獲得鄰接矩陣午笛,在編程實(shí)現(xiàn)時(shí)能夠更加簡(jiǎn)便惭蟋,構(gòu)建的鄰接矩陣也就表明了哪些樣本點(diǎn)之間有邊連接。也可以采用先建立圖然后再在圖上有邊的數(shù)據(jù)點(diǎn)上保留權(quán)重獲得鄰接矩陣的方法药磺。

  • 全連接法

這種方法會(huì)使所有的w_{ij}都大于0,可以選擇不用的核函數(shù)來(lái)度量相似度煤伟,比如多項(xiàng)式核函數(shù)癌佩、徑向基核函數(shù)和sigmoid核函數(shù)。最常用的是徑向基核函數(shù):

w_{ij}=exp\left \{-\frac{||x_{i}-x_{j}||_{2}^{2}}{2\sigma ^{2}}\right \}

在實(shí)際應(yīng)用時(shí)選擇全連接法建立鄰接矩陣是最普遍的便锨,在選擇相似度度量時(shí)徑向基核函數(shù)是最普遍的围辙。

  1. 拉普拉斯矩陣

圖的拉普拉斯矩陣(Graph Laplacian)L_{N\times N}是一個(gè)對(duì)稱矩陣,用度矩陣減去鄰接矩陣得到的矩陣就被定義為拉普拉斯矩陣放案,L=D-W姚建。拉普拉斯矩陣有一些性質(zhì)如下:
①對(duì)稱性。
②由于其對(duì)稱性吱殉,則它的所有特征值都是實(shí)數(shù)掸冤。
③對(duì)于任意向量f厘托,有:

f^{T}Lf=\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}(f_{i}-f_{j})^{2}

這一性質(zhì)利用拉普拉斯矩陣的性質(zhì)很容易可以得到:

f^{T}Lf=f^{T}Df-f^{T}Wf \\ =\sum _{i=1}^{N}d_{i}f_{i}^{2}-\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}f_{i}f_{j}\\ =\frac{1}{2}(\sum _{i=1}^{N}d_{i}f_{i}^{2}-2\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}f_{i}f_{j}+\sum _{j=1}^{N}d_{j}f_{j}^{2})\\ =\frac{1}{2}(\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}f_{i}^{2}-2\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}f_{i}f_{j}+\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}f_{j}^{2})\\ =\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}w_{ij}(f_{i}-f_{j})^{2}

④拉普拉斯矩陣是半正定的,則其所有特征值非負(fù)稿湿,這個(gè)性質(zhì)由性質(zhì)③很容易得出铅匹。并且其最小的特征值為0,這是因?yàn)?img class="math-inline" src="https://math.jianshu.com/math?formula=L" alt="L" mathimg="1">的每一行和為0饺藤,對(duì)于全1向量1_{N}=\begin{pmatrix} 1 & 1 & \cdots & 1 \end{pmatrix}^{T}包斑,有L\cdot 1_{N}=0=0\cdot 1_{N}

  1. 無(wú)向圖切圖

對(duì)于無(wú)向圖G的切圖涕俗,我們的目標(biāo)是將G=(V,E)切成相互沒有連接的k個(gè)子圖罗丰,每個(gè)子圖節(jié)點(diǎn)的集合為A_{1},A_{2},\cdots ,A_{k},它們滿足A_{i}\cap A_{j}=\phi再姑,且A_{1}\cup A_{2}\cup \cdots \cup A_{k}=V萌抵。

對(duì)于任意兩個(gè)子圖點(diǎn)的集合A,B\subset V,定義AB之間的切圖權(quán)重為:

W(A,B)=\sum _{i\in A,j\in B}w_{ij}

對(duì)于k個(gè)子圖的集合询刹,定義切圖cut為:

cut(A_{1},A_{2},\cdots ,A_{k})=\sum_{i=1}^{k}W(A_{i}, \overline{A}_{i})

上式中\overline{A}_{ i }A_{i}的補(bǔ)集谜嫉,意為除A_{i}子集以外的其他子集的并集。

每個(gè)子圖就相當(dāng)于聚類的一個(gè)類凹联,找到子圖內(nèi)點(diǎn)的權(quán)重之和最高沐兰,子圖間的點(diǎn)的權(quán)重之和最低的切圖就相當(dāng)于找到了最佳的聚類。實(shí)現(xiàn)這一點(diǎn)的一個(gè)很自然的想法是最小化cut蔽挠。然而這種方法存在問(wèn)題住闯,也就是最小化的cut對(duì)應(yīng)的切圖不一定就是符合要求的最優(yōu)的切圖,如下圖:

舉例

在上面的例子中澳淑,我們選擇在最小的權(quán)重上進(jìn)行切圖比原,比如在CH之間進(jìn)行切圖,這樣可以使得cut最小杠巡,但并不是最優(yōu)的切圖量窘。

接下介紹譜聚類使用的切圖方法。

三氢拥、譜聚類之切圖聚類

為了避免上述最小化cut存在的問(wèn)題蚌铜,需要對(duì)每個(gè)子圖的規(guī)模做出限制,接下來(lái)介紹兩種切圖方法嫩海,分別是RatioCutNCut冬殃。

  1. RatioCut切圖

RatioCut切圖為了避免上述最小切圖,對(duì)于每個(gè)切圖叁怪,不只考慮最小化cut审葬,還考慮最大化每個(gè)子圖點(diǎn)的個(gè)數(shù),即:

RatioCut(A_{1},A_{2},\cdots ,A_{k})=\sum_{i=1}^{k}\frac{W(A_{i},\overline{A}_{i})}{|A_{i}|}

為了最小化RatioCut這個(gè)函數(shù),我們引入指示向量h_{i}\in \left \{h_{1},h_{1},\cdots ,h_{k}\right \},i=1,2,\cdots ,k涣觉,對(duì)于每一個(gè)向量h_{i}痴荐, 它是一個(gè)N維向量,另外定義h_{ij}為:

h_{ij}=\left\{\begin{matrix} 0,v_{j}\notin A_{i}\\ \frac{1}{\sqrt{|A_{i}|}},v_{j}\in A_{i} \end{matrix}\right.

那么對(duì)于h_{i}^{T}Lh_{i}旨枯,有:

h_{i}^{T}Lh_{i}=\frac{1}{2}\sum_{m=1}^{N}\sum_{n=1}^{N}w_{mn}(h_{im}-h_{in})^{2}\\ =\frac{1}{2}(\sum _{m\in A_{i},n\notin A_{i}}w_{mn}(\frac{1}{\sqrt{|A_{i}|}}-0)^{2}+\sum _{m\notin A_{i},n\in A_{i}}w_{mn}(0-\frac{1}{\sqrt{|A_{i}|}})^{2})\\ =\frac{1}{2}(\sum _{m\in A_{i},n\notin A_{i}}w_{mn}\frac{1}{|A_{i}|}+\sum _{m\notin A_{i},n\in A_{i}}w_{mn}\frac{1}{|A_{i}|})\\ =\frac{1}{2}(\frac{1}{|A_{i}|}\sum _{m\in A_{i},n\notin A_{i}}w_{mn}+\frac{1}{|A_{i}|}\sum _{m\notin A_{i},n\in A_{i}}w_{mn})\\ =\frac{1}{2}(\frac{cut(A_{i}, \overline{A}_{i} )}{|A_{i}|}+\frac{cut( \overline{A}_{i} ,A_{i})}{|A_{i}|})\\ =\frac{cut(A_{i},\overline{A}_{i})}{|A_{i}|}

由上式可知蹬昌,某一個(gè)子圖的RatioCut也就是h_{i}^{T}Lh_{i},所有的k個(gè)子圖的RatioCut表達(dá)式也就是:

RatioCut(A_{1},A_{2},\cdots ,A_{k})=\sum_{i=1}^{k}h_{i}^{T}Lh_{i} \\ =\sum_{i=1}^{k}(H^{T}LH)_{ii}\\ =tr(H^{T}LH)

上式中tr(H^{T}LH)為矩陣H^{T}LH的跡攀隔,H=\begin{pmatrix} h_{1} & h_{2} & \cdots & h_{k} \end{pmatrix}皂贩,需要注意這里的H滿足H^TH=I,并且H的元素只能取0或者\frac{1}{|A_{i}|}昆汹。也就是說(shuō)我們需要優(yōu)化以下目標(biāo)函數(shù):

\underset{H}{argmin}\; tr(H^{T}LH)\; \; s.t.\; H^{T}H=I

由于每個(gè)元素只能取兩個(gè)值明刷,因此上面的目標(biāo)函數(shù)是不可求導(dǎo)的。這里每個(gè)指示向量都是N維的满粗,而且每個(gè)元素只有兩種取值辈末,所以就有2^N種取值方式,一共有k個(gè)指示向量映皆,因此共有k2^NH挤聘,因此想要找到滿足使目標(biāo)函數(shù)最小的H是一個(gè)NP難的問(wèn)題。

由于存在上述問(wèn)題捅彻,所以我們采用降維的思想來(lái)考慮解決這個(gè)優(yōu)化問(wèn)題组去。我們需要最小化tr(H^{T}LH),也就是需要優(yōu)化每一個(gè)h_{i}^{T}Lh_{i}步淹,這里的h是單位正交基从隆,L是對(duì)稱矩陣,因此h_{i}^{T}Lh_{i}的最大值是L的最大特征值缭裆,最小值是L的最小特征值键闺。之所以有這種結(jié)論可以參考主成分分析PCA的解法,在PCA中需要找到協(xié)方差矩陣(類比此處的拉普拉斯矩陣L澈驼,它們都是對(duì)稱的)的最大特征值辛燥,而在譜聚類中需要找到最小的k個(gè)非零特征值尔艇,然后得到這些特征值對(duì)應(yīng)的特征向量溺森,通過(guò)這個(gè)過(guò)程我們也就完成了數(shù)據(jù)的降維,最終H_{N\times k}就是降維的結(jié)果菠隆,使用這個(gè)結(jié)果來(lái)近似解決這個(gè)NP難的問(wèn)題氏淑。

一般我們?nèi)匀恍枰獙?duì)H按行做標(biāo)準(zhǔn)化,也就是:

h_{ij}^{*}=\frac{h_{ij}}{(\sum_{t=1}^{k}h_{it}^{2})^{1/2}}

由于在降維時(shí)損失了少量信息硕噩,導(dǎo)致得到的優(yōu)化后的指示向量h對(duì)應(yīng)的H現(xiàn)在不能完全指示各樣本的歸屬假残,因此在得到降維結(jié)果H后還需要進(jìn)行一次傳統(tǒng)的聚類,比如K-Means。

  1. NCut切圖

NCut切圖的方法與RatioCut切圖的方法很類似辉懒,只是把RatioCut的分母|A_{i}|換成vol(A_{i})阳惹。使用NCut切圖時(shí),由于子圖樣本個(gè)數(shù)多不一定權(quán)重就大(只有權(quán)重大時(shí)眶俩,子圖內(nèi)樣本點(diǎn)的相似度才高)莹汤,因此切圖時(shí)基于權(quán)重也更符合目標(biāo),一般來(lái)說(shuō)NCut切圖優(yōu)于RatioCut切圖:

NCut(A_{1},A_{2},\cdots ,A_{k})=\sum_{i=1}^{k}\frac{W(A_{i},\overline{ A }_{ i } )}{vol(A_{i})}

另外需要修改指示向量的表示形式颠印,RatioCut的指示向量使用\frac{1}{\sqrt{|A_{i}|}}來(lái)標(biāo)示樣本歸屬纲岭,而NCut使用子圖權(quán)重\frac{1}{\sqrt{vol(A_{i})}}來(lái)標(biāo)示指示向量h,定義如下:

h_{ij}=\left\{\begin{matrix} 0,v_{j}\notin A_{i}\\ \frac{1}{\sqrt{vol(A_{i})}},v_{j}\in A_{i} \end{matrix}\right.

類似的线罕,對(duì)于h_{i}^{T}Lh_{i}止潮,有:

h_{i}^{T}Lh_{i}=\frac{1}{2}\sum_{m=1}^{N}\sum_{n=1}^{N}w_{mn}(h_{im}-h_{in})^{2}\\ =\frac{1}{2}(\sum _{m\in A_{i},n\notin A_{i}}w_{mn}(\frac{1}{\sqrt{vol(A_{i})}}-0)^{2}+\sum _{m\notin A_{i},n\in A_{i}}w_{mn}(0-\frac{1}{\sqrt{vol(A_{i})}})^{2})\\ =\frac{1}{2}(\sum _{m\in A_{i},n\notin A_{i}}w_{mn}\frac{1}{vol(A_{i})}+\sum _{m\notin A_{i},n\in A_{i}}w_{mn}\frac{1}{vol(A_{i})})\\ =\frac{1}{2}(\frac{1}{vol(A_{i})}\sum _{m\in A_{i},n\notin A_{i}}w_{mn}+\frac{1}{vol(A_{i})}\sum _{m\notin A_{i},n\in A_{i}}w_{mn})\\ =\frac{1}{2}(\frac{cut(A_{i},\overline{ A }_{ i } )}{vol(A_{i})}+\frac{cut( \overline{ A }_{ i } ,A_{i})}{vol(A_{i})})\\ =\frac{cut(A_{i}, \overline{ A }_{ i } )}{vol(A_{i})}

同樣的優(yōu)化目標(biāo)也就是:

NCut(A_{1},A_{2},\cdots ,A_{k})=\sum_{i=1}^{k}h_{i}^{T}Lh_{i} \\ =\sum_{i=1}^{k}(H^{T}LH)_{ii}\\ =tr(H^{T}LH)

但是現(xiàn)在的約束條件不再滿足H^TH=I,而是H^TDH=I钞楼,證明如下:

H^{T}DH=\begin{pmatrix} h_{1}^{T}\\ h_{2}^{T}\\ \vdots \\ h_{k}^{T} \end{pmatrix}\begin{pmatrix} d_{1} & & & \\ & d_{2} & & \\ & & \ddots & \\ & & & d_{N} \end{pmatrix}\begin{pmatrix} h_{1} & h_{2} & \cdots & h_{k} \end{pmatrix}\\ =\begin{pmatrix} h_{11}d_{1} & h_{12}d_{2} & \cdots & h_{1N}d_{N}\\ h_{21}d_{1} & h_{22}d_{2} & \cdots & h_{2N}d_{N}\\ \vdots & \vdots & \ddots & \vdots \\ h_{k1}d_{1} & h_{k2}d_{2} & \cdots & h_{kN}d_{N} \end{pmatrix}\begin{pmatrix} h_{1} & h_{2} & \cdots & h_{k} \end{pmatrix}\\ =\begin{pmatrix} \sum_{i=1}^{N}h_{1i}^{2}d_{i} & \sum_{i=1}^{N}h_{1i}h_{2i}d_{i} & \cdots & \sum_{i=1}^{N}h_{1i}h_{ki}d_{i}\\ \sum_{i=1}^{N}h_{2i}h_{1i}d_{i} & \sum_{i=1}^{N}h_{2i}^{2}d_{i} & \cdots & \sum_{i=1}^{N}h_{2i}h_{ki}d_{i}\\ \vdots & \vdots & \ddots & \vdots \\ \sum_{i=1}^{N}h_{ki}h_{1i}d_{i} & \sum_{i=1}^{N}h_{ki}h_{2i}d_{i} & \cdots & \sum_{i=1}^{N}h_{ki}^{2}d_{i} \end{pmatrix}

對(duì)于對(duì)角線元素有:

\sum_{j=1}^{N}h_{ij}^{2}d_{j}=\frac{1}{vol(A_{i})}\sum _{j\in A_{i}}d_{j}=\frac{1}{vol(A_{i})}vol(A_{i})=1

由于h_{mi}h_{ni}不可能同時(shí)非零喇闸,因此對(duì)于非對(duì)角線元素有:

\sum_{i=1}^{N}h_{mi}h_{ni}d_{i}=\sum_{i=1}^{N}0\cdot d_{i}=0

因此有H^TDH=I。我們最終優(yōu)化的目標(biāo)函數(shù)為:

\underset{H}{argmin}\; tr(H^{T}LH)\; \; s.t.\; H^{T}DH=I

此時(shí)指示向量h并不是標(biāo)準(zhǔn)正交基询件,所以在RatioCut中的降維思想不能直接使用燃乍。對(duì)于這個(gè)問(wèn)題,只需要將指示向量h做一個(gè)轉(zhuǎn)化即可宛琅,我們令H=D^{-1/2}F刻蟹,則:

H^{T}LH=F^{T}{\color{Red}{D^{-1/2}LD^{-1/2}}}F\\ H^{T}DH=F^{T}F=I

也就是說(shuō)優(yōu)化的目標(biāo)變成了:

\underset{F}{argmin}\; tr(F^{T}{\color{Red}{D^{-1/2}LD^{-1/2}}}F)\; \; s.t.\; F^{T}F=I

可以發(fā)現(xiàn)這個(gè)式子和RatioCut基本一致,只是中間的L變成了D^{-1/2}LD^{-1/2}夯秃。如此我們就可以按照RatioCut的思想座咆,求出D^{-1/2}LD^{-1/2}的前k個(gè)最小非零特征值,然后求對(duì)應(yīng)的特征向量再進(jìn)行標(biāo)準(zhǔn)化得到最后的特征矩陣F仓洼,然后再使用K-Means等傳統(tǒng)方法進(jìn)行聚類即可介陶。

一般來(lái)說(shuō),D^{-1/2}LD^{-1/2}相當(dāng)于對(duì)拉普拉普斯矩陣做了一次標(biāo)準(zhǔn)化色建,即(D^{-1/2}LD^{-1/2})_{ij}=\frac{L_{ij}}{\sqrt{d_{i}*d_{j}}}哺呜。

四、總結(jié)

  1. 算法流程

NCut切圖為例總結(jié)一下譜聚類算法的流程:

輸入:樣本集D=(x_{1},x_{2},\cdots ,x_{N})箕戳,鄰接矩陣的生成方式某残,降維后的維度k_1,聚類方法陵吸,聚類的簇個(gè)數(shù)k_2玻墅。
輸出:簇劃分C(c_{1},c_{2},\cdots ,c_{k_{2}})
①根據(jù)輸入的鄰接矩陣生成方式構(gòu)建樣本的鄰接矩陣矩陣W和度矩陣D壮虫;
②計(jì)算拉普拉斯矩陣L澳厢;
③構(gòu)建標(biāo)準(zhǔn)化后的拉普拉斯矩陣D^{-1/2}LD^{-1/2}环础;
④計(jì)算D^{-1/2}LD^{-1/2}的最小的前k_1個(gè)非零特征值對(duì)應(yīng)的特征向量f
⑤將各自對(duì)應(yīng)的特征向量f組成的矩陣按行標(biāo)準(zhǔn)化剩拢,最終得到N\times k_1維的特征矩陣F线得;
⑥對(duì)F的每一行作為一個(gè)k_1維的樣本,共N個(gè)樣本徐伐,用輸入的聚類方法進(jìn)行聚類贯钩,聚類的簇的個(gè)數(shù)為k_2
⑦得到簇劃分C(c_{1},c_{2},\cdots ,c_{k_{2}})办素。

  1. 優(yōu)缺點(diǎn)

譜聚類的優(yōu)點(diǎn)有:
①譜聚類只需要數(shù)據(jù)之間的相似度矩陣角雷,因此對(duì)于處理稀疏數(shù)據(jù)的聚類很有效。這點(diǎn)傳統(tǒng)聚類算法比如K-Means很難做到摸屠。
②由于使用了降維谓罗,因此在處理高維數(shù)據(jù)聚類時(shí)的復(fù)雜度比傳統(tǒng)聚類算法好。

譜聚類的缺點(diǎn)有:
①如果最終聚類的維度非常高季二,則由于降維的幅度不夠檩咱,譜聚類的運(yùn)行速度和最后的聚類效果均不好。
②聚類效果依賴于相似矩陣胯舷,不同的相似矩陣得到的最終聚類效果可能很不同刻蚯。

參考資料

ref:譜聚類(spectral clustering)原理總結(jié)

最后編輯于
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市桑嘶,隨后出現(xiàn)的幾起案子炊汹,更是在濱河造成了極大的恐慌,老刑警劉巖逃顶,帶你破解...
    沈念sama閱讀 222,590評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件讨便,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡以政,警方通過(guò)查閱死者的電腦和手機(jī)霸褒,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,157評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來(lái)盈蛮,“玉大人废菱,你說(shuō)我怎么就攤上這事《队” “怎么了殊轴?”我有些...
    開封第一講書人閱讀 169,301評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵,是天一觀的道長(zhǎng)袒炉。 經(jīng)常有香客問(wèn)我旁理,道長(zhǎng),這世上最難降的妖魔是什么我磁? 我笑而不...
    開封第一講書人閱讀 60,078評(píng)論 1 300
  • 正文 為了忘掉前任韧拒,我火速辦了婚禮淹接,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘叛溢。我一直安慰自己,他們只是感情好劲适,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,082評(píng)論 6 398
  • 文/花漫 我一把揭開白布楷掉。 她就那樣靜靜地躺著,像睡著了一般霞势。 火紅的嫁衣襯著肌膚如雪烹植。 梳的紋絲不亂的頭發(fā)上,一...
    開封第一講書人閱讀 52,682評(píng)論 1 312
  • 那天愕贡,我揣著相機(jī)與錄音草雕,去河邊找鬼。 笑死固以,一個(gè)胖子當(dāng)著我的面吹牛墩虹,可吹牛的內(nèi)容都是我干的。 我是一名探鬼主播憨琳,決...
    沈念sama閱讀 41,155評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼诫钓,長(zhǎng)吁一口氣:“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼!你這毒婦竟也來(lái)了篙螟?” 一聲冷哼從身側(cè)響起菌湃,我...
    開封第一講書人閱讀 40,098評(píng)論 0 277
  • 序言:老撾萬(wàn)榮一對(duì)情侶失蹤,失蹤者是張志新(化名)和其女友劉穎遍略,沒想到半個(gè)月后惧所,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 46,638評(píng)論 1 319
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡绪杏,尸身上長(zhǎng)有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,701評(píng)論 3 342
  • 正文 我和宋清朗相戀三年下愈,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片寞忿。...
    茶點(diǎn)故事閱讀 40,852評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡驰唬,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出腔彰,到底是詐尸還是另有隱情叫编,我是刑警寧澤,帶...
    沈念sama閱讀 36,520評(píng)論 5 351
  • 正文 年R本政府宣布霹抛,位于F島的核電站搓逾,受9級(jí)特大地震影響,放射性物質(zhì)發(fā)生泄漏杯拐。R本人自食惡果不足惜霞篡,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,181評(píng)論 3 335
  • 文/蒙蒙 一世蔗、第九天 我趴在偏房一處隱蔽的房頂上張望。 院中可真熱鬧朗兵,春花似錦污淋、人聲如沸。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,674評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽(yáng)。三九已至盐欺,卻和暖如春赁豆,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背冗美。 一陣腳步聲響...
    開封第一講書人閱讀 33,788評(píng)論 1 274
  • 我被黑心中介騙來(lái)泰國(guó)打工魔种, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人粉洼。 一個(gè)月前我還...
    沈念sama閱讀 49,279評(píng)論 3 379
  • 正文 我出身青樓节预,卻偏偏與公主長(zhǎng)得像,于是被迫代替她去往敵國(guó)和親漆改。 傳聞我的和親對(duì)象是個(gè)殘疾皇子心铃,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,851評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容