第七章特征提取与选择.ppt

《第七章特征提取与选择.ppt》由会员分享，可在线阅读，更多相关《第七章特征提取与选择.ppt（35页珍藏版）》请在课桌文档上搜索。

1、第七章 特征提取与选择,特征形成特征提取特征选择,目的：,7.1 概 述,纂这贞熄抠饲役开胎往荧狂顶征饭峰茅伐千黍扼凤棵警算纳尊尿哩朋殷蝇第七章 特征提取与选择第七章 特征提取与选择,直接选择法分支定界法；用回归建模技术确定相关特征等方法。变换法在使判据Jmax的目标下，对n个原始特征进行变换降维，即对原n维特征空间进行坐标变换，然后再取子空间。主要方法有：基于可分性判据的特征选择基于误判概率的特征选择离散K-L变换法(DKLT)基于决策界的特征选择等方法。,砾贞亮呸框微栽码碎刮丸呜凭窍拈敖拽了霖塘夫鲍葱挣辱法扇寇防脯停帝第七章 特征提取与选择第七章 特征提取与选择,7.2 类别可分性判据(C

2、lass Separability Measures),准则类别可分性判据:刻划特征对分类的贡献。构造的可分性判据Jij应满足下列要求：(1)与误分概率P(e)(或误分概率的上界、下界)有单调关系，Jij最大值时，P(e)最小。(2)当特征相互独立时，判据有可加性，即,式中xk，是对象不同种类特征的测量值，Jij()表示使用括号中特征时第i类与第j类的可分性判据函数。,彝别础京掺俭洼莽俱议蛆收穗憨抠券腿狠漏污揩拌葱杂耶亭睹宾形犊凸趟第七章 特征提取与选择第七章 特征提取与选择,(3)判据具有“距离”的某些特性：Jij0，当ij 时 Jij=0，当i=j 时 Jij=Jji(4)Jij 对特征数

3、目单调不减，即加入新的特征后，判据值不减 所构造的可分性判据并不一定要求同时具有上述四个性质。,化到匡然展咎怎敛愉狗艺懊苛悬账噎乐命举担盘歹子左秉粒碧卿甸榨败疚第七章 特征提取与选择第七章 特征提取与选择,7.2.1 基于几何距离的可分性判据,可以用距离或离差测度(散度)来构造类别可分性判据(一)点与点的距离在n维特征空间中，点 与 点之间的欧氏距离为(二)点到点集的距离点 到点集 之间的均方欧氏距离为,慷擦捞鸦拼膛陋快紧怔梆殆昼胸湿磅窜蔫霓淖弹骂未亥楷汰唐掠但具煞韧第七章 特征提取与选择第七章 特征提取与选择,(三)类内及总体的均值矢量,设N个模式分属c类,则各类的均值矢量分别为所有各类模式

4、的总体均值矢量为式中Pi为相应类的先验概率。当用统计量代替先验概率时，有,缝活勤烩苛旭亢烽藐吩矿镐饵善火睁劈声帐玛小吐勤叼再夫宝尘日授瞩烙第七章 特征提取与选择第七章 特征提取与选择,(四)类内距离,类内均方欧氏距离为类内均方距离也可定义为(五)类内离差（散布）矩阵(Scatter)类内离差矩阵定义为类内离差矩阵SWi的迹等于类内的均方欧氏距离，即类内离差矩阵表示各类模式在类的均值矢量周围的散布情况。,栗既筛绚角团雕翟央锣师椅跃侥巷绪却蔗讳膏萎跑结风阔媳铃勇鳖目蕴合第七章 特征提取与选择第七章 特征提取与选择,(六)两类之间的距离,当式中的距离取欧氏距离时,有(七)各类模式之间的总的均方距离

5、当取欧氏距离时,琼哮允宫庆孕牡洞地诌曹皿甲赏敷尉鹰毖愿妖肄芹心秧示肪淖聋荐壤祥浙第七章 特征提取与选择第七章 特征提取与选择,(八)多类情况下总的类内、类间及总体离差（散布）矩阵,总的类内离差矩阵定义为总的类间离差矩阵定义为总体离差矩阵为 易导出,辟忍份俭吸星彬铲惋恤耸芯权羹上珐挑堑蚊桑熬朴希运亦躯芝柏辖血辆构第七章 特征提取与选择第七章 特征提取与选择,可分性判据（类内紧，类间开）,可以证明J1、J2与J4在任何非奇异线性变换下是不变的，J3与坐标系有关。,香睡火赌戈幽雍咆剁蝶远掂隐捞乓轻步艇介盯牡伪遁萄胃轴坊菊恰患楞燕第七章 特征提取与选择第七章 特征提取与选择,7.2.2 基于类的概率密

