用糾錯編碼改進Mry支持向量機多類分類算法

1、用糾錯編碼改進的 M-ry 支持向量機多類分類算法摘要：針對m-ary支持向量機(svm)多類分類算法結(jié)構(gòu)簡單，但泛 化能力較弱的特點 , 提出了與糾錯編碼理論相結(jié)合的改進的 m-ary svm算法。首先，將原始類別信息編碼作為信息碼；然后結(jié)合糾錯編 碼理論及期望的糾錯能力 , 產(chǎn)生一定程度上性能最佳的編碼 , 作為 分類器訓(xùn)練的依據(jù) ； 最后, 對于識別階段輸出編碼中的錯誤分類利 用檢錯糾錯原理進行校正。實驗結(jié)果表明 , 改進的算法通過引入盡 可能少的冗余子分類器增強了標(biāo)準(zhǔn) m-ary svm 多類分類算法的性 能。關(guān)鍵詞:m-ary;支持向量機;糾錯編碼；多類分類;最小碼間距離；輸 出校正

2、碼enhanced m-ary support vector machine byerror correction coding for multi-category classification 英文作者名 bao jian, liu ran* 英文地址 (school of computer science, hangzhou dianzi university, hangzhou zhejiang 310018, china) abstract: m-ary support vector machine (m-ary svm) for multi-category classificat

3、ion has the advantage of simple structure, but the disadvantage of weak generalization ability. this paper presented an enhanced m-ary svm algorithm in combination with error correction coding theory. the main idea of the approach was to generate a group of best codesbased on information codes deriv

4、ed from the original category flags information, then utilize such codes as the basis for training the classifier, while in the final feed-forward phase the output codes composedof each sub-classifier could be corrected by error detection and correction principle if there exists any identifying erro

5、r. the experimental results confirm the effectiveness of the improved algorithm brought about by introducing as few sub-classifiers as possible. key words: m-ary; support vector machine (svm); error correction coding; multi-category classification; minimum code distance; output correction code0 引言 作

6、為機器學(xué)習(xí)實現(xiàn)方法之一的統(tǒng)計學(xué)習(xí)理論 (statistical learning theory, slt), 以及基于此理論的支持向量機 1-2(support vector machine, svm) 憑借其顯著的性能優(yōu)勢 , 近 年來得到廣大研究人員的關(guān)注 ,并已取得了大量的研究成果 , 而此 前作為研究熱點的人工神經(jīng)網(wǎng)絡(luò) (artificial neural networks, ann)雖然在工程實踐中得到廣泛的應(yīng)用，但由于其建立在大數(shù)定理 的漸近理論之上 , 要求學(xué)習(xí)樣本足夠多 , 且容易陷入局部極值或過 學(xué)習(xí)的困境,并且在實際應(yīng)用中隱含層的層數(shù)及每層神經(jīng)元數(shù)目如 何確定仍無規(guī)律可循

7、, 只能憑借使用者的經(jīng)驗進行實驗試湊。正是 由于神經(jīng)網(wǎng)絡(luò)自身存在的這些不足 , 導(dǎo)致了支持向量機算法研究的興起標(biāo)準(zhǔn)支持向量機是針對兩類分類問題提出的 , 根據(jù)有限樣本信息在 模型復(fù)雜性和學(xué)習(xí)能力之間尋求最佳折中 , 即通過最大化分類間隔 得到最大的泛化能力 , 但是現(xiàn)實中的大多數(shù)模式識別問題都是多類 分類問題,對此,通常的解決方法主要有 4種: 一類對一類 (one-against-one, oao) 、一類對其余 (one-against-rest, oar) 、 有向無環(huán)圖 svm3(decision directed acyclic graph svm,ddagsvm)和m-ary sv

