降维PCA 主成分分析 Principal Components

2018-09-27  本文已影响0人  波洛的汽车电子世界

一些基本概念：

  1. 生成模型generative model：生成模型是指联合分布；判别模型是指条件分布。
  2. WLOG: Without loss of generality 不失一般性
  3. signal reconstruction: 信号重构
  4. 数据噪声：引入噪声通常是为了防止过拟合的，噪声一般能提高模型的泛化能力
  5. 过拟合：当训练时候的数据不够，即训练数据不足以估计整个数据的分布时，或者最模型进行过度训练时，会导致过拟合。
  6. 维度：维度通常指特征的个数。它比较少的情况下也可以指数据向量的第几维。我有段时间一直将维度的概念搞错了！

下面是PCA的内容：

  1. 什么是降维？
    根据维基百科的定义，在机器学习中，降维是指减少随机变量的个数的过程。主要包括两方面：特征选择(features selection)和特征提取(features extraction or features projection)。换句话说，降维是指减少特征空间的维数。
    为什么降维？
    1.为了减少数据噪声，突出主要特征，减少计算量，如PCA。
    2.为了减少模型的参数。
    3.为了避免过拟合。
    怎么降维？ 一般的想法是在低维保持数据的主要特征。

PCA是一个使数据不相关的过程。它的目标是，找到一个坐标系统，使不同的维度不相关。或者，找到一个坐标系统，找出最大的方差。

  1. 怎样实现PCA：相关性可以通过旋转数据点或坐标来消除。

我们有数据X = [x_1,x_2,\ldots,x_N] \in R^{D \times N}，PCA找到一个方向w^* \in R^{D}使w^* = argmax_w w^TXX^Tw。优化这个式子我们必须对w 有限制条件：||w||^2 =w^Tw = 1。
拉格朗日方程有：
L = w^TXX^Tw +\lambda (1-w^Tw)
对w求偏微分等于0有：
\frac{\partial{L}}{\partial w} = 2XX^Tw - 2\lambda w = 0
XX^T = \lambda w
这是一个标准的特征方程问题。w是XX^T对应最大特征根的的特征向量。
W = [w_1,\ldots,w_D]是由数据方差矩阵做特征根分解得到的：
XX^TW = W\Lambda主成分W是特征向量，\Lambda是对应的对角线上的特征根。

PCA的特征：
a. 特征向量是正交的： W^TW = WW^T = I。也就是说，PCA对应着生成模型x(t) =As(t)，这儿A = W, s(t) =W^Tx(t)。
b. W^TXX^TW = \Lambda是对角阵。也就是说，分解出来的s(t)在时间上是无关的。
c. 第i个特征根是第i个因子的方差: \Lambda_{ii} = Var(s_i) = Var(w_i^T x)

具体算法：

|-------------------------------------------------------------------------------------------|
Require : data x_1,\ldots, x_N \in R^d, number of principal components k
1: #Center data: X= X - 1/N \sum_iX_i
2: #Compute Covariance Matrix :C = 1/N XX^T
3: #Calculate eigenvectors and eigenvalues
of the covariance matrix: W, \Lambda = eig(C)
4: # Rank eigenvectors by its corresponding
eigenvalues
5: return top k eigenvectorsW

|-------------------------------------------------------------------------------------------|

  1. 什么是信号重构？
    PCA所做的是将数据投影到输入空间的子集上。例如，这张图里，投影数据在子空间里面有最大的方差。图中的红点是在投影上重构的数据。重构误差是从蓝点到红点的距离之和。
图片来自网络

信号重构的最优性
WLOG(不失一般性)， 假设特征向量对应的特征根有序排列，即
\Lambda_{11} \geq \Lambda_{22}\geq\ldots\Lambda_{DD}
那么，前k个成分方向的投影，即
[s_1,\ldots,s_k] = [w_1,\ldots,w_k]^TX
里面有\sum_{i=1}^k \Lambda{ii}/\sum_{i=1}^D \Lambda_{ii}的方差。

定理：在k维投影上的重构误差最小值是XX^T的余下的D - k个最小的特征根之和:
min_{v = [v_1,\ldots,v_k],V^TVX =I_k}||X - VV^TX||^2 = \sum_{i = k+1}^D \Lambda_{ii}
最小值在V =[w_1,\ldots,w_k]处取得。
证明：
化简||X - VV^TX||^2 = Tr(XX^T) - Tr(V^TXX^TV)
而max_{v = [v_1,\ldots,v_k],V^TVX =I_k}Tr(V^TXX^TV) = \sum_{i =1}^k \Lambda_{ii}

  1. Kernel Trick
    我们有数据X = [x_1,x_2,\ldots,x_N] \in R^{D \times N}, N\ll D，会遇到这样的问题：
    a. 协方差矩阵XX^T的矩阵的维数会很大
    b. 对于协方差矩阵的估计拥有的数据太少

我们知道w肯定在数据的延伸上，w = X\alpha, \alpha是每个点的权重。
将w = X\alpha代入PCA的式子里，得到
X\underbrace{X^TX}_{\text{ kernel K_X}}\alpha = \lambda X \alpha
则有：
K_X\alpha =\lambda \alpha
这种通过X^TX而不是XX^T解PCA的方法称作linear kernel PCA。

  1. Singular Value Decomposition(SVD)奇异值分解
    通过SVD我们可以分解任意一个矩阵X = ESF，这儿E和F是包含着奇异向量的正交矩阵， S是对角阵，为奇异值。

现在我们可以看到
a.协方差矩阵XX^T =ESF(ESF)^T = ESFF^TS^TE^T = ES^2E^T
b.核矩阵 X^TX= FSE(FSE)^T = FSEE^TS^TF^T = FS^2F^T
E是XX^T的特征向量，F是X^TX的特征向量。
S是XX^T和X^TX的特征值的平方根。
线性核PCA和经典PCA之间的关系是：ES =XF^T

上一篇下一篇

猜你喜欢

热点阅读