论文部分内容阅读
摘要:支持向量机(SVM)是在统计学习理论的基础上发展起来的新一代学习算法,具有全局最优,结构简单,推广能力强等优点,是目前机器学习和模式识别领域的研究热点之一。
关键词:支持向量机;文本分类;变量
中图分类号:O246文献标识码:A文章编号:1009-0118(2010)-03-0134-02
一、研究背景
机器学习主要研究从观测数据出发,寻找规律,并利用这些规律对未来的数据进行预测和分类,其实现方法大致有下列三种:
1、经典的统计预测方法
2、经验非线性方法
3、统计学习理论
在统计学习理论的基础上发展了一种新的机器学习方法——支持向量机(support vector machines简称SVM),它较完美的结合了最优化、判别分析、聚类、回归、分布估计等,而机器只要定义不同的核函数,就能实现现有的学习算法。因此,支持向量机已经在众多的领域取得了成功的应用。
二、国内外研究现状
支持向量机是Vapnik等人提出的,1998年Smola在其论文中的研究为进一步完善支持向量机的非线性算法做出了重要的贡献。
(1)支持向量机的变形算法
随着训练样本集的增大,支持向量机对时间复杂度和空间复杂度的要求也逐渐增加。为了提高其运行速度,扩大其应用领域,许多研究人员通过增加函数项,变量或者系数等方法使公式变形,产生出各种有某一方面优势或者一定应用范围的算法,如C-SVM系列,v-SVM系列,One-Class SVM等算法。
(2)C-SVM算法
该算法由Vapnik于1995年提出。以两类问题为例,训练样本xi∈Rn,i=1,2…,i,i为训练样本集的规模,yi ={+1,-1}为类别标记,则初始问题可描述为:
ww+ci
s,t,yi(w(xi)+b)≥1-
≥0,i-1,...,l
其中C为惩罚系数,C越大表示对错误分类的惩罚越大,是算法中唯一可调节的。这是一个具有线性约束的二次规划问题,采用拉格朗日乘子法即可求解。
(3)v-SVM算法
支持向量的树目是影响分类结果和算法效率的一个重要因素。其初始问题描述为:
ww+ci-vp
s,t,yi(w(xi)+b)≥1-
≥0,i-1,...,l
p≥0
为了计算控制参数b和p,选取相同数量s的训练样本组成两个集合S+和S-,S+表示从正类别样本中选取的集合,S-表示从负类别样本中选取的集合,其中包含的支持响亮Xi的系数m满足0≤m≤1,根据KKT条件式中的约束条件yi(w(xi)+b)≥p-可变为等式,并且≥0 。经过变形后可求得b和p。
(4) One-class SVM算法
One-class SVM算法最早用于高维分布估计,即寻找超平面VC维的估计值。该算法的初始问题描述为
ww+ci-p
s,t,w(xi)≥p-
≥0,i-1,...,l
用超球面替代超平面对样本进行划分,目标函数初始问题变为如下形式
R2+i
s,t,(xi)-c≥≤R+
≥0,i-1,...,l
通过设定参数v(0≤v≤1),使得超球面的半径R和它所能包含的训练样本树木进行折中。当v小的时候,尽量把样本放进球面内,而当v大的时候,则尽量压缩球的尺寸。也就是说,该方法通过把样本映射到特征空间,并且尽量用一个朝球面来描述特征空间的样本,把大部分的样本包含到球面中。
超平面只是将两类样本分开。由于超平面把空间一分为二,两边的地位都是相等的,对于第三类样本无法做响应处理;而超球面不仅可以分开两类,而且每一部分空间的地位是不相等的。对于第三类样本来说,处在超球面内部和外部也是不一样的。通过控制超球面的大小和范围,超球面的作用不仅仅是分开两类,而且还帮球里面的样本尽量包“牢”,包“纯”,拒绝其他类的样本进入。
三、SVM在文本分类中的应用
基于SVM的文本分类系统主要由三个步骤组成:产生数据字典、使用训练样本对分类器进行训练以及使用训练号的分类器进行分类。
第一个模块:产生数据字典
1、数据字典的产生。为了构成文本向量,第一步要产生数据字典。当生成一个文本向量,向量的每一维属性只能是数据字典里面所包含的特征值。
2、构成数据字典。在经过关键字提取的步骤之后,并不是所有的特征词都包含有用信息,可使用相关算法进行处理,建立适当的数据字典。
3、为了方便对分类器进行训练和测试,需要将训练文本和测试文本转换为特征向量。一个特征向量对应一篇文本,向量里面的每个属性对应数据字典里面若干关键字。
第二个模块:训练分类器
这个步骤主要是把样本提供给SVM,最终得到决策函数。所有的知识都包含在训练集合中。
第三个模块:分类器的预测
该模块主要用于检验分类器的效果。
由于SVM分类器在文本分类系统中起了重要作用,基于SVM的文本分类系统可以借助一些SVM的软件包,在其基础上进行设计与开发。下面介绍一个SVM软件包-SVM LIGHT。
SVMLIGHT由美国康奈尔大学Thorsten Joachims用C实现的支持向量机算法的软件包,具有以下特点:
•快速的优化算法
•解决了分类核回归问题
•计算出查全率和查准率
•可以处理大规模的训练样本以及上千的支持向量
•多种标准核函数的实现并允许用户自定义核函数
四、总结
支持向量机是在统计学习理论的 VC维理论和结构风险最小原理的基础上发展起来的一种新的机器学习方法。支持向量机在解决大规模数据的学习问题时,对时间和空间复杂度的要求较高。这一问题限制了其在实际中更广泛的应用。因此,研究有效的学习算法是目前支持向量机应用的主要问题。
参考文献:
[1]张学工.关于统计学习理论与支持向量机[J].自动化学报,2000,(26).
[2]Burges CA Tutorial on Support Vector Machines for Pattern Recognition[J].Data Mining and Knowledge Discovery, 1998,(2).
关键词:支持向量机;文本分类;变量
中图分类号:O246文献标识码:A文章编号:1009-0118(2010)-03-0134-02
一、研究背景
机器学习主要研究从观测数据出发,寻找规律,并利用这些规律对未来的数据进行预测和分类,其实现方法大致有下列三种:
1、经典的统计预测方法
2、经验非线性方法
3、统计学习理论
在统计学习理论的基础上发展了一种新的机器学习方法——支持向量机(support vector machines简称SVM),它较完美的结合了最优化、判别分析、聚类、回归、分布估计等,而机器只要定义不同的核函数,就能实现现有的学习算法。因此,支持向量机已经在众多的领域取得了成功的应用。
二、国内外研究现状
支持向量机是Vapnik等人提出的,1998年Smola在其论文中的研究为进一步完善支持向量机的非线性算法做出了重要的贡献。
(1)支持向量机的变形算法
随着训练样本集的增大,支持向量机对时间复杂度和空间复杂度的要求也逐渐增加。为了提高其运行速度,扩大其应用领域,许多研究人员通过增加函数项,变量或者系数等方法使公式变形,产生出各种有某一方面优势或者一定应用范围的算法,如C-SVM系列,v-SVM系列,One-Class SVM等算法。
(2)C-SVM算法
该算法由Vapnik于1995年提出。以两类问题为例,训练样本xi∈Rn,i=1,2…,i,i为训练样本集的规模,yi ={+1,-1}为类别标记,则初始问题可描述为:
ww+ci
s,t,yi(w(xi)+b)≥1-
≥0,i-1,...,l
其中C为惩罚系数,C越大表示对错误分类的惩罚越大,是算法中唯一可调节的。这是一个具有线性约束的二次规划问题,采用拉格朗日乘子法即可求解。
(3)v-SVM算法
支持向量的树目是影响分类结果和算法效率的一个重要因素。其初始问题描述为:
ww+ci-vp
s,t,yi(w(xi)+b)≥1-
≥0,i-1,...,l
p≥0
为了计算控制参数b和p,选取相同数量s的训练样本组成两个集合S+和S-,S+表示从正类别样本中选取的集合,S-表示从负类别样本中选取的集合,其中包含的支持响亮Xi的系数m满足0≤m≤1,根据KKT条件式中的约束条件yi(w(xi)+b)≥p-可变为等式,并且≥0 。经过变形后可求得b和p。
(4) One-class SVM算法
One-class SVM算法最早用于高维分布估计,即寻找超平面VC维的估计值。该算法的初始问题描述为
ww+ci-p
s,t,w(xi)≥p-
≥0,i-1,...,l
用超球面替代超平面对样本进行划分,目标函数初始问题变为如下形式
R2+i
s,t,(xi)-c≥≤R+
≥0,i-1,...,l
通过设定参数v(0≤v≤1),使得超球面的半径R和它所能包含的训练样本树木进行折中。当v小的时候,尽量把样本放进球面内,而当v大的时候,则尽量压缩球的尺寸。也就是说,该方法通过把样本映射到特征空间,并且尽量用一个朝球面来描述特征空间的样本,把大部分的样本包含到球面中。
超平面只是将两类样本分开。由于超平面把空间一分为二,两边的地位都是相等的,对于第三类样本无法做响应处理;而超球面不仅可以分开两类,而且每一部分空间的地位是不相等的。对于第三类样本来说,处在超球面内部和外部也是不一样的。通过控制超球面的大小和范围,超球面的作用不仅仅是分开两类,而且还帮球里面的样本尽量包“牢”,包“纯”,拒绝其他类的样本进入。
三、SVM在文本分类中的应用
基于SVM的文本分类系统主要由三个步骤组成:产生数据字典、使用训练样本对分类器进行训练以及使用训练号的分类器进行分类。
第一个模块:产生数据字典
1、数据字典的产生。为了构成文本向量,第一步要产生数据字典。当生成一个文本向量,向量的每一维属性只能是数据字典里面所包含的特征值。
2、构成数据字典。在经过关键字提取的步骤之后,并不是所有的特征词都包含有用信息,可使用相关算法进行处理,建立适当的数据字典。
3、为了方便对分类器进行训练和测试,需要将训练文本和测试文本转换为特征向量。一个特征向量对应一篇文本,向量里面的每个属性对应数据字典里面若干关键字。
第二个模块:训练分类器
这个步骤主要是把样本提供给SVM,最终得到决策函数。所有的知识都包含在训练集合中。
第三个模块:分类器的预测
该模块主要用于检验分类器的效果。
由于SVM分类器在文本分类系统中起了重要作用,基于SVM的文本分类系统可以借助一些SVM的软件包,在其基础上进行设计与开发。下面介绍一个SVM软件包-SVM LIGHT。
SVMLIGHT由美国康奈尔大学Thorsten Joachims用C实现的支持向量机算法的软件包,具有以下特点:
•快速的优化算法
•解决了分类核回归问题
•计算出查全率和查准率
•可以处理大规模的训练样本以及上千的支持向量
•多种标准核函数的实现并允许用户自定义核函数
四、总结
支持向量机是在统计学习理论的 VC维理论和结构风险最小原理的基础上发展起来的一种新的机器学习方法。支持向量机在解决大规模数据的学习问题时,对时间和空间复杂度的要求较高。这一问题限制了其在实际中更广泛的应用。因此,研究有效的学习算法是目前支持向量机应用的主要问题。
参考文献:
[1]张学工.关于统计学习理论与支持向量机[J].自动化学报,2000,(26).
[2]Burges CA Tutorial on Support Vector Machines for Pattern Recognition[J].Data Mining and Knowledge Discovery, 1998,(2).