在线的PCA算法

朱雀 2022-08-11 09:00 187阅读 0赞

**1、离线PCA**

PCA是一种最基本的降维算法，在机器学习中被广泛使用。它是一种线性降维，其基本思想是：

对大量的数据，找到其主成分，主成分的个数小于原始数据的维度，然后将原始数据投影到主成分张成的空间中，

可减小数据的维度。

从上面的描述我们可以总结出：

1. 原始数据(x1,x2,x3,…,xn)（列向量）是一个n维的数据，它是在n个基(1,0,0,…,0)，(0,1,0,…,0)，… ，(0,0,…0,1)下的表示。

2. 我们要找到k个主成分，每个主成分的维度是n，组成一个n×k的矩阵M，即每个主成分是M的一列。

3. 将原始数据投影到k个主成分张成的空间中，即可得到降维后的k维度的数据(x’1,x’2,x’3,…,x’k)（列向量），即(x’1,x’2,x’3,…,x’k)= (x1,x2,x3,…,xn) M。

可以看到，PCA的主要工作是找到主成分。可是如何寻找呢？下图是一个简单例子：

![Image 1][]![20140827092446991][]

原始的数据落在f\_1，f\_2为基的空间中，显然数据的维度为2。要对数据进行降维，只能降到1维，即我们只需要找到一个主成分。图中，f’\_1和f’\_2是两个主成分的候选，若选择f’\_2作为主成分，我们把数据点投影到f’\_2代表的线上后，数据之间的间隔将非常小，有些数据甚至会重合，这对于区分数据是不利的，因此f’\_2并不是一个好的主成分。而f’\_1这个主成分就相对好得多，数据投影到f’\_1后，依然可以被区分。而“被区分”怎么样才能在数学上被表示呢？就是要求投影（降维）后的数据方差最大。

本文主要讲述在线PCA算法，基本的PCA算法请参考[http://blog.codinglabs.org/articles/pca-tutorial.html][http_blog.codinglabs.org_articles_pca-tutorial.html]。

我们在这里只是简单地总结一下离线PCA。假设数据矩阵为X，其中X的每一行是一个数据，cov(X)是X的协方差矩阵，则离线PCA通过优化一下问题来寻找主成分M：

![20140827092526725][]

![Image 1][]

通过一些推导，可以通过解下列特征问题：

![20140827092631200][]

![Image 1][]

其中m\_j是M的某一列，可以看到，要求解的主成分即为cov(X)的特征向量，对应着特征值λ\_j。

**2、在线PCA**

上述离线PCA在大规模机器学习中，有一个问题：我们需要首先收集所有的数据，形成数据矩阵X，计算协方差矩阵cov(X)，如果数据非常大，或者是以流的形式出现，我们就无法收集所有数据，那离线PCA算法也自然无法应用。因此，我们需要在线的PCA算法。

为此，我们查阅资料，发现一种在线的PCA算法\[1\]。我们打算使用spark streaming进行实现。

首先，假设我们已经利用n个数据x\_1,x\_2,…,x\_n获得了U=\[u\_j\]，j=1,…,p等p个主成分，其对应的特征值集合为Λ。每个数据降维后的表示为a\_i，其维度为k，降维前数据为m维。

当第n+1个数据到来时，我们首先计算所有数据的均值

![20140827092703492][]

![Image 1][]

然后计算第n+1个数据在当前的主成分下表示的误差：

![20140827092726658][]

![Image 1][]

并将其归一化：

![Image 1][]![20140827092749059][]

新的主成分矩阵U’，为m×(k+1)的矩阵，即主成分相比k多了一个。它等于

![20140827092816578][]

![Image 1][]

其中Ｒ是(k+1)×(k+1)的一个旋转矩阵，它可以由下面的特征问题得到：

![20140827092713265][]

![Image 1][]

其中Λ’是新的特征值集合，并且D等于：

![Image 1][]

![Image 1][]![20140827092939695][]

![20140827092949928][]

![20140827092957370][]

![Image 1][]

由此，我们得到新的主成分和新的特征值，其个数比原来的个数多1，如果我们为了保持主成分的个数不变，可以选择舍弃一个最小的特征值和其对应的特征向量。

**3、在线PCA和离线PCA的运算量比较**

如果使用离线的PCA来得到新到达的数据x\_n后的特征向量，我们将重新计算cov(X)的特征向量，cov(X)的规模是m×m，而使用上述在线的PCA算法，需要求D的特征向量，D的规模是(k+1)×(k+1)，注意m>>k，所以在线PCA的算法运算量要小很多。

[Image 1]: 
[20140827092446991]: /images/20220810/8aecb77a5681494da7c2685a83bb6cab.png
[http_blog.codinglabs.org_articles_pca-tutorial.html]: http://blog.codinglabs.org/articles/pca-tutorial.html
[20140827092526725]: /images/20220810/083f9dfdc56f46b2a333ecb0590bdd5a.png
[20140827092631200]: /images/20220810/0e1e85a772554b208b46dc8c4949e9a3.png
[20140827092703492]: /images/20220810/8ad48acc65374d98ab3575a8436efdef.png
[20140827092726658]: /images/20220810/ae90e0a8219c47f9b3ae4781eaf76448.png
[20140827092749059]: /images/20220810/d629d949f8a543ec8b53bd1a75d5768e.png
[20140827092816578]: /images/20220810/40febde4a85c469da5595821233c1310.png
[20140827092713265]: /images/20220810/20a30d2c093f4eb6977056154d1fbeef.png
[20140827092939695]: /images/20220810/9f5c4fd8e55944a1b8980c7476b93f12.png
[20140827092949928]: /images/20220810/7c379ff20bfd42cb8955ac89d1d27b64.png
[20140827092957370]: /images/20220810/ec6a4310710d4c9ebce6627187348341.png