模式識別第講特征的選擇與提取

第1頁，課件共97頁，創(chuàng)作于2023年2月第10講特征的選擇與提取(2)第2頁，課件共97頁，創(chuàng)作于2023年2月本節(jié)課主要內(nèi)容1類別可分離性判據(jù)2特征提取3特征選擇第3頁，課件共97頁，創(chuàng)作于2023年2月§3特征選擇1最優(yōu)搜索算法2次優(yōu)搜索法3可分性判據(jù)的遞推計(jì)算4.特征選擇的幾種新方法第4頁，課件共97頁，創(chuàng)作于2023年2月

特征選擇的任務(wù)是從一組數(shù)量為D的特征中選擇出數(shù)量為d（D>d）的一組最優(yōu)特征來.

利用窮舉法總可以找出最優(yōu)的特征集,但計(jì)算量太大.從D個特征中選取d個,共

種組合。如:若D=20,d=10,則從D個特征中選取d個特征的組合數(shù)q=184756,對每一種組合需要計(jì)算判據(jù)值J(x)最優(yōu)特征的選擇，要解決兩個問題:選擇的標(biāo)準(zhǔn)，這可以用類可分離性判據(jù).確定一個較好的算法，以便找出最優(yōu)的特征集.第5頁，課件共97頁，創(chuàng)作于2023年2月本節(jié)主要討論第二個問題，簡單介紹幾種優(yōu)化算法.自下而上法

特征數(shù)從0逐步增加到d用優(yōu)化算法進(jìn)行特征選擇的兩種策略:自上而下法

從特征數(shù)從D開始逐步減少到d第6頁，課件共97頁，創(chuàng)作于2023年2月1.最優(yōu)搜索算法到目前為止唯一能獲得最優(yōu)結(jié)果的搜索方法是“分支定界”算法，它是一種“自上而下”的方法，但具有回溯功能，可使所有可能的特征組合都被考慮到。由于合理的組織搜索過程，使得有可能避免計(jì)算某些特征組合而不影響結(jié)果為最優(yōu)。整個搜索過程可用樹來表示樹的根結(jié)點(diǎn)表示原始特征集,其他結(jié)點(diǎn)表示從其父結(jié)點(diǎn)所代表的特征子集中去掉某一特征后所得到的特征子集,結(jié)點(diǎn)上的標(biāo)號是去掉的特征的編號.第7頁，課件共97頁，創(chuàng)作于2023年2月分支定界法的搜索樹示意圖(D=6，d=2)X根結(jié)點(diǎn):原始特征集結(jié)點(diǎn)標(biāo)號:去掉的特征3564566542534666545566665345544321每一結(jié)點(diǎn)表示去掉若干特征后得到的子集.從左到右同一級結(jié)點(diǎn)對應(yīng)的特征子集的類可分性判據(jù)值遞增.說明第8頁，課件共97頁，創(chuàng)作于2023年2月分支定界法之所以有效,這主要是利用了可分離性判據(jù)的單調(diào)性，即對有包含關(guān)系的特征組Ak，k=1，2，……，I，即有：可分性判據(jù)滿足：第9頁，課件共97頁，創(chuàng)作于2023年2月2.次優(yōu)搜索法最優(yōu)搜索法在有些情況下計(jì)算量太大而難以實(shí)現(xiàn)，這時不得不放棄最優(yōu)解而采取計(jì)算量較小的次優(yōu)搜索方法。下面我們介紹一些不同的算法，面對實(shí)際問題時可靈活選擇。（1）單獨(dú)最優(yōu)特征組合最簡單的方法是計(jì)算各特征單獨(dú)使用時的判據(jù)值并加以排隊(duì)，取前d個作為選擇結(jié)果。但我們需要注意的是，即使各特征是統(tǒng)計(jì)獨(dú)立的，這一結(jié)果也不一定就是最優(yōu)結(jié)果。只有當(dāng)可分性判據(jù)J可寫為如下兩種形式時，這種方法才能選出一組最優(yōu)的特征來：第10頁，課件共97頁，創(chuàng)作于2023年2月（2）順序前進(jìn)法（SFS）這是最簡單的“自下而上”的搜索方法。每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得判據(jù)J值為最大，直到特征數(shù)增加到d為止第11頁，課件共97頁，創(chuàng)作于2023年2月（3）順序后退法（SBS）它與順序前進(jìn)法的思路剛好相反。這是一種“自上而下”的方法，從全體特征開始每次剔除一個，所剔除的特征應(yīng)使仍然保留的特征組的判據(jù)J值最大，直到特征數(shù)減少到d為止。和順序前進(jìn)法比較，該方法用兩個特點(diǎn)：一是在計(jì)算過程中可以估計(jì)每去掉一個特征所造成可分性的降低；二是由于它的計(jì)算是在高維空間中進(jìn)行的，所以計(jì)算量比較大。第12頁，課件共97頁，創(chuàng)作于2023年2月比方說，在第k步可先用SFS法一個個加入特征到k+l個，然后再用SBS法一個個剔去r個特征，我們把這樣一種算法叫增l減r法（l–r法）（4）增l減r法（l–r法）這種方法是基于前兩種算法的特點(diǎn)提出的.為了避免前面方法的一旦被選入(或剔除)就不能再剔除(或選入)的缺點(diǎn)可在選擇過程中加入局部回溯過程。第13頁，課件共97頁，創(chuàng)作于2023年2月3.可分性判據(jù)的遞推計(jì)算所有上述搜索算法都有一個共同點(diǎn)，即第k