8、m4。此外，一些學(xué)者研究了其他一些針 對特定多類分類問題的解決方法 , 如針對多類分類情況下可能會出 現(xiàn)不可分區(qū)域及訓(xùn)練樣本中存在噪聲的情況，李廣麗等5在svm的 輸入端通過引入模糊隸屬度函數(shù)對輸入數(shù)據(jù)進行轉(zhuǎn)換并對利用改 進的序列最小優(yōu)化算法求解模糊多類分類支持向量機 , 從而獲得較 好的性能；于清等提出了一種被稱作2_a_2的多類分類方法，將 最少數(shù)量的子分類器結(jié)合在一起并分利用每個子分類器的識別結(jié) 果來實現(xiàn)多類分類，但是 , 這些算法通常存在著針對性強、泛化能 力弱、訓(xùn)練速度慢等不足。文獻 7 對 oao、oar 和 dagsvm 3 種多 分類svm模型結(jié)構(gòu)和性能進行了分析比較，并且指出

9、第一種和第三 種方法更加實用；文獻8對5種多類分類svm方法(oao、oar、二 叉樹法、糾錯輸出編碼 (error correction output code, ecoc)法和ddagsvm)的原理和實現(xiàn)方法進行了介紹和分析，從速度和精度兩 方面對這些方法的優(yōu)缺點進行了歸納和總結(jié)，研究如何用精簡的結(jié) 構(gòu)模型充分發(fā)揮支持向量機算法的優(yōu)勢對于工程實踐應(yīng)用有著深刻的意義。嵌入式系統(tǒng)近年來得到廣泛的普及 , 但是由于其小存儲容量、低功 耗以及軟硬件精簡等限制 , 如何將高效的算法應(yīng)用于嵌入式系統(tǒng)也 成為研究的一大熱點 , 支持向量機作為最新且較有潛力的機器學(xué)習(xí) 算法, 在嵌入式系統(tǒng)中的理論研究和應(yīng)

10、用也已有了一定的發(fā) 展,anguita等9-10將普通支持向量機算法中的參數(shù)表示利用分 枝定界法轉(zhuǎn)化為整型 , 從而使得在資源有限的嵌入式系統(tǒng)中能夠?qū)?現(xiàn)svm算法,并對經(jīng)典算法實現(xiàn)時又引入了區(qū)間算術(shù)法，簡化了搜索 空間的上下界，并且提出了硬件友好型svm的實現(xiàn)方法。國內(nèi)也有 不少這方面探索研究，文獻11對bp神經(jīng)網(wǎng)絡(luò)和支持向量機的優(yōu)化 過程進行了詳細的研究 ,并給出了兩種算法在嵌入式系統(tǒng)中實現(xiàn)的 改進措施,并采用基于迭代的選擇策略 12 逐步減小問題規(guī)模以利 于在嵌入式系統(tǒng)下訓(xùn)練svm；文獻13-15針對不同的平臺將支持向 量機應(yīng)用于解決具體的模式識別問題，這些研究和實現(xiàn)對支持向量 機在嵌入

11、式系統(tǒng)中的應(yīng)用有著指導(dǎo)意義。本文以 m-ary 支持向量機算法為基礎(chǔ) , 結(jié)合檢錯糾錯理論提出了改 進的具有糾錯能力的 m-ary 支持向量機算法 , 分析了其原理和實現(xiàn) 方法,并以pc和嵌入式系統(tǒng)為平臺，以手寫數(shù)字識別程序來驗證其 性能。第3期 包健等: 用糾錯編碼改進的 m-ary 支持向量機多類分類算法計算機應(yīng)用 第 32 卷 1m-ary svm 模型1.1 標(biāo)準(zhǔn) m-ary svm 算法m-ary 支持向量機是在 2000 年由 sebald 和 buchlew 等提出的 , 由 于精簡的結(jié)構(gòu)模型和較少的子分類器數(shù)量 , 使得問題求解規(guī)模得到 較大的簡化。標(biāo)準(zhǔn) m-ary 支持向量機

12、的結(jié)構(gòu)如圖 1 所示。 與其他多類分類方法相比 , 此算法大大減少了子分類器數(shù)量 ,因此 簡化了求解模型 , 但是其最大的缺陷就是容錯性較差 , 若在計算過 程中,某個子分類器的判別失誤造成符號取反 , 則會導(dǎo)致整個判別 結(jié)果錯誤 , 因此其泛化能力受到了較大影響 ,這也是影響其實際應(yīng) 用的主要因素 ,關(guān)于該算法的應(yīng)用研究及改進方案 , 也在逐漸被研 究人員所關(guān)注 16-18 。1.2m-ary svm 的性能研究和應(yīng)用較多的 oao 和 oar 多類分類支持向量機算法 , 主要缺點 是需要構(gòu)造較多的子支持向量機 ,不僅浪費了較多的系統(tǒng)資源 , 而 且增加了訓(xùn)練時間 , 因此對于軟硬件條件要求

