基于多分類支持向量機的船舶槳葉數識別研究

戴衛國?　邱家興　王易川　程玉勝

（海軍潛艇學院　青島　266042）

?研究報告?

基于多分類支持向量機的船舶槳葉數識別研究

戴衛國?邱家興王易川程玉勝

（海軍潛艇學院青島266042）

分析了目前常用的支持向量機多分類方法以及存在的不足，本文提出了一種混合糾錯輸出編碼的多分類支持向量機改進算法，并應用于利用船舶目標輻射噪聲DEMON譜進行船舶槳葉數分類的實驗。理論分析與實驗結果表明，該改進算法編碼明確、具備糾錯能力，是一種有效的多分類支持向量機方法，在船舶槳葉數識別中，其分類性能優于一對余、一對一及最小輸出編碼支持向量機等多分類方法，可適用于船舶槳葉數的分類識別。

船舶輻射噪聲，支持向量機，多分類，螺旋槳槳葉數

1　引言

船舶目標槳葉數物理意義明確，與船舶工況無相關性，是進行水聲目標識別最重要的識別特征之一，在某些情況下單憑槳葉數即可識別目標，這對船舶目標識別具有特別的意義。通過對船舶輻射噪聲的DEMON（Detection of envelope modulation on noise）譜分析可以獲取船舶目標槳葉數特征［1］。

支持向量機（SVM）是一種基于統計學習理論的模式識別方法，建立在統計學習理論VC維（Vapnik Chervonenkis dimension）理論和結構風險最小原理基礎上，采用結構風險最小化原則代替了傳統機器學習方法中的經驗風險最小化原則，與其他學習機相比具有良好的推廣能力和很強的普適性，已經被成功地應用到目標識別與分類等問題中［2-4］。但是，傳統的SVM是基于兩類目標分類問題，而實際需要解決的一般是多類問題，如何有效地將其推廣到多類問題仍是當前SVM研究的重要內容之

一［5-6］。

本文通過對目前SVM分類方法的分析，在糾錯輸出編碼（Error correcting out code，ECOC）SVM多分類的基礎上，克服糾錯輸出編碼的編碼隨機的不足，以一對余、一對一的多分類方法為基礎，將稠密型和稀疏型糾錯輸出編碼方法融合在一起，提出了一種混合糾錯輸出編碼（MECOC）SVM多分類算法，該算法編碼明確、具備糾錯能力。通過利用船舶目標輻射噪聲DEMON譜進行螺旋槳槳葉數分類的實驗，表明該算法是一種有效的SVM多分類方法。

2　傳統的SVM多分類方法

目前通常使用的SVM多分類方法主要有用多個兩類分類器實現、用層次型兩類分類器實現、用一個最優化問題一次性實現和用糾錯輸出編碼實現等方法［5-7］。

2.1用多個兩類分類器實現多類分類

用多個兩類分類器實現多類分類的方法主要有一對余、一對一兩種方式。

2.1.1一對余

“一類對余類（One-versus-all，簡稱一對余）”算法是SVM解決多分類問題的一種方法，對于k（k≥2）類分類問題，構造k個兩類分類器，將k分類問題轉化為k個兩類分類問題。第i個SVM分類問題是把第i類作為一類，其余k-1類為另一類。對于給定的l個訓練樣本（x1，y1），···，（xl，yl），j，j=1，2，···，l，yj∈｛1，...，k｝，第i個SVM可通過求解下面的最優化問題得到

式（1）中：wi∈Rn為第i個SVM中分類超平面的法向量；bi∈R為偏置量；ξj∈R為約束條件中非負的松弛項；C為懲罰因子；Φ是所采用的核函數。

對未知樣本x進行分類時，用k個兩類決策函數進行判定，x屬于wi·Φ（x）+bi中最大值的上標i所對應的類別［6-7］。

2.1.2一對一

“一類對一類（One-versus-one，簡稱一對一）”算法是SVM解決多分類問題的另一種方法，該算法是在每2類之間訓練一個SVM分類器，因此對于一個k類問題，訓練階段共構造k（k-1）/2個兩類分類器，每個分類器是取任意2個類別的數據進行訓練。對第i類和第j類之間的分類器，可通過求解下面的最優化問題得到

對未知樣本x進行分類時，常用的一種方法是“最大投票法”，x屬于最后票數最多的那一類［7］。

2.2用糾錯輸出編碼實現多類分類

2.2.1糾錯輸出編碼

糾錯輸出編碼SVM分類方法是對類別通過二進制編碼將多類問題轉化為多個兩類問題，采用具有糾錯能力的編碼對類別進行編碼，并將SVM作為碼位分類器的一種多分類算法。