步特征組是在第k–1步特征組上加入或剔除某些特征來構(gòu)成的，因此我們可以分析一下，是否有可能從k–1步的判據(jù)值J(k-1)推算出J(k),而不必完全重新計(jì)算.事實(shí)上，對于有些情況，對于這些判據(jù)遞推關(guān)系是存在的，即求J(k)時可在J(k-1)的基礎(chǔ)上把新加入（或剔除）特征的影響加進(jìn)去即可，不必從頭算起，這樣就大大簡化了計(jì)算工作.第14頁，課件共97頁，創(chuàng)作于2023年2月我們注意到在進(jìn)行特征選擇時需要以可分性判據(jù)來度量特征選擇的好壞.特征選擇是一個組合優(yōu)化問題,因此可以使用解決優(yōu)化問題的方法來解決特征選擇問題.優(yōu)化問題是很多研究人員關(guān)注的一個熱點(diǎn)問題，近年來出現(xiàn)了一些有特色的解決方法,如:1)模擬退火算法2)遺傳算法3)Tabu搜索算法4.特征選擇的幾種新方法第15頁，課件共97頁，創(chuàng)作于2023年2月來源于統(tǒng)計(jì)力學(xué)。材料粒子從高溫開始，非常緩慢地降溫(退火)，粒子就可在每個溫度下達(dá)到熱平衡。假設(shè)材料在狀態(tài)i的能量為

E(i)，那么材料在溫度

T時從狀態(tài)i進(jìn)入狀態(tài)j遵循如下規(guī)律1)模擬退火算法如果

E(j)≤E(i)，接受該狀態(tài)被轉(zhuǎn)換。如果

E(j)>E(i)，則狀態(tài)轉(zhuǎn)換以如下概率被接受：第16頁，課件共97頁，創(chuàng)作于2023年2月1)模擬退火算法模擬退火優(yōu)化法：f

:x→R+，其中x∈S，表示優(yōu)化問題的一個可行解。N(x)≤S

表示x的一個鄰域集合。第17頁，課件共97頁，創(chuàng)作于2023年2月首先給定初始溫度T0和初始解

x(0)，以概率P生成下一個新解x’1)模擬退火算法對于溫度Ti和該優(yōu)化問題的解x(k)，可以生成新解x’經(jīng)過多次轉(zhuǎn)換，降低溫度得到

T

i+1<

Ti。在Ti+1下重復(fù)上述過程，最終的解是對該問題尋優(yōu)的結(jié)果。第18頁，課件共97頁，創(chuàng)作于2023年2月1)模擬退火算法:步驟Step1:

令i=0,k=0,給出初始溫度T0和初始特征組合x(0)。Step2:

在x(k)的鄰域N(x(k))中選擇一個狀態(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)時的特征組合即為算法的結(jié)果。否則繼續(xù)。Step5:

