一種改進的支持向量機及其在圖像分割中的應用

劉 琦，趙彥暉

（西安建筑科技大學，陜西西安 710055）

一種改進的支持向量機及其在圖像分割中的應用

劉 琦，趙彥暉

（西安建筑科技大學，陜西西安 710055）

支持向量機方法在解決小樣本，非線性及高維模式識別中表現出許多特有的優勢。目前主要用于二元分類問題中，而對于其在多類分類應用仍是一個值得研究的問題。在目前存在的各種多類支持向量機分類問題中，一對一方法是一種最符合實際的方法。文章提出了一種改進的支持向量機，并將其應用于圖像分割。這種改進的支持向量機它對一對一方法進行了改進，實驗表明，支持向量機的方法是一種很有潛力的圖像分割技術。

支持向量機;距離;決策函數;一對一;分類器

1 前言

支持向量機是一種基于統計學理論的機器學習的新方法，它的理論基礎是統計學理論的VC理論和結構風險的最小化準則，其是由 Corinne Cortes和Vapnik［1］等于1995年首先提出來的，它在解決小樣本，非線性及高維模式識別中表現出許多特有的優勢，并能夠推廣應用到函數擬合等其他機器學習問題中，相比較于傳統的方法，支持向量機具有以下優點: （1）專門針對于有限樣本的情況，（2）使用了核函數，將原問題通過隱形非線性變換轉換到高維的特征空間，在高維空間中構造線性決策函數來實現原空間中的非線性決策函數，（3）SVM的解也具有稀疏性。

近年來，國內外對于SVM的研究發展迅速，以Suykell為代表的研究團隊提出了用于分類的最小二乘支持向量機;用于支持向量機泛化能力的理論分析的概念——支持向量數據域描述（Support vector data，Discriptill，SVDD）思想，提出了只針對于某個單類問題進行學習的單分類支持向量機，這種方法使得訓練樣本大大的減少了，使得學習時間也隨之減少，但它使得整體的泛化能力下降。

本文旨在構造一種改進的支持向量機，并將其應用到圖像分割中，因而本文所研究的主要內容可分為兩個板塊:其一為對現有的支持向量機進行改進，提出一種改進的向量機;其二，利用改進的支持向量機進行圖像分割。

2 改進的支持向量機

支持向量機在解決二元分類問題上具有很好的泛化能力，但是它在多類分類問題上的應用依然是一個值得研究的問題。很多應用支持向量機解決多類分類問題的方法被提出，例如:一對一方法，一對多方法，以及有向無環圖方法。解決多類分類問題關鍵是要求分類的數目要與變量的數目相適應，因而在相同數據的計算上，較二元問題，它在時間上的花費要多得多。對于類的分類問題，一對多的方法構造了個分類器（這個分類器的構造是利用訓練集的數據）。一對一方法構造了k（k－1）/2分類器（這些分類器的構造是通過使用從個分類中選出的兩類的訓練數據來構造的），雖然它需要構建的分類器數量較多，但他的訓練時間大大低于其它的方法。有向無環圖也利用了k（k－1）/2分類器。然而，它在訓練時間上遠不及一對一方法的。Hsn和Lin通過比較上述方法的的表現方式以及計算耗時，對上述方法進行了比較，他們認為在訓練時間上沒有任何方法能比得上一對一的方法，也沒有任何方法比一對一的方法更具有泛化能力。因而，一對一方法相比較于其他方法更符合實際問題。近年來，Lee和Lin提出了一種多目標分類的支持向量機，該種支持向量機被認為是二元問題向多類問題應用的一個很好的推廣。正如在二元問題中一樣，他們在多類問題中應用了貝葉斯定理，但是它面臨著使得數據的計算問題變得更為復雜。

一對一方法在類訓練樣本中構造所有可能的兩類分類器，分類決策采用了投票策略（即“最大得分理論”），它每個分類器僅僅在類中的兩類訓練樣本上訓練，結果構造k（k－1）/2個分類器，雖然它需要構建的分類器數量較多，但在實際應用中使用最好，但該種方法最大的缺點就是它也存在不可分域，為此，Abel等人，對一對一方法進行了改進，提出了多類分類的模糊支持向量機，對于位于不可分域中的向量采用了最小算子其隸屬度決定其類別。

圖1 一對一不可分區域的解決策略

眾所周知，在分類問題中，距離是一種最簡單，最直觀的分類測度，基于這樣的考慮，提出了一種改進的一對一的方法，實現過程如下:

針對多類分割問題，當向量位于不可分割區域時，計算其到所有兩類超平面的距離:

所對應的分類超平面為

決策函數為

