第6章 特征的提取與選擇

第6章特征的選擇與提取

模式識別的三大核心問題:

特征數(shù)據(jù)采集分類識別特征提取與選擇

分類識別的正確率取決于對象的表示、訓練學習和分類識別算法。【W(wǎng)hy】主要內(nèi)容1.引言2類別可分離性判據(jù)3特征選擇4.特征提取5.K-L變換及PCA1.引言

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

目的：使在最小維數(shù)特征空間中異類模式點相距較遠（類間距離較大），而同類模式點相距較近（類內(nèi)距離較小）。人臉識別的例子

ORL(http://www.cl.cam.ac.uk/research/dtg/attarchive/facedatabase.html)人臉數(shù)據(jù)庫中，每幅圖像的分辨率為112×92，如果將每個像素作為1維特征，則高達10304維。若把所有的原始特征都作為分類特征送到分類器，不僅使得分類器復雜，分類判別計算量大，而且分類錯誤概率也不一定??；原始特征的特征空間有很大的冗余，完全可以用很小的空間相當好地近似表示圖像，這一點與壓縮的思想類似。因此有必要減少特征數(shù)目，以獲取“少而精”的分類特征，即獲取特征數(shù)目少且能使分類錯誤概率小的特征向量。使作為識別分類用的特征應(yīng)具備以下幾個條件：(1)具有很大的識別信息量。即所提供的特征應(yīng)具有很好的可分性，使分類器容易判別。(2)具有可靠性。對那些模棱兩可，似是而非不易判別的特征應(yīng)該去掉。(3)具有盡可能強的獨立性。重復的、相關(guān)性強的特征只選一個，因為強的相關(guān)性并沒有增加更多的分類信息，不能要。(4)數(shù)量盡可能少，同時損失的信息盡量小。x1x2x3..xd對象模式的特征的有效性直接影響分類器的設(shè)計和性能.由信息獲取部分獲得的原始數(shù)據(jù)量一般是相當大的.為了有效地實現(xiàn)分類識別，要對原始數(shù)據(jù)進行選擇或變換，得到最能反應(yīng)分類本質(zhì)的待征，構(gòu)成特征向量.這就是特征抽取與選擇的過程.傳感器y1y2y3..ym學習.訓練選擇.提取分類器特征選擇：從一組特征中挑選出一些最有效的特征以達到降低特征空間維數(shù)的目的，這個過程叫特征選擇。特征提?。簩⒁唤M高維特征，通過變換的方法得到一組新的低維特征，這個過程叫特征提取。特征形成：

根據(jù)被識別的對象產(chǎn)生出一組基本特征（也可稱為原始特征），它可以是計算出來的，也可以是用儀表或傳感器測量出來的。

有時特征提取和選擇并不是截然分開的。例如，可以先將原始特征空間映射到維數(shù)較低的空間，在這個空間中再進行選擇以進一步降低維數(shù)；也可以先經(jīng)過選擇去掉那些明顯沒有分類信息的特征，再進行映射以降低維數(shù)。特征提取特征選擇概念描述

模式識別中減少特征數(shù)目(或壓縮特征空間)的方法有兩種：一種是特征提取，另一種是特征選擇。

原始特征：通過直接測量得到的特征稱為原始特征。比如人體的各種生理指標（描述其健康狀況）；數(shù)字圖像中的各像素點的亮度值（描述圖像內(nèi)容），都是原始特征。

特征提?。和ㄟ^映射(變換)的方法把高維的特征向量變換為低維的特征向量。通過特征提取獲得的特征是原始特征集的某種組合，即A:X→Y，可見新的特征中包含有原有全體特征的信息。

特征選擇：從原始特征中挑選出一些最有代表性、分類性能好的特征以達到降低特征空間維數(shù)的目的。也就是說，特征選擇就是從已有的D個原始特征中挑選出d個特征組成一個特征子集，同時將D-d個對類別可分離性無貢獻的或貢獻不大的特征簡單地忽略掉。

特征提取與具體問題有很大關(guān)系，目前沒有理論能給出對任何問題都有效的特征提取方法。由于在許多實際問題中，那些最重要的特征往往不易找到，使得特征選擇和特征提取成為構(gòu)造模式識別系統(tǒng)最困難的任務(wù)之一。如：?用傅立葉變換或小波變換的系數(shù)作為圖像的特征；?指紋的特征；?統(tǒng)計特征，如矩、灰度共生矩陣(Co-occurrence

Matrix)等；?用PCA方法作特征壓縮；?用LDA方法作特征壓縮。共性選擇方法(1)特征可以獲取

模式識別系統(tǒng)的主要處理設(shè)備是計算機，因此作為觀察對象的數(shù)字化表達，觀察對象應(yīng)該是可以通過數(shù)據(jù)采集設(shè)備輸入到計算機的。目前，市場上有各種傳感設(shè)備和數(shù)字化設(shè)備，如采集圖像信息的圖像卡和采集語音信息的聲卡等。作為特征，既可以是數(shù)字化表達的結(jié)果，也可以是在數(shù)字化表達基礎(chǔ)上形成的參數(shù)性質(zhì)的值，如圖像分割后的子目標特征表達等。共性選擇方法(2)類內(nèi)穩(wěn)定

選擇的特征對同一類應(yīng)具有穩(wěn)定性。由于模式類是由具有相似特性的若干個模式構(gòu)成的,因此它們同屬一類模式,其首要前提是特性相似,反映在取值上,就應(yīng)該有較好的穩(wěn)定性。共性選擇方法(3)類間差異

選擇的特征對不同的類應(yīng)該有差異。若不同類的模式的特征值差異很小，則說明所選擇的特征對于不同的類沒有什么差異，作為分類的依據(jù)時，容易使不同的類產(chǎn)生混淆，使誤識率增大。一般來講，特征的類間差異應(yīng)該大于類內(nèi)差異。特征的類別1物理的：物理特征是比較直接、人們?nèi)菀赘兄奶卣鳎话阍谠O(shè)計模式識別系統(tǒng)時容易被選用。如為了描述指定班級中的某個學生，可以用以下物理特征：性別、身高、胖瘦、膚色等外在特征。物理特征雖然容易感知,卻未必能非常有效地表征分類對象。2結(jié)構(gòu)的：結(jié)構(gòu)特征的表達能力一般要高于物理特征，如漢字識別的成功實現(xiàn)離不開結(jié)構(gòu)特征的選擇。結(jié)構(gòu)特征的表達是先將觀察對象分割成若干個基本構(gòu)成要素，再確定基本要素間的相互連接關(guān)系。如指紋的識別就是基于結(jié)構(gòu)信息完成的。結(jié)構(gòu)信息對對象的尺寸往往不太敏感，如漢字識別時，識別系統(tǒng)對漢字大小不敏感，只對筆劃結(jié)構(gòu)信息敏感。人臉的五官結(jié)構(gòu)信息等，是目前認定人的身份的重要參數(shù)。

