模式識(shí)別與人工智能

1、Pattern Recognition & artificial IntelligenceLecture 2: 特征選擇與提?。ㄒ唬?主要內(nèi)容,1.引言2 類別可分離性判據(jù)3 特征選擇4.特征提取,,1.引言,【問(wèn)題的提出】,,【問(wèn)題的提出】,,【問(wèn)題的提出】,【問(wèn)題的提出】,方案2.強(qiáng)調(diào)分析不同截面的信號(hào)，如在框架的若干部位沿不同方向截取截面分析從背景到字，以及從字到背景轉(zhuǎn)換的情況,如AB截面切割字符三次，CD截

2、面切割字符一次等。,【問(wèn)題的提出】,例 用RGB顏色空間和HSI顏色空間,【問(wèn)題的提出】,【問(wèn)題的提出】,【問(wèn)題的提出】,【概念】,【概念】,,【概念】,,2 類別可分離性判據(jù),【概念】,特征選擇與提取的任務(wù)是找出一組對(duì)分類最有效的特征，因此需一準(zhǔn)則。,概念：數(shù)學(xué)上定義的用以衡量特征對(duì)分類的效果的準(zhǔn)則實(shí)際問(wèn)題中需根據(jù)實(shí)際情況人為確定。,誤識(shí)率判據(jù)：理論上的目標(biāo)，實(shí)際采用困難（密度未知，形式復(fù)雜，樣本不充分，…）,可分性判據(jù)：實(shí)用的可計(jì)算

3、的判據(jù),【概念】,(1) 與誤判概率(或誤分概率的上界、下界)有單調(diào)關(guān)系。,(2) 當(dāng)特征相互獨(dú)立時(shí)，判據(jù)有可加性，即 ：,,類可分別判斷函數(shù),【概念】,,(3) 判據(jù)具有“距離”的某些特性，即 ：,(4) 對(duì)特征數(shù)目是單調(diào)不減，即加入新的特征后，判 據(jù)值不減。,類可分別判斷函數(shù),【概念】,19,,值得注意的是：上述的構(gòu)造可分性判據(jù)的要求，即“單調(diào)性”、“疊加性”、“距離性”、“單調(diào)不減性”。在實(shí)際應(yīng)用并不一定能同時(shí)具備，但并不影響它在

4、實(shí)際使用中的價(jià)值。,類可分別判斷函數(shù),類可分別判斷依據(jù)的常用方法：基于幾何距離的可分性判據(jù)基于概率密度的可分性判據(jù)基于熵的類可分性判據(jù),基于幾何距離的類可分離判據(jù),一般來(lái)講，不同類的模式可以被區(qū)分是由于它們所屬類別在特征空間中的類域是不同的區(qū)域。顯然，區(qū)域重疊的部分越小或完全沒(méi)有重疊，類別的可分性就越好。因此可以用距離或離差測(cè)度（散度）來(lái)構(gòu)造類別的可分性判據(jù)。,基于幾何距離的類可分離判據(jù),(一) 點(diǎn)與點(diǎn)的距離,(二) 點(diǎn)

5、到點(diǎn)集的距離,用均方歐氏距離表示,基于幾何距離的類可分離判據(jù),(三) 類內(nèi)及總體的均值矢量,各類模式的總體均值矢量,類的均值矢量：,為相應(yīng)類的先驗(yàn)概率，當(dāng)用統(tǒng)計(jì)量代替先驗(yàn)概率時(shí)，總體均值矢量可表示為：,基于幾何距離的類可分離判據(jù),,(四) 類內(nèi)距離,,,類內(nèi)均方歐氏距離,類內(nèi)均方距離也可定義為：,,基于幾何距離的類可分離判據(jù),,,,,(五) 類內(nèi)離差矩陣,顯然,(六) 兩類之間的距離,基于幾何距離的類可分離判據(jù),,,,,(七)各類模