根據(jù)溫度下降方法計(jì)算新的溫度Ti+1。轉(zhuǎn)到Step2。第19頁，課件共97頁，創(chuàng)作于2023年2月第20頁，課件共97頁，創(chuàng)作于2023年2月該算法受進(jìn)化論啟迪，根據(jù)“物競天擇，適者生存”這一規(guī)則演變.2)遺傳算法基因鏈碼：使用遺傳算法時要把問題的每個解編碼成一個基因鏈碼。比如要從D個特征中挑選d個,就用一個D位的0或1組成的字符串表示一種特征組合。1表示該特征被選中，每個基因鏈碼代表一個解，稱作一個“個體”，其中的每一位看作一個“基因”群體：若干個體的集合，也就是一些解的集合第21頁，課件共97頁，創(chuàng)作于2023年2月交叉：選擇群體中的兩個個體，以這兩個個體為雙親作基因鏈碼的交叉，從而產(chǎn)生兩個新的個體，作為后代。2)遺傳算法變異：對某個體，隨機(jī)選取其中一位，將其翻轉(zhuǎn)適應(yīng)度：對每個解，以給定的優(yōu)化準(zhǔn)則來評價其性能的優(yōu)劣，作為其適應(yīng)度，即函數(shù)fi的值，個體xi越好，fi越大。新一代群體對環(huán)境的平均適應(yīng)度比父代高第22頁，課件共97頁，創(chuàng)作于2023年2月Step1:令進(jìn)化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個體。Step3:對P(t)中每個個體估值，并將群體中最優(yōu)解x’

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

授課教師薛耀紅xueyh@第29頁，課件共97頁，創(chuàng)作于2023年2月第9講特征的選擇與提取(1)第30頁，課件共97頁，創(chuàng)作于2023年2月本節(jié)課主要內(nèi)容1類別可分離性判據(jù)2特征提取3特征選擇第31頁，課件共97頁，創(chuàng)作于2023年2月

特征提取與選擇的基本任務(wù)是研究如何從眾多特征中求出那些對分類識別最有效的特征，從而實(shí)現(xiàn)特征空間維數(shù)的壓縮,即獲取一組“少而精”且分類錯誤概率小的分類待征.

可以把特征分為三類1物理的；2結(jié)構(gòu)的：易于為人的直覺感知，但有時難于定量描述，因而不易用于機(jī)器判別3數(shù)學(xué)的：易于用機(jī)器定量描述和判別，如基于統(tǒng)計(jì)的特征第32頁，課件共97頁，創(chuàng)作于2023年2月x1x2x3..xd對象模式的特征的有效性直接影響分類器的設(shè)計(jì)和性能.由信息獲取部分獲得的原始數(shù)據(jù)量一般是相當(dāng)大的.為了有效地實(shí)現(xiàn)分類識別，要對原始數(shù)據(jù)進(jìn)行選擇或變換，得到最能反應(yīng)分類本質(zhì)的待征，構(gòu)成特征向量.這就是特征抽取與選擇的過程.傳感器y1y2y3..ym學(xué)習(xí).訓(xùn)練選擇.提取分類器第33頁，課件共97頁，創(chuàng)作于2023年2月特征選擇：從一組特征中挑選出一些最有效的特征以達(dá)到降低特征空間維數(shù)的目的，這個過程叫特征選擇。特征提?。涸谠继卣鞯木S數(shù)很高的情況下，通過映射（或變換）的方法用低維空間來表示樣本，這個過程叫特征提取，映射后的特征稱作二次特征。

特征形成：

根據(jù)被識別的對象產(chǎn)生出一組基本特征（也可稱為原始特征），它可以是計(jì)算出來的，也可以是用儀表或傳感器測量出來的,稱作原始特征。第34頁，課件共97頁，創(chuàng)作于2023年2月

