劉 琦，趙彥暉

（西安建筑科技大學(xué)，陜西西安 710055）

一種改進(jìn)的支持向量機(jī)及其在圖像分割中的應(yīng)用

劉 琦，趙彥暉

（西安建筑科技大學(xué)，陜西西安 710055）

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

支持向量機(jī);距離;決策函數(shù);一對一;分類器

1 前言

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

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

本文旨在構(gòu)造一種改進(jìn)的支持向量機(jī)，并將其應(yīng)用到圖像分割中，因而本文所研究的主要內(nèi)容可分為兩個板塊:其一為對現(xiàn)有的支持向量機(jī)進(jìn)行改進(jìn)，提出一種改進(jìn)的向量機(jī);其二，利用改進(jìn)的支持向量機(jī)進(jìn)行圖像分割。

2 改進(jìn)的支持向量機(jī)

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

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

圖1 一對一不可分區(qū)域的解決策略

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

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

所對應(yīng)的分類超平面為

決策函數(shù)為

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

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

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

圖2 一對一方法對不可分區(qū)域的劃分

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

3 圖像分割實驗

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

實驗過程步驟如下:

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

（2）將實驗數(shù)據(jù)一分為二，一部分作為訓(xùn)練數(shù)集，一部分作為測試數(shù)集。

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

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

（5）對于所有的分類應(yīng)用上述的第3步的方法，進(jìn)而得到分類方式。

（6）將所得結(jié)果應(yīng)用在測試數(shù)集上。

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

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

圖3 實驗前后的圖像對比

4 結(jié)語

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

［1］ V.N.Vapnik.統(tǒng)計學(xué)習(xí)理論的本質(zhì)［M］.張學(xué)工，譯.北京:清華大學(xué)出版社，2000.

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

［3］ 岳振軍，邱望成，劉春林.一種自適應(yīng)的多目標(biāo)圖像分割方法［J］.中國圖像圖形學(xué)報，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－h(huán)ui
（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－），男，陜西西安人，西安建筑科技大學(xué)在讀碩士研究生，從事概率統(tǒng)計應(yīng)用研究。

（責(zé)編:王玉琴）