第6章 特征的提取與選擇_第1頁
第6章 特征的提取與選擇_第2頁
第6章 特征的提取與選擇_第3頁
第6章 特征的提取與選擇_第4頁
第6章 特征的提取與選擇_第5頁
已閱讀5頁,還剩166頁未讀 繼續免費閱讀

下載本文檔

版權說明:本文檔由用戶提供并上傳,收益歸屬內容提供方,若內容存在侵權,請進行舉報或認領

文檔簡介

第6章特征的選擇與提取

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

特征數據采集分類識別特征提取與選擇

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

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

目的:使在最小維數特征空間中異類模式點相距較遠(類間距離較大),而同類模式點相距較近(類內距離較小)。人臉識別的例子

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

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

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

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

原始特征:通過直接測量得到的特征稱為原始特征。比如人體的各種生理指標(描述其健康狀況);數字圖像中的各像素點的亮度值(描述圖像內容),都是原始特征。

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

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

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

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

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

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

選擇的特征對不同的類應該有差異。若不同類的模式的特征值差異很小,則說明所選擇的特征對于不同的類沒有什么差異,作為分類的依據時,容易使不同的類產生混淆,使誤識率增大。一般來講,特征的類間差異應該大于類內差異。特征的類別1物理的:物理特征是比較直接、人們容易感知的特征,一般在設計模式識別系統時容易被選用。如為了描述指定班級中的某個學生,可以用以下物理特征:性別、身高、胖瘦、膚色等外在特征。物理特征雖然容易感知,卻未必能非常有效地表征分類對象。2結構的:結構特征的表達能力一般要高于物理特征,如漢字識別的成功實現離不開結構特征的選擇。結構特征的表達是先將觀察對象分割成若干個基本構成要素,再確定基本要素間的相互連接關系。如指紋的識別就是基于結構信息完成的。結構信息對對象的尺寸往往不太敏感,如漢字識別時,識別系統對漢字大小不敏感,只對筆劃結構信息敏感。人臉的五官結構信息等,是目前認定人的身份的重要參數。

3數學的:易于用機器定量描述和判別,如基于統計的特征,數學特有時和觀察對象的固有特性沒有任何聯系,有時則是物理特征或結構特征的計算結果。

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

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

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

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

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

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

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

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

3)這種判據優點是計算簡單;缺點是當類間距離較小,類內距離較大時,判據仍有可能取得較大的值,而此時的可分離性并不大。特點:直觀,易于實現(用樣本計算),較常用。不能確切表明各類分布重疊情況,與錯誤率無直接聯系。當各類協差相差不大時,用此種判據較好。選擇原則:ii.計算簡單,易于實現。iii.數學上容易處理。準則函數的遞推計算問題:每增/減一個特征,只影響向量中的一個元素,矩陣的一行和一列。【用于可分性判據的類內類間距離】i.實際分類問題需要,找與分類性能關系密切者。【基于概率分布的可分性判據】考查兩類分布密度之間的交疊程度【基于概率分布的可分性判據】定義:兩個密度函數之間的距離:它必須滿足三個條件:【基于概率分布的可分性判據】具體定義有多種:Bhattacharyya距離Chernoff

界散度【基于概率分布的可分性判據】正態分布情況下:【基于概率分布的可分性判據】幾種常見的概率距離準則(J)和概率相關性準則(I)

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

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

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

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

我們想知道的是:給定某一x后,我們從觀察得到的結

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

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

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

若移動后得到更優解,則總是接受該移動,若移動后的解比當前解要差,則以一定的概率接受移動,而且這個概率隨著時間推移逐漸降低(逐漸降低才能趨向穩定)。假設在狀態xold時,系統受到某種擾動而使其狀態變為xnew。與此相對應,系統的能量也從E(xold)變成E(xnew),系統由狀態xold變為狀態xnew的接受概率p。1)隨機產生一個初始解x0,令xbest=x0,并計算目標函數值E(x0);2)設置初始溫度T(0)=To,迭代次數i=1;3)DowhileT(i)>Tmin1)forj=1~k2)對當前最優解xbest按照某一鄰域函數,產生一新的解xnew。計算新的目標函數值E(xnew),并計算目標函數值的增量Δ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)輸出當前最優點,計算結束【模擬退火算法】

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

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

