基于SVDD的層次糾錯輸出編碼研究

雷 蕾，王曉丹，羅 璽，宋亞飛

（1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051；2.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西西安710077）

基于SVDD的層次糾錯輸出編碼研究

雷 蕾1，王曉丹1，羅 璽2，宋亞飛1

（1.空軍工程大學(xué)防空反導(dǎo)學(xué)院，陜西西安710051；2.空軍工程大學(xué)信息與導(dǎo)航學(xué)院，陜西西安710077）

糾錯輸出編碼能有效地將多類問題分解為一系列二類子問題進(jìn)行求解，已受到眾多機(jī)器學(xué)習(xí)研究者的關(guān)注。如何構(gòu)建基于數(shù)據(jù)的編碼矩陣是編碼方法確定的關(guān)鍵。針對此問題，基于Fisher原理，提出一種基于支持向量數(shù)據(jù)描述（support vector domain description，SVDD）的層次糾錯輸出編碼構(gòu)造方法（hierarchical error-correcting output codes，HECOC）。該方法首先采用SVDD計算各類別的可分程度，從而得到由不同子類構(gòu)成的二叉樹；然后分別對二叉樹的各層結(jié)點進(jìn)行編碼并最終形成層次輸出編碼。在仿真實驗中，對不同子類類群劃分構(gòu)成的基分類器的可分性進(jìn)行了對比，結(jié)果表明，該編碼方法能在保證分類精度的同時，提高基分類器之間的差異性和糾錯輸出編碼的容錯能力。

多類分類；糾錯輸出編碼；類間可分性；支持向量數(shù)據(jù)描述

0 引 言

多類分類是模式識別領(lǐng)域的研究重點和難點。糾錯輸出編碼（error-correcting output codes，ECOC）［1］作為一種分而治之的多類解決方案，將復(fù)雜的多類問題分解為多個簡單的二類分類任務(wù)；同時繼承糾錯碼特有的糾錯能力，使得利用一定的解碼規(guī)則能對由二類分類器產(chǎn)生的錯誤具有一定的糾錯能力。而編碼矩陣的構(gòu)造作為完成ECOC多類分類的第一步，已受到眾多學(xué)者的關(guān)注和研究［2－5］。目前主要的編碼方法有：事前編碼、基于樣本數(shù)據(jù)編碼（也稱基于問題域編碼）和基于基分類器編碼［6］。事前編碼是指編碼不依賴樣本的編碼方法，因此，所得到的編碼矩陣不能反映分類信息，這在實際應(yīng)用中將影響此類編碼的應(yīng)用效果。基于基分類器編碼，即基分類器已選定，如何找出與基分類器最優(yōu)搭配的編碼矩陣。早在2002年，Crammer和Singe經(jīng)過理論分析得出此類編碼問題是NP難問題［6］。而基于數(shù)據(jù)的編碼矩陣能充分利用訓(xùn)練樣本數(shù)據(jù)本身包含的類別信息，從而提升分類效果。目前在此方面的研究有：判別式編碼方法［7］（discriminate error-correcting output codes，DECOC）、子類編碼方法［8］（subclass error-correcting output codes，SECOC）等。2013年，為保證基分類器之間的獨立性，文獻(xiàn)［9］提出子空間ECOC編碼方法（subspace ECOC），利用不同的特征子集訓(xùn)練基分類器。文獻(xiàn)［10］針對經(jīng)典的“一對一”三符號編碼矩陣中符號“0”會引入分類偏差的問題，利用訓(xùn)練樣本分類結(jié)果對編碼矩陣中的碼字“0”進(jìn)行再編碼，并將該分類結(jié)果作為權(quán)值融入到基于損失函數(shù)的解碼過程中，基于人臉數(shù)據(jù)的實驗表明，該方法能提高基于傳統(tǒng)一對一和稀疏編碼矩陣的ECOC分類性能。文獻(xiàn)［11］提出利用編碼矩陣中二類劃分的先驗原始類結(jié)構(gòu)信息可以提高ECOC分類性能，并給出了在流形假設(shè)和聚類假設(shè)的情況下將先驗結(jié)構(gòu)信息融入基分類器決策函數(shù)的方法。文獻(xiàn)［12－13］把編碼矩陣的構(gòu)造問題轉(zhuǎn)化為一個搜索問題并得到包含訓(xùn)練樣本數(shù)據(jù)信息的編碼方法和基于混淆矩陣的自適應(yīng)編碼方法。