3數(shù)學的：易于用機器定量描述和判別，如基于統(tǒng)計的特征，數(shù)學特有時和觀察對象的固有特性沒有任何聯(lián)系，有時則是物理特征或結(jié)構(gòu)特征的計算結(jié)果。

對特征空間的改造、優(yōu)化、主要的目的是降維，即把維數(shù)高的特征空間改成維數(shù)低的特征空間。降維主要有兩種途徑。一種是刪選掉一些次要的特征，問題在于如何確定特征的重要性，以及如何刪選。另一種方法是使用變換的手段，在這里主要限定在線性變換的方法上，通過變換來實現(xiàn)降維。

實現(xiàn)特征選擇的前提是確定特征是否有效的標準，在這種標準下，尋找最有效的特征子集。用于特征選擇的特征既可以是原始特征，也可以是經(jīng)數(shù)學變換后得到的二次特征。需要注意，特征提取一定要進行數(shù)學變換，但數(shù)學變換未必就是特征提取。【問題的提出】【問題的提出】典型的運用線性變換對原特征空間優(yōu)化的基本方法，進一步深入理解模式識別處理問題的基本方法-確定準則函數(shù)，并通過計算進行優(yōu)化。使用特征選擇方法的基本問題。1．什么叫特征空間？如果我們用顏色、尺寸、重量來衡量水果的構(gòu)造的特特空間是幾維空間？2．如果用顏色、尺寸與重量組成的特征空間來區(qū)分蘋果與梨，你認為這三種度量中的哪種最有效？為什么？能否想像這兩種水果在這個三維空間的分布？如果用這個特征空間來區(qū)分紅蘋果與櫻桃，你想像一下這兩類水果在特征空間如何分布？能否對這兩種情況設(shè)計更經(jīng)濟有效的特征空間？【問題的提出】3．如果兩類物體在一個二維特征空間如圖分布,能否用刪除其中任一維來優(yōu)化特征空間？有沒有什么方法能得到一個對分類很有利的一維特征空間？【問題的提出】

4．上題的答案可用右圖Y1與Y2組成的空間表示？你認為哪個分量可以刪掉？

5．你有沒有辦法將原在X1、X2空間表示的數(shù)改成用Y1、Y2空間表示？【問題的提出】1．需要找到描述事物方法的選擇與設(shè)計-確定準則函數(shù)方案1.從框架的左邊框到數(shù)字之間的距離變化反映了不同數(shù)字的不同形狀，這可以用來作為數(shù)字分類的依據(jù)。方案2.強調(diào)分析不同截面的信號，如在框架的若干部位沿不同方向截取截面分析從背景到字，以及從字到背景轉(zhuǎn)換的情況,如AB截面切割字符三次，CD截面切割字符一次等?！締栴}的提出—總結(jié)】2．需要確定特征空間的優(yōu)化---優(yōu)化算法

這個層次的工作發(fā)生在已有了特征的描述方法之后，也就是已有了一個初始的特征空間，如何對它進行改造與優(yōu)化的問題。一般說來要對初始的特征空間進行優(yōu)化是為了降維。即初始的特征空間維數(shù)較高。能否改成一個維數(shù)較低的空間，稱為優(yōu)化，優(yōu)化后的特征空間應(yīng)該更有利于后續(xù)的分類計算

