作者 | 荔枝boy
目錄
一. 拉普拉斯矩陣性質
二.拉普拉斯矩陣與圖分割的聯繫
三.Ratiocut
四.總結
一. 拉普拉斯矩陣性質
這篇文章可能會有些枯燥，著重分享了譜聚類的原理中的一些思想，以及自己本人對譜聚類的一些理解。如果在看完這篇文章後，也能解決你對譜聚類的一些疑問，想必是對你我都是極好的。在之前查閱了很多關於譜聚類的資料，博客，但是發現有些地方仍不是很明白，比如為什麼用拉普拉斯矩陣L的特徵向量就能表示一個樣本，為什麼L總會有個最小特徵值是0等。
前文簡略的介紹瞭如何將所有樣本X構建成拉普拉斯矩陣，利用拉普拉斯矩陣對樣本點X進行合適大小的分割，此分割不需要類標，所以是無監督分割。那麼這其中具體的原理是什麼呢？為什麼將n個d維度的樣本Xi構建成了相似度矩陣後，構建拉普拉斯矩陣L，就能通過求解L矩陣特徵向量後，用特徵向量表示Xi，進行kmeans聚類表示Xi的聚類效果呢？
這裡我們要知道，拉普拉斯矩陣是基於樣本Xi之間構建的相似度矩陣構建的，所以拉普拉斯矩陣相當於是一個圖G（V，E），該矩陣（及改圖）包含了各個樣本點，以及樣本點之間的聯繫的信息。假設有6個樣本點，通過構建相似度矩陣，生成了拉普拉斯矩陣，有些樣本點是沒有聯繫的，如圖一：
圖一
我們想要對圖中的節點進行分割歸類，得到一個比較合理的樣本分割。
分割成如圖二的效果：
圖二
不得不感嘆前輩們的聰明智慧，將一個表示樣本點聯繫的圖分割，通過拉普拉斯矩陣轉換成了矩陣求解的問題。先彆著急想拉普拉斯矩陣L與圖像分割有什麼聯繫，我們先單純的從數學角度來L矩陣有什麼性質。假設一共有n個樣本Xi，現已知得到樣本點構建的相似度矩陣S（本章不在此展開，構建相似度矩陣有很多種方式，比如歐式距離，高斯距離等），S是大小為n*n的矩陣，S_ij記錄了Xi與Xj樣本間的聯繫。通過相似度矩陣S構建鄰接矩陣W（這裡構建W的方式也有很多，比如K近鄰，全連接構建W等），通過W_ij創建對角度矩陣D，大小為n*n，其中對角線元素,其餘位置Dij=0。構建了相似度矩陣W和度矩陣D後，就得到了拉普拉斯矩陣L=D-W。
我們發現L矩陣是一個全對稱矩陣，對角線元素是度矩陣中對應的Dii（i=j），其他位置的元素(i!=j)L_ij=-W_ij。
1）拉普拉斯性質一
該矩陣第一個性質，任意一個1*n維的f向量，我們都能得到如下公式，具體推導如公式一：
公式一
性質有什麼用呢，舉個例子，我們知道L是一個矩陣，假設該L代表的樣本Xi是全連接的，一個類。f是任意一個向量，其實Lf=λf，即λ是L的特徵值，而f是L的特徵向量。所以f’Lf=f’λf=λf’f，而f’*f是一個常數，所以我們會發現f’Lf是一個定值，假如λ=0，則f’Lf=0，求出來的f就是L對應特徵值為0的特徵向量。根據性質一，我們會發現W_ij>0,則要想f’Lf=0,必須有f_i=f_j。我們發現Xi的真實情況是都在一類中，而求出來的f’Lf=0中的特徵向量有f_i=f_j這個性質。我們可以將真實情況中Xi彼此為一類的現象與L的0特徵值對應的f_i=f_j這個性質聯繫，發現二者始終同步且二者只能互相依存。所以在此，我們可以設置拉普拉斯矩陣L的0特徵值對應的特徵向量f為全1向量，可以用f_i在某種程度代表Xi。求出的L的0特徵值對應特徵向量f_i=f_j，剛好可以代表Xi與Xj都是同一類。
2)拉普拉斯矩陣性質二
拉普拉斯矩陣L求出的0特徵值個數即對應有幾個聚類。聚類間的Xi互不聯繫。
之前假設的是L中n個樣本點全是一類，這是極特殊的現象，一般情況中假設L中有k個部分L1，L2，...Lk，這樣的矩陣Li中的元素互為同一類，如圖三所示:
圖三
在這種理想情況下，我們已知有k個聚類，而聚類之間元素沒有聯繫，置為0。L矩陣除了對角的L1，L2,...,Lk矩陣以外的位置上元素都是0。我們發現求出L對應的0特徵值個數k，即代表了整個圖中聚類的個數。求出對應每個0特徵值對應的特徵向量fi可以做Xi樣本的聚類指示器。eg：假設L是一個7*7的矩陣，其中L1是個3*3的矩陣，那麼代表X1,X2,X3是同一類，則求出L的其中一個0特徵值，與之對應的特徵向量可以表示為f1=[1,1,1,0,0,0,0]。通過該0特徵值對應的特徵向量，我們可以看見f中為1的下標對應的樣本Xi在同一類。
當然上述只是一種理想情況，在已知聚類結果的條件下，構建了此拉普拉斯矩陣L，讓不在同一類的樣本W_ij=0。得到0特徵值對應特徵向量做指示器，未免有些馬後炮的感覺。但是在此，我們也有了一個發現，就是拉普拉斯矩陣L的特徵向量，在一定程度上可以表示樣本Xi。
3) 拉普拉斯矩陣性質三
拉普拉斯矩陣L至少有一個特徵值為0。
通過性質二，我們很容易發現，一個L代表的樣本Xi，至少也會有一個類，也就是Xi與Xj之間互相都有聯繫，Lij>0。所以根據性質二反推，則一個拉普拉斯矩陣L至有一個特徵值為0。
二.拉普拉斯矩陣與圖分割的聯繫
介紹完了拉普拉斯矩陣的性質後，我們來講下拉普拉斯與圖分割的聯繫。
在開始我們交代過，有6個樣本點，我們用圖來表示這6個樣本點，希望能通過圖分割出比較好的幾個部分，即代表了這幾個樣本點的聚類。圖四就是我們想要的比較好的分割效果：
圖四
我們希望將所有樣本點分成A1,A2,...,Ak個部分，我們想要分割的代價最小，用如下公式表示該分割效果：
公式二
其中我們想要不同類之間有聯繫的樣本點權值相加，切割的部分即這些不同類的樣本點之間的邊，所以我們想要cut（A1，A2，...,Ak）最小。但是我們會發現，這種策略下的分割很容易造成分割不均勻的現象，如圖五所示：
圖五
圖五這樣的切割結果不是我們想要的分割結果，雖然分割的cut（A1，A2,...,Ak）最小，但是會造成分割出很多單個離散的樣本點作為一類，分割的類別不均勻。因此，我們提出了Ratiocut和Ncut兩種能夠均勻地切割圖的方法，分別如公式三所示：
公式三
其中Ratiocut中|Ai|代表Ai類別中樣本點的個數，Ncut中vol(Ai）代表Ai類別中所有邊的權重和。兩種切割方法都能很好的抑制樣本被過於極端的分割造成分割不均勻的現象。
三.Ratiocut
1)L的特徵向量h（指示器）
關鍵來了，拉普拉斯矩陣跟Ratiocut或者Ncut有什麼聯繫呢？在這裡我們以Ratiocut為例，我們想要min Ratiocut（A1,A2,...,Ak）。和上文中的L向量的特徵向量f（做指示器）一樣，現在引入{A1,A2,...,Ak}的指示向量h_j=[h1,h2,...,hk]，其中j=1,2,...,k，其中h_j的具體表達如公式四所示：
公式四
由拉普拉斯性質二最後得到的心得可以看到，在這裡我們可以讓h_j中的h1,h2等可以分別表示樣本X1，X2等，並且hj*1=0。這裡要注意h_j表示的是Aj類別的指示器，h_j中的數值只能表示在Aj中（1/sqrt（|Aj|））,和不在Aj中（0），所以h_j指示器只能侷限的表示所有樣本是否在一種類別Aj上，不能表示樣本與別的類別Ai之間的聯繫。我們需要更多的指示器h_i來表示樣本點與別的各類別之間的關係。
2）拉普拉斯矩陣min(f’Lf)等價min Ratiocut（Ai,~Ai）
指示器h_j是一個向量，那麼可以利用拉普拉斯矩陣性質一，用h_j向量來進行推導。推導過程公式五六所示：
公式五
公式六
這裡推導過程於拉普拉斯的性質一推導相同，我們設定了h_j中的值，將h_j替換成設定的值，繼續化簡，會發現化簡到最後就是Ratiocut。
公式七
我們發現設定一個指示器h_j，拉普拉斯矩陣L表示Xi，h_j做拉普拉斯矩陣L的特徵向量後，根據L的性質一，竟然hi’Lhi=Ratiocut（Ai，~Ai）。也就是說，我們可以將求解拉普拉斯矩陣性質一與Ratiocut（Ai，~Ai）等價。成功的將最小切割圖問題轉化成了求解矩陣特徵向量的問題。之前我們說了，h_j指示器中的值只能表示所有樣本點是否在類別Aj的關係，需要更多的指示器hi來表示所有樣本點跟別的類別的關係。而h_j對於拉普拉斯矩陣L，是L的特徵向量。所以需要更多的h_i就轉換成了需要L更多的特徵向量。根據min (hi’*L*hi)=min (hi’*λ*hi)=min (λhi’*hi)=min (λ*常數)，求解多分類的極小化問題轉換成了如下所示，約束條件由開始設定h_j’*1向量=0.得：
公式八
我們需要最小的特徵值，而L矩陣最小的特徵值必為0，對應特徵向量是全1向量,對於預測所有樣本與類別Ai間的聯繫沒有幫助，所以我們求得倒數二小的特徵值開始的前k個特徵值對應的特徵向量做指示器，因為每個L的特徵向量都是對某一類的指示，所以現在要聚k個類，我們就講這前k個特徵向量組成一個矩陣，大小為n*k。其中每一列是特徵向量hi，每一行i有k個位置，分別代表h1,h2,...,hk指示器對該樣本Xi與不同類別A1,A2,...,Ak的關係，間接表示一個樣本，這樣我們就可以通過前k個特徵向量表示每個樣本Xi後，用Kmeans對這些間接表示的樣本進行聚類。（這其中放寬了公式八多分類的約束條件，因為公式八是hj中是離散數值，這樣會造成NP-hard問題）最終，前輩們成功的將圖分割問題與求解拉普拉斯矩陣L的特徵向量成功聯繫在一起，給前輩們一個贊！Ncut原理也與Ratiocut類似，在此不重複介紹。
3)疑問
不過在整個推理譜聚類的過程中還存在一個問題，沒有搞明白，譜聚類中核心是對拉普拉斯矩陣進行特徵分解，求其最小k個特徵向量，用這些特徵向量降維表示Xi，然後kmeans聚類。但是如公式八所示，最小化圖分割問題裡，求解出來的特徵向量是有約束條件的，怎麼能保證求得的倒數k個小特徵值對應的特徵值向量hi就一定滿足hi*1=0呢？
四. 總結
拉普拉斯矩陣L有很多特殊的性質，通過這些性質我們發現了L矩陣的特徵向量中每個元素i可以一定程度上與表示樣本Xi。通過這個特性，前輩們成功的通過求解L的k個特徵向量，綜合來表示樣本Xi，等價求解將整個圖的最小化分割問題。所以，可以說拉普拉斯矩陣的作用是對所有樣本進行了降維表示，因為是用特徵向量表示，所以整個圖拉普拉斯矩陣在用k個特徵向量表示後也保留了很多關鍵信息，最後通過kmeans對這些降維後的Xi進行聚類。
對深度學習感興趣，熱愛Tensorflow的小夥伴，歡迎關注我們的網站！http://www.panchuang.net 我們的公眾號：磐創AI。
閱讀更多 人工智能遇見磐創 的文章