對于k類數據的分類問題，定義一個k×m的編碼矩陣M，每一行稱為“碼字”，每一個編碼元素稱為“碼位”，每個元素的取值范圍可采用二符號｛-1，+1｝表示，“1”和“-1”表示正、負兩類（即稠密型編碼），或采用三符號｛-1，0，+1｝表示，“0”表示該碼字位所對應的類不參加該分類器的訓練（即稀疏型編碼），這就把k類分類問題轉化為m個兩類分類問題。由于每個碼位上的分類器只需要做兩類分類，所以可以采用SVM作為碼位分類器。

對于一個新樣本，m個SVM分類結果構成一個碼字S，k個編碼中與S漢明距離最小的碼字所代表的類別就是這個新樣本所屬類別。對于一個最小漢明距離為d的編碼來說，最少能修正（d-1）/2位錯誤［8-9］。

2.2.2最小輸出編碼

最小輸出編碼（MOC）是在糾錯輸出編碼方法基礎上進行的一種改進方法，而改進的重點就是采用確定的最少的兩類支持向量機實現多類分類。在二進制數的基礎上構建分類編碼矩陣，建立采用能夠對多類問題進行分類的最小數目的兩類分類器。其中，四類分類問題只需要兩個二類分類器即可構造分類編碼矩陣。但該編碼的最小漢明距離為2，不具備糾錯能力［10］。

2.2.3最小漢明距離譯碼

在譯碼過程中，一般采用最小漢明距離譯碼的方式進行譯碼，在編碼過程中存在稀疏編碼的情況下，即在｛-1，0，1｝三符號編碼情況下，兩向量U，V∈｛-1，0，1｝l之間的漢明距離為［8］

其中，l為編碼長度。

3　混合糾錯輸出編碼SVM多分類方法

3.1傳統SVM多分類存在的主要問題

從目前常用的SVM多分類方法來看，主要存在以下問題：

（1）用一個最優化問題一次性實現多類分類，由于需要同時優化選擇多個SVM的模型參數，不利于SVM的參數尋優，分類精度一般；

（2）用層次型兩類分類器實現多類分類，主要是用有向無環圖和二叉樹結構多分類SVM進行多分類。由于存在誤差積累問題，應用存在一定的局限性；

（3）應用最普遍的一對一、一對余方式用多個兩類分類器實現多類分類，但存在誤分、拒分區域較大的問題；

（4）最小輸出編碼不具備糾錯能力，且也存在誤差積累問題；

（5）常規的糾錯輸出編碼具備（d-1）/2位的糾錯能力，但其在編碼過程，尤其詳盡碼（Exhaustive codes）編碼［10］時，對實際問題的聚類性質考慮不夠，在劃分目標類型時，常把不相干的兩類及多類目標混成一類目標進行訓練，人為地增加了SVM的訓練難度和測試誤差。

3.2混合糾錯輸出編碼的基礎編碼

3.2.1一對余編碼

一對余的SVM分類方法可以看作是糾錯輸出編碼的一種特殊方式，屬于稠密型編碼類型（即二符號編碼），該方式的編碼方式為在每個分類器基中都把對應的類作為正類而把其他作為負類來訓練。具體編碼形式為

該編碼的碼間最小漢明距離為2［8］，不具備糾錯能力。

3.2.2一對一編碼

一對一的SVM分類方法仍可以看作是糾錯輸出編碼的一種特殊方式，屬于稀疏型編碼類型（即三符號編碼），所有類兩兩之間的每一個組合都對應于一個分類器。具體形式為

該編碼的碼間最小漢明距離為（C2k-1）/2+1［8］，在k≥4的情況下，具備糾錯能力。

3.3混合糾錯輸出編碼的SVM多分類編碼

在糾錯輸出編碼的基礎上，以一對余、一對一的多分類SVM為依托，將稠密型和稀疏型糾錯輸出編碼方法融合在一起，提出了一種混合糾錯輸出編碼多類SVM算法。

3.3.1混合糾錯輸出編碼多分類支持向量編碼原則

（1）“冗余編碼”

按照一對余、一對一的SVM二分類器的原則，分別訓練各SVM分類器，并進行各分類器的分類模型尋優。然后將一對余、一對一的所有分類器均參加分類編碼，各分類可采用不同的模型參數，不同的核函數和不同類型的SVM算法。

（2）“分區配置”

將一對余配置的各分類器放置于I區，將一對一配置的各分類器放置于II區，兩區平行配置。

3.3.2混合糾錯輸出編碼多分類支持向量編碼方法

