您的位置: 首页  >  文章  >  轻松解剖数据降维——PCA

轻松解剖数据降维——PCA

分类: 文章 • 2024-01-20 16:28:58

目录

为什么要进行数据降维？

我们知道数据降维是减少过拟合的重要方法之一，且对于高维度的数据，不仅计算量庞大的吓人，而且容易带来维度灾难。

下面我们从几何角度看看什么是维度灾难，会带来哪些影响？
下图是一个同圆心构成的圆环，大圆半径为R = 1，圆环间隙ξ\xi足够小，即趋于0，小圆半径为r = R - ξ\xi = 1 - ξ\xi。
在二维平面上大圆和小圆的面积几乎相等，圆环的面积趋于0.
V小圆V大圆=lim⁡ξ→0,k=2π(1−ξ)2π12=1(1) \frac{ V小圆 }{ V大圆 } = \lim\limits_{\xi \rightarrow 0 ,k = 2} \frac{\pi (1-\xi)^2}{\pi 1^2} = 1 \tag{1}
如果将下图映射到一个k维空间时，假设k很大，区域 + ∞\infty 。
那么可得：
V小圆V大圆=lim⁡ξ→0,k→+∞π(1−ξ)kπ1k=01=0(2) \frac{ V小圆 }{ V大圆 } = \lim\limits_{\xi \rightarrow 0,k \rightarrow +\infty} \frac{\pi (1-\xi)^k}{\pi 1^k} = \frac{ 0 }{ 1 } = 0 \tag{2}
V圆环V大圆=lim⁡ξ→0,k→+∞π12−π(1−ξ)kπ1k=1−01=1(3) \frac{ V圆环 }{ V大圆 } = \lim\limits_{\xi \rightarrow 0,k \rightarrow +\infty} \frac{\pi 1^2 -\pi (1-\xi)^k}{\pi 1^k} = \frac{ 1-0 }{ 1 } = 1 \tag{3}
轻松解剖数据降维——PCA
总结：低维数据映射到高维数据，会使得数据变得更加稀疏，分布不均匀，且几乎只有原先边缘部分的数据是分散在高维空间内。这样带来的不好现象就被称为维度灾难。

中心矩阵是什么？

先不急说中心矩阵是什么？有什么作用？有什么性质？我们可以利用均值和协方差矩阵来引出它。
假设有N个样本数据，每个数据是P维特征，用矩阵X来表示这些数据。
向量 xi 没有说明，默认都是列向量。
Xnp=[x1,x2...,xn]T=[x1Tx2T...xnT]=[x11x12...x1px21x22...x2p......xn1xn2...xnp]np(4) X_{np} = \left[ \begin{matrix} x_1, x_2...,x_n \end{matrix} \right]^T = \left[ \begin{matrix} x_1^T \\ x_2^T \\ ... \\ x_n^T \end{matrix} \right] = \left[ \begin{matrix} x_{11} & x_{12} & ... & x_{1p} \\ x_{21} & x_{22} & ... & x_{2p} \\ ...... \\ x_{n1} & x_{n2} & ... & x_{np} \end{matrix} \right]_{np} \tag{4}

  • 样本均值

实际上是求所有样本在不同特征下的均值，故最后结果为 p维的列向量.
设1n = [11...1]n×1\left[ \begin{matrix} 1 \\ 1 \\ ... \\ 1 \end{matrix} \right]_{n\times1}，矩阵In是n维的单位矩阵。

x‾p=1n∑i=1nxi=1nXT1n(5) \overline{x}_{p} = \frac{ 1 }{ n } \sum_{i=1}^n x_i \tag{5} = \frac{ 1 }{ n } X^T1_n

  • 样本协方差矩阵

协方差矩阵符号记为S。