例用RGB顏色空間和HSI顏色空間【問題的提出】用RGB顏色空間和HSI顏色空間RGB和HSI是兩種常用的顏色空間，雖然它們描述顏色的范圍是一樣的，也有確定的轉(zhuǎn)換關(guān)系，但是用這兩種不同的特征描述圖像，對以后的識別工作會有很大影響2類別可分離性判據(jù)【概念】特征選擇與提取的任務(wù)是找出一組對分類最有效的特征，因此需一準則。概念：數(shù)學上定義的用以衡量特征對分類的效果的準則，實際問題中需根據(jù)實際情況人為確定。誤識率判據(jù)：理論上的目標，實際采用困難（密度未知，形式復雜，樣本不充分，…）可分性判據(jù)：實用的可計算的判據(jù)為什么需要類別可分離性判據(jù)一般說來分類器最基本的性能評估是其分類的錯誤率如果能用反映錯誤率大小的準則，在理論上是最合適的

對錯誤率的計算是極其復雜的，以至于很難構(gòu)筑直接基于錯誤率的判據(jù)為此人們設(shè)法從另一些更直觀的方法出發(fā)，設(shè)計出一些準則，用來檢驗不同的特征組合對分類性能好壞的影響，甚至用來導出特征選擇與特征提取的方法 這些準則就是類別可分離性判據(jù)

【概念】【類別可分離性判據(jù)應(yīng)滿足的條件】類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準則理想準則：某組特征使分類器錯誤概率最小常用類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)，也可以用：相關(guān)性、分類的錯誤率等參數(shù)?！靖拍睢炕诰嚯x的可分性判據(jù)的實質(zhì)是Fisher準則的延伸，即綜合考慮不同類樣本的類內(nèi)聚集程度與類間的離散程度這兩個因素。判據(jù)的優(yōu)化體現(xiàn)出降維特征空間較好地體現(xiàn)類內(nèi)密集。一些不能體現(xiàn)類間分隔開的特征很可能被排除掉了。離散度矩陣（散布矩陣）：一種描述數(shù)據(jù)離散程度的方法。6.2.1基于距離的可分性判據(jù)【類內(nèi)類間距離】基于距離度量是分類的常用的重要依據(jù)，因為一般情況下同類物體在特征空間呈聚類狀態(tài)，即從總體上說同類物體內(nèi)各樣本由于具有共性，因此類內(nèi)樣本間距離應(yīng)比跨類樣本間距離小。Fisher準則是以使類間距離盡可能大同時又保持類內(nèi)距離較小這一種原理為基礎(chǔ)的。同樣在特征選擇與特征提取中也使用類似的原理，這一類被稱為基于距離的可分性判據(jù)。為了度量類內(nèi)、類間的距離，可用其他方法描述方法，即描述樣本的離散程度的方法。6.2.1基于距離的可分性判據(jù)【類內(nèi)類間距離】各類樣本可以分開是因為它們位于特征空間的不同區(qū)域，顯然這些區(qū)域之間距離越大，類別可分性就越大。如何表示兩個類之間的距離?【類內(nèi)類間距離】【用于可分性判據(jù)的類內(nèi)類間距離】【用于可分性判據(jù)的類內(nèi)類間距離】定義【用于可分性判據(jù)的類內(nèi)類間距離】常用的基于類內(nèi)類間距離的可分性判據(jù)：1)基于類內(nèi)類間距離的可分離性判據(jù)是一種常用的判據(jù)，它實際上是各類向量之間的平均距離。2)具體而言，即J(x)表示各類特征向量之間的平均距離，我們通常認為J(x)越大，可分離性越好。

3)這種判據(jù)優(yōu)點是計算簡單；缺點是當類間距離較小，類內(nèi)距離較大時，判據(jù)仍有可能取得較大的值，而此時的可分離性并不大。特點：直觀，易于實現(xiàn)（用樣本計算），較常用。不能確切表明各類分布重疊情況，與錯誤率無直接聯(lián)系。當各類協(xié)差相差不大時，用此種判據(jù)較好。選擇原則：ii.計算簡單，易于實現(xiàn)。iii.數(shù)學上容易處理。準則函數(shù)的遞推計算問題:每增/減一個特征，只影響向量中的一個元素，矩陣的一行和一列?！居糜诳煞中耘袚?jù)的類內(nèi)類間距離】i.實際分類問題需要，找與分類性能關(guān)系密切者?！净诟怕史植嫉目煞中耘袚?jù)】考查兩類分布密度之間的交疊程度【基于概率分布的可分性判據(jù)】定義：兩個密度函數(shù)之間的距離：它必須滿足三個條件：【基于概率分布的可分性判據(jù)】具體定義有多種：Bhattacharyya距離Chernoff

界散度【基于概率分布的可分性判據(jù)】正態(tài)分布情況下：【基于概率分布的可分性判據(jù)】幾種常見的概率距離準則(J)和概率相關(guān)性準則(I)

最佳分類器由后驗概率確定，所以可由特征的后驗概率分布來衡量它對分類的有效性。兩種特殊情形下最佳分類器的錯誤率:1)各類后驗概率是相等錯誤率錯誤率可見后驗概率越集中,錯誤概率就越小.后驗概率分布越平緩(接近均勻分布)，則分類錯誤概率就越大。【熵可分性判據(jù)】

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

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

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

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

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

