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

關(guān)鍵詞：核方法；支持向量機；核函數(shù)

中圖分類號：TP311文獻標(biāo)識碼：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 引言

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

2 支持向量機

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

3 核函數(shù)

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

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

根據(jù)Hilbert-Schmidt 理論，Hilbert空間中的內(nèi)積有一個等價表達(dá)式

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

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

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

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

神經(jīng)網(wǎng)絡(luò)核函數(shù)為： K(x，xi)=tanh(k1+K2)

支持向量機通過引入核函數(shù)，不僅可以實現(xiàn)非線性算法，而且算法的復(fù)雜度不會增加，這是基于核函數(shù)學(xué)習(xí)方法的關(guān)鍵。

4 核方法

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

4.1核方法的基本思想

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

在這一空間中這個核函數(shù)生成內(nèi)積。即：

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

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

4.2 核方法的優(yōu)點

與傳統(tǒng)的機器學(xué)習(xí)方法相比，核方法具有以下幾個優(yōu)點：

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

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

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

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

核方法還可以把許多經(jīng)典的線性機器學(xué)習(xí)算法，如主成分分析，推廣到其非線性形式，擴展它們的應(yīng)用。

4.3 核方法的算法實現(xiàn)

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

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

約束為：

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

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

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

引入拉格朗日函數(shù)

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

得到優(yōu)化問題的對偶形式為：

約束為：

???aiyi=0

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

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

根據(jù)KKT條件，在鞍點有

于是得到 的計算式如下：

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

最后得到判別函數(shù)為：

5 實例

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

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

取映射為：

相應(yīng)的核函數(shù)為：

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

目標(biāo)函數(shù)的對偶形式為：

對目標(biāo)函數(shù)進行優(yōu)化，得優(yōu)化值為：

ai=a2=a3=a4=1/8

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

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

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

6 結(jié)論

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

參考文獻：

[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] 張冰，孔銳.一種支持向量機的組合核函數(shù)[J].計算機應(yīng)用，2007，27[2]:44-47.

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

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

[9] 吳今培，孫德山.現(xiàn)代數(shù)據(jù)分析[M].北京:機械工業(yè)出版社，2006.1-33.

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

收稿日期：2008-03-27

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

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文?！?/p>