所謂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技術社區-登錄
下一篇
前往理由 (Reason to go):1. 死亡谷國傢公園是除阿拉斯加外最大的國傢公園,幾近深不可測。公園占地面積 330萬英畝/134萬公...