1、模式識別,授課教師 薛耀紅 ,第10講 特征的選擇與提取(2),本節(jié)課主要內(nèi)容,1 類別可分離性判據(jù) 2 特征提取 3 特征選擇,3 特征選擇,1 最優(yōu)搜索算法 2 次優(yōu)搜索法 3 可分性判據(jù)的遞推計(jì)算 4.特征選擇的幾種新方法,特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出 數(shù)量為d（Dd）的一組最優(yōu)特征來.,利用窮舉法總可以找出最優(yōu)的特征集,但計(jì)算量太 大.從D個(gè)特征中選取d個(gè),共 種組合。,如: 若D=20, d=10, 則從D個(gè)特征中選取d個(gè)特征的組合數(shù)q=184756, 對每一種組合需要計(jì)算判據(jù)值J(x),最優(yōu)特征的選擇，要解決兩個(gè)問題:,選擇的標(biāo)準(zhǔn)，這可以用類可分離性判據(jù). 確定一個(gè)

2、較好的算法，以便找出最優(yōu)的特征集.,本節(jié)主要討論第二個(gè)問題，簡單介紹幾種優(yōu)化算法.,1. 最優(yōu)搜索算法,到目前為止唯一能獲得最優(yōu)結(jié)果的搜索方法是“分支定界”算法，它是一種“自上而下”的方法，但具有回溯功能，可使所有可能的特征組合都被考慮到。,由于合理的組織搜索過程，使得有可能避免計(jì)算某些特征組合而不影響結(jié)果為最優(yōu)。,整個(gè)搜索過程可用樹來表示,樹的根結(jié)點(diǎn)表示原始特征集, 其他結(jié)點(diǎn)表示從其父結(jié)點(diǎn)所代表的特征子集中去掉某一特征后所得到的特征子集, 結(jié)點(diǎn)上的標(biāo)號是去掉的特征的編號.,分支定界法的搜索樹示意圖(D=6，d=2),X,根結(jié)點(diǎn):原始特征集,結(jié)點(diǎn)標(biāo)號:去掉的特征,每一結(jié)點(diǎn)表示去掉若干特征后得到

3、的子集.,從左到右同一級結(jié)點(diǎn)對應(yīng)的特征子集的類可分性判據(jù)值遞增.,說明,分支定界法之所以有效, 這主要是利用了可分離性判據(jù)的單調(diào)性，即對有包含關(guān)系的特征組 Ak，k =1，2，I，即有：,可分性判據(jù)滿足：,2. 次優(yōu)搜索法,最優(yōu)搜索法在有些情況下計(jì)算量太大而難以實(shí)現(xiàn)，這時(shí)不得不放棄最優(yōu)解而采取計(jì)算量較小的次優(yōu)搜索方法。下面我們介紹一些不同的算法，面對實(shí)際問題時(shí)可靈活選擇。,（1）單獨(dú)最優(yōu)特征組合,最簡單的方法是計(jì)算各特征單獨(dú)使用時(shí)的判據(jù)值并加以排隊(duì)，取前d個(gè)作為選擇結(jié)果。但我們需要注意的是，即使各特征是統(tǒng)計(jì)獨(dú)立的，這一結(jié)果也不一定就是最優(yōu)結(jié)果。,只有當(dāng)可分性判據(jù)J可寫為如下兩種形式時(shí)，這種方法

4、才能選出一組最優(yōu)的特征來：,（2）順序前進(jìn)法（SFS）,這是最簡單的“自下而上”的搜索方法。每次從未入選的特征中選擇一個(gè)特征，使得它與已入選的特征組合在一起時(shí)所得判據(jù)J值為最大，直到特征數(shù)增加到d為止,（3）順序后退法（SBS）,它與順序前進(jìn)法的思路剛好相反。這是一種“自上而下”的方法，從全體特征開始每次剔除一個(gè)，所剔除的特征應(yīng)使仍然保留的特征組的判據(jù)J值最大，直到特征數(shù)減少到d為止。,和順序前進(jìn)法比較，該方法用兩個(gè)特點(diǎn)：一是在計(jì)算過程中可以估計(jì)每去掉一個(gè)特征所造成可分性的降低；二是由于它的計(jì)算是在高維空間中進(jìn)行的，所以計(jì)算量比較大。,比方說，在第k步可先用SFS法一個(gè)個(gè)加入特征到 k+l 個(gè)