有時特征提取和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數(shù)較低的空間，在這個空間中再進(jìn)行選擇以進(jìn)一步降低維數(shù)；也可以先經(jīng)過選擇去掉那些明顯沒有分類信息的特征，再進(jìn)行映射以降低維數(shù)。本講討論特征的選擇與提取方法.特征提取特征選擇第35頁，課件共97頁，創(chuàng)作于2023年2月細(xì)胞自動識別：原始測量：（正常與異常）細(xì)胞的數(shù)字圖像原始特征（特征的形成，找到一組代表細(xì)胞性質(zhì)的特征）：細(xì)胞面積，胞核面積，形狀系數(shù)，光密度，核內(nèi)紋理，核漿比壓縮特征：原始特征的維數(shù)仍很高，需壓縮以便于分類（2種方式）1.特征提?。河糜成洌ɑ蚍Q變換）的方法把原始特征變換為較少的新特征2.特征選擇：從原始特征中去挑選出一些最有代表性的特征特征的選擇與提取舉例1第36頁，課件共97頁，創(chuàng)作于2023年2月特征的選擇與提取舉例2特征提取和選擇：對單個魚的信息進(jìn)行特征選擇，從而通過測量某些特征來減少信息量長度亮度寬度魚翅的數(shù)量和形狀嘴的位置，等等…分類決策：把特征送入決策分類器第37頁，課件共97頁，創(chuàng)作于2023年2月特征的選擇與提取舉例第38頁，課件共97頁，創(chuàng)作于2023年2月特征的選擇與提取舉例第39頁，課件共97頁，創(chuàng)作于2023年2月特征的選擇與提取舉例第40頁，課件共97頁，創(chuàng)作于2023年2月特征的選擇與提取舉例第41頁，課件共97頁，創(chuàng)作于2023年2月§1類別可分離性判據(jù)1.準(zhǔn)則函數(shù)-判據(jù)2.基于類間距離的可分性判據(jù)3.基于概率分布的可分性判據(jù)4.基于熵函數(shù)的可分性判據(jù)第42頁，課件共97頁，創(chuàng)作于2023年2月1.準(zhǔn)則函數(shù)特征選擇與提取的任務(wù):求出一組對分類最有效的特征。類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準(zhǔn)則理想準(zhǔn)則：某組特征使分類器錯誤概率最小常用類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)第43頁，課件共97頁，創(chuàng)作于2023年2月類別可分離性判據(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）與錯誤概率（或其的上下界）有單調(diào)關(guān)系；（2）當(dāng)特征獨(dú)立時有可加性第44頁，課件共97頁，創(chuàng)作于2023年2月（3）具有“距離”的某些特性，即（4）對特征數(shù)目是單調(diào)不減，即加入新的特征后，判據(jù)值不減。

這里指出，所構(gòu)造的可分離性判據(jù)并不一定同時具有上述的四個性質(zhì)，但這并不影響它在實(shí)際使用中的性質(zhì)。下面對幾種常用的判據(jù)進(jìn)行討論。第45頁，課件共97頁，創(chuàng)作于2023年2月2.類內(nèi)類間距離各類樣本可以分開是因?yàn)樗鼈兾挥谔卣骺臻g的不同區(qū)域，顯然這些區(qū)域之間距離越大，類別可分性就越大。如何表示兩個類之間的距離?第46頁，課件共97頁，創(chuàng)作于2023年2月2.類內(nèi)類間距離點(diǎn)到點(diǎn)的距離點(diǎn)到點(diǎn)集的均方歐式距離類內(nèi)均值向量樣本總均值向量各類均值向量Pi

先驗(yàn)概率第47頁，課件共97頁，創(chuàng)作于2023年2月2.類內(nèi)類間距離類內(nèi)均方歐式距離類內(nèi)離差矩陣類內(nèi)離差矩陣SWi的跡等于類內(nèi)均方歐式距離兩類之間的均方距離第48頁，課件共97頁，創(chuàng)作于2023年2月C類特征向量之間的平均距離為：2.類內(nèi)類間距離(8-5)類內(nèi)平均距離類間距離(8-6)(8-1)第49頁，課件共97頁，創(chuàng)作于2023年2月2.類內(nèi)類間距離基于距離的準(zhǔn)則概念直觀，計(jì)算方便，但與錯誤率沒有直接聯(lián)系樣本類間

離散度矩陣樣本類內(nèi)

離散度矩陣類間可分離性判據(jù)第50頁，課件共97頁，創(chuàng)作于2023年2月1)基于類內(nèi)類間距離的可分離性判據(jù)是一種常用的判據(jù)，它實(shí)際上是各類向量之間的平均距離。2)具體而言，即J(x)表示各類特征向量之間的平均距離，我們通常認(rèn)為J(x)越大，可分離性越好。

