一種基于ＳＶＭ新的學習方法及應用

摘要：該文提出一種基于支持向量機的組合核函數的學習方法，它首先由遺傳算法作為新的學習方法得到訓練，組合核函數的權值在學習過程中被確定，并在決策模型的分類階段用來作為參數。這種學習方法被應用在兩個關于癌癥診斷的公用數據集中，從而獲得分類最優超平面。通過實驗，這種學習方法顯示出比用單一核函數具有較好的性能。

關鍵詞：支持向量機；組合核函數；遺傳算法

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)33-1474-02

A New Method for Support Vector Machine and Application

XIA Yong-jun

(Lanzhou Jiaotong University， Department of Electronics and Information Engineering， Lanzhou 730070， China)

Abstract: This paper proposes a unified kernel function for support vector machine， which are trained by a new learning method based on genetic algorithm. The weights of basis kernel functions in the unified kernel are determined in learning phase and used as the parameters in the decision model in the classification phase. The unified kernel and the learning method were applied to obtain the optimal decision model for the classification of two public data sets for diagnosis of cancer diseases. The experiment showed fast convergence and greater flexibility than other kernel functions.

Key words: SVM; unified kernel function; GA

1 引言

支持向量機(Support Vector Machine，SVM) 是在統計學習理論基礎上發展起來的一種新的機器學習方法，已成為目前研究的熱點，并在模式識別、分類、回歸等領域有著很好的應用。遺傳算法是基于對自然界中生物的遺傳和進化機理進行模擬而到的一種智能算法。算法流程主要模仿的是生物遺傳進化過程中的選擇、交叉、和變異操作，從而完成對問題最優解的自適應過程。近年來，SVM和GA的結合與應用越來越受到人們的關注[5]。它在與癌癥疾病診斷相關的分類問題中顯示了較好的性能。

2 支持向量機(SVM)

支持向量機作為一種通用的學習方法首先由Vapnic等人提出來，并在實際應用中顯示出越來越多的優越性能。支持向量機[1]主要思想是通過某種事先選擇的非線性映射將輸入向量x映射到一個高維特征空間Z，并在此空間中構造最優超平面。在最簡單的線性模型中，一個SVM就是這樣一個超平面，它使得正例和反例之間的分類間隔最大化。所謂的分類間隔即一群正例樣本與反例樣本之間的距離。從而構造的線性函數為：

y=w#8226;x-b（1）

這里w是基于超平面的普通向量，x是一個輸入向量。其中分離超平面即y=0的平面和與超平面具有相等距離的兩個平行面。

H1:y= w#8226;x-b=+1， H2:y= w#8226;x-b=-1 （2）

這樣，分類間隔M被定義為：■ （3）

若想將兩類樣本無錯誤地分開且使兩類樣本的分類間隔最大，則可通過求解最小化 來實現，這是一個典型的非線性問題的不等式約束。可以通過設置Lagrange函數的鞍點來解決此最優化問題，最優解即為下面的Lagrange函數的鞍點：

■ （4）

式中αi是Lagrange乘子，且αi≥0。

不過，線性學習機[7]計算能力的限制在19世紀60年代有Minsky和Papert提出來。它可以很容易的認識到，在現實世界的應用需要比線性函數更加廣泛和靈活的假設空間。但是這種限制可通過多層神經網絡得以解決。核函數還提供了另一種解決辦法，即由預測數據轉換為髙維特征空間，以增加線性學習機的計算能力。對于非線性問題，可以通過選用合適的核函數由線性變換轉化到某個高維特征空間來實現。核函數的優點之一是能得到應用領域并能簡單的編碼到合適的核函數的特征空間。

3 遺傳算法(GA)

遺傳算法[2](GA)是一個優化算法機理上的自然演變程序。大多數遺傳算法都有一個基于自然界的生物遺傳進化機理而演化出的一種自適應優化程序。通過選擇、交叉、變異操作，并能再生產，來完成對問題的最優解的自適應搜索過程。GA通常應用在具有較大搜索空間問題。它和其它隨機搜索算法有所不同，已經被證實比直接搜索方法具有更好的魯棒性。

4 組合核函數的提出及訓練學習方法

4.1 組合核函數的提出