5、，然后再用SBS法一個(gè)個(gè)剔去 r 個(gè)特征，我們把這樣一種算法叫增 l 減 r 法（lr 法）,（4）增 l 減 r 法（lr 法）,這種方法是基于前兩種算法的特點(diǎn)提出的.為了避免前面方法的一旦被選入(或剔除)就不能再剔除(或選入)的缺點(diǎn)可在選擇過程中加入局部回溯過程。,3. 可分性判據(jù)的遞推計(jì)算,所有上述搜索算法都有一個(gè)共同點(diǎn)，即第 k 步特征組是在第 k1 步特征組上加入或剔除某些特征來構(gòu)成的，因此我們可以分析一下，是否有可能從 k1 步的判據(jù)值 J(k-1) 推算出 J(k),而不必完全重新計(jì)算.,事實(shí)上，對于有些情況，對于這些判據(jù)遞推關(guān)系是存在的，即求J(k)時(shí)可在 J(k-1)的基礎(chǔ)上

6、把新加入（或剔除）特征的影響加進(jìn)去即可，不必從頭算起，這樣就大大簡化了計(jì)算工作.,我們注意到在進(jìn)行特征選擇時(shí)需要以可分性判據(jù)來度量特征選擇的好壞.特征選擇是一個(gè)組合優(yōu)化問題,因此可以使用解決優(yōu)化問題的方法來解決特征選擇問題.,優(yōu)化問題是很多研究人員關(guān)注的一個(gè)熱點(diǎn)問題，近年來出現(xiàn)了一些有特色的解決方法,如:,1) 模擬退火算法,2) 遺傳算法,3) Tabu搜索算法,4. 特征選擇的幾種新方法,來源于統(tǒng)計(jì)力學(xué)。材料粒子從高溫開始，非常緩慢地降溫(退火)，粒子就可在每個(gè)溫度下達(dá)到熱平衡。假設(shè)材料在狀態(tài)i的能量為 E(i)，那么材料在溫度 T時(shí)從狀態(tài)i進(jìn)入狀態(tài)j遵循如下規(guī)律,1) 模擬退火算法,如果

7、 E(j) E(i)，接受該狀態(tài)被轉(zhuǎn)換。 如果 E(j)E(i)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：,1) 模擬退火算法,模擬退火優(yōu)化法：f : xR+， 其中xS，表示優(yōu)化問題的一個(gè)可行解。 N(x)S 表示x的一個(gè)鄰域集合。,首先給定初始溫度T0和初始解 x(0)，以概率P生成下一個(gè)新解x,1) 模擬退火算法,對于溫度Ti和該優(yōu)化問題的解x(k)，可以生成新解x 經(jīng)過多次轉(zhuǎn)換，降低溫度得到 T i+1 Ti。在Ti+1下重復(fù)上述過程，最終的解是對該問題尋優(yōu)的結(jié)果。,1) 模擬退火算法: 步驟,Step1: 令i=0, k=0, 給出初始溫度T0和初始特征組合x(0)。 Step2: 在x(k)的

8、鄰域N(x(k)中選擇一個(gè)狀態(tài)x，即新特征組合。計(jì)算其可分性判據(jù)J(x)，并按概率P接受x(k+1)=x。 Step3: 如果在Ti下還未達(dá)到平衡，則轉(zhuǎn)到Step2。 Step4: 如果Ti已經(jīng)足夠低，則結(jié)束，當(dāng)時(shí)的特征組合即為算法的結(jié)果。否則繼續(xù)。 Step5: 根據(jù)溫度下降方法計(jì)算新的溫度Ti+1。轉(zhuǎn)到Step2。,該算法受進(jìn)化論啟迪，根據(jù)“物競天擇，適者生存”這一規(guī)則演變.,2) 遺傳算法,基因鏈碼：使用遺傳算法時(shí)要把問題的每個(gè)解編碼成一個(gè)基因鏈碼。比如要從D個(gè)特征中挑選d個(gè),就用一個(gè)D位的0或1組成的字符串表示一種特征組合。1表示該特征被選中，每個(gè)基因鏈碼代表一個(gè)解，稱作一個(gè)“個(gè)體”，

