1、PCA
主成分分析(PCA) 是降维中非常常用的一种手段,比如汽车有n个属性(或者说特征,那么维度就是n),而其中两个属性xi,xj分别表示汽车每小时行驶多少公里和每小时行驶多少英里,实际上这两个特征可以认为是一样的或者说是线性相关的,那么可以合并成一个,此时数据的维度应该降为n−1。那么如何来自动识别和删除这一冗余呢,使用PCA。
关于向量A,B的内积,A⋅B=a1b1+a2b2,...,anbn,考虑几何解释的话那就是A⋅B=∣A∣∣B∣cosα,如果∣B∣=1那么A⋅B=∣A∣cosα就表示为向量A向B所在直线投影的矢量长度。知道这点很重要,在后面会用到,向量xi在基向量wjT上的投影为wjTxi,既然提到了基向量,那么下面说一下基的概念。
首先说一下基的概念,考虑向量a=(3,4)T,如下图所示,
基的定义:给定一个空间向量V,V的一组基B是指V里面的可线性生成V的一个线性无关的子集,B的元素称为基向量。需要注意的是基向量线性无关(任意两个基向量互相垂直,即内积为0此时是不是也叫做正交了呢)。
那么可以很自然的想到向量a=(3,4)T可以使用基(0,1)T和(1,0)T线性表示为a=4(0,1)T+3(1,0)T。那么基(0,1)T和(1,0)T为二维空间的一组基,任意向量都可以有这个两个即线性表示。
如果我们使用另外一组基(21,21)T,(21,−21)T来表示向量a=(3,4)T,那么就会得到不一样的新坐标。
(1/21/21/2−1/2)(34)=(7/2−1/2)
这种操作我们称作为基变换,写成定义的样子如下
基变换:数据与一个基做内积运算,结果作为第一个新的左边分量,然后与第二个基做内积运算,结果作为第二个新坐标的分量,依次类推,公式化如下
⎝⎜⎜⎜⎛p1p2⋮pd′⎠⎟⎟⎟⎞(a1,a2,...,aM)=⎝⎜⎜⎜⎛p1a1p2a1⋮pd′a1p1a2p2a2⋮pd′a2……⋱…p1aMp2aM⋮pd′aM⎠⎟⎟⎟⎞
上式中,ai=(ai1,ai2,...,aid)T原本是d维的,最后得到的是d′维的(不是说a成了pd′维,而是样本从原来的(a1,a2,...,aM)变成了上式中的新矩阵,对应的仍然是M个样本即列向量,只是维度成了pd′了)。
再回来看PCA,不是说PCA用来降维吗,将d维度,降到d′ 维。数据是(a1,a2,...,aM),而我们要做的是求出d′个基向量p,相乘(即基变换后)得到d′×M维度的矩阵,即每个数据ai的维度变成了d′
任意pi,pj是相互正交的,我们进行标准化,即∣pi∣=1,那么得到的就是正交单位阵了。
补充:两个矩阵相乘的意义是将右边那个矩阵的每一列的列向量变换到左边矩阵的每一行向量为基所表示的空间中去。
下面考虑如何选择这些基向量
PCA的目标是尽量保留最多的原始信息(任意特征都尽可能表示更多的信息),一种直观的做法就是将样本投影到新空间中,使得在该空间中方差最大。
补充:很多地方都说是样本方差最大,个人认为应该指的是特征的方差最大,如果是样本的方差的话,投影变换后样本的方差实际是个矩阵,矩阵最大似乎没听过。
为了便于理解,多说两句:
(1)、特征的方差表示样本关于该特征的分散程度,所以要求数据在该特征上够分散,那么该特征的方差尽可能大。
(2)、两个特征的协方差表示这两个特征的相关程度,PCA既然是降维,线性相关的特征我们就不要了。也就是说我们选择的基向量需要两两正交(此时任意两个特征的协方差为0,即线性无关),通俗点说是因为一个基向量决定一个特征不是吗,比如上面的式子d′个基向量不是决定了最后的d′个特征。
(3)、如果仅仅选择方差最大的基,一旦选出来第一大方差所对应的基(变换后等于对应一个特征),那么第二个基实际上是非常接近于第一个基的那么就说明这两个特征的相关性较大了,但是为了让每个特征尽可能表示多的信息,所以希望任意两个基都是线性无关的。
那么我们总结一下:
寻找一个一维基,使得所有数据变换为这个基上的坐标表示后,方差值最大。
由于任意两个特征要求线性无关,即协方差为0,所以要求每个基都是相互正交的,基于此,我们再求方差第二大时所对应的基,以此类推下去。
由于协方差矩阵的对角元素为各个特征的方差(是去均值化了的方差,即xi=xi−m1i=1∑mxi),位置(i,j),i̸=j则表示特征的协方差,根据上面所说的,要求协方差为0,即协方差矩阵中除了对角线元素外,其他位置的值要求均为0。
所以基组成的矩阵WT是单位正交阵,记数据集X,变换后的矩阵A=WTX的协方差矩阵AAT的对角线以外的元素均为0,而对角线上的元素为各个特征的方差。
AAT=WTXXTW,由于XXT是对称阵,所以肯定存在单位正交阵W使得WTXXTW=Λ,其中Λ除对角线上的元素外,其他位置元素的值均为0的方阵。这部分参考线代的书的矩阵对角化部分内容即可,实际上对角线上的值即为方差,也是XXTw=λw的特征值λ,对应的w为特征向量。这个操作被称作特征分解(后面会介绍,建议看一下线代的这部分内容,比什么博客都说的清楚)。
然后将对角线上的元素由大到小排列,取我们需要的前d′个所对应的特征向量即可.这d′个向量就是主成分。
下面给出PCA算法流程和一个具体的例子
PCA算法流程
输入:样本集D={x1,x2,...,xm}
输出:降维后的样本集D′
第一步: 对所有样本集进行去中心化操作 xi=xi−m1i=1∑mxi;
第二步:计算样本的协方差矩阵XXT;
第三步:对协方差矩阵XXT进行特征值分解,得到特征值集合后并由大到小排序{λ1,λ2,...,λm}
第四步:取前K大的特征值对应的特征向量WT=(w1,w2,...,wd′)T
第五步:对样本集D进行降维转换,即新的样本zi=WTxi。
补充:有没有指定d′,而是换种方式,指定一个降维到的主成分比重阈值t,则K可以通过下式计算得到
d′=argd′mini=1∑dλii=1∑d′λi≥t
2、SVD
进行特征分解需要方阵,而进行奇异值分解则不需要了,下面给出奇异值分解的定义
对于任意实矩阵A∈Rm×n,都可以分解为 以下形式:
A=UΣVT
其中,U为m阶方阵,是满足UTU=I的酉矩阵(正交矩阵往复数上的推广);V为n阶方阵,是满足VTV=I的酉矩阵。Σ是m×n阶矩阵,除主对角线元素外,其他位置元素均为0,且主对角线元素值由大到小排列。
其中U中的列向量ui称为左奇异向量,V中的vi称为右奇异向量,Σ中的对角线上的值σi称为奇异值。
那么这几个参数怎么求呢?
方便起见,先求方阵V中的向量vi,讲PCA的时候说了数据集组成的矩阵为A,求AATui=λiui,这里的ui即为奇异值分解式子U中的ui。
再求方阵V中的向量vi,ATAvi=λivi,这里的vi即为奇异值分解式子V中的vi。
最后求Σ中对角线元素σi,AV=UΣVTV=>AV=UΣ=>Avi=uiσi=>σi=Avi/ui
下面做个简单的证明:
AT=VΣTUT=>ATA=VΣTUTUΣVT=VΣTΣVT=VΣ2VT
注意:ΣTΣ=Σ2为n阶方阵,对角线上的值,为ΣT对角线位置的值的平方,将其看做Λ。ATA为对称阵,将其看做C,那么C=VΛVT这不就是特征分解的公式吗,恰好说明了vi为特征向量,同时也发现了λi=σi2。
所以分解可以这样做
- 求AATui=λiui,这里的ui即为奇异值分解式子U中的ui,
- 求ATAvi=λivi,这里的vi即为奇异值分解式子V中的vi,同时得到σi=λi。
实际上,往往只保留前K大的奇异值,用这钱K大的元素就足够来描述这个矩阵了,有 A=Um×KΣK×KVK×nT。这个性质非常重要,常常用来做降维,去噪,推荐算法。