本文針對如何構(gòu)造基于數(shù)據(jù)樣本的編碼矩陣問題，提出了一種基于支持向量數(shù)據(jù)描述（support vector domain description，SVDD）的層次糾錯輸出編碼構(gòu)造方法（hierarchical error-correcting output codes，HECOC）。該方法基于Fisher準(zhǔn)則，首先利用SVDD獲得類間可分性度量，并根據(jù)依此度量形成的二叉樹獲得最優(yōu)子類劃分；然后自上而下對二叉樹每層結(jié)點進(jìn)行編碼并最終獲得所需的編碼矩陣。

本文首先簡要介紹基于ECOC進(jìn)行多類分類的原理和HECOC的基本思想；然后提出一種基于SVDD的層次矩陣編碼方法，利用SVDD作為類別可分性度量準(zhǔn)則，找出最優(yōu)類別組合并據(jù)此構(gòu)建層次編碼輸出；最后給出實驗結(jié)果和分析。

1 基于SVDD編碼的思想

模式識別中經(jīng)典的Fisher準(zhǔn)則函數(shù)：

指出，當(dāng)同類別數(shù)據(jù)樣本密集緊湊，不同類別數(shù)據(jù)樣本分散時，就能得到優(yōu)秀的分類效果。因此兩類樣本均值之差越大越好，而類內(nèi)離散度越小越好。此時分類樣本具有最大的類間距離和最小的類內(nèi)距離，最容易被區(qū)分，即具有最佳的分類效果。ECOC編碼的本質(zhì)是如何進(jìn)行最優(yōu)二類劃分，盡可能地減少分類的復(fù)雜性。因此，在基于數(shù)據(jù)的編碼矩陣構(gòu)造當(dāng)中，其目的就是依據(jù)Fisher準(zhǔn)則來盡可能地獲得最優(yōu)的子類劃分，這些子類之間相關(guān)性較小，易于分類；相關(guān)性較大的原始類別將被分為同一子類?；诖祟悇澐謽?gòu)造的基分類器分類的難度最小，能達(dá)到較高準(zhǔn)確率，從而實現(xiàn)分類效果的整體提高［8，13］。

因此，如何根據(jù)Fisher準(zhǔn)則來獲得最佳的子類劃分成為本文方法的關(guān)鍵。基于特征空間幾何距離的方法對樣本數(shù)據(jù)的充分性和樣本分布的先驗知識要求不高，可以較快地進(jìn)行子類劃分，所以本文采用基于特征空間幾何距離的方法。而ECOC子類劃分本身就潛在地將樣本劃分得不平衡，從而導(dǎo)致正負(fù)類樣本數(shù)量上的差異。而基于距離測度的SVDD的學(xué)習(xí)過程僅僅需要“目標(biāo)類”樣本，與非目標(biāo)類關(guān)系不大，很好地解決了分類中樣本不足或者難以獲得非目標(biāo)樣本帶來的學(xué)習(xí)問題［14］。本文采用SVDD作為可分性度量準(zhǔn)則，第2節(jié)將進(jìn)行理論介紹。

2 基于SVDD的HECOC

本節(jié)利用SVDD作為類別劃分度量，從而獲得最優(yōu)子類類群劃分。然后根據(jù)子類劃分自下而上構(gòu)建二叉樹，對二叉樹的每層結(jié)點進(jìn)行編碼，得到最終的層次編碼矩陣。

2.1 SVDD

SVDD是Tax于1999年首次提出的［15－16］，其目的是在高維空間中構(gòu)造一個超球體S，使得該超球體能最大限度地覆蓋所有數(shù)據(jù)樣本。描述如下：

式中，o為中心；r為半徑。最小覆蓋球可以通過求解該二次優(yōu)化問題得到。文獻(xiàn)［16］提出了采用核函數(shù)的思想來得到更為緊湊的優(yōu)化區(qū)域。同時很多文獻(xiàn)引入了松弛變量ξi，使得問題變?yōu)?/p>

