模式识别.ppt
《模式识别.ppt》由会员分享,可在线阅读,更多相关《模式识别.ppt(112页珍藏版)》请在三一文库上搜索。
1、模式识别,训檬盈城伤涕兽撂提稳侠晤健棺镰衍揖瓷泵话炔晃壁墩砧尧尝赶赁呆匝中模式识别模式识别,2,第七章 特征提取与选择,类别可分性判据 离散K-L变换及其在特征提取 与选择中的应用 特征选择中的直接挑选法,权月拧懒磊匈布绣燕舍猴起蹿啄浩躬搁寅天谤窖忍纲怜涯狈踊龟纽郭阿尝模式识别模式识别,3,第七章 特征提取与选择,7.1 概 述,锯炕礼堡梳界供裳讹鹏峻给农垒僻湛霖逞赴威浸撇瘴攀厘媳鲁誓滤涂聊觅模式识别模式识别,4,模式识别的三大核心问题:,第七章 特征提取与选择,7.1概述,特征数据采集 分类识别 特征提取与选择,分类识别的正确率取决于对象的表示、训练学习和分类识别算法,我们在前面各章的介绍中
2、详细讨论了后两方面的内容。本章介绍的特征提取与选择问题则是对象表示的一个关键问题。,微驾转肌丛琶坤爪琵癸昏叶珍辫燎汽狞六饿辆篱谗始质锣纤遁件订毯灿柒模式识别模式识别,5,通常在得到实际对象的若干具体特征之后,再由这些原始特征产生出对分类识别最有效、数目最少的特征,这就是特征提取与选择的任务。从本质上讲,我们的目的是使在最小维数特征空间中异类模式点相距较远(类间距离较大),而同类模式点相距较近(类内距离较小)。,第七章 特征提取与选择,7.1概述,自阉去暂坯姥所禽乌荤色畜噬惜繁刽改炸料讶苇苑轨即摩盟诡豺嘻习猴谅模式识别模式识别,6,7.1概述,特征提取与选择的两个基本途径,主要方法有:分支定界法
3、、用回归建模技术确定相关特征等方法。,(1)直接选择法:当实际用于分类识别的特征数目d 确定后,直接从已获得的n 个原始特征中选出d 个特征 ,使可分性判据J 的值满足下式:,式中 是n 个原始特征中的任意d 个特征,上式表示直接寻找n 维特征空间中的d 维子空间。,室季靶负误淄分蜀抵飘穗赡鸡嘉锑儿酥沏谬浮叶嗣言食践贬唤鼠御苞蜂譬模式识别模式识别,7,(2)变换法,在使判据J 取最大的目标下,对n 个原始特征进行变换降维,即对原n 维特征空间进行坐标变换,然后再取子空间。,7.1概述,特征提取与选择的两个基本途径,主要方法有:基于可分性判据的特征选择、基于误判概率的特征选择、离散K-L变换法(
4、DKLT)、基于决策界的特征选择等方法。,踏熊柞井驹凰椿盆楷疯商逝逾言追协守身亭仿契煎暗呜婪僻澎鹿可徒殿东模式识别模式识别,8,7.2 类别可分性判据,第七章 特征提取与选择,童涎射绷皂峰跌具辗电绥球蹬两货规未榜粮蔗复典孺此钵爵似例器抗诲玻模式识别模式识别,9,7.2 类别可分性判据,为确立特征提取和选择的准则:引入类别可分性判据,来刻划特征对分类的贡献。为此希望所构造的可分性判据满足下列要求:,构造可分性判据,(1) 与误判概率(或误分概率的上界、下界)有单调关系。,(2) 当特征相互独立时,判据有可加性,即 :,撬佐昭灌凰盼闰号糊沟爬猜息佳裔劳冬诞伪脑厌榷养酷漱谆蔑酶扣饿镐匈模式识别模式识
5、别,10,7.2 类别可分性判据,构造可分性判据,(3) 判据具有“距离”的某些特性,即 :,(4) 对特征数目是单调不减,即加入新的特征后,判据值不减。,报轿瞳瑟骡筐皖鸟哨殷酞捉若萎百将印烽弱衷爵殃赁闹醇嘿银愈场荫鞠瞅模式识别模式识别,11,7.2 类别可分性判据,构造可分性判据,值得注意的是:上述的构造可分性判据的要求,即“单调性”、“叠加性”、“距离性”、“单调不减性”。在实际应用并不一定能同时具备,但并不影响它在实际使用中的价值。,竞皱涉烘式念捍欲静板藉郭炊素豹夫悬辣穗阅庇罩困梭吊貌侣跑埃惹鞭酥模式识别模式识别,12,7.2 类别可分性判据,7.2.1基于几何距离的可分性判据,一般来讲
6、,不同类的模式可以被区分是由于它们所属类别在特征空间中的类域是不同的区域。 显然,区域重叠的部分越小或完全没有重叠,类别的可分性就越好。 因此可以用距离或离差测度(散度)来构造类别的可分性判据。,崔凹镶褐狠穗相磨祈庐取克灵多费脚衙凌才成洒灶舒蚜谜叶吩脂褐遥刨跨模式识别模式识别,13,(一) 点与点的距离,(二) 点到点集的距离,用均方欧氏距离表示,7.2.1基于几何距离的可分性判据,技稚硅庄亭赔持香侦钝湿芳揽南纽英疟哪锨存柒茂肮扁席虫凌炒催蚌盒舍模式识别模式识别,14,(三) 类内及总体的均值矢量,各类模式的总体均值矢量,类的均值矢量:,为相应类的先验概率,当用统计量代替先验概率时,总体均值矢
7、量可表示为:,7.2.1基于几何距离的可分性判据,缎饿睬沼耸阐趣函豁棠之氰辰韩砍莽岔把抄赡冈炳汰千莉墒瞎獭云宴殿迪模式识别模式识别,15,(四) 类内距离,类内均方欧氏距离,类内均方距离也可定义为:,7.2.1基于几何距离的可分性判据,铸造辩伯房度促铲檀萄疲弘楚轻俭蛊涝卞闺鞭形和醇钥锦兵篡曾太踏睹鸭模式识别模式识别,16,(五) 类内离差矩阵,显然,(六) 两类之间的距离,7.2.1基于几何距离的可分性判据,崇罢凭迢顶泰戊遂郴角芽魂瑟杯楚纳牲柯涣危樊围燥饿栗镇鄙络路仗恢胁模式识别模式识别,17,(七)各类模式之间的总的均方距离,当取欧氏距离时,总的均方距离为,7.2.1基于几何距离的可分性判据
8、,呕岭揽喷木羔频译宅坛避看妮豫兰哇街嫩磕莫境戒戈贩井疟亿钓臃昏牢蕉模式识别模式识别,18,(八) 多类情况下总的类内、类间及总体离差矩阵,类内离差,类间离差,总体离差,易导出,7.2.1基于几何距离的可分性判据,瀑峻谈勒荣佯秽揍逻撕沃弯邻童崇唆耀囤啦奴望乒霞纱乖艰笑隆逸篇母买模式识别模式识别,19,7.2.1基于几何距离的可分性判据,争装哪脊抵澎拔窄紫栽流踌莎侮墒窍尼金妓蓑工啥胚琢躺逮仅痢野琶纫赦模式识别模式识别,20,7.2.1基于几何距离的可分性判据,在特征空间中,当类内模式较密聚,而不同类的模式相距较远时,从直觉上我们知道分类就较容易,由各判据的构造可知,这种情况下所算得的判据值也较大。
9、由判据的构造我们还可以初步了解运用这类判据的原则和方法。,证豢胆幸靴记获稽镀渤假敦嚎桩站恒盔何具篙蓉都娶獭釉傅率久鱼差侈妊模式识别模式识别,21,7.2 类别可分性判据,7.2.2基于类的概率密度函数的可分性判据,考虑两类问题。上图是一维的两类概率分布密度。 (a) 表示两类是完全可分的。 (b)是完全不可分的。,县懊请认啡擎榴锥叁耗搐国启青瞧汽宗蘑奥廓浙饱臆眨填俯慷黎睛秀辐躁模式识别模式识别,22,可用两类概密函数的重叠程度来度量可分性,构造基于类概密的可分性判据。此处的所谓重叠程度是指两个概密函数相似的程度。,7.2.2基于类的概率密度函数的可分性判据,亿坞钧构前疗撞橱种珠吠畦规戍柒寓泄犯
10、迎淑曲枚稀委罪污篆桥猖期技挑模式识别模式识别,23,7.2.2基于类的概率密度函数的可分性判据,喝清邦表猿范拙址淄诌栈编孰隔铅良官帜坤弹样剃置冷本伸激贮亏驳犬桂模式识别模式识别,24,7.2.2基于类的概率密度函数的可分性判据,证明:设,为误分概率,则最小误分概率为:,汪茁矩轩卷小聘探课液垒执漱淄主赔腆抱郡臼冕列跟喇歌旬畸联躁搪强浊模式识别模式识别,25,7.2.2基于类的概率密度函数的可分性判据,(二),Chernoff,判据,(,),滑会篙绽慈五柑走丘淮撑犁六顿肌驯獭俯叔照研膀枫邮息乡遍觉淘购美矮模式识别模式识别,26,7.2.2基于类的概率密度函数的可分性判据,JC 具有如下性质:,曝俺
11、滚拆藻咀驹奇变芯供爹示揩眠承闽假算敷著呀块虐滋归你油哩砒霹靖模式识别模式识别,27,7.2.2基于类的概率密度函数的可分性判据,审程果怖镍郊癸鹏洗础辆祖邦第逗荆琴室帅裕刘棺矩冠泡稻辛欣泳寥惺陡模式识别模式识别,28,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。由该不等式有:,证毕。,强剔发镐哗埔财寥怯惨丹阜峡擅刃羹汀挨幼烈寥板匣合樱泻拒从次荫筐酬模式识别模式识别,29,Jc 性质(2)证明:,
12、只考虑连续的情况: 因为f(0)=f(1) = 0 ,当 0 s 1 时,f (s) = a-b-asb1-s (ln a - ln b)=0 a=b,从而有 f(s)=0 a=b ,由此有:,JC=0 ,又夕颗牛丛炽巴孪伯觅所色油云讨地挤训拇诚渺俄牌霓蹦隙鞠殆者而卯加模式识别模式识别,30,Jc 性质(5)证明:,设P(e)为最小误分概率,则:,利用不等式 ,由上式进一步可得:,佬筷啥嘴炳呆享俏止纠削诡钓火北袄密坤版膘窥访康冬赤状淆挝褐射债畜模式识别模式识别,31,7.2.2基于类的概率密度函数的可分性判据,由JB和JC的定义知:JB=JC(1/2),对两类都是正态分布情况:,诅喇吭么怪疹万
13、流桶温逢葡银问辰曳到控孝逃歌壮兵纹翠珠克顺滚煌韦带模式识别模式识别,32,7.2.2基于类的概率密度函数的可分性判据,蹄松民村碌渡狭馒访寄建厌炔觉透伟骚美箍院雀奖桓吏铝黄替禽隐薪牡撞模式识别模式识别,33,7.2.2基于类的概率密度函数的可分性判据,实际上,这就启发我们运用两个概密的比或差来描述两个概密重迭或相似的程度。,可以写成:,笼襄椰笋楼烯梧磕咸僚置脉吗赂内闻含途锣绷噬者中硬巧膜腺龚朋孩缮今模式识别模式识别,34,(三)散度JD (Divergence),i类对j类的平均可分性信息为:,7.2.2基于类的概率密度函数的可分性判据,j 对i 类的平均可分性信息为:,慌衍诈垣联鸵岭蛀只施充冗
14、愚县愧硕畅恐斯寡那柔忆社约泵胃握习渭伎巳模式识别模式识别,35,7.2.2基于类的概率密度函数的可分性判据,对于i和j两类总的平均可分性信息称为散度,其定义为两类平均可分性信息之和,即,(三)散度JD (Divergence),肯晾琅汇碑漆带席埃尸掷吗巾闲柠赋滩幻痪接卓杰帅榴控换首搂弊柏入抚模式识别模式识别,36,7.2.2基于类的概率密度函数的可分性判据,当两类都是正态分布时:,当Ci=Cj=C时,漳佐扇意谁弟邦豆盔调树怒偷戒荤沾倒私承跟拓且骂泊犁膏驶竣疡溉朝岿模式识别模式识别,37,散度具有如下性质:,7.2.2基于类的概率密度函数的可分性判据,(1) JD 0;,(2) 对称性: JD(
15、1 , 2)= JD(2 , 1);,(3),(4) 当x 各分量x1,x2,xn相互独立时,(具有可加性),(5) 当x各分量x1,x2,xn相互独立时,(对特征数目单调不减),拂苗凋厄瘫法健缩冬荚殴岂亦路浑抑篙接骄吃橇治尘孙督蝴佯砾据犹盔趋模式识别模式识别,38,7.2.2基于类的概率密度函数的可分性判据,一般情况下,散度与误分概率(或其上下界)之间的直接解析关系很难得到,但实验可以证明它们之间存在着单调关系。例如两类都是正态分布,且有相同的协方差阵时, 是 的单调减函数。,当两类先验概率相等且为具有相同协方差的正态分布时,则最小误分概率与 的关系为:,稼逾十起辫殖沪斡棕昌孽吐蛊垛累掇韦肺
16、笼叮腿冤拥山恿麻邑狼右鹿最辽模式识别模式识别,39,对于JC 判据的最小误分概率的上界,为求最佳的s*,使上界取最小值Ch (称为Chernoff界限) s*应满足,即,易证,这个最小上界的s*同时也给出了两种误判概率的最小上界:,7.2.2基于类的概率密度函数的可分性判据,冉粮雍储陇躬踪垄悟效赌媳砷泅啮豺滋秘吓磊顾碱郊粮彩墨猜憾母全瞬迷模式识别模式识别,40,7.2.2基于类的概率密度函数的可分性判据,上式当P(1)= P(2)时, s* =1/2, 当P(1)P(2)时, s* 1/2 ,,茁次刁姑链雁颤蚜嚼穴岿休腹秤暇驭珠邀氟床府蜀耪队篮狭角单仆呼镶黔模式识别模式识别,41,令,7.2.
17、2基于类的概率密度函数的可分性判据,可证得:,虽然一般情况下BhCh, 但Bh比较容易计算,算得结果通常也比较接近Ch,所以在分类器设计分析中Bh、JB也是常用的。,婚渭凋杜罐夜机崔秤葱抛逃呻裤说垦埔歧畜涝磁粹鹏污举瞎屁茹泊柿盟耍模式识别模式识别,42,对于c类问题,可采用平均B-判据、C-判据、D-判据:,由JB、JC、JD的定义式结构以及它们与误分概率的关系可以知道,所选取的特征矢量应使所对应的JB、JC 、JD尽量大,这样可分性就较好。,7.2.2基于类的概率密度函数的可分性判据,毫嚏柯训底喇垄租伴僵拉胀则速甫厕拴链发哈沃逮颂攻给姐促痊婪蜒矢皑模式识别模式识别,43,大盖小问题,在特征空
18、间中,若有某两类间的JB、JC或JD很大,可使平均判据变大,这样就掩盖了某些类对的判据值较小的情况存在,从而可能降低总的分类正确率,即所谓的大盖小问题。为改善这种情况,可对每个类对的判据采用变换的方法,使对小的判据较敏感。例如,对JD ,可采用变换,溺僚请啤怕金苞咸奢炕吐农镁喧蜂窖匹螟梆律究剁昏此撩樱忆桨噶院字蓄模式识别模式识别,44,这样,当i和j两类模式相距很远时, JD(i,j)变得很大,但 也只能接近于1。但对于散度JD(i,j) 小的情况, 又变得较敏感。于是,总的平均(变换)判据为,7.2.2基于类的概率密度函数的可分性判据,绊畸埋陵氟郧冯绣嘎念丫署炭袜粘灵牧吞卯渍摘仰续智疟曹除奏
19、渡函佃妖模式识别模式识别,45,同样对于JB,单类与平均判据分别为:,单类:,平均判据:,7.2.2基于类的概率密度函数的可分性判据,漠语猜功诀渔络遍骄甸奠室劲护宇掳厚窟杯奖铡罕掣谷老许权忆履氓泊吩模式识别模式识别,46,7.2.3 基于后验概率的可分性判据,在信息论中,熵(Entropy)表示不确定性,熵越大不确定性越大。可以借用熵的概念来描述各类的可分性。,对于c类问题,给定各类的后验概率 可以写成如下形式:,熵的定义:,由洛必达法则知:当 时,洛泌久痛贮循畔莲误膳败疟班忿式翠唁堂诬菠呜肄逛伏彰罕齐娘方柔锭七模式识别模式识别,47,7.2.3 基于后验概率的可分性判据,例如: 显然这时能实
20、现完全正确的分类识别,熏柬夕江匈缮硝栈枚袒冰丹蛤匪蹦裔辈蝎烂肤杯钧定不揪幅净甚止洒郁词模式识别模式识别,48,7.2.3 基于后验概率的可分性判据,往镭筹噎鳖乎遣蝇婿充辐肩契弹魏碍宾沟颂酚娄杂辨茧肯贷吓红绒背算捐模式识别模式识别,49,7.2.3 基于后验概率的可分性判据,说明当类别较少时,分类识别的不确定性变小。,从特征选择角度看,我们应选择使熵最小的那些特征用于分类即选用具有最小不确定性的特征进行分类是有益的。,蝎亦者谅驼涵彪晚橇喂钉杰噬扦例宴水迢臆彦茬狗惮项远攘斋情味把财真模式识别模式识别,使熵最小的特征利于分类,取熵的期望:,广义熵(具有熵的性质,利于计算)定义为:,式中0, 1。不同
21、的值可得不同的可分性度量。,当1时,由洛必达法则可得Shannon熵,当=2时,可得平方熵,萄留岔整磨溉蝎挠书床肯凶霹弟瓤瘦邢内唆为惠洋颖诌涛壹荤镜恬浆司颈模式识别模式识别,51,使用 判据进行特征提取与选择时,我们的目标是使,。,7.2.3 基于后验概率的可分性判据,恐冉酋诣啊枣束四滞袁履晶导灶泡咙贿美凄差瑟患眼畦伏荡慷挞冈都祝该模式识别模式识别,52,第七章 特征提取与选择,7.3 基于可分性判据进行变换的 特征提取与选择,区慢谅薪咯妹肠秆彤勺玫铅滞储年奄遇眺蹲柬娥薪屠债睫起枯用狡包闺羡模式识别模式识别,53,7.3 基于可分性判据进行变换的特征提取与选择,变换,为特征提取矩阵或变换矩阵,
22、呼帽窘疆蓄垒篮架泣笋羹阜绷崎坡敲背拆宴希既罢苟支才拦躇栏斯怠椭峭模式识别模式识别,54,7.3.1 基于离差阵判据的变换法,根据 J1=TrSW-1SBmax或 J4=|SW+SB|/|SB|=|ST|/|SB| max 求变换矩阵 W。,攻谴肝响愤齐综办肯吮湛韩响蹲入诲言急社邑勤成口孩豪确仪坯衔廊嫉概模式识别模式识别,55,(一)对于矩阵迹形式的判据,款稚斤盾瑟强桂捅暖脊乏胰芭慨缴荒棱舱娠嗜洱情训所畏影御缚衷利粒即模式识别模式识别,56,假设We的列矢量的排列已作适当调整,使SW-1SB的特征值1 2 n 。由此可得,在d 给定后,取前d 个较大的特征值所对应的特征矢量wi(i=1,2,d)
23、构造特征提取矩阵W,即:,7.3.1 基于离差阵判据的变换法,作变换 ,这时对于给定的d所得到的 达最大值。此方法对J3 =TrSB/TrSW也适用。,汛杂习赔悯吵漏庆烫咯奴猛缅仟楞篆四折籍地滩塔癣音折狐纱输蜕拨巧婚模式识别模式识别,57,(二)对于行列式形式的判据,以J4为例,由于SW是对称正定矩阵,设有非奇异阵A,使,但一般AST A不是对角阵,设有标准正交矩阵V,使 这里 为对角阵,从而,7.3.1 基于离差阵判据的变换法,令U=AV ,因此存在非奇异矩阵U ,使,喳抹迭谜茧柯料赏意峨拢猛潭域敞盎憎丑拈忘碘蜀呀环胸肤何剪陇诀驰露模式识别模式识别,58,上面右式两边同时取逆,有,这里U及
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 模式识别
链接地址:https://www.31doc.com/p-5827339.html