统计模式识别b-参数估计-OK.pdf

1 1HMMHMM模型模型HMMHMM的基本思想的基本思想 MarkovMarkov链链 HMMHMM的概念的概念HMMHMM的基本算法的基本算法 前向后向算法前向后向算法 ViterbiViterbi算法算法 BaumBaum-WelchWelch算法算法HMMHMM的基本思想的基本思想MarkovMarkov链链 随机序列在任意时刻它所处的状态，且他在时随机序列在任意时刻它所处的状态，且他在时刻所处的状态为的概率，至于他在时刻的状态刻所处的状态为的概率，至于他在时刻的状态有关，而与时刻以前他所处的状态无关即有：有关，而与时刻以前他所处的状态无关即有：3 3讲义：模式识别第三章：统计模式识别(二)概率密度函数的参数估计概率密度函数的参数估计引言引言参数估计方法参数估计方法 极大似然估计极大似然估计(未知参数为一确定值）未知参数为一确定值）贝叶斯估计（未知参数为一随机变量）贝叶斯估计（未知参数为一随机变量）贝叶斯学习（未知参数为一随机变量）贝叶斯学习（未知参数为一随机变量）非参数估计非参数估计 ParzenParzen窗估计窗估计 K K-N N 近邻估计近邻估计3.3.密度函数的估计密度函数的估计BayesBayes分类分类 已知先验概率已知先验概率与类条件概率与类条件概率，可，可以设计一个最优分类器。以设计一个最优分类器。问题问题 实际情况中，实际情况中，的确切分布很难知道，这的确切分布很难知道，这就需要根据已有样本作出参数估计。就需要根据已有样本作出参数估计。特定条件下，可以合理地假设特定条件下，可以合理地假设是均值是均值为为，协方差矩阵为，协方差矩阵为的正态分布，将问题缩的正态分布，将问题缩小为估计小为估计的值。的值。(|)iP X()iP(|)iP X(|)iP Xiiii密度函数的估计密度函数的估计参数估计的方法：参数估计的方法：有监督的参数估计有监督的参数估计最大似然估计最大似然估计BayesBayes估计估计 无监督的参数估计无监督的参数估计 非参数估计非参数估计ParzenParzen窗窗K K-N N 近邻近邻基础知识：基础知识：1.1.2.2.=()(|)()P A BP A BP B=()(|)()P A BP A B P B即即=(|)(|)(|)P A B CP ABC P BC(1)(1)最大似然估计最大似然估计a1a1一般原则：条件一般原则：条件 设已知样本集有样本类设已知样本集有样本类，其中，其中类类有样本有样本，是按概率密度，是按概率密度从总从总体中独立地抽取的，但是其中某一参数体中独立地抽取的，但是其中某一参数或参或参数矢量数矢量不知道，记作参数不知道，记作参数。假设假设1 1：参数：参数唯一地是由唯一地是由决定的，记决定的，记作作，即认为此概率密度是由，即认为此概率密度是由作为作为条件的条件概率密度。条件的条件概率密度。假设假设2 2：在：在类的样本中不包含类的样本中不包含的信息。可的信息。可以对每一类独立地进行处理。以对每一类独立地进行处理。(|)jP X12,cLXXXjX12,nXXXL(,)jj,jj(|)jP XjXj(|,)jjP X(|,)jjP X (|)jP X 2 2(1)(1)最大似然估计最大似然估计a2a2似然函数似然函数：同一类的样本子集同一类的样本子集，它们具有，它们具有概率密度概率密度，且样本是独立，且样本是独立抽取的，因此抽取的，因此12,nXXX=LX(|),1,2,kP Xkn=L1(|)(|),nkkPP X=X(|)PX()(|)LP=Xargmax()L=(|)PXO下页(1)(1)最大似然估计最大似然估计a3a3对数似然函数对数似然函数：计算：计算：log(|)PX1()log(|)log(|),nkkLPP X=Xargmax()L=()1log(|)log(|)0nkkLPP X=X1p=M最大似然估计最大似然估计a4a4问题：问题：并不一定能够得到解。并不一定能够得到解。举例：举例：x x服从均匀分布，参数服从均匀分布，参数未知未知假设从总体中独立地抽取假设从总体中独立地抽取N N个样本，则个样本，则=0L 12，=12211(|)0XP Xotherwise()=211()(|)0NLP X最大似然估计最大似然估计a5a5对数似然函数对数似然函数()=21()log(|)lnLPNX=121()1LN=221()1LN=1x=2x分母越小似然函数越大，估计参数为训练样本中最小和最大的(1)(1)最大似然估计最大似然估计b1b1均值未知的均值未知的d d维正态情况维正态情况 设设中的某一样本中的某一样本具有正具有正态形式，参数态形式，参数未知，未知，若干基础知识：若干基础知识：X12(,)TkkkkdXxxx=L112211(|)exp()()2(2)|TdkkkP XXX=111log(|)log(2)|()()22dTkkkP XXX=loglog()TTTABB A=1是对称矩阵是对称矩阵是对称矩阵，则是对称矩阵，则TAA=1log(|)()().TkkkP XXX=(1)(1)最大似然估计最大似然估计b2b2进一步地进一步地结论结论111111log(|)()()()()()()1()()12 1()TkkkTTkkkkTTTkkTkP XXXXXXXXXX=+=+=12 1()0TkLX=1()0nkkX=11nkkXn=3 3(1)(1)最大似然估计最大似然估计c1c1均值、方差未知的一维正态情况均值、方差未知的一维正态情况=1,2122()11(|)exp22kkxP x=2122()11log(|)log222kkxP x=loglog=22(1)(1)最大似然估计最大似然估计c2c2均值均值2122()11log(|)log222kkxP x=111121()0nnkkkLx=11()0nkkx=111nkkxn=111221log(|)2()(1)2kkkxP xx=1(1)(1)最大似然估计最大似然估计c2c2方差：有偏估计方差：有偏估计2122()11log(|)log222kkxP x=222212221222()11log(|)(2)(1)222()122kkkxP xx=+22111122()1(1)02nnnkkkkxL=+=22111()nkkxn=2211()1nkkxn=(1)(1)最大似然估计最大似然估计c3c3多变量情况多变量情况11nkkXn=11()()nTkkkXXn=)(2)Bayes(2)Bayes估计估计a1a1已知：已知：BayesBayes分类分类 核心：类条件概率密度必须知道，但若有一批核心：类条件概率密度必须知道，但若有一批已知类别的样本已知类别的样本，则可以根据后验概率计算，则可以根据后验概率计算出条件概率。出条件概率。目的目的 求条件概率密度求条件概率密度方法方法 根据联合概率密度的积分根据联合概率密度的积分，得到后，得到后验概率和条件概率的关系。验概率和条件概率的关系。X(|)P XX(,)P Xd(2)Bayes(2)Bayes估计估计a2a2两个假设两个假设 有监督学习，样本的类别已知并且类分布独立。有监督学习，样本的类别已知并且类分布独立。存在一个概率密度的分布形式已知，而参数存在一个概率密度的分布形式已知，而参数未未知的后验概率密度知的后验概率密度，从样本中得到的信，从样本中得到的信息都反映在后验密度息都反映在后验密度中。中。(|)P X(|)P X12,cLXXXij12(|,)cjP XLXXXjX12(|,)ciP XLXXX4 4(2)Bayes(2)Bayes估计估计a3a3推导推导()(,)P XP Xd=条件：样本集条件：样本集X(|)(,|)P XP Xd=XX(,)(|)()P XP XP=(|)(|,)(|)P XP XPd=XXX(|)(|)(|)P XP XPd=XX确定后，确定后，与与无关无关X条件概率后验概率(2)(2)BayesBayes估计估计估计，学习示例估计，学习示例b1b1求后验密度求后验密度条件条件1 1：为已知类别为为已知类别为的的n n个同个同类样本，并且是独立抽取的。类样本，并且是独立抽取的。条件条件2 2：考虑：考虑是一维的情况。是一维的情况。条件条件3 3：把：把均看作是随机变量，遵循如下分布均看作是随机变量，遵循如下分布12,nXXX=LXjX,X2(|)(,)kP xN:200()(,)PN:(2)(2)BayesBayes估计估计估计、学习示例估计、学习示例b2b2推导过程推导过程1(|)()(|)(|)()(|)()(|)()nkkPPPPPP XPPPd=XXXX条件322022100220102222002222221000()()11(|)expexp22221exp2221exp2nkknkknkkkxPxxx=+=+X202222100111exp22nkknx=+条件1(2)(2)BayesBayes估计估计估计、学习示例估计、学习示例b3b3仍是一个正态函数，称为再生密度。仍是一个正态函数，称为再生密度。假设假设，即，即202222100111(|)exp22nkknPx=+X(|)P X2222222()11(|)exp222111exp22nnnnnnnnnP=+X2(|)(,)nnPN:X比较(2)(2)BayesBayes估计估计估计学习示例估计学习示例b4b4的求解的求解22200022222100111nnnnkknnnxm=+=+=+,nn22022022002202220nnnnmnnn=+=+11nnkkmxn=(2)(2)BayesBayes估计估计估计、学习示例估计、学习示例b5b5分析：分析：1.1.再生密度的均值是再生密度的均值是样本均值样本均值和和先验均值先验均值的线性的线性组合。组合。2.2.一般情况下一般情况下，则当，则当。极端情况极端情况1 1：，说明先验值，说明先验值十十分可靠。分可靠。极端情况极端情况2 2：，说明先验值十分，说明先验值十分没有把握。没有把握。3.3.随随n n的增加而减小，说明的增加而减小，说明趋于趋于。参见下页图示参见下页图示22220022220222000nnnnmnnn=+=+00 2n2n2n,nnnm 0nnm=?000,nn=05 512(|,)nPx xxL(2)(2)BayesBayes估计估计学习学习b6b6-4 4-3 3-2 2-1 10 01 12 23 34 45 5-5 51n=4n=9n=16n=25n=2.02.01.81.81.61.61.41.41.21.21.01.00.80.80.60.60.40.40.20.20.00.0(2)(2)BayesBayes学习学习c1c1求类条件密度求类条件密度(|)(|)(|)P XP XPd=XX2(|)(,)P XN:2(|)(,)nnPN:X2222222()()1111(|)expexp2222()1exp(,)2nnnnnnnxP Xdxf=+X222222222()1(,)exp2nnnnnxfd+=+其中，其中，(2)(2)BayesBayes学习学习c2c2分析分析1.1.2.2.条件概率条件概率的均值和后验概率的均值和后验概率的均值相等。的均值相等。3.3.条件概率条件概率的方差比后验概率的方差比后验概率的的方差大。方差大。4.4.多维正态分布多维正态分布222()(|)expnnxP X+X(|)P XX(|)P X(|)P XX(|)P X22(|)(,)nnP XN +:X2n22n+(|)(,)nnP XN +:X目录目录2828讲义：模式识别第三章：统计模式识别(二)最大熵估计最大熵估计Maximum entropy Maximum entropy extinationextination EntropyEntropyDefinition Definition ConditionsConditionsAssume Assume p(xp(x)is unknown)is unknownRelated constraints including mean value,Related constraints including mean value,variance,etcvariance,etc.are.are knownknown To maximize this entropyTo maximize this entropy Example:Example:Ref.Pattern Recognition,Page 35.Ref.Pattern Recognition,Page 35.=XdxxpxpH)(ln)(2929讲义：模式识别第三章：统计模式识别(二)Mixture ModelsMixture ModelsIdea:Idea:Unknown Unknown p(xp(x)is a linear combination of density)is a linear combination of density functions functions Procedure:Procedure:Step1:set density components Step1:set density components p(x|jp(x|j:)Step2:known training samples to compute unknown Step2:known training samples to compute unknown and and p pj j MethodsMethodsMaximum likelihood Maximum likelihood Difficult to calculateDifficult to calculate The maximization task is a nonlinear fashion,thus nonlinear The maximization task is a nonlinear fashion,thus nonlinear optimization iterative techniques have to be adoptedoptimization iterative techniques have to be adopted=xjJjjdxjxpPPjxpxp1)|(1 where)|()(13030讲义：模式识别第三章：统计模式识别(二)The Expectation Maximization Algorithm(EM)The Expectation Maximization Algorithm(EM)It is good at cases in which the available data It is good at cases in which the available data set is incomplete.set is incomplete.Procedure:Procedure:Initialize Initialize 0 0,T,iT,i=0=0DoDo i=i+1i=i+1 ExpectationExpectation step:compute Q(step:compute Q(;i i)Maximization step:Max Q(Maximization step:Max Q(;i i)?i i+1+1Until Q(Until Q(i i+1+1;i i)-Q(Q(i i;i i-1 1)=T)=T Return Return=i i+1+1Example:Example:模式识别模式识别(中文版），中文版），page 23page 230);(:);|;(ln();(1=+iikikyiQXypEQ6 63131讲义：模式识别第三章：统计模式识别(二)EM AlgorithmEM Algorithm4.4.非参数方法非参数方法前几节的结论是基于概率密度的分布形式前几节的结论是基于概率密度的分布形式已知的假设。已知的假设。实际问题并不一定满足这个假设。实际问题并不一定满足这个假设。经典的参数密度是单峰的。经典的参数密度是单峰的。实际的问题包含多峰的密度。实际的问题包含多峰的密度。模式分类的非参数方法模式分类的非参数方法 根据样品模式估计密度函数根据样品模式估计密度函数，然后利，然后利用用BayesBayes公式；公式；直接估计后验概率直接估计后验概率。(|)jP X(|)jPX非参数方法非参数方法非参数方法非参数方法 概率密度的估计概率密度的估计 ParzenParzen窗估计法窗估计法 近邻估计近邻估计(1).(1).概率密度的估计概率密度的估计a a基础：基础：一个向量一个向量X X落在区域落在区域R R里的概率里的概率P P为为概率概率P P是密度函数是密度函数P P(X X)的一种经过平均后的形式，的一种经过平均后的形式，对对P P作估计就是估计出作估计就是估计出P P(X X)的这个平均值。的这个平均值。概率密度估计概率密度估计 设样本设样本是按照概率密度是按照概率密度独立抽取独立抽取的，的，n n个样本中有个样本中有k k个落在区域个落在区域R R里的概率符合里的概率符合二项定律。二项定律。其中，其中，P P是是1 1个样本落在区域个样本落在区域R R里的概率。里的概率。()RPP X dX=1,nXXL()P X(1)kkn knkPC PP=概率密度的估计概率密度的估计b bk k是一个随机变量，是一个随机变量，k k的期望值是的期望值是由于由于k k的二项分布在均值附近有一个峰值，所以的二项分布在均值附近有一个峰值，所以k k/n n是是P P的一个很好的估计。的一个很好的估计。假设假设P P(X X)连续，且连续，且R R小到小到P P(X X)在在R R上几乎没有什么变上几乎没有什么变化，则，化，则，其中，其中，X X是是R R中的一点，中的一点，V V是被是被R R包围的体积。包围的体积。()()1()RRPP X dXP XdXPXV=/()knP XVPnPkkEnkk=0)(概率密度的估计概率密度的估计c c讨论讨论(1)(1)体积体积V V固定，如果样本取得越来越多，则比值固定，如果样本取得越来越多，则比值k k/n n将在概率上按预计的收敛，因此得到一个将在概率上按预计的收敛，因此得到一个P P(X X)的空间平均估计值，的空间平均估计值，若要想得到若要想得到P P(X X)，必须必须让让V V趋于趋于0 0。如果固定样本数如果固定样本数n n，让，让V V趋于趋于0 0，则区域不断缩小，则区域不断缩小，以至最后不包含任何样本，而以至最后不包含任何样本，而的估计没有意的估计没有意义。若恰好有几个样本和义。若恰好有几个样本和X X重合，则估计值就发散重合，则估计值就发散到无穷大，同样也没有意义。到无穷大，同样也没有意义。/()knP XV()1RRP X dXPVdX=()0P X7 7概率密度的估计概率密度的估计d d讨论讨论(2)(2)实际上，样本的数目有限，所以体积不允许任实际上，样本的数目有限，所以体积不允许任意小，因此密度函数是一定范围内的平均值。意小，因此密度函数是一定范围内的平均值。理论上，假设可以利用的样本数无穷，可以利理论上，假设可以利用的样本数无穷，可以利用极限的方法来研究密度函数的估计。即，用极限的方法来研究密度函数的估计。即，构造一个包含构造一个包含X X在内的区域序列在内的区域序列，设，设的体积是的体积是，其中的样本数为，其中的样本数为，则，则1,nRRL/()nnnknP XV=nRnVnk什么条件？什么条件？makemake()()nP XP X概率密度的估计概率密度的估计e e三个条件：三个条件：1.1.2.2.3.3.n n增大时，落入增大时，落入V Vn n中样本数中样本数k kn n也要增加；也要增加；同时，同时，V Vn n应不断减少，以使应不断减少，以使P Pn n(X X)趋于趋于P P(X X)；在小区域在小区域V Vn n中尽管落入了大量样本，但相对于中尽管落入了大量样本，但相对于样本总数，这个数量仍然很小；样本总数，这个数量仍然很小；为了防止为了防止V Vn n下降太快，必须控制使之下降比下降太快，必须控制使之下降比V Vn n/n n的下降慢一些，例如的下降慢一些，例如。lim()()nnP XP X=limnnk=lim0nnV=lim/0nnkn=1nVn=概率密度的估计概率密度的估计f f概率密度估计的结论及方法的演变概率密度估计的结论及方法的演变 ParzenParzen窗窗：在具有一定数量的样本时，可以选：在具有一定数量的样本时，可以选定一个中心在定一个中心在X X处的体积处的体积V Vn n，然后计算落入其然后计算落入其中的样本数中的样本数k kn n来估计局部密度来估计局部密度P Pn n(X X)的值。的值。k kn n近邻估计近邻估计：选定一个：选定一个k kn n值，以值，以X X为中心建立一为中心建立一个体积个体积V Vn n，让，让V Vn n不断增大，直到它能捕获不断增大，直到它能捕获k kn n个个样本，这是的体积样本，这是的体积V Vn n即用来计算即用来计算P Pn n(X X)的估值。的估值。问题问题 样本有限时，上述两种方法的性能难以估计。样本有限时，上述两种方法的性能难以估计。(2).(2).ParzenParzen窗估计法窗估计法a aParzenParzen窗函数窗函数其中，其中，X X是是d d维空间中要估计概率密度维空间中要估计概率密度值值P Pn n(X X)的点，的点，V Vn n是以是以X X为中心边长为为中心边长为h hn n的超立方体。的超立方体。X Xi i是样本，是样本，落在落在V Vn n中的样本数中的样本数k kn n是是otherwise1|,1,2,20niinhXXjdXXh=L1nininXXkh=111()nindinnXXP Xnhh=ParzenParzen窗函数窗函数方窗函数方窗函数正态窗函数正态窗函数指数窗函数指数窗函数()=otherwise11|20uu()=211exp22uu()=exp|uuParzenParzen窗估计法窗估计法b bh hn n对的对的P Pn n(X X)影响影响若若则则 h hn n既影响的既影响的幅度，又影响它的宽度幅度，又影响它的宽度 V Vn n或或h hn n太大，估计的分辨率太低，平滑的结果太大，估计的分辨率太低，平滑的结果 V Vn n或或h hn n太小，估计的统计变动太大，不稳定的太小，估计的统计变动太大，不稳定的“噪声性噪声性”的估计的估计=11()()nnniiP XXXn=1()nnnXXVh=dnnVh()nX8 8ParzenParzen窗估计法窗估计法c cP Pn n(X X)收敛性的讨论收敛性的讨论如果如果P Pn n(X X)满足，满足，则称则称P Pn n(X X)均方收敛于均方收敛于P P(X X)。=lim()()nnP XP X=2lim()0nnXParzenParzen窗估计法窗估计法d d条件条件 P P(X X)在在X X处连续；处连续；窗函数窗函数 窗宽窗宽 sup()nu=|1lim()0diuiuu=limnnnV=lim0nnVParzenParzen窗估计法窗估计法e e均值的收敛性均值的收敛性=1()()111()()()nnniinninnnP XE P XXXEnVhXXPVdVVhXV P V dV因此因此,()()nnP XP XParzenParzen窗估计法窗估计法f f方差的收敛性方差的收敛性P Pn n(X X)是统计独立的随机变量的函数之和，因此它是统计独立的随机变量的函数之和，因此它的方差是每项之和的方差是每项之和=22212222221 11()()()()111()1 11 11()()ninnnninninnninnnnXXXEP XP XEP XnVhnXXnEPXn VhnXXP V dVPXn Vn Vhn=222()()()()D XE XE XE XE XParzenParzen窗估计法窗估计法g g=221 11 1()()innnnXXXP V dVn Vn Vh sup()nu2sup()()()nnnP XXnV结论：满足结论：满足方差就可以收敛到方差就可以收敛到0 0。=limnnnV=lim0nnV=1nVVn=1lognVVnParzenParzen窗估计法窗估计法h h例子：正态分布例子：正态分布:()(0,1)P XN=211()exp22uu=1nhhn=111()nininnXXP Xnhh平滑的正态曲线平滑的正态曲线9 9ParzenParzen窗估计法窗估计法i i例子：二个均匀分布例子：二个均匀分布密度的混合。密度的混合。=+几何意义一个分割平面的能力一个分割平面的能力b bd d维空间维空间n n个点的二分法可以线性分割的比例个点的二分法可以线性分割的比例超平面的能力超平面的能力1313(4).(4).平均错误率问题平均错误率问题研究表明，小规模数据设计的分类器对新研究表明，小规模数据设计的分类器对新样本的分类能力是有限的。样本的分类能力是有限的。研究重点：分类错误率和样本数目的关系研究重点：分类错误率和样本数目的关系 根据样本估计未知参数根据样本估计未知参数 根据估计值决定分类器根据估计值决定分类器 计算分类器的分类错误率计算分类器的分类错误率实际上，上述的分析是很困难的，最终的实际上，上述的分析是很困难的，最终的结果和多个因素相关。结果和多个因素相关。平均错误率问题平均错误率问题b b例子：一个先验概率相等的两类问题。例子：一个先验概率相等的两类问题。特征空间被分成特征空间被分成mm个不相交的单元个不相交的单元如果条件概率密度如果条件概率密度相差不大，则问题简相差不大，则问题简化为离散情况。设化为离散情况。设向量向量就决定了概率结构就决定了概率结构BayesBayes准则：若准则：若，则，则；否则，；否则，分类错误率：分类错误率：12,.,mC CC(|)iP X1(|)iiPP XC=2(|)iiQP XC=111()()2PP=12(,.,)TmPP PP=12(,.,)TmQQ QQ=PQ1X2X11(|,)min|2miiiP e P QPQ=平均错误率问题平均错误率问题c c若若P P,Q Q都未知，则必须使用一组样本进行估都未知，则必须使用一组样本进行估计，这是得到的错误率高于前面的值。计，这是得到的错误率高于前面的值。要计算错误率，必须知道真正的条件概率要计算错误率，必须知道真正的条件概率P P和和Q Q以及样本以及样本X X。简化的模型：简化的模型：P P和和Q Q是均匀分布的是均匀分布的 平均错误率如图所示平均错误率如图所示平均错误率问题平均错误率问题d d讨论：当n固定时，P作为单元数m的函数，当样本无限多时，最大似然估计是非常好的，而P是Bayes错误率对所有问题的平均。当m趋于无限大时，错误率趋于0.25。每一个有限样本数目的曲线都有一个最佳的单元数。当样本数目一定时，如果特征很多的话，分类器的性能就会变坏。当m趋于无限大时，错误率趋于0.5。(5).(5).错误率的估计错误率的估计分析错误率的必要性分析错误率的必要性 掌握分类器的性能掌握分类器的性能 与其它分类器对比与其它分类器对比方法：方法：按照标准的参量模型计算，存在一定的问题。按照标准的参量模型计算，存在一定的问题。经验分析法：利用试验来检验分类器，根据无经验分析法：利用试验来检验分类器，根据无分类样本的百分比作为错误率的估计。分类样本的百分比作为错误率的估计。举例：举例：假设分类器的真正的但未知的错误率是假设分类器的真正的但未知的错误率是P P，n n个个独立的随机抽取的试验样本中有独立的随机抽取的试验样本中有k k个错分，则个错分，则错误率的估计错误率的估计b bk k满足二项分布满足二项分布错分样本的比率是错分样本的比率是P P的最大似然估计的最大似然估计P P的的95%95%置信区间与置信区间与和和n n的关系图的关系图()(1)kkn knP kC PP=kPn=P1414错误率的估计错误率的估计c c错误率的估计错误率的估计d d数据的使用：训练集和测试集数据的使用：训练集和测试集平均法：平均法：分为两组，一组训练，一组检验，反复多次，分为两组，一组训练，一组检验，反复多次，计算平均值。计算平均值。“留一法留一法”：n n个样本，取个样本，取n n-1 1个训练，个训练，1 1个样本测试个样本测试 重复重复n n次，取平均。次，取平均。6.6.降低特征的维数降低特征的维数问题：模式分类的问题：模式分类的“维数灾难维数灾难”策略：压缩特征空间的维数策略：压缩特征空间的维数 特征组合特征组合 重新提取重新提取 主成分分析主成分分析(PCA PCA-Principal Component AnalysisPrincipal Component Analysis)特征投影特征投影FisherFisher判决函数判决函数降低特征的维数降低特征的维数b bTyWX=1x2xOW1x2xOW降低特征的维数降低特征的维数c c假设一个集合中有假设一个集合中有n n个维的样本个维的样本，其中其中个属于个属于类的样本，类的样本，个属于个属于类的类的样本。样本。几个基本参量几个基本参量d d维空间：维空间：样本均值样本均值 类内离散度类内离散度 类间离散度类间离散度12,.,nXXX1N2N211,1,2iiXiXMiN=X()(),1,2iTiiiXSXMXMi=X1212()()bTMMSMM=12wSSS=+,1,2,.,TiiyW X in=降低特征的维数降低特征的维数d d1 1维空间：维空间：样本均值样本均值 类内离散度类内离散度目标目标 投影后，在一维空间里各样本尽可能分得开一投影后，在一维空间里各样本尽可能分得开一些，即两类均值之差些，即两类均值之差越大越好。同时各越大越好。同时各类样本内部尽量密集，即类内离散度越小越好类样本内部尽量密集，即类内离散度越小越好11,1,2iiTXiiiXyW X iNNm=%YY221(),1,2iiySymi=%Y2212wSSS=+%12mm%1515降低特征的维数降低特征的维数e eFisherFisher准则函数准则函数2122212()mmJ WSS=+%类间分离程度类间分离程度类内分离程度类内分离程度221()()()iiTTTTiiiXXTiSWXWMWXMXMWWSW=%XX()2212121212()()()TTTTTbmmW MW MWMMMMWW SW=%2211TwSSW S W+=%()212TbmmW SW=%降低特征的维数降低特征的维数f f因此因此根据根据LagrangeLagrange乘子法，使乘子法，使J J达到极大值的达到极大值的WW满足满足如果如果非奇异，则非奇异，则()TbTwW S WJ WWS W=广义广义RayleighRayleigh比比*wbS WS W=wS*1wbSS WW=矩阵矩阵的特征值的特征值1wbSS降低特征的维数降低特征的维数g g进一步进一步*121212()()()TbS WMMMMWMMR=*1112()()wwbWSS WSMMR=*112()wRWSMM=*112()wWSMM=广义广义RayleighRayleigh比比降低特征的维数降低特征的维数h h1 1维空间中的分类：选择分类阈值维空间中的分类：选择分类阈值 当维数和样本数很大时，可以采用当维数和样本数很大时，可以采用BayesBayes决策决策准则，获得在一维空间中的准则，获得在一维空间中的“最优最优”分类器。分类器。上述条件不满足，则上述条件不满足，则可以选取如下之一可以选取如下之一0y12(1)02mmy+=%1122(2)012N mN myNN+=+%()1212(3)012ln()/()22PPmmyNN+=+%TyWX=0y0102yyXyyX小小 结结BayesBayes法则法则统计分类的判决准则统计分类的判决准则正态分布下的判决正态分布下的判决参数估计和非参数估计参数估计和非参数估计分类错误率的讨论分类错误率的讨论高维特征的投影高维特征的投影第四章 聚类分析