基于模糊核匹配追尋的特征模式識別

1、計算機學報2009年8期 基于模糊核匹配追尋的特征模式識別李青 焦李成 周偉達 (南京電子技術研究所1313信箱100分箱 南京 210013) (西安電子科技大學智能信息處理研究所 西安710071)摘要：核匹配追尋算法是近年來新興的模式識別方法，在處理非線性及高維模式識別問題中表現(xiàn)出了突出的優(yōu)點。傳統(tǒng)的核匹配追尋在處理模式識別的問題中平等地對待所有樣本，最終的判決函數(shù)是針對所有樣本的一個平等綜合考慮，要求總識別誤差盡可能的小，并不能對某一類指定的樣本進行針對性地識別，然而實際應用中經(jīng)常會碰到這樣的情況：要求對某一類樣本的識別精度很高，尤其是對于非平衡樣本中或者對于具有時間屬性的樣本序列，由

2、于標準核匹配追尋學習機自身的局限性，使其不能有效地處理這些問題。本文針對這些問題，提出了模糊核匹配追尋學習機，預先根據(jù)分類的要求對每個樣本做出了不同的重要性定義，學習機根據(jù)重要性不同，對樣本進行程度不同的學習，最終得到基于問題的判決對重要樣本保持很高的分類精度；最后通過實際的仿真實驗證明了模糊匹配追尋的有效性及可行性。關鍵詞 機器學習；核匹配追尋；模糊；時間序列; 特征目標識別1、 引言核匹配追尋（Kernel Matching Pursuit，即KMP）是近年來新提出的一種模式識別方法，它首先通過核映射將訓練樣本映射成為一組基原子字典，通過貪婪算法在基函數(shù)字典中尋找一組基原子的線性組合來最小

3、化損失函數(shù)，該線性組合即為所要求解的判別函數(shù)。核匹配追尋分類器的分類性能幾乎可以達到支撐矢量機的分類性能，同時較其他經(jīng)典的核機器算法相比，具有更為稀疏的解1。然而在實際問題中，存在這樣幾種情況：1）對指定類別的識別精度有特殊性要求在識別問題中，一類樣本（或某些樣本）比另一類樣本（或其余樣本）更為重要，要求對這些重要樣本的識別精度要高（例如對癌細胞的檢測、非法入侵的檢測）；2）所獲得的樣本是具有特征時間屬性的，也就是說，在某些特定的問題中，某一時間段內(nèi)的樣本相比其他樣本具有更為重要的意義，這就需要對處于這一時間段內(nèi)的樣本給予特殊地對待，使得這些樣本對最終的判決起到更為重要的貢獻；3）非平衡樣本的

4、識別，在很多實際的問題中，兩類樣本的個數(shù)是不平衡的，尤其是當所采得的特征樣本（或弱勢樣本）相對于另一類樣本很少時，對弱勢樣本的識別就變得非常困難，由于傳統(tǒng)核匹配追尋的最終決策是針對整個樣本集做出的綜合考慮，這就使得學習機弱勢樣本識別很難。雖然核匹配追尋已經(jīng)成功地應用于許多領域，如人臉識別，手寫體識別，筆記身份鑒定，數(shù)據(jù)挖掘等3,5；然而，傳統(tǒng)的核匹配追尋在處理模式識別的問題中平等地對待所有的樣本，最終的求解是對錯分誤差和分類間隔進行折中的結果，它可以對兩類樣本做出平等綜合的考慮，要求總識別誤差盡可能的小，并不能對某一類或某一些指定的樣本進行針對性的識別，這就限制了核匹配追尋在這些有特殊要求問題

5、中的應用。本文認真分析了核匹配追尋的原理，提出了模糊核匹配追尋，根據(jù)樣本之間的重要性，對每個樣本分別設定不同的模糊因子，使得學習機訓練出針對目標樣本的決策，進一步擴展了核匹配追尋的應用范圍。最后，通過實際的實驗證明了模糊核匹配追尋的可行性及有效性。2、 核匹配追尋2.1 基本匹配追尋算法給定個觀測點，相應的觀測值為。匹配追尋的基本思想是：在一個高度冗余的字典（dictionary）空間D中將觀測值為分解為一組基函數(shù)的線性組合，其中字典D是定義在希爾伯特空間中的一組基函數(shù)2,3。假定字典包含M個基函數(shù)： （1）同時，定義損失函數(shù)（亦稱為重構誤差）： （2）其中，稱為殘差，是對個觀測點的觀測值的逼

