1、第四章统计分类器及其学习第四章统计分类器及其学习第四讲第四讲 Principal Component Analysis Fisher 线性判别准则问题的提出在建立识别系统时，抽取的原始特征往往比较多，特征的维数比较大，这会给识别器的训练带来很大的困难，因此希望能够采用某种方法降低特征的维数。这些方法可以称作成分分析的方法。1.主成分分析；寻找最小均方意义下，最能代表原始数据的投影方法2.多重判别分析；寻找最小均方意义下，最能分开各类数据的投影方法人脸识别举例1 主成分分析（PCA，Principal Component Analysis）PCA是一种最常用的线性成分分析方法；PCA的主要思想是
2、寻找到数据的主轴方向，由主轴构成一个新的坐标系（维数可以比原维数低），然后数据由原坐标系向新的坐标系投影。PCA的其它名称：离散K-L变换，Hotelling变换；问题：有n个d维样本，x1,x2,.xn,如何仅用一个样本x0代表这些样本，使误差准则函数最小？20001()nkkJxxx011nkknxmx201()()nkkxmxm22001112()()nnntkkkkkxmxmxmxm22001112()()nnntkkkkkxmxmxmxm0不依赖于不依赖于x0 x0=m时取得最小值时取得最小值样本均值是样本数据集的零维表达。样本均值是样本数据集的零维表达。将样本数据集的空间分布，压缩
3、为一个均值点。将样本数据集的空间分布，压缩为一个均值点。简单，但简单，但不能反映不能反映样本间的样本间的差异差异零维表达改为零维表达改为“一维一维”表达，将数据集空间，表达，将数据集空间，压缩为一条过均值点的线压缩为一条过均值点的线。每个样本在直线上存在不同的投影，可以反映样本间的差异每个样本在直线上存在不同的投影，可以反映样本间的差异axmee为直线的单位向量为直线的单位向量a为直线上的点到为直线上的点到m的距离的距离kx2111(,)()nnkkkJ aaaemex201()nkkJmm x0维平方误差1维平方误差kameka221111(,)()()nnnkkkkkkJ aaaaemex
4、exm2221112()nnntkkkkkkkaaee xmxm111(,)22()0tnkkkJ aaaaee xm()tkka e xmkxm只需把向量只需把向量 向过向过 的直线的直线垂直投影就能得到最小方差垂直投影就能得到最小方差kx如何找到直线的最优方向？如何找到直线的最优方向？m1()=1 tJe Seee最小化最大化，约束条件为：221111(,)()()nnnkkkkkkJ aaaaemexexm222111(2)nnnkkkkkkktaae xxmme1()tkka e xm2211211()2knnnkkkkkJaaexm2121()ntnkkkkxme xm211()()
5、nnktkkkkte xm xm exm21nktkxmeSe1()()ntkkkSxm xm协方差矩阵的协方差矩阵的n-1倍：散布矩阵倍：散布矩阵=1 te See最大化，约束条件为：Lagrange乘子法乘子法 ttueeSee 2=02uSeee See散布矩阵散布矩阵散布矩阵的散布矩阵的特征值特征值 tte Seee为了最大化为了最大化 选取散布矩阵最大特征值选取散布矩阵最大特征值选取选取 对应的特征向量作为投影直线对应的特征向量作为投影直线 的方向的方向te Semaxmaxe2,选取选取 对应的特征向量作为直线方向对应的特征向量作为直线方向PCA算法从0维，1维到d 维维有n个d维
6、样本，x1,x2,.xn,011nkknxmx零维表达：零维表达：仅用一个样本仅用一个样本x0代表这些样本，使误差最小？代表这些样本，使误差最小？一维表达：一维表达：将这些样本，映射到过将这些样本，映射到过m的一条直线上使误差最小？的一条直线上使误差最小？简单，但不能反简单，但不能反映样本间的差异映样本间的差异1,选取散布矩阵选取散布矩阵 最大特征值最大特征值maxmax1()()ntkkkSxm xmaxme3,将样本向直线做垂直投影将样本向直线做垂直投影d 维表达：维表达：将这些样本，映射到以将这些样本，映射到以m为原点的为原点的d维空间中维空间中，使误使误差准则函数最小？差准则函数最小？
7、PCA算法d 维表达：1,nxx1,tdxxxm1diiiaexm ie1,0,tijijije etiia exmddx1diiiaexm有样本集合，其中，以样本均值为坐标原点建立新的坐标系，则有：，其中为标准正交向量基：因此有：将特征维数降低到，则有对的近似：1211dikdikiiiinkaaee误差平方和准则函数：。211dikiindkae 21nkkkJexx121dikindka11ndtkkikiditexmxm ePCA算法d 维表达：1211dikdikiiiinkaaee211dikiindkae 21nkkkJexx121dikindka11ndtkkikiditexm
8、xm e11dittikkidnkexmxm e1dttidiie Se散布矩阵散布矩阵()=1 J ee最小化，约束条件为：使用拉格朗日乘数法：11dTTiiiiii dJee See e 11dTTiiiiii dJee See e 220iiiiJeSeeeiiiSeeiSieS为的特征值，为的特征矢量。1dTiii dJee Se J eSdd要使最小，只需将 的特征值由大到小排序，选择最大的前个特征值对应的特征向量构成一个新的维坐标系，将样本向新的坐标系的各个轴上投影，计算出新的特征矢量 11,TTddxxaaTiia exm其中1dTiiii de e1dii dPCA算法1.利用
9、训练样本集合计算样本的均值m和散布矩阵S；2.计算S的特征值，并由大到小排序；3.选择前d个特征值对应的特征矢量作成一个变换矩阵E=e1,e2,ed；4.训练和识别时，每一个输入的d维特征矢量x可以转换为d维的新特征矢量y：y=Et(x-m)。PCA的讨论 由于S是实对称阵，因此特征矢量是正交的；将数据向新的坐标轴投影之后，特征之间是不相关的；特征值描述了变换后各维特征的重要性，特征值为0的各维特征为冗余特征，可以去掉。例 有两类问题的训练样本：将特征由2维压缩为1维。1:5,4,4,5,5,6,6,5tttt 2:5,4,4,5,5,6,6,5ttttx1x2e1e2特征人脸 e1 e2 e
10、3 e4 e5 e6 e7 e8PCA重构重构原图像原图像 d=1 5 10 20 50 100 2002 多重判别分析（MDA,Multiple Discriminant Analysis）x1x2e1e2MDA与PCA PCA将所有的样本作为一个整体对待，寻找一个均方误差最小意义下的最优线性映射，而没有考虑样本的类别属性，它所忽略的投影方向有可能恰恰包含了重要的可分性信息；MDA则是在可分性最大意义下的最优线性映射，充分保留了样本的类别可分性信息；MDA还被称为：FDA(Fisher Discriminant Analysis)或LDA(Linear Discriminant Analys
11、is)。Fisher 线性判别准则如何选择直线方向如何选择直线方向W，使样本可分性最好？，使样本可分性最好？样本点样本点 在在W方向上的投影方向上的投影xWytywxx1m2m两类样本均值两类样本均值M1,M2投影之差：投影之差：1212()tmmw mm12mm第第i类投影的内类散布：类投影的内类散布：22()iiiy Ysy m总体内类散布：总体内类散布：2212ss可分性准则函数：可分性准则函数：（Fisher线性判别准则）线性判别准则）122212()mmJssw二分类问题二分类问题 可分性准则函数的构造可分性准则函数的构造ty w x21itwiiiDxSxmxm1212tBSmmm
12、mFisher线性判别准则：线性判别准则：122212()ttBwmmJsswwwwS wS22()()()iittttiiiiiDDsSxxwx wmw x mx mww w样本样本x在在w方向上的投影：方向上的投影：类间散布矩阵：类间散布矩阵：总类内散布矩阵：总类内散布矩阵：22121w2+tttssSSSww wwww212121212()()()ttttBtmmw mw mw mmmmwwwS广义瑞利商广义瑞利商准则函数的准则函数的广义瑞利商广义瑞利商形式形式瑞利商瑞利商与与广义瑞利商广义瑞利商设设A是是n阶实对称矩阵，阶实对称矩阵，称称R(x)为为A的的瑞利商瑞利商 ()0ttRxx
13、xxxxA，nxR设设A，B是是n阶实对称矩阵，阶实对称矩阵，且且B正定，正定，称称R(x)为为A相对于相对于B的的广义瑞利商广义瑞利商 ()0ttRxxxxxAxB，R(x)具有以下特性具有以下特性 1，R(x)是是x的连续函数。的连续函数。0()(),0RRxx3，时，时，R(x)为一常数为一常数,4，R(x)的最大，最小值存在，能在单位球面的最大，最小值存在，能在单位球面 上找到上找到nxR2，R(x)是是x的的0次齐次函数：次齐次函数：00(),0Lxxx,1nS x xRx瑞利商瑞利商特性特性()ttRAxxxxxR(x)的最大、最小值为：的最大、最小值为：1max(),min()n
14、RRxx12n12nAppp设实对称矩 的特征值为：，对应标准正交单位特征向量为，,X展开为展开为pi的的线性组合线性组合iiiAppip 是正交单位向量广义瑞利商广义瑞利商特性特性()ttRxxxxABx广义特征向量广义特征向量()ttRxxxxBAx2()+2tdRRdBBxxxxxAx2-()=0tRdRdxxxxx BxBA000=()Rxx BxAFisher线性判别准则：线性判别准则：122212()ttBwmmJsswwwwS wS21itwiiiDxSxmxm1212tBSmmmm类间散布矩阵：类间散布矩阵：总类内散布矩阵：总类内散布矩阵：最大化最大化 必须满足：必须满足：=B
15、wS wS w()J w 为：为：相对于相对于 的特征值，的特征值，为对应的特征向量为对应的特征向量wBSwS 当当 非奇异时非奇异时 1=BwSSwwwSFDA算法1.利用训练样本集合计算类内散布矩阵Sw和类间散度矩阵SB；2.计算Sw-1SB的特征值；3.选择非0的c-1个特征值对应的特征矢量作成一个变换矩阵W=w1,w2,wc-1；4.训练和识别时，每一个输入的d维特征矢量x可以转换为c-1维的新特征矢量y：y=Wtx。3类问题FDAFDA的讨论 经FDA变换后，新的坐标系不是一个正交坐标系；新的坐标维数最多为c-1，c为类别数；只有当样本数足够多时，才能够保证类内散度矩阵Sw为非奇异矩
16、阵（存在逆阵），而样本数少时Sw可能是奇异矩阵。成分分析的其它问题 独立成分分析(ICA,Independent Component Analysis)：PCA去除掉的是特征之间的相关性，但不相关不等于相互独立，独立是更强的要求。ICA试图使特征之间相互独立。多维尺度变换(MDS,Multidimensional Scaling)典型相关分析(CCA,Canonical Correlation Analysis)偏最小二乘(PLS,Partial Least Square)10,1,9,0,10,1,11,0,0,9,1,10,0,11,1,10tttttttt5,5tm25.5252525.5S现有下列训练样本，请用PCA算法将2维特征降为1维，并画出训练样本和投影主轴以及投影后的样本点。样本：均值：，协方差矩阵：See112225.5252525.5eeee1225.5252525.5ee0计算协方差矩阵的特征值和特征向量：25.52502525.5120.5,50.511,1te21,1te带入线性方程组：，11212 e21212 e归一化为：，-2024681012-2024681012