從特征提取的角度看，顯然用具有最小不確定性的那些特征進行分類是有利的。在信息論中用“熵”作為不確定性的度量.【熵可分性判據(jù)】【熵可分性判據(jù)】熵：事件不確定性的度量A事件的不確定性大（熵大），則對A事件的觀察所提供的信息量大。思路：【熵可分性判據(jù)】定義熵函數(shù)滿足如下條件①規(guī)一化②對稱性③確定性④擴張性⑤連續(xù)性⑥分枝性即函數(shù)式內(nèi)項的次序可以變換不影響熵的值【熵可分性判據(jù)】常用的熵函數(shù)Shannon熵：平方熵：廣義熵：【熵可分性判據(jù)】結(jié)論【熵可分性判據(jù)】舉例：圖像分割3.特征選擇問題：從D維特征中選取d維（d<D），使分類性能最佳（J最大）?！締栴}的提出】搜索算法可分為三類算法分為完全搜索(Complete)，啟發(fā)式搜索(Heuristic)，隨機搜索(Random)3大類一、窮舉算法：計算每一可能的組合，逐一比較準則函數(shù)。適用于：d或D?d很小（組合數(shù)較少）的情況。二、分支定界算法：從頂向下，有回溯應(yīng)用條件：準則函數(shù)單調(diào)性基本思想：按照一定的順序?qū)⑺锌赡艿慕M合排成一棵樹，沿樹進行搜索，避免一些不必要的計算，使找到最優(yōu)解的機會最早。【完全搜索方法】特征總數(shù)D以及選擇特征數(shù)d增加時，窮舉法計算量迅速上升?！就耆阉鞣椒ā扛F舉法存在的問題：非最優(yōu)，但某些情況下最優(yōu)，實現(xiàn)簡單（1）單獨最優(yōu)組合選前d個單獨最佳的特征（2）SFS法（SequentialForwardSelection：順序前進）：從底向上每加入一個特征尋優(yōu)一次，使加入該特征后特征函數(shù)最大。特點：考慮了特征間的相關(guān)性，但某特下一經(jīng)入選，即無法淘汰（3）廣義SFS法（GSFS）從底向上，每次增加l個特征。考慮了新增特征中的相關(guān)性計算量比SFS大，若l=d，（一步加滿），則就是窮舉法【啟發(fā)式搜索方法】（4）SBS法（順序后退，后向貫序）從頂向下，每次減一個特征與SFS相對，一旦失去，無法換回。（5）廣義SBS法（GSBS）從頂向下，每次減r個特征SFS與SBS都屬于貪心算法，容易陷入局部最優(yōu)值模擬退火算法（SA,SimulatedAnnealing）

遺傳算法(GA,GeneticAlgorithms)【隨機搜索方法】【爬山算法】爬山算法是一種簡單的貪心搜索算法，該算法每次從當前解的臨近解空間中選擇一個最優(yōu)解作為當前解，直到達到一個局部最優(yōu)解。其主要缺點是會陷入局部最優(yōu)解，而不一定能搜索到全局最優(yōu)解。如下圖所示：假設(shè)C點為當前解，爬山算法搜索到A點這個局部最優(yōu)解就會停止搜索，因為在A點無論向那個方向小幅度移動都不能得到更優(yōu)的解。【模擬退火算法】思想1）爬山法是完完全全的貪心法，每次都鼠目寸光的選擇一個當前最優(yōu)解，因此只能搜索到局部的最優(yōu)值。模擬退火其實也是一種貪心算法，但是它的搜索過程引入了隨機因素。模擬退火算法以一定的概率來接受一個比當前解要差的解，因此有可能會跳出這個局部的最優(yōu)解，達到全局的最優(yōu)解。以上圖為例，模擬退火算法在搜索到局部最優(yōu)解A后，會以一定的概率接受到E的移動。也許經(jīng)過幾次這樣的不是局部最優(yōu)的移動后會到達D點，于是就跳出了局部最大值A(chǔ)。

若移動后得到更優(yōu)解，則總是接受該移動，若移動后的解比當前解要差，則以一定的概率接受移動，而且這個概率隨著時間推移逐漸降低（逐漸降低才能趨向穩(wěn)定）。假設(shè)在狀態(tài)xold時，系統(tǒng)受到某種擾動而使其狀態(tài)變?yōu)閤new。與此相對應(yīng)，系統(tǒng)的能量也從E(xold)變成E(xnew)，系統(tǒng)由狀態(tài)xold變?yōu)闋顟B(tài)xnew的接受概率p。1)隨機產(chǎn)生一個初始解x0，令xbest＝x0，并計算目標函數(shù)值E(x0);2)設(shè)置初始溫度T(0)=To，迭代次數(shù)i=1;3)DowhileT(i)>Tmin1)forj=1~k2)對當前最優(yōu)解xbest按照某一鄰域函數(shù)，產(chǎn)生一新的解xnew。計算新的目標函數(shù)值E(xnew)，并計算目標函數(shù)值的增量ΔE=E(xnew)-E(xbest)。3)如果ΔE＜0，則xbest=xnew；4)如果ΔE＞0，則p=exp(-ΔE/T(i));1)如果c=random[0,1]<p，xbest=xnew;否則xbest=xbest。5)Endfor4)i=i＋1；5)EndDo6)輸出當前最優(yōu)點，計算結(jié)束【模擬退火算法】

基本遺傳算法（SimpleGeneticAlgorithms，簡稱SGA），其遺傳進化操作過程簡單，容易理解，是其它一些遺傳算法的雛形和基礎(chǔ)。

