局部保持投影（Locality preserving projections，LPP）

局部保持投影（Locality preserving projections，LPP）

方法概述

核心思想

• 有映射$\underset{m\ast n}{Y}=f(\underset{d\ast n}{X})$，能够实现将d维的样本变换到m维空间之中

• 假设：对于一个好的降维方法，在高维空间下距离近（相似度高）的两个点，在低维空间下依旧保持相近的关系。高维空间相似度高的两个点在低维空间相似度依旧很高

• 考虑映射$Y=W^{T}X$，即原样本空间中有$x_i$与$x_j$距离近， $y_i$ 与 $y_j$($y_i=W^T{x}_i$)仍保持相近关系

优化目标

• 定义优化目标：
  $$min\sum _i\sum _j||y_i-y_j|{|}^2{s}_{ij}$$
  即在原始空间中近的点（$s_{ij}$大），其在降维后应该尽可能接近（$y_i与y_j距离更小$）

方法推导：

• 对于LPP方法，有目标：

$$\underset{W}{argmin}\sum _i\sum _j||y_i-y_j|{|}^2{s}_{ij}$$

• 对于目标：
  $$\begin{gathered} \sum _{i=1}^n\sum _{j=1}^n||y_i-y_j|{|}^2{s}_{ij} \\ =\sum _{i=1}^n\sum _{j=1}^n(y_i^T{y}_i-y_i^T{y}_j-y_j^T{y}_i+y_j^T{y}_j)s_{ij} \\ =\sum _{i=1}^n(\sum _{j=1}^n{s}_{ij})2y_i^T{y}_i-\sum _{i=1}^n\sum _{j=1}^n{y}_i^T{y}_j{s}_{ij} \\ =2\sum _i^n{y}_i^T{y}_i{d}_{ii}-2\sum _i^n\sum _j^n{y}_i^T{y}_j{s}_{ij} \\ =2tr(YD{Y}^T)-2tr(YS{Y}^T) \\ =2tr(YL{Y}^T) \end{gathered}$$

去除乘数，最终优化目标为：
$$tr(YL{Y}^T)$$
带入$Y=W^{T}X$，得到最小化目标：
$$tr(W^{T}XL{X}^{T}W)$$

• 该目标存在平凡零解：$W=O_{m\ast d}$

  此时L取最小值0，出现维度坍缩，所有样本映射到同一个点上，此解无意义

• 当W不取零矩阵时，由于没有添加尺度约束，在降维子空间一定（组成基向量方向一致）情况下，当尺度不断变小时，目标L会同时变小，无限趋于0，不存在最小值

• 因此，考虑对最小化目标变形为：

  • $$\frac{tr(YL{Y}^T)}{tr(YD{Y}^T)}=\frac{tr(W^{T}XL{X}^{T}W)}{W^{T}XD{X}^{T}W}$$

    考虑到尺度因素，加以约束$YD{Y}^T=I$也即$W^{T}XD{X}^{T}W=I$,

    原始优化问题有多个解。由于是线性映射，若同比例缩小低维样本$y_i$，得到的数据集Y都可作为最优的低维数据集。故加入约束：$tr(YD{Y}^{\top })={\sum }_{i=1}^n{d}_{ii}{y}_i^T{y}_i=1$，通过限制$y_i$的模长，使问题有唯一解。

• 参考LDA中提到的广义瑞利商，可知：

  • $${\lambda }_{min}((XD{X}^T{)}^{-1}(XL{X}^T))\le \frac{tr(W^{T}XL{X}^{T}W)}{tr(W^{T}XD{X}^{T}W)}\le {\lambda }_{max}((XD{X}^T{)}^{-1}(XL{X}^T))$$

    变换矩阵：$W=[w_1,w_2,...,w_m]$由$(XD{X}^T{)}^{-1}(XL{X}^T)$最小m个特征向量构成

• 矩阵形式推导：

由拉格朗日乘子法，构建L：$L=tr(W^{T}XL{X}^{T}W)-tr(\Lambda (W^{T}XD{X}^{T}W-I))$

对W求偏导并令为0：
$$\begin{gathered} 2XL{X}^{T}W-2XD{X}^{T}W\Lambda =0 \\ XL{X}^{T}W=XD{X}^{T}W\Lambda \\ 有：(XD{X}^T{)}^{-1}XL{X}^{T}W=W\Lambda \end{gathered}$$

W由$(XD{X}^T{)}^{-1}XL{X}^T$的特征向量作为列向量构成，且为了最小化目标函数，选取的特征向量应该是最小m个特征值对应的特征向量

相关定义

• 权重矩阵S：

  • 定义样本$x_i$和$x_j$之间的权重$w_{ij}$, 原则是样本点之间距离越小，权重越大

  • 权重矩阵S常用定义方式：
    $$S_{ij}=\{\begin{array}{c}{s}_{ij}=exp(-\frac{||x_i-x_j|{|}^2}{t})x_i\in N_k(x_j)即x_i是x_j的k近邻\\ s_{ij}=0else\end{array}$$

• 度矩阵D：

  • 度矩阵D是一个对角阵，其对角元素$D_{ii}={\sum }_{j=1}^n{s}_{ij}$

  • $$D=\{\begin{array}{c}{\sum }_{j=1}^n{s}_{1j}0...0\\ 0{\sum }_{j=1}^n{s}_{2j}...0\\ ............\\ 00...{\sum }_{j=1}^n{s}_{nj}\end{array}\}$$

• 拉普拉斯矩阵L：L=D-S

有运算：
$$\begin{gathered} YD{Y}^T=[y_1,y_2,...,y_n][\begin{array}{c}{d}_{11}0...0\\ 0d_{22}...0\\ ............\\ 00...d_{nn}\end{array}][\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_n^T\end{array}] \\ =[d_{11}{y}_1,d_{22}{y}_2,...,d_{nn}{y}_n][\begin{array}{c}{y}_1^T\\ y_2^T\\ ...\\ y_n^T\end{array}] \\ =d_{11}{y}_1{y}_1^T+d_{22}{y}_2{y}_2^T+...+d_{nn}{y}_n{y}_n^T=\sum _{i=1}^n{y}_i{d}_{ii}{y}_i^T=\sum _{i=1}^n{d}_{ii}{y}_i{y}_i^T \end{gathered}$$
因此有：
$$tr(YD{Y}^T)=\sum _{i=1}^n{d}_{ii}{y}_i^T{y}_i$$
类似可得：
$$tr(YS{Y}^T)=\sum _{i=1}^n\sum _{j=1}^n{s}_{ij}{y}_i^T{y}_j$$

方法流程
1）由样本矩阵X构建权重矩阵S，度矩阵D，拉普拉斯矩阵L

2）求$(XD{X}^T{)}^{-1}XL{X}^T$的特征向量，取最小m个作列向量构成变换矩阵W

3）由$Y=W^{T}X$完成降维