13、苛刻的嵌入式系統(tǒng)并 不適用 , 而對于性能相對優(yōu)越的 m-ary svm 的性能分析的文獻不多 , 從直觀上來分析，假設(shè)訓(xùn)練集t中共有p個不同的類別和n個訓(xùn)練 樣本, 按照上述多分類支持向量機的構(gòu)造方法 , 各算法應(yīng)有的子 svm 數(shù)目(nclass)、需訓(xùn)練的參數(shù)數(shù)量(nparam)以及訓(xùn)練時間(ntime) 如表1所示,其中m為子分類器數(shù)量,r是與訓(xùn)練算法有關(guān)的系數(shù)， 如采用smo算法時,r 2。表格(有表名)表14種多類分類器性能比較-p (p-1)/svmnclassnparamntimeoaop(p-1)/2(p-1)no(2n/p)r2) oarp-1p no(p nr)ddagp

14、(p-1)/2(p-1)no(2r-1 p2-r nr)m-arylb pn lb po(m n2)從表 1 可看出： m-ary svm 僅需要構(gòu)造對數(shù)級數(shù)量的子分類器 , 不 僅使求解規(guī)模得到簡化 ,同時大大降低了問題的復(fù)雜性 , 且訓(xùn)練速 度得到較大的提高，使得其成為最快的svm算法,從理論上講，只要 對其子分類器的參數(shù)選擇得當(dāng) , 其整體性能會有較大的改進。2 改進的 m-ary 算法2.1 改進算法的提出一些學(xué)者提出的糾錯輸出編碼 (error correcting output code, ecoc) 支持向量機 19-20, 將常規(guī)的支持向量機算法與糾錯編碼相 結(jié)合, 通過糾錯編

15、碼來對子分類器的輸出進行糾錯 , 從而增強了模 型的泛化性 , 通常的 ecoc svm 是利用某種糾錯碼構(gòu)造方法 ( 如文獻 19 中提到的詳盡編碼法、列選擇法、爬山法等 )得到合適的碼字 , 然后將不同的碼字分配給不同的類別作為訓(xùn)練的依據(jù) , 每個子分類 器分別對應(yīng)碼字的不同位 , 也就是碼字的位數(shù)對應(yīng)于分類器中子分 類器的數(shù)量,這種方法不僅充分利用了支持向量機的兩類特性 ,同 時也降低了問題的復(fù)雜性 , 但是并沒有將原始信息碼作為構(gòu)造碼字 的依據(jù),選取的碼字直接影響了分類器的性能。針對這一問題 ,本文 提出了改進的 m-ary 支持向量機算法。以手寫數(shù)字識別程序為目標(biāo) , 待識別的目標(biāo)類

16、也因此有 10類(即待 識別的10個數(shù)字：0,1，,9),則所使用的m-ary子分類器數(shù)目應(yīng)為lb 10=4,根據(jù)上面所提到的子svm類別劃分規(guī)則,4個分類器中的類別標(biāo)識如表2所示。2.2輸出校正m-ary算法本文以標(biāo)準(zhǔn)m-ary svm類別劃分編碼為信息碼，采用糾錯能力可控 的編碼方法，加入適當(dāng)?shù)男ｒ炍?，共同?gòu)成碼字，稱為校驗碼。訓(xùn)練 后通過檢錯糾錯原理對實際輸出進行校驗，進而對出錯的分類模式 進行校正，可把該算法稱為輸出校正 m-ary支持向量機(output correcting m-ary svm, oc-msvm),將其應(yīng)用于 pc禾口嵌入式系統(tǒng)下的多類模式識別問題，并用手寫數(shù)字識別