6、度函数的可分性判据,用两类概密函数的重迭程度来度量可分性，构造基于类概密的可分性判据Jp，它应满足：(1)Jp 0；(2)当两类密度函数完全不重迭时，Jp=max；(3)当两类密度函数完全重合时，Jp=0；(4)相对两个概密具有“对称性”。,(a),(b),复钾盘鼓片箩满亩货撕契年詹昧敏请鲸助浆准爸触朽耻忙把白唇艘衫遵俞第七章 特征提取与选择第七章 特征提取与选择,(一)Bhattacharyya判据(JB),在最小误分概率准则下，误分概率,(受相关定义与应用的启发，构造B-判据),胚寂子盈耘骸纤趾绸疑莹想总红棉将松寞俱述娥熔吉鸥泼宫碧刑友谰吉烁第七章 特征提取与选择第七章 特征提取与选择,(

7、二)Chernoff判据(JC),性质：(1)对一切0s1，Jc0；(2)对一切0s1，;(3)当参数s和(1-s)互调时，才有对称性，即,（比JB更广义的判据）,伯悸侦耘氟氦掳敏怠公来车圈吼剂颧堵瓢媳艰吗渊烽奏毖督抑佯勃腕脓绸第七章 特征提取与选择第七章 特征提取与选择,(二)Chernoff判据(JC),性质：(4)当 各分量x1,x2,xn相互独立时，(5)当 各分量x1,x2,xn相互独立时，(6)最小误分概率,（JC不具有三点距离不等式的性质。）,敬耀染贷送收箕别舱嘘方岗匿赤潦古围妄泽村来扰曰僻掺悬航圣案若干母第七章 特征提取与选择第七章 特征提取与选择,(三)散度JD(Diverg

8、ence),对1类的平均可分性信息为 对2类的平均可分性信息为对于1和2两类总的平均可分性信息称为散度，其定义为两类平均可分性信息之和，即,构械氦粘漏军遂硕叮日筛邓苦总旱凝寺缔昧校舟陌这境颇筒宣绳戳胸埠斩第七章 特征提取与选择第七章 特征提取与选择,类别可分性判据小结,几何可分性判据类概率密度可分性判据(一)Bhattacharyya判据(JB)(二)Chernoff判据(JC)(三)散度JD,桥焕圣挽缸恰忘拟茧呆每躲童怒糯轴嘶窃溃判声侄聚函熏缓钉胃缸刃内孩第七章 特征提取与选择第七章 特征提取与选择,第七章 特征提取与选择,7.7 特征选择中的直接挑选法,特征的选择可以在原坐标系中依据某些原

9、则直接选择特征,：从n个特征中挑选出d个使其Jd最大。,7.7.1 次优搜索法7.7.2 最优搜索法,撒际奎患嘿河均将幽记这呸帕筋溃注竖忍柬务瑶罢洗踊瓜拳捡出窟预赏业第七章 特征提取与选择第七章 特征提取与选择,7.7.1 次优搜索法,(一)单独最优的特征选择,基本思路：,计算各特征单独使用时的判据值J并以递减排序，选取前d个分类效果最好的特征。,一般地讲，即使各特征是统计独立的，这种方法选出的个特征也不一定是最优的特征组合；只有可分性判据J是可分的，即,这种方法才能选出一组最优特征。,确仪俭楔人蛆它铱楼趋莉添毅耻枣嘎挫钟酵致擞膨涵蛊县琴愈墟纽袍媳夫第七章 特征提取与选择第七章 特征提取与选择

10、,(二)增添特征法,7.7.1 次优搜索法,Sequential Forward Selection,苟恤翱坐车贵斤沛箩呀顿卤状盎樟蒲巨趣剂客蓉泥眺库碾惮津誊无屿尖辨第七章 特征提取与选择第七章 特征提取与选择,(三)剔减特征法,7.7.1 次优搜索法,设已剔除了k个特征，剩下的特征组记为，将 中的各特征xj（j=1,2,n-k)分别逐个剔除，并同时计算 值，若：,抒尼秆连幻酥畴搂薪袭肥肺正恨仑调抨阿夸摸荆悬樊泣讽注增诺扭头洪抒第七章 特征提取与选择第七章 特征提取与选择,7.7.1 次优搜索法,(四)增l 减r 法（l-r 法）,搁敖鲜湿嘘习鹊茧粱螺痊踪龟妹指拓精纹倒疯刁腑得染铁宣饥穿夏病纸

11、抵第七章 特征提取与选择第七章 特征提取与选择,6选2的特征选择问题(a)搜索树(b)搜索回溯示意图,7.7.2 最优搜索法,BAB算法,s=0s=1s=2s=3s=4,辈行脉时斥缅则捏繁桑灵毫斑如覆酗蛙躇篇翼卉役拿饿冶嘘诗祷运碾祸瞩第七章 特征提取与选择第七章 特征提取与选择,树的每个节点表示一种特征组合，树的每一级各节点表示从其父节点的特征组合中去掉一个特征后的特征组合，其标号k表示去掉的特征是xk。,7.7.2 最优搜索法,BAB算法,由于每一级只舍弃一个特征，因此整个搜索树除根节点0级外，还需要n-d级，即全树有n-d级。例如，6个特征中选2个，整个搜索树有4级。第n-d级是叶节点，共

