主成分分析-PCA

重点考特征值计算（三维矩阵，代码实现不做考察。重点看 基于特征值分解协方差实现 $PCA$，$SVD$ 可以放一放

关于计算以及线性代数基本知识，推荐一篇回答 【机器学习】降维——PCA（非常详细）

$PCA$ 是一种 数据降维 的方法，属于 无监督学习

维数灾难

就是数据量大，每个样本点含有的变量很多，变量之间关联性大，增加了问题分析的复杂性巴拉巴拉的。

数据降维

降维 就是对高维度特征数据进行预处理，将高维度数据保留下最重要的一些特征，去除噪声和不重要的特征，从而实现提升数据处理速度的目的

降维的优点：

• 使得数据集更易使用
• 降低算法的计算开销成本
• 去除噪声
• 使得计算结果更易理解

常用降维算法：奇异值分解 $(SVD)$、主成分分析 $(PCA)$、因子分析 $(FA)$、独立成分分析 $(ICA)$。

基本思想

$PCA$ 的主要思想是将 $n$ 维特征映射到 $k$ 维上，这 $k$ 维是 全新的 正交特征也被称为 主成分，是在原有 $n$ 维特征的基础上重新构造出来的 $k$ 维特征。

$PCA$ 的工作就是从原始的空间中顺序地找一组 相互正交 的坐标轴，新的坐标轴的选择与数据本身是密切相关的。

其中，第一个新坐标轴选择是原始数据中方差最大的方向，第二个新坐标轴选取是与第一个坐标轴正交的平面中使得方差最大的，第三个轴是与第 $1,2$ 个轴正交的平面中方差最大的。依次类推，可以得到 $n$ 个这样的坐标轴。

通过这种方式获得的新的坐标轴，我们发现，大部分方差都包含在前面k个坐标轴中，后面的坐标轴所含的方差几乎为 $0$。于是，我们可以忽略余下的坐标轴，只保留前面 $k$ 个含有绝大部分方差的坐标轴。

事实上，这相当于只保留包含绝大部分方差的维度特征，而忽略包含方差几乎为 $0$ 的特征维度，实现对数据特征的降维处理。

如何得到这些包含最大差异性的主成分方向？

事实上，通过计算数据矩阵的 协方差矩阵，然后得到协方差矩阵的 特征值特征向量，选择特征值最大(即方差最大)的 $k$ 个特征所对应的特征向量组成的矩阵。这样就可以将数据矩阵转换到新的空间当中，实现数据特征的降维。

由于得到协方差矩阵的特征值特征向量有两种方法：特征值分解协方差矩阵、奇异值分解协方差矩阵，所以 $PCA$ 算法有两种实现方法：

1. 基于特征值分解协方差矩阵实现 $PCA$ 算法。
2. 基于 $SVD$ 分解协方差矩阵实现 $PCA$ 算法。

接下来就重点介绍这两种不同的 $PCA$ 算法（有例子

基于特征值分解协方差矩阵实现PCA（99%

协方差和散度矩阵

样本均值：

$$\bar{x}=\frac{1}{n} \sum_{i=1}^{N} x_{i}$$

样本方差：

$$S^{2}=\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)^{2}$$

样本 $X$ 和样本 $Y$ 的协方差

$$\begin{aligned} \operatorname{Cov}(X, Y) & =E[(X-E(X))(Y-E(Y))] \\ & =\frac{1}{n-1} \sum_{i=1}^{n}\left(x_{i}-\bar{x}\right)\left(y_{i}-\bar{y}\right) \end{aligned}$$

通过上述公式，可以得出以下结论：

1. 方差的计算公式是针对一维特征，即针对同一特征不同样本的取值来进行计算得到；而协方差则必须要求至少满足 二维特征；方差是协方差的特殊情况。
2. 方差和协方差的除数是 $n-1$ ,这是为了得到方差和协方差的无偏估计。

协方差为正时，说明 $X$ 和 $Y$ 是正相关关系；协方差为负时，说明 $X$ 和 $Y$ 是负相关关系；协方差为0时，说明 $X$ 和 $Y$ 是相互独立。

$Cov(X,X)$ 就是 $X$ 的方差。当样本是 $n$ 维数据时，它们的协方差实际上是协方差矩阵(对称方阵)。

例如，对于3维数据 $(x,y,z)$，计算它的协方差就是：