6、近。匹配追尋算法在每一步的迭代中從字典中尋找一個基函數(shù)及其相應的系數(shù)，使得當時，當前的殘差能量最小，即 （3）由匹配追尋算法4， （4） （5）其中，表示兩個向量的點積，表示向量的二范數(shù)。由上可知，匹配追尋實際上采用了貪婪算法，每次迭代都是從字典中查找與當前殘差相關系數(shù)最大的基函數(shù)分量，隨著分解次數(shù)的增加，式（5）右端基函數(shù)向量的線性組合理論上可以任意的逼近原始觀測值，但是通常在滿足某種精度條件時就終止了，如殘差能量低于某一閾值，或者當基函數(shù)的個數(shù)大于預先設定的值。2. 2 后擬合匹配追尋算法基本匹配追尋算法在每一步的優(yōu)化迭代中，針對當前殘差尋找與之相關系數(shù)最大的基函數(shù)及其系數(shù)，這樣，觀測值在

7、第代的逼近為： （6）然而，當增加后，匹配追尋在第代對觀測值的逼近并不一定是最優(yōu)的；可以通過后擬合的方法修正，使其進一步逼近觀測值5。所謂后擬合，就是增加項后，重新調(diào)整系數(shù)，使得當前的殘差能量最小，即： （7）上式的優(yōu)化過程是一個非常耗時的計算，通常采用折中的方法：匹配追尋算法在迭代運算數(shù)步后進行一次后擬合3。2.3 核匹配追尋核匹配追尋實際上是將匹配追尋應用于機器學習問題中的一個非常簡單的思想：采用核方法生成函數(shù)字典1。給定核函數(shù)，利用觀測點處的核函數(shù)值生成函數(shù)字典：。核方法的應用受啟發(fā)于機器學習方法中的支撐矢量機；在支撐矢量機中，應用的核函數(shù)要滿足Mercer條件6,7，然而在匹配追尋中，

8、核函數(shù)不必滿足次條件，并且，可以在生成函數(shù)字典時同時采用多個核函數(shù)。通常采用的核函數(shù)有8,9：1） 多項式核 2） 徑向基核 3） Sigmoid核 2.4 損失函數(shù)的拓展基本的匹配追蹤算法采用的損失函數(shù)是能量損失函數(shù)（即平方損失函數(shù)），可以通過梯度下降法將匹配追蹤的損失函數(shù)進行拓展，使學習機能夠?qū)θ我饨o定的損失函數(shù)進行學習。假設損失函數(shù)，當觀測值為時計算預測值的殘差定義如下1： （8）那么，由匹配追蹤算法，在每一次迭代中所要尋求的最優(yōu)基函數(shù)為 （9）對應該最優(yōu)基函數(shù)的系數(shù)為： （10）此時，后擬合即是進行如下的優(yōu)化過程： （11）通常在神經(jīng)網(wǎng)絡中所采用的損失函數(shù)均可以應用于核匹配追蹤學習機中

9、，例如：1) 平方損失： （12）2) 修正雙曲正切損失： （13）由于在分類問題中，觀測值，故而，將核匹配追蹤方法應用于分類領域中可以采用間隔損失函數(shù)，假定分類器輸出為，則間隔損失損失函數(shù)為：1) 平方間隔損失： （14）2) 修正雙曲正切間隔損失： （15）其中，稱為分類間隔。最終，由核匹配追蹤學習機訓練所得到的判決超平面為： （16）其中 KMP的訓練類似于支撐矢量機（SVM），即每一個訓練樣本均對應一個系數(shù)，而決策超平面僅取決于那些對應系數(shù)不為零的樣本，為了區(qū)分于支撐矢量機中關于支撐矢量（SV）的定義，我們將核匹配追尋中對應系數(shù)不為零的樣本稱為支撐模式（Support Pattern，

