淺談局部線性嵌入
淺談局部線性嵌入
01-數據降維
數據降維是指通過線性的或非線性的映射關係將高維數據轉換成低維數據的過程。一般情況下，該低維數據代表了原始高維數據的主要成分（圖1），並描述了原始高維數據的空間分布結構。由於經過降維後的數據更易於被分類、識別、可視化以及存儲等，故數據降維技術在諸多科研領域受到了越來越多地關注。
從數據本身的的性質特徵來看，數據降維可以大致分為線性降維和非線性降維兩種技術方法。其中，線性降維技術僅對於數據維數相對較低、且具有全局線性結構的數據有著很好的降維效果。然而，在實際的科學研究中，科研工作者卻需要面對海量的非線性高維數據。因此，能夠有效處理高維非線性數據的方法亟待被提出，本文將介紹一種用於處理高維非線性數據的降維方法。
圖1
02-局部線性嵌入
02-01-全局重建矩陣的求解
局部線性嵌入（Locally linear embedding, LLE）是一種非線性的降維方法，該演算法由 Sam T.Roweis等人於2000年提出並發表在《Science》雜誌上。LLE試圖保留原始高維數據的局部性質，通過假設局部原始數據近似位於一張超平面上，從而使得該局部的某一個數據可以由其鄰域數據線性表示，如圖2所示：
圖2
基於上述思想，原始數據集中任意一個數據都可以看作被表示的點，這相當於將局部的線性表示一步一步轉換成了全局的非線性表示。該過程的數學描述為：
其中，xi表示原始數據集中的第i個數據，xik表示數據xi的第k個鄰域數據，wik表示xik對應的權重。當xi已知時，鄰域數據xik可以通過KNN等演算法求出。因此，可以將上式轉化成對wik的優化問題，誤差函數如下所示：
其中，wi=[wi1,wi2,...wik]T，表示xi的重建係數。為了方便求解，不妨對wi添加約束條件：
於是有：
進一步化簡得到：
其中有：
應用拉格朗日數乘法求解上述的優化問題，得到：
其中，one=[1,1,...,1]1xk.因此，對拉格朗日函數求wi的偏導數，得到：
為簡便起見，此處進一步化簡為：
由於Ai不一定可逆，所以對Ai添加一定的擾動項，如下所示：
其中，small_num表示一個極小的常數值，trace()表示矩陣求跡，eye(k,k)表示kxk的單位對角矩陣。因此解得xi的重建係數為：
最後再對求得的wi做歸一化即可。
綜上所述，雖然以上分析過程只是針對高維數據xi，但是其他數據xj(j不等於i)也可以按照此方法計算出相應的局部重建矩陣，從而最終得到整個數據集的全局重建矩陣。
02-02-低維數據的求解
在上一節中求得的wi實際為kx1的向量。因此，若原始數據集中共含有n個數據，那麼最終求得的w可以組成一個kxn的矩陣，如下所示：
由於局部線性嵌入會保留原始數據的拓撲結構，故降維得到的低維數據具有同高維數據一樣的局部線性結構，即：
其中，yi表示低維數據集中的第i個數據，yik表示yi的第k個鄰域數據，wik表示與yik對應的重建係數（即上節中求得的重建係數）。故，本節的優化函數為：
將該式化簡為：
其中，mi為nxn的權值矩陣，表示從低緯數據集y中取出用於表示yi的鄰域數據以及從mi中取出相應的權值係數，Ii表示從低維數據集y中取出第i個數據。mi實際上就是由w組成的稀疏矩陣。例如，當w1=[2,5,7,3,9]時,則m1隻在表示第2、5、7、3、9列數據的坐標上不為0，而其他位置均用0表示。進一步化簡得到：
令R=(Ii-mi)，於是有：
為了定解，對l(y)添加如下兩個約束條件：
其中Id表示d維的單位矩陣。又因為：
同理可得：
故第一個約束條件可以改為：
其中y=[y1,y2,...,yn].
對該優化函數應用拉格朗日數乘法，得到：
對y求偏導數，得：
令該偏導數為0，則有：
因此，yT實際為由矩陣R*RT特徵向量組成的矩陣。
03-實驗再現
根據LLE的演算法原理，筆者編寫並執行了LLE程序，得到的實驗結果如圖3、圖4所示。其中，圖3表示3維原始數據，圖4表示降維後的2維數據。
圖3
圖4
04-思考與總結
局部線性嵌入演算法以局部線性、全局非線性的策略對待原始高維數據，從而在保持原始數據拓撲結構的基礎上進行數據降維。該演算法充分利用了矩陣理論的相關知識，將第一、二次優化問題分別轉換成了二次型、特徵值求解問題，具有較強的啟發性和科學論證的嚴謹性。
求低維數據時添加的兩個約束條件，其一表示低維數據的協方差矩陣之和等於單位矩陣的n倍，其二表示所有低維數據的均值為0。另外，由於該協方差約束可以進行如下展開：
註：假設y1=[y11,y12]T.
因此，y中的行向量均位於半徑為sqrt(n)的n維單位球上，且兩兩正交。
05-參考文獻
[1] Roweis, S. T., & Saul, L. K. (2000). Nonlinear dimensionality reduction by locally linear embed- ding. Science, 290(5500), 2323-6.
[2] WOJCIECHCHOJNACKI, & Brooks, M. J. (2009). A note on the locally linear embedding algorith- m. International Journal of Pattern Recognition & Artificial Intelligence, 23(8), 1739-1752.
[3] Saul, L. K., & Roweis, S. T. (2001). An introduction to locally linear embedding. Journal of Machine Learning Research, 7.
[4] 吳曉婷, 閆德勤. 數據降維方法分析與研究[J]. 計算機應用研究, 2009, 26(8):2832-2835.
[5] 王靖. 流形學習的理論與方法研究[D]. 浙江大學, 2006.
[6] 馬宇. 基於高維空間的非線性降維的局部線性嵌入LLE方法[D]. 西南交通大學, 2017.
TAG:Algorithman |