本篇内容主要来源于白板书推导

背景介绍

过拟合
- 增加Data
- 正则化
- 降维
  - 直接降维：特征选择
  - 线性降维：PCA、MDS
  - 非线性降维：流形LSOMAP、LLE
维度灾难
- 集合角度
- 数据稀疏，且分布不均

预备知识

基础知识

数据：

$x=\left(x_{1} \cdots x_{n}\right)_{n x p}^{T}=\left(\begin{array}{c} {x_{1}^{T}} \\ {x_{2}^{T}} \\ {\vdots} \\ {x_{n}^{T}} \end{array}\right)=\left(\begin{array}{ccc} {x_{11}} & {x_{12}} & {\cdots} & x_{1 p} \\ {x_{21}} & {x_{22}} & {\cdots} & x_{2 p} \\ {\vdots} & {\vdots} & {\vdots} & {\vdots}\\ {x_{n\times1}} & {x_{n \times 2}} & {\cdots} & x_{n\times p} \end{array}\right)$
期望：

$\bar{x}=\frac{1}{2} \sum_{i=1}^{N} x_{i}$
方差：

$S_{p \times p}=\frac{1}{N} \sum_{i=1}^{N}\left(x_{i}-\bar{x}\right) \cdot\left(x_{i}-\bar{x}\right)^{T}$

推导技巧

技巧：

$\bar{x}=\frac{1}{N} \sum_{i=1}^{N} x_{i}=\frac{1}{N}(x_1,x_2,\dots,x_n)\cdot \left(\begin{array}{l} {1} \\ {1} \\ {\vdots} \\ 1\\ \end{array}\right) = \frac{1}{N}x^T\cdot 1^n$

$\begin{aligned} (x_1 - \bar{x},x_2- \bar{x},\dots,x_n- \bar{x}) & =(x_1,x_2,\dots,x_n)-\bar{x}\cdot (1,1,\dots,1)\\ & =x^T-\frac{1}{N}x^T\cdot 1_N \cdot (1_{N})^T \\& =x^T(I_n- \frac{1}{N}\cdot 1_N \cdot (1_N)^T)\\&=x^T\cdot H_N \\ & = H\cdot x \end{aligned}$

$H$ 的性质：
- 易证： $H^T = H$
- $H^2 = H \cdot H = H$
  
  证明：
  
  $\begin{aligned} H^2 & = (I_n-\frac{1}{N}1^n\cdot (1^n)^T)\cdot (I_n-\frac{1}{N}1^n\cdot (1^n)^T)^T \\ &= I_n + \frac{1}{N^2}1_N1_N^T1_N1_N^T - \frac{2}{N}1_N1_N^T \\ &= I_n - \frac{1}{N}1_N1_N^T = H \end{aligned}$
  
  推广有：
  
  $H^N = H$

⭕️根据上面的技巧改写期望和方差公式:

$\begin{aligned} \bar{x} &= \frac{1}{N}x^T\cdot 1^n \\ S_{p \times p} &= \frac{1}{N}x^TH\cdot(x^T H)^T=\frac{1}{N}x^THx \end{aligned}$

主成分分析原理（PCA）

Principal Component Analysis

一个中心
- 原始特征空间的重构
两个基本点
- 最大投影方差角度
- 最小重构距离【还原后的数据与原数据的差距最小】

最大投影方差角度

0. 预备知识 - 向量投影

向量投影：

**坐标值：**与单位投影向量点积

$Projection = |a|\cdot cos\theta$

若此时 $\bar{b}$ 为单位向量，则 $Projection = a \cdot b =|a||b|cos\theta$
**坐标系：**投影向量

1. 算法原理

将 $x$ 向量往最大投影向量 $\bar{u_k}$ 处投影：

$(x_i^T \cdot u_k )u_k$

令投影后向量的方差最大
- 投影后的向量为： $(x_i^T \cdot u_k )u_k$
- 投影后的向量的方差：
$\begin{aligned} J &= \frac{1}{N}\cdot \sum_{i=1}^N((x_i-\bar{x}) \cdot u_k )^2 \\ &= \frac{1}{N}\cdot \sum_{i=1}^N ((x_i-\bar{x}) \cdot u_k )^T\cdot ((x_i-\bar{x}) \cdot u_k ) \\ & = \sum_{i=1}^N \frac{1}{N} u_k^T(x_i - \bar{x})(x_i - \bar{x})^T u_k \\ & = u_k^T [\sum_{i=1}^N \frac{1}{N}(x_i - \bar{x})(x_i - \bar{x})^T] u_k \\ & = u_k^T S_{p \times p} u_k \end{aligned}$

