模式識別特征選擇和提取

模式識別特征選擇和提取第一頁，共四十七頁，編輯于2023年，星期日特征選擇和提取特征選擇和提取是模式識別中的一個關鍵問題前面討論分類器設計的時候，一直假定已給出了特征向量維數(shù)確定的樣本集，其中各樣本的每一維都是該樣本的一個特征；這些特征的選擇是很重要的，它強烈地影響到分類器的設計及其性能；假若對不同的類別，這些特征的差別很大，則比較容易設計出具有較好性能的分類器。第二頁，共四十七頁，編輯于2023年，星期日特征選擇和提取特征選擇和提取是構造模式識別系統(tǒng)時的一個重要課題在很多實際問題中，往往不容易找到那些最重要的特征，或受客觀條件的限制，不能對它們進行有效的測量；因此在測量時，由于人們心理上的作用，只要條件許可總希望把特征取得多一些；另外，由于客觀上的需要，為了突出某些有用信息，抑制無用信息，有意加上一些比值、指數(shù)或對數(shù)等組合計算特征；如果將數(shù)目很多的測量值不做分析，全部直接用作分類特征，不但耗時，而且會影響到分類的效果，產(chǎn)生“特征維數(shù)災難”問題。第三頁，共四十七頁，編輯于2023年，星期日特征選擇和提取為了設計出效果好的分類器，通常需要對原始的測量值集合進行分析，經(jīng)過選擇或變換處理，組成有效的識別特征；在保證一定分類精度的前提下，減少特征維數(shù)，即進行“降維”處理，使分類器實現(xiàn)快速、準確和高效的分類。為達到上述目的，關鍵是所提供的識別特征應具有很好的可分性，使分類器容易判別。為此，需對特征進行選擇。應去掉模棱兩可、不易判別的特征；所提供的特征不要重復，即去掉那些相關性強且沒有增加更多分類信息的特征。第四頁，共四十七頁，編輯于2023年，星期日特征選擇和提取說明實際上，特征選擇和提取這一任務應在設計分類器之前進行；從通常的模式識別教學經(jīng)驗看，在討論分類器設計之后講述特征選擇和提取，更有利于加深對該問題的理解。第五頁，共四十七頁，編輯于2023年，星期日特征選擇和提取所謂特征選擇，就是從n個度量值集合{x1,x2,…,xn}中，按某一準則選取出供分類用的子集，作為降維（m維，m<n）的分類特征；所謂特征提取，就是使(x1,x2,…,xn)通過某種變換，產(chǎn)生m個特征(y1,y2,…,ym)(m<n)，作為新的分類特征（或稱為二次特征）；其目的都是為了在盡可能保留識別信息的前提下，降低特征空間的維數(shù)，已達到有效的分類。第六頁，共四十七頁，編輯于2023年，星期日特征選擇和提取以細胞自動識別為例通過圖像輸入得到一批包括正常細胞和異常細胞的圖像，我們的任務是根據(jù)這些圖像區(qū)分哪些細胞是正常的，哪些細胞是異常的；首先找出一組能代表細胞性質的特征，為此可計算細胞總面積總光密度胞核面積核漿比細胞形狀核內(nèi)紋理……第七頁，共四十七頁，編輯于2023年，星期日特征選擇和提取以細胞自動識別為例這樣產(chǎn)生出來的原始特征可能很多（幾十甚至幾百個），或者說原始特征空間維數(shù)很高，需要降低（或稱壓縮）維數(shù)以便分類；一種方式是從原始特征中挑選出一些最有代表性的特征，稱之為特征選擇；另一種方式是用映射（或稱變換）的方法把原始特征變換為較少的特征，稱之為特征提取。第八頁，共四十七頁，編輯于2023年，星期日7.1模式類別可分性的測度距離和散布矩陣[點到點之間的距離][點到點集之間的距離][類內(nèi)距離]第九頁，共四十七頁，編輯于2023年，星期日7.1模式類別可分性的測度距離和散布矩陣[類內(nèi)散布矩陣]對屬于同一類的模式樣本，類內(nèi)散布矩陣表示各樣本點圍繞其均值周圍的散布情況，這里即為該分布的協(xié)方差矩陣。[類間距離和類間散布矩陣][多類模式集散布矩陣]以上各類散布矩陣反映了各類模式在模式空間的分布情況，但它們與分類的錯誤率沒有直接聯(lián)系。（若與分類錯誤率聯(lián)系起來，可采用散度作為類別可分性的度量，在此不詳細介紹）第十頁，共四十七頁，編輯于2023年，星期日類別可分離性判據(jù)：衡量不同特征及其組合對分類是否有效的定量準則理想準則：某組特征使分類器錯誤概率最小實際的類別可分離性判據(jù)應滿足的條件：度量特性：與錯誤率有單調(diào)關系當特征獨立時有可加性：單調(diào)性：常見類別可分離性判據(jù)：基于距離、概率分布、熵函數(shù)第十一頁，共四十七頁，編輯于2023年，星期日類間可分性:=所有樣本間的平均距離：(8-1)squaredEuclidian(8-5)類內(nèi)平均距離類間

