1、2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)1,第四章 特征的選擇與提取,討論的問題是對已有的特征空間進(jìn)行改造，著重于研究對樣本究竟用什么樣的度量方法更好。使用什么樣的特征描述事物，也就是說使用什么樣的特征空間是個很重要的問題。這個問題稱之為描述量的選擇問題，又稱特征的優(yōu)化問題。,學(xué)習(xí)指南,對特征空間的改造、優(yōu)化、主要有兩種途徑。一種是刪選掉一些次要的特征，問題在于如何確定特征的重要性，以及如何刪選。另一種方法是使用變換的手段，在這里主要限定在線性變換的方法上，通過變換來實現(xiàn)降維。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)2,了解特征空間的選擇在設(shè)計

2、模式識別系統(tǒng)，解決模式識別具體問題中是至關(guān)重要的。,學(xué)習(xí)目的,了解描述量選擇，特征組合優(yōu)化的兩種基本方法，一是對原特征空間進(jìn)行刪選，另一種是通過變換改造原特征空間。,典型的運用線性變換對原特征空間優(yōu)化的基本方法，進(jìn)一步深入理解模式識別處理問題的基本方法確定準(zhǔn)則函數(shù)，并通過計算進(jìn)行優(yōu)化。,使用特征選擇方法的基本問題。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)3,本章重點,1、弄清對特征空間進(jìn)行優(yōu)化的含義。,2、對特征空間進(jìn)行優(yōu)化的兩種基本方法特征選擇與特征的組合優(yōu)化。,3、對特征空間進(jìn)行優(yōu)化的一些常用判據(jù)。,4、利用線段變換進(jìn)行特征空間優(yōu)化的基本方法。,2020/7/12

3、,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)4,1、要透徹理解什么叫特征空間的優(yōu)化，為什么要對特征空間進(jìn)行優(yōu)化。,2、對特征空間進(jìn)行優(yōu)化，要用到一些數(shù)學(xué)工具，如向量點積、線性變換、正交變換、解決條件極值問題的拉格朗日乘子方法等。,本章難點,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)5,1、什么叫特征空間？如果我們用顏色、尺寸、重量來衡量水果的構(gòu)造的特特空間是幾維空間？,2、如果用顏色、尺寸與重量組成的特征空間來區(qū)分蘋果與梨，你認(rèn)為這三種度量中的哪種最有效？為什么？能否想像這兩種水果在這個三維空間的分布？如果用這個特征空間來區(qū)分紅蘋果與櫻桃，你想像一下這兩類水果在特征空間

4、如何分布？能否對這兩種情況設(shè)計更經(jīng)濟有效的特征空間？,課前思考題,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)6,3、如果兩類物體在一個二維特征空間如圖分布,能否用刪除其中任一維來優(yōu)化特征空間？有沒有什么方法能得到一個對分類很有利的一維特征空間？,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)7,4、上題的答案可用下圖Y1與Y2組成的空間表示？你認(rèn)為哪個分量可以刪掉？,5、有沒有辦法將原在X1、X2空間表示的數(shù)改成用Y1、Y2空間表示？,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)8,4.1 基本概念,特征空間如何設(shè)計的問題,如何確定合

5、適的特征空間是設(shè)計模式識別系統(tǒng)另一個十分重要，甚至更為關(guān)鍵的問題。如果所選用的特征空間能使同類物體分布具有緊致性，即各類樣本能分布在該特征空間中彼此分割開的區(qū)域內(nèi)，這就為分類器設(shè)計成功提供良好的基礎(chǔ)。反之，如果不同類別的樣本在該特征空間中混雜在一起，再好的設(shè)計方法也無法提高分類器的準(zhǔn)確性。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)9,對要識別的事物用什么方法進(jìn)行描述、分析的問題。有以下幾個不同的層次：,1、物理量的獲取與轉(zhuǎn)換,對從傳感器中得到的信號，可以稱之為原始信息。,2、描述事物方法的選擇與設(shè)計,在得到了原始信息之后，要對它進(jìn)一步加工，以獲取對分類最有效的信息。設(shè)計