10、簡寫為SP）。表示由模糊核匹配追尋算法得到的支撐模式。3、 模糊核匹配追尋（Fuzzy Kernel Matching Pursuit，即Fuzzy KMP 或FKMP）3.1 基于平方損失函數(shù)的模糊學習機核匹配追尋在模式識別領域中表現(xiàn)了顯著的優(yōu)勢，然而，由于算法本身的特點，限制了對一些特定問題的應用（如時間序列樣本識別等）。下面，我們將詳細建立模糊核匹配追尋，對傳統(tǒng)的核匹配追尋進行擴展。由（2）式，傳統(tǒng)的核匹配追尋采用平方損失，并令殘差，通過該殘差函數(shù)，任意一點的殘差均等于目標值與該點的逼近值的差值。這樣，所有樣本的殘差定義并沒有區(qū)別，從而使得標準KMP算法平等地對待所有的樣本，最終做出的判

11、決也是對所有樣本的一個平等綜合考慮，要求總識別誤差盡可能的小，并不能對某一類指定的樣本進行針對性地識別。然而在實際的問題中，樣本之間的重要性是不同的（如癌變細胞與正常細胞），問題的核心就是對這些具有重要的樣本做出盡可能準確的判別。本文提出了模糊核匹配追尋，根據(jù)每個樣本的重要性對其賦予不同的權重（稱之為模糊因子），并根據(jù)模糊因子重新定義其殘差，使得學習機對每一個樣本的學習程度不同，對應較大的要求學習機對其充分學習，盡可能地保證識別正確，而對于較小的則要求學習機僅對其進行粗略的學習。這樣，學習機最終得到的判別函數(shù)就是考慮了不同權重樣本的結果，能夠?qū)嘀馗叩臉颖咀龀霰M可能精確的識別。首先，我們給出如

12、下定義：定義（運算）：對于兩個向量，向量之間的運算定義為 （17）同時， （18）下面，我們詳細地建立基于平方損失函數(shù)的模糊核匹配追尋。給定樣本，其中為其特征，為觀測值，為其相應的權重因子（模糊因子），采用核函數(shù)，利用觀測點處的核函數(shù)值生成函數(shù)字典：。重新定義殘差 （19）其中，是第點的估計值，則其重構誤差為 （20）由匹配追尋算法， （21）則 （22）尋找相應的，使得重構誤差最小，令，可得 （23）故 （24）將代入（21），得 （25）由上，模糊核匹配追尋即是在由核函數(shù)生成的字典D中，尋找基函數(shù)，使得最小，即 （26）（27）式等價為 （27）相應的 （28）采用同標準匹配追尋相似的方法

13、，每fitN步進行一次后擬合來修正系數(shù)，使進一步逼近觀測值，即： （29）最終得到判決函數(shù) （30）其中表示由模糊核匹配追尋算法得到的支撐模式。3.2 基于任意損失函數(shù)的模糊核匹配追蹤學習機類似于核匹配追蹤學習機向非平方損失函數(shù)地拓展策略，采用梯度下降法將模糊核匹配追蹤學習機拓展到任意的非平方損失函數(shù)。給定某損失函數(shù)，結合模糊因子我們重新建立基于損失函數(shù)的自適應殘差為，即 （31）利用貪婪算法，在第N1步迭代中，最優(yōu)基原子和相應的系數(shù)為 （32） （33）當增加后，匹配追蹤在第代對觀測值的逼近并不一定是最優(yōu)的；仍然通過后擬合的方法修正，使其進一步逼近觀測值，即重新調(diào)整系數(shù)，使得當前的自適應殘差

14、能量最?。?（34）最后得到的模糊核匹配追蹤學習機的判決超平面為 （35）其中表示由模糊匹配追蹤算法得到的支撐模式。3.3 模糊參數(shù)的選取模糊核匹配追尋根據(jù)每個樣本的重要性對其賦予不同的權重（稱之為模糊因子），使得學習機對每一個樣本的學習程度不同，對應較大的要求學習機對其充分學習，而對于較小的則要求學習機僅對其進行粗略的學習，從而使得不同的樣本對最終的判決函數(shù)做出相應的貢獻。3.3.1 階躍參數(shù)在實際的應用中，經(jīng)常碰到這樣一種問題：要求對其中一類樣本的識別精度很高，甚至只考慮對指定類別樣本的識別（如對癌癥細胞的識別），這就使得指定類別樣本比其余樣本更為重要，要求對這類樣本的識別精度很高，此時模

