模式特征的提取與選擇

模式特征的提取與選擇第一頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇在一個較完善的模式識別系統(tǒng)中，或者明顯地或者隱含地要有特征提取與選擇技術(shù)環(huán)節(jié)，通常其處于對象特征數(shù)據(jù)采集和分類識別兩個環(huán)節(jié)之間，特征提取與選擇方法（或質(zhì)量）的優(yōu)劣極大地影響著分類器的設(shè)計和性能，它是模式識別的核心問題之一。第二頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述在實際問題中，常常不容易找到那些最重要的特征，或受條件限制不能對它們進行測量，這就使特征選擇和提取的任務(wù)復(fù)雜化而成為構(gòu)造模式識別系統(tǒng)最困難的任務(wù)之一。特征提取和選擇的基本任務(wù)是如何從許多特征中找出那些最易得且有效的特征,從而實現(xiàn)特征空間維數(shù)的壓縮.第三頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述雖然特征的提取和選擇在模式識別中占有重要地位,但迄今沒有一般方法,大多數(shù)的方法都是面向問題的.對于不同的模式識別問題可以有不同的特征提取和選擇方法,而且即使對于同一模式識別問題往往也可能用不同方法,所以要對這些方法作一般的評價是困難的.第四頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述模式特征并非提取得越多越好.在實際工作中,往往會發(fā)現(xiàn)當特征的數(shù)目達到某個限度后,不但不能改善分類器的性能,反而會使它的工作惡化.其原因在于用以設(shè)計分類器的樣本數(shù)目是有限的.為了使模式識別的結(jié)果滿意,在增加特征的同時,必須增加供學習的樣本數(shù)量.第五頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述(1)用一定數(shù)量的樣本估計出來的參數(shù)設(shè)計Bayes分類器時,隨著維數(shù)的增加要求樣本數(shù)急劇增加,這樣才能保證一定的錯誤率.第六頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述(2)在用線性判別函數(shù)來劃分模式空間時,一般要用一組樣本來決定劃分區(qū)域的超平面.當增加維數(shù)時,樣本數(shù)應(yīng)有更多的增加才能保持原有的超平面容度.第七頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述(3)在鄰近法與集群分析中,經(jīng)常應(yīng)用的是群內(nèi)離散度矩陣Sw,為了使用行列式準則,離散度矩陣必須是非奇異的,這就要求樣本數(shù)與群數(shù)之差應(yīng)遠大于維數(shù).第八頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述幾個基本概念特征形成:根據(jù)被識別的對象產(chǎn)生一組基本特征,它可以是計算出來的(當識別對象是波形或數(shù)字圖像時),也可以是用儀表或傳感器測量出來的(當識別對象是實物或某過程時),這樣產(chǎn)生出來的特征叫做原始測量(一次測量),原始測量的直接結(jié)果或間接結(jié)果稱為原始特征.第九頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述幾個基本概念特征提取:原始特征的數(shù)量可能很大,或者說樣本是處于一個高維空間中,通過映射(或變換)的方法可以用低維空間來表示樣本,這個過程叫特征提取.映射后的特征叫二次特征,它們是原始特征的某種組合.變換A:Y→X稱為特征提取器.第十頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇1概述幾個基本概念特征選擇:從一組特征中挑選出一些最有效的特征以達到降低特征空間維數(shù)的目的,這個過程叫特征選擇.有時特征提取和選擇并不是截然分開的，在具體的模式識別問題中也可以結(jié)合使用。第十一頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)把一個高維空間變換為低維空間的映射有很多，哪種映射對分類最有利，需要一個比較標準，即類別可分性判據(jù)，這些判據(jù)應(yīng)能反映各類在特征空間中的分布情況，應(yīng)能刻畫各特征分量在分類識別中的重要性或貢獻。以分類器的錯誤概率做為標準有難度.第十二頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)與錯誤概率(或其界限)有單調(diào)關(guān)系,使判據(jù)取最值時,錯誤概率也較小.當特征相互獨立時,判據(jù)具有可加性.判據(jù)須有度量特性(非負性,對稱性).自身有單調(diào)性(加入新特征時,判據(jù)不減小).類別可分性判據(jù)應(yīng)滿足的幾個要求:第十三頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)點與點的距離點到點集的距離類內(nèi)距離(類內(nèi)均方歐氏距離d2)類內(nèi)離差矩陣Sw(d2=Tr[Sw])兩類之間的距離各類間的總均方距離總的類內(nèi)類間及總體離差矩陣

