LLE降维

LLE 是 Locally Linear embedding

直观是在样本点的高维空间相邻近的话，可以用低维的子空间描述。

基本原理分三步：
（1） 找到邻居 neighbors .(可以使用多种方法，邻居K的数目选择影响很大)
（2）使用周围的邻居作为基向量， reconstruct with linear weights
minimize reconstruction error.

$\underset{W}{\min }\epsilon (W)={\sum }_i||x_i-{\sum }_{j\in N_i}{W}_{ij}{x}_j|{|}_2^2$,

${\sum }_i||x_i-{\sum }_{j\in N_i}{W}_{ij}{x}_j|{|}_2^2={\sum }_j||W_{ij}(x_i-x_j)|{|}_2^2={\sum }_{jk}{W}_{ij}{W}_{ik}{G}_{jk}=W_i^{T}G{W}_i$,

$G_{jk}=(x_i-x_j{)}^T(x_i-x_k),\forall j,k\in N_i$
使用拉格朗日方法：

$2G{W}_i-\lambda I=0,{\sum }_j{W}_{ij}=1$

$W_i=\frac{G^{-1}I}{I^T{G}^{-1}I}$

$s.t.{\sum }_j{W}_{ij}=1,{\forall }_i$

为了防止G病态多个解，加入二范数
$mi{n}_{W_i}{W}_i^{T}G{W}_i+\gamma W_i^T{W}_i$
得到
$2(G+\gamma I)W_i-\lambda I=0$

$W_i=\frac{(G+\gamma I{)}^{-1}I}{I^T(G+\gamma I{)}^{-1}I}$

(3) Map to embedding coordinates
$\underset{Y}{\min }\varphi (Y)={\sum }_i||y_i-{\sum }_{j\in N_i}{W}_{ij}{y}_i|{|}_2^2$

对y要做约束，不然有很多解，比如平移。

$s.t.{\sum }_i{y}_i=0,\frac{1}{N}{\sum }_i{y}_i{y}_i^T=I$

解决方法拉格朗日方法 ， eigenvalue problem
$F=\frac{1}{2}{\sum }_i||y_i-{\sum }_j{W}_{ij}{y}_j|{|}_2^2-\frac{1}{2}{\sum }_{\alpha \beta }{\lambda }_{\alpha \beta }(\frac{1}{N}{\sum }_i{y}_i\alpha y_i\beta -\delta \alpha \beta )$

$(1-W{)}^T(1-W)Y=\frac{1}{N}Y\Lambda ,where{\Lambda }_{\alpha \beta }={\lambda }_{\alpha \beta }$

最后

以上就是欢喜悟空最近收集整理的关于LLE降维的全部内容，更多相关LLE降维内容请搜索靠谱客的其他文章。