最小二乘支持向量機(jī)的兩點(diǎn)改進(jìn)

王立國(guó)，趙亮，石瑤，路婷婷

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001）

最小二乘支持向量機(jī)的兩點(diǎn)改進(jìn)

王立國(guó)，趙亮，石瑤，路婷婷

（哈爾濱工程大學(xué)信息與通信工程學(xué)院，黑龍江哈爾濱150001）

最小二乘支持向量機(jī)以其較好的性能得到了廣泛應(yīng)用，但仍存在2點(diǎn)不足：一方面，最小二乘支持向量機(jī)將所有訓(xùn)練樣本都作為支持向量參與未知樣本的分類，導(dǎo)致該算法在泛化過(guò)程中處理速度較慢；另一方面，最小二乘支持向量機(jī)主要利用光譜數(shù)據(jù)進(jìn)行訓(xùn)練和分類，忽略了對(duì)地物空間信息的挖掘，影響了分類精度。為此，提出一種基于庫(kù)倫引力模型的樣本縮減策略，在此基礎(chǔ)上將分類結(jié)果與基于空間信息的分類器相融合，由此產(chǎn)生的新分類器可以有效解決以上兩方面的問(wèn)題。實(shí)驗(yàn)表明了新分類模型在分類精度與速度方面的優(yōu)勢(shì)。

高光譜；支持向量機(jī)；樣本縮減；馬爾科夫隨機(jī)場(chǎng)；空間信息

高光譜遙感技術(shù)也已經(jīng)成為礦產(chǎn)資源探測(cè)、環(huán)境監(jiān)測(cè)、海洋調(diào)查、精細(xì)農(nóng)業(yè)、植被研究、軍事偵察與識(shí)別偽裝等領(lǐng)域的有效技術(shù)手段。高光譜圖像在實(shí)現(xiàn)監(jiān)測(cè)、勘探等目標(biāo)的重要前提是分類技術(shù)，其中從統(tǒng)計(jì)學(xué)習(xí)理論中發(fā)展起來(lái)的支持向量機(jī)，以結(jié)構(gòu)風(fēng)險(xiǎn)最小化作為理論基礎(chǔ)，避免了過(guò)學(xué)習(xí)造成分類器過(guò)于復(fù)雜，喪失泛化性的問(wèn)題，尤其在有限樣本的情況下仍然具有良好的分類性能［1?4］，因而受到國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，其核函數(shù)的引入，也為解決線性不可分問(wèn)題提供了最佳的解決途徑。在文獻(xiàn)［5］中，將支持向量機(jī)與最大似然分類器，神經(jīng)網(wǎng)絡(luò)分類器以及決策樹分類器進(jìn)行了對(duì)比，結(jié)果表明支持向量機(jī)相比其他幾種分類器在分類精度上具有明顯的優(yōu)勢(shì)。

隨著支持向量機(jī)（support vector machine，SVM））的不斷發(fā)展，產(chǎn)生了許多SVM的新類型，如球形SVM、單類SVM、最小二乘SVM（least squares SVM，LSSVM）、模糊SVM、粒度SVM、排序SVM、孿生SVM，等。在這些發(fā)展類型中，LSSVM因其高效的分類和回歸功能而得到廣泛的使用。更為主要的：LSSVM的數(shù)學(xué)模型是一個(gè)僅帶有等式約束的誤差代價(jià)函數(shù)平方和的優(yōu)化問(wèn)題，其求解可在線性系統(tǒng)中進(jìn)行，學(xué)習(xí)過(guò)程得到大大簡(jiǎn)化。不足的是：LSS?VM將二次規(guī)劃問(wèn)題轉(zhuǎn)化為方程組求解問(wèn)題，但卻喪失了支持向量的稀疏性，泛化模型的復(fù)雜所導(dǎo)致的應(yīng)用效率較低影響了該方模型的廣泛應(yīng)用，特別是一些特定領(lǐng)域的應(yīng)用中對(duì)實(shí)時(shí)性有較高的需求，這將嚴(yán)重影響該方法的實(shí)用價(jià)值。另一方面，LSS?VM主要利用光譜數(shù)據(jù)進(jìn)行訓(xùn)練以及分類，忽略了對(duì)地物空間相關(guān)性的挖掘，造成信息獲取不充分的缺陷。針對(duì)以上問(wèn)題，本文在基本保持分類精度的前提下，引用物理學(xué)原理對(duì)SVM的訓(xùn)練樣本進(jìn)行精簡(jiǎn)以提高泛化效率，在此基礎(chǔ)上，同時(shí)利用MRF（Markov random field，MRF）模型將原始分類結(jié)果進(jìn)行與空間相關(guān)信息的融合，進(jìn)一步提高分類精度。

