核方法的探討及其應用

摘要：核方法是機器學習中一種新的強有力的學習方法。針對核方法進行了探討，給出了核方法的基本思想和優點。同時，描述了核方法的算法實現并舉例進行了說明。

關鍵詞：核方法；支持向量機；核函數

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)12-20000-00

Research on Kernel Method and its Application

WANG Xiao-ju，LI Yong-hua

(College of Mathematics and Information Science， Northwest Normal University. Lanzhou， Gansu 730070， Chain)

Abstract:kernel method is a new powerful learning approach in many machine learning tasks.In this paper，kernel method is researched in detail，It’s fundamental thoughts and merits are given.And it’s algorithm is described by using simplex method.

Key words:kernel method;support vector machines;kernel function

1 引言

經典統計理論在處理低維數據的分類和估計問題中作出了不平凡的貢獻。但是，它是建立在大數定律基礎上的一種漸近理論，它要求樣本點的數目足夠多，隨著樣本數目的增加需要呈指數地增加計算資源，這就導致了“維數災難”。另外，還要求先假設樣本服從某一具體的分布函數，然后利用樣本數據對分布中的參數進行估計，從而得到分析的目的。但這種參數估計方法隨著數據維數的增加，對樣本點數目的要求呈指數增長。因此，面對大規模多變量的現代數據分析問題，經典統計理論就暴露出這些缺點。在1992年，Vapnik教授對有限樣本下的機器學習問題進行研究逐步形成了統計學習理論，并提出結構風險最小化準則，在此理論基礎上提出支持向量機的概念。

2 支持向量機

支持向量機(Support Vector Machines， SVM)是Vapnik等人提出的一種基于訓練集的新型機器學習方法，它可以自動尋找出對學習結果有重要影響的支持向量，因此能夠成功地處理分類問題，從而達到從大量數據中挖掘出有價值信息的目的，由于支持向量機出色的學習性能，它成為機器學習以及數據挖據算法的研究熱點。處理分類問題的支持向量機稱為支持向量分類機，分類問題就是根據訓練集建立分類模型，求解模型得決策函數，然后利用決策函數對未知類別的數據進行分類，支持向量分類機之所以能取得廣泛而很好的分類效果，主要源于核函數的引進，按照函數的形式支持向量分類機模型分為兩大類：一是線性支持向量分類機模型，二是非線性支持向量分類機模型。線性支持向量分類機模型簡單，它所對應的決策函數是一個超平面，但它卻完全體現了支持向量分類機的工作原理。本文用非線性支持向量分類機模型說明核方法是很重要的，并給出仿真實例來說明核方法的實現方式。

3 核函數

核函數在支持向量機中是至關重要的。核函數的引入極大地提高了學習機器的非線性處理能力，保持了學習機器在高維空間中的內在線性，使得學習容易得到控制。支持向量機通過使用核函數將原空間中的數據隱含地表示在高維特征空間中，訓練了一個線性的分類器，訓練過程不需要知道具體的非線性映射，核函數代替原空間中的內積，將輸入空間的向量 ，通過一個非線性變換 映射到某個高維特征空間中，然后在高維特征空間中進行線性分類，最后映射回到原空間就成為輸入空間中的非線性分類，如圖1所示。

將輸入向量x∈Rn映射到一個Hilbert空間，即：φ1(x)， φ2(x)， …， φn(x)，

根據Hilbert-Schmidt 理論，Hilbert空間中的內積有一個等價表達式

= ??a1h1(x1)hl(x2)??K(x1，x2)，ai≥0(1)

式中，K(x1，x2)為滿足Mercer定理 的對稱函數，稱為核函數。任意連續對稱函數都可作為核函數，采用不同的核函數會導致不同的學習算法，然而核函數的選擇至今沒有一個完善的理論指導，目前使用的核函數主要有 多種，其中流行的核函數如下：

次多項式為： K(x，xi)=(1+)d

高斯徑向基函數為： K(x，xi)=exp(-‖x-xi‖2/σ2)

神經網絡核函數為： K(x，xi)=tanh(k1+K2)

支持向量機通過引入核函數，不僅可以實現非線性算法，而且算法的復雜度不會增加，這是基于核函數學習方法的關鍵。

4 核方法

核方法 是“基于核的學習(Kernel-Base learning)”的簡稱，它是Vapnik 等人在統計學習理論基礎上發展起來的一種新的機器學習方法。核方法作為由線性到非線性之間的橋梁，它的作用就是代替高維特征空間的內積運算，避免了復雜的高維運算，它在支持向量機扮演著重要的角色。

4.1核方法的基本思想

滿足Mercer條件的任一核函數K(x1，x2)，對應一個特征空間（φ1(x)， φ2(x)， …， φn(x)）

在這一空間中這個核函數生成內積。即：

K(x，xi)=??aihi(x)hi(xi) (2)

樣本空間的內積運算已替換成核，運算是在樣本空間進行，而不是在高維空間中進行。

4.2 核方法的優點

