网站建设公司的名字,电商网站开发人员人数,南通建设工程网,如何增强网站的安全性近期在完成信息论的作业#xff0c;发现网上的资料大多是直观解释#xff0c;对其中的数学原理介绍甚少#xff0c;并且只介绍了向量降维#xff0c;而没有介绍向量重构的问题#xff08;重构指的是#xff1a;根据降维后的低维向量来恢复原始向量#xff09;#xff0…近期在完成信息论的作业发现网上的资料大多是直观解释对其中的数学原理介绍甚少并且只介绍了向量降维而没有介绍向量重构的问题重构指的是根据降维后的低维向量来恢复原始向量因此在这里做一个总结配合另一篇博客看效果可能会更好参考博客。
简介
PCA降维就是要把 m m m维空间的n个样本点 x i , i 1 ⋯ n x_i,i1\cdots n xi,i1⋯n映射成 l l l维的低维空间中的向量 y i , i 1 ⋯ n y_i,i1\cdots n yi,i1⋯n其中 l ≪ m l\ll m l≪m。这个映射不是随意的而是要确保利用低维的向量 y i y_i yi重构出的 x i ′ x_i^{} xi′与原向量 x i x_i xi的误差最小化。这个过程可以描述成 y l × 1 W l × m x m × 1 y_{l\times1}W_{l\times m}x_{m\times1} yl×1Wl×mxm×1 于是PCA的任务就是找到这样一个W矩阵。
算法数学推导
我们考虑一个二维空间中的数据压缩成一维的问题 给定五个样本点 x i , i 1 ⋯ 5 x_i,i1\cdots5 xi,i1⋯5每个样本点都是一个二维的列向量把它们拼成一个矩阵 X ( x 1 , x 2 , x 3 , x 4 , x 5 ) [ 1 1 2 4 2 1 3 3 4 4 ] X(x_1,x_2,x_3,x_4,x_5)\begin{bmatrix}11242\\13344\end{bmatrix} X(x1,x2,x3,x4,x5)[1113234424]。 这个例子和文章开头提到的那篇博客中的例子是一致的可以参考那篇博客的图片。 我们知道每个向量是通过一组基和在这组基下的坐标来描述的例如 x 1 [ 1 , 1 ] T x_1[1,1]^T x1[1,1]T是该向量在单位正交基 ξ 1 [ 0 , 1 ] T , ξ 2 [ 1 , 0 ] T \xi_1[0,1]^T,\xi_2[1,0]^T ξ1[0,1]T,ξ2[1,0]T下的坐标表示坐标实际上就是向量向各个基上的投影值。同样的如果我们要将一个二维向量压缩成一维向量那么只需要找到一条直线直线的单位方向向量 w w w作为基然后用向量向这条直线的投影值就可以描述压缩后的一维向量。
一条直线可以用它经过的点 μ \mu μ和单位方向向量 w w w来描述即 x μ α w x\mu\alpha w xμαw这里我们用的 μ \mu μ是上述五个样本点的均值 [ 2 , 3 ] T [2,3]^T [2,3]T这里的 α \alpha α就可以理解为坐标 w w w是基。那么我们要寻找的二维向量 x i x_i xi经过压缩后的一维向量其实就是 α i \alpha_i αi现在需要确定 w w w这样才能求出二维向量向直线的投影值。正如前一节所述这个 w w w不是任意的而是应该确保重构后的误差最小化它可以描述成如下的优化问题 min w f ( w ) 1 2 ∑ i 1 n ∥ ( μ α i w ) − x i ∥ 2 2 \min _{w} f(w)\frac{1}{2} \sum_{i1}^n\left\|\left(\mu\alpha_i w\right)-x_i\right\|_2^2 wminf(w)21i1∑n∥(μαiw)−xi∥22 先求出 α i \alpha_i αi的取值 ∂ f ∂ α i w T ( μ α i w − x i ) 0 \frac{\partial f}{\partial \alpha_i}w^T(\mu\alpha_iw-x_i)0 ∂αi∂fwT(μαiw−xi)0 由于 w w w是单位向量即 w T w 1 w^Tw1 wTw1由上式可得 α i w T ( x i − μ ) \alpha_iw^T(x_i-\mu) αiwT(xi−μ) 这个公式就给出了 α i \alpha_i αi的求解方法。下面继续推导确定 w w w的过程定义散布矩阵如下 S ∑ i 1 n ( x i − μ ) ( x i − μ ) T S\sum_{i1}^n(x_i-\mu)(x_i-\mu)^T Si1∑n(xi−μ)(xi−μ)T 对于上面的例子我们把 X X X中的每个样本 x i x_i xi都减去均值 μ \mu μ得到一个新的矩阵记为 X ~ [ − 1 − 1 0 2 0 − 2 0 0 1 1 ] \tilde{X}\begin{bmatrix}-1-1020\\-20011\end{bmatrix} X~[−1−2−10002101]那么上面的散步矩阵其实可以简单地记为 S X ~ X ~ T S\tilde{X}\tilde{X}^T SX~X~T 说明它是一个对称矩阵。 将上面求出的 α i \alpha_i αi的表达式代入到 f ( w ) f(w) f(w)中得到 f ( w ) 1 2 ∑ i 1 n ∥ α i w − ( x i − μ ) ∥ 2 2 1 2 ( ∑ i 1 n α i 2 ∥ w ∥ 2 2 − 2 ∑ i 1 n α i w T ( x i − μ ) ∑ i 1 n ∥ x i − μ ∥ 2 2 ) − 1 2 ∑ i 1 n α i 2 1 2 ∑ i 1 n ∥ x i − μ ∥ 2 2 − 1 2 ∑ i 1 n [ w T ( x i − μ ) ] 2 1 2 ∑ i 1 n ∥ x i − μ ∥ 2 2 − 1 2 ∑ i 1 n w T ( x i − μ ) ( x i − μ ) T w 1 2 ∑ i 1 n ∥ x i − μ ∥ 2 2 − 1 2 w T ( ∑ i 1 n ( x i − μ ) ( x i − μ ) T ) w 1 2 ∑ i 1 n ∥ x i − μ ∥ 2 2 − 1 2 w T S w 1 2 ∑ i 1 n ∥ x i − μ ∥ 2 2 \begin{aligned} f(\boldsymbol{w}) \frac{1}{2} \sum_{i1}^n\left\|\alpha_i \boldsymbol{w}-\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)\right\|_2^2 \\ \frac{1}{2}\left(\sum_{i1}^n \alpha_i^2\|\boldsymbol{w}\|_2^2-2 \sum_{i1}^n \alpha_i \boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)\sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2\right) \\ -\frac{1}{2} \sum_{i1}^n \alpha_i^2\frac{1}{2} \sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2 \\ -\frac{1}{2} \sum_{i1}^n\left[\boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)\right]^2\frac{1}{2} \sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2 \\ -\frac{1}{2} \sum_{i1}^n \boldsymbol{w}^{\mathrm{T}}\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)^{\mathrm{T}} \boldsymbol{w}\frac{1}{2} \sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2 \\ -\frac{1}{2} \boldsymbol{w}^{\mathrm{T}}\left(\sum_{i1}^n\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)\left(\boldsymbol{x}_i-\boldsymbol{\mu}\right)^{\mathrm{T}}\right) \boldsymbol{w}\frac{1}{2} \sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2 \\ -\frac{1}{2} \boldsymbol{w}^{\mathrm{T}} S \boldsymbol{w}\frac{1}{2} \sum_{i1}^n\left\|\boldsymbol{x}_i-\boldsymbol{\mu}\right\|_2^2 \end{aligned} f(w)21i1∑n∥αiw−(xi−μ)∥2221(i1∑nαi2∥w∥22−2i1∑nαiwT(xi−μ)i1∑n∥xi−μ∥22)−21i1∑nαi221i1∑n∥xi−μ∥22−21i1∑n[wT(xi−μ)]221i1∑n∥xi−μ∥22−21i1∑nwT(xi−μ)(xi−μ)Tw21i1∑n∥xi−μ∥22−21wT(i1∑n(xi−μ)(xi−μ)T)w21i1∑n∥xi−μ∥22−21wTSw21i1∑n∥xi−μ∥22 上式的第二项与 w w w无关因此要极小化 f ( w ) f(w) f(w)只要使第一项极小化于是优化问题转化为 min − 1 2 w T S w s . t . w T w 1 \begin{aligned}\min -\frac{1}{2}w^TSw\\ {\rm s.t.\ } w^Tw1\end{aligned} mins.t. −21wTSwwTw1 这个优化问题可以用拉格朗日乘子法求解令拉格朗日函数为 L ( w , λ ) − 1 2 w T S w λ 2 ( w T w − 1 ) L(w,\lambda)-\frac{1}{2}w^TSw\frac{\lambda}{2}(w^Tw-1) L(w,λ)−21wTSw2λ(wTw−1) 令 ∂ L ∂ w − S w λ w 0 \frac{\partial L}{\partial w}-Sw\lambda w0 ∂w∂L−Swλw0 从而 S w λ w Sw\lambda w Swλw 到这里结果已经逐渐清晰了我们要求的 w w w正是矩阵 S S S的特征向量。稍作变形 w T S w λ w T w λ w^TSw\lambda w^Tw\lambda wTSwλwTwλ 我们要最小化 − 1 2 w T S w -\frac{1}{2}w^TSw −21wTSw就是要最大化 w T S w w^TSw wTSw则 w w w应该是 S S S的最大特征值 λ max \lambda_{\max} λmax对应的特征向量。
算法总结
至此我们可以总结一下二维向量压缩成一维的PCA的方法 (1)求矩阵 S ∑ i 1 n ( x i − μ ) ( x i − μ ) T X ~ X ~ T S\sum_{i1}^n(x_i-\mu)(x_i-\mu)^T\tilde{X}\tilde{X}^T Si1∑n(xi−μ)(xi−μ)TX~X~T (2)求 S S S最大的特征值对应的特征向量即 w w w (3)求 α i w T ( x i − μ ) \alpha_iw^T(x_i-\mu) αiwT(xi−μ)
于是 X ( x 1 , x 2 , x 3 , x 4 , x 5 ) X(x_1,x_2,x_3,x_4,x_5) X(x1,x2,x3,x4,x5)经过压缩之后得到的结果就是 Y ( α 1 , α 2 , α 3 , α 4 , α 5 ) Y(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5) Y(α1,α2,α3,α4,α5)。
投影到方向向量 w w w所对应的直线之后 w w w成了唯一的一个基于是一维空间中的样本 x i ′ x_i^{} xi′可以由基向量 w w w表示 x i ′ μ α i w x_i^{}\mu\alpha_iw xi′μαiw 在原来的2维空间中我们用基的系数来表示样本 x i x_i xi而在1维空间中同样以基 w w w的系数 α i \alpha_i αi来表示一维向量它被称为主成分。
将二维向量压缩成一维向量 α i \alpha_i αi有时候只是为了减少传输时的数据量一维向量是无法直接使用的需要根据一维向量重构出原来的二维向量。如何重构呢其实上面关于的 x i ′ x_i^{} xi′的公式已经给出了答案。
二维样本PCA降维的例子
还是上面的例子我们按照这个流程走一遍 μ [ 2 , 3 ] T \mu[2,3]^T μ[2,3]T X ~ X − μ [ − 1 − 1 0 2 0 − 2 0 0 1 1 ] \tilde{X}X-\mu\begin{bmatrix}-1-1020\\-20011\end{bmatrix} X~X−μ[−1−2−10002101] S X ~ X ~ T [ − 1 − 1 0 2 0 − 2 0 0 1 1 ] [ − 1 − 2 − 1 0 0 0 2 1 0 1 ] [ 6 4 4 6 ] S\tilde{X}\tilde{X}^T\begin{bmatrix}-1-1020\\-20011\end{bmatrix}\begin{bmatrix}-1-2\\-10\\00\\21\\01\end{bmatrix}\begin{bmatrix}64\\46\end{bmatrix} SX~X~T[−1−2−10002101] −1−1020−20011 [6446] S的最大特征值为10对应特征向量 w [ 1 2 , 1 2 ] T w[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^T w[2 1,2 1]T 于是降维后的表示为 Y ( α 1 , α 2 , α 3 , α 4 , α 5 ) w T X ~ [ 1 2 , 1 2 ] [ − 1 − 1 0 2 0 − 2 0 0 1 1 ] [ − 3 / 2 , − 1 / 2 , 0 , 3 / 2 , − 1 / 2 ] Y(\alpha_1,\alpha_2,\alpha_3,\alpha_4,\alpha_5)w^T\tilde{X}[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]\begin{bmatrix}-1-1020\\-20011\end{bmatrix}[-3/\sqrt{2},-1/\sqrt{2},0,3/\sqrt{2},-1/\sqrt{2}] Y(α1,α2,α3,α4,α5)wTX~[2 1,2 1][−1−2−10002101][−3/2 ,−1/2 ,0,3/2 ,−1/2 ]
要重构第一个样本 x 1 ′ x_1{} x1′方法是 x 1 ′ μ α 1 w [ 2 , 3 ] T − 3 2 [ 1 2 , 1 2 ] T [ 1 2 , 3 2 ] T x_1^{}\mu\alpha_1w[2,3]^T\frac{-3}{\sqrt{2}}[\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}]^T[\frac{1}{2},\frac{3}{2}]^T x1′μα1w[2,3]T2 −3[2 1,2 1]T[21,23]T 当然与原本的 x 1 [ 1 , 1 ] T x_1[1,1]^T x1[1,1]T还是有一些误差的。
更高维的情况
前面介绍的是二维降为一维的情况更一般地对于 m m m维向量 x i x_i xi如果要降维为 l l l维的 y i y_i yi算法也是类似的不加证明地给出以下步骤 (1)求矩阵 S ∑ i 1 n ( x i − μ ) ( x i − μ ) T X ~ X ~ T S\sum_{i1}^n(x_i-\mu)(x_i-\mu)^T\tilde{X}\tilde{X}^T Si1∑n(xi−μ)(xi−μ)TX~X~T (2)求 S S S的所有特征值从大到小排列选取前 l l l个特征值所对应的特征向量即 W ( w 1 , w 2 , ⋯ , w l ) W(w_1,w_2,\cdots,w_l) W(w1,w2,⋯,wl)。 (3)求各个样本点 x i x_i xi对应于基 w 1 , w 2 , ⋯ , w l w_1,w_2,\cdots,w_l w1,w2,⋯,wl的系数即主成分 α i , k w k T ( x i − μ ) , k 1 ⋯ l \alpha_{i,k}w_k^T(x_i-\mu),k1\cdots l αi,kwkT(xi−μ),k1⋯l得到低维的表示 y i ( α i , 1 , α i , 2 , ⋯ α i , l ) T y_i(\alpha_{i,1},\alpha_{i,2},\cdots \alpha_{i,l})^T yi(αi,1,αi,2,⋯αi,l)T 这个过程可以写成矩阵的形式 Y W T X ~ YW^T\tilde{X} YWTX~ Y ( y 1 , y 2 , ⋯ , y n ) Y(y_1,y_2,\cdots,y_n) Y(y1,y2,⋯,yn)是压缩后的样本点组成的矩阵。 (4) 原向量的重构 x i ′ μ ∑ k 1 L α i , k w k x_i^{}\mu\sum_{k1}^L\alpha_{i,k}w_k xi′μk1∑Lαi,kwk 写成矩阵的形式为 X ′ μ W Y X^{}\muWY X′μWY
PCA用于图像处理
原图 PCA处理后(选40个特征向量)
