0 引言

    11月1日上午，機(jī)器學(xué)習(xí)班第7次課,，鄒博講聚類（PPT）,，其中的譜聚類引起了自己的興趣，他從最基本的概念：單位向量,、兩個(gè)向量的正交,、方陣的特征值和特征向量,，講到相似度圖,、拉普拉斯矩陣，最后講譜聚類的目標(biāo)函數(shù)和其算法流程。

    課后自己又琢磨了番譜聚類跟拉普拉斯矩陣,，打算寫篇博客記錄學(xué)習(xí)心得， 若有不足或建議,，歡迎隨時(shí)不吝指出,，thanks。

1 矩陣基礎(chǔ)

    在講譜聚類之前,，有必要了解一些矩陣方面的基礎(chǔ)知識,。

1.0 理解矩陣的12點(diǎn)數(shù)學(xué)筆記

    如果對矩陣的概念已經(jīng)模糊，推薦國內(nèi)一人寫的《理解矩陣by孟巖》系列,，其中,，拋出了很多有趣的觀點(diǎn)，我之前在閱讀的過程中做了些筆記,，如下：

“1,、簡而言之：矩陣是線性空間里的變換的描述，相似矩陣則是對同一個(gè)線性變換的不同描述,。那，何謂空間,？本質(zhì)而言,，“空間是容納運(yùn)動(dòng)的一個(gè)對象集合，而變換則規(guī)定了對應(yīng)空間的運(yùn)動(dòng)”by孟巖,。在線性空間選定基后,，向量刻畫對象的運(yùn)動(dòng)，運(yùn)動(dòng)則通過矩陣與向量相乘來施加,。然,，到底什么是基？坐標(biāo)系也,。

1.1 一堆基礎(chǔ)概念

    根據(jù)wikipedia的介紹,，在矩陣中，n階單位矩陣,，是一個(gè)的方形矩陣,，其主對角線元素為1，其余元素為0,。單位矩陣以表示,；如果階數(shù)可忽略，或可由前后文確定的話,，也可簡記為（或者E）,。 如下圖所示,，便是一些單位矩陣：

    單位矩陣中的第列即為單位向量。單位向量同時(shí)也是單位矩陣的特征向量,，特征值皆為1,，因此這是唯一的特征值，且具有重?cái)?shù)n,。由此可見,，單位矩陣的行列式為1，且跡數(shù)為n,。 

    

    單位向量又是什么呢,？數(shù)學(xué)上，賦范向量空間中的單位向量就是長度為 1 的向量,。歐幾里得空間中,，兩個(gè)單位向量的點(diǎn)積就是它們之間角度的余弦（因?yàn)樗鼈兊拈L度都是 1）。

    一個(gè)非零向量的正規(guī)化向量（即單位向量）就是平行于的單位向量,，記作：

    這里是的范數(shù)（長度）,。

    何謂點(diǎn)積？點(diǎn)積又稱內(nèi)積,，兩個(gè)向量 = [a1, a2,…, an]和 = [b1, b2,…, bn]的點(diǎn)積定義為：

    這里的Σ指示求和符號,。

    例如，兩個(gè)三維向量[1, 3, -5]和[4, -2, -1]的點(diǎn)積是：

    這里的指示矩陣的轉(zhuǎn)置,。使用上面的例子，將一個(gè)1×3矩陣（就是行向量）乘以一個(gè)3×1向量得到結(jié)果(通過矩陣乘法的優(yōu)勢得到1×1矩陣也就是標(biāo)量)：

    除了上面的代數(shù)定義外,，點(diǎn)積還有另外一種定義：幾何定義,。在歐幾里得空間中，點(diǎn)積可以直觀地定義為：

    這里||表示的模（長度）,，θ表示兩個(gè)向量之間的角度,。 根據(jù)這個(gè)定義式可得：兩個(gè)互相垂直的向量的點(diǎn)積總是零。若和都是單位向量（長度為1）,，它們的點(diǎn)積就是它們的夾角的余弦,。 

    正交是垂直這一直觀概念的推廣，若內(nèi)積空間中兩向量的內(nèi)積（即點(diǎn)積）為0,，則稱它們是正交的,，相當(dāng)于這兩向量垂直,，換言之,，如果能夠定義向量間的夾角，則正交可以直觀的理解為垂直,。而正交矩陣（orthogonal matrix）是一個(gè)元素為實(shí)數(shù),，而且行與列皆為正交的單位向量的方塊矩陣（方塊矩陣,，或簡稱方陣，是行數(shù)及列數(shù)皆相同的矩陣,。）

    若數(shù)字和非零向量滿足,，則為的一個(gè)特征向量，是其對應(yīng)的特征值,。 換句話說,，在這個(gè)方向上，做的事情無非是把沿其的方向拉長/縮短了一點(diǎn)（而不是毫無規(guī)律的多維變換）,，則是表示沿著這個(gè)方向上拉伸了多少的比例,。 簡言之，對做了手腳,，使得向量變長或變短了,，但本身的方向不變。

     矩陣的跡是矩陣的對角線元素之和,，也是其個(gè)特征值之和,。 

