所謂LLE（局部線性嵌入）即”Locally Linear Embedding”的降維算法，在處理所謂流形降維的時候，效果比PCA要好很多。

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

LLE的降維實現過程，直觀的可視化效果如下圖1所示：

LLE降維可視化效果

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

既然是線性，則對每個數據點 (D維數據，即 Dtimes1 的列向量)，可以用其近鄰數據點的線性組合來表示(見下圖所示)

87bc787cd85e9dc6961f2cb78eb76eca

相應的數學表達式即: large x_i = sum_{j=1}^{k}w_{ji}x_{ji}

上式中，w_i 是 ktimes1 的列向量， w_{ji} 是 w_{i} 的第 j 行, x_{ji} 是 x_{i} 的第 j 個近鄰點。

通過使下述loss-function最小化： argmin limits_{w}sum_{i=1}^{N}(|x_i-sum_{j=1}^{k}w_{ji}x_{ji}|_2^2)

求解上式可得到權重系數 w = [w_1, w_2, ..., w_N]

其中 w 對應於 N 個數據點，即N 列 w_i(i=1,2,...N) 。

接下來是LLE中又一個假設：即認為將原始數據從 D 維降到 d 維後， x_i(Dtimes 1) rightarrow y_i(dtimes 1) ,其依舊可以表示為其 k 近鄰的線性組合，且組合系數不變，即 仍然是 w_i ,再一次通過最小化loss-function:

\argmin limits_{Y}sum_{i=1}^{N}(|y_i-sum_{j=1}^{k}w_{ji}y_{ji}|_2^2)

最終得到降維後位於低維空間的的數據: Y=[y_1,y_2,...,y_N]。

詳細的算法推導過程如下：

step 1：運用k近鄰算法得到每個數據 x_i 的 k 近鄰點：

\N_i = knn(x_i,k), N_i = [x_{1i}, ..., x_{ki}]

step 2: 求解權重系數矩陣,即求解如下有約束優化問題：

\argmin limits_{w}sum_{i=1}^{N} |x_i - sum_{j=1}^{k}w_{ji}x_{ji}|^2, s.t. sum_{j=1}^k w_{ji}=1

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

　　 輸入： X = [x_1, x_2, ..., x_N], Dtimes N

　　 權重： w= [w_1, w_2, ..., w_N], ktimes N

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

Phi(w)=sum_{i=1}^{N} |x_i - sum_{j=1}^{k}w_{ji}x_{ji}|^2=sum_{i=1}^{N} |sum_{j=1}^k (x_i-x_{ji})w_{ji}|^2\ =sum_{i=1}^N |(X_i-N_i)w_i|^2, X_i =underbrace {[x_i, ..., x_i]}_k, N_i = [x_{1i}, ..., x_{ki}]\= sum_{i=1}^N w_i^T(X_i-N_i)^T(X_i-N_i)w_i

將 S_i 看做局部協方差矩陣, 即:

\ S_i = (X_i-N_i)^T(X_i-N_i)

\Phi(w)=sum_{i=1}^N w_i^T S_i w_i

運用拉格朗日乘子法： L(w_i) = w_i^T S_i w_i + lambda(w_i^T1_k-1)

求導可得： frac{partial L(w_i)}{partial w_i} = 2S_iw_i+lambda 1_k = 0

\ w_i = frac{S_i^{-1}1_k}{1_k^T S_i^{-1}1_k}

其中 1_k 為 ktimes 1 的元素全1的列向量，就上述表達式而言，局部協方差矩陣 S_i 是個 ktimes k 的矩陣，其分母實質是矩陣 S_i 逆矩陣的所有元素之和，而其分子是 S_i 的逆矩陣對行求和後得到的列向量。

step 3: 映射到低維空間

即求解下述有約束優化問題：

\arg min limits_{Y} Psi(Y) = sum_{i=1}^N|y_i - sum_{j=1}^k w_{ji}y_{ji}|^2,

\ s.t. sum_{i=1}^N y_i = 0, sum_{i=1}^N y_i y_i^T = NI_{dtimes d}

輸出結果即低維空間向量組成的矩陣： Y = [y_1, y_2, ..., y_N], 維度為 dtimes N

首先，用一個 Ntimes N 的稀疏矩陣(sparse matrix) W 來表示 w :

對 i 的近鄰點 j ： W_{ji} = w_{ji} ，否則非臨近點 : W_{ji} = 0

因此： sum_{j=1}^N w_{ji}y_{ji} =sum_{j=1}^k w_{ji}y_{ji} =YW_i

其中， w_{k+1,i}=w_{k+2,i}=...=w_{N,i}=0

其中， W_i 是 方陣 W(Ntimes{N}) 的第 i 列, I_i 是 單位矩陣 I(Ntimes{N}) 的第 i 列， y_i 對應矩陣 Y 的第 i 列，所以 :

\Psi(Y) = sum_{i=1}^N|Y(I_i-W_i)|^2

由矩陣論相關知識可知：對矩陣 A = [a_1, a_2, ..., a_N] ，有

\sum_i (a_i)^2 = sum_i a_i^T a_i = tr(AA^T)

所以：

\Psi(Y) = tr(Y(I-W)(I-W)^TY^T)= tr(YMY^T)

\ M = (I-W)(I-W)^T

再一次使用拉格朗日乘子法：

\L(Y) = YMY^T+lambda (YY^T-NI)

求導：

\frac{partial L}{partial Y} = 2MY^T+2lambda Y^T = 0

即:

\MY^T = lambda'Y^T

可見 Y 其實是 M 的特征向量構成的矩陣，為瞭將數據降到 d 維，我們隻需取 M 的最小的 d 個非零特征值對應的特征向量，而一般第一個最小的特征值接近0，我們將其舍棄，最終按從小到大取前 [2, d+1] 個特征值對應的特征向量。

結果演示

對swiss roll數據集進行瞭LLE降維。原始的數據如下：

1ed600c070b85dce24828c647f06f879swiss roll數據集可視化效果圖

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

​

LLE降維在不同k值的二維分佈結果

k代表在k近鄰算法時選取的最近鄰個數。

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

原文鏈接：CSDN-專業IT技術社區-登錄