【基本遺傳算法】基本遺傳算法的組成（1）編碼（產(chǎn)生初始種群）（2）適應(yīng)度函數(shù)（3）遺傳算子（選擇、交叉、變異）（4）運行參數(shù)算法描述：首先隨機產(chǎn)生一批特征子集，并用評價函數(shù)給這些特征子集評分，然后通過交叉、突變等操作繁殖出下一代的特征子集，并且評分越高的特征子集被選中參加繁殖的概率越高。這樣經(jīng)過N代的繁殖和優(yōu)勝劣汰后，種群中就可能產(chǎn)生了評價函數(shù)值最高的特征子集。

編碼

GA是通過某種編碼機制把對象抽象為由特定符號按一定順序排成的串。正如研究生物遺傳是從染色體著手，而染色體則是由基因排成的串。SGA使用二進制串進行編碼?！净具z傳算法】幾個術(shù)語

基因型：1000101110110101000111

表現(xiàn)型：0.637197編碼解碼個體（染色體）基因【基本遺傳算法】初始種群：SGA采用隨機方法生成若干個個體的集合，該集合稱為初始種群。初始種群中個體的數(shù)量稱為種群規(guī)模。適應(yīng)度函數(shù)

：遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。【基本遺傳算法】

遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體?！净具z傳算法】選擇算子：交叉算子：所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率Pc按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算是遺傳算法區(qū)別于其他進化算法的重要特征，它在遺傳算法中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。SGA中交叉算子采用單點交叉算子。交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000交叉點【基本遺傳算法】交叉算子示意圖

所謂變異運算，是指依據(jù)變異概率Pm將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。遺傳算法中的變異運算是產(chǎn)生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。SGA中變異算子采用基本位變異算子?！净具z傳算法】變異算子基本位變異算子的執(zhí)行過程變異前：000001110000000010000變異后：000001110001000010000變異點【基本遺傳算法】SGA的框圖產(chǎn)生初始群體是否滿足停止準則是輸出結(jié)果并結(jié)束計算個體適應(yīng)度值比例選擇運算單點交叉運算基本位變異運算否產(chǎn)生新一代群體執(zhí)行M/2次【基本遺傳算法】4特征提取特征選擇：從D個特征中選出d個特征提取：把D個特征變?yōu)閐個新特征目的：更好分類和/或減少計算量【基本概念】按歐氏距離度量的特征提取方法基于距離可分性判據(jù)的特征優(yōu)化過程是通過一個線性變換實現(xiàn)特征提取在這里意味著找到一個線性變換W,對原始特征向量Y=[y1,…，yD]T實行映射變換W：Y→X，得到維數(shù)減少的向量X=[x1,…，xd]T，即

W為D×d矩陣【歐氏距離準則下的特征提取】歐氏距離的判據(jù)【歐氏距離準則下的特征提取】【歐氏距離準則下的特征提取】利用W（D×d矩陣）線形變換后，希望變換后的特征向量能滿足使某個準則函數(shù)達到極值的要求使用J2判據(jù)進行特征提取注意：如果對特征空間實行一個D×D矩陣的非奇異線性變換，J2保持不變【歐氏距離準則下的特征提取】例如對原特征空間實行一D×D線性變換A令Sw,Sb為原空間離散度矩陣S*w,S*b為映射后的離散度矩陣，則：

S*b=A

Sb

AT S*w=A

Sw

AT經(jīng)變換后的J2變?yōu)?

J2*(A)=tr[(A

Sw

AT)-1

A

Sb

AT] =tr[(AT)-1

Sw-1Sb

AT]=tr[Sw-1Sb]=J2(A)【歐氏距離準則下的特征提取】使用J2判據(jù)進行特征提取因而以下討論的特征提取變換，只考慮是降維的即用D×d矩陣(d＜D)進行變換其目的是在維數(shù)d的條件下，使相應(yīng)的判據(jù)為最大【歐氏距離準則下的特征提取】使用J2判據(jù)進行特征提取將J2判據(jù)表示成變換W的函數(shù)令Sw,Sb為原空間離散度矩陣，S*w,S*b為映射后的離散度矩陣:

S*b=WT

Sb

W S*w=WT

Sw

W則經(jīng)變換后的J2變?yōu)?

J2(W)=tr[(WT

Sw

W)-1

WT

Sb

W]【歐氏距離準則下的特征提取】使用J2判據(jù)進行特征提取求使J2(W)最大的W解可利用特征值方法對W的各分量求偏導數(shù)，并另其為零，可以確定W值。結(jié)論:對J2

，J2

，J5來說,使判據(jù)達到最大的變換W如下:設(shè)矩陣Sw-1Sb的本征值為λ1，λ2…λD，按大小順序排列為:

λ1≥

λ2

≥…≥λD，【歐氏距離準則下的特征提取】使用J2判據(jù)進行特征提取則選前d個本征值對應(yīng)的本征向量作為W即:W=[μ1，μ

2

…μ

d]此時:

J2(W)=λ1+λ2+…+λd【歐氏距離準則下的特征提取】1.Chernoff