距離(8-6)第十二頁，共四十七頁，編輯于2023年，星期日基于距離的準則概念直觀，計算方便，但與錯誤率沒有直接聯(lián)系樣本類間

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

離散度矩陣類間可分離性判據(jù)第十三頁，共四十七頁，編輯于2023年，星期日7.2特征選擇設有n個可用作分類的測量值，為了在不降低（或盡量不降低）分類精度的前提下，減小特征空間的維數(shù)以減少計算量，需從中直接選出m個作為分類的特征。問題：在n個測量值中選出哪一些作為分類特征，使其具有最小的分類錯誤？第十四頁，共四十七頁，編輯于2023年，星期日特征選擇:=從原始特征中挑選出一些最有代表性、分類性能最好的特征進行分類。從D個特征中選取d個,共CdD種組合。若不限定特征選擇個數(shù)，則共2D種組合

－典型的組合優(yōu)化問題特征選擇的方法大體可分兩大類：Filter方法：根據(jù)獨立于分類器的指標J來評價所選擇的特征子集S，然后在所有可能的特征子集中搜索出使得J最大的特征子集作為最優(yōu)特征子集。不考慮所使用的學習算法。Wrapper方法：將特征選擇和分類器結合在一起，在學習過程中表現(xiàn)優(yōu)異的的特征子集會被選中。第十五頁，共四十七頁，編輯于2023年，星期日經(jīng)典特征選擇算法許多特征選擇算法力求解決搜索問題，經(jīng)典算法有：分支定界法:最優(yōu)搜索，效率比盲目窮舉法高。單獨最優(yōu)特征組合法：次優(yōu)搜索。順序后退法順序前進法模擬退火法Tabu搜索法遺傳算法特征

選擇第十六頁，共四十七頁，編輯于2023年，星期日單獨最優(yōu)特征組合計算各特征單獨使用時的可分性判據(jù)J并加以排隊，取前d個作為選擇結果不一定是最優(yōu)結果當可分性判據(jù)對各特征具有(廣義)可加性，該方法可以選出一組最優(yōu)的特征來，例：各類具有正態(tài)分布各特征統(tǒng)計獨立可分性判據(jù)基于Mahalanobis距離特征

選擇第十七頁，共四十七頁，編輯于2023年，星期日順序前進法自下而上搜索方法。每次從未入選的特征中選擇一個特征，使得它與已入選的特征組合在一起時所得的J值為最大，直至特征數(shù)增加到d為止。該方法考慮了所選特征與已入選特征之間的相關性。特征

選擇第十八頁，共四十七頁，編輯于2023年，星期日順序后退法該方法根據(jù)特征子集的分類表現(xiàn)來選擇特征搜索特征子集：從全體特征開始，每次剔除一個特征，使得所保留的特征集合有最大的分類識別率依次迭代，直至識別率開始下降為止特征

選擇第十九頁，共四十七頁，編輯于2023年，星期日遺傳算法從生物進化論得到啟迪。遺傳，變異，自然選擇?；蜴湸a：待解問題的解的編碼，每個基因鏈碼也稱為一個個體。對于特征選擇，可用一個D位的0/1構成的串表示一種特征組合。群體：若干個個體的集合，即問題的一些解的集合。交叉：由當前兩個個體的鏈碼交叉產(chǎn)生新一代的個體。變異：由一個鏈碼隨機某基因使其翻轉。特征

選擇第二十頁，共四十七頁，編輯于2023年，星期日遺傳算法適應度：每個個體xi的函數(shù)值fi，個體xi越好，fi越大。新一代群體對環(huán)境的平均適應度比父代高。遺傳算法的基本框架：Step1:令進化代數(shù)t=0。Step2:給出初始化群體P(t)，令xg為任一個體。Step3:對P(t)中每個個體估值，并將群體中最優(yōu)解x’與xg比較，如果x’的性能優(yōu)于xg，則xg=x’Step4:如果終止條件滿足，則算法結束，xg為算法的結果。否則繼續(xù)。Step5:從P(t)中選擇個體并進行交叉和變異操作，得到新一代群體P(t+1)。令t=t+1,轉到Step3。特征

選擇第二十一頁，共四十七頁，編輯于2023年，星期日6.5

