《模式识别与人工智能.pptx》由会员分享,可在线阅读,更多相关《模式识别与人工智能.pptx(60页珍藏版)》请在课桌文档上搜索。
1、Pattern Recognition&artificial IntelligenceLecture 2:特征选择与提取(一),主要内容,1.引言2 类别可分离性判据3 特征选择4.特征提取,1.引言,【问题的提出】,【问题的提出】,【问题的提出】,【问题的提出】,方案2.强调分析不同截面的信号,如在框架的若干部位沿不同方向截取截面分析从背景到字,以及从字到背景转换的情况,如AB截面切割字符三次,CD截面切割字符一次等。,【问题的提出】,例 用RGB颜色空间和HSI颜色空间,【问题的提出】,【问题的提出】,【问题的提出】,【概念】,【概念】,【概念】,2 类别可分离性判据,【概念】,特征选择与
2、提取的任务是找出一组对分类最有效的特征,因此需一准则。,概念:数学上定义的用以衡量特征对分类的效果的准则实际问题中需根据实际情况人为确定。,误识率判据:理论上的目标,实际采用困难(密度未知,形式复杂,样本不充分,),可分性判据:实用的可计算的判据,【概念】,(1)与误判概率(或误分概率的上界、下界)有单调关系。,(2)当特征相互独立时,判据有可加性,即:,类可分别判断函数,【概念】,(3)判据具有“距离”的某些特性,即:,(4)对特征数目是单调不减,即加入新的特征后,判 据值不减。,类可分别判断函数,【概念】,19,值得注意的是:上述的构造可分性判据的要求,即“单调性”、“叠加性”、“距离性”
3、、“单调不减性”。在实际应用并不一定能同时具备,但并不影响它在实际使用中的价值。,类可分别判断函数,类可分别判断依据的常用方法:基于几何距离的可分性判据基于概率密度的可分性判据基于熵的类可分性判据,基于几何距离的类可分离判据,一般来讲,不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。显然,区域重叠的部分越小或完全没有重叠,类别的可分性就越好。因此可以用距离或离差测度(散度)来构造类别的可分性判据。,基于几何距离的类可分离判据,(一)点与点的距离,(二)点到点集的距离,用均方欧氏距离表示,基于几何距离的类可分离判据,(三)类内及总体的均值矢量,各类模式的总体均值矢量,类的
4、均值矢量:,为相应类的先验概率,当用统计量代替先验概率时,总体均值矢量可表示为:,基于几何距离的类可分离判据,(四)类内距离,类内均方欧氏距离,类内均方距离也可定义为:,基于几何距离的类可分离判据,(五)类内离差矩阵,显然,(六)两类之间的距离,基于几何距离的类可分离判据,(七)各类模式之间的总的均方距离,当取欧氏距离时,总的均方距离为,基于几何距离的类可分离判据,(八)多类情况下总的类内、类间及总体离差矩阵,类内离差,类间离差,总体离差,易导出,各模式之间总的均方距离,基于几何距离的类可分离判据,基于几何距离的类可分离判据,在特征空间中,当类内模式较密聚,而不同类的模式相距较远时,从直觉上我
5、们知道分类就较容易,由各判据的构造可知,这种情况下所算得的判据值也较大。由判据的构造我们还可以初步了解运用这类判据的原则和方法。,选择原则:,ii.计算简单,易于实现。,iii.数学上容易处理。,准则函数的递推计算问题:每增/减一个特征,只影响向量中的一个元素,矩阵的一行和一列。,i.实际分类问题需要,找与分类性能关系密切者。,基于几何距离的类可分离判据,基于概率分布的可分性判据,考查两类分布密度之间的交叠程度,基于概率分布的可分性判据,32,可用两类概密函数的重叠程度来度量可分性,构造基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。,基于概率分布的可分性判据,基于概率分
6、布的可分性判据,证明:设,为误分概率,则最小误分概率为:,基于概率分布的可分性判据,(二),Chernoff,判据,(,),基于概率分布的可分性判据,JC 具有如下性质:,基于概率分布的可分性判据,JC 具有如下性质:,基于概率分布的可分性判据,Jc 性质(1)证明:,考虑函数 f(s)=sa+(1-s)b-asb1-s(a,b0),因为,当 0 s 1 时 f(s)=-asb1-s(ln a-ln b)2 0(ab),且 f(0)=f(1)=0,从而有 f(s)0。由该不等式有:,基于概率分布的可分性判据,Jc 性质(2)证明:,只考虑连续的情况:因为f(0)=f(1)=0,当 0 s 1
7、时,f(s)=a-b-asb1-s(ln a-ln b)=0 a=b,从而有 f(s)=0 a=b,由此有:,JC=0,基于概率分布的可分性判据,Jc 性质(5)证明:,设P(e)为最小误分概率,则:,利用不等式,由上式进一步可得:,基于概率分布的可分性判据,由JB和JC的定义知:JB=JC(1/2),对两类都是正态分布情况:,基于概率分布的可分性判据,基于概率分布的可分性判据,实际上,这就启发我们运用两个概密的比或差来描述两个概密重迭或相似的程度。,可以写成:,基于概率分布的可分性判据,(三)散度JD(Divergence),i类对j类的平均可分性信息为:,j 对i 类的平均可分性信息为:,
8、基于概率分布的可分性判据,(三)散度JD(Divergence),对于i 和j 两类总的平均可分性信息称为散度,其定义为两类平均可分性信息之和,即,基于概率分布的可分性判据,(三)散度JD(Divergence),当两类都是正态分布时:,当Ci=Cj=C时,基于概率分布的可分性判据,散度具有如下性质:,(1)JD 0;,(2)对称性:JD(1,2)=JD(2,1);,(3),(4)当x 各分量x1,x2,xn相互独立时,(具有可加性),(5)当x各分量x1,x2,xn相互独立时,(对特征数目单调不减),基于概率分布的可分性判据,一般情况下,散度与误分概率(或其上下界)之间的直接解析关系很难得到
9、,但实验可以证明它们之间存在着单调关系。例如两类都是正态分布,且有相同的协方差阵时,是 的单调减函数。,当两类先验概率相等且为具有相同协方差的正态分布时,则最小误分概率与 的关系为:,基于概率分布的可分性判据,对于c类问题,可采用平均B-判据、C-判据、D-判据:,由JB、JC、JD的定义式结构以及它们与误分概率的关系可以知道,所选取的特征矢量应使所对应的JB、JC、JD尽量大,这样可分性就较好。,基于概率分布的可分性判据,大盖小问题,在特征空间中,若有某两类间的JB、JC或JD很大,可使平均判据变大,这样就掩盖了某些类对的判据值较小的情况存在,从而可能降低总的分类正确率,即所谓的大盖小问题。
10、为改善这种情况,可对每个类对的判据采用变换的方法,使对小的判据较敏感。例如,对JD,可采用变换:,基于概率分布的可分性判据,这样,当i和j两类模式相距很远时,JD(i,j)变得很大,但 也只能接近于1。但对于散度JD(i,j)小的情况,又变得较敏感。于是,总的平均(变换)判据为:,基于概率分布的可分性判据,同样对于JB,单类与平均判据分别为:,单类:,平均判据:,熵可分性判据,熵可分性判据,对于c类问题,给定各类的后验概率 可以写成如下形式:,熵的定义:,由洛必达法则知:当 时,熵可分性判据,例如:显然这时能实现完全正确的分类识别,熵可分性判据,熵可分性判据,说明当类别较少时,分类识别的不确定性变小。,从特征选择角度看,我们应选择使熵最小的那些特征用于分类即选用具有最小不确定性的特征进行分类是有益的。,熵可分性判据,使熵最小的特征利于分类,取熵的期望:,广义熵(具有熵的性质,利于计算)定义为:,式中0,1。不同的值可得不同的可分性度量。,当1时,由洛必达法则可得Shannon熵,当=2时,可得平方熵,熵可分性判据,使用 判据进行特征提取与选择时,我们的目标是使,小 结,可分性判据:距离:类内距离,类间距离,离差矩阵概率密度:JB,JC,JD判据熵:熵和概率的关系,以及熵和判别函数的关系,