3)這種判據(jù)優(yōu)點(diǎn)是計(jì)算簡單；缺點(diǎn)是當(dāng)類間距離較小，類內(nèi)距離較大時，判據(jù)仍有可能取得較大的值，而此時的可分離性并不大。2.類內(nèi)類間距離第51頁，課件共97頁，創(chuàng)作于2023年2月3.基于概率分布的可分性判據(jù)上面介紹的距離準(zhǔn)則是直接從各類樣本間的距離算出的,沒有考慮各類的概率分布,不能確切表明各類交疊的情況，因此與錯誤概率沒有直接聯(lián)系,下面提出一些基于概率分布的可分性判據(jù).兩個分布密度函數(shù)之間的距離

任何函數(shù)J，如果滿足下述條件，都可用來作為類分離性的概率距離度量。1)J具有非負(fù)性2)當(dāng)兩類完全不交疊時，J取最大值3)當(dāng)兩類分布密度相同時，J應(yīng)為0第52頁，課件共97頁，創(chuàng)作于2023年2月如圖所示，圖1表示兩類為完全可分的情況，而圖2則表示兩類完全不可分的。P（x∣ω1）=P（x∣ω2）圖2圖1P（x∣ω1）P（x∣ω2）=0第53頁，課件共97頁，創(chuàng)作于2023年2月(1)Bhattacharyya距離注：s是在[0,1]區(qū)間取值的一個參數(shù)，當(dāng)s=0.5時，上述二者相等(2)Chernoff距離第54頁，課件共97頁，創(chuàng)作于2023年2月定義散度等于各類平均可分信息之和：(3)散度對數(shù)似然比提供ω1類對ω2類的可分性信息ω1類對ω2類的平均可分性信息為第55頁，課件共97頁，創(chuàng)作于2023年2月4.基于熵函數(shù)的可分性判據(jù)

最佳分類器由后驗(yàn)概率確定，所以可由特征的后驗(yàn)概率分布來衡量它對分類的有效性。兩種特殊情形下最佳分類器的錯誤率:1)

各類后驗(yàn)概率是相等錯誤率錯誤率可見后驗(yàn)概率越集中,錯誤概率就越小.后驗(yàn)概率分布越平緩(接近均勻分布)，則分類錯誤概率就越大.第56頁，課件共97頁，創(chuàng)作于2023年2月

設(shè)ω為可能取值為ωi,(i=1,2,…,c)的一個隨機(jī)變量,

它的取值依賴于分布密度為p(x)的隨機(jī)向量x(特征向量),即給定x后ω的概率為p(ω/x).

為了衡量后驗(yàn)概率分布的集中程度，需要規(guī)定一個定量準(zhǔn)則.我們可以借助于信息論中關(guān)于熵的概念.

我們想知道的是：給定某一x后，我們從觀察得到的結(jié)

果中得到了多少信息?或者說ω的不確定性減少了多少?

從特征提取的角度看，顯然用具有最小不確定性的那些特征進(jìn)行分類是有利的。在信息論中用“熵”作為不確定性的度量.4.基于熵函數(shù)的可分性判據(jù)第57頁，課件共97頁，創(chuàng)作于2023年2月ωiωjωi

ωj

重疊程度越大熵函數(shù)值越大4.基于熵函數(shù)的可分性判據(jù)第58頁，課件共97頁，創(chuàng)作于2023年2月1)廣義熵α為大于1的正數(shù)2)Shannon熵4.基于熵函數(shù)的可分性判據(jù)第59頁，課件共97頁，創(chuàng)作于2023年2月3)平方熵為了對所提取的特征進(jìn)行評價，我們要計(jì)算空間每一點(diǎn)的熵函數(shù).在熵函數(shù)取值較大的那一部分空間，不同類的樣本必然在較大的程度上互相重疊.可以表征類別的分離程度，它可用來作為所提取特征的分類性能的準(zhǔn)則函數(shù).因此熵函數(shù)的期望值4.基于熵函數(shù)的可分性判據(jù)第60頁，課件共97頁，創(chuàng)作于2023年2月§2特征提取1按歐氏距離度量的特征提取方法2基于判別熵最小化的特征提取3兩維顯示第61頁，課件共97頁，創(chuàng)作于2023年2月y1y2y3yDox1x2xdo特征提取D>dY空間

D維原始特征集Y空間

d維新特征集變換確定變換的依據(jù):類別可分性判據(jù)目標(biāo):

在新的特征空間中,各類之間容易區(qū)分.§2特征提取第62頁，課件共97頁，創(chuàng)作于2023年2月

