最小二乘支持向量機的兩點改進

王立國，趙亮，石瑤，路婷婷

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

最小二乘支持向量機的兩點改進

王立國，趙亮，石瑤，路婷婷

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

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

高光譜；支持向量機；樣本縮減；馬爾科夫隨機場；空間信息

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

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

1 庫倫力縮減策略

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

1.1 基本原理

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

如圖1所示，在庫倫力模型中，由每個訓練樣本受到同類樣本中心的斥力及異類樣本中心的引力之和大小及方向的不同，即可篩選出那些對分類超平面的構建貢獻度高的樣本，即準支持向量。那些靠近分類超平面的訓練樣本將會受到同類樣本中心的斥力，以及異類樣本中心的引力，因而具有一個向分類超平面移動的趨勢；而那些距離分類超平面很遠的訓練樣本將會受到兩類樣本中心的庫侖力之和使之遠離分類超平面。

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

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

1.2 庫侖力模型

以二分類［9?10］問題為例，對于在低維空間中線性不可分的問題，庫倫力縮減策略中也相應采用核函數，經過非線性映射后正類和負類樣本中心分別為

兩類樣本的基準特征方向的計算由式（1）和（2）得出：

式中的非線性映射函數的具體公式形式并不知道，因此無法直接獲得類別中心以及基準特征方向的值。但由式（1）～（4）可知，利用貢獻值可轉換為向量內積表達式，故可通過核函數計算出最終結果。正類非線性斥力得分計算公式、負類非線性斥力得分計算公式、正類非線性引力得分計算公式、負類非線性引力得分計算公式依次為式（5）～（8）。

通過分別計算CV＝α·RFS+β·AFS便可以得到訓練樣本在LSSVM分類器分類過程中對于分類超平面的決策貢獻度的排序，在應用過程中根據實際情況需要，可以對分類精度與分類時間進行權衡，選擇針對不同情況下的最佳性能分類器。

2 結合空間信息的分類模型

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

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

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

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

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

由支持向量機軟分類結果得到fc（xi），與引力勢能進行線性加權可以得到空間相關性的分類模型：

3 實驗仿真

本文涉及的仿真實驗的硬件運行環境是CPU為Intel Core 2，2.00GHz，內存2GB的PC機；軟件環境是：Window 7操作系統，仿真平臺為Matlab 2010a。實驗中，原始的LSSVM，利用庫侖力精簡訓練樣本的CF?LSSVM，利用承載空譜間信息的MRF的LSSVM?MRF，以及同時利用庫侖力和MRF的CF?LSSVM?MRF 4種方法來進行比較來驗證所提出方法的有效性。

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

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

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

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

由圖2可以直觀的看出，在融合空間信息后的分類器的分類效果得到明顯提高，這種新型的分類模型有效避免類別內部像素點的錯分情況，使分類結果具有更強的完整性，尤其適用于區域面積較大的地物目標。由表2的具體各類別分類精度可以看出，結合空間信息的分類模型具有更高的分類準確度；同時，分類時間統計表明，樣本縮減模型較之未縮減模型所耗時間明顯減少。

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

4 結束語

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

［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］王立國，王群明，劉丹鳳，等.基于幾何估計的光譜解混方法［J］.紅外與毫米波學報，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，FOOFY 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］.計算機應用，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］鄭瑋.基于模糊馬爾科夫隨機場的遙感圖像分割算法研究［D］.成都：電子科技大學，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.網絡出版時間：2015?04?28.

國家自然科學基金資助項目（61275010）；國家教育部博士點基金資助項目（20132304110007）；黑龍江省自然科學基金資助項目（F201409）；中央高校基本科研業務費重大資助項目（HEUCFD1410）.

王立國（1974?），男，教授，博士生導師.

王立國，E?mail：wangliguo＠hrbeu.edu.cn.