1 庫(kù)倫力縮減策略

在普通SVM中，只有數(shù)量較少的支持向量對(duì)最優(yōu)分類超平面的確定起作用，而在LSSVM［6］中，由公式αi＝γei可以看出，支持值正比于這點(diǎn)的錯(cuò)誤值，所有訓(xùn)練樣本的α均不為零。為了讓LSSVM重新獲得稀疏性［8］，基于電子間庫(kù)侖力（coulomb force）的物理模型思想提出一種篩選支持向量的樣本縮減策略（CF?LSSVM），使得LSSVM具備一定的稀疏性。

1.1 基本原理

物理學(xué)中的電子之間有同號(hào)電荷相互排斥，異號(hào)電荷相互吸引的性質(zhì)，作用力的方向在它們的連線上；本文則以兩類別中心連線的中垂線作為分類超平面的近似，篩選出更靠近此中垂線的訓(xùn)練樣本。

如圖1所示，在庫(kù)倫力模型中，由每個(gè)訓(xùn)練樣本受到同類樣本中心的斥力及異類樣本中心的引力之和大小及方向的不同，即可篩選出那些對(duì)分類超平面的構(gòu)建貢獻(xiàn)度高的樣本，即準(zhǔn)支持向量。那些靠近分類超平面的訓(xùn)練樣本將會(huì)受到同類樣本中心的斥力，以及異類樣本中心的引力，因而具有一個(gè)向分類超平面移動(dòng)的趨勢(shì)；而那些距離分類超平面很遠(yuǎn)的訓(xùn)練樣本將會(huì)受到兩類樣本中心的庫(kù)侖力之和使之遠(yuǎn)離分類超平面。

圖1 庫(kù)倫力篩選策略示意圖Fig.1 Diagram of Coulomb Force screening strategy

由于庫(kù)倫力是一個(gè)矢量，任意兩點(diǎn)間的庫(kù)倫力的方向在兩點(diǎn)連線上，因此對(duì)于大量的訓(xùn)練樣本會(huì)獲得大量不同方向的庫(kù)倫力，但是無(wú)法直接從這些帶有方向的庫(kù)侖力中比較出哪些訓(xùn)練樣本是更靠近分類超平面的準(zhǔn)支持向量，而更關(guān)心的是訓(xùn)練樣本點(diǎn)受到的庫(kù)倫力在垂直分類超平面方向上的分量。但分類超平面的法向量是未知的，因此利用兩類樣本的中心點(diǎn)連線近似為分類面的法線方向。求得訓(xùn)練樣本所受斥力、引力之后，向兩類樣本中心點(diǎn)連線方向投影，得到該力的水平分量。在本文中將一個(gè)樣本點(diǎn)的斥力水平分量與引力水平分量的加權(quán)和作為判斷其是否能成為準(zhǔn)支持向量的貢獻(xiàn)值。貢獻(xiàn)值越大的，就越具備成為準(zhǔn)支持向量的條件，反之同理。根據(jù)貢獻(xiàn)值確定出準(zhǔn)支持向量集，從而訓(xùn)練最終的分類模型。

1.2 庫(kù)侖力模型

以二分類［9?10］問(wèn)題為例，對(duì)于在低維空間中線性不可分的問(wèn)題，庫(kù)倫力縮減策略中也相應(yīng)采用核函數(shù)，經(jīng)過(guò)非線性映射后正類和負(fù)類樣本中心分別為