按照3.3.1的編碼原則，以“+1”表示將此類目標樣本編入正類；以“-1”表示將此類目標樣本編入負類；“0”表示將此類樣本不參加訓練，構建了混合糾錯輸出編碼的編碼方法：

該編碼的碼間最小漢明距離為（C2k-1）/2+3，在多類（k≥3）的情況下，具備（C2k-1）/4+1位的糾錯能力。

混合糾錯輸出編碼的理想輸出為該編碼的編碼方案，以四類（A、B、C、D）為例，A類的理想輸出編碼為｛1-1-1-1 1 1 1 0 0 0｝；B類的理想輸出編碼為｛-1 1-1-1-1 0 0 1 1 0｝；C類的理想輸出編碼為｛-1-1 1-1 0-1 0-1 0 1｝；D類的理想輸出編碼為｛-1-1-1 1 0 0-1 0-1-1｝。

但在實際的目標譯碼過程中，A目標在“B對C”、“B對D”、“C對D”的分類判決中，同樣會有“+1”或“-1”的輸出，不可能先知先覺地輸出“0”而到達理想的輸出。因此在實際輸出中，在3分類混合糾錯輸出編碼到理想輸出編碼的最小漢明距離為0.5，在4分類混合糾錯輸出編碼到理想輸出編碼的最小漢明距離為1.5，在5分類混合糾錯輸出編碼到理想輸出編碼的最小漢明距離為3.0。

3.4混合糾錯輸出編碼最小漢明距離譯碼算法

（1）按照混合糾錯輸出編碼方案對目標樣本進行分組，可分為正類、負類，或不參加訓練；

（2）按照分組方案分別訓練各二分類SVM分類器，尋求最優分類模型參數，構建支持向量機分類模型；

（3）應用各二分類SVM分類器對待識別目標樣本進行分類，輸出其分類編碼；

（4）分別計算該輸出編碼與各類理想輸出編碼之間的漢明距離；

（5）漢明距離最小的類別即為該目標輸出類別。

4　實驗及分析

4.1實驗準備

目前，船舶螺旋槳葉片數一般為三葉、四葉、五葉、六葉和七葉共五類，根據葉片數從三葉到七葉的順序，可將艦船目標分為A～E五類。

槳葉數識別主要包括特征提取和分類識別兩部分。在特征提取部分，通過對船舶目標輻射噪聲進行DEMON譜分析，提取DEMON譜軸頻的1至15階諧波線譜的幅度、線譜寬度，軸頻的頻率穩定度、幅度穩定度，諧波簇信噪比共33維特征，進行歸一化處理后作為槳葉數識別的特征；在分類識別部分，為驗證本文提出的基于混合糾錯輸出編碼的SVM算法有效性，本文同時采用“最小輸出編碼SVM”、“一對余SVM”、“一對一SVM”、“BP（Back propagation）神經網絡”和“近鄰法”共5種分類算法進行槳葉數識別，作為對比參照算法。

進行試驗的船舶目標輻射噪聲樣本全部為海上綜合聲納聽測波束實際錄取的船舶目標噪聲，試驗樣本的選取條件：（1）在綜合聲納對噪聲目標探測和穩定跟蹤后輸出得到的遠場單目標噪聲信號；（2）船舶目標噪聲DEMON譜中存在可見的調制線譜；（3）船舶目標的類型特征、槳葉數明確。通過樣本選取共獲取了3725個船舶目標噪聲樣本，按葉片數進行分類，其中A類樣本1466個、B類樣本1101個、C類樣本570個、D類樣本240個、E類樣本348個。

4.2槳葉數識別特征提取

對船舶輻射噪聲依次進行帶通濾波、檢波、低通濾波、降采樣、FFT（Fast Fourier transformation）變換得到DEMON譜［1］，如圖1所示，橫坐標為頻率，縱坐標為幅度。DEMON譜中一般存在很多頻率成倍數關系的諧波線譜，這組諧波中的第一根線譜頻率對應螺旋槳轉速。根據諧波線譜的幅度關系、寬度特征、穩定度、信噪比等特征，可以判斷螺旋槳的槳葉數信息，圖1為典型的4葉槳目標DEMON譜圖。

本文提取的槳葉數識別特征是由以下5部分特征組成的33維特征矢量：

（1）軸頻的1至15階諧波線譜的歸一化幅度大小；

（2）軸頻的1至15階諧波線譜的歸一化寬度大小；

（3）軸頻的頻率穩定性，本文以30 s數據中軸頻頻率變化的方差作為頻率穩定性特征；

（4）軸頻的幅度穩定性，本文以30 s數據中軸頻幅度變化的方差作為幅度穩定性特征；