2 拉普拉斯矩陣

2.1 Laplacian matrix的定義

    拉普拉斯矩陣（Laplacian matrix)）,，也稱為基爾霍夫矩陣, 是表示圖的一種矩陣。給定一個(gè)有n個(gè)頂點(diǎn)的圖,，其拉普拉斯矩陣被定義為:

    其中為圖的度矩陣,，為圖的鄰接矩陣。

    把此“圖”轉(zhuǎn)換為鄰接矩陣的形式，記為：

    把的每一列元素加起來得到個(gè)數(shù),，然后把它們放在對角線上（其它地方都是零）,，組成一個(gè)的對角矩陣，記為度矩陣,，如下圖所示：

    根據(jù)拉普拉斯矩陣的定義,，可得拉普拉斯矩陣 為：

2.2 拉普拉斯矩陣的性質(zhì)  

    其中，定義為節(jié)點(diǎn)到節(jié)點(diǎn)的權(quán)值,，如果兩個(gè)節(jié)點(diǎn)不是相連的,，權(quán)值為零。
    ②與某結(jié)點(diǎn)鄰接的所有邊的權(quán)值和定義為該頂點(diǎn)的度d,，多個(gè)d 形成一個(gè)度矩陣 （對角陣）

    拉普拉斯矩陣 具有如下性質(zhì)：

    其中，,，,，。

3 譜聚類

3.1 相關(guān)定義

3.2 目標(biāo)函數(shù)

   

    設(shè)為圖的幾個(gè)子集（它們沒有交集） ，為了讓分割的Cut 值最小,，譜聚類便是要最小化下述目標(biāo)函數(shù)： 

    其中k表示分成k個(gè)組,， 表示第i個(gè)組，表示 的補(bǔ)集,，表示第 組與第組之間的所有邊的權(quán)重之和（換言之,，如果要分成K個(gè)組,，那么其代價(jià)就是進(jìn)行分割時(shí)去掉的邊的權(quán)值的總和）。

    為了讓被切斷邊的權(quán)值之和最小,，便是要讓上述目標(biāo)函數(shù)最小化,。但很多時(shí)候，最小化cut 通常會(huì)導(dǎo)致不好的分割,。以分成2類為例,，這個(gè)式子通常會(huì)將圖分成了一個(gè)點(diǎn)和其余的n-1個(gè)點(diǎn)。如下圖所示,，很明顯,，最小化的smallest cut不是最好的cut，反而把{A,、B,、C、H}分為一邊,，{D,、E、F,、G}分為一邊很可能就是最好的cut：

    為了讓每個(gè)類都有合理的大小,，目標(biāo)函數(shù)盡量讓A1,A2...Ak 足夠大。改進(jìn)后的目標(biāo)函數(shù)為：

    其中|A|表示A組中包含的頂點(diǎn)數(shù)目,。

   或：

    其中,，。

3.3 最小化RatioCut  與最小化等價(jià)

    下面,，咱們來重點(diǎn)研究下RatioCut 函數(shù),。

    目標(biāo)函數(shù)：
    定義向量，且：

    根據(jù)之前得到的拉普拉斯矩陣矩陣的性質(zhì),，已知

    現(xiàn)在把的定義式代入上式,，我們將得到一個(gè)非常有趣的結(jié)論！推導(dǎo)過程如下：

    是的,，我們竟然從推出了RatioCut,，換句話說，拉普拉斯矩陣L 和我們要優(yōu)化的目標(biāo)函數(shù)RatioCut 有著密切的聯(lián)系,。更進(jìn)一步說,，因?yàn)?img doc360img-src='http://image84.360doc.com/DownloadImg/2015/03/3022/51807656_73' src="http://pubimage.360doc.com/wz/default.gif" alt="">是一個(gè)常量，所以最小化RatioCut,，等價(jià)于最小化,。

    同時(shí)，因單位向量的各個(gè)元素全為1，所以直接展開可得到約束條件：且,，具體推導(dǎo)過程如下：

    最終我們新的目標(biāo)函數(shù)可以由之前的,，寫成：

    其中，,，且因,，所以有：f'f = n（注：f是列向量的前提下，f'f是一個(gè)值,，實(shí)數(shù)值，ff'是一個(gè)N*N的矩陣）,。

    繼續(xù)推導(dǎo)前,，再次提醒特征向量和特征值的定義：