一個核函數在支持向量機中提供了一個靈活而有效的學習機制，可是核函數的選擇受到先驗知識的影響。對我們來說，通過挖掘先知模型來獲得合適的核函數通常是很困難的。并且如何通過給定的數據集去選擇最好的核函數已成為公開的問題。但是，在實際應用中通常沒有優越的核函數，因為核函數的性能常依賴于具體的應用實例。

在本文中，我們設想把一系列加權基本核函數的線性組合定義為一個組合的核函數。它的公式表示如下：

■ （5）

其中βi∈[0，1]，i=1，…，m，■βi=1，Ki，i=1，…，m是一系列基本核函數。

下面是我們在學習試驗中用到的核函數[3，4]：

① 多項式核函數：K(x，xi)=[(x#8226;xi)+1]p

② 徑向基核函數：■

③ Sigmoid內積函數：K(x，xi)=S(u(x#8226;xi)+c)

以上核函數用來構造組合核函數。它們已經被Mercer理論證明。為了使得到的組合核函數更好的應用于一個訓練數據集，βi起著非常重要的作用。

在學習階段，訓練樣本空間的結構通過組合核函數進行學習。GA技術的引入是為了獲得較優的公用的βi，使得分類的錯誤率達到最小。在學習階段后期，我們得到一個較好的決策模型。

4.2 訓練學習方法介紹

訓練學習方法的過程描述如下：

第一步：在預測階段，通過特征選擇方法降低在特征空間的維數。這樣，許多癌癥病例和普通模式組成的訓練集和測試集在學習階段被選擇并通過。

第二步：在學習階段，我們把基于GA和SVM學習方法應用于獲得分類的最優決策模型。

第三步：為了在分類過程中對于新樣本更好的分類，把在學習過程中獲得最優決策模型應用在SVM上。并且該模型的性能優于測試樣本。

具體模型表示如圖1。

5 實驗分析及驗證

1） 在本節中，我們給出分類后的結果。實驗過程中，我們用到兩個非常著名的公用數據集，Leukemia數據集和Colon癌癥數據集，通過基于組合核函數的新的學習方法進行分類。最后用具有組合核函數分類模型的性能與其它核函數逐一做了比較。

2） Colon 癌癥數據集

Colon癌癥數據由22個正常組織樣本和40個癌癥樣本組成。并且每個樣本具有2000個特征。隨機選擇42個樣本作為訓練集，余下的樣本作為測試集。我們選擇前50個特征做靜態試驗。發現用組合核函數方法比用其它核函數顯示出更好的穩定性和較高的精確度。結果如下表1所示：

表1 靜態試驗結果

5.3 Leukemia 數據集

Leukermia數據集包含72個樣本，這些樣本被分成兩類，Acute Myeloid Leukermia (AML)和Acute Lymphoblastic Leukermia (ALL).每個樣本具有7129個特征。用38個樣本作為訓練（27個ALL和11個AML），34個用作測試（20個ALL和14個AML）。與在Colon數據集上一樣，我們選擇50個特征試驗。同樣顯示出用組合核函數方法的優越性。試驗結果如下表2：

表2 試驗結果

6 結論

在本論文中，我們提出用基于SVM組合核函數的思想的新的學習方法。利用GA技術獲得分類的最優決策模型。組合核函數在從一個特征空間映射到另一個新的特征空間的過程中起著十分重要的作用，并提高了SVM分類器的性能。通過與其它三種核函數進行比較，組合核函數在分類過程中獲得較高和較穩定的精確性。這樣，我們的核函數比其它的核函數在解決問題空間中顯示更靈活的性能。

參考文獻：

[1] 張學工.統計學習理論的本質[M].北京:清華大學出版社，2000.

[2] 高雋.智能信息處理方法導論[M].北京:機械工業出版社，2004.

[3] Cristianini N， Shawe-Taylor J. An introduction to Support Vector Machines and other kernel-based learning methods[J].Cambridge，2000.

[4] Cristianini N， Shawe-Taylor J.支持向量機導論[M].北京:電子工業出版社，2004.

[5] Goldberg D E. Genetic Algorithms in Search， Optimization Machine Learning[M].Adison Wesley，1989.

[6] Furey T S， Cristianini N， Duffy N， et al. Support vector machine classification and validation of cancer tissue samples using microarray expression data[J]. Bioinformatics，2000，16(10):906-914.

[7] Minsky M L， Papert S A.Perceptrons[M]. MIT Press，1969.

注：“本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文。”