（5）諧波簇信噪比，本文以15階諧波線譜相對背景干擾線譜的突出程度作為信噪比特征。

據此對圖1所示DEMON譜進行分析，得到33維槳葉數識別特征矢量如圖2所示。

圖1　某典型4葉槳目標DEMON譜圖Fig.1 A typical DEMON spectrum of one 4 blades ship

圖2　33維特征矢量示意圖Fig.2 Schematic diagram of 33 dimension feature vector

4.3基于SVM的實驗

利用混合糾錯輸出編碼—最小漢明距離譯碼算法進行船舶目標螺旋槳葉片數的SVM多分類實驗，并與一對多、一對一編碼方式，以及最小輸出編碼方法進行了對比。

在實驗中將樣本隨機分為兩部分，50%用于訓練，50%用于測試，應用徑向基核函數SVM對樣本進行實驗，采用網格搜索法，在懲罰因子C=1～100之間，以1為單位步進；徑向基核函數，σ=0.1～10之間，以0.01為單位步進，根據總樣本的錯誤識別率最小原則，分別獲取各SVM算法模型的最優參數，以此模型參數對訓練樣本、測試樣本進行測試。

其中，最小輸出編碼方法采用了3個分類器，其具體編碼為

一對余編碼方法共應用了5個分類器，其具體編碼為

一對一編碼方法共應用了10個分類器，其具體編碼為

混合糾錯輸出編碼法的I區為前5列，對應一對余編碼區，II區為后10列，對應一對一編碼區，共應用了15個分類器（f1—f15）。其具體編碼方式如表1所示。

按照混合糾錯輸出編碼—最小漢明距離譯碼算法的過程，依據各支持向量機算法的具體編碼方式，隨機進行10次多分類實驗。

4.4基于BP神經網絡的實驗

BP算法為目前應用最為廣泛的神經網絡學習算法，近90%的神經網絡應用是基于BP算法的［11］。本文對同一批數據，采用隨機抽取50%樣本訓練，50%進行測試，通過綜合考慮和模型尋優后，采用輸入層為33個神經元，中間層為12個神經元、輸出層為5個神經元的三層BP神經網絡進行了10次分類實驗。

4.5實驗結果

基于支持向量機各編碼方式以及BP神經網絡、近鄰法的各實驗結果平均正確率（百分比%）如圖3所示。

4.6實驗分析

本實驗屬于5類目標的多分類問題，其實驗結果分析如下：

（1）最小輸出編碼和一對余算法，采用了二符號編碼方式，編碼之間最小漢明距離為2，不具備糾錯能力，所有的訓練樣本均參加每一個基礎二分類的訓練，分別應用了3個和5個基礎兩分類器進行分類，總體多類分類效果一般；

（2）一對一算法，采用了三符號編碼方式，編碼之間最小漢明距離為5.5，具備糾正2位輸出錯誤的能力，每一個基礎分類器僅有兩類樣本參加訓練，其他三類樣本不參加訓練，雖然應用了10個基礎兩分類器進行分類，但由于每個基礎分類器的訓練樣本數量少，從而總的訓練計算量仍小于一對余的5個基礎兩分類器的總訓練量，總體分類效果優于最小輸出編碼和一對余算法；

（3）混合糾錯編碼-漢明距離譯碼應用了二符號編碼和三符號編碼的混合糾錯輸出編碼方式，編碼之間最小漢明距離為7.5，具備糾正3位輸出錯誤的能力，綜合運用了一對余算法、一對一算法共15個基礎兩分類器進行分類，其編碼配置雖然存在一定的冗余，但編碼明確、訓練和測試時計算量為“一對一”、“一對多”的計算量之和，不大于“一對多”算法的2倍的計算量。其總體多類分類效果最優，尤其是在C類、D類、E類不均衡小樣本的分類中明顯優于其他算法；

（4）經過參數尋優后的三層BP神經網絡以及近鄰法，其總體性能弱于一對一和混合輸出糾錯編碼的支持向量機算法，尤其是在小樣本的分類中明顯弱于混合輸出糾錯編碼算法。

表1　5分類混合糾錯輸出編碼的具體編碼方式Table 1 The detailed coding method of MECOC for 5 classes’classification

綜合而言，在對船舶槳葉數分類識別中，本文所提出的混合糾錯輸出編碼方法是一種有效的支持向量機多分類方法。

5　結論

