logo

主要成分分析(PCA)

维数约减

维数约减是一种无监督学习,它是通过对数据降维来解决数据对硬盘、内存占用过大,以及训练速度慢的问题.

另外它也是一种强力的数据可视化工具,很多高维数据难以可视化,这时我们可以通过将他们降维至二维或三维进行可视化.

在我们的数据中有很多特征非常相似,比如说这两个特征:

image

现在我们来旋转一下坐标系:

image

我们发现数据在x1纬度上变化不大,所以我们可以忽略这个维度.于是数据可以只用一个维度来表达:
image

这就是维数约减的原理.PAC是常见的维数约减算法.

PCA

如果我们找到了一个正确的向量来代替原来的纬度,那么原数据在这个向量上都投影的距离会很远:

image

如果我们找到的向量是错误的,那么原数据在这个向量上都投影的距离会很小:

image

根据这个原则,我们可以建立我们的优化方程.我们希望找到方向 u ,如果 ||u|| = 1 ,那么向量 x^{(i)} 在 u 上的投影的长度为 {x^{(i)}}^Tu ,所以最优的u会使投影的长度最大,即:

max \frac{1}{m}\sum_{i=1}^m||{x^{(i)}}^Tu||

这个公式可以整理成如下形式:

\begin{equation} \begin{split} &\frac{1}{m}\sum_{i=1}^m||{x^{(i)}}^Tu|| \\ =& \frac{1}{m}\sum_{i=1}^m({x^{(i)}}^Tu)({x^{(i)}}^Tu)^T \\ =& \frac{1}{m}\sum_{i=1}^mu^Tx^{(i)}{x^{(i)}}^Tu \\ =& u^T(\frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T)u \end{split} \end{equation}

我们发现中间的式子刚好是数据的协方差矩阵:

\Sigma = \frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T

则原式可以写为:

max \; u^T\Sigma u

条件 ||u|| = 1 可以写为 u^Tu = 1

这是一个有约束的优化问题,我们可以用拉格朗日定理求极值:

l(u,\lambda) = u^T\Sigma u - \lambda(u^Tu - 1)

极值处导数为0,所以对拉格朗日函数求导,得:

\Sigma u - \lambda u = 0

即:

\Sigma u = \lambda u

这与特征向量的定义相吻合,所以 u 为 \Sigma 的特征向量.

在实际运用PAC的时候,我们并不会这样去计算协方差矩阵:

\Sigma = \frac{1}{m}\sum_{i=1}^mx^{(i)}{x^{(i)}}^T

如果数据的特征数非常多的话,比如说 x^{(i)} \in R^{5000} ,那么协方差矩阵会非常庞大 \Sigma \in R^{5000*5000} .

对 X 奇异值分解可以轻松的得到 X^TX 的特征向量:

X = U\Lambda V^T

其中 V 就是 X^TX 的特征向量.

现在我们计算出了新的纬度 V ,但是这个维度和原理的纬度大小是一样的,仅仅是用这个维度相当于将原来的数据换了个坐标系,并不能做到压缩纬度的目的.我们需要取 V 中比较重要的纬度,即奇异值比较大的k个维度:

u = u_1,u_2,...,u_k

对于向量B在向量A上的投影,计算方法为 A^TB ,同样的对于 x^{(i)} \in R^n 在 u \in R^k 上的投影为:

y^{(i)} = \begin{bmatrix} u_1^Tx^{(i)}\newline u_2^Tx^{(i)}\newline \vdots \newline u_k^Tx^{(i)}\newline \end{bmatrix}

PCA还可以以另外一种思路来理解,我们把数据 X 的矩阵看成是由各"分力"的叠加,"分力"的方向就是特征向量的方向,"分力"的大小就是特征值.我们可以使用奇异值分解求出 X 的特征向量,与特征值.维度约减就是忽略"分力"较小的方向,只考虑"分力较大的方向".关于奇异值分解(SVD)的内容参考我的另一篇文章奇异值分解(SVD)的理解及其在机器学习中的应用.

编程实现:
https://www.kaggle.com/swimmingwhale/principal-component-analysis

参考:
http://cs229.stanford.edu/
https://www.coursera.org/learn/machine-learning

posted @ 2018-08-12 09:03:35
评论加载中...
发表评论