Spp=1n∑i=1n(xi−x‾)(xi−x‾)T(6) S_{pp} = \frac{ 1 }{ n } \sum_{i=1}^n (x_i - \overline{x})(x_i - \overline{x})^T \tag{6}
Spp=1n(x1−x‾,x2−x‾,...,xn−x‾)(x1−x‾,x2−x‾,...,xn−x‾)T=1n[(x1,x2,...,xn)−x‾(1,1,...,1)n][(x1,x2,...,xn)−x‾(1,1,...,1)n]T=1n(XT−x‾1nT)(XT−x‾1nT)T将式(5)带入可得Spp=1n(XT−1nXT1n1nT)(XT−1nXT1n1nT)T=1n[XT(In−1n1n1nT)][XT(In−1n1n1nT)]T=1nXT(In−1n1n1nT)(In−1n1n1nT)TX令Hn=In−1n1n1nT，则可得Spp=1nXTHHTX S_{pp}= \frac{ 1 }{ n }(x_1- \overline{x},x_2 - \overline{x},...,x_n- \overline{x}) (x_1- \overline{x},x_2 - \overline{x},...,x_n- \overline{x}) ^T \\ = \frac{ 1 }{ n } [(x_1,x_2,...,x_n) - \overline{x}(1,1,...,1)_n][(x_1,x_2,...,x_n) - \overline{x}(1,1,...,1)_n]^T \\ = \frac{ 1 }{ n } (X^T-\overline{x}1_n^T) (X^T-\overline{x}1_n^T)^T \\ 将式(5)带入可得 \\ S_{pp}= \frac{ 1 }{ n }(X^T-\frac{ 1 }{ n } X^T1_n1_n^T)(X^T-\frac{ 1 }{ n } X^T1_n1_n^T)^T \\ = \frac{ 1 }{ n } [X^T(I_n - \frac{ 1 }{ n }1_n1_n^T)] [X^T(I_n-\frac{ 1 }{ n }1_n1_n^T)]^T \\ = \frac{ 1 }{ n }X^T(I_n - \frac{ 1 }{ n }1_n1_n^T)(I_n - \frac{ 1 }{ n }1_n1_n^T)^TX \\ 令H_n = I_n - \frac{ 1 }{ n }1_n1_n^T，则可得 \\ S_{pp} = \frac{ 1 }{ n }X^THH^TX

上述的H就是中心矩阵，他的作用是使得数据中心化，即
HnTX=[(x1−x‾)T(x2−x‾)T......(xn−x‾)T] H_n^TX = \left[ \begin{matrix} (x_1 - \overline{x})^T\\ (x_2 - \overline{x})^T \\ ...... \\ (x_n - \overline{x})^T \end{matrix} \right]

性质如下：

  1. H = H T
  2. Hn = H

PAC

PAC算法的思想总结一句话——将一组可能线性相关的变量通过正交变换变换成一组线性无关的变量，即原始特征重构。
接下来我们从两个角度来看PAC算法，一个是最大投影方差，另一个是最小重构距离。

最大投影方差

轻松解剖数据降维——PCA
如上图有一堆二维分散的数据点，我们选择了u1和u2两个方向进行投影，哪个方向效果更好呢？
从图中可以直观看到u1方向更好，从数学角度看，是因为它的投影矿都d1远大于d2，从而造成投影方差更大，即投影后的数据分布更加的分散。
当我们确定了u1方向投影效果最好时，即找到了主成分。我们来尝试求最大投影方差。

设 || u1 || = 1，即 u1T u1 = 1，有n个数据点。
一般步骤：

  1. 中心化
    xi−x‾x_i - \overline{x}
  2. 求一个点的投影距离
    点x1的投影距离=(x1−x‾)Tu1 点x_1的投影距离 =(x_1 - \overline{x})^Tu_1
  3. 求所有样本点的投影距离之和
    投影长度之和P=∑i=1n(xi−x‾)Tu1 投影长度之和 P = \sum_{i=1}^n (x_i - \overline{x})^Tu_1
  4. 求投影方差
    J=1n∑i=1n[(xi−x‾)Tu1]2=1n∑i=1n((xi−x‾)Tu1)T((xi−x‾)Tu1)=1n∑i=1nu1T(xi−x‾)(xi−x‾)Tu1=u1T(1n∑i=1n(xi−x‾)(xi−x‾)T)u1根据式(6)可得：J=u1TSu1(7) J = \frac{ 1 }{ n } \sum_{i=1}^n [(x_i - \overline{x})^Tu_1]^2 \\ = \frac{ 1 }{ n } \sum_{i=1}^n((x_i - \overline{x})^Tu_1)^T((x_i - \overline{x})^Tu_1) \\ =\frac{ 1 }{ n } \sum_{i=1}^n u_1^T(x_i-\overline{x})(x_i-\overline{x})^Tu_1 \\ =u_1^T(\frac{ 1 }{ n } \sum_{i=1}^n(x_i-\overline{x})(x_i-\overline{x})^T)u_1 \\ 根据式(6)可得：\\ J = u_1^TSu_1 \tag{7}
  5. 求最大投影方差

