【主成份分析】PCA推导

2019-01-24 本文已影响12人 dapenghuang

假设空间 $R^{n}$ 中有m个点{ $x^{1},......,x^{n}$ },希望压缩，对每个 $x^{i}$ 都有一个向量 $c^{i} \in R^{l}$ ，并且l < m(所以才压缩。)。所以需要找到一个编码函数f(x) = c 和一个解码函数 $g(c) \approx x$ 。

在PCA中我们用矩阵乘法作为解码器 $g(c) = Dc ,D \in R^{n \times l}$ ，约定D中所有列向量都有单位范数，同时限制D的列向量彼此正交。

为了得到最优的编码 $c^{*}$ ,希望平方L2范数最小： $c^{*} = arg min_{c}||x-g(c)||^{2}_{2} \tag{2.55}$ 。选择L2平方范数的原因是计算简便，可以用向量点积计算。

公式2.55可以简化为 $c^{*} =(x-g(c))^{T}(x-g(c)) \tag{2.56}$

展开公式2.56，在利用分配率，标量的转置等于自己等性质以及省略与c无关的项，可得： $c^{*} = arg min_{c}-2x^{T}g(c)+g(c)^{T}g(c) \tag{2.57}$

给公式2.57带入g(c)的定义可得 $c^{*} = arg min_{c}-2x^{T}Dc + c^{T}D^{T}Dc \tag{2.60}$

由于D各列向量之间彼此正交，且范数为1， $D^{T}D = I$ ，所以公式2.60简化为 $c^{*} = arg min_{c}-2x^{T}Dc + c^{T}c \tag{2.62}$

用向量微积分来解决最优化问题，公式2.62等价于

$\nabla_{c}(-2x^{T}Dc + c^{T}c) =0 \tag{2.63}$

参考常用矩阵微分公式：https://wenku.baidu.com/view/ff79346a55270722192ef7ff.html

公式2.63等价于

$-2D^{T}x + 2c =0 \tag{2.64}$

$c = f(x) = D^{T}x \tag{2.66}$

重新构建回x的操作为

$x^{*} = r(x) = g(c) = Dc = DD^{T}x \tag{2.67}$

通过上述推导，编码器（公式2.66）和解码器（公式2.67）都有了，接下来问题是如何找到矩阵D。

目标函数是最小化编码再解码后所有点与原始点的误差，即最小化所有点的误差矩阵的Frobenius范数。

$D^{*} =arg min_{D} \sqrt{\sum_{i,j}(x_{j}^{(i)} - r(x^{(i)})_{j})^{2}} ，在D各列向量正交且范数为1的前提下 D^{T}D = I_{l} \tag{2.68}$

上述公式解释为在原数据点x，和编码再解码后的的数据点的距离之和最小。

把所有的点向量堆叠成一个矩阵（这里就可以转一个一个样本的串行运算为并行运算），记为 $X \in R^{n \times m}$ (注：此处与原书表示方法不同，可以更简便)

则公式2.68可表示为：

$D^{*} =arg min_{D} ||X - DD^{T}X||^{2}_{F} \tag{2.69}$

考虑到Frobenius范数的一个性质： $||A||_{F} = \sqrt{Tr(AA^{T})}$ ，则：

$D^{*} =arg min_{D} Tr((X - DD^{T}X)(X - DD^{T}X)^{T}) \tag{2.70}$

将公式2.70展开，并去除与D无关的项,在考虑到迹运算可以顺序调换位置的特性 $Tr(\prod_{i=1}^{n}F^{i}) = Tr(F^{n}\prod_{i=1}^{n-1}F^{i})$ 以及转置运算的特性： $(AB)^{T} = B^{T}A^{T}$ ，则等价于

$argmin_{D}-Tr(D^{T}XX^{T}D) \tag{2.71}$

考察这里公式2.71和原书的2.84，因为这里定义的X纬度和书中相反，所以结论正好一致。

公式2.71的最优化问题可以通过特征分解来求解，最优的D是 $XX^{T}$ (注意这里的x是书中x的转置)最大特特征值对应的特征向量。


import numpy as np

from sklearn.decomposition import PCA

X = np.array([[-1, -1], [-2, -1], [-3, -2], [1, 1], [2, 1], [3, 2]])

pca = PCA(n_components=2)

pca.fit(X)

# PCA(copy=True, iterated_power='auto', n_components=2, random_state=None,

#  svd_solver='auto', tol=0.0, whiten=False)

print(pca.explained_variance_ratio_)

# [ 0.99244...  0.00755...]

print(pca.singular_values_)

#[ 6.30061...  0.54980...]

PCA和SVD的区别：

https://www.zhihu.com/question/38319536/answer/131029607

SVD可以认为是PCA的一种计算方法，PCA中的特征值和SVD中的奇异值是有关系的。

手机扫码或点击此处访问我的个站

我的个站.png

【主成份分析】PCA推导

猜你喜欢

热点阅读