机器学习之降维及PCA算法

为什么需要降维

当处理真实问题和真实数据时，我们往往遇到维度高达数百万的高维数据，而高维情形下会出现样本稀疏、计算困难等问题，这是所有机器学习方法共同面临的严重障碍，被称为“维数灾难”。通过降维，在尽可能保留原数据信息的同时，可以使得计算复杂度变低，模型迭代更快，可以应用在性能比精度重要的一些场景。

高维数据可视化是困难的，通过降维，我们可以将数据映射到低维空间，便于可视化，可以对数据有一个直观感受。

为什么可以降维

数据存在冗余，要么有一些没有用的信息，要么有一些重复的信息

消除特征之间的相关性，并发现一些潜在的特征变量

降维可以保留原始数据的主要信息，却极大降低了计算量、时间和资源

什么是降维

降维的一种方式是学习一种函数f，将原高维空间中的数据点映射到低维度的空间中。新生成的数据是原数据经过变换后的，与原数据是不一致的。

另一种方式是特征选择，即从原始数据的特征中挑选一部分作为原始数据的表达，通常根据特征重要度进行选择。

主成分分析（PCA）

PCA是一个古老的算法，但也是一个应用非常广泛的无监督降维算法。目标是基于方差提取最有价值的信息。

1. 基变换

PCA主要是基于基变换，将原始数据变换到一组新的基所表示的空间上。

基变换

其中$p{i}\in {p{1}, p{2}, p{3},..,p{R}}$是行向量，表示第$i$个基，$a{j}\in {a{1}, a{2}, a{3},..,a{M}}$是表示第$j$个原始数据。R决定了变换后的维数，是可以小于原始数据维度N的。这种矩阵相乘可以表示降维变换。

2. 方差与协方差

如何选择基，使得可以尽量保留最多的原始信息，一种直观的看法是：希望投影后的投影值尽可能分散。而分散程度可以用数学上的方差来表示，方差越大数据越分散。
方差：$Var(a) = \frac{1}{m}\sum{i=1}^{m}(a{i}-u)^2$
协方差（假设均值为0）：$Cov(a, b) = \frac{1}{m}\sum{i=1}^{m}a{i}b_{i}$
从二维降到一维可以使用方差最大来选出能使基变换后数据分散最大的方向（基），但在高维的情况下，我们需要用协方差来选择第二个方向（基）。协方差表达特征a和b之间的关系。为了让两个特征尽可能表示更多的原始信息，是不希望它们之间存在（线性）相关性的。我们可以用协方差表示两个特征a,b的相关性，当协方差为0时，表示两个特征完全独立，为了让协方差为0，选择第二个基时只能在与第一个基正交的方向上选择，因此需要选择正交基，同时要选择方差最大的方向。

3. 协方差矩阵

假设原始数据矩阵X有两个特征：

matrix_X

我们可以用X乘以X的转置，并乘上$\frac{1}{m}$来计算协方差矩阵：

matrix_cov

可见，协方差矩阵是一个对称矩阵，对角线是各个维度的方差，其他是各个维度之间的协方差。

4. 协方差矩阵对角化

目标是使$\frac{1}{m}\sum{i=1}^{m}a{i}b{i} = 0$，这里我们可以对协方差矩阵进行特征值分解，然后对特征值进行排序，取降维的前K个特征值所对应的特征向量组成矩阵$P^T=(P{1}, P{2},…,P{k})$，然后乘以原始数据矩阵，即可得到降维后的矩阵。

算法流程

输入：n维样本集X = ($x{1}, x{2},…,x{m}$)，要降到维度K
输出：降维后的样本集Y
1.对所有样本进行中心化：$x{i} = x{i} - \frac{1}{m}\sum{j=1}^{m}x_{j}$
2.计算协方差矩阵：$C = \frac{1}{m}XX^T$
3.求出协方差矩阵对应的特征值和特征向量
4.将特征向量按特征值从大到小排成矩阵，取前K行组成矩阵P
5.PX = Y即为降维后的样本集

简单代码实现

import numpy as np
'''
X: m samples, n features(m x n)
k: mumber of components to keep
'''
def pca(X, k):
    mean = mean(X, axis=0)
    X_std = X - mean
    cov_mat = cov(X_std, rowvar=0)
    eig_vals, eig_vecs = np.linalg.eig(cov_mat)
    eig_val_ind = argsort(eig_vals)            
    eig_val_ind = eig_val_ind[:-(k+1):-1]  
    k_eig_vecs = eig_vecs[:,eig_val_ind] 
    Y = X_std * k_eig_vecs
    return Y