根據(jù)前面提到的類別可分離性判據(jù)。我們可以依據(jù)這些判據(jù)進(jìn)行特征的提取。

設(shè)原特征向量，對作線性變換，產(chǎn)生d維向量，，即

矩陣稱為特征提取矩陣或變換矩陣，稱為二次特征。第63頁，課件共97頁，創(chuàng)作于2023年2月①s階Minkowski度量多維空間中兩個向量之間有多種距離度量②歐氏距離在Minkowski度量中，令s=2，得到常用的歐氏距離：1.按歐氏距離度量的特征提取方法第64頁，課件共97頁，創(chuàng)作于2023年2月③Chebychev距離:棋盤距離④Mahalanobis距離:式中Q是給定的正定標(biāo)尺矩陣第65頁，課件共97頁，創(chuàng)作于2023年2月在實(shí)際應(yīng)用中，在計(jì)算的復(fù)雜性方面，在是否便于進(jìn)行解析分析以及用它進(jìn)行特征提取的效果方面都各不相同。由于歐氏距離在很多情況下便于分析和計(jì)算.前面已經(jīng)推導(dǎo)出了基于歐氏距離的一種度量函數(shù)，其中Sb為類間離散度矩陣,Sw為類內(nèi)離散度矩陣.同樣的，我們還可以提出下面各種判據(jù)：第66頁，課件共97頁，創(chuàng)作于2023年2月以J2為例,特征提取的步驟如下①

作線性映射：其中Y為D維原始特征向量；X為d維壓縮后的特征向量②

令其中Sw，Sb為原空間（即Y的）離散度矩陣，S*w，S*b為映射后（即X的）離散度矩陣。第67頁，課件共97頁，創(chuàng)作于2023年2月③J2的表達(dá)式為：④求變換矩陣W,使

J2（W）最大將上式對W的各分量求偏導(dǎo)數(shù)并令其為零,可以確定一個W，從而得到使判據(jù)達(dá)最大的變換W⑤新特征集為其中Y為原始特征集(D維),X為新特征集(d維)第68頁，課件共97頁，創(chuàng)作于2023年2月注:W的計(jì)算（適用于J2—J5判據(jù)）：則選前d個特征值對應(yīng)的特征向量作為W，即：

W=[u1,u2,……,ud

]此時第69頁，課件共97頁，創(chuàng)作于2023年2月2.基于判別熵最小化的特征提取上節(jié)中討論了用熵作為不確定性的一種度量的表達(dá)式，這里我們引入判別熵W(p,q)來表征兩類分布p(xi)和q(xj)差別大小,令：對于特征提取來說，我們應(yīng)該求得一組特征，它使上述判別熵最小。第70頁，課件共97頁，創(chuàng)作于2023年2月計(jì)算步驟如下:①A=G1-G2,G1，G2分別是第一類樣本集和第二類樣本集的協(xié)方差矩陣Y為所要求的一組特征，它使得判別熵最小③新特征集為②將矩陣A的特征值進(jìn)行排序選取前d個特征值對應(yīng)的特征向量構(gòu)成變換矩陣W=[U1，U2，……，Ud]第71頁，課件共97頁，創(chuàng)作于2023年2月3.兩維顯示

人的經(jīng)驗(yàn)和直觀對分類有很大作用，如果能將各樣本在特征空間的分布情況顯示出來，我們可以直接觀察哪些樣本聚集在一起，因而可能屬于一類。最好能把原來的高維特征空間映射到二維平面上顯示出來，這一映射要盡可能的保持原來樣本的分布情況，或者盡量使各樣本間相互距離關(guān)系保持不變.

