维数约减

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

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

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

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

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

PCA

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

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

根据这个原则,我们可以建立我们的优化方程.我们希望找到方向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^nu \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
评论加载中...

发表评论