9、其中的每一位看作一個(gè)“基因” 群體：若干個(gè)體的集合，也就是一些解的集合,交叉：選擇群體中的兩個(gè)個(gè)體，以這兩個(gè)個(gè)體為雙親作基因鏈碼的交叉，從而產(chǎn)生兩個(gè)新的個(gè)體，作為后代。,2) 遺傳算法,變異：對某個(gè)體，隨機(jī)選取其中一位，將其翻轉(zhuǎn),適應(yīng)度：對每個(gè)解，以給定的優(yōu)化準(zhǔn)則來評價(jià)其性能的優(yōu)劣，作為其適應(yīng)度，即函數(shù)fi的值，個(gè)體xi越好，fi 越大。新一代群體對環(huán)境的平均適應(yīng)度比父代高,Step1: 令進(jìn)化代數(shù)t=0。 Step2: 給出初始化群體P(t)，令xg為任一個(gè)體。 Step3: 對P(t)中每個(gè)個(gè)體估值，并將群體中最優(yōu)解x 與xg比較，如果x的性能優(yōu)于xg，則xg=x Step4: 如果終止條

10、件滿足，則算法結(jié)束，xg為算法的 結(jié)果。否則繼續(xù)。 Step5: 從P(t)中選擇個(gè)體并進(jìn)行交叉和變異操作，得 到新一代群體P(t+1)。令t=t+1,轉(zhuǎn)到Step3。,2) 遺傳算法：步驟,關(guān)于遺傳算法的說明： 由步驟3保證了最終解是所搜索過的最優(yōu)解 常用的終止條件是群體的世代數(shù)超過一個(gè)給定值，或連續(xù)數(shù)個(gè)世代都沒有得到更優(yōu)解 群體的大小和演化代數(shù)是值得重視的參數(shù)。在一定范圍內(nèi)，這兩個(gè)參數(shù)大些能得到更好的解 對交叉的親本選擇可采用如下規(guī)則：個(gè)體的性能越好，被選中的可能性也越大,3) Tabu搜索算法,自學(xué),本節(jié)課結(jié)束 謝謝大家！,經(jīng)過有限次轉(zhuǎn)換，在溫度Ti下的平衡態(tài)xi的分布為,1) 模擬退火

11、算法,當(dāng)溫度T降為0時(shí)，xi的分布為,模式識別,授課教師 薛耀紅 ,第9講 特征的選擇與提取(1),本節(jié)課主要內(nèi)容,1 類別可分離性判據(jù) 2 特征提取 3 特征選擇,特征提取與選擇的基本任務(wù)是研究如何從眾多特征中求出那些對分類識別最有效的特征，從而實(shí)現(xiàn)特征空間維數(shù)的壓縮,即獲取一組“少而精”且分類錯(cuò)誤概率小的分類待征.,可以把特征分為三類 1 物理的；2 結(jié)構(gòu)的：易于為人的直覺感知，但有時(shí) 難于定量描述，因而不易用于機(jī)器判別 3 數(shù)學(xué)的：易于用機(jī)器定量描述和判別，如基于統(tǒng)計(jì) 的特征,x1 x2 x3 . . xd,對 象,模式的特征的有效性直接影響分類器的設(shè)計(jì)和性能.由信息獲取部分獲得的原始數(shù)

12、據(jù)量一般是相當(dāng)大的.為了有效地實(shí)現(xiàn)分類識別，要對原始數(shù)據(jù)進(jìn)行選擇或變換，得到最能反應(yīng)分類本質(zhì)的待征，構(gòu)成特征向量.這就是特征抽取與選擇的過程.,傳感器,y1 y2 y3 . . ym,學(xué)習(xí).訓(xùn)練,選擇.提取,分類器,特征選擇： 從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的，這個(gè)過程叫特征選擇。,特征提?。?在原始特征的維數(shù)很高的情況下，通過映射（或變換）的方法用低維空間來表示樣本，這個(gè)過程叫特征提取，映射后的特征稱作二次特征。,特征形成： 根據(jù)被識別的對象產(chǎn)生出一組基本特征（也可稱為原始特征），它可以是計(jì)算出來的，也可以是用儀表或傳感器測量出來的,稱作原始特征。,有時(shí)特征提取

