pca.md

主成分分析 - PCA (Principal Component Analysis)

PCA是一种数据线性降维的方法，在学习PCA之前，先回顾一些基础知识。 内容部分参考Mathematics for Machine Learning: Multivariate Calculus。

• 主成分分析 - PCA (Principal Component Analysis)
  • 方差和协方差 Varianes & Covariances
    • 方差 Variance
    • Covariance 协方差
    • Rules 方差规则
  • 积 Product
    • 点积 Dot product
      • 代数定义 Algebraic definition
      • 几何定义 Geometric definition
    • 内积 Inner product
      • 内积性质 Inner product properties
      • 函数内积 Inner product of functions
      • 随机变量内积 Inner product of random variables
  • 投影 Projection
    • 投影到一维空间 Projection onto 1D subspaces
    • 投影到高维空间 Projections onto higher-dimentional subspaces
  • PCA
    • PCA推导
    • PCA算法
      • PCA步骤
      • 高维空间PCA High-dimentional PCA
  • 推荐阅读

方差和协方差 Varianes & Covariances

方差 Variance

方差：

标准差：

协方差 Covariance

对于2D数据，协方差矩阵如下：

Rules 方差规则

• Var[D] = Var[D + a]
• Var[α D] = α² Var[D]

对于矩阵 D = x₁, x₂, ..., x_n, x ∈ R^p

• Var[AD + b] = A Var[D] A^T

积 Product

点积 Dot product

代数定义 Algebraic definition

x^Ty = Σ^D_d=1 x_d y_d, x, y ∈ R^D

几何定义 Geometric definition

x^Ty=||x|| · ||y||cos(θ)

内积 Inner product

定义：对于 x, y ∈ V ，内积 〈x, y〉的定义为 x, y 到实数 R 的映射: V×V->R ，内积具有如下性质：

• Bilinear
  • 〈λx + z, y〉= λ〈x, y〉+〈z, y〉
  • 〈x, λy + z〉= λ〈x, y〉+〈x, z〉
• Positivedefinite
  • 〈x, x〉 ≥ 0,〈x, x〉= 0 ⇔ x = 0
• Symmetric
  • 〈x, y〉=〈y, x〉

如果定义 〈x,y〉= x^T A y ，当 A = I ，则其和x，y的点积一致，否则不同。

内积性质 Inner product properties

• ||λ x|| = |λ| · ||x||
• ||x + y|| ≤ ||x|| + ||y||
• ||〈x,y〉|| ≤ ||x|| · ||y||

计算角度

函数内积 Inner product of functions

例子：

其中， u(x) = sin(x), v(x) = cos(x), f(x) = sin(x)cos(x)

随机变量内积 Inner product of random variables

例子； 〈x,y〉=cov[x,y]

其中

投影 Projection

投影到一维空间 Projection onto 1D subspaces

投影后的向量 $\pi_u(x)$ 具有如下两点属性:

1. 存在 λ ∈ R: π_u(x) = λb。(π_u(x) ∈ U )
2. 〈b,pi_u(x)-x〉= 0。 (正交)

得到

推导如下：

投影到高维空间 Projections onto higher-dimentional subspaces

投影后的向量 $\pi_u(x)$ 具有如下两点属性:

1. 
2. 〈π_u(x) - x, b_i〉= 0, i=1, ..., M (正交)

其中

推导如下：

PCA

PCA推导

问题描述： 对于点集合 X = x₁, ..., x_N, x_i ∈ R^D ，定义是低维空间坐标系 B = (b₁, ..., b_M) 。 其中 M < D ， b_i 是正交基， β_i 是正交基系数。 希望找到一个映射集合 。 有如下 公式(A)：

假设使用的是点积， β_{D(D ≠ i)} 和 b_i 正交，那么得到公式(B)：

z_n = B^TX ∈ R^M 是 X 在低维空间 B 上的投影的坐标值，称为coordinates或code。可得

对于PCA问题，其优化目标为：样本点到新的超平面上的距离足够近，等于最小化下面的成本函数，公式(C)：

因此可得 公式(D)：

公式(E)：

由(D), (E)可得

由(A), (B)可得

公式(F)：

由(C), (F)可得

公式(G)：

上式等于将数据的协方差矩阵 S 投影到子空间 R^D-M 中，因此 min(J) 等于投影到该子空间后的数据的方差最小化。

由(G)构造拉格朗日函数，其中 ，得到公式(H)：

由(G), (H)可得

所以在忽略的子空间里要选那些比较小的特征值，在主子空间选那些大的特征值。

这与协方差矩阵的属性一致。由于对称性，协方差矩阵的特征向量彼此正交，并且属于具有最大方差的数据方向上的最大特征值点的特征向量和该方向上的方差由相应的特征值给出。

PCA算法

PCA步骤

1. 数据预归一化 (normalization)
   1. 每列数据减该列平均值(mean), to avoid numerial problems
   2. 每列数据除该列标准差(std)，使数据无单位（unit-free）且方差为1

2. 计算数据协方差矩阵（covariance matrix）和该矩阵对应的特征值、特征向量（eigenvalues, eigenvectors）
   • 
   • B 是由特征向量作为列的矩阵，其中特征向量对应的是最大的特征值

高维空间PCA High-dimentional PCA

对于 矩阵

如果 N << D ， 那么 X 的协方差矩阵 S 的秩为 N。那么 S 有 D-N+1 个特征值为0，其非满秩矩阵。

下面考虑如何把 S 转换为满秩矩阵 E：

其中 c_i=Xb_i ，在变换后，E 为满秩矩阵，由PCA的计算方法可以得到 E 对应的特征向量 c_i ，但这里需要计算 S 对应的特征向量。再次变换上式：

所以 S 的特征向量为 X^Tc_i 。

推荐阅读

1. PCA chapter of "Mathematics for Machine Learning"