$$\operatorname{Cov}(X, Y, Z)=\left[\begin{array}{lll} \operatorname{Cov}(x, x) & \operatorname{Cov}(x, y) & \operatorname{Cov}(x, z) \\ \operatorname{Cov}(y, x) & \operatorname{Cov}(y, y) & \operatorname{Cov}(y, z) \\ \operatorname{Cov}(z, x) & \operatorname{Cov}(z, y) & \operatorname{Cov}(z, z) \end{array}\right]$$

散度矩阵 的定义为：（讲人话喂！）

$$The\ scatter\ matrix\ is\ computed\ by\ the\ following\ equation: \\ S=\sum_{k=1}^{n}\left(\boldsymbol{x}_{k}-\boldsymbol{m}\right)\left(\boldsymbol{x}_{k}-\boldsymbol{m}\right)^{T} \\ where\ \boldsymbol{m}\ is\ the\ mean\ vector \\ \boldsymbol{m}=\frac{1}{n} \sum_{k=1}^{n} \boldsymbol{x}_{k}$$

对于数据 $X$ 的散度矩阵为 $XX^T$ 。其实协方差矩阵和散度矩阵关系密切，散度矩阵就是协方差矩阵乘以（总数据量-1）。因此它们的特征值和特征向量是一样的。

（可以直接看后面的例子

基于特征值分解矩阵的原理

1. 特征值与特征向量

如果一个向量 $v$ 是矩阵 $A$ 的特征向量，将一定可以表示成下面的形式： $Av = \lambda v$

其中，$λ$ 是特征向量 $v$ 对应的特征值，一个矩阵的一组特征向量是一组 正交向量。

2. 特征值分解矩阵

对于矩阵 $A$，有一组特征向量 $v$，将这组向量进行正交化单位化，就能得到一组正交单位向量。特征值分解，就是将矩阵 $A$分解为如下式：

$$A=Q \Sigma Q^{-1}$$

其中，$Q$ 是矩阵 $A$ 的特征向量组成的矩阵，$Σ$ 则是一个对角阵，对角线上的元素就是特征值。

基于特征值分解协方差矩阵实现 PCA（99%

（可以看后面的例子进行理解

对于输入数据 $X=\left\{x_{1}, x_{2}, x_{3}, \ldots, x_{n}\right\}$，需要降到 $k$ 维。进行一下步骤

1. 去平均值(即去中心化)，即每一位特征减去各自的平均值。
2. 计算协方差矩阵 $\frac{1}{n} XX^T$，（注：这里除或不除样本数量 $n$ 或 $n-1$，其实对求出的特征向量没有影响。）
3. 用特征值分解方法求协方差矩阵 $\frac{1}{n} XX^T$ 的特征值与特征向量。
4. 对特征值从大到小排序，选择其中最大的 $k$ 个。然后将其对应的 $k$ 个特征向量分别作为行向量组成特征向量矩阵 $P$。
5. 将数据转换到 $k$ 个特征向量构建的新空间中，即 $Y=PX$。

关于为什么用特征值分解矩阵？

因为 $\frac{1}{n} XX^T$ 是 方阵，能很轻松的求出特征值与特征向量。当然，用奇异值分解也可以，是求特征值与特征向量的另一种方法。

举个栗子 *

$e.g.$

$$X=\left(\begin{array}{ccccc} -1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1 \end{array}\right)$$

以 $X$ 为例，我们用 $PCA$ 方法将这两行数据降到一行。

1. 因为X矩阵的每行已经是零均值，所以不需要去平均值。
2. 求协方差矩阵：

$$C=\frac{1}{5}\left(\begin{array}{ccccc} -1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1 \end{array}\right)\left(\begin{array}{cc} -1 & -2 \\ -1 & 0 \\ 0 & 0 \\ 2 & 1 \\ 0 & 1 \end{array}\right)=\left(\begin{array}{cc} \frac{6}{5} & \frac{4}{5} \\ \frac{4}{5} & \frac{6}{5} \end{array}\right)$$

3. 求协方差矩阵的特征值与特征向量。

求解后的特征值为：

$$\lambda_{1}=2, \lambda_{2}=\frac{2}{5}$$

其对应的特征向量为：

$$c_{1}\left(\begin{array}{l} 1 \\ 1 \end{array}\right), c_{2}\left(\begin{array}{c} -1 \\ 1 \end{array}\right)$$

其中对应的特征向量分别是一个通解，$c_1$, $c_2$ 可以取任意实数。那么标准化后的向量为：

$$\left(\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right),\left(\begin{array}{c} -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right)$$

