拉普拉斯矩阵/特征映射

https://www.jianshu.com/p/87057397a070
https://blog.csdn.net/v_july_v/article/details/40738211
https://blog.csdn.net/yujianmin1990/article/details/48420483
https://www.cnblogs.com/xbinworld/archive/2012/11/29/2795287.html
http://web.cse.ohio-state.edu/~belkin.8/papers/LEM_NIPS_01.pdf

1.拉普拉斯矩阵(Laplacian Matrix)

• 表示图的一种矩阵，给定n个顶点的图G=(V,E)$G=(V,E)$，分别表示graph、vertex、edge
• Laplacian Matrix定义为，D为度矩阵，W为邻接矩阵
  
  L=D−W$$L=D-W$$
  
  例子：
  
  则邻接矩阵W为
  
  W=⎡⎣⎢⎢⎢⎢⎢⎢⎢010010101010010100001011110100000100⎤⎦⎥⎥⎥⎥⎥⎥⎥$$W=\left[\begin{array}{cccccc}0& 1& 0& 0& 1& 0\\ 1& 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 0& 0\\ 0& 0& 1& 0& 1& 1\\ 1& 1& 0& 1& 0& 0\\ 0& 0& 0& 1& 0& 0\end{array}\right]$$
  
  度矩阵D为
  
  D=⎡⎣⎢⎢⎢⎢⎢⎢⎢200000030000002000000300000030000001⎤⎦⎥⎥⎥⎥⎥⎥⎥$$D=\left[\begin{array}{cccccc}2& 0& 0& 0& 0& 0\\ 0& 3& 0& 0& 0& 0\\ 0& 0& 2& 0& 0& 0\\ 0& 0& 0& 3& 0& 0\\ 0& 0& 0& 0& 3& 0\\ 0& 0& 0& 0& 0& 1\end{array}\right]$$
  
  则拉普拉斯矩阵为
  
  L=D−W=⎡⎣⎢⎢⎢⎢⎢⎢⎢2−100−10−13−10−100−12−10000−13−1−1−1−10−130000−101⎤⎦⎥⎥⎥⎥⎥⎥⎥$$L=D-W=\left[\begin{array}{cccccc}2& -1& 0& 0& -1& 0\\ -1& 3& -1& 0& -1& 0\\ 0& -1& 2& -1& 0& 0\\ 0& 0& -1& 3& -1& -1\\ -1& -1& 0& -1& 3& 0\\ 0& 0& 0& -1& 0& 1\end{array}\right]$$

拉普拉斯矩阵的性质

• L是对称半正定矩阵
• L1=01$L1=01$，即最小特征值是0，L∗1=(D−W)∗1=0=0∗1$L\ast 1=(D-W)\ast 1=0=0\ast 1$
• L有n个非负的实特征值
• 对任意实向量f∈ℝn$f\in {\mathbb{R}}^n$，成立
  

  fTLf=12∑i,j=1Nwij(fi−fj)2$$f^{T}Lf=\frac{1}{2}\sum _{i,j=1}^N{w}_{ij}(f_i-f_j{)}^2$$

  
  

2.拉普拉斯特征映射步骤

拉普拉斯特征映射将处于流形上的数据，在尽量保留原数据间相似度的情况下，映射到低维下表示。 流程：

2.1 构造邻近图(用邻近图近似流形)

• 距离阈值，‖xi−xj‖2≤ϵ$\Vert x_i-x_j{\Vert }^2\le ϵ$
• K近邻

2.2 计算边权重(样本间相似度)

• 热核
  
  wij=⎧⎩⎨⎪⎪exp(−‖xi−xj‖2t)0节点i与j相连不相连$$w_{ij}=\{\begin{array}{rlrl}& exp(-\frac{\Vert x_i-x_j{\Vert }^2}{t})& & 节点i与j相连\\ & 0& & 不相连\end{array}$$
• 简单形式
  
  wij={10节点i与j相连不相连$$w_{ij}=\{\begin{array}{rlr}1& & 节点i与j相连\\ 0& & 不相连\end{array}$$

2.3 特征映射

1. 求解Lf=λDf$Lf=\lambda Df$;——广义特征值问题
2. 得到特征值和特征向量
   
   {Lf0=λ0Df0;Lf1=λ1Df1;...Lfm=λmDfm...0=λ0≤λ1≤...≤λ...$$\{\begin{array}{rl}& L{f}_0={\lambda }_{0}D{f}_0;L{f}_1={\lambda }_{1}D{f}_1;...L{f}_m={\lambda }_{m}D{f}_m...\\ & 0={\lambda }_0\le {\lambda }_1\le ...\le {\lambda }_{.}..\end{array}$$
3. 取最小的m个非零特征值的特征向量作为降维结果，即

3.推导

希望相互间有关系的点（在图中相连的点）在降维后的空间中尽可能的靠近。Laplacian Eigenmaps可以反映出数据内在的流形结构。
假设样本n个，目标维度m，则目标矩阵为Yn×m$Y^{n\times m}$，每个行向量yTi$y_i^T$表示xi$x_i$在目标空间中的向量那个表示，拉普拉斯特征映射要最小化目标函数

令对角阵D为W中每行之和，经过线性变化([3]中有推导)转化为优化

使得公式最小化的Y的列向量是以下广义特征值问题的m个最小非0特征值对应的特征向量