落园 » 统计学习精要(The Elements of Statistical Learning)课堂笔记(二十五):降维和PCA|专注经济视角下的互联网

统计学习精要(The Elements of Statistical Learning)课堂笔记(二十五):降维和PCA

 降维

降维完全属于unsupervised learning了,即给定数据集\{x_{1},...,x_{n}\},x_{i}\in\mathbb{R}^{p},我们希望降到q维的\{z_{1},...,z_{n}\}。从这个角度来讲,降维和聚类还是有相通之处的,都是对于特征的提取。只是一个从行的角度出发,一个对列操作的感觉。

PCA(主成分分析,Principle Component Analysis)

个人觉得这也是起名字起的比较好的模型之一...乍一听起来很有用的感觉 -_-||

1. 求u_{1},\left\Vert u_{1}\right\Vert =1使得z_{i}=u_{i}x_{i},且\sum z_{i}^{2}最大。

PCA

直觉上来讲,就是想寻找一个主方向。

这样,求解问题为:

\max\sum z_{i}^{2}=\sum(u_{1}x_{i})^{2}=\sum u_{1}'x_{i}x_{i}'u_{1}=u_{1}'\left(\sum x_{i}x_{i}'\right)u_{1}。所以我们只需要求一阶导数\frac{\partial\sum z_{i}^{2}}{\partial u_{1}}即可。

设A为对称矩阵,则存在正交阵u'u=I使得A=u\Lambda u',其中\Lambda=\left[\begin{array}{ccc}\lambda_{1}\\ & \ddots\\ & & \lambda_{n}\end{array}\right]为A的特征值矩阵,故Au_{i}=\lambda_{i}u_{i}(列向量为特征向量)。不失一般性,我们可以排序使得\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{n}(从大到小排序)。

最大特征值: \max_{\left\Vert x\right\Vert =1}x'Ax=\lambda_{1}

同时C=\frac{1}{n}\sum x_{i}x_{i}'为x的相关矩阵,\{u_{1},u_{2},...,u_{q}\}=U_{q},从而z_{i}=U_{q}U_{q}'x_{i},\forall i

2. 找到\{u_{1},u_{2},...,u_{q}\}=U_{q}(q维的子空间)

x_{i}投影到该q维空间,这样z_{i}=U_{q}U_{q}'x_{i}=U_{q}\left[\begin{array}{c}u_{1}'\\\vdots\\u_{q}'\end{array}\right]x_{i}=U_{q}\left[\begin{array}{c}u_{1}'x_{i}\\\vdots\\u_{q}'x_{i}\end{array}\right]=\left[u_{1},u_{2},...,u_{q}\right]\left[\begin{array}{c}u_{1}'x_{i}\\\vdots\\u_{q}'x_{i}\end{array}\right]=(u_{1}'x_{i})u_{1}+...+(u_{q}'x_{i})u_{q},且\left\Vert u_{q}u_{q}'x-x\right\Vert _{F}^{2}最小。

A矩阵的范数:\left\Vert A\right\Vert _{F}=\sum_{i}\sum_{j}a_{ij}^{2}=tr(AA')
tr表示矩阵的迹(对角线元素和)。

则上述问题等价于,求(u_{1},...,u_{q})=U_{q}使得tr[(u_{q}u_{q}'x-x)'(u_{q}u_{q}'x-x)]最小。

=tr(x'U_{q}U_{q}'U_{q}U_{q}'x-x'U_{q}U_{q}'x-x'U_{q}U_{q}'x+x'x)=tr(-x'U_{q}U_{q}'x+x'x)最小。

即使得tr(x'U_{q}U_{q}'x)最大(注意没有负号)。

S=x'x称为数据的相似矩阵=(x_{i}'x_{j})

AA'A'A均为对称阵,且两个阵有相同的特征值。记r为A的秩,AA'的特征向量u_{1},...,u_{m}\in\mathbb{R}^{m},A'A的特征向量v_{1},...,v_{m}\in\mathbb{R}^{n},则A'u_{i}=\lambda_{i}u_{i}A'v_{i}=\lambda_{i}v_{i}。做奇异值分解,则A=U\Lambda V'.

由此,tr(x'U_{q}U_{q}'x)求得的和前述结果等价。

回到PCA。如果降维后需要重构,则u_{i}z_{i}=\hat{x_{i}},解\min\sum_{i}\left\Vert x_{i}-\hat{x_{i}}\right\Vert 即可。

3. 对偶PCA。如果p\geq n即数据非常高的时候,可以转置后再做。

4. KPCA (kernel)PCA也可以先用核函数\Phi(\cdot),即实现非线性的降维。需要注意,降维的过程需要保持可逆。

---------------

PS. PCA不适合解决overfitting的问题。如果需要解决,加regularization项。


Comments

Leave a Reply

Your email address will not be published. Required fields are marked *