求maxJ，且u1T u1 = 1，根据拉格朗日乘子法可得：
L(u1,λ)=u1TSu1+λ(1−u1Tu1) L(u_1,\lambda) = u_1^TSu_1 + \lambda(1-u_1^Tu_1)
∂L∂u1=2Su1−2λu1=0所以可得：Su1=λu1(8) \frac{\partial L}{\partial u_1} =2Su_1-2\lambda u_1 = 0 \\ 所以可得： \\ Su_1 = \lambda u_1 \tag{8}

通过观察式（8），可以发现这是一个特征值分解，即λ\lambda是协方差矩阵S的特征值，u1是于特征值对应的特征向量。PCA的方法就是选择前k个最大特征值对应的特征向量，然后变成单位向量，即选取了k个主成分进行降维。

最小重构距离

实际上是比较n维数据点用另一个n维坐标轴映射，然后从n维挑选p个坐标轴映射的数据前后的误差。
下图原始数据点x是一个二维向量，通过u1和u2两个方向映射成一个新的同维度的数据点x’，很明显向量坐标将会改变，且新的x’ = (xTu1)u1 + (xTu2)u2
轻松解剖数据降维——PCA

同样对于n个样本的p维向量xi，我们假设中心化后映射到向量u1、u2、…、un。则新的向量：
xi′=∑k=1p((xi−x‾)Tuk)ukx'_i = \sum_{k=1}^p((x_i-\overline{x})^Tu_k)u_k
如果我们要从原先的p维降到q维，则映射后的向量为：
x^i=∑k=1q((xi−x‾)Tuk)uk\widehat{x}_i = \sum_{k=1}^q((x_i-\overline{x})^Tu_k)u_k
设重构误差为J，则：
J=1n∑i=1n∣∣xi−x^i∣∣2=1n∑i=1n∣∣∑k=q+1p((xi−x‾)Tuk)uk∣∣2=1n∑i=1n∑k=q+1p((xi−x‾)Tuk)2=∑k=q+1pukTSuk J = \frac{ 1 }{ n }\sum_{i=1}^n ||x_i-\widehat{x}_i | |^2 = \frac{ 1 }{ n }\sum_{i=1}^n|| \sum_{k=q+1}^p ((x_i-\overline{x})^Tu_k)u_k||^2 \\ = \frac{ 1 }{ n }\sum_{i=1}^n \sum_{k=q+1}^p ((x_i-\overline{x})^Tu_k)^2 \\ = \sum_{k=q+1}^p u_k^TSu_k

同理对J进行拉格朗日乘子法，得
L(uk,λ)=∑k=q+1pukTSuk+∑k=q+1pλ(1−ukTuk) L(u_k,\lambda) = \sum_{k=q+1}^pu_k^TSu_k + \sum_{k=q+1}^p\lambda(1-u_k^Tu_k)
∂L∂uk=∑k=q+1p2Su1−∑k=q+1p2λu1=0所以可得：∑k=q+1pSu1=∑k=q+1pλu1(9) \frac{\partial L}{\partial u_k} = \sum_{k=q+1}^p2Su_1- \sum_{k=q+1}^p2\lambda u_1 = 0 \\ 所以可得： \\ \sum_{k=q+1}^pSu_1 = \sum_{k=q+1}^p\lambda u_1 \tag{9}
∂L∂λ=∑k=q+1p(1−ukTuk)=0(10) \frac{\partial L}{\partial \lambda} = \sum_{k=q+1}^p (1-u_k^Tu_k)= 0 \tag{10}

将式（9）、（10）带入L函数可得：
L=∑k=q+1pλL = \sum_{k=q+1}^p \lambda

因为要使得L最小，所以选择得特征值是从最小得几个里面选择，即从p维降到q维，需要抛弃掉最小得p-q个特征值及其对应的特征向量。

从SVD角度看PAC

待续

相关推荐