概率距離【概率距離判據(jù)下的特征提取方法】【概率距離判據(jù)下的特征提取方法】【概率距離判據(jù)下的特征提取方法】【概率距離判據(jù)下的特征提取方法】多類情況【概率距離判據(jù)下的特征提取方法】【基于判別熵最小化的特征提取】【基于判別熵最小化的特征提取】5K-L變換及PCAK-L變換及PCA1.引言2基于K-L展開式的特征提取3主成分分析(PCA)4.應(yīng)用舉例2基于K-L展開式的的特征提取非監(jiān)督情況下，沒有已知類別的訓練樣本，可分離性指標無從定義。只能根據(jù)知識和/或假定來進行特征選擇。通常用方差作為衡量指標，認為選擇或提取總體未知樣本方差越大，越有利于將它分開。（實際上，我們無法確認方差大的特征一定有利于分類，但至少方差過小的特征是不利于分類的。）【非監(jiān)督的特征提取】特征提?。河糜成洌ɑ蜃儞Q）的方法把原始特征變換為較少的新特征PCA(PrincipleComponentAnalysis)方法：

進行特征降維變換，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的的變換方法使損失最小。K-L(Karhunen-Loeve)變換：最優(yōu)正交線性變換，相應(yīng)的特征提取方法被稱為PCA方法特征提取與K-L變換基本原則：進行特征降維變換，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的變換方法使損失最小。K-L變換：以最小均方誤差為準則，將原特征向量作變換后再壓縮原特征維數(shù)的方法。特征提取與K-L變換K-L變換最佳的含義K-L變換討論的是特征空間的降維，因此，這個最佳是與降維聯(lián)系起來的。對于降維，原特征空間是D維的，現(xiàn)希望降至d維(d<D)。不失一般性，認為D為無限大的情況，并設(shè)原信號x可用一組正交變換基uj表示：現(xiàn)要求降維至d維，也就是說將d+1維以上的成分略去，其表示成:現(xiàn)在的問題是如何在給定一個樣本集條件下要找一個好的正交變換，能使這種誤差從總體上來說是最小。顯然原信號會因此受到一些損失，而每個信號的損失則表示成x與之差。注意這里講的是總體，這是因為降維以后，樣本集中的每個樣本數(shù)據(jù)都受到損失，要衡量的是總體效果。在這種情況下最常用的指標是均方誤差最小，或稱均方誤差的期望值最小，即：或者說要找一個正交變換，使樣本集截取所造成的損失的均方誤差的期望值為最小。uj是確定性向量，則公式寫為：令：欲使該均方誤差為最小，即在確保正交變換的條件下，使

達最小的問題，這可用拉格朗日乘子法求解。有：并對uj求導數(shù)，得：

可見向量uj，j=d+1,…,是矩陣特征值的特征向量截斷誤差為:

取前d項特征值對應(yīng)的特征向量組成的坐標系，可使向量的均方誤差為最小。滿足上述條件的變換就是K-L變換。將i按其大小順序排列：結(jié)論：以矩陣的特征向量作為坐標軸來展開x時，其截斷均方誤差具有極值性質(zhì)，且當取d個uj,j=1,2,…,d來逼近x時，均方誤差為：強調(diào)K-L變換的特殊性。K-L變換是一種獨特的正交變換，它與一些常用的正交變換不同。最常見的正交變換，如傅立葉變換，哈達瑪變換，離散余弦變換等都是一種通用的正交變換，它們各自有固定的形式，如傅立葉變換的基是以頻率為參數(shù)的e的指數(shù)函數(shù)族組成。它主要用來對數(shù)據(jù)作頻譜分析、濾波等。K-L變換的基并沒有固定的形式，它是從對給定數(shù)據(jù)集{x}進行計算產(chǎn)生的。給定的數(shù)據(jù)集不同，得到的K-L變換基函數(shù)也因此而不同。由于它對給定數(shù)據(jù)集{x}存在依賴關(guān)系，它能在降低維數(shù)時仍能較好地描述數(shù)據(jù)，因此是模式識別中降低特征空間維數(shù)的有效方法。由于它的正交基函數(shù)族是從訓練樣本集中計算出來的，因此并不存在一種對任何數(shù)據(jù)都適用的K-L變換基。一般的作法是先用一組訓練數(shù)據(jù)計算出K-L變換基，然后用這組基來重構(gòu)或分析其它數(shù)據(jù)。K-L變換方法1.通過變換來尋求有效的特征向量，原樣本(特征向量)x經(jīng)過T變換變?yōu)樾碌奶卣飨蛄縴,將y中的N個元素中的N-M個用預(yù)先選定的常數(shù)代替或者舍去后所表征的x*向量與原來x的均方誤差最小。2.將原特征向量組用維數(shù)較少的特征向量代替?；静襟E：對N個樣本(特征向量)，求產(chǎn)生矩陣。對矩陣，求N個特征值與特征向量。將N

個特征值按值的大小的順序排列。取M個特征值(特征向量)，組成新的變換矩陣yM=TxN

代替原來的特征向量。如何求解產(chǎn)生矩陣?舉例:四個樣本用K-L變換降維(維數(shù)為1,四個樣本)解:1.求協(xié)方差矩陣2.協(xié)方差矩陣的本征值及本征向量u1u2x1x23.求新的變換矩陣，新的特征空間保留1舍棄2u1u2y1y2y3y44.計算特征變換所引起的均方誤差上述變換并不引起誤差x1x23.主成分分析例子：小學各科成績的評估可以用下面的綜合成績來體現(xiàn)：a1×語文＋a2×數(shù)學＋a3×自然＋a4×社會科學