上述所討論的各種變換方法有利于我們解決這樣一種兩維顯示的任務(wù).第72頁，課件共97頁，創(chuàng)作于2023年2月①線性映射兩維顯示只不過是前面所涉及的各種映射(線性)的一種特殊情況,即d=2②非線性映射對一些比較復(fù)雜的樣本,線性映射常不能滿足上面所提的保持分布不變的要求,可以用非線性映射替代第73頁，課件共97頁，創(chuàng)作于2023年2月設(shè)映射前兩點(diǎn)間距離為D，映射后該兩點(diǎn)間距離為D*.希望映射后D*盡可能等于D.令e=D–D*為任意兩點(diǎn)映射前后距離之差，我們要選擇映射函數(shù)f使e的函數(shù)值達(dá)最小.由于非線性映射比較復(fù)雜，一般情況下是用迭代算法。即選一個x的初值，再逐步調(diào)整（每次調(diào)整的方向應(yīng)使誤差減?。?，直到滿足一個停止準(zhǔn)則（例如，誤差小于給定值，迭代次數(shù)超過預(yù)定次數(shù)，或顯示結(jié)果已滿足觀察者要求為止).第74頁，課件共97頁，創(chuàng)作于2023年2月本節(jié)課結(jié)束謝謝大家！第75頁，課件共97頁，創(chuàng)作于2023年2月1設(shè)有兩類三維樣本，都服從正態(tài)分布，且樣本均值和協(xié)方差矩陣分別為：1).計(jì)算其類可分性散度判據(jù)JD的值2).利用基于類內(nèi)類間距離的判據(jù)

進(jìn)行最優(yōu)特征提取。第76頁，課件共97頁，創(chuàng)作于2023年2月2設(shè)樣本均值為（1，2），樣本的協(xié)方差矩陣和相關(guān)矩陣分別為：計(jì)算分別用Σ和R計(jì)算得到的主成分，并說明其差異。第77頁，課件共97頁，創(chuàng)作于2023年2月4.基于主成分變換的特征提取方法在實(shí)際問題中,研究多變量問題是經(jīng)常遇到的，然而在多數(shù)情況下,不同指標(biāo)之間是有一定相關(guān)性。由于指標(biāo)較多,再加上指標(biāo)之間有一定的相關(guān)性，勢必增加了分析問題的復(fù)雜性.主成分分析就是設(shè)法將原來指標(biāo)重新組合成一組新的相互無關(guān)的幾個綜合指標(biāo)來代替原來指標(biāo),同時根據(jù)實(shí)際需要從中可取幾個較少的綜合指標(biāo)盡可能多地反映原來指標(biāo)的信息。這種將多個指標(biāo)化為少數(shù)相互無關(guān)的綜合指標(biāo)的統(tǒng)計(jì)方法叫做主成分分析（PrincipalComponentAnalysis).第78頁，課件共97頁，創(chuàng)作于2023年2月某人要做一件上衣要測量很多尺寸,如身長、袖長等十幾項(xiàng)指標(biāo),但某服裝廠要生產(chǎn)一批新型服裝絕不可能把尺寸的型號分得過多,而是從多種指標(biāo)中綜合成幾個少數(shù)的綜合指標(biāo),作為分類的型號,如下圖:4基于主成分變換的特征提取方法第79頁，課件共97頁，創(chuàng)作于2023年2月4基于主成分變換的特征提取方法主成分分析的基本方法是通過構(gòu)造原變量的適當(dāng)?shù)木€性組合,以產(chǎn)生一系列互不相關(guān)的新信息,從中選出少數(shù)幾個新變量并使它們含有盡可能多的原變量帶有的信息,從而使得用這幾個新變量代替原變量分析問題和解決問題成為可能.當(dāng)研究的問題確定之后,變量中所含“信息”的大小通常用該變量的方差或樣本方差來度量.省份GDPX1居民消費(fèi)水平X2固定資產(chǎn)投資X3職工平均工資X4貨物周轉(zhuǎn)量X5居民消費(fèi)價格指數(shù)X6商品零售價格指數(shù)X7工業(yè)總產(chǎn)值X8第80頁，課件共97頁，創(chuàng)作于2023年2月如圖,設(shè)二維樣本集呈現(xiàn)扁橢圓分布.x1x2u將二維樣本Xi向長軸方向投影,可得到一維樣本Yi設(shè)u為長軸方向的單位向量,則有XiYi一般如何求“最好”的方向u？4基于主成分變換的特征提取方法第81頁，課件共97頁，創(chuàng)作于2023年2月（1）數(shù)學(xué)模型設(shè)X1,X2,…,Xp為某實(shí)際問題所涉及的p個隨機(jī)變量.記X=(X1,X2,…,Xp)T,其協(xié)方差矩陣為設(shè)li=(l1i,l2i,…,lpi)T(i=1,2,…,p)為p個常數(shù)向量,考慮如下線性組合:第82頁，課件共97頁，創(chuàng)作于2023年2月我們希望用Y1代替原來p個變量,這就要求Y1盡可能的反映原p個變量的信息,即Var(Y1)越大.為此,我們對li做如下限制,否則Var(Y1)無界,即:因此,我們希望在約束條件l1Tl1=1