13、和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數(shù)較低的空間，在這個(gè)空間中再進(jìn)行選擇以進(jìn)一步降低維數(shù)；也可以先經(jīng)過選擇去掉那些明顯沒有分類信息的特征，再進(jìn)行映射以降低維數(shù)。,本講討論特征的選擇與提取方法.,細(xì)胞自動(dòng)識別： 原始測量：（正常與異常）細(xì)胞的數(shù)字圖像 原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比 壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類（2種方式） 1. 特征提?。河糜成洌ɑ蚍Q變換）的方法把原始特征變換為較少的新特征 2. 特征選擇：從原始特征中去挑選出一些最有代表性的特征,特征的選擇與提取舉例1,特征的

14、選擇與提取舉例2,特征提取和選擇：對單個(gè)魚的信息進(jìn)行特征選擇，從而通過測量某些特征來減少信息量 長度 亮度 寬度 魚翅的數(shù)量和形狀 嘴的位置，等等 分類決策：把特征送入決策分類器,特征的選擇與提取舉例,特征的選擇與提取舉例,特征的選擇與提取舉例,特征的選擇與提取舉例,1 類別可分離性判據(jù),1.準(zhǔn)則函數(shù)-判據(jù) 2.基于類間距離的可分性判據(jù) 3.基于概率分布的可分性判據(jù) 4.基于熵函數(shù)的可分性判據(jù),1.準(zhǔn)則函數(shù),特征選擇與提取的任務(wù):求出一組對分類最有效的特征。 類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準(zhǔn)則 理想準(zhǔn)則：某組特征使分類器錯(cuò)誤概率最小 常用類別可分離性判據(jù)：基于距離、

15、概率分布、熵函數(shù),類別可分離性判據(jù),我們可以依據(jù)某種準(zhǔn)則進(jìn)行特征提取和選擇，為此，應(yīng)當(dāng)首先構(gòu)造這樣的準(zhǔn)則類別可分離性判據(jù)。這些判據(jù)應(yīng)能反映各類在特征空間中的分布情況，應(yīng)能刻畫各特征分量在分類識別中的重要性或貢獻(xiàn)。 1 類別可分離性判據(jù)滿足的要求 （1）與錯(cuò)誤概率（或其的上下界）有單調(diào)關(guān)系； （2）當(dāng)特征獨(dú)立時(shí)有可加性,（3）具有“距離”的某些特性，即 （4）對特征數(shù)目是單調(diào)不減，即加入新的特征后，判據(jù)值不減。 這里指出，所構(gòu)造的可分離性判據(jù)并不一定同時(shí)具有上述的四個(gè)性質(zhì)，但這并不影響它在實(shí)際使用中的性質(zhì)。 下面對幾種常用的判據(jù)進(jìn)行討論。,2. 類內(nèi)類間距離,各類樣本可以分開是因?yàn)樗鼈兾挥谔卣骺?/p>

16、間的不同區(qū) 域，顯然這些區(qū)域之間距離越大，類別可分性就越大。,如何表示兩個(gè)類之間的距離?,2. 類內(nèi)類間距離,點(diǎn)到點(diǎn)的距離,點(diǎn)到點(diǎn)集 的均方歐式距離,類內(nèi)均值向量,樣本總均值向量,各類均值向量,Pi 先驗(yàn)概率,2. 類內(nèi)類間距離,類內(nèi)均方歐式距離,類內(nèi)離差矩陣,類內(nèi)離差矩陣 SWi 的跡等于類內(nèi)均方歐式距離,兩類之間的均方距離,C 類特征向量之間的平均距離為：,2. 類內(nèi)類間距離,(8-5),類內(nèi)平均距離,類間距離,(8-6),(8-1),2. 類內(nèi)類間距離,基于距離的準(zhǔn)則概念直觀，計(jì)算方便，但與錯(cuò)誤率沒有直接聯(lián)系,樣本類間離散度矩陣,樣本類內(nèi)離散度矩陣,類間可分離性判據(jù),1) 基于類內(nèi)類間距