編碼

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

基因型:1000101110110101000111

表現型:0.637197編碼解碼個體(染色體)基因【基本遺傳算法】初始種群:SGA采用隨機方法生成若干個個體的集合,該集合稱為初始種群。初始種群中個體的數量稱為種群規模。適應度函數

:遺傳算法對一個個體(解)的好壞用適應度函數值來評價,適應度函數值越大,解的質量越好。適應度函數是遺傳算法進化過程的驅動力,也是進行自然選擇的唯一標準,它的設計應結合求解問題本身的要求而定。【基本遺傳算法】

遺傳算法使用選擇運算來實現對群體中的個體進行優勝劣汰操作:適應度高的個體被遺傳到下一代群體中的概率大;適應度低的個體,被遺傳到下一代群體中的概率小。選擇操作的任務就是按某種方法從父代群體中選取一些個體,遺傳到下一代群體。【基本遺傳算法】選擇算子:交叉算子:所謂交叉運算,是指對兩個相互配對的染色體依據交叉概率Pc按某種方式相互交換其部分基因,從而形成兩個新的個體。交叉運算是遺傳算法區別于其他進化算法的重要特征,它在遺傳算法中起關鍵作用,是產生新個體的主要方法。SGA中交叉算子采用單點交叉算子。交叉前:00000|0111000000001000011100|00000111111000101交叉后:00000|0000011111100010111100|01110000000010000交叉點【基本遺傳算法】交叉算子示意圖

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

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

S*b=A

Sb

AT S*w=A

Sw

AT經變換后的J2變為:

J2*(A)=tr[(A

Sw

AT)-1

A

Sb

AT] =tr[(AT)-1

Sw-1Sb

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

S*b=WT

Sb

W S*w=WT

Sw

W則經變換后的J2變為:

J2(W)=tr[(WT

Sw

W)-1

WT

Sb

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

,J2

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

λ1≥

λ2

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

2

…μ

d]此時:

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

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

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

達最小的問題,這可用拉格朗日乘子法求解。有:并對uj求導數,得:

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

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

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

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

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

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

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

定義:記x1,x2,…,xP為原變量指標,z1,z2,…,zm(m≤p)為新變量指標系數lij的確定原則:①

zi與zj(i≠j;i,j=1,2,…,m)相互無關;②

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

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

從以上的分析可以看出,主成分分析的實質就是確定原來變量xj(j=1,2,…,p)在諸主成分zi(i=1,2,…,m)上的載荷lij(i=1,2,…,m;j=1,2,…,p)。因此主成分分析的關鍵就是確定這些系數。

從數學上可以證明,它們分別是的協方差(相關)矩陣的m個較大的特征值所對應的特征向量。(一)計算相關系數矩陣

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

(二)計算特征值與特征向量

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

分別求出對應于特征值的特征向量,要求=1,即,其中表示向量的第j個分量。③

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

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

計算主成分載荷

各主成分的得分

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

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

如果選取的主成分少于p個,則這些主成分的變化應盡可能多地反映原來全部p個變量的變化。主成分分析的優點

★它能找到表現原始數據陣最重要的變量的組合★

通過表示最大的方差,能有效地直觀反映樣本之間的關系★

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

四、主成分分析方法應用舉例相關矩陣為:相關陣R的特征值分別為2.077,0.919,0.004,

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

HelpprincompinMATLAB

例:使用princomp作主分量分析

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

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

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

的n個觀測值yik

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

是樣本協方差矩陣,其特征值為

,相應的正交單位化特征向量為

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

這時

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

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

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

%Example1%C

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯系上傳者。文件的所有權益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網頁內容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經權益所有人同意不得將文件中的內容挪作商業或盈利用途。
  • 5. 人人文庫網僅提供信息存儲空間,僅對用戶上傳內容的表現方式做保護處理,對用戶上傳分享的文檔內容本身不做任何修改或編輯,并不能對任何下載內容負責。
  • 6. 下載文件中如有侵權或不適當內容,請與我們聯系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論