6、所要信息的形式是十分關(guān)鍵的。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)10,設(shè)計對事物的描述方法是充分發(fā)揮設(shè)計者智慧的過程，這個層次的工作往往因事物而易，與設(shè)計者本人的知識結(jié)構(gòu)也有關(guān)。這是一個目前還無法自動進(jìn)行的過程。,例：印刷體數(shù)字識別,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)11,3、特征空間的優(yōu)化,已有了一個初始的特征空間，如何對它進(jìn)行改造與優(yōu)化的問題。一般說來要對初始的特征空間進(jìn)行優(yōu)化是為了降維。即初始的特征空間維數(shù)較高。能否改成一個維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化后的特征空間應(yīng)該更有利于后續(xù)的分類計算。,2020/7/12,中國礦業(yè)大學(xué)

7、計算機科學(xué)與技術(shù)學(xué)院,(28)12,例：用RGB顏色空間和HSI顏色空間,上圖中右邊是原始圖像，左邊是用HSI空間描述的同一圖像(但是為了顯示出來，用H對應(yīng)R，S對應(yīng)G，I對應(yīng)B，然后再以RGB的方式顯示出來)。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)13,確定特征空間包括若干層次：,把物體所具有的物理性質(zhì)，結(jié)構(gòu)性質(zhì)等轉(zhuǎn)換成計算機能處理的數(shù)學(xué)描述量。,使用傳感器對樣本的物理及其它屬性進(jìn)行轉(zhuǎn)換與度量可得到對樣本的原始度量。然而原始度量需要進(jìn)一步轉(zhuǎn)換成有效的特征。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)14,對特征空間進(jìn)行優(yōu)化有兩種基本方法,1、

8、特征選擇 ：刪掉部分特征,已有D維特征向量空間：,xiyj,2、特征的組合優(yōu)化 ：通過一種映射，說新的每一個特征是原有特征的一個函數(shù)。,已有D維特征向量空間：,找到一個映射關(guān)系： A:YX,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)15,思考題,1、研究模式識別中事物的描述方法主要靠什么？,其中若y1= x1 ， y2= x3 ，屬哪一種方法：特征選擇還是組合優(yōu)化。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)16,4.2 類別可分離性判據(jù),討論的評價方法目的在于找出對特征空間進(jìn)行優(yōu)化的具體算法。,對特征空間進(jìn)行優(yōu)化是一種計算過程：,找到一種準(zhǔn)則(或稱

9、判據(jù))，通常用一種式子表示；計算出一種優(yōu)化方法，使這種計算準(zhǔn)則達(dá)到一個極值。,判據(jù)：與計算錯誤率有關(guān)的判據(jù),實用性強的判據(jù),(1) 基于距離的可分性判據(jù)：計算樣本在特征空間離散程度,(2) 基于概率密度分布的判據(jù),2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)17,4.3 按距離度量的特征提取方法,基于距離度量是人們常用來進(jìn)行分類的重要依據(jù)，因為一般情況下同類物體在特征空間呈聚類狀態(tài)，即從總體上說同類物體內(nèi)各樣本由于具有共性，因此類內(nèi)樣本間距離應(yīng)比跨類樣本間距離小。,Fisher準(zhǔn)則正是以使類間距離盡可能大同時又保持類內(nèi)距離較小這一種原理為基礎(chǔ)的。,同樣在特征選擇與特征提取中

