第 24 卷 第 1 期
V ol. 24 No . 1
控 制 与 决 策
Contro l and Decisio n
2009 年 1 月
Jan. 2009
收稿日期: 2007-10-19; 修回日期: 2008-01-15.
基金项目: 国防基础科研项目( A1420061264) .
作者简介: 连可 ( 1978 ) ) , 男, 重庆璧山人, 博士生, 从事 故障诊断、模式识别的研究; 王厚军( 1961 ) ) , 男, 北京人,
教授, 博士生导师, 从事信号信息处理、电子测试等研究.
文章编号: 1001-0920( 2009) 01-0007-06
基于遗传算法的 SVM 多分类决策树优化算法研究
连 可, 陈世杰, 周建明, 龙 兵, 王厚军
( 电子科技大学 自动化工程学院, 成都 610054)
摘 要: 设计一种基于遗传算法( G A ) 的支持向量 机( SVM ) 多分类 决策树 优化算 法, 以 克服因 传统 SVM 多分 类决
策树结构固定, 单个 SV M 节点在树中位置随意而引起/ 误差积累0 现象严重 的缺陷. 采用了 SVM 分类 间隔作为 GA
适应度函数. 利用 G A 在每一决策节点自动选择最优或近优的分类决策, 最终自适应地实现了对决策树的优化. 仿真
实验表明, 与传统方法相比, 所提出 的方法可使/ 误差积累0 现象明显降低, 分类质量大大提高.
关键词: 支持向量机; 遗传算法; 决策树; 误差积累
中图分类号: T P39 文献标识码: A
Study on GA-based SVM multi-class classification decision-tree
optimization algorithm
L I A N K e, C H EN S hi-j ie , Z H OU J ian-ming , LONG B ing, W A NG H ou-j un
( Co llege o f A utomation Engineering, Univ ersity o f Electro nic Science and Techno lo gy o f China, Cheng du 610054,
China. Co rrespondent: LIA N Ke, E-mail: lian_k@ 163. co m)
Abstract: Fo r the fixed t ree config uratio n of traditional suppor t vecto r machine ( SVM ) multi-class classification
decision-tree algo rithm s and the random po sitio ns of their decisio n nodes, the er ro r accumulate is very severity.
T her efore, we pre sent a GA-based SVM multi-class cla ssifica tion decision-tree optimiza tion algo rithm. We adopt the
/ marg in0 of S VM a s adaption functio n to desig n G A . T hen, GA is used to create optimal o r subo ptimal decision-tree
automa tically , which makes the ma rgin between two cla sses max imal a t ever y decisio n node. Experiment results show
that the er ror accumulatio n pheno mena is w eaken o bviously and classifica tion quality is advanced g reatly .
Key words: Suppo rt vecto r machine; Genetic alg o rithm; Decision tree; Erro r accumulation
1 引 言
支持向量机( SVM ) 是一种新的基于统计学习
理论的机器学习方法. 自诞生以来, 由于其突出的小
样本学习的能力和良好的泛化性能, 已在不同的领
域得到了广泛的应用. 但是, 传统的 SVM 只能处理
二分类问题, 而在许多应用领域中( 如医学诊断、设
备故障诊断等) , 待识别的样本往往包含多种模式,
因此, 研究利 用 SVM 处理 多 类别分类问题具重
要的现实意义, 也是目前 SVM 研究的热点问题之
一.
目前已提出的 SVM 多分类方法大致可分为两
类: 一次性求解法和分解重构法. 一次性求解法是由
Weston 等人
[1 ]
在 1998 年最早提出的, 它在所有训
练样本上求解一个大型二次规划问题, 同时将所有
样本分开. 由于该方法变量个数多, 计算复杂度高,
实用性并不强. 而分解重构法是一种比一次性求解
法更适合于实际应用的方法
[2 ]
, 其主要思想是将多
类分类问题转化为多个两类分类问题, 并采用某种
策略将多个两类分类器组合起来以实现多分类. 其
中, one-against-rest( 1-a-r)
[3 ]
和 one-ag ainst-one ( 1-
a-1)
[4 ]
是较早提出的两种经典的 SVM 多分类法. 1-
a-1 采用/ 一对一0 的方法训练基本 SVM , 采用投票
法组合策略进行多分类; 1-a-r 则采用/ 一对其余0的
方法训练基本 SV M , 同时采用/ 最大输出0法实现多
分类. 这两种方法的优点是分类精度较高. 缺点是:
1) 其泛化误差无界; 2) 对于 K 分类问题必须分别
训练K ( K - 1) /2 个和 K 个基本 SVM , 且分类必须
遍历所有训练的 SVM , 训练复杂, 分类效率 低. 对
DOI：10.13195/j.cd.2009.01.9.liank.012
