核方法的探讨及其应用

开篇：润墨网以专业的文秘视角，为您筛选了一篇核方法的探讨及其应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要：核方法是机器学习中一种新的强有力的学习方法。针对核方法进行了探讨，给出了核方法的基本思想和优点。同时，描述了核方法的算法实现并举例进行了说明。

关键词：核方法；支持向量机；核函数

中图分类号：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-xi2/σ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)代替高维空间中的内积运算。采用松弛变量解决可能存在一些样本不能被分离超平面正确分离，于是优化问题为：

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

约束为：

Yi(+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格式阅读原文。”