第 24 卷 第 8 期 2007 年 8 月 计 算 机 应 用 研 究 Application Research of Computers Vol. 24 No. 8 Aug. 2007 基 于 支 持 向 量 机 的 增 量 学 习 算 法 * 曹 杰 a, 刘志镜 b ( 西安 电子 科技 大学 a. 计算 机系 ; b. 计 算中 心, 西 安 710071) 摘 要: 分 析了 支持 向量 的性 质和 增量 学习 过程, 提 出了 一 种新 的 增 量 学 习 算 法, 舍 弃 了 对 最 终分 类 无 用 的 样 本, 在保 证测 试精 度的 同时 减少 了训练 时间 。最 后的 数值 实验 和应用 实例 说明 该算 法是 可行 、有 效的 。 关键 词: 结 构风 险最 小化 ; 支持 向量 ; 增量 学习 中图 分类 号: TP301. 6 文 章编 号: 1001- 3695( 2007) 08- 0048- 02 文 献标 志码 : A Incremental learning algorithm based on SVM ( a. Dept. of Computer; b. Computer Centre, Xidian University, Xi’an 710071, China) CAO Jiea, LIU Zhi-jingb Abstract: By analyzing the characteristics of support vectors and the processing of incremental learning, this paper presented a new algorithm of incremental learning. It discarded useless samples and kept the testing accuracy, meanwhile reduced the training time. Numerical and applicable results illustrate that the technique is feasible and effective in the end. Key words: structural risk minimization; support vector; incremental learning 支持向量机( support vector machine, SVM) 由 Vapnik 及 其 合作者发明, 在 1992 年计算 学习理 论会议 上进入 机器 学习 领 域之后, 便受到了广泛关注。它建立在结构风险最小化原则基 础之上, 具有很强的学习 能力和 泛化性 能, 能 够较好 地解决 小 样本、高维数、非线性、局部极小等问题, 可以有效地进行分类、 回归、密度估计等。由于这些优点, 其得到了全面深入的发展, 现已成为机器学习和数据挖掘领域的标准工具。 增量学习技术( incremental learning technique) 是一种得 到 广泛应用的智能化数据挖 掘与知 识发现 技术。其思 想是当 样 本逐步积累 时, 学习 精 度也 要随 之 提高。与 传 统学 习技 术 相 比, 增量学习技术可以充 分利用 历史学 习的结 果, 显 著节省 后 继训练时间。一种机器学习方 法是否 具有良 好的增 量学习 功 能已经成为评价其性能优 劣的重 要标准 之一。经典 的支持 向 量机理论与增量式学习并 不具备 直接的 相容性。但 是支持 向 量机训练所得的支持向量能够完全反映分类超平面的信息, 而 支持向量通常只占训练样本很小一部份, 这对支持向量机增量 学习算法的构建具有重要意义。 1 支持向量机基本理论 支持向量机的理论最初 来自对 数据分 类问题 的处 理。对 于数据分类问题, 如果采 用通用 的神经 网络方 法来实 现, 其 机 理可以简单地描述为: 系 统随机 产生一 个超平 面并移 动它, 直 到训练集中属于不同分类 的点正 好位于 平面的 不同侧 面。这 种处理机制决定了用神经网络方法进行数据分类, 最终获得的 分割平面将相当靠近训练集 中的点, 而 在绝大 多数情 况下, 这 并不是一个最优 解。为此, SVM 考 虑寻 找一 个 满足 分类 要 求 的分割平面, 并使训练集 中的点 距离该 分割平 面尽可 能地远, 即寻找一个分割平面, 使其两侧的空白区域最大。 1. 1 支持向量机 设 i, yi ) } l { ( x i =1 Rn ×{ 1, - 1} 是 二分类 问题的 训练样 本  集。根据统计学习理论, 建立如下标准模型: l min( 1 /2) ω′ω+ ( C/2) ∑ i =1 s. t. yi( ω′x i - r) + ξi≥1; i∈ { 1, 2, … ξi , l } ; ξi ≥0 ; ( 1 ) , l} 其中: C 为正则化参数; ξi≥0, i∈{ 1, 2, … 为松弛 变量; ω∈ Rn 为分类超平 面的法向量; r∈R 为阈值。目标 函数前一项 反 映的是置信范围, 后一项反 映的是 训练误 差, 前后两 项体现 了 结构风险最小化原则。根 据优化 理论, 式( 1) 的 Wolfe 对偶 形 式是 l αi - ( 1 /2 ) ∑ i =1 l max∑ i =1 s. t. 0≤ αi ≤C; i∈ { 1, 2, … l ∑ j=1 αi αjy iyj χi χj , l} ( 2 ) l ∑ i =1 αiy i = 0 其中: α为 Lagrange 乘子。由上 述问 题得 到最 优 解 α, 则 SVM 的分类函数为 l f( x) = sgn ∑ i = 1 αiyi ( X ×Xi ) + b ( 3 ) 如果分类问题是 非线性 的, 则采 用一 种称 为 核函 数 ( ker- nel function) 的方法, 使输入 空间映射到高维核函数特征空间, 将非线性问题转换为该空 间中的 线性分 类问题。根 据泛函 理 论, 特征空间中对偶问题和得到的决策函数中的点积可以由输 入空间中的核函数来替换。此时, 决策函数为 l f( x) = sgn ∑ i =1 αiy iK( X ×X i) + b ( 4 ) 其中 ( : K ) 为核函数。 收 稿日期 : 2006- 06- 23; 修 返日期 : 2006- 08- 26 基 金项 目: 国 家自 然科学 基金 资助项 目( 60573139) 作 者简介 : 曹杰( 1979- ) , 男 , 陕西人 , 硕士 研究 生, 主 要研 究方 向为 数据 挖 掘、支持 向量 机 ( cj3054@ 163 . com) ; 刘 志 镜( 1957- ) , 男, 陕 西 人, 教 授, 主要研 究方 向为计 算机 网络、多媒 体技 术. 

第 8 期 1. 2 KKT 条件 曹 杰, 等: 基 于支持 向量 机的 增量 学习 算法 ·94· 对偶问题的最优解 α= [ α1, α2, …, αl ] , 使得 每 个样 本 X αi = 0 满足优化问题的 KKT 条件为  yi fi( Xi ) ≥1  0 < αi < C  y i fi( Xi) ≤1 其中: 非零的 α为支持向量。 αi = C yi fi( X i) = 1 ( 5) ( 6) ( 7) 考虑函数系 f( x) = h, 可知 f( x) = 0 为分类面; f( x) = ±1 为分类间隔的边界; 其上的样本即为支持向量, 如图 1 所示。 定理 1 对 样 本 集 进 行 训 练 得 到 SVM 分 类 器, α为 La- grange 乘子。α= 0 对应 的样 本 分布 在分 类 器分 类间 隔 之外; 0≤α≤ C 的 样 本位 于 分类 间隔 之 上; α= C 位 于分 类间 隔 之 内。也就是 αi = 0  |f( X i) |≥1  0 < αi < C  |f( X i) |≤1 αi = C |f( Xi) |= 1 ( 8) ( 9) ( 10) 2 增量学习算法 当核函数类型及其参数确定后, 支持向量集可以完全描述 整个样本集的分类特征, 支持向量集和训练样本集之间的等价 关系可以得到证明。但是随着新样本集的引入, 打破了支持向 量集和初始训练样本集的等价关系, 使得原有的支持向量集已 不能充分刻画新训练集的分类特征。 定理 2 f( x) 为 SVM 分类决策函数, { Xi , yi } 为新增样本。 满足 KKT 条件的新增样本不会改变 支持向量 集; 违 背 KKT 条 件的新增样本会使支持向量集发生变化。违背 KKT 条件 的样 本可以分为三类( 图 2) : a) 位于分类间隔中, 与本类 在分类 边界同 侧, 被 原分类 器 正确分类, 满足 0≤yi f( Xi) < 1; b) 位于分类间隔中, 与本类 在分类 边界异 侧, 被 原分类 器 错误分类, 满足 - 1≤yi f( Xi) < 0; c) 位于分类间隔外, 与本类 在分类 边界异 侧, 被 原分类 器 错误分类, 满足 yi f( Xi) < - 1。 图 2 中, 圆 形标 记 代表 y = 1; 方 形标 记代 表 y = - 1; A1、 A2、A3 代表新增样本。 图 1 样本 分布 图 2 新 增样本 与 KKT 条 件的关 系 定理 2 表明, KKT 条件比分 类函数 的分类 判断更 合理, 分 类错误是样本违 反 KKT 条 件的 特 定情 况。只 有违 背 KKT 条 件的样本, 才会影响 增量学 习后的 支持向 量集。因此, 新增 样 本可以分为违背 KKT 条件 的样 本和满 足 KKT 条件 的样 本 两 部分。后者由于包含的信息已经被原来分类器所反映, 可以不 被学习。 3 新的 SVM 增量学习算法 传统的 SVM 增量学习算法只是将历史样本集和增量样 本 集混合起来进行训练。该方法 忽视了 支持向 量机的 重要性 质 以及 KKT 条件的快速 性。基于 以上 分析, 本 文提 出一 种新 的 增量学习方法。将 SV 集的向量划分为 两种类 型: 一 种类型 是 对 应于 αi = C 的 SV 向量, 这类向量称为 BSV, 代表了所有不能 被正确 分类的 样本向 量; 另一种 类型的 SV, 其对应 的 αi 值 满 足0 < αi < C, 这类 向量 代表了 训练 集中 大部 分样 本的 分类 特 征, 并与 BSV 共同决定最终的结果分类器形式。 前提: 原样本集 A 和由其训 练得到 的 SVM 分 类器 PA; ASV 表示 P A 的支持向量集; B 表示新增样本集。 算法: a) 根据 PA 的 KKT 条件对样本集 B 进行检验, 将样本集 B 分为违背 KKT 条件的样本集 Berr和没有违背 KKT 条件的样 本 集 Bok。 b) 如果 B 中 的 样 本 没 有 违 背 PA 的 KKT 条 件, 即 Berr = , 则迭代结束; 如 果 B 中 的样 本 有 违背 PA 的 KKT 条件, 即 Berr≠ , 则将 ASV和 Berr的并集 A1 作为新 的训练 集, 得到一 个 新的分类器 P1 A 和新的支持向量集 A1 SV。  c) 将集合 A 中除去 ASV的剩余样本作为新的新增样本集 B1。 d) 令 B = B1, 重复( 2) ( 3) 。 e) 通过多次迭代, 算法收敛于分类器 Pn, 令 P = Pn, P 为所 求的结果。 4 实验结果及分析 在上面研究的基础上, 本文对包含 3 483 个 手工标定的 文 档样本, 使用新的 SVM 增量学 习算法 进行电 子文 本的 自动 分 类实验。实验中分别选取样 本空间 中 527 个文档 作为 测试 样 本集, 763 个文档 作为初 始训 练样 本集, 并 将剩 余的 文档 随 机 分为五组, 构成五个增 量训练 样本 集。使用 新的 SVM 增量 学 习算法和经典 SVM 学 习方 法进 行比 较 实验, 实 验 结果 如表 1 所 示( 其中 SVM 训练核函数采用高斯函数。软件环境为 MAT- LAB 7. 0; 硬件环境为 Pentium 4/256 MB 内存) 。 表 1 新的 SVM 增量 学习 结果与 传统 SVM 学习 结果比 较 训 练 集 增 量 样 本 数 初 始 训 练 增 量 1 增 量 2 增 量 3 增 量 4 增 量 5 763 446 109 223 59 1 356 新 SV M 增 量 学 习 算 法 传 统 SV M 增 量 学 习 算 法 时 间 / s 98 . 4 77 . 8 106. 2 123. 5 43 . 3 99 . 6 精 度 93 . 2 % 95 . 6 % 92 . 7 % 94 . 2 % 96 . 5 % 93 . 6 % 时 间 / s 167 223. 4 326. 7 464. 5 592. 1 672. 9 精 度 92 . 4 % 95 . 9 % 91 . 6 % 93 . 8 % 96 . 7 % 93 . 7 % 从上面实验可以看出, 与传统的 SVM 增量学习 算法相比, 新的 SVM 增量学习算法在 不降低 训练精 度的 同时, 显 著提 高 了学习速度。 5 结束语 本文基于支持向量机的特性, 研究了支持向量机的增量学 习方法, 并在此基础上提 出了 使用 KKT 条件 进行 增量 学习 的 算法。实验结果表明, 这种学习方法在精确度和 ( 下转第 52 页 ) 