条件： $|u_k|=1$ ，也即 $u_k^T\cdot u_k =1$
拉格朗日函数法，求上面的极大值：

$L(u_k,\lambda)= u_k^T S_{p \times p} u_k + \lambda \cdot (1 - u_k^T\cdot u_k)$

求导后等于0：

$\frac{\partial L}{\partial u_k} = 2 \cdot S_{p \times p }\cdot u_k - \lambda \cdot 2 \cdot u_1 =0$

可得：

$S\cdot u_k = \lambda \cdot u_k$

综上可得，投影向量为方差矩阵 $S_{p\times p}$ 的特征向量。

2. 算法流程

**步骤1：**数据中心化，即 $H \cdot X$ ,根据需要归一化 – Normalized
去中心化后的目的，让 $u_k$ 的原点正好穿过特征的中心。
**步骤2：**计算协方差矩阵
步骤3：利用特征值分解可以得到特征向量。
步骤4：根据特征向量构造投影矩阵
**步骤5：**根据投影矩阵，降维数据。

最小重构原理

降维的思路：
- 先利用方差矩阵 $S_{p \times p }$ 可以找到一组独立的基向量 $\{u_1,u_2,\dots,u_p\}$ 对应的特征值为 $\{\lambda_1,\lambda_2,\dots,\lambda_p\}$
- 压缩降维，选择前 $q$ 个最大值的 $\lambda$
根据投影方向向量 $u_k$ 来重构原先的坐标 $x_k$

$x_i = \sum_{k=1}^P (x_i^T \cdot u_k)\cdot u_k$

$\hat{x}= \sum_{k=1}^q (x_i^T \cdot u_k)\cdot u_k$
最小重构代价：

$J = \sum_{i=1}^N \frac{1}{N} \|x_i - \hat{x_i}\|^2 = \sum_{k=q+1}^p u_k^TS u_k$

同理要求： $u_k^T\cdot u_k = 1$

总结

最大投影方差等价于 最小重构原理

目的：从 $u_k$ 轴重构回去的损失最小

PCA 实践：

基础：SVD 奇异值分解

公式：
$\begin{aligned} W &= U\Sigma V^T \\ &= \sqrt(\lambda_1)\vec{u_1}(\vec{v_1})^T + \sqrt(\lambda_2)\vec{u_2}(\vec{v_2})^T \end{aligned}$

上述公式只有两个特征值，说明原向量的维度是2，方差矩阵是 $S_{2\times 2}$ ,降维的话，直接舍弃其中的一个部分即可。现在的问题就是如何求以上的几个值？

如何求解： $\lambda$ 、 $u_k$ 、 $v_k$ ？
- 首先，我们可以对任何的矩阵（并非一定要方阵）进行奇异值分解，若想要将矩阵对角化求取特征值，必须要求方阵，而$W \cdot W^T $以及$ W^T\cdot W$一定是方阵。
- $W\cdot W^T$
  
  $\begin{aligned} W\cdot W^T &= (U\Sigma V^T)(U\Sigma V^T)^T \\ &= U (\Sigma^T\Sigma)U^T \\ &= U \cdot D \cdot U^T \\ \end{aligned}$
- $W^T \cdot W$
  
  $\begin{aligned} W^T \cdot W &= (U\Sigma V^T)^T(U\Sigma V^T) \\ &= V (\Sigma^T\Sigma)V^T \\ &= V \cdot D \cdot V^T \\ \end{aligned}$
- 只要分别将原矩阵与自己的转置相乘，就可以得到对应的 特征值 和 特征向量

三种角度看PCA降维问题：

空间重构原理：

找到方差矩阵，进行特征值分解，对应的特征值向量，即为主方向【即可】

$S_{p \times p} = G \cdot K \cdot G^T \\ s.t. G^TG = 1$

其中 $K$ 值为：

$\begin{array}{c} K\ =\ \left[ \begin{matrix} k_1& & & \\ & k_2& & \\ & & \ddots& \\ & & & k_p\\ \end{matrix} \right]\\ k_1\ge k_2\ge k_3\ge \cdots \ge k_p\\ \end{array}$

如何还原？
- 选择前 $q$ 个最大的K值，所对应的特征向量 $u_k$ 即可。
- 有了最大的投影向量，我们直接往最大方向投影就ok了！
  
  无损失：
  
  $x_i = \sum_{k=1}^P (x_i^T \cdot u_k)\cdot u_k$
  
  少选几个特征：
  
  $\hat{x}= \sum_{k=1}^q (x_i^T \cdot u_k)\cdot u_k$

通过对中心化后的数据，求SVD奇异值分解，奇异值的平方即为特征值

这里直接对中心化后的数据进行SVD分解

原理：