為了驗證改進方法的有效性，該方法在UCI標準數據庫［8］的iris以及vehicle以及wine數據上進行了實驗，并將是分類性能與一對一方法以及Abe等人改進的方法進行了比較，試驗中，將樣本一分為二，一半用于訓練，一半用于測試，核函數采用了二階的多項式核函數

此時的支持向量機是一個含有階多項式的分類器。

表1為幾種方法的分類性能比較結果，從表1中可以知道，本文改進的方法可以獲得與Abe等人改進方法相比較，此法比較簡單實用。同時本文的方法還是不可分區域進行了劃分，如圖2。

圖2 一對一方法對不可分區域的劃分

表1 幾種一對一方法分類性能的比較

3 圖像分割實驗

為了評價SVM方法對于圖像分割的性能，本文以2010年研究生建模競賽A題的中瘤基因癌變圖為例，進行了分割實驗。該圖像具有邊界模糊，目標灰度不明確以及不連續的特點，選擇它主要是為了增加分割的全面性和客觀性。

實驗過程步驟如下:

（1）對所有數據進行提取，然后對其進行歸一化處理形成SVM的輸入向量。

（2）將實驗數據一分為二，一部分作為訓練數集，一部分作為測試數集。

（3）將訓練數據分到所有的二元子集中，利用前面所給出的距離計算所有的分類間的距離。

（4）構造第i個分類的界，實現過程如下:讓j作為第i個分類的有序元素，如果j是第i個分類的第一個元素，且對于第i個分類來講，沒有一個分類器被它所構造，則應用SVM去分類與j。如果j不是第個i分類的第一個元素，且對于第i個分類來講，沒有一個分類器被i與j所構造，且分類i與其它分類所構造分類器不能把i與j區分出來，則應用SVM去分類i與j。檢查第個分類所有的以及在需要的情況下應用SVM去分類i與j。

（5）對于所有的分類應用上述的第3步的方法，進而得到分類方式。

（6）將所得結果應用在測試數集上。

實驗中，選擇核函數為k（x，xi）=［（x*xi）+ 1］d，其中d=3。

如圖3，圖像被成功的分割。因而對于一些目標邊界模糊，目標灰度不明確的圖形分割，SVM是一種很好的選擇。

圖3 實驗前后的圖像對比

4 結語

本文提出了一種改進的支持向量機，這種支持向量機是建立在對于多類分類支持向量機方法的研究上的。通過大量的實驗將其和一對一方法，還有Abel等人提出的方法進行了比較。同時還其應用于圖像分割中。實驗的結果表明，本文提出的改進的支持向量機具有很好的實際效用，同時對于圖像分割的處理SVM是一種很好的方法，它有著較好的前景。

［1］ V.N.Vapnik.統計學習理論的本質［M］.張學工，譯.北京:清華大學出版社，2000.

［2］ Welcome to the UC Irvine Machine Learning Repository!［EB/OL］.www.ics.uci.edu/～mlearn/MLRepostitory.html.

［3］ 岳振軍，邱望成，劉春林.一種自適應的多目標圖像分割方法［J］.中國圖像圖形學報，2004，9（6）:674－678.

［4］ C.W.Hsu，C.J.Lin.A comparison of methods for multiclass support vector machines［J］.IEEE Transactions on Neural Network，2002，13（2）:415－425.

［5］ J.Weston，C.Watkins.Multi-class support vector machines［R］.CSD-TR-98-04，1998:1－9.

［6］ J.C.Platt，N.Cristianini，T.J.Shawe.Largemargin DAGs for Multiclass classification［J］.In advances in Neural Information Processing Systems，MIT Press，2000（12）: 547－553.

［7］ Hsu C-W，Lin C-J.A comparison of methods for Multiclass support vector machines.IEEE Trans Networks［J］.2002（13）:415－425.

An Im proved Support Vector Machine and Its Application in Image Segmentation

LIU Qi，ZHAO Yan－hui
（Xi’anUniversityofArchitectureandTechnology，Xi’an710055，China）

Support vector machine is a statistical theory based on the new machine learning method;it addresses the Small Sample，Nonlinear and High Dimensional Pattern Recognition performance of the many unique advantages.At present it is mainly used for binary classification problems，and for its application in multi-class classification is still a problem worthy of study.In a variety of existing multi-class support vector machine classification problem，one-against-one is one of the most realistic approaches.This paper presents an improved support vector machines and applied it to image segmentation.This improved method of support vector machines is one of the improvements of one-against－one，experiments show that support vector machine approach is a promising image segmentation technique.

support vector machine;distance;decision function;one-against-one;classifier

G43

A

1671－1491（2012）02－0015－03

2012－01－04

劉 琦（1986－），男，陜西西安人，西安建筑科技大學在讀碩士研究生，從事概率統計應用研究。

（責編:王玉琴）