這是為了允許有少數(shù)樣本不在超球體內(nèi)。其中，C＞0是一個懲罰因子，其作用是在最小覆蓋球半徑的r大小和可能落在球體外的樣本數(shù)量之間保持平衡。采用Lagrange乘子，將問題轉(zhuǎn)化為對偶問題：

當(dāng)它到超球體中心的距離滿足小于或等于r時，即‖x－o‖2≤r2，則未知樣本被判為目標(biāo)類，否則為非目標(biāo)類。

2.2 基于SVDD的可分性度量

假設(shè)對于k類分類問題，訓(xùn)練樣本集｛X1，X2，…，Xk｝，Xi＝｛x1，x2，…，xNi｝，i＝1，…，k。采用核函數(shù)，分別用每類的訓(xùn)練樣本構(gòu)造SVDD超球面，得到球面集合：S＝｛S1，S2，…，Sk｝＝｛（r1，o1），（r2，o2），…，（rk，ok）｝，其中（ri，oi）表示第i個超球面的半徑和球心。然后計算各類的訓(xùn)練樣本到各類的超球面的距離，構(gòu)成如下矩陣：

解該優(yōu)化問題可得到αi，其中使0＜αi≤C的樣本點被稱為支持向量。

對于未知樣本x而言，設(shè)

式中，mij（t）為第i類訓(xùn)練樣本中到第j類超球面距離小于t的樣本個數(shù)。文獻(xiàn)［17］用mij（t）來表示兩類的相交程度。因為在構(gòu)造各個類的SVDD超球面時，適當(dāng)允許個別樣本落在球體外，超球面不一定能覆蓋所有樣本。所以用mij（t）來表示可分程度不一定準(zhǔn)確。因此本文用兩個超球體的球心距離作為類可分性的判據(jù)：

式中

由式（6）得到的可分性度量矩陣D有兩個性質(zhì)：①對稱性，即dij＝dji；②對角線元素為0。當(dāng)dij≥1說明對應(yīng)的兩類在特征空間沒有交集，不相交，dij越大，兩類的分離程度越好。0＜dij＜1時兩類在該距離定義上相交，值越小，兩類相交程度越高，即可分性越差，在識別過程中就容易發(fā)生誤判。當(dāng)dij＝0時，則說明兩個超球體在特征空間中完全重疊。

2.3 基于SVDD的層次編碼矩陣構(gòu)造

構(gòu)造層次編碼矩陣的重點是對多類根據(jù)類間可分性進(jìn)行劃分。其步驟如下：首先，將每個類視為一個子類類群，然后利用式（6）計算類間可分性度量矩陣D，將最不容易區(qū)分的兩個子類，即dij的最小值所對應(yīng)的兩類（同類間的距離度量值dii排除）合并成一個子類，再計算該重組子類和剩余其他類之間的可分性度量矩陣，將相交程度最高兩個子類進(jìn)行合并，一直到所有子類合并成一個類。對于一個k類問題，這樣就構(gòu)成了一個倒立的二叉樹T。接下來利用該二叉樹的每個節(jié)點（除去葉子節(jié)點和父節(jié)點）對不同子類進(jìn)行編碼：

式中，M（i，j）表示編碼矩陣的第i行第j列碼字；對于二叉樹的第j層結(jié)點（除去父節(jié)點），和分別為其左右樹枝，當(dāng)類別Xi屬于或時，其在編碼矩陣中對應(yīng)的碼字為“1”或“－1”；當(dāng)類別Xi都不屬于這一層結(jié)點時，其對應(yīng)的編碼為“0”。

假設(shè)有5類數(shù)據(jù)，如圖1所示。SVDD的核函數(shù)采用高斯核函數(shù)，通過交叉驗證法選擇其參數(shù)為C＝3.56，σ＝1.02。

圖1 5類高斯分布樣本數(shù)據(jù)

根據(jù)式（6）得到類可分性度量矩陣D1，如表1所示。

表1 5類樣本數(shù)據(jù)的可分性度量矩陣

由類可分性度量矩陣可以看到，類間距離0.026 4最小，將class3和class4合并為一個新類，記為subgroup1＝｛class3，class4｝，此時類的總數(shù)減少1。再利用SVDD，按照式（6）計算新類和其他類的距離，得到新的可分性度量矩陣。依次類推，可以得到如圖2所示的二叉樹。

