机器学习与数据挖掘大数据，机器学习，人工智能 ML

PCA

2019-01-05 本文已影响1人 Dev_hj

降维算法

PCA主成分分析, 是无监督的降维方法, 可以将你的数据降低到n-1维.

它有几种不同的方式去解释原理, 下面我们来一起看看吧.

最大方差理论

样本数据是在一个n维度空间中, 我们需要找到[1, n-1]之间的维度空间的轴, 然后将样本投影到这些轴上, 下面我们来看一下, 这里我们用二维假设(便于理解, 高维类推即可).

image

可以看到, 如果投影到方差较大轴上, 数据还会保持尽可能大的距离, 如果投影到方差较少的轴上, 样本之间是非常接近的, 这就很难处理了.

我们首先对数据进行一个去中心化处理(这只是放到坐标原点附近, 不会改变数据之间原有的关系), 假设我们原本的数据集D => {X1, X2, ...}, 去中心化后的数据集D1 => {V1, V2, ...}.

我们有如下关系成立:

$V_i = X_i - \sum_i^n\frac{X_i}{n}$

我们将样本投影到对应的坐标轴上, 我们有:

$V_i = X_i\cdot W$

在几何表示上, 两个向量的内积就表示了一个向量在另一个向量上的投影了, $W$ 是单位向量(新坐标轴的).

那么, 新坐标轴的方差是:

$\sigma = \frac{1}{n}\sum_i^n(V_i - \mu_v)^2$

$\mu_v = 0$ , 因为我们是在原数据集上做了去中心化处理.

$\mu_v = \frac{1}{n}(\sum_i^nX_i^T) \cdot W$

$(\sum_i^nX_i^T) = 0$

我们的方差公式转换为:

$\sigma = \frac{1}{n}\sum_i^nV_i^2 = \frac{1}{n}\sum_i^n(X_i^TW)^2 = \frac{1}{n}\sum_i^n(X_i^TW)^T(X_i^TW) = \frac{W^T}{n}\sum_i^nX_iX^TW$

可以看出来, 其实 $XX^T$ 就是自身的协方差矩阵(去中心化之后, 均值是零), 我们将它表示为 $\sum$ , 同时, W是新坐标轴上的单位向量, 所以有,

$W^TW = 1$

我们现在有了最大化问题以及约束了

$max {W^T\sum W}$

$st. W^TW = 1$

我们引入拉格朗日乘子, 然后对W求导, 令其等于0.

$f(w) = {W^T\sum W} - \lambda{W^TW}$

${W^T\sum W} - \lambda{W^TW} = 0$

$\sum{W} = \lambda{W^T}$

这个式子就很直接了, 其实就是XX^T协方差矩阵的特征值分解, $\lambda$ 其实就是前[1, n-1]较大的特征值.

最小方差理论(最小二乘法)

image

还是这个图, 这一次我们从线性回归拟合的角度出发.

我们希望找到一条线, 可以尽可能的拟合这些点.

点到线(高维是超平面), 可以平面的法向量, 然后连接到线(超平面)上一点.

假设平面的点为 $V_k$

距离可以表示为:

$Distance(X, L) = |X - V_k|$

如果该线(超平面)由K组正交基表示, $W => {W_1, W_2, W_3, .., W_n}$ 组成, 这里二维降到一维其实只有一个w, 作为基的话, 其实还有一个特性 $|W| = 1$ , 然后我们会有, 直线上的(超平面)中可以由这组基来表示:

$V_k = \sum_{i=1}^d(W_i^TX_i)W$

其中 $W^TX_i$ 表示 $X_i$ 在 $W_i$ 方向上投影的长度, 因此, $V_k$ 其实实际上是 $X_i$ 在这一组正交基上的坐标表示(通过乘以W).

所以, 我们的优化目标:

$argmin\sum_{k=1}^n|X_i - V_k|^2$

当对应位置相同的时候是零,不同的时候是1.

$st. W^TW = \delta_{i,j} = [1, 0]$

我们将距离公式展开:

$|X_i - V_k|^2 = (X_i - V_k)^T(X_i - V_k) = X^TX - 2X^TV_k + V_K^TV_K$

第一项是个常数(原坐标系), 将 $V_k$ 的表示代入到这个式子:

$X^TV_k = X^T\sum_{i=1}^d(W^TX_k)W = \sum_{i=1}^d(W^TX_iX_i^TW)$

第三项为:

$V_K^TV_K = \sum_{i=1}^d\sum_{j=1}^d((W^TX_k)W_j)^T((W_i^TX_K)W_j)$

$W^TX$ 其实都是常数, 所以我们也忽略掉, 而且当 $i != j$ 时候, $W_i^TW_j = 0$ , 最后这个交叉项只剩下

$V_K^TV_K = \sum_{i=1}^d\sum_{j=1}^d((W^TX_k)W_j)^T((W_i^TX_K)W_j) = \sum_{i=1}^d(W^TXX^TW)$

这里面最后的表达式其实就是 $W^TXX^TW$ 的迹, 所以最后距离表示是可以转换为

$|X - V|^2 = -2X^TV_k + V_K^TV_K = -tr(W^TXX^TW) + X^TX = -tr(W^TXX^TW) + C$

取一个相反数, 变成求最大化的问题.

$argmax W^TXX^TW$

$st. W^TW = 1$

然后就和前面一样了, 通过引入拉格朗日乘子, 然后求导为零即可.

上一篇下一篇

猜你喜欢

热点阅读