6、式之間的總的均方距離,當(dāng)取歐氏距離時(shí)，總的均方距離為,基于幾何距離的類可分離判據(jù),,,,,(八) 多類情況下總的類內(nèi)、類間及總體離差矩陣,類內(nèi)離差,類間離差,總體離差,易導(dǎo)出,各模式之間總的均方距離,基于幾何距離的類可分離判據(jù),,,,,基于幾何距離的類可分離判據(jù),,,,,在特征空間中，當(dāng)類內(nèi)模式較密聚，而不同類的模式相距較遠(yuǎn)時(shí)，從直覺(jué)上我們知道分類就較容易，由各判據(jù)的構(gòu)造可知，這種情況下所算得的判據(jù)值也較大。由判據(jù)的構(gòu)造我們還可以初步

7、了解運(yùn)用這類判據(jù)的原則和方法。,選擇原則：,ii. 計(jì)算簡(jiǎn)單，易于實(shí)現(xiàn)。,iii. 數(shù)學(xué)上容易處理。,準(zhǔn)則函數(shù)的遞推計(jì)算問(wèn)題:每增/減一個(gè)特征，只影響向量中的一個(gè)元素，矩陣的一行和一列。,i. 實(shí)際分類問(wèn)題需要，找與分類性能關(guān)系密切者。,基于幾何距離的類可分離判據(jù),基于概率分布的可分性判據(jù),考查兩類分布密度之間的交疊程度,基于概率分布的可分性判據(jù),32,可用兩類概密函數(shù)的重疊程度來(lái)度量可分性，構(gòu)造基于類概密的可分性判據(jù)。此處的所謂重疊程

8、度是指兩個(gè)概密函數(shù)相似的程度。,,基于概率分布的可分性判據(jù),基于概率分布的可分性判據(jù),證明：設(shè),為誤分概率，則最小誤分概率為：,基于概率分布的可分性判據(jù),（二）,Chernoff,判據(jù),(,),,,,基于概率分布的可分性判據(jù),,,,JC 具有如下性質(zhì)：,,基于概率分布的可分性判據(jù),,,,JC 具有如下性質(zhì)：,基于概率分布的可分性判據(jù),,,,Jc 性質(zhì)（1）證明：,考慮函數(shù) f(s) = sa+(1-s)b- asb1-s (a,b

9、>0),因?yàn)椋?dāng) 0? s ? 1 時(shí) f ’’(s) = -asb1-s(ln a - ln b)2 < 0 (a?b),且 f(0)=f(1) = 0，從而有 f(s)?0。由該不等式有：,基于概率分布的可分性判據(jù),,,,Jc 性質(zhì)（2）證明：,只考慮連續(xù)的情況：因?yàn)閒(0)=f(1) = 0 ，當(dāng) 0? s ? 1 時(shí),f ’(s) = a-b-asb1-s (ln a - ln b)=0 ? a=b

10、,從而有 f’(s)=0 ? a=b ，由此有：,JC=0 ?,基于概率分布的可分性判據(jù),,,,Jc 性質(zhì)（5）證明：,設(shè)P(e)為最小誤分概率，則：,利用不等式 ，由上式進(jìn)一步可得：,基于概率分布的可分性判據(jù),,,,由JB和JC的定義知：JB=JC(1/2),,對(duì)兩類都是正態(tài)分布情況:,,,,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,基于概率分布的可分性判據(jù)

11、,,,,,,,,,,,,,,,,,,,,實(shí)際上,這就啟發(fā)我們運(yùn)用兩個(gè)概密的比或差來(lái)描述兩個(gè)概密重迭或相似的程度。,,可以寫(xiě)成：,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,(三)散度JD (Divergence),?i類對(duì)?j類的平均可分性信息為：,?j 對(duì)?i 類的平均可分性信息為：,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,(三)散度JD (Divergence),對(duì)于?i 和?j 兩類