確定權(quán)重系數(shù)的過程就可以看作是主成分分析的過程，得到的加權(quán)成績總和就相對于新的綜合變量——主成分【問題的提出】推而廣之，當某一問題需要同時考慮好幾個因素時，我們并不對這些因素個別處理而是將它們綜合起來處理。這樣綜合處理的原則是使新的綜合變量能夠解釋大部分原始數(shù)據(jù)方差?！締栴}的提出】由于各種量測到數(shù)據(jù)通常是以矩陣的形式記錄、表達和存儲的，實際中的很多數(shù)據(jù)信息往往是重疊與冗余的。從線性代數(shù)的觀點來看，就是這些數(shù)據(jù)矩陣中存在相關(guān)的行或列。因此需要對其進行處理和提煉，抽取出有意義、獨立的變量。

主成分分析(PrincipalComponentAnalysis,簡稱PCA)是一種常用的基于變量協(xié)方差矩陣對信息進行處理、壓縮和抽提的有效方法?！締栴}的提出】情形II下總分的方差為0，顯然不能反映三個學生各科成績各有所長的實際情形，而紅色標記的變量對應(yīng)的方差最大，可反映原始數(shù)據(jù)的大部分信息?！締栴}的提出】為什么要根據(jù)方差確定主成分？上例可見，用總分有時可以反映原分數(shù)表的情況，保留原有信息，有時則把信息丟盡，不能反映原有的情況和差異。根據(jù)總分所對應(yīng)的方差可以確定其代表了多大比例的原始數(shù)據(jù)（分數(shù)）信息。一般來說，我們希望能用一個或少數(shù)幾個綜合指標（分數(shù)）來代替原來分數(shù)表做統(tǒng)計分析，而且希望新的綜合指標能夠盡可能地保留原有信息，并具有最大的方差?！締栴}的提出】對主成分的要求壓縮變量個數(shù)，用較少的變量去解釋原始數(shù)據(jù)中的大部分變量，剔除冗余信息。即將許多相關(guān)性很高的變量轉(zhuǎn)化成個數(shù)較少、能解釋大部分原始數(shù)據(jù)方差且彼此互相獨立的幾個新變量，也就是所謂的主成分。這樣就可以消除原始變量間存在的共線性，克服由此造成的運算不穩(wěn)定、矩陣病態(tài)等問題?！締栴}的提出】主成分分析的目的PCA分析在很多領(lǐng)域有廣泛應(yīng)用（模式識別、化學組分的定量分析、多元物系的組分數(shù)目確定、動力學反應(yīng)機理的確定等）主成分變換將三維空間的樣本顯示在二維空間【問題的提出】舉例根據(jù)方差最大化原理，用一組新的、線性無關(guān)且相互正交的向量來表征原來數(shù)據(jù)矩陣的行（或列）。這組新向量（主成分）是原始數(shù)據(jù)向量的線性組合。通過對原始數(shù)據(jù)的平移、尺度伸縮(減均值除方差)和坐標旋轉(zhuǎn)(特征分解)，得到新的坐標系(特征向量)后，用原始數(shù)據(jù)在新坐標系下的投影(點積)來替代原始變量。一.主成分分析的基本原理假定有n個樣本，每個樣本共有p個變量，構(gòu)成一個n×p階的數(shù)據(jù)矩陣

當p較大時，在p維空間中考察問題比較麻煩。為了克服這一困難，就需要進行降維處理，即用較少的幾個綜合指標代替原來較多的變量指標，而且使這些較少的綜合指標既能盡量多地反映原來較多變量指標所反映的信息，同時它們之間又是彼此獨立的。

定義：記x1，x2，…，xP為原變量指標，z1，z2，…，zm（m≤p）為新變量指標系數(shù)lij的確定原則：①

zi與zj（i≠j；i，j=1，2，…，m）相互無關(guān)；②

z1是x1，x2，…，xP的一切線性組合中方差最大者，z2是與z1不相關(guān)的x1，x2，…，xP的所有線性組合中方差最大者,或者說是對原始數(shù)據(jù)中尚未被z1解釋的差異部分擁有最大的解釋能力；

……zm是與z1，z2，……，zm－1都不相關(guān)的x1，x2，…xP，的所有線性組合中方差最大者。則新變量指標z1，z2，…，zm分別稱為原變量指標x1，x2，…，xP的第一，第二，…，第m主成分。

從以上的分析可以看出，主成分分析的實質(zhì)就是確定原來變量xj（j=1，2，…，p）在諸主成分zi（i=1，2，…，m）上的載荷lij（i=1，2，…，m；j=1，2，…，p）。因此主成分分析的關(guān)鍵就是確定這些系數(shù)。

從數(shù)學上可以證明，它們分別是的協(xié)方差（相關(guān)）矩陣的m個較大的特征值所對應(yīng)的特征向量。（一）計算相關(guān)系數(shù)矩陣

rij（i，j=1，2，…，p）為原變量xi與xj的相關(guān)系數(shù)，rij=rji，其計算公式為二、主成分分析的計算步驟

（二）計算特征值與特征向量

①

解特征方程，求出特征值，并使其按大小順序排列

②

分別求出對應(yīng)于特征值的特征向量，要求=1，即，其中表示向量的第j個分量。③

