一、概述

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

數(shù)據(jù)

然而對于下圖所示的數(shù)據(jù)，單純的GMM和K-Means就無效了，可以通過核方法對數(shù)據(jù)進(jìn)行轉(zhuǎn)換，然后再進(jìn)行聚類：

數(shù)據(jù)

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

總結(jié)來說，聚類算法可以分為兩種思路：

①Compactness，這類有 K-means，GMM 等，但是這類算法只能處理凸集，為了處理非凸的樣本集，必須引?核技巧。
②Connectivity，這類以譜聚類為代表。

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

無向權(quán)重圖

譜聚類的方法基于帶權(quán)重的無向圖，圖的每個(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}$ 來表示， $W=[w_{ij}],1\leq i,j\leq N$ ，由于是無向圖，因此 $w_{ij}=w_{ji}$ 。

另外還有度的概念，這里可以類比有向圖中的出度和入度的概念，不過圖中的點(diǎn) $v_i$ 的度 $d_i$ 并不是和該點(diǎn)相連的點(diǎn)的數(shù)量，而是和其相連的邊的權(quán)重之和，也就是鄰接矩陣的每一行的值加起來，即：

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

而圖的度矩陣（對角矩陣） $D_{N\times N}$ 可以表示如下：

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

另外我們定義，對于點(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)造的鄰接矩陣不對稱，而譜聚類算法需要一個(gè)對稱的鄰接矩陣。因此有以下兩種方法來構(gòu)造一個(gè)對稱的鄰接矩陣：

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

$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í)能夠更加簡便，構(gòu)建的鄰接矩陣也就表明了哪些樣本點(diǎn)之間有邊連接。也可以采用先建立圖然后再在圖上有邊的數(shù)據(jù)點(diǎn)上保留權(quán)重獲得鄰接矩陣的方法。

全連接法

這種方法會(huì)使所有的 $w_{ij}$ 都大于 $0$ ，可以選擇不用的核函數(shù)來度量相似度，比如多項(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è)對稱矩陣，用度矩陣減去鄰接矩陣得到的矩陣就被定義為拉普拉斯矩陣， $L=D-W$ 。拉普拉斯矩陣有一些性質(zhì)如下：
①對稱性。
②由于其對稱性，則它的所有特征值都是實(shí)數(shù)。
③對于任意向量 $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$ ，對于全 $1$ 向量 $1_{N}=\begin{pmatrix} 1 & 1 & \cdots & 1 \end{pmatrix}^{T}$ ，有 $L\cdot 1_{N}=0=0\cdot 1_{N}$ 。

無向圖切圖

對于無向圖 $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$ 。

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

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

對于 $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$ 。然而這種方法存在問題，也就是最小化的 $cut$ 對應(yīng)的切圖不一定就是符合要求的最優(yōu)的切圖，如下圖：

舉例

在上面的例子中，我們選擇在最小的權(quán)重上進(jìn)行切圖，比如在 $C$ 和 $H$ 之間進(jìn)行切圖，這樣可以使得 $cut$ 最小，但并不是最優(yōu)的切圖。

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

三、譜聚類之切圖聚類

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

$RatioCut$ 切圖

$RatioCut$ 切圖為了避免上述最小切圖，對于每個(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$ ，對于每一個(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.$

那么對于 $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}|}$ 。也就是說我們需要優(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難的問題。

由于存在上述問題，所以我們采用降維的思想來考慮解決這個(gè)優(yōu)化問題。我們需要最小化 $tr(H^{T}LH)$ ，也就是需要優(yōu)化每一個(gè) $h_{i}^{T}Lh_{i}$ ，這里的 $h$ 是單位正交基， $L$ 是對稱矩陣，因此 $h_{i}^{T}Lh_{i}$ 的最大值是 $L$ 的最大特征值，最小值是 $L$ 的最小特征值。之所以有這種結(jié)論可以參考主成分分析PCA的解法，在PCA中需要找到協(xié)方差矩陣（類比此處的拉普拉斯矩陣 $L$ ，它們都是對稱的）的最大特征值，而在譜聚類中需要找到最小的 $k$ 個(gè)非零特征值，然后得到這些特征值對應(yīng)的特征向量，通過這個(gè)過程我們也就完成了數(shù)據(jù)的降維，最終 $H_{N\times k}$ 就是降維的結(jié)果，使用這個(gè)結(jié)果來近似解決這個(gè)NP難的問題。

一般我們?nèi)匀恍枰獙?img class="math-inline" src="https://math.jianshu.com/math?formula=H" alt="H" mathimg="1">按行做標(biāo)準(zhǔn)化，也就是：

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

由于在降維時(shí)損失了少量信息，導(dǎo)致得到的優(yōu)化后的指示向量 $h$ 對應(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)，一般來說 $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}|}}$ 來標(biāo)示樣本歸屬，而 $NCut$ 使用子圖權(quán)重 $\frac{1}{\sqrt{vol(A_{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.$

類似的，對于 $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}$

對于對角線元素有：

$\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í)非零，因此對于非對角線元素有：

$\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$ 中的降維思想不能直接使用。對于這個(gè)問題，只需要將指示向量 $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$

也就是說優(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è)最小非零特征值，然后求對應(yīng)的特征向量再進(jìn)行標(biāo)準(zhǔn)化得到最后的特征矩陣 $F$ ，然后再使用K-Means等傳統(tǒng)方法進(jìn)行聚類即可。

一般來說， $D^{-1/2}LD^{-1/2}$ 相當(dāng)于對拉普拉普斯矩陣做了一次標(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è)非零特征值對應(yīng)的特征向量 $f$ ；
⑤將各自對應(yīng)的特征向量 $f$ 組成的矩陣按行標(biāo)準(zhǔn)化，最終得到 $N\times k_1$ 維的特征矩陣 $F$ ；
⑥對 $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ù)之間的相似度矩陣，因此對于處理稀疏數(shù)據(jù)的聚類很有效。這點(diǎn)傳統(tǒng)聚類算法比如K-Means很難做到。
②由于使用了降維，因此在處理高維數(shù)據(jù)聚類時(shí)的復(fù)雜度比傳統(tǒng)聚類算法好。

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

參考資料

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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

一、概述

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

三、譜聚類之切圖聚類

四、總結(jié)

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

一、概述

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

三、譜聚類之切圖聚類

四、總結(jié)

參考資料

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

一、概述

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

三、譜聚類之切圖聚類

四、總結(jié)