兩類樣本的基準(zhǔn)特征方向的計(jì)算由式（1）和（2）得出：

式中的非線性映射函數(shù)的具體公式形式并不知道，因此無(wú)法直接獲得類別中心以及基準(zhǔn)特征方向的值。但由式（1）～（4）可知，利用貢獻(xiàn)值可轉(zhuǎn)換為向量?jī)?nèi)積表達(dá)式，故可通過(guò)核函數(shù)計(jì)算出最終結(jié)果。正類非線性斥力得分計(jì)算公式、負(fù)類非線性斥力得分計(jì)算公式、正類非線性引力得分計(jì)算公式、負(fù)類非線性引力得分計(jì)算公式依次為式（5）～（8）。

通過(guò)分別計(jì)算CV＝α·RFS+β·AFS便可以得到訓(xùn)練樣本在LSSVM分類器分類過(guò)程中對(duì)于分類超平面的決策貢獻(xiàn)度的排序，在應(yīng)用過(guò)程中根據(jù)實(shí)際情況需要，可以對(duì)分類精度與分類時(shí)間進(jìn)行權(quán)衡，選擇針對(duì)不同情況下的最佳性能分類器。

2 結(jié)合空間信息的分類模型

支持向量機(jī)在高光譜遙感圖像高維數(shù)據(jù)的分類中表現(xiàn)出良好的性能，然而常規(guī)的分類方法都主要關(guān)注單個(gè)像元光譜信息的挖掘，而沒(méi)有最大限度結(jié)合空間相關(guān)信息以此提高分類器的可靠性。MRF是一種將空間相關(guān)性整合到圖像分類中的概率模型［11］，早已在各個(gè)領(lǐng)域中得到廣泛關(guān)注。大量文獻(xiàn)中對(duì)MRF在圖像分類中如何發(fā)揮最佳效果都進(jìn)行了深入的研究，尤其在文獻(xiàn)［12?14］中，將支持向量機(jī)技術(shù)與MRF框架結(jié)合，提高遙感圖像分類精度。在這些文獻(xiàn)中，都用支持向量機(jī)分類結(jié)果估計(jì)類條件概率密度函數(shù)，并用MRF根據(jù)空間相關(guān)性對(duì)類別先驗(yàn)概率做出估計(jì)，在最大后驗(yàn)概率準(zhǔn)則（maximum a posterior，MAP）下進(jìn)行判決，并獲得良好的實(shí)驗(yàn)效果。本文將所提出的縮減分類器CF?LSSVM?MRF與基于MRF空譜分類模型結(jié)合，在提高分類速度的同時(shí)使分類精度得到顯著提高。實(shí)驗(yàn)證明本文方法與未結(jié)合空間信息的模型相比，前者效果更理想。

MRF在圖像分割［15］過(guò)程中，可以通過(guò)K均值距離分類法得到圖像的一種分類結(jié)果，并由此結(jié)果得到條件概率與標(biāo)號(hào)場(chǎng)所得X的聯(lián)合概率分布的乘積，以最大后驗(yàn)概率準(zhǔn)則作為判決標(biāo)準(zhǔn)，將最終概率乘積最大的類別作為未知樣本的標(biāo)號(hào)。借助MRF的原理，將樣本縮減后的LSSVM一對(duì)一多類分類器所得的概率形式分類結(jié)果與MRF的標(biāo)號(hào)場(chǎng)模型相結(jié)合，建立光譜信息與空間信息相結(jié)合的分類器模型，在縮短分類時(shí)間的基礎(chǔ)上大大提高分類精度。