$\begin{aligned} H X&= U\Sigma V^T \\ &= \sqrt(\lambda_1)\vec{u_1}(\vec{v_1})^T + \sqrt(\lambda_2)\vec{u_2}(\vec{v_2})^T + \cdots \end{aligned}$

如何计算
- $HX(HX)^T$ 进行特征对角化处理，可以求得： $\lambda$ 、 $\vec{u}$
- $(HX)^THX$ 进行特征对角化处理，可以求得： $\lambda$ 、 $\vec{v}$
如何还原？

取前k项即可，取得越多越近似！

主坐标分析法（PCoA）

$Principle\ coordinate\ analysis$

背景说明:
若此时$S_{p \times p} $中维度P远远大于样本的个数 $N$ 时，【如图片处理，维度都是几万维】求解 $S_{p \times p}$ 还是比较困难的。有没有解决简单的方法可以跳过对方差的计算？当然有！

前两个方法的缺点：
- 当$S_{p \times p} $的维度太大的时候，计算效率太低
注：SVD分解中，其实也蕴含着对方差的计算，如：对 $x^TH^THx$ 进行特征分解。

$S_{p \times p} = \frac{1}{N}x^TH\cdot(x^T H)^T=\frac{1}{N}x^TH^THx$
PCA中的结果：

第一步：我们在PCA中的目的，就是为了找到一组能使方差最大化的特征向量。

第二步：将中心化后的特征 $HX$ 直接投到这组新的坐标下，即与特征向量 $v$ 进行点积，在新坐标系 $v_k$ 下的坐标值 $U \Sigma$ 。公式如下：

$HX\cdot V = U \Sigma V^TV=U\Sigma$

然后，，坐标值为 $U\Sigma$ 。
若直接对 $HX(HX)^T$ 进行特征对角化处理，可以求得： $\Sigma$ 和 $U$

将两者相乘，就直接得到了我们在新坐标系下的坐标。

PCA代码实践

实例01：

$A\ =\ \left[ \begin{matrix} 3& 2000\\ 2& 3000\\ 4& 5000\\ 5& 8000\\ 1& 2000\\ \end{matrix} \right]$

Python基础实现：

数据预处理，【数据归一化，数据缩放】

中心化公式： $H\cdot X$

# 数据归一化
mean = np.mean(A, axis=0)
norm = A - mean
# 数据缩放
scope = np.max(norm, axis=0) - np.min(norm, axis=0)
norm = norm / scope

奇异值分解：

$\begin{aligned} H\cdot X &= U\Sigma V^T \\ &= \sqrt(\lambda_1)\vec{u_1}(\vec{v_1})^T + \sqrt(\lambda_2)\vec{u_2}(\vec{v_2})^T \end{aligned}$
U, S, V = np.linalg.svd(np.dot(norm.T, norm))
U

array([[-0.67710949, -0.73588229],
[-0.73588229, 0.67710949]])

选取特征矩阵的第一个列来构造

$\hat{R} = \sqrt(\lambda_1)\vec{u_1}(\vec{v_1})^T$

U_reduce = U[:, 0].reshape(2,1)
R = np.dot(norm, U_reduce)
R

array([[ 0.2452941 ],
       [ 0.29192442],
       [-0.29192442],
       [-0.82914294],
       [ 0.58384884]])

还原：

投影公式：

$Z = HX\cdot V$

说明：V是一个正交矩阵，有： $V \cdot V^T = V \cdot V^{-1}=E$

还原公式：

$H\cdot X = Z \cdot V^{-1} = Z \cdot V^T$
Z = np.dot(R, U_reduce.T)
Z

array([[-0.16609096, -0.18050758],
[-0.19766479, -0.21482201],
[ 0.19766479, 0.21482201],
[ 0.56142055, 0.6101516 ],
[-0.39532959, -0.42964402]])

反中心化和反数据放缩

# 反数据放缩 + 反中心化
np.multiply(Z, scope) + mean

sklearn调包：`PCA`

调包实践

from sklearn.decomposition import PCA
from sklearn.pipeline import Pipeline
from sklearn.preprocessing import MinMaxScaler

def std_PCA(**argv):
    scaler = MinMaxScaler()
    pca = PCA(**argv)
    pipeline = Pipeline([('scaler', scaler),
                         ('pca', pca)])
    return pipeline

pca = std_PCA(n_components=1)
R2 = pca.fit_transform(A)
R2

array([[-0.2452941 ],
       [-0.29192442],
       [ 0.29192442],
       [ 0.82914294],
       [-0.58384884]])

反放缩和反归一化，之前是np.multiply(Z, scope) + mean
# 调包反数据预处理
pca.inverse_transform(R2)