17、離的可分離性判據(jù)是一種常用的判據(jù)，它實(shí)際上是各類向量之間的平均距離。 2) 具體而言，即 J(x) 表示各類特征向量之間的平均距離，我們通常認(rèn)為 J(x) 越大，可分離性越好。 3) 這種判據(jù)優(yōu)點(diǎn)是計(jì)算簡單；缺點(diǎn)是當(dāng)類間距離較小，類內(nèi)距離較大時(shí)，判據(jù)仍有可能取得較大的值，而此時(shí)的可分離性并不大。,2. 類內(nèi)類間距離,3.基于概率分布的可分性判據(jù),上面介紹的距離準(zhǔn)則是直接從各類樣本間的距離算出的,沒有考慮各類的概率分布,不能確切表明各類交疊的情況，因此與錯(cuò)誤概率沒有直接聯(lián)系,下面提出一些基于概率分布的可分性判據(jù).,兩個(gè)分布密度函數(shù)之間的距離,任何函數(shù)J，如果滿足下述條件，都可用來作為類分 離性的

18、概率距離度量。,1) J具有非負(fù)性 2 ) 當(dāng)兩類完全不交疊時(shí)，J取最大值 3 ) 當(dāng)兩類分布密度相同時(shí)，J應(yīng)為0,如圖所示，圖1表示兩類為完全可分的情況，而圖2則表示兩類完全不可分的。,(1) Bhattacharyya距離,注： s是在 0,1 區(qū)間取值的一個(gè)參數(shù)，當(dāng)s=0.5時(shí)，上述二者相等,(2) Chernoff距離,定義散度等于各類平均可分信息之和：,(3) 散度,對數(shù)似然比,提供1類對2 類的可分性信息,1類對2類的平均可分性信息為,4.基于熵函數(shù)的可分性判據(jù),最佳分類器由后驗(yàn)概率確定，所以可由特征的后驗(yàn) 概率分布來衡量它對分類的有效性。,兩種特殊情形下最佳分類器的錯(cuò)誤率:,錯(cuò)誤

19、率,可見后驗(yàn)概率越集中, 錯(cuò)誤概率就越小.后驗(yàn)概率分布越平緩(接近均勻分布)，則分類錯(cuò)誤概率就越大.,設(shè)為可能取值為i, ( i=1,2,c)的一個(gè)隨機(jī)變量, 它的取值依賴于分布密度為p(x)的隨機(jī)向量x(特征向 量),即給定x后的概率為p(/ x).,為了衡量后驗(yàn)概率分布的集中程度，需要規(guī)定一個(gè)定 量準(zhǔn)則.我們可以借助于信息論中關(guān)于熵的概念.,我們想知道的是：給定某一x后，我們從觀察得到的結(jié) 果中得到了多少信息?或者說的不確定性減少了多少?,從特征提取的角度看，顯然用具有最小不確定性的那 些特征進(jìn)行分類是有利的。在信息論中用“熵”作為 不確定性的度量.,4.基于熵函數(shù)的可分性判據(jù),重疊程度越

20、大熵函數(shù)值越大,4.基于熵函數(shù)的可分性判據(jù),2) Shannon熵,4.基于熵函數(shù)的可分性判據(jù),3) 平方熵,為了對所提取的特征進(jìn)行評價(jià)，我們要計(jì)算空間每一點(diǎn)的熵函數(shù). 在熵函數(shù)取值較大的那一部分空間，不同類的樣本必然在較大的程度上互相重疊.,4.基于熵函數(shù)的可分性判據(jù),2 特征提取,1 按歐氏距離度量的特征提取方法 2 基于判別熵最小化的特征提取 3 兩維顯示,確定變換的依據(jù):類別可分性判據(jù),目標(biāo): 在新的特征空間中, 各類之間容易區(qū)分.,2 特征提取,根據(jù)前面提到的類別可分離性判據(jù)。我們可以依據(jù)這些判據(jù)進(jìn)行特征的提取。 設(shè)原特征向量 ，對 作線性變換，產(chǎn)生 d 維向量 ， ，即 矩陣 稱為