圖2 5類數(shù)據(jù)的層次二叉樹

自下而上得到二叉樹后，利用式（7）對其進(jìn)行編碼，得到最終的層次輸出編碼矩陣為

3 實 驗

本節(jié)采用UCI數(shù)據(jù)集來驗證本文方法的分類效果。

3.1 實驗數(shù)據(jù)

實驗中所用的UCI數(shù)據(jù)集如表2所示。

表2 UCI數(shù)據(jù)集及數(shù)據(jù)描述

3.2 實驗設(shè)計

首先，基于UCI公共數(shù)據(jù)集對基于SVDD的層次編碼矩陣與幾種經(jīng)典的編碼方法：一對一編碼（one-versusone）、一對多編碼（one-versus-all）、密集隨機(jī)編碼（dense random）、稀疏隨機(jī)編碼（sparse random）、判別式編碼（DECOC）以及子類編碼（SECOC）在不同解碼策略下的分類效果。兩種隨機(jī)編碼方法的選擇按照文獻(xiàn)［13］進(jìn)行。實驗中采用的兩種解碼策略為：Hamming距離解碼和歐式距離解碼；兩種基分類器為：線性邏輯分類器（linear logic classifier，LOGLC）和支持向量機(jī)（多項式核函數(shù)，C＝2）。

接著，對經(jīng)典編碼方法與本文方法進(jìn)行編碼長度比較，討論編碼的有效性和糾錯能力。最后探討在不同編碼方式下，訓(xùn)練得到的基分類器的獨立性。

利用雙邊估計t檢驗法來計算置信水平為0.95的分類錯誤率置信區(qū)間作為最終結(jié)果，計算公式如下：

式中，μ、σ分別表示n重交叉驗證的均值和標(biāo)準(zhǔn)差；t0.025（4）＝2.776 4；t0.025（9）＝2.262 2。

3.3 實驗結(jié)果及分析

3.3.1 分類結(jié)果比較

表3和表4列出了當(dāng)基分類器采用SVM時，基于SVDD的編碼方法HECOC與經(jīng)典編碼方法的分類結(jié)果比較。在每張表中加粗的數(shù)據(jù)為最大分類正確率，分類正確率下方為編碼長度。

從表中的結(jié)果可以看出，在大部分情況下，基于HECOC編碼方法的分類精度要優(yōu)于其他經(jīng)典的事前編碼或部分基于數(shù)據(jù)編碼方法。同時，HECOC編碼矩陣長度也占有優(yōu)勢。這是因為從初始數(shù)據(jù)集開始，進(jìn)行了類間可分性比較，在獲得可分性矩陣的前提下，對二叉樹從上至下進(jìn)行了編碼，使得對于N類樣本數(shù)據(jù)，其編碼矩陣為N×（N－1），這與DECOC編碼的碼字長度類似，但分類精度表現(xiàn)更好；同時針對其他的編碼方法，尤其是事前編碼，HECOC不僅能在促進(jìn)多類分類的實際效果的情況下，提高了編碼的糾錯性能，而且能獲得更加緊湊的編碼，大大縮減了訓(xùn)練和測試時間，提高了編碼解碼的速度。

3.3.2 基分類器差異性比較

為進(jìn)一步總結(jié)本文方法優(yōu)勢，本文從統(tǒng)計學(xué)的角度采用Yule的Q統(tǒng)計量［18］對基分類器之間的差異性進(jìn)行比較。

對于分類器Ci和Cq，兩者之間的Q統(tǒng)計量可表示為

式中，Nab的含義如表5所示。

從式（9）可以看出，對于識別同一類別的基分類器，其Q統(tǒng)計量的值為正，否則為負(fù)；相互獨立的基分類器，其Q值為零。對于L個基分類器，可以用平均值來衡量，即

表3 基于SVM和Hamming距離解碼的各數(shù)據(jù)集分類正確率及置信區(qū)間為0.95的置信區(qū)間 %

表4 基于SVM和歐式距離解碼的各數(shù)據(jù)集分類正確率及置信區(qū)間為0.95的置信區(qū)間 %

表5 Nab的含義