12、總的平均可分性信息稱為散度，其定義為兩類平均可分性信息之和，即,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,(三)散度JD (Divergence),當(dāng)兩類都是正態(tài)分布時(shí)：,當(dāng)Ci=Cj=C時(shí),,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,散度具有如下性質(zhì)：,(1) JD ? 0；,(2) 對(duì)稱性: JD(?1 , ?2)= JD(?2 , ?1);,(3),(4) 當(dāng)x 各分量x1,x2,…

13、,xn相互獨(dú)立時(shí)，(具有可加性),(5) 當(dāng)x各分量x1,x2,…,xn相互獨(dú)立時(shí)，(對(duì)特征數(shù)目單調(diào)不減),基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,一般情況下，散度與誤分概率(或其上下界)之間的直接解析關(guān)系很難得到，但實(shí)驗(yàn)可以證明它們之間存在著單調(diào)關(guān)系。例如兩類都是正態(tài)分布，且有相同的協(xié)方差陣時(shí)， 是 的單調(diào)減函數(shù)。,當(dāng)兩類先驗(yàn)概率相等且為具有相同協(xié)方差的正態(tài)分布時(shí)，則最小誤分概率與 的關(guān)系為：,基

14、于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,對(duì)于c類問(wèn)題，可采用平均B-判據(jù)、C-判據(jù)、D-判據(jù)：,由JB、JC、JD的定義式結(jié)構(gòu)以及它們與誤分概率的關(guān)系可以知道，所選取的特征矢量應(yīng)使所對(duì)應(yīng)的JB、JC 、JD盡量大，這樣可分性就較好。,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,大蓋小問(wèn)題,在特征空間中，若有某兩類間的JB、JC或JD很大，可使平均判據(jù)變大，這樣就掩蓋了某些類對(duì)的判據(jù)值較小的情

15、況存在，從而可能降低總的分類正確率，即所謂的大蓋小問(wèn)題。為改善這種情況，可對(duì)每個(gè)類對(duì)的判據(jù)采用變換的方法，使對(duì)小的判據(jù)較敏感。例如，對(duì)JD ，可采用變換：,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,這樣，當(dāng)?i和?j兩類模式相距很遠(yuǎn)時(shí)，JD(?i,?j)變得很大，但 也只能接近于1。但對(duì)于散度JD(?i,?j) 小的情況， 又變得較敏感。于是，總的平均(

16、變換)判據(jù)為 ：,基于概率分布的可分性判據(jù),,,,,,,,,,,,,,,,,,,,,同樣對(duì)于JB，單類與平均判據(jù)分別為：,單類：,平均判據(jù)：,熵可分性判據(jù),熵可分性判據(jù),對(duì)于c類問(wèn)題，給定各類的后驗(yàn)概率 可以寫(xiě)成如下形式：,熵的定義：,由洛必達(dá)法則知：當(dāng) 時(shí),,熵可分性判據(jù),例如：顯然這時(shí)能實(shí)現(xiàn)完全正確的分類識(shí)別,熵可分性判據(jù),,熵可分性判據(jù),說(shuō)明當(dāng)類別較少時(shí)，分類識(shí)別的不確定性變小。

17、,從特征選擇角度看，我們應(yīng)選擇使熵最小的那些特征用于分類即選用具有最小不確定性的特征進(jìn)行分類是有益的。,熵可分性判據(jù),使熵最小的特征利于分類，取熵的期望：,廣義熵（具有熵的性質(zhì)，利于計(jì)算）定義為:,式中?>0， ??1。不同的?值可得不同的可分性度量。,當(dāng)??1時(shí)，由洛必達(dá)法則可得Shannon熵,當(dāng)?=2時(shí)，可得平方熵,熵可分性判據(jù),使用 判據(jù)進(jìn)行特征提取與選擇時(shí)，我們的目標(biāo)是使,小 結(jié),可分性判據(jù)：距離：類內(nèi)