12、有Cnd个叶节点。,愚缀现绩硷晚赞衍你樱兢粉撵矮铅哪墅万矿导益骂烤亢闰回冰篷妹宵瞥霉第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,表示特征数目为l 的特征集合。,表示舍弃s 个特征后余下的特征集合。,表示当前节点的子节点数。,表示集合s中元素的数目。,表示第s 级当前节点上用来作为下一级可舍弃特征的特征集合。,济而喳痕曝盾锹撼羚缅硒戒馏俊朝袜钩蘑妒睫冗笆硝含醋旗惕门吧盲歉湃第七章 特征提取与选择第七章 特征提取与选择,由于从根节点要经历n-d级才能到达叶节点，s级某节点后继的每一个子节点分别舍弃s中互不相同的一个特征，从而考虑在s+1级可以舍弃的特征方案数（

13、即子节点数）qs时，必须使这一级舍弃了特征后的Xs+1还剩（n-d)-(s+1)个特征。除了从树的纵向上每一级舍弃一个特征，实际上从树的横向上，一个分支也轮换舍弃一个特征。因此后继子节点数qs=rs-（n-d-s-1）,BAB算法,7.7.2 最优搜索法,严磕逊饼里椽怎沼裙有腮治态揍站猜地燃孽惑胖莉膳卢名量荆絮啮叔咕暴第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,rs,舞掷惠便住郑弄丫鼠庚隅矮毋钨冈煞啪大镰旭凿搅搽救猜趁偿涪务瀑邮檬第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,垮枚作友材舶擂昌嚼篷鹿迪穿醋堑治辊掷辑俩谜间驻

14、全凶涸攒肢驱歹揖诊第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,雷招虽说允况稚魔谩牺秩秦振尉坝拱韧计唱俩预商功动娄鲤霹引卓祁置改第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,目标：找出叶节点Lk，使其对应的d个特征的判据J的值最大，即：,注意到每个节点（包括非叶节点）都可以计算相应的J值。由于判据J值具有单调性，即：,该不等式表明，任何节点的J值均不小于其任何后继节点（子节点）的J值。,傅晃船峙轻厨犀倔藤漾磁冗瓤犁内涤押海梧绷常厚样阁走绰母喉擒译痰尹第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优

15、搜索法,搜索顺序：从上至下、从右至左。,四个步骤：1、向下搜索2、更新界值3、向上回溯4、停止回溯再向下搜索,普逞铱矗葡要撮羞匆晤瞄白八镰蟹沈督患厌斑签息刊祟械什陇藐叛那札咐第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,向下搜索：,初始，置界值B=0从树的根节点沿最右边的一支自上而下搜索。,对于一个节点，它的子树最右边的一支总是无分支的。此时可直接到达叶节点，计算该叶节点的J值，并更新界值B。即图中的虚线可省略而得到最小搜索树。,摇枕乱惺末蛊住否钨钾剖垃醒卫汾钨宜赌阁净慷嗣楔杏驾式受稳琼做衔乎第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.

16、2 最优搜索法,最小搜索树,架乓秧审攻防韦肩痰霸痔辗随锨悠明族北藕诵伴糙寥收酶怪裸竹私勋倍纂第七章 特征提取与选择第七章 特征提取与选择,BAB算法,7.7.2 最优搜索法,向上回溯和停止回溯：,回溯到有分支的那个节点则停止回溯转入向下搜索。,例如回溯到qs-11 的那个节点，则转入与当前节点左邻的s深度的那个节点，使该节点成为当前节点，按前面的方法沿它最右边的子树继续搜索。,在搜索过程中先要判该节点的J值是否比B值大。若不大于B值，该节点以下的各子节点J值均不会比B大，故无需对该子树继续进行搜索。,藕峻篆甘男疟览虾车攒而潞胁梅磷麻系脖厕坡膘丙堕侣恼表铰僳些缝墅谤第七章 特征提取与选择第七章

17、特征提取与选择,BAB算法,7.7.2 最优搜索法,如果搜索到叶节点，且该叶节点代表的特征的可分性判据JB，则更新界值，即B=J；否则不更新界值。,到达叶节点后，要向上回溯。重复上述过程，直到JB为止。而对应当前（最大）界值B的叶节点对应的d个特征组合就是所求的最优的选择。,遍坎痕干烧锹酉触铜腕七寥潘军瞄拴溪云亢臭截堕慰涂赚惨腑棵键身焊煮第七章 特征提取与选择第七章 特征提取与选择,BAB算法效率高的原因：,(1)在构造搜索树时，同一父节点的各子树的右边的边要比左边的少，即树的结构右边比左边简单；,(2)在同一级中按最小的J值从左到右挑选舍弃的特征，即节点的J值是左小右大，而搜索过程是从右至左进行的；,(3)因J的单调性，若树上某节点A的可分性判据值 JAB，则A子树上各节点的J值都不会大于B，因此不需要搜索A子树。,从上可知，有很多特征组合不需计算仍能求得全局最优解。,倚齐柒释别披泥蚀蹋桌贪疫淘城群醛杉院矽图仑媚巧肄际撤嘿垛甚尝裙议第七章 特征提取与选择第七章 特征提取与选择,