4. 特征向量矩阵 $P$ 为：

$$P=\left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)$$

5. 最后我们用P的第一行乘以数据矩阵 $X$，就得到了降维后的表示：

$$Y=\left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \end{array}\right)\left(\begin{array}{ccccc} -1 & -1 & 0 & 2 & 0 \\ -2 & 0 & 0 & 1 & 1 \end{array}\right)=\left(\begin{array}{lllll} -\frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 & \frac{3}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right)$$

注意：如果我们通过特征值分解协方差矩阵，那么我们只能得到一个方向的 $PCA$ 降维。这个方向就是对数据矩阵 $X$ 从行(或列)方向上压缩降维。

基于SVD分解协方差矩阵实现PCA算法（30%

SVD分解矩阵原理

奇异值分解是一个能适用于任意矩阵的一种分解的方法，对于任意矩阵 $A$ 总是存在一个奇异值分解：

$$A = U \Sigma V^T$$

假设 $A$ 是一个 $m*n$ 的矩阵，那么得到的 $U$ 是一个 $m*m$ 的 方阵，$U$ 里面的正交向量被称为左奇异向量。

$Σ$ 是一个 $m*n$ 的矩阵，$Σ$ 除了对角线其它元素都为0，对角线上的元素称为奇异值。 $V^T$ 是 $V$ 的转置矩阵，是一个 $n*n$ 的矩阵，它里面的正交向量被称为右奇异值向量。而且一般来讲，我们会将 $Σ$ 上的值按从大到小的顺序排列。

$SVD$ 分解矩阵 $A$ 的步骤：

1. 求 $AA^T$ 的特征值和特征向量，用 单位化的特征向量 构成 $U$。
2. 求 $A^TA$ 的特征值和特征向量，用 单位化的特征向量 构成 $V$。
3. 将 $AA^T$ 或者 $A^TA$ 的特征值求平方根，然后构成 $Σ$。

python 实现

说好不会考的，跳过跳过

import numpy as np
def pca(X,k):#k is the components you want
    """PCA降维

    Args:
        X (array): 原始数据集
        k (int): 降维后的维度

    Returns:
        array: 降维后的k维数据集
    """    
    #mean of each feature
    n_samples, n_features = X.shape
    mean=np.array([np.mean(X[:,i]) for i in range(n_features)])
    #normalization
    norm_X=X-mean
    #scatter matrix
    scatter_matrix=np.dot(np.transpose(norm_X),norm_X)
    #Calculate the eigenvectors and eigenvalues
    eig_val, eig_vec = np.linalg.eig(scatter_matrix)
    eig_pairs = [(np.abs(eig_val[i]), eig_vec[:,i]) for i in range(n_features)]
    # sort eig_vec based on eig_val from highest to lowest
    eig_pairs.sort(reverse=True)
    # select the top k eig_vec
    feature=np.array([ele[1] for ele in eig_pairs[:k]])
    #get new data
    data=np.dot(norm_X,np.transpose(feature))
    return data

降维后维度数的选取

（这部分好像麻油要求，ppt也没有，了解一下就好了吧

PCA 误差

$PCA$ 的原理是，为了将数据从 $n$ 维降低到 $k$ 维，需要找到 $k$ 个向量，用于投影原始数据，使投影误差（投影距离）最小。

用公式表示如下：（看到这个公式大概知道为什么wsp不讲了

$$\frac{\frac{1}{m} \sum_{i=1}^{m}\left\|x^{(i)}-x_{\text {approx }}^{(i)}\right\|^{2}}{\frac{1}{m} \sum_{i=1}^{m}\left\|x^{(i)}\right\|^{2}} \leq 0.01$$

其中：$m$ 表示特征数

稍微用人话解释一下：分子表示原始点与投影点之间的距离之和，而误差越小，说明降维后的数据越能完整表示降维前的数据。如果这个误差小于0.01，说明降维后的数据能保留99%的信息。

k值的选取

实际应用中，我们一般根据上式，选择能使误差小于0.01（99%的信息都被保留）或0.05（95%的信息都被保留）的 $k$ 值。

而在实际编码中，在 $PCA$ 的实现过程中，对 协方差矩阵 做 奇异值分解 时，能得到 $S$ 矩阵（特征值矩阵）。此时，$PCA$ 的误差公式等价于：

$$1-\frac{\sum_{1}^{k} S_{i}}{\sum_{1}^{m} S_{i}} \leq 0.01$$

---