• 若數(shù)字和非零向量滿足，則為的一個(gè)特征向量,，是其對應(yīng)的特征值,。

    假定  =  ，此刻,，是特征值,， 是 的特征向量。兩邊同時(shí)左乘,，得到 = ,，而f'f=n，其中n為圖中頂點(diǎn)的數(shù)量之和,，因此 = n,，因n是個(gè)定值，所以要最小化,，相當(dāng)于就是要最小化,。因此，接下來,，我們只要找到 的最小特征值及其對應(yīng)的特征向量即可,。

    但到了這關(guān)鍵的最后一步，咱們卻遇到了一個(gè)比較棘手的問題,，即由之前得到的拉普拉斯矩陣的性質(zhì)“最小的特征值為零,，并且對應(yīng)的特征向量正好為”可知：其不滿足的條件，因此,，怎么辦呢,？根據(jù)論文“A Tutorial on Spectral Clustering”中所說的Rayleigh-Ritz 理論，我們可以取第2小的特征值,，以及對應(yīng)的特征向量,。 

    更進(jìn)一步，由于實(shí)際中，特征向量 里的元素是連續(xù)的任意實(shí)數(shù),，所以可以根據(jù) 是大于0,，還是小于0對應(yīng)到離散情況下的，決定 是取,，還是取,。而如果能求取 的前K個(gè)特征向量，進(jìn)行K-means聚類,，得到K個(gè)簇,，便從二聚類擴(kuò)展到了K 聚類的問題。

    就這樣，因?yàn)殡x散求解很困難,，但RatioCut 巧妙地把一個(gè)NP難度的問題轉(zhuǎn)換成拉普拉斯矩陣特征值（向量）的問題,，將離散的聚類問題松弛為連續(xù)的特征向量，最小的系列特征向量對應(yīng)著圖最優(yōu)的系列劃分方法,。剩下的僅是將松弛化的問題再離散化,，即將特征向量再劃分開，便可以得到相應(yīng)的類別,。不能不說妙哉,！

3.4 譜聚類算法過程

    綜上可得譜聚類的算法過程如下：

1. 根據(jù)數(shù)據(jù)構(gòu)造一個(gè)Graph，Graph的每一個(gè)節(jié)點(diǎn)對應(yīng)一個(gè)數(shù)據(jù)點(diǎn),，將各個(gè)點(diǎn)連接起來（隨后將那些已經(jīng)被連接起來但并不怎么相似的點(diǎn),，通過cut/RatioCut/NCut 的方式剪開），并且邊的權(quán)重用于表示數(shù)據(jù)之間的相似度,。把這個(gè)Graph用鄰接矩陣的形式表示出來,，記為 ,。
2. 把的每一列元素加起來得到個(gè)數(shù)，把它們放在對角線上（其他地方都是零）,，組成一個(gè)的對角矩陣,，記為度矩陣，并把 - 的結(jié)果記為拉普拉斯矩陣,。
3. 求出的前個(gè)特征值（前個(gè)指按照特征值的大小從小到大排序得到）,，以及對應(yīng)的特征向量。
4. 把這個(gè)特征（列）向量排列在一起組成一個(gè)的矩陣,，將其中每一行看作維空間中的一個(gè)向量,，并使用 K-means 算法進(jìn)行聚類。聚類的結(jié)果中每一行所屬的類別就是原來 Graph 中的節(jié)點(diǎn)亦即最初的個(gè)數(shù)據(jù)點(diǎn)分別所屬的類別,。

    或許你已經(jīng)看出來,，譜聚類的基本思想便是利用樣本數(shù)據(jù)之間的相似矩陣（拉普拉斯矩陣）進(jìn)行特征分解（ 通過Laplacian Eigenmap 的降維方式降維），然后將得到的特征向量進(jìn)行 K-means聚類,。

    此外,，譜聚類和傳統(tǒng)的聚類方法（例如 K-means）相比,，譜聚類只需要數(shù)據(jù)之間的相似度矩陣就可以了,，而不必像K-means那樣要求數(shù)據(jù)必須是 N 維歐氏空間中的向量。

4 參考文獻(xiàn)與推薦閱讀