討論特征的選擇與提取是模式識別中重要而困難的一步模式識別的第一步：分析各種特征的有效性并選出最有代表性的特征降低特征維數(shù)在很多情況下是有效設計分類器的重要課題三大類特征：物理、結構和數(shù)學特征物理和結構特征：易于為人的直覺感知，但難于定量描述，因而不易用機器判別數(shù)學特征：易于用機器定量描述和判別第二十二頁，共四十七頁，編輯于2023年，星期日7.2特征選擇從n個測量值中選出m個特征，一共有中可能的選法。一種“窮舉”辦法：對每種選法都用訓練樣本試分類一下，測出其正確分類率，然后做出性能最好的選擇，此時需要試探的特征子集的種類達到種，非常耗時。需尋找一種簡便的可分性準則，間接判斷每一種子集的優(yōu)劣。對于獨立特征的選擇準則一般特征的散布矩陣準則第二十三頁，共四十七頁，編輯于2023年，星期日7.2特征選擇對于獨立特征的選擇準則類別可分性準則應具有這樣的特點，即不同類別模式特征的均值向量之間的距離應最大，而屬于同一類的模式特征，其方差之和應最小。假設各原始特征測量值是統(tǒng)計獨立的，此時，只需對訓練樣本的n個測量值獨立地進行分析，從中選出m個最好的作為分類特征即可。[例：對于i和j兩類訓練樣本的特征選擇]第二十四頁，共四十七頁，編輯于2023年，星期日7.2特征選擇討論：上述基于距離測度的可分性準則，其適用范圍與模式特征的概率分布有關。三種不同模式分布的情況(a)中特征xk的分布有很好的可分性，通過它足以分離i和j兩種類別；(b)中的特征分布有很大的重疊，單靠xk達不到較好的分類，需要增加其它特征；(c)中的i類特征xk的分布有兩個最大值，雖然它與j的分布沒有重疊，但計算Gk約等于0，此時再利用Gk作為可分性準則已不合適。因此，假若類概率密度函數(shù)不是或不近似正態(tài)分布，均值和方差就不足以用來估計類別的可分性，此時該準則函數(shù)不完全適用。第二十五頁，共四十七頁，編輯于2023年，星期日7.2特征選擇一般特征的散布矩陣準則[類內(nèi)、類間和總體的散布矩陣Sw、Sb和St]Sw的行列式值越小且Sb的行列式值越大，可分性越好。[散布矩陣準則J1和J2形式]使J1或J2最大的子集可作為所選擇的分類特征。注：這里計算的散布矩陣不受模式分布形式的限制，但需要有足夠數(shù)量的模式樣本才能獲得有效的結果。第二十六頁，共四十七頁，編輯于2023年，星期日作業(yè)設有如下三類模式樣本集ω1，ω2和ω3，其先驗概率相等，求Sw和Sb

ω1：{(10)T,(20)T,(11)T} ω2：{(-10)T,(01)T,(-11)T} ω3：{(-1-1)T,(0-1)T,(0-2)T}第二十七頁，共四十七頁，編輯于2023年，星期日7.3離散K-L變換全稱：Karhunen-Loeve變換（卡洛南-洛伊變換）前面討論的特征選擇是在一定準則下，從n個特征中選出k個來反映原有模式。這種簡單刪掉某n-k個特征的做法并不十分理想，因為一般來說，原來的n個數(shù)據(jù)各自在不同程度上反映了識別對象的某些特征，簡單地刪去某些特征可能會丟失較多的有用信息。如果將原來的特征做正交變換，獲得的每個數(shù)據(jù)都是原來n個數(shù)據(jù)的線性組合，然后從新的數(shù)據(jù)中選出少數(shù)幾個，使其盡可能多地反映各類模式之間的差異，而這些特征間又盡可能相互獨立，則比單純的選擇方法更靈活、更有效。K-L變換就是一種適用于任意概率密度函數(shù)的正交變換。第二十八頁，共四十七頁，編輯于2023年，星期日6.3特征提取與K-L變換特征提?。河糜成洌ɑ蜃儞Q）的方法把原始特征變換為較少的新特征PCA(PrincipleComponentAnalysis)方法：

進行特征降維變換，不能完全地表示原有的對象，能量總會有損失。希望找到一種能量最為集中的的變換方法使損失最小。K-L(Karhunen-Loeve)變換：最優(yōu)正交線性變換，相應的特征提取方法被稱為PCA方法第二十九頁，共四十七頁，編輯于2023年，星期日K-L變換離散K-L變換：對向量x用確定的完備正交歸一向量系uj展開特征

提取第三十頁，共四十七頁，編輯于2023年，星期日離散K-L變換的均方誤差用有限項估計x：該估計的均方誤差：特征

提取第三十一頁，共四十七頁，編輯于2023年，星期日求解最小均方誤差正交基用Lagrange乘子法：結論：以相關矩陣R的d個本征向量為基向量來展開x時，其均方誤差為：K-L變換：當取矩陣R的d個最大本征值對應的本征向量來展開x時，其截斷均方誤差最小。這d個本征向量組成的正交坐標系稱作x所在的D維空間的d維K-L變換坐標系，x在K-L坐標系上的展開系數(shù)向量y稱作x的K-L變換特征