表6和表7給出了在所有數(shù)據(jù)集上的基分類器差異性比較的結(jié)果，第一行是每種方法在所有數(shù)據(jù)集上的平均值。其中“s”表示wintieloss統(tǒng)計量，即col＜row，col＝row和col＞row的數(shù)據(jù)集個數(shù)。

表6 基于SVM的各個數(shù)據(jù)集上差異性比較

表7 基于LOGLC的各個數(shù)據(jù)集上差異性比較

從表中的實驗結(jié)果可以看出，基于HECOC編碼方法訓(xùn)練得到的不同基分類器都具有最大的差異性。7種方法中基分類器差異性由好到差的排列為HECOC、SECOC、DECOC、one-vs-one、dense／sparse、one-vs-all。由前面的分析可得，基于數(shù)據(jù)的編碼矩陣能使子類的可分性最佳，因此，訓(xùn)練不同子類數(shù)據(jù)得到的基分類器之間的差異性也就應(yīng)該更明顯。

4 結(jié) 論

在基于ECOC的多類分類中，如何快速有效地構(gòu)造基于樣本數(shù)據(jù)的編碼是目前研究的重點。本文從Fisher判據(jù)出發(fā)利用SVDD構(gòu)造類可分性準(zhǔn)則，基于該準(zhǔn)則找出最相似的兩類進(jìn)行合并，從而使相關(guān)性較大的子類劃分在一起，依此類推，直到所有子類合并為一個類。然后從上至下建立二叉樹，對二叉樹的每層結(jié)點進(jìn)行編碼，從而獲得最終的層次糾錯輸出編碼。利用公共數(shù)據(jù)集對其驗證發(fā)現(xiàn)HECOC在有效提高多類分類準(zhǔn)確率的同時，能提高基分類器之間的差異性。這也是因為在編碼矩陣構(gòu)造時對相似度高的子類進(jìn)行了合并，將相似度低的子類劃分開來，確保了訓(xùn)練得到的基分類器差異性，同時提高分類精度。

［1］Dietterich T G，Bakiri G.Solving multi-class learning problems via error-correcting output codes［J］.Journal of Artificial Intelligence Research，1995，34（2）：263－286.

［2］Bagheri M A，Qigang G，Escaler S.A genetic-based subspace analysis method for improving error-correcting output coding［J］.Pattern Recognition，2013，46（5）：2830－2839.

［3］Miguel A B，Escaler S，Xavier B，et al.On the design of an ECOC-compliant genetic algorithm［J］.Pattern Recognition，2014，47（8）：865－884.

［4］Escaler S，David M.Online error correcting output codes［J］.Pattern Recognition Letters，2011，32（1）：458－467.

［5］Bouzas D，Arvanitopoulos N，Anastasios T.Optimizing linear discriminant error correcting output codes using particle swarm optimization［J］.Lecture Notes in Computer Science，2011，6792（4）：79－86.

［6］Crammer K，Singer Y.On the learnability and design of output codes for multiclass problems［C］∥Proc.of the 13th Annual Conference on Computational Learning Theory，2000：896－909.

［7］Pujol O，Radeva P，Vitria J.Discriminate ECOC：a heuristic method for application dependent design of error correcting output codes［J］.IEEE Trans.on Pattern Analysis and Machine Intelligence，2006，28（6）：1001－1007.

［8］Escalera S，David M J Tax，Pujol O，et al.Subclass problemdependent design for error-correcting output codes［J］.IEEE Trans.on Pattern Analysis and Machine Intelligence，2008，30（6）：1041－1054.

［9］Bagheri M A，Montazer G A.A subspace approach to error correcting output codes［J］.Pattern Recognition Letters，2013，34（1）：176－184.

［10］Escalera S，Pujol O.Re-coding ECOCs without re-training［J］.Pattern Recognition Letters，2013，31（5）：555－562.

［11］Wang Y Y，Chen S C，Xue H.Can under-exploited structure of original-classes help ECOC-based multi-class classification［J］.Eeurocomputing，2012，89（15）：158－167.

［12］Zhou J D，Wang X D.Coding design for error correcting output codes based on perception［J］.Optical Engineering，2012，51（5）：322－331.

