机器学习 PCA算法

机器学习 PCA算法

七月 31, 2020

夜间观看请点

PCA在机器学习降维中的应用

为什么要降维(Dimensionality Reduction)?

1.提取重要信息,防止计算量过大

2.高维信息无法用图像呈现,将图像降维至3维以下可以用图像呈现

如何降维?

用两个简单的例子来说明:

2维到1维:

image-20200731190754948

用一条直线拟合二维平面上的所有数据点,然后每个数据点在这条线上都具有一个投影坐标,从而2维数据坐标平面变为1维直线

3维到2维:

image-20200731191147148

同样地,用一个平面拟合空间里的所有数据点,把每个数据点投影在这个平面上,从而3维数据坐标空间变为2维平面

PCA(Principle Components Analysis)主成分分析法

PCA本质上是在找出一組最能代表你手中數據的主成分(Principal Components),並以此為基底重新得到數據的成分表徵。這個新的成分表徵能為數據降維、去關聯並幫助我們理解數據本質。

image-20200731191907123

n维空间需要n个线性无关的向量来作为空间的基,可以简单理解为n维空间需要n个坐标轴。

例如2维空间降维到1维空间,本质上就是找到一个向量,将2维平面上的所有点都投影到这个向量上。如果是n维空间降维到k维空间,则需要寻找到k个向量,并将每个数据点投影到这k个向量上,从而构成新的k维空间坐标$$\vec a = (x_1,x_2,x_3) \in \mathbb{R^3}$$

3维空间降维到2维空间之后,产生2个基,从而向量可以重新表示为:

假设变换矩阵为U,则新的坐标Z = U*X(原有坐标)

其中$$\vec a = (z_1,z_2)\in \mathbb{R^2}$$

经过这样的流程,三维坐标被化为二维坐标,之所以二维坐标依然能保留三维数据的主要信息,是因为两个基底本身是三维的,并且他们描述了这个三维数据集的主要特性,因此后续只需要对这两个基进行线性组合就可以了。在PCA算法中,我们将N维空间压缩到K维空间,其步骤如下

算法具体流程

image-20200731194118017

假设我们要把N维数据降到K维

定义协方差矩阵(Covariance Matrix):

$$\Sigma = 1/m \sum_{i=1}^n (x^i)(x^i)^T$$

其中x^i为第i个训练数据,注意左侧的符号是大写的Sigma,不是求和符号。

协方差矩阵是一个n* n的对称矩阵,应用svd/eig函数求得协方差矩阵的特征向量,返回值[U,S,V]为3个矩阵,其中S为与协方差矩阵相同大小的矩阵,并满足U* S* V’ = Sigma。

SVD函数会将矩阵的N个特征向量按照重要性降序排列,我们选取前K个,再将原有的数据集投影到这K个比较重要的特征向量上,那么我们就将原有的N维数据压缩成了K维数据,这也是PCA的主要思想。除此之外,数学上证明,协方差矩阵的特征向量值就是我们需要找的主成分

SVD函数返回值U是协方差矩阵的特征向量矩阵,是一个n*n方阵,选取前k个后变为n*k的降维矩阵,原有的坐标Xi是一个n1的向量。$$z^i = U^T * x^i$$

其中z为k维空间的k*1的新坐标,x为原n维空间的坐标。

image-20200731205646922

下面是一段关于特征向量的说明作为小结:

具体的说,求特征向量,就是把矩阵A所代表的空间进行正交分解,使得A的向量集合可以表示为每个向量a在各个特征向量上的投影长度。我们通常求特征值和特征向量即为求出这个矩阵能使哪些向量只发生拉伸,而方向不发生变化,观察其发生拉伸的程度。这样做的意义在于,看清一个矩阵在哪些方面能产生最大的分散度(scatter),减少重叠,意味着更多的信息被保留下来。

我们如何衡量一个降维是好还是坏?

1.较高的近似程度 2.所选择的K个基有较大变异(Variance)(原来的数据集在这个基上分散得最开)

当你选择的K个基具有了很好的代表性,那么降维之后的数据就能很好近似地还原原有的数据。为了衡量近似程度,这里需要引出一个概念:重建偏差(RE)

重建偏差(Reconstruction Error):

这个概念应该很好理解,就是原有数据被投影到k维之后,再还原回n维空间,值得指出的是,由于PCA没有保留所有的主成分(否则就无法实现降维),还原数据之后原有的数据必然会与还原的数据产生一定的偏差(就数据集而言),这些偏差定义出了RE:等于所有还原数据和原有数据的距离之和

image-20200731211902129

其中T^-1(因为图是别处拿的,所以其实是降维矩阵U)的逆矩阵。

根据前文,我们有$$z^i = U^T * x^i$$ 那么想要还原x,就只需要左乘U’的逆矩阵,即$$inv(U^T)*z^i = X^i$$

image-20200731212651722

图中黄线的距离之和就是RE的值

误差程度如下定义:image-20200731213131810

倘若我们需要实现99%的近似程度,只需要选择一个k能使得误差程度<1%就可以了,当然为了实现最大程度的压缩,k越小越好。

有人可能会问,是不是存在别的近似方式,使得误差程度更小呢?

数学上证明(苦笑),PCA方式实现的近似是误差程度最小的。

最后贴一个很好的关于PCA的链接:

https://leemeng.tw/essence-of-principal-component-analysis.html

返回主页