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

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

（1.空軍工程大學防空反導學院，陜西西安710051；2.空軍工程大學信息與導航學院，陜西西安710077）

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

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

（1.空軍工程大學防空反導學院，陜西西安710051；2.空軍工程大學信息與導航學院，陜西西安710077）

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

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

0 引 言

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

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

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

1 基于SVDD編碼的思想

模式識別中經典的Fisher準則函數：

指出，當同類別數據樣本密集緊湊，不同類別數據樣本分散時，就能得到優秀的分類效果。因此兩類樣本均值之差越大越好，而類內離散度越小越好。此時分類樣本具有最大的類間距離和最小的類內距離，最容易被區分，即具有最佳的分類效果。ECOC編碼的本質是如何進行最優二類劃分，盡可能地減少分類的復雜性。因此，在基于數據的編碼矩陣構造當中，其目的就是依據Fisher準則來盡可能地獲得最優的子類劃分，這些子類之間相關性較小，易于分類；相關性較大的原始類別將被分為同一子類?；诖祟悇澐謽嬙斓幕诸惼鞣诸惖碾y度最小，能達到較高準確率，從而實現分類效果的整體提高［8，13］。

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

2 基于SVDD的HECOC

本節利用SVDD作為類別劃分度量，從而獲得最優子類類群劃分。然后根據子類劃分自下而上構建二叉樹，對二叉樹的每層結點進行編碼，得到最終的層次編碼矩陣。

2.1 SVDD

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

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

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

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

2.2 基于SVDD的可分性度量

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

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

對于未知樣本x而言，設

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

式中

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

2.3 基于SVDD的層次編碼矩陣構造

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

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

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

圖1 5類高斯分布樣本數據

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

表1 5類樣本數據的可分性度量矩陣

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

圖2 5類數據的層次二叉樹

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

3 實 驗

本節采用UCI數據集來驗證本文方法的分類效果。

3.1 實驗數據

實驗中所用的UCI數據集如表2所示。

表2 UCI數據集及數據描述

3.2 實驗設計

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

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

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

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

3.3 實驗結果及分析

3.3.1 分類結果比較

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

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

3.3.2 基分類器差異性比較

為進一步總結本文方法優勢，本文從統計學的角度采用Yule的Q統計量［18］對基分類器之間的差異性進行比較。

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

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

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

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

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

表5 Nab的含義

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

表6 基于SVM的各個數據集上差異性比較

表7 基于LOGLC的各個數據集上差異性比較

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

4 結 論

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

［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］.系統工程與電子技術，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］.電子學報，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.（陶卿，羅強.大規模SVDD的坐標下降算法［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］.紅外與毫米波學報，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］.武漢大學學報（信息科學版），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－），女，博士研究生，主要研究方向為目標識別、智能信息處理。

E-mail：wendyandpaopao＠163.com

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

E-mail：21776496＠qq.com

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

E-mail：wendyandpaopao2＠163.com

宋亞飛（1988－），男，博士研究生，主要研究方向為數據融合、目標識別。

E-mail：yafei＿song＠163.com

1001－506X201508－1916－06

網址：www.sys－ele.com

2014－01－06；

2014－09－24；網絡優先出版日期：2015－01－20。

網絡優先出版地址：http：／／www.cnki.net／kcms／detail／11.2422.TN.20150120.1050.007.html

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