［13］Zhou J D，Wang X D，Zhou H J.Multiclass classification of adaptive error-correcting output codes based on confusion matrix［J］.Systems Engineering and Electronics，2012，34（7）：1518－1524.（周進(jìn)登，王曉丹，周紅建.基于混淆矩陣的自適應(yīng)糾錯輸出編碼多類分類方法［J］.系統(tǒng)工程與電子技術(shù)，2012，34（7）：1518－1524.）

［14］Zhu X K，Yang D G.Multi-class support vector domain description for pattern recognition based on a measure of expansibility［J］.Acta Electronica Sinica，2009，37（3）：464－469.（朱孝開，楊德貴.基于推廣能力測度的多類SVDD模式識別方法［J］.電子學(xué)報，2009，37（3）：464－469.）

［15］Tao Q，Luo Q.Coordinate descent algorithms for large-scale SVDD［J］.Pattern Recognition and Artificial Intelligence，2012，25（6）：950－957.（陶卿，羅強.大規(guī)模SVDD的坐標(biāo)下降算法［J］.模式識別與人工智能，2012，25（6）：950－957.）

［16］Wang X F，Zhang J P，Zhang Y.Unmixing algorithm of hyperspectral images［J］.Journal of Infrared Millimeter Waves，2012，29（3）：210－215.（王曉飛，張鈞萍，張曄.高光譜圖像混合像元分解算法［J］.紅外與毫米波學(xué)報，2012，29（3）：210－215.）

［17］Liu Z G，Li D R.Hierarchical multi-category support vector machines based inter-class separability in feature space［J］.Geomatics and Information Science of Wuhan University，2004，29（4）：324－328.（劉志剛，李德仁.基于特征空間中類間可分性的層次性多類支持向量機(jī)［J］.武漢大學(xué)學(xué)報（信息科學(xué)版），2004，29（4）：324－328.）

［18］Garcia P N，Ortiz-Boyer D.An empirical study of binary classifier fusion methods for multi-class classification［J］.Information Fusion，2011，12（9）：111－130.

Hierarchical error-correcting output codes based on SVDD

LEI Lei1，WANG Xiao-dan1，LUO Xi2，SONG Ya-fei1
（1.Air and Missile Defense Institute，Air Force Engineering University，Xi’an 710051，China；2.Information and Navigation Institute，Air Force Engineering University，Xi’an 710077，China）

As a decomposing framework，error-correcting output codes（ECOC）can effectively reduce the multiclass to the binary and attract much attention，in which the construction of coding matrix based on data is the key to use ECOC to solve multiclass problems.An approach of hierarchical error-correcting output codes（HECOC）based on support vector domain description（SVDD）and Fisher theory is presented.Firstly，the SVDD is used to measure the class separabilty quantitatively.Then the inter-class separability matrix is got gradually.The binary tree is built based on the matrixes from the bottom to the top.Then，each node of the binary tree is encoded by the level to get the final HECOC.The separability of base classifiers trained by different class partition is compared in experiments.The results show that the HECOC can promote the diversity of the base classifiers and the error-correcting ability of codewords as well as enhance the classification accuracy.

multi-classification；error-correcting output codes（ECOC）；class separability；support vector domain description（SVDD）

TP 391

A

10.3969／j.issn.1001-506X.2015.08.30

雷 蕾（1988－），女，博士研究生，主要研究方向為目標(biāo)識別、智能信息處理。

E-mail：wendyandpaopao＠163.com

王曉丹（1966－），女，教授，博士，主要研究方向為智能信息處理、機(jī)器學(xué)習(xí)。

E-mail：21776496＠qq.com

羅 璽（1988－），男，碩士，主要研究方向為智能信息處理。

E-mail：wendyandpaopao2＠163.com

宋亞飛（1988－），男，博士研究生，主要研究方向為數(shù)據(jù)融合、目標(biāo)識別。

E-mail：yafei＿song＠163.com

1001－506X201508－1916－06

網(wǎng)址：www.sys－ele.com

2014－01－06；

2014－09－24；網(wǎng)絡(luò)優(yōu)先出版日期：2015－01－20。

網(wǎng)絡(luò)優(yōu)先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150120.1050.007.html

國家自然科學(xué)基金（60975026，61273275）資助課題