15、糊因子選取如下： （36）這里，是折中因子，對兩類樣本的識別精度取折中（在這一類問題中，即使我們對非指定類別產(chǎn)生較大的錯分誤差，它帶來的風險仍然比較小錯識指定類別造成的風險低，所以，允許學習機對非指定類別有一個較低的識別率，而對指定類別必須具有較高的精度識別）：D越大，對指定類別的樣本學習程度越充分，識別精度越高，同時非指定類別樣本的識別精度損失也越大。3.3.2 時間參數(shù)在某些特定的工程應用（如經(jīng)濟預測、氣象預報等）中，樣本是隨著時間逐次到達的，并且由先驗信息已知某時間段或晚到的樣本具有相對重要的意義。因而，設計模糊函數(shù)是對時間的函數(shù) 在時間參數(shù)中，本文給出的時間參數(shù)是基于“晚到的樣本具有相

16、對重要的意義”這一情況，對于“特定時間段內(nèi)的重要樣本”，其模糊因子的設定可采用3.3.1節(jié)中階躍參數(shù)的形式。，可以采用如下的表達形式10 （37）這里，代表第個到達的樣本，共采集到個樣本，是衰減因子，為遺忘因子，通過圖1和圖2可以清晰地看出隨時間及衰減因子、遺忘因子的變化。圖1. 時間參數(shù)圖，（x軸為樣本序列；當時，均為0.5，隨著的增大，函數(shù)左半部分下降，右半部分上升，至時，相當于階躍函數(shù)）圖2. 時間參數(shù)圖，（x軸為樣本序列；當時，大部分先前的樣本被遺忘，隨著的減小，被遺忘的樣本數(shù)量下降）4、 仿真試驗4.1 指定樣本高精度識別產(chǎn)生兩類交錯的同心圓樣本，其中第一類樣本的半徑是均勻分布，第二

17、類樣本的半徑是均勻分布，兩類樣本各50個作為訓練樣本，采用RBF核，核匹配追尋本文中，KMP均采用了早停策略（即預設貪婪算法的最大迭代次數(shù)，用maxN表示）；fitN表示每經(jīng)過fitN步進行一次后擬合，參見文獻1。參數(shù)maxN30，fitN4對樣本進行實驗了實驗，采用折中因子選取。分別用 “+”和“”表示兩類樣本，要求對樣本“”（即中心區(qū)域樣本）的識別精度盡可能高。圖3、圖4分別給出了用標準核匹配追尋和模糊核匹配追尋識別的結果，從圖中清晰地看出，模糊核匹配追尋能夠很好地滿足我們的要求，對“”樣本達到100的識別，而標準核匹配追尋則不能。圖3：標準核匹配追尋對同心圓樣本的識別圖4：模糊核匹配追尋

18、對同心圓樣本的識別（要求對“”樣本的識別精度）4.2 時間序列樣本識別產(chǎn)生兩類交錯分布的同心圓樣本各26個；用數(shù)字記錄該樣本的位置及到達時刻，用陰影數(shù)字兩類樣本；分別用標準核匹配追尋和本文提出的模糊匹配追尋對兩類樣本進行了識別，要求能夠?qū)π路f樣本的識別率盡可能高。實驗采用時間學習因子選取，RBF核參數(shù)，核匹配追尋參數(shù)maxN30，fitN4。圖5是標準核匹配追尋給出的結果，圖6是模糊核匹配追尋給出的分類結果。由圖可知：模糊核匹配追尋對最后采得的20個樣本作出了精確的分類而傳統(tǒng)的核匹配追尋則不然。圖5：標準核匹配追尋對時間序列樣本的識別圖6：模糊核匹配追尋對時間序列樣本的識別4.3 FKMP有效