與傳統的機器學習方法相比，核方法具有以下幾個優點：

(1) 核方法專門針對小樣本問題，它的性能優良，泛化能力好，不存在過學習問題。

(2) 核方法結構簡單，不存在如何確定網絡結構等復雜的問題，其求解算法可歸結為一個二次優化問題。從理論上說，得到的將是全局最優點，避免了神經網絡方法中常見的局部極小值問題。

(3) 對于非線性問題，核方法通過非線性映射將樣本從輸入空間映射到高維特征空間，機器學習任務可以在這個高維空間中執行，其計算復雜性與輸入模式的維數沒有直接的關系，避免了“維數災難”問題。

(4) 核方法構造的支持向量機具有模塊化特征。它由兩層構成，第一層從由核定義給定基的集合中選擇基K(x，xi)，i=1，2， …，l；第二層在這一空間中構造一個線性函數。

核方法還可以把許多經典的線性機器學習算法，如主成分分析，推廣到其非線性形式，擴展它們的應用。

4.3 核方法的算法實現

根據核方法的思想，對于非線性分類，首先采用一個非線性映射φ把數據映射到一個高維特征空間，然后在高維特征空間中進行線性分類，映回到原空間后就成了輸入空間中的線性分類。為了避免高維空間中的復雜計算，采用一個核函數K(x，y)代替高維空間中的內積運算<φ(x).φ(y)>。采用松弛變量解決可能存在一些樣本不能被分離超平面正確分離，于是優化問題為：

min1/2??ω 2+c??(3)

約束為：

Yi(<ω， φ(xi)>+b) ≥1-εi，i=1， …，l

εi=0，i=1， …，l

為一正常數。式（3）中第一項使樣本到超平面的距離盡量大，提高泛化能力；第二項使分類誤差盡量小。

引入拉格朗日函數

式中， ai，γi≥0， i=1， …，l。

得到優化問題的對偶形式為：

約束為：

???aiyi=0

0≤ai，γi≥0， i=1， …，l

一般情況下，該優化問題的特點是大部分 將為零 ，其中不為零的 所對應的樣本為支持向量。

根據KKT條件，在鞍點有

于是得到 的計算式如下：

可以通過任何一個支持向量求出 的值，也可以用所有 的支持向量求出 的值，然后取平均。

最后得到判別函數為：

5 實例

下面用XOR分類問題來說明核方法實現的方式。該問題的取值情況如表1

該問題是非線性分類問題，利用核映射方法映射到高維空間來解決。

取映射為：

相應的核函數為：

式中X=[x1，x2]T和Xi=[xi1，xi2]T，因而內積核K(X，Xi) 可表示為：

目標函數的對偶形式為：

對目標函數進行優化，得優化值為：

ai=a2=a3=a4=1/8

所有4個輸入向量都是支持向量。采用其中一個可以計算出 ，將結果帶入式（4）中，得到判別函數為：

f(x)=sgn(-x1，x2)

當x1=x2=-1，x1=x2=+1時，輸出d=-1，當x1=-1，x2=+1，以及x1=+1，x2=-1時，輸出 。因此，XOR問題得以解決。

6 結論

核方法作為線性到非線性之間的橋梁，它的作用是代替高維空間中的內積運算，其計算復雜性與輸入模式的維數沒有直接的關系，這樣避免了復雜的高維運算，其求解算法可歸結為一個二次優化問題。核方法不僅在支持向量機中扮演著重要的角色，而且為許多模式分析應用領域提供了一個統一的框架。

參考文獻：

[1] LIN C-F，WANG S-D.Fuzzy support vector machines[J].IEEE Trans on Neural Networks.2002， 13(2):464-471.

[2] David V ，Sanchez A. Advanced support vector machines and Kernel methods[J].Neurocomputing， 2003，55: 5-20.

[3] Fmuke Frieddrichs ，Christian Igel Evolutionary tuning of multiple SVM parmeters[J].64 (2005) 107-117.

[4] V Vapnik.Statistical learning theory[M]. NJ：JohnWiley Press，1998.

[5] VAPNIK VN. The Nature of Statistical learning theory[M].New York Springer Verlag 1995.

[6] 張冰，孔銳.一種支持向量機的組合核函數[J].計算機應用，2007，27[2]:44-47.

[7] 萬海平，何華燦，周延泉.局部核方法及其應用[J].山東大學學報，2006，41[3]:18-21.

[8] 邱瀟鈺，張化祥.概論核方法及核參數的選擇[J].研究與探討，2007，8[6]:63-65.

[9] 吳今培，孫德山.現代數據分析[M].北京:機械工業出版社，2006.1-33.

[10] 章兢，張小剛，等.數據挖掘算法及其工程應用[M].北京:機械工業出版社，2006.149-156.

收稿日期：2008-03-27

作者簡介：王小菊（1973- ），女，山西晉城人，碩士研究生，研究方向：數據挖掘；李永華（1977-），男，甘肅隴南人，碩士研究生，研究方向：數據挖掘。

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