模式識別與人工智能

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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