21、特征提取矩陣或變換矩陣， 稱為二次特征。, s階Minkowski度量,多維空間中兩個(gè)向量之間有多種距離度量,1. 按歐氏距離度量的特征提取方法, Chebychev距離: 棋盤距離,在實(shí)際應(yīng)用中，在計(jì)算的復(fù)雜性方面，在是否便于進(jìn)行解析分析以及用它進(jìn)行特征提取的效果方面都各不相同。由于歐氏距離在很多情況下便于分析和計(jì)算.,同樣的，我們還可以提出下面各種判據(jù)：,以J2為例, 特征提取的步驟如下, 作線性映射：,其中Y為D維原始特征向量；X為d維壓縮后的特征向量, 令,其中Sw，Sb為原空間（即Y的）離散度矩陣，S*w，S*b 為映射后（即X的）離散度矩陣。, J2的表達(dá)式為：, 求變換矩陣W,

22、使 J2（W）最大,將上式對W的各分量求偏導(dǎo)數(shù)并令其為零,可以確定一個(gè)W，從而得到使判據(jù)達(dá)最大的變換W,注: W的計(jì)算（適用于J2J5判據(jù)）：,則選前d 個(gè)特征值對應(yīng)的特征向量作為W，即： W=u1, u2, , ud ,此時(shí),2. 基于判別熵最小化的特征提取,上節(jié)中討論了用熵作為不確定性的一種度量的表達(dá)式，這里我們引入判別熵 W(p, q) 來表征兩類分布 p(xi) 和 q(xj) 差別大小, 令：,對于特征提取來說，我們應(yīng)該求得一組特征，它使上述判別熵最小。,計(jì)算步驟如下:, A=G1-G2, G1，G2分別是第一類樣本集和第二類樣本集的協(xié)方差矩陣,3. 兩維顯示,人的經(jīng)驗(yàn)和直觀對分類有

23、很大作用，如果能將各樣本在特征空間的分布情況顯示出來，我們可以直接觀察哪些樣本聚集在一起，因而可能屬于一類。 最好能把原來的高維特征空間映射到二維平面上顯示出來，這一映射要盡可能的保持原來樣本的分布情況，或者盡量使各樣本間相互距離關(guān)系保持不變. 上述所討論的各種變換方法有利于我們解決這樣一種兩維顯示的任務(wù).,設(shè)映射前兩點(diǎn)間距離為D，映射后該兩點(diǎn)間距離為D* . 希望映射后D*盡可能等于D. 令 e =DD*為任意兩點(diǎn)映射前后距離之差，我們要選擇映射函數(shù) f使e的函數(shù)值達(dá)最小.,由于非線性映射比較復(fù)雜，一般情況下是用迭代算法。即選一個(gè)x的初值，再逐步調(diào)整（每次調(diào)整的方向應(yīng)使誤差減?。?，直到滿足一

24、個(gè)停止準(zhǔn)則（例如，誤差小于給定值，迭代次數(shù)超過預(yù)定次數(shù)，或顯示結(jié)果已滿足觀察者要求為止).,本節(jié)課結(jié)束 謝謝大家！,1 設(shè)有兩類三維樣本，都服從正態(tài)分布，且樣本均值和協(xié)方差矩陣分別為：,1). 計(jì)算其類可分性散度判據(jù)JD的值,2 設(shè)樣本均值為（1，2），樣本的協(xié)方差矩陣和相關(guān)矩陣分別為：,計(jì)算分別用和R計(jì)算得到的主成分，并說明其差異。,4. 基于主成分變換的特征提取方法,在實(shí)際問題中, 研究多變量問題是經(jīng)常遇到的，然而在多數(shù)情況下, 不同指標(biāo)之間是有一定相關(guān)性。由于指標(biāo)較多, 再加上指標(biāo)之間有一定的相關(guān)性，勢必增加了分析問題的復(fù)雜性. 主成分分析就是設(shè)法將原來指標(biāo)重新組合成一組新的相互無關(guān)的幾

