特征提取——主成分分析(PCA)
/5/23
引言：特征提取是机器学习中很经常使用数据处理方式，通常都出如今实际搭建模型以前，以达到特征空间维度的变化(常见是降维操做)。特征提取是经过适当变换把已有样本的D个特征转换成d(
(
<
D
)个新特征。这样作的主要目的有：web
下降特征空间的维度，使后续的分类器设计在计算上更容易实现；
消除原有特征之间的相关度，减小数据信息的冗余，更有利于分类。
前面提到特征提取就是经过适当变换将特征从现有的特征空间转换到新的空间。因此特征提取的关键任务在于寻找适当变换，最常采用的变换方法是线性变换，即若xϵRDx
ϵ
R
D是DD为原始特征，变换后的dd维新特征ξϵRdξ
ϵ
R
d为： 算法
ξ=WTxξ
=
W
T
x
(这是一个线性变换) (1)
其中，WW是D×dD
×
d维矩阵，称做变换阵。所谓特征提取，就是寻找一个合适的矩阵WW，使得原有样本通过式(1)的变换后，可以保留尽量多的原有信息。若是用类别可分性判据来做为衡量新特征的准则，这一原则能够用一个表达式来表示：机器学习
lW∗=argmaxJ(WTx){W}W
∗
=
a
r
g
m
a
x
J
(
W
T
x
)
{
W
}, 其中J(WTx)J
(
W
T
x
)即为基于类内类间距离的可分性判据。svg
本次咱们先介绍喜闻乐见的主成分分析法(PCA)。学习
主成分分析法(PCA)
PCA是很是经常使用的数据降维方法。它的基本思想是从一组特征中计算出一组按照重要性的大小从大到小依次排列的新特征，它们是原有特征的线性组合，而且新特征之间不相关, 咱们计算出原有特征在新特征上的映射值即为新的降维后的样本。也就是说PCA的目标是用一组正交向量来对原特征进行变换获得新特征，新特征是原有特征的线性组合。优化
数听说明，样本集为已经通过中心化后的数据，X={x1,x2,...,xn}X
=
{
x
1
,
x
2
,
.
.
.
,
x
n
}，其中xix
i为p维列向量，共有n个样本，知足∑ni=1xi=0∑
i
=
1
n
x
i
=
0。atom
用矩阵AA来表示一组正交列向量，而且为了归一化，令 aTiai=1a
i
T
a
i
=
1，spa
同时有aTiaj=0,i≠ja
i
T
a
j
=
0
,
i
≠
j。设计
若原样本有pp维特征，即原向量xi={xi1,xi2,...,xip}x
i
=
{
x
1
i
,
x
2
i
,
.
.
.
,
x
p
i
},则通过变换后获得新的样本向量 ξi=ATxiξ
i
=
A
T
x
iorm
展开即为ξij=aTjxi=∑pt=1ajtxitξ
j
i
=
a
j
T
x
i
=
∑
t
=
1
p
a
j
t
x
t
i 。 (2)
一. 推导矩阵AA的计算方法，即各向量aia
i的计算方法。
1. 计算a1a
1
咱们先考虑第一个新特征上的值ξi1=∑pj=1a1jxijξ
1
i
=
∑
j
=
1
p
a
1
j
x
j
i，这个式子表示的是将原向量xix
i投影到向量a1=[a11,a12,...,a1p]a
1
=
[
a
11
,
a
12
,
.
.
.
,
a
1
p
]上获得值ξi1ξ
1
i,即第一个特征值为原向量在第一个变换向量a1a
1上的投影值。
咱们的目标是使得样本集X={x1,x2,...,xn}X
=
{
x
1
,
x
2
,
.
.
.
,
x
n
}在向量a1a
1上的投影值ξ1={ξ11,ξ21,...,ξn1}ξ
1
=
{
ξ
1
1
,
ξ
1
2
,
.
.
.
,
ξ
1
n
}的方差最大，也就是当将样本集XX投影到向量a1a
1上后，不一样样本间的区分度最大，使得不一样样本在该向量上可分。
ξ1ξ
1的方差：
var(ξ1)=E(ξ21)−E(ξ1)2=E(aT1xxTa1)−E(aT1x)E(xTa1)=aT1∑a1v
a
r
(
ξ
1
)
=
E
(
ξ
1
2
)
−
E
(
ξ
1
)
2
=
E
(
a
1
T
x
x
T
a
1
)
−
E
(
a
1
T
x
)
E
(
x
T
a
1
)
=
a
1
T
∑
a
1
注：由于样本已经通过中心化，因此E(aT1x)=aT1E(x)=0E
(
a
1
T
x
)
=
a
1
T
E
(
x
)
=
0
其中∑∑表示样本集的协方差矩阵，∑=1nXXT∑
=
1
n
X
X
T。
如今咱们将问题变成了一个优化问题，即
{maxaT1∑a1s.t.aT1a1−1=0{
m
a
x
a
1
T
∑
a
1
s
.
t
.
a
1
T
a
1
−
1
=
0
这是一个带约束的极值问题，将其转换为拉格朗日对偶问题：
f(a1)=aT1∑a1−v1(aT1a1−1)f
(
a
1
)
=
a
1
T
∑
a
1
−
v
1
(
a
1
T
a
1
−
1
)
上式对a1a
1求偏导，获得：
∂f(a1)∂a1=(∑+∑T)a1−2v1a1=0∂
f
(
a
1
)
∂
a
1
=
(
∑
+
∑
T
)
a
1
−
2
v
1
a
1
=
0
⟹∑a1=v1a1⟹
∑
a
1
=
v
1
a
1
因此，a1a
1是协方差矩阵∑∑的特征向量，v1v
1为对应的特征值。
⟹v1ar(ξ1)=aT1v1a1=v1⟹
v
1
a
r
(
ξ
1
)
=
a
1
T
v
1
a
1
=
v
1
显然为使var(ξ1)v
a
r
(
ξ
1
)最大，咱们只须要选择v1v
1为协方差矩阵∑∑的最大特征值:
即对协方差矩阵∑∑的p个特征值排序，λ1≥λ2≥...≥λpλ
1
≥
λ
2
≥
.
.
.
≥
λ
p
有 v1=λ1v
1
=
λ
1,向量a1a
1为对应的特征向量。
如今a1a
1已知，则根据式(2)就能够获得各个原样本xx在a1a
1上的投影值，即对应的ξ1ξ
1。
2. 计算a2a
2
通常来说，咱们在进行降维时不会只保留一维特征，为了获得计算变换向量aia
i的通常规律，咱们计算a2a
2，根据a2a
2就可知道原向量在该向量上的投影，从而获得原向量在第二个主成分特征上的值ξ2ξ
2。
同理，为了使得样本集中全部原向量在第二个主成分上的值ξ2={ξ12,ξ22,...,ξ2n}ξ
2
=
{
ξ
2
1
,
ξ
2
2
,
.
.
.
,
ξ
n
2
}方差最大，便可分性最大。
ξ2ξ
2的方差：
var(ξ2)=aT2∑a2v
a
r
(
ξ
2
)
=
a
2
T
∑
a
2
转换为优化问题：
⎧⎩⎨⎪⎪maxaT1∑a1s.t.aT1a1−1=0aT2a1=0{
m
a
x
a
1
T
∑
a
1
s
.
t
.
a
1
T
a
1
−
1
=
0
a
2
T
a
1
=
0
转换为拉格朗日对偶问题：
f(a2)=aT2∑a2−v2(aT2a2−1)−βaT2a1f
(
a
2
)
=
a
2
T
∑
a
2
−
v
2
(
a
2
T
a
2
−
1
)
−
β
a
2
T
a
1
f(a2)f
(
a
2
)对a2a
2求偏导：
∂f(a2)∂a2=(∑+∑T)a2−2v2a2−βa1=0∂
f
(
a
2
)
∂
a
2
=
(
∑
+
∑
T
)
a
2
−
2
v
2
a
2
−
β
a
1
=
0
上式左乘
aT1a
1
T
⟹2aT1∑a2−2aT1v2a2−βaT1a1=0(∑=∑T)⟹
2
a
1
T
∑
a
2
−
2
a
1
T
v
2
a
2
−
β
a
1
T
a
1
=
0
(
∑
=
∑
T
)
取转置
⟹aT1∑a2=0,aT1a2=0⟹
a
1
T
∑
a
2
=
0
,
a
1
T
a
2
=
0
βaT1a1=0,aT1a1=1β
a
1
T
a
1
=
0
,
a
1
T
a
1
=
1
β=0β
=
0
因此，
∂f(a2)∂a2=0∂
f
(
a
2
)
∂
a
2
=
0
⟹∑a2=v2a2⟹
∑
a
2
=
v
2
a
2
⟹v2⟹
v
2
为协方差矩阵
∑∑
的特征值，而
a2a
2
为相应的特征向量。
且，
var(ξ2)=aT2v2a2=v2v
a
r
(
ξ
2
)
=
a
2
T
v
2
a
2
=
v
2
因此，为使var(ξ2)v
a
r
(
ξ
2
)最大，即便v2v
2最大便可。前面已提到，v2v
2为协方差矩阵的特征值,
对协方差矩阵∑∑的p个特征值排序，λ1≥λ2≥...≥λpλ
1
≥
λ
2
≥
.
.
.
≥
λ
p,已有 v1=λ1v
1
=
λ
1，因此选择v2=λ2v
2
=
λ
2即为最优解。
到这里，咱们彷佛已经摸索出了某种规律。能够从理论上证实，第k个主成分方向就是协方差矩阵∑∑的第k大的特征值λkλ
k对应的特征向量。
结论：协方差矩阵为p×pp
×
p维的二维矩阵，特征值很少于pp个，因此经过PCA方法，能够将原有的p维向量经过矩阵A映射到k(k≤p)k
(
k
≤
p
)维空间。矩阵A=[a1,a2,...,ak]A
=
[
a
1
,
a
2
,
.
.
.
,
a
k
],ai(i=1,2,...,k)a
i
(
i
=
1
,
2
,
.
.
.
,
k
)为p维列向量，且若将协方差矩阵∑∑的p个特征值排序，λ1≥λ2≥...≥λpλ
1
≥
λ
2
≥
.
.
.
≥
λ
p, aia
i为λiλ
i对应的特征向量。
二. PCA算法的实现流程
(假设数据未进行中心化)：
输入数据X={x1,x2,...,xn}p×n,nX
=
{
x
1
,
x
2
,
.
.
.
,
x
n
}
p
×
n
,
n个pp维的列向量。
1.数据中心化：μ=1n∑ni=1xi,xi=xi−μ,i=1,2,...,nμ
=
1
n
∑
i
=
1
n
x
i
,
x
i
=
x
i
−
μ
,
i
=
1
,
2
,
.
.
.
,
n
2.计算协方差矩阵∑=1nXXT,(X∑
=
1
n
X
X
T
,
(
X为中心化后的数据)，∑∑为p×pp
×
p维对称矩阵
3.对协方差矩阵∑∑进行特征值分解，获得特征值λ1≥λ2≥...≥λpλ
1
≥
λ
2
≥
.
.
.
≥
λ
p,选择前kk个特征值所对应的特征向量，构成投影矩阵A=[a1,a2,...,ak]A
=
[
a
1
,
a
2
,
.
.
.
,
a
k
],aia
i为pp维列向量
4.将原样本投影到新的特征空间，获得新的降维样本，X′=WTXX
′
=
W
T
X,X′X
′为p×np
×
n维矩阵。
三. 几点说明
1.如何选择k
使用降维算法咱们都是但愿可以将数据尽量降到低维的空间，这样便于后续的分类等算法的实现。可是为了保证数据的主要内容不会丢失，又不可降到过低的维度。若是取前k个主成分(一个特征向量aia
i即为一个主成分)，这k个主成分所表明的数据所有方差的比例为：
∑ki=1λi∑pi=1λi∑
i
=
1
k
λ
i
∑
i
=
1
p
λ
i
在实际经过程序选择k时，能够先设定好新特征所能表明的数据总方差的比例，好比80%80
%或者90%90
%，而后再选择知足条件的k值。通常来说，数据中的大部分信息主要集中前几个较少的主成分上。
下图为一次主成分分析所获得特征值的分布，能够看到前面几个特征值较大但衰减速度很快，而到后面的特征值基本都很小，衰减也很慢。有的方法推荐选择拐点来做为k值，好比下图中选择k=3。
2.重新的特征空间回到原空间
从向量ξξ回到原空间样本(中心化)，
x=A−1ξx
=
A
−
1
ξ
(3)
若回到最初为中心化的原样本，
x^=A−1ξ+μx
^
=
A
−
1
ξ
+
μ
(4)
只要k<
^就必定与原来的真实值存在偏差，但通常来说偏差很小。
3.主成分分析理解
最多见的主成分分析都是用来对数据降维，选择较少的主成分来表示数据，能够有效减小后续的工做量，节省计算资源。另外主成分分析也能够用来进行数据的降噪。再特征值中排列较靠后的主成分(或称次成分)每每是数据中的随机噪声。若是把ξξ中对应特征值很小的成分置0，再用式(3)或式(4)反变换回原空间，就实现了对原始数据的降噪处理。
写在最后：至此，主成分分析方法就已介绍完毕。从上面的介绍内容中，咱们能够发现，整个过程没有用到样本的类别信息。因此主成分分析是一种非监督算法，而对于分类问题，仅以方差大为目标彷佛并不必定老是利于后续的分类，因此就产生了另外一种经常使用的降维算法——K-L变换，它与PCA算法很相似，可是能够针对分类的目标进行特征提取，以后我会专门来介绍这种算法。
