譜聚類|機(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í)

無(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}$

鄰接矩陣

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

$\epsilon$ -近鄰法

首先需要設(shè)置一個(gè)閾值 $\epsilon$ 扼雏，比較任意兩點(diǎn) $x_i$ 與 $x_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)相似度只有 $\epsilon$ 和 $0$ 兩個(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ù)是最普遍的围辙。

拉普拉斯矩陣

圖的拉普拉斯矩陣（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}$ 。

無(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$ ，定義 $A$ 和 $B$ 之間的切圖權(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)行切圖比原，比如在 $C$ 和 $H$ 之間進(jìn)行切圖，這樣可以使得 $cut$ 最小杠巡，但并不是最優(yōu)的切圖量窘。

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

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

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

$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^N$ 種 $H$ 挤聘，因此想要找到滿足使目標(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。

$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é)

算法流程

以 $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}})$ 办素。

優(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é)

最后編輯于：2021.10.24 15:23:02

?著作權(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
惡毒庶女頂嫁案：這布局不是一般人想出來(lái)的
文/花漫我一把揭開白布楷掉。她就那樣靜靜地躺著，像睡著了一般霞势。火紅的嫁衣襯著肌膚如雪烹植。梳的紋絲不亂的頭發(fā)上，一...
開封第一講書人閱讀 52,682評(píng)論 1贊 312
城市分裂傳說(shuō)
那天愕贡，我揣著相機(jī)與錄音草雕，去河邊找鬼。笑死固以，一個(gè)胖子當(dāng)著我的面吹牛墩虹，可吹牛的內(nèi)容都是我干的。我是一名探鬼主播憨琳，決...
沈念sama閱讀 41,155評(píng)論 3贊 422
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼诫钓，長(zhǎng)吁一口氣：“原來(lái)是場(chǎng)噩夢(mèng)啊……” “哼！你這毒婦竟也來(lái)了篙螟？” 一聲冷哼從身側(cè)響起菌湃，我...
開封第一講書人閱讀 40,098評(píng)論 0贊 277
萬(wàn)榮殺人案實(shí)錄
序言：老撾萬(wàn)榮一對(duì)情侶失蹤，失蹤者是張志新（化名）和其女友劉穎遍略，沒想到半個(gè)月后惧所，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體，經(jīng)...
沈念sama閱讀 46,638評(píng)論 1贊 319
?護(hù)林員之死
正文獨(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
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布霹抛，位于F島的核電站搓逾，受9級(jí)特大地震影響，放射性物質(zhì)發(fā)生泄漏杯拐。R本人自食惡果不足惜霞篡，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 42,181評(píng)論 3贊 335
男人毒藥：我在死后第九天來(lái)索命
文/蒙蒙一世蔗、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧朗兵，春花似錦污淋、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 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