提取第三十二頁，共四十七頁，編輯于2023年，星期日求解最小均方誤差正交基用Lagrange乘子法：結論：以相關矩陣R的d個本征向量為基向量來展開x時，其均方誤差為：K-L變換：當取矩陣R的d個最大本征值對應的本征向量來展開x時，其截斷均方誤差最小。這d個本征向量組成的正交坐標系稱作x所在的D維空間的d維K-L變換坐標系，x在K-L坐標系上的展開系數(shù)向量y稱作x的K-L變換特征

提取第三十三頁，共四十七頁，編輯于2023年，星期日K-L變換的表示K-L變換的向量展開表示：K-L變換的矩陣表示：特征

提取第三十四頁，共四十七頁，編輯于2023年，星期日K-L變換的性質y的相關矩陣是對角矩陣：特征

提取第三十五頁，共四十七頁，編輯于2023年，星期日K-L變換的性質K-L坐標系把矩陣R對角化，即通過K-L變換消除原有向量x的各分量間的相關性，從而有可能去掉那些帶有較少信息的分量以達到降低特征維數(shù)的目的特征

提取第三十六頁，共四十七頁，編輯于2023年，星期日K-L變換的數(shù)據(jù)壓縮圖解取2x1變換矩陣U=[u1]，則x的K-L變換y為：

y=UTx=u1Tx=y1變換的能量損失為特征

提取第三十七頁，共四十七頁，編輯于2023年，星期日K-L變換的產(chǎn)生矩陣數(shù)據(jù)集KN={xi}的K-L變換的產(chǎn)生矩陣由數(shù)據(jù)的二階統(tǒng)計量決定，即K-L坐標系的基向量為某種基于數(shù)據(jù)x的二階統(tǒng)計量的產(chǎn)生矩陣的本征向量K-L變換的產(chǎn)生矩陣可以有多種選擇：x的相關函數(shù)矩陣R=E[xxT]x的協(xié)方差矩陣C=E[(x-μ)(x-μ)T]樣本總類內(nèi)離散度矩陣：特征

提取第三十八頁，共四十七頁，編輯于2023年，星期日未知類別樣本的K-L變換用總體樣本的協(xié)方差矩陣C=E[(x-μ)(x-μ)T]

進行K-L變換，K-L坐標系U=[u1,u2,...,ud]按照C的本征值的下降次序選擇例：設一樣本集的協(xié)方差矩陣是：

求最優(yōu)2x1特征提取器U

解答：計算特征值及特征向量[V,D]=eig(C);

特征值D=[24.736,2.263]T,特征向量:

由于λ1>λ2，故最優(yōu)2x1特征提取器

此時的K-L變換式為：特征

提取第三十九頁，共四十七頁，編輯于2023年，星期日7.3離散K-L變換5.3.1[離散的有限K-L展開][展開式的形式]如果對c種模式類別{i}i=1,…,c做離散正交展開，則對每一模式可分別寫成：xi=

ai，其中矩陣取決于所選用的正交函數(shù)。對各個模式類別，正交函數(shù)都是相同的，但其展開系數(shù)向量ai則因類別的不同模式分布而異。[K-L展開式的性質]K-L展開式的根本性質是將隨機向量x展開為另一組正交向量j的線性和，且其展開式系數(shù)aj（即系數(shù)向量a的各個分量）具有不同的性質。[在此條件下，正交向量集{j}的確定][K-L展開式系數(shù)的計算步驟]第四十頁，共四十七頁，編輯于2023年，星期日7.3離散K-L變換5.3.2[按K-L展開式選擇特征]K-L展開式用于特征選擇相當于一種線性變換。若從K個特征向量中取出m個組成變換矩陣，即 =(12…m)，m<K

此時，是一個n*m維矩陣，x是n維向量，經(jīng)過Tx變換，即得到降維為m的新向量。[選取變換矩陣，使得降維后的新向量在最小均方差條件下接近原來的向量x]第四十一頁，共四十七頁，編輯于2023年，星期日7.3離散K-L變換5.3.2[按K-L展開式選擇特征]結論從K-L展開式的性質和按最小均方差的準則來選擇特征，應使E[aj]=0。由于E[a]=E[Tx]=TE[x]，故應使E[x]=0。基于這一條件，在將整體模式進行K-L變換之前，應先將其均值作為新坐標軸的原點，采用協(xié)方差矩陣C或自相關矩陣R來計算特征值。如果E[x]<>0，則只能得到“次最佳”的結果。第四十二頁，共四十七頁，編輯于2023年，星期日7.3離散K-L變換5.3.2[按K-L展開式選擇特征]結論將K-L展開式系數(shù)aj（亦即變換后的特征）用yj表示，寫成向量