·25· 计 算 机 应 用 研 究 2007 年 则 Xm3 t Xm1 t 1 , …, Xm3 t F^( Xm3 , X i, C→X j) /F^( Xm3 F^( X m1 , X j, C→ Xi) /F^( Xm1 , …, Xm1t 1 , Xj, C→Xi ) /F^( X m3 , …, X m3 t , C→X i) > F^( Xm3 1 , …, 1 , …, Xm3 t , C→ Xj) , 定向为弧 Xj→Xi ; 1 , Xi, C→ Xj) /F^( Xm1 , …, Xm1 t , C→ Xj) > F^( Xm1 1 , …, 1 , …, Xm1 t , C→ Xi ) , 定向为弧 Xj←Xi。 1 3) 环路检验 删除没有父节点和没有子节点的节点及与其相连接的弧; 在剩下的子图中再删除没有父 节点和 没有子 节点的 节点及 与 其相连接的弧。如此下去, 如果存在每一个节点既有父节点又 有子节点的子图, 那么存在环路; 否则, 不存在环路。 3. 2 实验 在 UCI 机器学习数据仓库 [ 9] 中选 择 20 个 分类数 据集, 对 取连续值的特征, 使用等 频离散 化的方 法进行 离散化, 利用 所 有的例子数据进行贝叶斯网络分类器结构学习, 分别使用朴素 贝叶斯( naive Bayes) 分 类器、C4. 5 分类 器和 贝 叶斯 网络 分 类 器进行分类。采 用 10 折 交叉 有效 性 ( 10-fold cross-validation) 验证方法进行分类 器的 分类 准确 性估 计。分类 准确 性如 表 1 所示。 表 1 三种 分类器 分类准 确性 比较 Domain 朴 素 贝 叶 斯 分 类 器 C4. 5 贝 叶 斯 网 络 从表 1 中可以看出, 贝叶斯网络分类器相对于朴素贝叶 斯 分类器和 C4. 5 分类 器都 具 有优 势。其 主要 原 因是 贝叶 斯 网 络分类器既具有最优性, 同时又能够去除不相关和冗余的属性 变量。这样既提 高了 抗 噪声 能力, 又 避 免了 对数 据 的过 度 拟 合, 因此具有良好的分类效果。 4 结束语 基于预测能力的贝叶斯网络分类器是最优分类器, 但当例 子数量较少时, 由于不能可靠地 进行结 构学习, 适宜 选择 TAN 分类器或朴素贝叶斯分类 器。 本文给 出的贝 叶斯网 络分类 器 学习方法中, 充分利用在样 本充足 的情况 下, 变量之 间存在 预 测关系, 证明了预测准确率就是预测能力。通过这种结构方法 使得离散变量贝叶斯网络分类器倾向于简单化, 同时建立的分 类器有较强的分类能力。 参考文献: [ 1] EARL J. Probabilistic reasoning in intelligent systems: networks of plausible inference[ M] . San Fransisco: Morgan Kaufmann Publishers Inc, 1988 : 117-133. [ 2] HECKERMAN D, GEIGER D, CHICKERING D M. Learning Baye- sian networks: the combination of knowledge and statistical data[ J] . Mach ine Lea rning, 1995, 20 ( 1- 3) : 197- 243 . he art_ dise ase 82. 96 ±5 . 02 77. 98 ±6 . 67 80 . 84 ±4. 3 [ 3 ] FRIEDMAN N, GEIGER D, GOLDSZMIDT M. Bayesian network 80 . 67 ±10. 93 76 . 13 ±10. 68 75. 51 ±1 . 49 classifiers[ J] . M achine Learning , 1997 , 29 ( 2- 3) : 131-161 . 67. 37 ±6 . 58 99. 19 ±0 . 79 95. 16 ±3 . 23 97. 33 ±4 . 66 78 . 3 ±6. 92 99. 45 ±0 . 41 94. 97 ±3 . 17 96. 38 ±3 . 85 [ 4] RAMONI M, SEBASTIAMI P. Robust Bayes classifiers[ J] . Artif icial Intelligence, 2001, 125 ( 1- 2 ) : 209 - 226. [ 5] 王双成 , 苑 森 淼, 王 辉. 基 于类 约 束 的 贝 叶 斯 网 络 分 类 器 学 习 63. 50 ±6 . 73 77 . 34 ±11. 83 79 . 93 ±10. 96 [ J] . 小 型微 型计算 机系 统, 2004, 25 ( 6) : 968- 972. 96. 13 ±2 . 94 92. 14 ±5 . 93 84. 31 ±3 . 98 99 . 6 ±0. 97 92 . 8 ±1. 49 68. 83 ±3 . 79 62. 31 ±5 . 55 84. 34 ±4 . 83 92. 14 ±1 . 33 97. 51 ±2 . 01 93. 24 ±6 . 39 84 . 8 ±2. 99 99 . 7 ±0. 48 92. 81 ±1 . 43 69. 48 ±5 . 17 65. 77 ±5 . 51 84. 86 ±5 . 07 93. 21 ±1 . 25 [ 6] 王双成 , 苑 森淼. 具 有 丢 失数 据 的 贝 叶斯 网 络 结 构 学 习 研 究. 软 件学报 , 2004, 1 5( 7) : 1030-1041. [ 7] LAM W, BACCHUS F. Learning Bayesian belief networks: an ap- proach based on the MDL principle [ J] . Computational Intelli- gence , 1994 , 10 ( 4) : 269- 293. [ 8] CHENG Jie, BELL D, LIU Wei-ru. Learning Bayesian networks from data: an efficient approach based on information-theory[ J] . Artif icial Intelligence, 2002, 137 ( 1- 2 ) : 43- 90. [ 9 ] NEWMAN D J, HETTICH S, BLAKE C L, et al. UCI repository of machine learning databases [ EB/ OL] . http: / / www. ics. uci. edu/ ～ mlearn/ MLRepository. html. he patitis soybean 72. 90 ±9 . 26 c hess_ kr_ vs_ kp 87. 69 ±2 . 41 voting_ rec ords 89. 77 ±5 . 21 iris wpbc wdbc wine c rx 95. 33 ±4 . 27 94. 21 ±3 . 33 92. 78 ±7 . 47 82. 46 ±2 . 71 agricus_ lepio ta 98. 20 ±1 . 66 ann_ train flare _ data 92. 73 ±1 . 32 69. 72 ±5 . 75 primary_ tumor 70. 29 ±6 . 09 tic_ tac _ to e 70. 63 ±5 . 27 sick_ e uthyro id 90. 47 ±1 . 64 bre ast_ cane er 69. 66 ±8 . 42 73 . 83 ±12. 34 75 . 58 ±11. 80 liver_ disease backup_ large glass 61. 43 ±5 . 75 62. 26 ±9 . 35 65. 71 ±7 . 62 59. 76 ±8 . 69 85. 69 ±6 . 96 73. 46 ±6 . 92 64. 42 ±6 . 89 77. 98 ±6 . 67 77. 98 ±6 . 67 ( 上 接第 49 页 ) 时间消耗上 均优 于传 统的 SVM 增 量学 习算 法。 本文算法在训 练时只涉及 全 体样 本中 的 一小 部分 , 但是 那 些 没有参加训 练的 样 本 仍 然 需要 被 存 储, 占 用 计算 机 的 内 存, 其中有一些 样本自 始 至 终 都 没 有 参 加 训 练。 如 何 彻 底 放 弃 这一部分样 本, 减 少训练所 占用 的 空间 是今 后 进一 步研 究 的 方向。 参考文献: [ 3 ] 汪西莉 , 刘 芳, 焦李 成. 基于大 规模 数据的 支持 矢量机 的训 练和 分 类[ J] . 西安 电子 科 技 大 学 学 报: 自然 科 学 版, 2002 , 29 ( 1 ) : 123- 127. [ 4 ] 焦李成 , 屈 炳云 , 周 伟达. 一种 基于 支撑矢 量机 的多用 户检 测算 法 [ J] . 电 子学 报, 2002, 30 ( 10 ) : 1549- 1551. [ 5] 张学工 . 关于统 计学习 理论 与支持 向量 机[ J] . 自动化 学报 , 2000, 26 ( 1) : 31- 42 . [ 1] APNIK V. The nature of statistical learning theory[ M] . New York: Springer-Verlag, 1995. [ 6] 曾文华 , 马健. 一种 新的 支持向 量 机增 量 学 习算 法 [ J] . 厦 门大 学 学报: 自 然科学 版, 2002, 41 ( 6) : 687- 691 . [ 2] VAPNIK V, LEVIN E, CUN Y L. Measuring the VC-dimension of a [ 7] 周伟达 , 张莉, 焦李 成. 支撑 矢量 机 推广 能 力 分 析[ J] . 电 子 学报 , learning machine[ J] . Neural Comput ation , 1994, 6 ( 5) : 851- 876. 2001, 29 ( 5) : 590- 594 .