哈工大 模式识别第四章第五章

2020/1/4哈尔滨工业大学电信院宿富林1第四章特征的选择与提取2020/1/4哈尔滨工业大学电信院宿富林2§4.1基本概念如何确定合适的特征空间是设计模式识别系统另一个十分重要，甚至更为关键的问题。如果所选用的特征空间能使同类物体分布具有紧致性，即各类样本能分布在该特征空间中彼此分割开的区域内，这就为分类器设计成功提供良好的基础。反之，如果不同类别的样本在该特征空间中混杂在一起，再好的设计方法也无法提高分类器的准确性。这一章要讨论的问题就是特征空间如何设计的问题2020/1/4哈尔滨工业大学电信院宿富林3如何构造一个特征空间，即对要识别的事物用什么方法进行描述、分析的问题？1、物理量的获取与转换(原始测量）这是指用什么样的传感器获取电信号，如摄取景物则要用摄像机。可以称之为原始信息(原始测量，得到测量空间)。2、描述事物方法的选择与设计(特征形成)在得到了原始信息之后，要对它进一步加工，以获取对分类最有效的信息。设计所要信息的形式是十分关键的。2020/1/4哈尔滨工业大学电信院宿富林4例用RGB颜色空间和HSI颜色空间右边是原始图像，左边是用HSI空间描述的同一图像(但是为了显示出来，用H对应R，S对应G，I对应B，然后再以RGB的方式显示出来3、特征空间的优化这个层次的工作发生在已有了特征的描述方法之后，也就是已有了一个初始的特征空间，如何对它进行改造与优化的问题。一般说来要对初始的特征空间进行优化是为了降维。即初始的特征空间维数较高。能否改成一个维数较低的空间，称为优化，优化后的特征空间应该更有利于后续的分类计算，这就是本章着重讨论的问题。对特征空间进行优化有两种基本方法：一种为特征选择，一种为特征的组合优化----特征的提取。2020/1/4哈尔滨工业大学电信院宿富林52020/1/4哈尔滨工业大学电信院宿富林6特征选择已有D维特征向量空间，Y={y1,y2,…,yD}，从原有的D维特征空间，删去一些特征描述量，从而得到精简后的特征空间。在这个特征空间中，样本由d维的特征向量描述：X={x1,x2,…,xd}，d＜D。X只是Y的一个子集，每个分量xi必然能在原特征集中找到其对应的描述量xi＝yj。2020/1/4哈尔滨工业大学电信院宿富林7特征提取找到一个映射关系：A:Y→X使新样本特征描述维数比原维数降低。其中每个分量xi是原特征向量各分量的函数，即Xi=fi(y1,y2,…,yD)这两种降维的基本方法是不同的。在实际应用中可将两者结合起来使用，比如先进特征提取，然后再进一步选择其中一部分，或反过来。2020/1/4哈尔滨工业大学电信院宿富林8§4.2类别可分离性判据对原特征空间优化，就要对优化结果进行评价实际的评价方法，是对系统性能进行测试，测试指标主要有正确率、计算速度、存储容量等。本章讨论的评价方法：目的在于找出对特征空间进行优化的具体算法。对特征空间进行优化是一种计算过程，它的基本方法仍然是模式识别的典型方法：找到一种准则(或称判据，通常用一种式子表示），以及一种优化计算方法，使这种准则达到一个极值。2020/1/4哈尔滨工业大学电信院宿富林9判据理想的情况是与计算错误率有关的判据直接反映错误率的是贝叶斯公式，在实际中运用有困难采用其他判据2020/1/4哈尔滨工业大学电信院宿富林10可分性判据应满足的要求（1）与错误率有单调关系，这使判据取最大值时错误率也较小（2）当特征独立时有可加性：（Jij是第i类与第j类的可分性准则）（3）度量特性：（4）单调性：加入新的特征时，判据不减小dkkijdij)(xJ),...,x,x(xJ121ijijijjiJ0,ij;J0,ij;JJ),...,x,x(xJ),...,x,x(xJdijdij1d2121x,2020/1/4哈尔滨工业大学电信院宿富林11几种常用的可分性判据以计算样本在特征空间离散程度为基础的准则，称为基于距离的可分性判据（重点）基于概率密度分布的可分性判据。基于熵函数的可分性判据（不讲）2020/1/4哈尔滨工业大学电信院宿富林12一、基于距离的可分性判据基于距离的度量是用来进行分类的重要依据。因为一般情况下同类物体在特征空间呈聚类状态，即从总体上说同类物体内各样本由于具有共性，因此类内样本间距离应比跨类样本间距离小。Fisher准则(也可看成是特征提取方法)正是以使类间距离尽可能大同时又保持类内距离较小这一种原理为基础的。同样在特征选择与特征提取中也使用类似的原理，这一类被称为基于距离的可分性判据。2020/1/4哈尔滨工业大学电信院宿富林13两类之间的距离：ω1任一点与ω2中任一点的距离和的平均。多类：各类之间的平均距离:ωi任一点xk(i)与ωj中任一点xj(j)的距离Pi,Pj是第i类和第j类的先验概率度量类内、类间的距离，可用不同方法，如欧氏距离等。()()()(,)jinnccijdijklijklijJxPPxxnn1111112ijklxx()()(,)2020/1/4哈尔滨工业大学电信院宿富林14iijijTijklklklniikkiciiixxxxxxmxnmPm()()()()()()()(,)()()111欧氏距离下的可分性判据欧氏距离：每类均值：所有样本集总均值：平均距离：（判据）令：则得判据的矩阵形式：bwdJxtrSS~~()()inccTiiTbwiiiikikiiikiSPmmmmSPxmxmn~~()()()(),()()1111inciTiTdikikiiiikiJxPxmxmmmmmn()()()[()()()()]111上述公式是有限样本集，是均值及散度的估计。对于无限样本，tr：迹2020/1/4哈尔滨工业大学电信院宿富林15wbSS~~,imm,,i,,wbSS,iiExEx[][],ccTTwiiiibiiiiiSPExxSP[()()]()()11dbwJxtrSS()()2020/1/4哈尔滨工业大学电信院宿富林16考虑类内类间欧氏距离的其它判据判据Jd(X)是计算特征向量的总平均距离，以下一些判据则基于使类间离散度尽量大，类内离散度尽量小的考虑而提出。()()||ln[]||||||wbbwbwwbwJxtrSSSJxStrSJxtrSSSJxS12345（）（）（）2020/1/4哈尔滨工业大学电信院宿富林17基于距离的可分性判据优缺点距离准则：是样本在特征空间的分布的距离作为特征提取的依据。优点：直观，计算简便。缺点：没有考虑概率分布，因此当不同类样本中有部分在特征空间中交迭分布时，简单地按距离划分，无法表明与错误概率之间的联系。2020/1/4哈尔滨工业大学电信院宿富林18基于概率分布的可分性判据：依据不同类别类分布概率密度函数来优化特征空间不考虑各类的先验概率，或假设两类样本的先验概率相等（如下图），可以看出：1.如果两类条件概率分布互不交迭，则这两类就完全可分；2.对所有X都有p(X|ω1)＝p(X|ω2)，则两类就完全不可分。完全可分重合，完全不可分二、基于概率分布的可分性判据2020/1/4哈尔滨工业大学电信院宿富林20任何函数若满足下列条件，则用于做判据：1、Jp≥02、当两类完全不交叠时，Jp取最大值若对所有x有：p(X|ω2)≠0时，p(x|ω1)=0，则Jp=max3、当两类分布相同时，Jp=0若：p(X|ω2)=p(x|ω1)，则Jp=0dx]P2,P1),2|x(p),1|x(g[pJp一种是用p(x|ω1)，p(x|ω2)之间的乘法来计算其重迭程度，像Bhattacharya距离、Chernoff界限等Bhattacharyya距离、Chernoff界限与错误率的上界有直接关系（见第二章）。因此Bhattacharyya距离、Chernoff界限不仅用来对特征空间进行降维优化，而且也用来对分类器的错误率作出估计。另一种用两者间的比值，称为散度。2020/1/4哈尔滨工业大学电信院宿富林212020/1/4哈尔滨工业大学电信院宿富林221、Bhattacharyya距离和Chernoff界限Bhattacharyya距离显然，当p(X|ω1)＝p(X|ω2)时，JB＝0；而当两者完全不交迭时JB为无穷大Chernoff界限dx)]|x(p)|x(p[lnJ2/121B-ln(|)(|)[,].ssCCBJpxpxdxSSJJ1120105，2020/1/4哈尔滨工业大学电信院宿富林232、散度(|)()ln(|)iijjpxlxpX另一种常用的基于概率距离度量的判据是利用似然比或对数似然比。对两类问题，对数似然比为：可提供ωi对ωj的可分性信息。如果对某个X，当p(X|ω1)＝p(X|ω2)时，则lij=0,反之若两者差异越大，则lij的绝对值也大。2020/1/4哈尔滨工业大学电信院宿富林24对整个特征空间概率分布的差异程度作出评价，可将对ωi类及对ωj的平均可分性信息定义为iiijijjXpxpxIxEpxdxpXpX(|)(|)()[ln](|)ln(|)(|)总的平均可分信息则可表示成散度(|)[(|)(|)]ln(|)iDijjiijjXpxJIIpxpxdxpX2020/1/4哈尔滨工业大学电信院宿富林253、正态分布时可分性判据TDijjiijijijJtrI()()()111111222ij若则一维：TDijijJ()()1ijDJ()222020/1/4哈尔滨工业大学电信院宿富林26jijiTBijijjiJ/|()|()[]()ln[||||]1121112822若则ijTBijijMJJ()()111882020/1/4哈尔滨工业大学电信院宿富林274.3特征提取4.3.1按距离度量的特征提取方法基于距离的可分性判据的实质是Fisher准则的延伸，即综合考虑不同类样本的类内聚集程度与类间的离散程度这两个因素。这种判据的优化体现出降维后的特征空间较好地体现类内密集、类间分离的要求。2020/1/4哈尔滨工业大学电信院宿富林28按欧氏距离度量的特征提取方法基于距离可分性判据的特征优化过程是通过一个线性变换实现的。设在原特征空间一个样本向量表示成X(D维)而在优化特征空间中，样本向量表示成Y(d维)而X与Y之间的关系是：Y=WTX其中W是一个D×d维矩阵（dD）目的：利用判据找出一种线性变换W，它可实现这种判据J(Y)=J(W)的极值化。1、J2判据下的特征提取将原特征空间X(D维)通过线性映射Y=WTX降维到特征空间Y中，若X空间的类内离散度矩阵和类间离散度矩阵分别为SW,Sb;则按J2判据的的最后特征提取矩阵W是按如下方式构造的：若矩阵SW-1Sb的本征值λi按大小顺序列为则选择前d个本征值所对应的本征向量组成变换矩阵WD*d，都可使这些判据J2(W)达到最大值。2020/1/4哈尔滨工业大学电信院宿富林29D123wbJxtrSS()()122020/1/4哈尔滨工业大学电信院宿富林30证明：因为：Y=WTX，设：X的类内和类间离散度矩阵分别为SW,Sb则：Y的类内和类间离散度矩阵分别为SW‘,Sb‘为SW’=WSW’WT,Sb’=WSb’WT（见第3章中，Fisher准则一节）在使用J2判据下，将其Y的可分性判据表示成变换W的函数：J2(Y)=tr[(SW’)-1Sb’]则：J2(Y)=tr[(WSWWT)-1(WSbWT)]=J2(W)可以证明：在不降维条件下，即，设