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

方法概述

核心思想

• 有映射$\underset{m?n}{Y}=f(\underset{d?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?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}^{?})={\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$完成降維