由MRF的性質(zhì)可知，中心像元的類別標(biāo)號(hào)只與其鄰域系統(tǒng)中的像元類別標(biāo)號(hào)有關(guān)，因此可以通過(guò)中心像元的鄰域系統(tǒng)內(nèi)各個(gè)像元的類別標(biāo)號(hào)求出中心像元所屬類別的先驗(yàn)概率P x()。由地物分布的相關(guān)特性，可以在原有分類器分類結(jié)果的基礎(chǔ)上，通過(guò)對(duì)空間相關(guān)性進(jìn)行計(jì)算，計(jì)算結(jié)果作為決定標(biāo)號(hào)的重要參考。在大量文獻(xiàn)中都對(duì)結(jié)合空間相關(guān)性的方法的分類效果進(jìn)行論證，均對(duì)分類精度有改進(jìn)的效果。本文根據(jù)MRF原理，利用MRF對(duì)標(biāo)號(hào)場(chǎng)先驗(yàn)概率的估計(jì)模型，提出一種空譜結(jié)合的分類器模型。該模型主要分為兩部分，首先通過(guò)CF?LSSVM?MRF對(duì)未知數(shù)據(jù)進(jìn)行分類，通過(guò)1?a?1型多分類結(jié)構(gòu)通過(guò)投票得到各個(gè)分類結(jié)果對(duì)應(yīng)的概率。假設(shè)共有N類待分類地物，則應(yīng)該建立N（N-1）／2個(gè)一對(duì)一分類器，得到后驗(yàn)概率的形式為

式中：Pij（i｜X）的取值為0或者1。

式中：C為類別標(biāo)號(hào)，i為X鄰域系統(tǒng)中的某像元，本文采用8-鄰域系統(tǒng)，因此i＝1，2，…，8。由式（10）可以求得X的類別標(biāo)號(hào)取遍所有類別的每個(gè)引力勢(shì)能的值。在8-鄰域系統(tǒng)中的8個(gè)像元，由于相對(duì)位置的關(guān)系不同，可以分為2類。分別是與中心像元直接相鄰的4個(gè)像元，另一類是與中心像元對(duì)角相鄰的4個(gè)像元。由于這2類像元相對(duì)中心像元空間位置關(guān)系的不同，對(duì)于中心像元標(biāo)號(hào)的影響也是不同的，因此模型中引入各個(gè)像元與中心像元的歐式距離作為影響因子：

由支持向量機(jī)軟分類結(jié)果得到fc（xi），與引力勢(shì)能進(jìn)行線性加權(quán)可以得到空間相關(guān)性的分類模型：

3 實(shí)驗(yàn)仿真

本文涉及的仿真實(shí)驗(yàn)的硬件運(yùn)行環(huán)境是CPU為Intel Core 2，2.00GHz，內(nèi)存2GB的PC機(jī)；軟件環(huán)境是：Window 7操作系統(tǒng)，仿真平臺(tái)為Matlab 2010a。實(shí)驗(yàn)中，原始的LSSVM，利用庫(kù)侖力精簡(jiǎn)訓(xùn)練樣本的CF?LSSVM，利用承載空譜間信息的MRF的LSSVM?MRF，以及同時(shí)利用庫(kù)侖力和MRF的CF?LSSVM?MRF 4種方法來(lái)進(jìn)行比較來(lái)驗(yàn)證所提出方法的有效性。

第1組實(shí)驗(yàn)采用Pavia大學(xué)高光譜數(shù)據(jù)中的2類進(jìn)行二分類仿真。2類地物分別選取Asphalt、Bricks，由地物監(jiān)督圖可以看出，這2種地物分布覆蓋范圍比較廣，且較為分散，并不是同類地物集中分布，各類別地物的細(xì)節(jié)信息較豐富，因此選擇這2種地物進(jìn)行分類實(shí)驗(yàn)，驗(yàn)證本文方法在這種特征的高光譜圖像分類中的表現(xiàn)。各種分類模型所取得的分類精度如表1所示。CF?LSSVM分類模型的分類精度與LSSVM相差不大，而分類時(shí)間則由32.15 s降至1.61 s；CF?LSSVM?MRF分類模型較之LSSVM分類精度有較大提高，在分類時(shí)間上則與CF?LSSVM基本持平。可見，空譜結(jié)合模型CF?LSSVM?MRF較之基本的LSSVM模型不但提高了分類精度，也大量節(jié)省了推廣階段的分類時(shí)間。