17、程序來驗證該實現(xiàn)。此處 將m-ary svm與糾錯編碼相結(jié)合，使其校驗法能夠檢測模型中子分 類器輸出中的錯誤分類并糾正該錯誤，以期獲得比標(biāo)準(zhǔn)算法更高的 泛化能力。限于具體的應(yīng)用要求，以及簡化解碼的復(fù)雜性要求，可比較分析線 性循環(huán)碼中的系統(tǒng)碼的碼長及設(shè)計最小距離在m-ary svm性能改進方面的影響，進而設(shè)計能夠滿足性能要求的輸出校正m-ary svm模型。由糾錯編碼原理可知，當(dāng)設(shè)計編碼的最小碼間距離為 dmin時： 若dmine+1,則碼組內(nèi)可檢出不多于 e個錯誤；若dmin2t+1,則 碼組內(nèi)可糾正不多于t個錯誤;若dmint+e+1,其中e>t,則碼組內(nèi) 可糾正不多于t個錯誤，同時檢

18、測e個錯誤。由于bch碼是糾錯能力可控的循環(huán)碼，能夠糾正多個隨機錯誤，并且可以根據(jù)期望糾錯的個數(shù)構(gòu)造出理想碼字。本文選用bch編碼方法進行校正m-ary svm的輸出,針對l,m,d碼(l為碼長,m為信息 位長,d為編碼的最小距離）,設(shè)計具有不同糾錯能力的碼字t,并作 為訓(xùn)練m-ary svm的輸入特征分類向量，則原信息碼對應(yīng)于糾錯編 碼的高m位。假設(shè)原訓(xùn)練樣本為（xi,yi）, 其中xi為樣本特征向量,yi為類標(biāo)簽（即yi=O,9）,并表示為表3所示的編碼，利用糾錯編碼方法編碼 后碼字的二進制位數(shù)為I,則輸出校正m-ary算法描述如下：1）利用式（1）和式類別劃分規(guī)則及2.1節(jié)中類別編碼方法

19、將yi 編碼為表3所示碼字ci,其中ci 0,14。2）以ci為信息碼,利用選定的編碼規(guī)則進行編碼，生成對應(yīng)碼長為l、最小碼距為d的碼字ci*,其中ci* 0,1l, 高4位即為ci; 為提高訓(xùn)練過程計算效率，在算法實現(xiàn)時引入了掩碼技術(shù)，即為每 個子分類器svmj分配掩碼maskj二2j-1,其中j=1,2,l。3）將編碼后的訓(xùn)練樣本即（xi,ci*）輸入各個子分類器svmj（其中j=1,2，,l）進行訓(xùn)練：將該訓(xùn)練樣本的類別編碼ci*與maskj進行 位與操作，即ci* maskj,若結(jié)果為0,則將該樣本作為負類樣本； 否則,若結(jié)果為非0,則將該樣本作為正類樣本，用輸入的樣本訓(xùn)練 該兩類分類

20、svm。4）將待識別樣本輸入已訓(xùn)練好的分類器模型中各個子分類器svmj,并得到其輸出yj,按照子分類器編號組成編碼ti,即ti=ylyl-1 y1, 其中 yj 0,1。5）利用檢錯原理檢查編碼ti是否合法,如果合法，則可直接利用所 得編碼的高k位得到分類結(jié)果ci*:此處可直接將ti右移l-4位得 到4位信息碼，即ci* = ti >> (1-4); 否則，利用糾錯原理對ti進 行校正,然后再對ti右移1-4位得到分類結(jié)果。因此,在預(yù)測新的樣本時，第5)步對實際分類器分類編碼利用檢錯 糾錯原理進行必要的檢錯糾錯后得到其所屬類別，該算法可在一定 程度上克服標(biāo)準(zhǔn)m-ary支持向量機容錯

21、性較差的缺點。從上述過程可以看出，由于生成的碼字長度直接決定分類器的復(fù)雜 度,因此輸出糾錯m-ary支持向量機算法的目標(biāo)明確，即把長度為lb k的原貽類別編訓(xùn)作為信息碼，根據(jù)選定的編碼方法編碼為具有最小距離可控的碼字，因此得到的類別編碼不論是在編碼難易 程度方面還是追求最小碼間距離方面，實際是在一定程度上最優(yōu)的 文獻19中提到的ecoc編碼方法如詳盡編碼法和列選擇法由于是 針對長度為指數(shù)級的編碼進行操作的，在類別稍多時工作量太大而 不再實用，爬山法追求的是編碼矩陣的行最小距離與列最小距離之 和最大,雖然可以碼字長度可控，但碼間最小距離并不能保證是最 優(yōu)的,且其中的隨機性較大。在下面的實驗中將用