通過對支持向量機多分類方法的理論分析和應用對比，提出了混合糾錯輸出編碼的支持向量機多分類算法，該算法編碼明確，采用了分區配置、冗余編碼的方法，雖然所用的基礎分類器有所增加，但總體計算量不大于2倍“一對多”算法的計算量，且具備（C2k-1）/4+1位的糾錯能力。應用于船舶目標輻射噪聲的螺旋槳槳葉數分類實驗，表明該算法的多分類算法性能優于“一對余”、“一對一”、最小輸出編碼等傳統的多分類方法，可適用于船舶槳葉數分類，是一種有效的多分類算法，可以進一步研究和應用。

［1］程玉勝，王易川，史廣智.基于現代信號處理技術的艦船噪聲信號DEMON分析［J］.聲學技術，2006，25（1）：71-74.

CHENG Yusheng，WANG Yichuan，SHI Guangzhi.DEMON analysis of underwater target radiation noise based on modern signal processing［J］.Technical Acoustics，2006，25（1）：71-74.

［2］劉向東，陳兆乾.一種快速支持向量機分類算法的研究［J］.計算機研究與發展，2004，41（8）：1327-1330.

LIU Xiangdong，CHEN Zhaoqian.A fast classification algorithm of support vector machines［J］.Journal of Computer Research and Development，2004，41（8）：1327-1330.

［3］CHANG Y W，LIN C J.Feature ranking using linear SVM［J］.Journal of Machine Learning Research，2008，3：53-64.

［4］Ryan Rifkin，Aldebaro Klautau.In defense of one-vsall classification［J］.Machine Learning Research，2004，5：101-141.

［5］趙春暉，陳萬海，趙春燕.多類支持向量機方法的研究現狀與分析［J］.智能系統學報，2007，2（2）：11-17.

ZHAO Chunhui，CHEN Wanhai，ZHAO Chunyan.Research and analysis of methods for multiclass support vector machines［J］.CAAI Transactions on Intelligent Systems，2007，2（2）：11-17.

［6］黃勇，鄭春穎，宋忠虎.多類支持向量機算法綜述［J］.計算技術與自動化，2005，24（4）：61-63.

HUANG Yong，ZHENG Chunying，SONG Zhonghu. Multi-classsupportvectormachinesalgorithmsummarization［J］.Computing Technology and Automation，2005，24（4）：61-63.

［7］Vojtěch Franc，Václav Hlavá?.Statistical pattern recognition toolbox for Matlab user's guide［EB/OL］.［2013-12-12］.ftp：//cmp.felk.cvut.cz/pub/cmp/articles/Franc-TR-2004-08.pdf.

［8］ALLWEIN E L，SCHAPIRE R E，SINGER Y.Reducing multiclass to binary：a unifying approach for margin classifiers［J］.Journal of Machine Learning Research，2000，1：113-141.

［9］吳成東，杜崇峰，楊麗英.基于誤差修正碼的支持向量機大類別分類方法［J］.沈陽建筑工程學院學報，2004，20（1）：66-70.

WU Chengdong，DU Chongfeng，YANG Liying.A multiclass classification method of support vector machine based on error correcting output codes［J］.Journal of Shenyang Arch.and Civ.Eng.Univ.，2004，20（1）：66-70.

［10］HSU C W，LIN C J.A comparison of methods for multiclass support vector machines［J］.Neural Networks，2002，13（2）：415-425.

［11］許東，吳錚.基于MATLAB6.X的系統分析與設計——神經網絡［M］.西安：西安電子科技大學出版社，2003.

Ship propeller blade number classification based on multi-class support vector machine

DAI WeiguoQIU JiaxingWANG YichuanCHENG Yusheng
（Navy Submarine Academy，Qingdao 266042，China）

The paper first analyzes the common multi-class support vector machine（SVM）classification algorithms and points out the disadvantages of these algorithms，and then presents an advanced multi-class SVM classification algorithm based on mix error correcting out code（MECOC）.Experiment of ship propeller blade number classification which is based on DEMON spectrum of ship target radiated noise has been done by using this algorithm.Theoretical and experimental results show that the proposed algorithm with clear code and error correction ability is an efficient multi-class SVM classification algorithm.In the ship propeller blade number classification experiment，the classification performance of this algorithm is better than one-versus-all，one-versus-one and minimum output coding（MOC）multi-class SVM classification algorithm，which is suitable for ship propeller blade number classification problem.

Ship-radiated noise，SVM，Multi-class，Propeller blade number

O427.9

A

1000-310X（2015）03-0236-07

10.11684/j.issn.1000-310X.2015.03.008

2014-09-01收稿；2015-03-17定稿

戴衛國（1968-），男，河北深州人，博士，副教授，研究方向：水聲目標識別。?

E-mail：dwg1968@163.com