表1 Pavia University二分類模型性能對(duì)比Table 1 Performance comparison of two?classification model for Pavia University data set

第2組實(shí)驗(yàn)采用印第安農(nóng)林?jǐn)?shù)據(jù)驗(yàn)證算法性能，在仿真實(shí)驗(yàn)中LSSVM采用性能較好的高斯徑向基核函數(shù)進(jìn)行非線性分類，其中核函數(shù)中σ取值0.9，γ為1 000。本章中均采用1?a?1型多分類結(jié)構(gòu)。實(shí)驗(yàn)主要通過(guò)高光譜數(shù)據(jù)分類對(duì)比了原始LSSVM分類法，本文提出的CF?LSSVM?MRF分類法以及本章提出的空譜結(jié)合分類器在各類別分類精度，整體分類精度以及Kappa系數(shù)的對(duì)比，圖2為經(jīng)各方法分類后的地物分布效果圖。

圖2 4種分類方法效果圖Fig.2 Classification results of four methods

由圖2可以直觀的看出，在融合空間信息后的分類器的分類效果得到明顯提高，這種新型的分類模型有效避免類別內(nèi)部像素點(diǎn)的錯(cuò)分情況，使分類結(jié)果具有更強(qiáng)的完整性，尤其適用于區(qū)域面積較大的地物目標(biāo)。由表2的具體各類別分類精度可以看出，結(jié)合空間信息的分類模型具有更高的分類準(zhǔn)確度；同時(shí)，分類時(shí)間統(tǒng)計(jì)表明，樣本縮減模型較之未縮減模型所耗時(shí)間明顯減少。

表2 India Pine 4種分類模型性能對(duì)比Table 2 Performance comparison of four kinds of classification models for India Pine data set

4 結(jié)束語(yǔ)

本文提出一種基于庫(kù)侖力的LSSVM樣本縮減策略，該方法將物理學(xué)中帶電粒子間引力的模型引入到對(duì)于訓(xùn)練樣本空間位置關(guān)系的計(jì)算當(dāng)中，并通過(guò)設(shè)置標(biāo)準(zhǔn)特征方向，由矢量投影方式對(duì)計(jì)算進(jìn)行簡(jiǎn)化，實(shí)驗(yàn)證明本方法可以在精度要求范圍內(nèi)提升判別新樣本的速度，提高了LSSVM的推廣能力。在樣本縮減分類器模型的基礎(chǔ)上，提出一種融合了光譜信息以及空間相關(guān)性的新型分類器，該分類器把樣本縮減了的LSSVM與MRF理論相結(jié)合，顯著提高了分類器分類精度。從理論分析和實(shí)驗(yàn)評(píng)價(jià)方面均顯示出本文提出方法的可行性和有效性。

［1］BRUZZONE L，MARCONCINI M.Toward the automatic up?dating of land?cover maps by a domain?adaptation SVM clas?sifier and a circular validation strategy［J］.IEEE Trans Geosci Remote Sens，2009，47（4）：1108?1122.

［2］DEMIR B，ERTURK S.Clustering?based extraction of bor?der training patterns for accurate SVM classification of hy?perspectral images［J］.IEEE Geosci Remote Sens Lett，2009，6（4）：840?844.

［3］王立國(guó)，王群明，劉丹鳳，等.基于幾何估計(jì)的光譜解混方法［J］.紅外與毫米波學(xué)報(bào)，2013，32（1）：56?61.WANG Liguo，WANG Qunming，LIU Danfeng，et al.Geo?metric estimation method of spectral unmixing［J］.Journal of Infrared and Millimeter Waves，2013，32（1）：56?61

［4］MATHUR A，F(xiàn)OOFY G M.Crop classification by a SVM with intelligently selected training data for an operational ap?plication［J］.International Journal of Remote Sensing，2008，29（8）：2227?2240.

［5］HUANG C，DAVIS L S，TOWNSHEND J R G.An assess?ment of support vector machines for land cover classification［J］.Int J Remote Sens，2002，23（4）：725?749.

