目录
向量表示与基变换1.1 内积1.2 基1.3 基变换的矩阵表示最大可分性2.1 方差2.2 协方差2.3 协方差矩阵2.4 矩阵对角化2.5 补充3 求解步骤4 性质5 细节5.1 零均值化5.2 与 SVD的对比参考文章/search?type=content&q=PCA
PCA(Principal Component Analysis)
是一种常见的数据分析方式,常用于高维数据的降维,可用于提取数据的主要特征分量。
PCA 的数学推导可以从最大可分型和最近重构性两方面进行
前者的优化条件为划分后方差最大,后者的优化条件为点到划分平面距离最小
这里我将从最大可分性的角度进行证明。
向量表示与基变换
介绍线代基本知识
1.1 内积
两个向量A、BA、BA、B的内积表示形式为
(a1,a2,....,an)⋅(b1,b2,...,bn)=a1b1+a2b2+....+anbn(a_1,a_2,....,a_n)\cdot(b_1,b_2,...,b_n) = a_1b_1+a_2b_2+....+a_nb_n(a1,a2,....,an)⋅(b1,b2,...,bn)=a1b1+a2b2+....+anbn
内积运算将两个向量映射为实数,计算方式容易理解,但是物理含义并不明白。
从几何角度进行分析,假设A、BA、BA、B为二维向量,则
A=(x1,y1),B=(x2,y2),A⋅B=∣A∣∣B∣cos(α)A = (x_1,y_1),B=(x_2,y_2),A\cdot B= |A||B|cos(\alpha)A=(x1,y1),B=(x2,y2),A⋅B=∣A∣∣B∣cos(α)
如下图所示
A、BA、BA、B的内积就是AAA到BBB的投影乘以BBB的模
若是假设BBB的模为111,即∣B∣=1|B| = 1∣B∣=1,则
A⋅B=∣A∣cost(α)A\cdot B = |A|cost(\alpha)A⋅B=∣A∣cost(α)
A与B的内积值等于A向B所在直线投影的标量长度
这是第一个重要结论,将在后面推导中反复使用此结论
1.2 基
我们常常用到的坐标系中,向量(3,2)(3,2)(3,2)隐式定义了:以x轴和y轴正方向长度为111的向量为标准。
向量(3,2)(3,2)(3,2)实际上就是在xxx轴上投影为333,yyy轴上投影为222。
投影为标量,有正负
向量(3,2)(3,2)(3,2)在(1,0),(0,1)(1,0),(0,1)(1,0),(0,1)这组基上的坐标,即分别内积即可,结果依然是(3,2)(3,2)(3,2)
结论:
我们要准确描述向量,需要首先确定一组基,然后给出在基所在的各个直线上的投影值为了便于求坐标,我们希望这组基向量模长为1。因为向量的内积运算,当模长为1时,内积表示可以直接表示投影我们还需要这组基是线性无关的,我们一般用正交基,非正交基也可以,但是正交基具有更好的性质
1.3 基变换的矩阵表示
举例
对向量(3,2)(3,2)(3,2)这个点,在(12,12),和(−12,12)(\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}}),和(-\frac{1}{\sqrt{2}},\frac{1}{\sqrt{2}})(21,21),和(−21,21)这组基下的坐标是多少?
将向量(3,2)分别与之内积,得到(52,−12)(\frac{5}{\sqrt{2}},-\frac{1}{\sqrt{2}})(25,−21)这个新坐标
用矩阵相乘的简介形式进行表示
(1212−1215)(32)=(52−12)\begin{pmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\-\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{5}} \end{pmatrix} \begin{pmatrix}3 \\ 2 \end{pmatrix} = \begin{pmatrix}\frac{5}{\sqrt{2}} \\ \frac{-1}{\sqrt{2}} \end{pmatrix}(21−212151)(32)=(252−1)
左边矩阵两行分别是两个基,乘以原向量,其结果刚好为新基的坐标。
推广一下,如果我们有m个二维向量,只要将二维向量按排列排成一个两行m列矩阵,然后用"基矩阵"乘以这个矩阵就可以获得所有这些向量在新基下的值。
例如数据点(1,1),(2,2),(3,3)(1,1),(2,2),(3,3)(1,1),(2,2),(3,3)
(1212−1215)(123123)=(224262000)\begin{pmatrix}\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\-\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{5}} \end{pmatrix} \begin{pmatrix}1 ~~2 ~~3\\ 1 ~~ 2 ~~ 3 \end{pmatrix} = \begin{pmatrix}\frac{2}{\sqrt{2}} ~~ \frac{4}{\sqrt{2}} ~~ \frac{6}{\sqrt{2}} \\ 0 ~~0 ~~0 \end{pmatrix}(21−212151)(123123)=(222426000)
将其写成通用的表示形式
(p1p2…pR)(a1a2…aM)=(p1a1p1a2⋯p1aMp2a1p2a2⋯p2aM⋮⋮⋮pRa1pRa2⋯pRaM)\begin{pmatrix} p_1 \\ p_2\\ \dots \\ p_R \end{pmatrix}\begin{pmatrix} a_1 ~~ a_2 ~~ \dots ~~ a_M \end{pmatrix} = \begin{pmatrix}p_1a_1 ~~ p_1a_2 \cdots p_1a_M \\ p_2a_1 ~~ p_2a_2 \cdots ~~ p_2a_M \\ \vdots ~~ \vdots ~~\vdots \\ p_Ra_1 ~~ p_Ra_2 \cdots p_Ra_M \\ \end{pmatrix}⎝⎜⎜⎛p1p2…pR⎠⎟⎟⎞(a1a2…aM)=⎝⎜⎜⎜⎛p1a1p1a2⋯p1aMp2a1p2a2⋯p2aM⋮⋮⋮pRa1pRa2⋯pRaM⎠⎟⎟⎟⎞
pip_ipi是一个行向量,表示第iii个基,aja_jaj表示一个列向量,表示第jjj个原始数据记录
两个矩阵相乘的意义将右边矩阵中每一列向量aia_iai变换到左边矩阵中以每一行行向量为基所表示的空间中去
最大可分性
上面我们讨论了选择不同的基可以对同样一组数据给出不同的表示,若是基的数量少于向量本身的维数,则可以达到降维的效果
当前关键的问题:如何选择基才是最优的?或者如果说我们有一组N维向量,现在要将其降到k维(k≤N)(k \leq N)(k≤N),我们如何选择k个基才能最大程度保留原有的信息?
一种直观的看法是:希望投影后的投影值尽可能分散,如果重叠就会有样本消失。当然也可以从熵的角度进行理解,熵越大所含信息越多
2.1 方差
方差可用来描述数值的分散程度。
Var(α)=1m∑i=1m(ai−μ)2Var(\alpha) = \frac{1}{m}\sum_{i=1}^{m}(a_i - \mu)^2Var(α)=m1i=1∑m(ai−μ)2
为了方便计算,我们会将数据中心化,即变量的平均值为000。因此方差可以直接用每个元素的平方和除以元素个数表示
Var(a)=1m∑i=1mai2Var(a) = \frac{1}{m}\sum_{i=1}^m a_i^2Var(a)=m1i=1∑mai2
当样本数过多的时候,计算方差无需在意是mmm还是m−1m-1m−1,
为什么样本方差(sample variance)的分母是 m-1?
上面的问题被形式化表述为:寻找一个一维基,使得所有数据变换为这个基上的坐标表示后,方差值最大
2.2 协方差
如何通俗易懂地解释「协方差」与「相关系数」的概念? - GRAYLAMB的回答 - 知乎
以为空间中我们可以用方差表示数据的分散程度。对于高维数据,我们用协方差进行约束,协方差可以表示两个变量的相关性。
为了让两个变量尽可能表示更多的原始信息,我们希望它们之间不存在线性相关性,因为相关性意味着两个变量不完全独立,存在着重复信息
协方差公式为:
Cov(a,b)=1m−1∑i=1m(ai−μa)(bi−μb)Cov(a,b) = \frac{1}{m-1}\sum_{i=1}^m(a_i - \mu_a)(b_i - \mu_b)Cov(a,b)=m−11i=1∑m(ai−μa)(bi−μb)
由于均值为0,所以协方差公式写为以下
Cov(a,b)=1m−1∑i=1maibiCov(a,b) = \frac{1}{m-1}\sum_{i=1}^ma_ib_iCov(a,b)=m−11i=1∑maibi
样本数较大时,不必在意为mmm还是m−1m-1m−1
协方差为0时,表示两个变量完全独立.
为了让协方差为0,我们选择第二个基时只能与第一个基正交的方向上进行选择,因此最终选择的方向一定是正交的。
至此,降维问题的优化目标:
将一组N维向量将为K维,其目标时选择K个单位正交基,使得原始数据变换到这组基上后,各变量两两间协方差为0,而变量方差尽可能大(在正交的约束下,最大的K个方差)
2.3 协方差矩阵
从数学的角度来给出优化目标
最终达到的目的与变量内方差及变量间协方差有密切关系
我们希望能将两者统一表示,两者均可以表示为内积的形式,而内积又与矩阵相乘密切相关。
假设a、b两个变量,那么我们将它们按行组成矩阵X:
X=(a1a2⋯amb1b2⋯bm)X = \begin{pmatrix} a_1 ~~ a_2 ~~\cdots~ a_m \\ b_1 ~~ b_2 ~~\cdots~ b_m \end{pmatrix}X=(a1a2⋯amb1b2⋯bm)
然后:
1mXXT=(1m∑i=1mai21m∑i=1maibi1m∑i=1maibi1m∑i=1mbi2)=(Cov(a,a)Conv(a,b)Cov(a,b)Conv(b,b))\frac{1}{m}XX^T = \begin{pmatrix} \frac{1}{m}\sum_{i=1}^m a_i^2 ~~ \frac{1}{m}\sum_{i=1}^m a_ib_i \\ \frac{1}{m}\sum_{i=1}^m a_ib_i ~~ \frac{1}{m}\sum_{i=1}^m b_i^2 \end{pmatrix}=\begin{pmatrix} Cov(a,a) ~~ Conv(a,b) \\ Cov(a,b) ~~ Conv(b,b) \end{pmatrix}m1XXT=(m1∑i=1mai2m1∑i=1maibim1∑i=1maibim1∑i=1mbi2)=(Cov(a,a)Conv(a,b)Cov(a,b)Conv(b,b))
这个矩阵对角线的分别是变量的方差,而其他元素是aaa和bbb的协方差。两者被统一到一个矩阵中。
我们将其推广到一般情况:
设我们有mmm个nnn维数据记录,将其排列成Xn,mX_{n,m}Xn,m,设C=1mXXTC = \frac{1}{m}XX^TC=m1XXT,则CCC是一个对称矩阵,其对角线分别对应各个变量的方差,而第iii行jjj列和jjj行iii列元素相同,表示iii和jjj两个变量的协方差
2.4 矩阵对角化
根据我们的优化条件,我们需要将除对角线外的其他元素化为0,并且在对角线上将元素按大小从上到下排列(变量方差尽可能大),这就是我们的优化目的。
原矩阵与基变换后矩阵协方差矩阵的关系
原始数据矩阵XXX,其对应的协方差矩阵为CCC,而P是一组基按行组成的矩阵,设Y=PXY = PXY=PX,则YYY为XXX对PPP做基变换后的数据。设YYY的协方差矩阵为DDD,推导以下DDD与CCC的关系
D=1mYYT=1m(PX)(PX)T=1mPXXTPT=P(1mXXT)PT=PCPTD = \frac{1}{m}YY^T \\ = \frac{1}{m}(PX)(PX)^T \\ = \frac{1}{m}PXX^TP^T \\ = P(\frac{1}{m}XX^T)P^T \\ = PCP^TD=m1YYT=m1(PX)(PX)T=m1PXXTPT=P(m1XXT)PT=PCPT
故优化目标变成:寻找一个矩阵PPP,满足PCPTPCP^TPCPT是一个对角矩阵,并且对角元素按从大到小依次排列,那么PPP的前KKK行就是要寻找的基,用PPP的前KKK行组成的矩阵乘以XXX就使得XXX从NNN维降到了KKK维并满足上述优化条件
我们离PCA仅一步之遥,需完成对角化
由上文知道,协方差矩阵CCC是一个是对称矩阵,在线性代数中实对称矩阵有非常好的性质
实对称矩阵不同特征值对应的特征向量必然正交设特征向量λ\lambdaλ 重数为rrr,则必然存在rrr个线性无关的特征向量对应于λ\lambdaλ,因此我们可以将这rrr个特征向量单位正交化
由此知道,一个nnn行nnn列的实对称矩阵一定可以找到nnn个单位正交特征向量,设这n个特征向量为e1,e2,...,ene_1,e_2,...,e_ne1,e2,...,en,我们将其按列组成矩阵:E=(e1,e2,...,en)E=(e_1,e_2,...,e_n)E=(e1,e2,...,en)
则对协方差矩阵CCC有如下结论
其中⋀\bigwedge⋀为对角矩阵,其对角元素为各特征向量对应的特征值(可能有重复)
到这里,我们已经找到了需要的矩阵P = E^T
PPP是协方差矩阵的特征向量单位话后按行排列出的矩阵,其中每一行都是CCC的一个特征向量。
如果设PPP按照⋀\bigwedge⋀中特征值的从大到小,将特征向量从上到下排列,则用PPP的前KKK行组成的矩阵乘以原始数据矩阵XXX,就得到了我们需要的降维后的数据矩阵YYY
2.5 补充
(1) 拉格朗日乘子法
在叙述求协方差矩阵对角化时,我们给出希望变化后的变量有:变量间协方差为000且变量内方差尽可能大
样本点xix_ixi在基www下的坐标为(xi,w)=xiTw(x_i,w) = x_i^Tw(xi,w)=xiTw,于是我们有方差
D(x)=1m∑i=1m(xiTw)2=1m∑i=1m(xiTw)T(xiTw)=1m∑i=1mwTxixiTw=wT(1m∑i=1mxixiT)wD(x) = \frac{1}{m}\sum_{i=1}^{m} (x_i^Tw)^2 \\ = \frac{1}{m}\sum_{i=1}^m(x_i^Tw)^T(x_i^Tw) \\ = \frac{1}{m}\sum_{i=1}^mw^Tx_ix_i^Tw \\ = w^T(\frac{1}{m}\sum_{i=1}^{m}x_ix_i^T)wD(x)=m1i=1∑m(xiTw)2=m1i=1∑m(xiTw)T(xiTw)=m1i=1∑mwTxixiTw=wT(m1i=1∑mxixiT)w
1m∑i=1mxixiT\frac{1}{m}\sum_{i=1}^{m}x_ix_i^Tm1∑i=1mxixiT为原样本的协方差,我们另这个矩阵为⋀\bigwedge⋀,于是有
然后构造拉格朗日函数:
L(w)=wT⋀w+λ(1−wTw)L(w) = w^T\bigwedge w+\lambda(1-w^Tw)L(w)=wT⋀w+λ(1−wTw)
对www求导
⋀w=λw\bigwedge w = \lambda w⋀w=λw
此时我们的方差为:
D(x)=wT⋀w=λwTw=λD(x) = w^T\bigwedge w = \lambda w^Tw = \lambdaD(x)=wT⋀w=λwTw=λ
于是我们发现,xxx投影后的方差就是协方差矩阵的特征值。我们要找到最大方差也就是协方差矩阵最大的特征值,最佳投影方向就是最大特征值所对应的特征向量,次佳就是第二大特征值对应的特征向量,以此类推。
至此完成基于最大可分性的PCA数学证明
(2) 最近重构性
上述为基于最大可分性的思想,通过一条直线使得样本点投影到该直线上的防擦好最大
除此之外,我们还可将其转换为线性回归问题,其目标是求解一个线性函数使得对应直线能够更好地拟合样本点集合。这使得我们的优化目标从方差最大转化为方差最小,因为映射距离越短,丢失的信息也会越小。区别于最大可分性,这是从最近重构性的角度进行论证
3 求解步骤
总结以下PCA的算法步骤
设有m条n维数据
将原始数据按列组成n行m列矩阵X将X的每一行进行零均值化,即减去这一行的均值求出协方差矩阵C=1mXXTC = \frac{1}{m}XX^TC=m1XXT求出协方差矩阵的特征值及对应的特征向量将特征向量按对应特征值大小从上到下按行排列成矩阵,取前k行组成矩阵PY = PX即为降维到k维后的数据
4 性质
缓解维度灾难:PCA 算法通过舍去一部分信息之后能使得样本的采样密度增大(因为维数降低了),这是缓解维度灾难的重要手段;降噪:当数据受到噪声影响时,最小特征值对应的特征向量往往与噪声有关,将它们舍弃能在一定程度上起到降噪的效果;过拟合:PCA 保留了主要信息,但这个主要信息只是针对训练集的,而且这个主要信息未必是重要信息。有可能舍弃了一些看似无用的信息,但是这些看似无用的信息恰好是重要信息,只是在训练集上没有很大的表现,所以 PCA 也可能加剧了过拟合;特征独立:PCA 不仅将数据压缩到低维,它也使得降维之后的数据各特征相互独立;5 细节
5.1 零均值化
当对训练集进行 PCA 降维时,也需要对验证集、测试集执行同样的降维。而对验证集、测试集执行零均值化操作时,均值必须从训练集计算而来,不能使用验证集或者测试集的中心向量。
原因
因为我们的训练集时可观测到的数据,测试集不可观测所以不会知道其均值,而验证集再大部分情况下是在处理完数据后再从训练集中分离出来,一般不会单独处理。如果真的是单独处理了,不能独自求均值的原因是和测试集一样。
另外我们也需要保证一致性,我们拿训练集训练出来的模型用来预测测试集的前提假设就是两者是独立同分布的,如果不能保证一致性的话,会出现 Variance Shift 的问题。
5.2 与 SVD的对比
特征值和特征向量是针对方阵才有的,而对任意形状的矩阵都可以做奇异值分解
PCA:方阵的特征值分解,对于一个方阵AAA,从可以写成:A=Q⋀Q−1A = Q \bigwedge Q^{-1}A=Q⋀Q−1
QQQ是这个矩阵A的特征向量组成的矩阵
⋀\bigwedge⋀ 是一个对角矩阵,每一个对角线元素都是一个特征值,里面的特征值是由小排列的,这些特征值所对应的特征向量就是描述这个矩阵变化方向(从主要的变化到次要的变化排列)。也就是说矩阵 A 的信息可以由其特征值和特征向量表示。
SVD:矩阵的奇异值分解其实就是对于矩阵AAA的协方差矩阵ATAA^TAATA和AATAA^TAAT做特征值分解推导出来的:
Am,n=Um,m⋀m,nVn,nT≈Um,k⋀k,kVk,nTA_{m,n} = U_{m,m}\bigwedge _{m,n} V^T_{n,n} \approx U_{m,k}\bigwedge_{k,k}V_{k,n}^TAm,n=Um,mm,n⋀Vn,nT≈Um,kk,k⋀Vk,nT
而实际上 Sklearn 的 PCA 就是用 SVD 进行求解的,原因有以下几点:
当样本维度很高时,协方差矩阵计算太慢;方针特征值分解计算效率不高;SVD出了特征值分解这种求解方式外,还有更高效更准确的迭代求解方式,避免了ATAA^TAATA的计算;其实 PCA 与 SVD 的右奇异向量的压缩效果相同。
如果觉得《降维--PCA学习笔记》对你有帮助,请点赞、收藏,并留下你的观点哦!