matlab jacobi算法求特征值_降維打擊之LLE算法

　　　　　　　　　　　　　背景

　　最近在溫習之前了解過的spectral clustering 的時候接觸到一個看着bigger滿滿的術語：manifold learing，然後順藤摸瓜找到一篇2000年的science，不過他們當時并沒有大肆炒這個manifold learning的概念，而是提出了一種叫做“local linear embedding”的降維算法，在處理所謂的流形的降維的時候，效果比PCA要好很多。于是我了解了下這個“簡約而不簡單”的LLE算法的具體實作方法，寫一下我目前的了解。

圖檔來源

　　首先，所謂流形，我腦海裡最直覺的印象就是上圖這種Swiss roll,我吃的時候喜歡把它整個攤開成一張餅再吃，其實這個過程就實作了對瑞士卷的降維操作，即從三維降到了兩維。降維前，我們看到相鄰的卷層之間看着距離很近，但其實攤開成餅狀後才發現其實距離很遠，是以如果不進行降維操作，而是直接根據近鄰原則去判斷相似性其實是不準确的。

　　　　　　　　　　　　原理

　　LLE的原理其實是這樣的：

• 所謂局部線性，就是認為在整個資料集的某小範圍内，資料是線性的，就比如雖然地球是圓的，但我們還是可以認為我們的籃球場是個平面；而這個“小範圍”，最直接的辦法就是k-近鄰原則。這個“近鄰”的判斷也可以是不同的依據：比如歐氏距離，測地距離等。
• 既然是線性，那麼對每個資料點

  

  (D維資料，即

  

  的列向量)，可以用其k近鄰的資料點的線性組合來表示，即

  

  。其中，

  

  是

  

  的列向量，

  

  是

  

  的第

  

  行,

  

  是

  

  的第

  

  個近鄰點。
• 通過使loss function最小化：

  

  得到權重系數

  

  ,一共

  

  個資料點，對應

  

  列

  

  。
• 接下來是LLE中又一個假設：即認為将原始資料從D維降到d維後，

  

  ,其依舊可以表示為其k近鄰的線性組合，且組合系數不變，即

  

  ,再一次通過最小化loss function:

  

  得到降維後的資料。

　　　　　　　　　　　 算法推導

step 1 ：

運用k近鄰算法得到每個資料的k近鄰點：

step 2 :

求解權重系數矩陣

即求解：

在推導之前，我們首先統一下資料的矩陣表達形式

　　輸入：

　　權重：

則可逐漸推導出權重系數矩陣的表達式：

将

看做局部協方差矩陣 , 那麼 :

運用拉格朗日乘子法 ：

其中，

是全

的列向量。

求導：

　　就上述表達式而言，局部協方差矩陣

是個

的矩陣，根據讓矩陣計算說人話，其分母

其實是對

的所有元素求和，而其分子

是 對

的每行求和後得到的列向量。

step 3: 映射到低維空間

即求解：

　　低維空間向量：

首先，用一個

的稀疏矩陣(sparse matrix)

來表示

:

　　　　　對

的近鄰點

：

;

　　　　　否則:

是以：

是

方陣的第

列。是以

，

表示機關矩陣的第

列。

由矩陣論可知：對矩陣

，有

是以：

再一次拉格朗日乘子法：

求導：

即

　　可見Y其實是M的特征向量構成的矩陣，為了将資料降到

維，我們隻需要取M的最小的

個非零特征值對應的特征向量，而一般第一個最小的特征值接近0，我們将其舍棄，取前

個特征值對應的特征向量。

　　　　　　　　　　　　結果示範

　　借助matlab強大的矩陣運算能力對swiss roll資料集進行了LLE降維。原始的資料如下：

Fig.1. Swill roll資料集。

通過LLE降維後的結果如下：

Fig. 2. LLE降維在不同k值的二維分布結果。k代表在k近鄰算法時選取的最近鄰個數。

　　可以看出，當k取值較小（k=4）時，算法不能将資料很好地映射到低維空間，因為當近鄰個數太少時，不能很好地反映資料的拓撲結構。當k值取值适合，這裡選取的是k=15，可見不同顔色的資料能很好地被分開并保持适合的相對距離。但若k取值太大，如k=50，不同顔色的資料開始互相重疊，說明選取的近鄰個數太多則不能反映資料的流形資訊。

　　　　　　　　　　　　　思考

1. 在step 3中為什麼是取d個最小的非零特征值，而不是最大的

   

   個特征值呢？
2. 怎樣了解每一步的限制條件呢？

沒想到導入md檔案公式還是不能渲染出來，重新用知乎的公式編輯器把公式編輯了一遍，不得不吐槽一句：知乎的公式編輯真是不友善而且太不美觀了。。。

我是個人部落格搬運工

降維打擊之LLE算法​www.quanlion.com