［6］SUYKENS J A K，BRABANTER J D，LUKAS L，et al.Weighted least squares support vector machines［J］.Neuro?computing，2002，48（1／4）：85?105.

［7］SUYKENS J A K，LUKAS L，VANDEWALLE J.Sparse ap?proximation using least squares support vector machines［J］.IEEE International Symposium on Circuits and Systems，2000，2：757?760.

［8］吳宗亮，竇衡.一種新的最小二乘支持向量機(jī)稀疏化算法［J］.計(jì)算機(jī)應(yīng)用，2009，29（6）：1559?1562.WU Zongliang，DOU Heng.New sparse least squares sup?port vector machine algorithm［J］.Journal of Computer Ap?plications，2009，29（6）：1559?1562.

［9］HSU C W，LIN C J.A comparison of methods for multi?class support vector machines［J］.IEEE Trans Neural Netw，2002，13（2）：415?425.

［10］PLATT J C，CRISTIANINI N，SHAWE-TAYLOR J.Large margin DAGs for multiclass classification［J］.Proc Adv Neural Inf Process Syst，2000，12（6）：547?553.

［11］VERHOEYE J，de WULF R R.Land?cover mapping at sub?pixel scales using linear optimization techniques［J］.Remote Sensing of Environment，2002，79（1）：96?104.

［12］FARAG A A，MOHAMED R M，EL-BAZ A.A unified framework for map estimation in remote sensing image seg?mentation［J］.IEEE Trans Geosci Remote Sensing，2005，43（7）：1617?1634.

［13］BOVOLO F，BRUZZONE L.A context?sensitive technique based on support vector machines for image classification［M］.Berlin：Pattern Recognition and Machine Intelli?gence，2005：260?265.

［14］GONG Peng，KELLY M，LIU Desheng.A spatial?temporal approach to monitoring forest disease spread using multi?temporal high spatial resolution imagery［J］.Remote Se?ning of Environment，2006，101（2）：167?180.

［15］鄭瑋.基于模糊馬爾科夫隨機(jī)場(chǎng)的遙感圖像分割算法研究［D］.成都：電子科技大學(xué)，2007：28?35.ZHENG Wei.Research on remote sensing image segmenta?tion algorithms based on fuzzy Markov random field［D］.Chengdu：University of Electronic Science and Technology of China，2007：28?35.

Two improvements for least squares support vector machines

WANG Liguo，ZHAO Liang，SHI Yao，LU Tingting

（College of Information and Communication Engineering，Harbin Engineering University，Harbin 150001，China）

The least squares support vector machine（LSSVM）has been widely used due to its better performance.However，LSSVM still has two deficiencies.On the one hand，it sacrifices the speed in the generalization process because it treats all the training samples as the support vector set to participate in classification of unknown samples.On the other hand，LSSVM mainly uses spectral data for training and classification，and it ignores mining on the spatial information of a terrestrial object，which influences classification precision.Therefore，a sample reduction strategy based on the Coulomb gravity model is proposed.And on this basis，a new classifier model which merges the above classification result with the classifier based on spatial information can solve the two problems mentioned above.Experimental results indicate that this new classifier performs better than the standard LSSVM both in classi?fication accuracy and speed.

hyperspectral；support vector machine（SVM）；sample reduction；Markov random field（MRF）；spa?tial information

10.3969／j.issn.1006?7043.201404078

TP753

：A

：1006?7043（2015）06?0847?05

http：／／www.cnki.net／kcms／detail／23.1390.u.20150428.1118.022.html

2014?04?25.網(wǎng)絡(luò)出版時(shí)間：2015?04?28.

國(guó)家自然科學(xué)基金資助項(xiàng)目（61275010）；國(guó)家教育部博士點(diǎn)基金資助項(xiàng)目（20132304110007）；黑龍江省自然科學(xué)基金資助項(xiàng)目（F201409）；中央高校基本科研業(yè)務(wù)費(fèi)重大資助項(xiàng)目（HEUCFD1410）.

王立國(guó)（1974?），男，教授，博士生導(dǎo)師.

王立國(guó)，E?mail：wangliguo＠hrbeu.edu.cn.