計算主成分貢獻率及累計貢獻率貢獻率累計貢獻率

一般取累計貢獻率達85%~95%的特征值所對應(yīng)的第1、第2、…、第m（m≤p）個主成分。

④

計算主成分載荷

⑤

各主成分的得分

關(guān)于特征值原始數(shù)據(jù)前的加權(quán)系數(shù)決定了新的綜合變量主成分（得分）的大小和性質(zhì)，通常稱為主成分軸或者載荷向量（載荷軸、載荷系數(shù)）。主成分分析的關(guān)鍵就是確定這些系數(shù)，這些系數(shù)構(gòu)成了新的坐標系，將原始變量在新的坐標系下投影就可求得新坐標系下的變量值（主成分得分）。主成分軸、載荷向量PC1=a1xi1+a2xi2+a3xi3PC2=b1xi1+b2xi2+b3xi3三維主成分分析示意圖三.主成分的特點☆主成分是原變量的線性組合；☆各個主成分之間互不相關(guān)；☆主成分按照方差從大到小依次排列，第一主成分對應(yīng)最大的方差（特征值）；☆每個主成分的均值為0、其方差為協(xié)方差陣對應(yīng)的特征值；☆不同的主成分軸（載荷軸）之間相互正交。主成分的特點☆

如果原來有p個變量，則最多可以選取p個主成分，這p個主成分的變化可以完全反映原來全部p個變量的變化；☆

如果選取的主成分少于p個，則這些主成分的變化應(yīng)盡可能多地反映原來全部p個變量的變化。主成分分析的優(yōu)點

★它能找到表現(xiàn)原始數(shù)據(jù)陣最重要的變量的組合★

通過表示最大的方差，能有效地直觀反映樣本之間的關(guān)系★

能從最大的幾個主成分的得分來近似反映原始的數(shù)據(jù)陣的信息例：有3個變量X1,X2與X3(p=3)，其16次（n=16）觀測值見下表：

四、主成分分析方法應(yīng)用舉例相關(guān)矩陣為：相關(guān)陣R的特征值分別為2.077,0.919,0.004，

前兩個主成分的累計貢獻率為99.866%。這說明第三個主成分所起作用非常小，可以只要兩個主成分。

HelpprincompinMATLAB

例：使用princomp作主分量分析

從代數(shù)觀點看主成分就是p個變量X1,X2,…,Xp的一些特殊的線性組合.在幾何上這些線性組合正是把X1,X2,…,Xp構(gòu)成的坐標系旋轉(zhuǎn)產(chǎn)生新坐標系,新坐標系軸使之通過樣本變差最大的方向(或說具有最大的樣本方差).以最簡單的二元正態(tài)變量來說明主成分的幾何意義.設(shè)有n個樣本,每個樣本有p個變量記為X1,X2,…,Xp,它們的綜合變量記為Y1,Y2,…,Yp.當p=2時,原變量是X1,X2,設(shè)X=(X1,X2)’～N2(μ,

∑

),它們有下圖的相關(guān)關(guān)系:對于二元正態(tài)分布變量,n個點的散布大致為一個橢圓,若在橢圓長軸方向取坐標軸Y1,在短軸方向取Y2,這相當于在平面上作一個坐標變換,即:Y2X2Y1X1可以看到Y(jié)1、Y2是原變量X1和X2的線性組合,用矩陣表示為顯然UT=U-1且是正交矩陣.如果上圖的橢圓是相當扁平的,可以只考慮長軸Y1方向上的波動,忽略Y2方向的波動.這樣,二維可以降為一維.一般情況,p個變量組成p維空間,n個樣本就是p維空間的n個點,對p元正態(tài)分布變量來說,找主成分的問題就是找p維空間中橢圓體的主軸問題.需要注意的地方在實際問題中,一般∑(或ρ)是未知的,需要通過樣本來估計.設(shè)其中分別以S和R作為∑和ρ的估計,按前面所述的方法求得的主成分稱為樣本主成分.具體有如下結(jié)論:其中x=(x1,x2,…,xp)T為X的任一觀測值.當依次代入X的n個觀測值xk=(x1k,x2k,…,xpk)T

時,便得到第i個樣本主成分yi

的n個觀測值yik

(k=1,2,…,n).設(shè)S=(sij)p×p

是樣本協(xié)方差矩陣,其特征值為

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

,則第i個樣本主成分為:

這時

第i個樣本主成分的貢獻率為:

前m個樣本主成分的累計貢獻率為:為了消除量綱的影響,我們可以對樣本進行標準化,即令則標準化數(shù)據(jù)的樣本協(xié)方差矩陣即為原數(shù)據(jù)的樣本相關(guān)矩陣R.由R出發(fā)所求得的樣本主成分稱為標準化樣本主成分.只要求出R的特征值及相應(yīng)的正交單位化特征向量,類似上述結(jié)果可求得標準化樣本主成分.這時標準化樣本的樣本總方差為p.例一設(shè)模式X=(X1,X2,X3)T的協(xié)方差矩陣為求X的各主成分.解:

易求得∑的特征值及其相應(yīng)的正交化特征向量分別為因此X的主成分為取第一主成分,則貢獻率為若取前兩個主成分,則累計貢獻率為因此,可用前兩個主成分代替原來三個變量.

%Example1%C