n
n
∑ ∑ maxW (α)
= αi -
i =1
1 2
ααi jyiyj
i, j =1
(
xi
·xj)
n
∑ w 3 = αiyixi i =1
b 3 = yi - w ·xi
(4)
(5) (6)
满足约束条件 :
n
∑yαi i = 0 ,αi Ε 0 , I = 1 ,2 ,3 , … n
1. 2 线性不可分的情况
对于线性不可分的情况 ,可以把样本 X 映射到一个高维特征空间 H ,并在此空间中运用原空间的函
数来实现内积运算 ,这样将非线性问题转换成另一空间的线性问题来获得一个样本的归属. 根据泛函的
有关理论 ,只要一种核函数满足 Mercer 条件 ,它就对应某一空间中的内积 , 因此只要在最优分类面上采
i 个样本的输出.
如果样本规模过大 ,则有可能使得矩阵 D = yiyj K( xi ·xj) 过大进而使得无法用计算机来完成处理
工作. 于是如何使得 SVM 对大规模样本集的训练能力得以提高与如何精简样本集来提高 SVM 的训练速
度成为 SVM 研究领域中的热点问题 .
1995 年 ,Cortes 和 Vapnik 提出 Chunking 算法[1] ,其出发点是删除矩阵中对应 Lagrange 乘子为零的行
min <( w)
=
1 2
‖w ‖2
(2)
Ξ 收稿日期 :2004202206 作者简介 :黄发良 (1975 - ) ,男 ,湖南永州人 ,硕士研究生 ;研究方向 :数据挖掘 、web 信息检索. © 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
化条件 ,则再次遍历全部乘子 ,一旦找到第一个乘子 ,内层循环寻找第二个乘子 ,使其在当前迭代中具有
最大的改变量. 为减少计算量 ,该算法根据当前分类器对样本的分类错误量来大致估计 ,对估计估计值
不满足要求的情况还设计出相应对策.
在提高 SVM 适应训练大样本的能力的同时 ,在解决具体问题时 ,研究者们都希望设计出相应的算
与列将不会影响最终结果. 因此 ,可将一个大型的 QP 问题子化为若干个相对小的 QP 问题 ,该算法的每
一步解决一个 QP 问题 ,其样本为上一步所剩的具有非零 Lagrange 乘子的样本与不满足 Kuhn - Tucker 条
件的 M 个样本 ,如果在某一步中不满足 Kuhn - Tucker 条件的样本小于 M 个 ,则这些样本全部加入到一
如下条件 ( Kuhn - Tucker 条件) :
αi = 0 Ζ yif ( xi) Ε 1
(12)
0 < αi < C Ζ f ( xi) = 1
(13)
αi = C Ζ f ( xi以表示模型复杂度与分类错误率之间的一种平衡 , f ( xi) 为 SVM 相对于第
边界 ,在必要时对最初的训练样本集用新决策边界编辑 ,去掉错分的样本 ,得到另一个新的训练集 ,再对
它进行训练得到新的决策边界. 在此基础之上的 NN - SVM 算法[5] ,它先对训练集进行修剪 ,根据每个
样本与其最近邻的类标的异同决定其取舍 ,然后用 SVM 训练得到分类器. ISUC 算法[6]则将无监督聚类
用适当的内积函数就可以实现这种线性不可分的分类问题. 此时的目标函数为
其相应的分类函数为 :
n
n
∑ ∑ maxW (α)
= αi -
i =1
1 2
ααi jyiyj K(
i, j =1
xi
·xj)
(10)
n
∑ f ( x) =
yαi i K( x ·xi) + b 3
i =1
(11)
1. 3 支持向量机
· 76 · 广 西 师 范 学 院 学 报 (自 然 科 学 版) 第 21 卷
满足约束条件 :
yi ( w ·xi + b) Ε 1 , i = 1 ,2 ,3 , …, n.
(3)
在特征数目特别大的情况 ,可以将此二次规划问题转化为其对偶问题 ,
目前我们主要所做的工作是 ,在我们开发的元搜索引擎原型中运用 SVM 实现自动化网页分类与个 性化信息服务.
个新的 QP 问题中. 每一个子 QP 问题都采用前一个子 QP 问题的结果作为初始值. 这样 ,Chunking 算法
就将矩阵规模由样本个数的平方减少到具有非零 Lagrange 乘子的样本个数的平方. 这大大降低了对计
算机性能要求.
尽管 Chunking 算法在一定程度上解决样本过大所引发的 SVM 训练难以实现这一难题 ,但是若训练
支持向量机的基本原理如图 1 所示.
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
第 3 期 黄发良 ,钟 智 :用于分类的支持向量机
· 77 ·
2 训练算法
SVM 训练算法的本质是求解一个二次规划问题 , 即最优化该问题的解就是要使得所有样本都满足
法 ,对大样本进行预处理使得训练样本容量缩小 ,从而使训练的速度大提高. 这方面研究形成了许多新
的算法 : ESVM( Editing Supporting Vector Machine) [4] ,它首先用 SVM 对训练集学习得到决策边界 ,去掉决
策边界附近一定区域内的样本有及错分的样本 ,然再对新训练样本重新用 SVM 进行训练得到新的决策
题 ,这是因为在每一步中 ,只能使一个样本符合 Kuhn - Tucker 条件. 同年 ,Joachims 提出一种解决大型
SVM 学习的算法 ,称为 SVMlight[2] . 其基本思想是 :如果存在不满足 Kuhn - Tucker 条件的样本 ,则以某种
方式选择 q 个样本作为工作集 ,其它样本保持不变 ,在这个工作集上解决 QP 问题. 重复这一过程 ,直至
2004 年 9 月 广西师范学院学报 (自然科学版) 第 21 卷第 3 期 Journal of Guangxi Teachers Education University( Natural Science Edition)
文章编号 :100228743 (2004) 0320075204
的意义.
© 1995-2005 Tsinghua Tongfang Optical Disc Co., Ltd. All rights reserved.
· 78 · 广 西 师 范 学 院 学 报 (自 然 科 学 版) 第 21 卷
3 我们的工作
i =1
(7)
这里α = (α1 , …,αn) 是 Lagrange 乘子 , w 3 是最优超平面的法向量 , b 3 是最优超平面的偏移量 ,在这类
优化问题的求解与分析中 , KKT 条件将起到很重要的作用 ,在 (7) 式中 ,其解必须满足
αi{ yi ( w ·x + b) - 1} = 0 , I = 1 ,2 ,3 , …, n.
算法与 SVM 结合起来 ,利用无监督聚类对训练集中的正例与反例进行聚类 ,然后在聚类结果中选择一
些例子训练 SVM ,这样将 SVM 的高准确率与无监督聚类的速度快有机结合起来.
在训练算法的设计过程中 ,如何进行合理地选择核函数也是一个有待解决的问题. 由于当核函数确
定之后 ,用户只能对 Kuhn - Tucker 条件中的 C 进行设定 ,因此核函数对 SVM 训练算法的性能有着极大
我们要利用 SVM 处理的高维 、小样本与非线性等特点 ,对网页信息进行分类 ,这主要有以下几个方 面的原因 :第一 ,Web 信息具有高维的特征输入空间. 作为现代人们交流一种媒介 ,web 信息的内容广泛 至极 ,无所不含. 第二 ,Web 信息具有高度的动态性与个体性. Web 信息内容日新月异 ,人本思想的泛行 导致个性化行为在 Web 中累见不鲜 ,由于 SVM 适合小样本分类空间 ,故使用 SVM 能产生性能良好的适 合用户需求的分类器.
所有样本都满足 Kuhn - Tucker 条件. 在此基础上 ,Platt 提出了一种名为 SMO 的新训练算法[3] ,它利用了
两条行之有效的经验来确定工作集. 外层循环在某个乘子集合中遍历 ,将第一个不满足优化条件的乘子
作为第一个被优化对象 ,第一次遍历全部乘子 ,以后遍历非有界乘子 ;如果所有非有界乘子都来满足优
样本中所含的支持向量数非常大时 ,Chunking 算法依然无能为力 ,于是乎 ,1997 年 ,Qsuna 等提出一种新
的算法 ,其主要方法是 :先建立一个工作集 ,保持其大小不变 ,在解决每个 QP 子问题时 ,先从工作集移
走一个样本 ,并加入一个不满足 Kuhn - Tucker 条件的样本 ,再进行优化. 然而此算法存在一定的效率问
(8)
从式 (5) 可知 ,那些αi = 0 的样本对分类没有任何作用 ,只有那些αi > 0 的样本才对分类起作用 ,这些样 本称为支持向量 ,故最终的分类函数为 :
n
∑ f ( x) =
yαi i ( x ·xi) + b 3
i =1
根据 f ( x) 的符号来确定 X 的归属.
(9)
SVM 的主要思想可以概括为两点 : (1) 它是针对线性可分情况进行分析 ,对于线性不可分的情况 , 通过使用非线性映射算法将低维输入空间线性不可分的样本转化为高维特征空间使其线性可分 ,从而 使得高维特征空间采用线性算法对样本的非线性特征进行线性分析成为可能 ; (2) 它基于结构风险最小 化理论之上在特征空间中建构最优分割超平面 ,使得学习器得到全局最优化 ,并且在整个样本空间的期 望风险以某个概率满足一定上界.