25、個(gè)綜合指標(biāo)來代替原來指標(biāo), 同時(shí)根據(jù)實(shí)際需要從中可取幾個(gè)較少的綜合指標(biāo)盡可能多地反映原來指標(biāo)的信息。 這種將多個(gè)指標(biāo)化為少數(shù)相互無關(guān)的綜合指標(biāo)的統(tǒng)計(jì)方法叫做主成分分析（Principal Component Analysis).,某人要做一件上衣要測量很多尺寸,如身長、袖長等十幾項(xiàng)指標(biāo),但某服裝廠要生產(chǎn)一批新型服裝絕不可能把尺寸的型號分得過多,而是從多種指標(biāo)中綜合成幾個(gè)少數(shù)的綜合指標(biāo),作為分類的型號,如下圖:,4 基于主成分變換的特征提取方法,4 基于主成分變換的特征提取方法,主成分分析的基本方法是通過構(gòu)造原變量的適當(dāng)?shù)木€性組合, 以產(chǎn)生一系列互不相關(guān)的新信息, 從中選出少數(shù)幾個(gè)新變量并使它們

26、含有盡可能多的原變量帶有的信息, 從而使得用這幾個(gè)新變量代替原變量分析問題和解決問題成為可能. 當(dāng)研究的問題確定之后,變量中所含“信息”的大小通常用該變量的方差或樣本方差來度量.,如圖, 設(shè)二維樣本集呈現(xiàn)扁橢圓分布.,x1,x2,u,將二維樣本Xi向長軸方向投影,可得到一維樣本Yi,設(shè)u為長軸方向的單位向量,則有,Xi,Yi,一般如何求“最好”的方向 u,？,4 基于主成分變換的特征提取方法,（1）數(shù)學(xué)模型,設(shè) X1,X2,Xp 為某實(shí)際問題所涉及的p個(gè)隨機(jī)變量.記 X=(X1, X2, , Xp )T, 其協(xié)方差矩陣為,設(shè)li=(l1i, l2i, , lpi)T (i=1,2,p)為p個(gè)常

27、數(shù)向量, 考慮如下線性組合:,我們希望用Y1代替原來p個(gè)變量,這就要求Y1盡可能的反映原p個(gè)變量的信息,即Var(Y1)越大.為此,我們對li做如下限制,否則Var(Y1)無界,即:,因此,我們希望在約束條件 l1Tl1=1 之下,求l1使達(dá)到最大,由此l1所確定的隨機(jī)變量 Y1=l1TX 稱為 X1, X2,Xp 的第一主成分.,如果第一主成分Y1還不足以反映原變量的信息,考慮采用Y2. 但要求Y1與Y2不相關(guān), 即,于是, 在約束條件 及 之下, 求 l2 使Var(Y2) 達(dá)到最大, 由此 l2 所確定的隨機(jī)變量Y2=l2TX 稱為X1, X2,Xp 的第二主成分.,一般,在約束條件 及

28、 (k=1,2,i-1)之下,求li 使Var(Yi)達(dá)到最大,由此 li 所確定的隨機(jī)變量 Yi=liTX 稱為 X1,X2,Xp 的第i個(gè)主成分.,并且有:,定理1 設(shè)是X=(X1,X2,Xp)T的協(xié)方差矩陣, 的特征值及其相應(yīng)的正交單位特征向量分別為 及 e1,e2,ep, 則X的第i個(gè)主成分為,下面進(jìn)一步討論 X1, X2, , Xp 的方差與各主成分的方差之間的關(guān)系,以確定各主成分所包含的信息占總信息的份額. 易證下面結(jié)果:,定理2 設(shè)Yi = eiTX (i=1,2,p) 為X的p各主成分, 則:,當(dāng) 時(shí)， 達(dá)到最大值,定義 第k個(gè)主成分Yk的貢獻(xiàn)率為: 前m個(gè)主成分Y1,Y2,Y