22、爬山法與bch法獲得等長的碼字，并對兩者的性能進行比較。3實驗設(shè)計及分析本實驗中用到的訓(xùn)練樣本為28X 28像素的手寫數(shù)字圖片經(jīng)過預(yù)處 理、二值化、去除邊界像素并按照灰度級進行規(guī)范化后 ，從中提取 12X 12個的特征,按照一行一行首尾相連形成一個 144維的輸入向 量,實驗的樣本如圖2所示。圖片圖 2 實驗中樣本示例 在此基礎(chǔ)上 , 對于實際輸出的分類編碼進行解碼后 ,通過糾錯程序 對輸出進行必要的糾錯 ,然后用編碼的高 k 位信息碼獲得實際的類 別輸出。實際用到的模型如圖 3 所示。圖片圖 3 改進的 m-ary svm 模型結(jié)構(gòu)圖3中:x為輸入訓(xùn)練樣本，yj為子分類器svmj的輸出（j=

23、1,2,1 且yj=0或I）,ylyl-1yl為各個子分類器分類輸出按照子分類器 序號遞減順序組成的二進制碼串。從 10000個圖片中隨機選取 5組數(shù)據(jù)作為訓(xùn)練樣本和測試樣本 （每 組數(shù)據(jù)包括2000個訓(xùn)練樣本和1000個測試樣本）,在pc上對標(biāo)準(zhǔn) m-ary算法和本文提出的輸出糾錯 m-ary算法進行實驗，并以5次實 驗的平均值作為結(jié)果。同時 , 為進一步比較分析輸出糾錯 m-ary svm 算法的性能，實驗中對隨機編碼法ecoc svm進行了實驗，得出兩種 算法的性能比較結(jié)果，如表4所示，其中oc代表輸出糾錯m-ary svm,ecoc 代表 ecoc svm, dmin 為對應(yīng)碼長碼組的

24、最小距離 ,prec 為各組 1000個測試樣本分類正確率的平均值 ,ttime 為各組測試樣 本的總的分類時間的平均值。表格（有表名）表4pc上oc_msvm與 ecoc svm 性能比較碼長oc-msvmdminprec/%ttime/secoc-svmdminprec/%ttime/s4188.565 .77188.577.347392.2010.78290.4312.918391.8812.04391.2514.7312594.2217.83593.3722.5114796.5622.78593.2527.03! 根據(jù)情 況左右加注：碼長為4時的oc-msvm為標(biāo)準(zhǔn) m-ary svm

25、。從表 4 容易看出 : 無論是 oc-msvm 還是 ecoc svm, 隨著糾錯編碼碼 長的增加,分類器的分類精度都有不同程度的提高。同時 ,由于所需 要的子分類器數(shù)量的增加 , 所需要的分類時間也會明顯的增加，并 且在相同的條件下本文提出的輸出糾錯 m-ary svm 的性能要優(yōu)于隨 機編碼法 ecoc svm。由于此研究的目標(biāo)是支持向量機能夠在嵌入式系統(tǒng)下的應(yīng)用實現(xiàn) , 因此在嵌入式系統(tǒng)環(huán)境中對兩者的性能進行了相同的實驗 , 得到的 性能結(jié)果如表 5 所示（參數(shù)含義同表 4）。表格（有表名）表5嵌入式系統(tǒng)下oc-msvm與ecoc svm性能比較 碼長 oc-msvmdminprec/

26、%ttime/secoc-svmdminprec/%ttime/s4185.107 .34185.047.387387.3213.66286.2613.548387.0615.82386.7215.8812589.7223.04589.3623.1614792.5427.41588.9227.43! 根據(jù)情 況左右加注：碼長為4時的oc-msvm為標(biāo)準(zhǔn) m-ary svm。同樣，在嵌入式系統(tǒng)下，本文提出的輸出校正m-ary svm的性能比標(biāo) 準(zhǔn) m-ary svm 性能有了一定的改善。在訓(xùn)練速度方面 , 由于 m-ary 算法的時間復(fù)雜度為o（m n2）,而對于各種碼長的svm訓(xùn)練過程中 訓(xùn)練