ST=Sw+ST基于幾何距離的可分性判據(jù)第十四頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)J1=Tr[Sw-1SB]J2=Tr[SB]/Tr[Sw]J3=Tr[Sw-1ST]J4=|ST|/|SW|=|Sw-1ST|基于幾何距離的可分性判據(jù)上述各種判據(jù)存在關(guān)聯(lián)性,其中一些判據(jù)如J1,J4具有非奇異線性變換不變性.它們本質(zhì)相似,但性能可能不同.第十五頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)基本原則Jp非負.當兩類概率密度函數(shù)完全不重疊時,Jp趨于無窮大.當兩類概率密度函數(shù)完全重合時,Jp為零.相對于兩個概率密度具有對稱性.基于類概率密度函數(shù)的可分性判據(jù)第十六頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)判據(jù)舉例Bhattacharyya判據(jù)JB=-lnS[p(x|w1)p(x|w2)]1/2dxChernoff判據(jù)JC=-lnSp(x|w1)sp(x|w2)1-sdx散度(總的平均可分性信息)JD=I12(x)+I21(x)基于類概率密度函數(shù)的可分性判據(jù)第十七頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)I12(x)=E1{ln[p(x|w1)/p(x|w2)]}基于類概率密度函數(shù)的可分性判據(jù)I21(x)=E2{ln[p(x|w2)/p(x|w1)]}第十八頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇2類別可分性判據(jù)原理：選擇使后驗熵最小的那些特征用于分類識別。基于后驗概率的可分性判據(jù)JH=Ex[-Sp(wi|x)logp(wi|x)]JHs=Ex[Hs(p1,p2,…,pc)]Hs=(21-s-1)[S(pis)-1]pi=p(wi|x)第十九頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇3基于可分性判據(jù)進行變換的特征提取Sw和SB分別為原始特征空間中類內(nèi)和類間離差矩陣,Sw*和SB*分別為變換特征空間中類內(nèi)與類間離差矩陣基于離差矩陣的特征提取Sw*=WTSwWSB*=WTSBW第二十頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇3基于可分性判據(jù)進行變換的特征提取若W為非奇異矩陣,則J1=Tr[Sw-1SB]是不變的.基于離差矩陣的特征提取因此,只需求出[Sw-1SB]的所有特征值,選其較大的d個,以其特征向量為列向量構(gòu)造W即可使J1最大.第二十一頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇3基于可分性判據(jù)進行變換的特征提取由于Sw是對稱正定矩陣,故有非奇異矩陣A,使ATSwA=I,取U=AV,其中V為標準正交矩陣,則U為非奇異矩陣,且使UTSTU為對角陣.UTSwU為單位陣.從而可知U及UTSTU分別為Sw-1ST的特征矢量矩陣及特征值對角陣.進而可得J4為特征值的某種和,同理只需要針對較大的特征值構(gòu)造W即可.基于離差矩陣的特征提取第二十二頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇4最佳鑒別矢量的提取前面依據(jù)類內(nèi),類間及總離差矩陣構(gòu)造可分性判據(jù)求最佳變換矩陣,其特點是整個最佳坐標系在形式上是一起求出的,但也可以用單個分量的類間類內(nèi)距離比作為準則,逐個求出最佳坐標系的各軸矢量.第二十三頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇4最佳鑒別矢量的提取Fisher鑒別矢量及鑒別平面在設(shè)計分類器時,在適當保證分類識別正確率的條件下,為簡便或為可實現(xiàn)性,常要求降低維數(shù),或有時為便于顯示,常首先要求模式的維數(shù)是1或2,這就要求將目標的原始n維特征矢量映射成一維標量或二維矢量.第二十四頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇4最佳鑒別矢量的提取Fisher鑒別矢量及鑒別平面要將高維模式映射成二維模式,需要兩個正交矢量.這時除了Fisher鑒別矢量u1外,還要求出第二個矢量u2.因此可用u1Tu2=0作為約束條件使JF(u2)最大,即Z=max[(u2TSBu2)/(u2TSwu2)-ku1Tu2]第二十五頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇4最佳鑒別矢量的提取最佳鑒別矢量集設(shè)u1是使JF(ui)取最大的Fisher最佳鑒別矢量,且u1已規(guī)格化,其模長為1,則單位Fisher最佳鑒別矢量u1是F-Sammon最佳鑒別矢量集中的第一個矢量.該矢量集中的第i個鑒別矢量ui通過解一個最優(yōu)化問題而求得.第二十六頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇4最佳鑒別矢量的提取最佳鑒別矢量集

Max[JF(ui)]s.t.uiTuj=0,j=1,2,…,i-1.|ui|=1令U=(u1,u2,…,ur),則變換y=UTx稱為F-S變換(FST).Fisher是r=2特例.第二十七頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇5離散K-L變換Karhunen-Loeve變換取變換函數(shù):y=g(x).為使變換后的特征還能很好的體現(xiàn)原有特征,作估計量x(m)=SmyiWi+Sm+1biWiΔx(m)=x-x(m)e2(m)=E{|Δx(m)|2}對于不保留的那些分量,應(yīng)當用它們的平均值來代替,就能得到最佳的bi值.第二十八頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇5離散K-L變換Karhunen-Loeve變換為了進一步得到Wi,還需要在WiTWi=1的條件下,找出使e2(m)最小的Wi.為此使用拉格朗日乘數(shù)法即可.每個特征在代表x方面的有效性由與它相對應(yīng)的特征值所確定.盡可能保留特征值大的分量.x的協(xié)方差矩陣的特征向量使拉格朗日函數(shù)在正交歸一的基向量的所有選擇中最小.第二十九頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇6特征選擇中的直接挑選法次優(yōu)搜索法單獨最優(yōu)的特征選擇法計算各特征單獨使用時的判據(jù)值并以遞減排序,從而選取前d個分類效果最好的特征即可.即使各特征是統(tǒng)計獨立的,該法選出的特征也不一定是最優(yōu)的特征組合.第三十頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇6特征選擇中的直接挑選法次優(yōu)搜索法增添特征法(順序前進法SFS)是一種最簡單的自下而上的搜索方法,每次從未選入的特征中選擇一個特征,使它與已選入的特征組合在一起時J最大,直到選入特征數(shù)目達到指定的維數(shù)為止.一般好于單獨最優(yōu)選擇法,主要缺點是某特征一旦選入,就無法刪除.該法可推廣.第三十一頁，共三十四頁，編輯于2023年，星期六模式特征的提取與選擇6特征選擇中的直接挑選法次優(yōu)搜索法剔減特征法(順序后退法SBS)是一種最簡單的自上而下的搜索方法,從全部特征開始每次剔除一個特征,所剔除的特征應(yīng)使尚保留的特征組合的J最大.計算量大于增添特征法,可推廣.第三十二頁，