10、也使用類似的原理，這一類被稱為基于距離的可分性判據(jù)。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)18,4.3.1 基于距離的可分性判據(jù),度量類內(nèi)、類間的距離，可用描述樣本的離散程度的方法。,回顧Fisher準(zhǔn)則中的各種距離定義：,類間離散度矩陣：,類內(nèi)離散度矩陣：,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)19,推廣至c類別情況，同時考慮各類的先驗概率Pi不等,其中m為所有樣本的總均值向量，Pi表示各類別的先驗概率，Ei表示i類的期望符號。,(4.3-1),(4.3-2),2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)20,利用(4

11、.3-1)與(4.3-2)式可以將基于距離的可分性判據(jù)表示成以下形式：,(1) 計算特征向量間平均距離的判據(jù),(4.3-3),其中“tr”表示矩陣的跡。(4.3-3)式實際上是從計算特征向量間總平均距離的公式推導(dǎo)得到的，該式可寫成,(4.3-4),其中Pi、Pj分別表示各類的先驗概率，ni、nj分別是第i與j類的樣本個數(shù)，(Xk(i), Xl(i) 用來表示第i類的第k個與j類第l個樣本之間的距離度量。在歐氏距離情況下有,(4.3-5),2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)21,均值向量,總均值向量,代入(4.3-4)式，可得,(4.3-6),(4.3-6)中右邊括

12、弧里的前一項涉及類內(nèi)各特征向量之間的平方距離，后一項則是類間距離項。后一項可寫成 ：,(4.3-7),2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)22,(2) 考慮類內(nèi)類間歐氏距離的其它判據(jù),判據(jù)Jd(X)是計算特征向量的總平均距離，以下一些判據(jù)則基于使類間離散度盡量大，類內(nèi)離散度盡量小的考慮而提出：,(4.3-8),(4.3-9),(4.3-10),(4.3-11),2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)23,4.3.2 按歐氏距離度量的特征提取方法,基于距離可分性判據(jù)的特征優(yōu)化過程是通過一個線性變換實現(xiàn)的。,設(shè)在原特征空間一個樣本向量表示成Y(

13、D維)而在優(yōu)化以及的特征空間中，樣本向量表示成X(d維)而X與Y之間的關(guān)系是：,W是一個Dd維矩陣，希望變換后的特征向量能滿足使某個準(zhǔn)則函數(shù)達(dá)到極值的要求。,如果對特征空間實行一個DD矩陣的非奇異線性變換，J2，J3 都保持不變。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)24,例如若對原特征空間實行一DD線性變換A，則離散度矩陣Sb與SW變?yōu)镾bASbAT及SWASWAT，而映射變換后的J2(X)有：,其目的是在維數(shù)d的條件下，使相應(yīng)的判據(jù)為最大。,在使用J2判據(jù)的情況下，可以將J判據(jù)表示成變換W的函數(shù)：,(4.3-12),求使J2(W)最大的W解可利用特征值方法。前面

14、曾提到如果W是一個DD的線性變換，則J2是不變的，而此時(4.3-12)可進(jìn)一步表示成：,(4.3-13),其中用WD代替(4.3-12)中的W，以強調(diào)是DD變換。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)25,如果WDT 是SW-1 Sb 的各特征值對應(yīng)的特征向量所組成的矩陣，則由(4.3-13)式可得：,(4.3-14),其中i表示SW-1 Sb的各特征值。,(4.3-14)式表明D維特征空間中，J2判據(jù)的值是SW-1 Sb矩陣的全部特征值之和。那么由對應(yīng)于d個最大的特征值的特征向量所組成的矩陣W(Dd)，就能使所得到的d維特征滿足J2判據(jù)最大的要求。,雖然J2，J

15、3，J5乃至J4所采用的計算方法各不相同，但都得到一個同樣的結(jié)論，如果矩陣的特征值按大小順序列為：,則選擇前d個特征值所對應(yīng)的特征向量組成變換矩陣W，都可使這些判據(jù)達(dá)到最大值。,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)26,例：給定先驗概率相等的兩類，其均值向量分別為：,協(xié)方差矩陣為：,求用J2判據(jù)的最優(yōu)特征提取。,解：,先求SW-1 Sb，再求此矩的特征矩陣。,混合均值：,類間離散度矩陣：,2020/7/12,中國礦業(yè)大學(xué) 計算機科學(xué)與技術(shù)學(xué)院,(28)27,類內(nèi)離散度矩陣：,求矩陣SW-1 Sb的特征值。由于這是一個兩類別問題，總均值向量值是兩個均值向量1和2的線性求和，則(1 -)中(2 -)只有一個是獨立的，因此矩陣SW-1 Sb的