29、m的累計(jì)貢獻(xiàn)率為:,在實(shí)際應(yīng)用中, 通常選取mp,使前m個(gè)累計(jì)貢獻(xiàn)率達(dá)到一定的比例(80%90%). 這樣用前m 個(gè)主成分代替原來的變量X1,X2,Xp而不至于損失太多的信息, 從而到達(dá)減少變量個(gè)數(shù)的目的.,在實(shí)際問題中,一般(或)是未知的, 需要通過樣本來估計(jì).設(shè),其中,（2）主成分的計(jì)算方法,分別以S和R作為和的估計(jì),按前面所述的方法求得的主成分稱為樣本主成分.具體有如下結(jié)論:,其中x=(x1,x2,xp)T為X的任一觀測值.當(dāng)依次代入X的n個(gè)觀測值 xk=(x1k,x2k,xpk)T 時(shí),便得到第i個(gè)樣本主成分yi 的n個(gè)觀測值yik (k=1,2,n).,設(shè) S=(sij)pp 是樣本

30、協(xié)方差矩陣,其特征值為 , 相應(yīng)的正交單位化特征向量為 ,則第i個(gè)樣本主成分為:,這時(shí),第i個(gè)樣本主成分的貢獻(xiàn)率為: 前m個(gè)樣本主成分的累計(jì)貢獻(xiàn)率為:,為了消除量綱的影響,我們可以對樣本進(jìn)行標(biāo)準(zhǔn)化,即令,則標(biāo)準(zhǔn)化數(shù)據(jù)的樣本協(xié)方差矩陣即為原數(shù)據(jù)的樣本相關(guān)矩陣R.,由R出發(fā)所求得的樣本主成分稱為標(biāo)準(zhǔn)化樣本主成分.,只要求出R的特征值及相應(yīng)的正交單位化特征向量,類似上述結(jié)果可求得標(biāo)準(zhǔn)化樣本主成分.這時(shí)標(biāo)準(zhǔn)化樣本的樣本總方差為p.,3） 主成分解釋,從代數(shù)觀點(diǎn)看主成分就是p個(gè)變量X1,X2,Xp的一些特殊的線性組合.,在幾何上這些線性組合正是把X1,X2,Xp構(gòu)成的坐標(biāo)系旋轉(zhuǎn)產(chǎn)生新坐標(biāo)系,新坐標(biāo)系軸使

31、之通過樣本變差最大的方向(或說具有最大的樣本方差).,以最簡單的二元正態(tài)變量來說明主成分的幾何意義.,設(shè)有n個(gè)樣本,每個(gè)樣本有p個(gè)變量記為X1,X2,Xp,它們的綜合變量記為Y1,Y2,Yp.當(dāng) p=2 時(shí),原變量是X1, X2,設(shè)X=(X1,X2)N2(, ),它們有下圖的相關(guān)關(guān)系:,對于二元正態(tài)分布變量, n個(gè)點(diǎn)的散布大致為一個(gè)橢圓,若在橢圓長軸方向取坐標(biāo)軸Y1, 在短軸方向取Y2, 這相當(dāng)于在平面上作一個(gè)坐標(biāo)變換, 即:,可以看到Y(jié)1、Y2是原變量X1和X2的線性組合, 用矩陣表示為,顯然UT=U-1且是正交矩陣.,如果上圖的橢圓是相當(dāng)扁平的,可以只考慮長軸Y1方向上的波動(dòng), 忽略Y2方向的波動(dòng). 這樣, 二維可以降為一維.,一般情況, p個(gè)變量組成p維空間,n個(gè)樣本就是p維空間的n個(gè)點(diǎn), 對p元正態(tài)分布變量來說, 找主成分的問題就是找p維空間中橢圓體的主軸問題.,（4）舉例,例一,設(shè)模式 X=(X1, X2, X3)T 的協(xié)方差矩陣為,求X的各主成分.,解: 易求得的特征值及其相應(yīng)的正交化特征向量 分別為,因此X的主成分為,取第一主成分,則貢獻(xiàn)率為,若取前兩個(gè)主成分,則累計(jì)貢獻(xiàn)率為,因此,可用前兩個(gè)主成分代替原來三個(gè)變量.,%Example