19、性測試選取UCI /mlearn/MLRepository.html數(shù)據(jù)庫中的Heart Disease數(shù)據(jù)，Heart Disease數(shù)據(jù)由13個含噪特征屬性和一個類別屬性構成，是一個2類問題，共270個樣本，選取170個樣本進行訓練（74個正類樣本），其余100個樣本中的44個正類樣本作測試。實驗中模糊核匹配追尋選取階越參數(shù)，圖7給出了不同折中因子D取值下對正類樣本和負類樣本的測試誤差。其中，核匹配追尋參數(shù)選?。簃axN=80，fitN8，RBF核參數(shù)，模糊因子在0.01,0.5上等間采樣50次。由圖可知：隨著D的增大，目標樣本的識別誤差隨之下降。

20、圖7：階越學習因子D對目標樣本識別影響4.4 對實際數(shù)據(jù)的測試選取UCI數(shù)據(jù)庫中的Breast Cancer、Diabetis、Heart Disease及Thyroid數(shù)據(jù)對本文提出的模糊核匹配追尋算法進行測試。其中，Breast Cancer數(shù)據(jù)由9個含噪特征屬性和一個類別屬性構成，是一個2類問題，共277個樣本，選取200個作為檢驗樣本，其余77個樣本中的23個正類樣本作測試；Pima Indians Diabetes數(shù)據(jù)由8個含噪特征屬性和一個類別屬性構成，是一個2類問題，共768個樣本，選取256個樣本進行訓練，其余512個樣本中的174個正類樣本作測試； Thyroid數(shù)據(jù)由5個含

21、噪特征屬性和一個類別屬性構成，是一個2類問題，共215個樣本，選取140個樣本進行訓練，其余75個樣本中的26個正類樣本作測試。在本實驗中，我們更為關注對于正類樣本的分類性能，這是因為正類樣本均刻畫了檢測呈陽性的病理狀態(tài)，學習機的任務就是要對這一類樣本盡可能的精確識別。實驗參數(shù)：采用RBF核，對于Breast Cancer數(shù)據(jù)maxN=60，fitN5，模糊因子；對于Pima Indians數(shù)據(jù)maxN=100，fitN8，模糊因子，對于Thyroid數(shù)據(jù)maxN=50，fitN3，模糊因子，分別用標準KMP和FKMP對病理類別特征樣本進行識別測試。我們是在matlab環(huán)境下，P43.2GHz

22、、2G內(nèi)存的微機上獨立進行30次實驗取平均的結果，表1給出了具體的實驗結果。由于采用的樣本為非平衡樣本（即兩類樣本個數(shù)相差較大），傳統(tǒng)的核匹配追尋不能對弱勢樣本（數(shù)量小的一類樣本）進行有效的識別，甚至失去了識別能力（識別率50），而采用模糊核匹配追尋，就可以有效地解決這一問題，仿真的試驗結果中，當標準KMP對弱勢樣本的識別率50（34.78）時，利用模糊KMP，仍然可以使識別精度可以達到99以上。表1：對UCI非平衡數(shù)據(jù)的測試數(shù) 據(jù)訓練樣本檢驗樣本損失函數(shù)算法支撐模式識別率Breast Cancer類：58類：142類：23Loss-mse Loss-mse表示核匹配追尋采用平方損失函數(shù)。Fu

23、zzy KMP499.92KMP5534.78Loss-tanh Loss-tanh表示核匹配追尋采用修正雙曲正切損失函數(shù)。Fuzzy KMP699.87%KMP6433.56%Pima Indians Diabetes類：94類：162類：174Loss-mseFuzzy KMP8799.14KMP10056.32Loss-tanhFuzzy KMP6999.25%KMP10257.22%Thyroid類：39類：101類：26Loss-mseFuzzy KMP50100KMP5084.62Loss-tanhFuzzy KMP48100%KMP5083.69%5、 總結核匹配追尋具有很強的推