27、樣本數(shù)量n均相同,不同的是子分類器數(shù)量 m,因此隨著碼長I 的增加,相應(yīng)的子分類器數(shù)量增加 ,因此算法的訓(xùn)練時間也就相應(yīng) 地增加 , 從實驗結(jié)果中不難看出這一結(jié)論。此外, 與編碼相關(guān)的因素即最小碼距 dmin 也反映在了上述數(shù)據(jù)中 最小碼距直接影響分類器的性能 ,表 45中碼長為 7,12,14 的碼字 最小距離分別為 3,5,7, 其分類精度隨最小距離的增加依次提高 , 但 同時可以看出 , 對于長度相同的編碼 , 由隨機編碼法得到的碼字并 不是最佳的 , 兩種方法對于長度為 7 和 14 的編碼的最小距離不同 , 因此其性能也就存在一定的差別 , 并且改進算法的性能要優(yōu)于 ecoc svm

28、;另外,oc-msvm中碼長為7和8的碼字最小碼距均為3,雖然后 者增加了一位的碼長 , 這也增加了判錯的概率 , 可以看出后者的分 類精度較前者略低，對于ecoc svm,由于最小距離相同，碼長為12和 14 的編碼對應(yīng)的分類器分類精度并不隨碼長增加而增加 , 反而隨碼 長增加其精度下降 , 因此碼長越長并非意味著分類器的性能越好。4 結(jié)語本文針對m-ary svm泛化性不足的缺陷，利用糾錯編碼原理，充分結(jié) 合了支持向量機二類分類問題的特點 , 將訓(xùn)練樣本的初始類別利用 糾錯編碼技術(shù)編碼為二進制碼串 , 使得標(biāo)準(zhǔn) m-ary 支持向量機算法 通過引入適當(dāng)?shù)娜哂嘧臃诸惼鱽磉_到提高該算法泛化性的

29、目的。本 文詳細地闡述了輸出糾錯 m-ary svm 算法實現(xiàn)過程 , 并從實驗結(jié)果 驗證了此改進算法的可行性 ,同時也得到在性能改進方面的一些結(jié) 論, 碼長和最小碼距成為 m-ary svm 算法改進方面兩個必須考慮的 因素, 這也成為分類精度和分類時間兩者折中考慮的結(jié)合點。進一 步的工作是定量分析碼長及碼間最小距離在 m-ary svm 性能改進上 的影響,從而尋求碼長及最小距離在算法改進上的最佳折中。 參考文獻 :1 vapnik v n.統(tǒng)計學(xué)習(xí)理論的本質(zhì)m.張學(xué)工，譯.北京：清華大學(xué)出版社，2000.2 cortesc, vapnik v n. support vector netw

30、orksj.machinelearni ng,1995,20(3):273-297.3 platt j c, cristia nini n, taylor j s. large margin dagsfor multiclass classificati on c n ips99: proceedi ngsof neural informationprocessing systems. cambridge, ma: mitpress,2000:547-553.4 sebald d j,bucklew j a. support vector mach ines and themultiple h

31、ypothesis test problemj. ieee tran sacti ons onsig nal process ing, 2001,49(11): 2865-2872.5 李廣麗,崔廣順.一種改進的模糊多類支持向量機算法j. 計算機測量與控制,2011,19(4):908-914. 于清,趙暉.一種2_a_2支持向量機多類分類新方法j. 計算 機工程與應(yīng)用,2008,44(25):186-188.7 hsu c,l in c. a comparis on of methods for multiclasssupport vector machi nesj. ieee tran s

32、acti ons on n euraln etworks,2002, 13(2):415-425.8 茍博,黃賢武.支持向量機多類分類方法j.數(shù)據(jù)采集與處理,2006, 21(3):334-339.9 anguitad, ghio a, pischiutta s. a support vector machine with in teger parametersj. n eurocomput ing, 2008,72(1/2/3):480-489.10 anguita d, ghio a,pischiutta s. a hardware-friendlysupport vector machine for embedded automotive applicationsc/ proceedings of internat