之下,求l1使達(dá)到最大,由此l1所確定的隨機(jī)變量Y1=l1TX

稱為X1,X2,…,Xp的第一主成分.第83頁，課件共97頁，創(chuàng)作于2023年2月如果第一主成分Y1還不足以反映原變量的信息,考慮采用Y2.但要求Y1與Y2不相關(guān),即于是,在約束條件及之下,求l2

使Var(Y2)達(dá)到最大,由此l2所確定的隨機(jī)變量Y2=l2TX稱為X1,X2,…,Xp的第二主成分.一般,在約束條件及(k=1,2,…,i-1)之下,求li

使Var(Yi)達(dá)到最大,由此li所確定的隨機(jī)變量Yi=liTX稱為X1,X2,…,Xp的第i個主成分.第84頁，課件共97頁，創(chuàng)作于2023年2月并且有:定理1

設(shè)∑是X=(X1,X2,…,Xp)T的協(xié)方差矩陣,∑的特征值及其相應(yīng)的正交單位特征向量分別為及e1,e2,…,ep,則X的第i個主成分為第85頁，課件共97頁，創(chuàng)作于2023年2月下面進(jìn)一步討論X1,X2,…,Xp的方差與各主成分的方差之間的關(guān)系,以確定各主成分所包含的信息占總信息的份額.易證下面結(jié)果:定理2設(shè)Yi=eiTX(i=1,2,…,p)為X的p各主成分,則:當(dāng)時，達(dá)到最大值第86頁，課件共97頁，創(chuàng)作于2023年2月定義第k個主成分Yk的貢獻(xiàn)率為:前m個主成分Y1,Y2,…,Ym的累計(jì)貢獻(xiàn)率為:在實(shí)際應(yīng)用中,通常選取m<p,使前m個累計(jì)貢獻(xiàn)率達(dá)到一定的比例(80%～90%).這樣用前m

個主成分代替原來的變量X1,X2,…,Xp而不至于損失太多的信息,從而到達(dá)減少變量個數(shù)的目的.第87頁，課件共97頁，創(chuàng)作于2023年2月在實(shí)際問題中,一般∑(或ρ)是未知的,需要通過樣本來估計(jì).設(shè)其中（2）主成分的計(jì)算方法第88頁，課件共97頁，創(chuàng)作于2023年2月分別以S和R作為∑和ρ的估計(jì),按前面所述的方法求得的主成分稱為樣本主成分.具體有如下結(jié)論:其中x=(x1,x2,…,xp)T為X的任一觀測值.當(dāng)依次代入X的n個觀測值xk=(x1k,x2k,…,xpk)T

時,便得到第i個樣本主成分yi的n個觀測值yik(k=1,2,…,n).設(shè)S=(sij)p×p是樣本協(xié)方差矩陣,其特征值為

,相應(yīng)的正交單位化特征向量為

,則第i個樣本主成分為:第89頁，課件共97頁，創(chuàng)作于2023年2月這時

第i個樣本主成分的貢獻(xiàn)率為:

前m個樣本主成分的累計(jì)貢獻(xiàn)率為:第90頁，課件共97頁，創(chuàng)作于2023年2月為了消除量綱的影響,我們可以對樣本進(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)化樣本主成分.這時標(biāo)準(zhǔn)化樣本的樣本總方差為p.第91頁，課件共97頁，創(chuàng)作于2023年2月3）主成分解釋從代數(shù)觀點(diǎn)看主成分就是p個變量X1,X2,…,Xp的一些特殊的線性組合.在幾何上這些線性組合正是把X1,X2,…,Xp構(gòu)成的坐標(biāo)系旋轉(zhuǎn)產(chǎn)生新坐標(biāo)系,新坐標(biāo)系軸使之通過樣本變差最大的方向(或說具有最大的樣本方差).以最簡單的二元正態(tài)變量來說明主成分的幾何意義.設(shè)有n個樣本,每個樣本有p個變量記為X1,X2,…,Xp,它們的綜合變量記為Y1,Y2,…,Yp.當(dāng)p=2時,原變量是X1,X2,設(shè)X=(X1,X2)’～N2(μ