24、廣能力，強大的非線性處理能力和高維處理能力，同時較其他核機器相比，其稀疏性更優(yōu)。然而在實際問題中經(jīng)常遇到這樣幾種情況：1）所獲得的樣本是具有時間屬性的；2）要求其中一類樣本的識別精度；3）非平衡樣本的識別。由于傳統(tǒng)的核匹配追尋在處理模式識別的問題平等對待所有的樣本，它要求總識別誤差盡可能的小，但是并不能對某一類或某一些指定的樣本進行針對性的識別，這就限制了核匹配追尋在這些實際問題中的應用。針對這些問題，本文提出了模糊核匹配追尋，根據(jù)問題的要求對每個樣本作出重要性定義，學習機可以根據(jù)樣本的重要性定義進行程度不同的學習，對次要的樣本粗略學習，而對重要的樣本進行充分學習，使學習機的最終判決對指定的重

25、要樣本達到較高的識別精度。本文進行了大量的仿真實驗，結合分類圖例證實了模糊核匹配追尋可行性及有效性；在對UCI數(shù)據(jù)的性能測試中可以得出：當傳統(tǒng)的核匹配追尋已不能對弱勢樣本進行識別（識別率小于50）時，模糊核匹配追尋仍然對弱勢樣本保持了較高的識別精度。參考文獻1 Pascal Vincent, Yoshua Bengio. Kernel matching pursuit. Machine Learning, 48:165-187, 2002.2 Mallat S., Z. Zhang (1993, Dec.). Matching pursuit with time-frequency dicti

26、onaries. IEEE Trans. Signal Proc. 41 (12), 3397-3415.3 Davis G., Mallat S., Z. Zhang. Adaptive time-frequency decompositions. Optical Engineering 33(7), 2183-2191.4 S. Mallat. A theory for nuliresolution signal decomposition: The wavelet representation. IEEE Trans. Pattern Anal. Machine Intell., vol

27、. 11, pp. 674-693, July 1989.5 Pati Y., Rezaiifar R. and Krishnaprasad P. Orthogonal Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition. In Proceedings of the 27th Annual Asilomar Conference on Signals, Systems, and Computers, pp. 40-44, 1993.6 Vapnik, V.N.

28、 An overview of statistical learning theory, IEEE Trans. Neural Networks, vol. 10, no.5, pp.988-999, 1999.7 C. J. C. Burges. A tutorial on support vector machines for pattern recognition. Data Mining and Knowledge Discovery, 1998, 2(2): 1-47.8 Schlkopf, B., Smola, A. Learning with kernels. MIT Press

29、, 1999.9 Burges, C. J. Geometry and invariance in kernel based method. In advance in kernel method-Support vector learning. Cambridge, MA: MIT Press, 1999, pp. 86-116.10 Cao, L. J. and Francis, E. H. Support vector machine with adaptive parameters in financial time series forecasting. IEEE Trans. Ne

30、ural Networks, vol. 14, no. 6, pp. 1506-1518, 2003.Pattern Recognition Based on the Fuzzy Kernel Matching PursuitLI Qing, JIAO Li-cheng, Zhou Weida( Institute of Intelligent Information Processing, Xidian University, Xian 710071 ) Abstract Kernel Matching Pursuit (KMP), a novel method of the pattern

31、 recognition, presents excellent performance in solving the problems with small sample, nonlinear and local minima. KMP has been proposed to provide a good generalization performance for both classes, yet the classification precision of some important data cant be classified precisely. This is mainl

32、y because the decision function found by KMP is the synthetic consideration results of all the data, which has greatly limited its use in many practical problems, such as time series identification and unbalanced data classification. In this paper, an fuzzy kernel matching pursuit machine is (FKMP)

33、proposed, which can classify the appointed important samples much more precisely according to the predefined importance of the data. Lots of experiments have been done in the paper to prove the feasibility and validation of the fuzzy kernel matching pursuit machine.Keywords Machine Learning, Kernel

34、Matching Pursuit, Fuzzy Kernel Matching Pursuit; Time Series Identification; Unbalanced Data Classificationl BackgroundWe have made researches on many fields of the support vector machine, such as Linear programming support vector machine, kernel matching pursuit classifier ensemble, support vector regression based on unconstrained convex quadratic programming and so on, and have appli