第7卷第2期2006年4月
空 军 工 程 大 学 学 报（自然科学版）
JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY （NATURAL SCIENCE EDITION ）
Vol. 7No. 2Apr. 2006
改进的SVM 决策树分类算法
史朝辉， 王晓丹， 赵士敏， 杨建勋
（空军工程大学导弹学院，陕西三原 713800）
摘 要：为解决多类分类问题，在分析SVM 决策树分类器及存在问题的基础上，通过引入类间可分离性测度，并将其扩展到核空间，提出一种改进的SVM 决策树分类器。实验表明了该分类算法对提高分类正确率的有效性。
关键词：支持向量机；SVM 决策树；可分离性测度；核空间
中图分类号：TP391. 4 文献标识码：A 文章编号：1009-3516（2006）02-0032-04
［1～2］，而实际的目标分类通常是多值分类问题。为了构造有效的SVM 多值分类SVM 本质上是2值分类
［3］
，也是一种器，除采用一对一、一对多方法及其改进外，将SVM 和二叉决策树结合起来，构成SVM 决策树
有效的方法。本文分析了SVM 决策树分类器及存在问题，基于待分类的分布，定义了一种基于类分布的类间分离性测度，并将其扩展到核空间从而给出了一种改进的SVM 决策树算法。
1 SVM 决策树
与通常的方法相比，SVM 决策树方法对于一个N 值分类问题，需要寻找N -1个最优分类面。随着训练的进行，需要的训练样本数逐渐减少，因此，在训练阶段，随着训练的进行，生成最优分类面所需要的训练时间逐渐减少。在分类阶段，该方法并不像通常的方法需要计算所有分类决策函数的值，它仅需要根据决策树的结构，计算所需要的分类决策函数值。
该方法的缺点是如果在某个结点上发生分类错误，则会把分类错误延续到该结点的后续下一级结点上。因此，分类错误在越靠近树根的地方发生，分类性能就越差。为构造性能良好的决策树结构，可以考虑：将容易分（不易产生错分）的类先分割出来，然后再分不容易分的类。这样，就能够使可能出现的错分尽可能地远离树根。
2 类间分离性测度
根据训练数据估计各类间易分性，通常的做法是
［4］
用类间的Euclidean 距离作为分离性测度，但这种方
法的缺点在于类中心间的距离远近并不能够代表类间的分离度，如图1所示，图1（a ）、图1（b ）中所代表的类间的距离均相等，但是很明显图1（b ）中的两类要比图1（a ）中的两类容易分。
基于上述分析，定义了一种基于类分布的类间分离性测度。
收稿日期：2005-04-13
基金项目：陕西省自然科学基金资助项目（2004F36） 作者简介：史朝辉（1974-），男，河北博野人，讲师，硕士生，主要从事智能信息处理、模式识别、支持向量机研究；
王晓丹（1966-），女，陕西汉中人，教授，博士生导师，主要从事智能信息处理、目标识别、支持向量机研究
.
图1 类中心间距离相等类间易分析的比较
*
第2期史朝辉等：改进的SVM 决策树分类算法
33
假设要进行k 类分类，训练样本集由类X i ，i =1，2，…，k 组成。
定义1 类i 和类j 间的分离性测度sm ij 为
d ij
sm ij =
（σi +σj ）
d （j =1，2，…，k ）表示类i 和类j 中心间的距离：其中，ij i ，
d ij =‖c i -c j ‖
c i 是根据训练样本计算出的类中心：
1
c i =Σx ， i =1，2，…，k
n i x ∈X i
记n i 为类X i 中的样本个数；σi 是类方差，表明了待分类的分布：
1
i =1，2，…，k σi =‖x i -c i ‖ ，
n i -1Σx ∈X i 越好。
定义2
类i 的分离性测度：
sm i =
j =1，2，…，k
j ≠i
（1）
（2）（3）
（4）
若sm ij ≥1，则类i 和类j 间无交叠；若sm ij
min （sm ij ）
（5）
将类i 与其余各类间的最小分离性测度作为该类的类i 的分离性测度表明了类i 与其余类间的分离性，分离性测度。
定义3
最易分的类：
s =arg max （sm i ） ， i =1，2，…，k
i =1，…，k
（6）
即分离性测度值最大的类是最易分的类。
基于上述定义，在线性情况下，定义中的距离采用Euclidean 距离即可。受文献［5］启发，在非线性情况下，采用非线性映射Φ把输入空间映射到某一特征空间H 后这两点间的距离可采用如下表示：引理1 已知两个向量z 1和z 2，经非线性映射Φ作用，映射到特征空间H ，则这两个向量在特征空间的Euclidean 距离为
d H （z 1，z 2）=111222（7）其中K （・，・）是核函数。这里需要指出的是输入空间样本的中心经映射后得到的值不再是特征空间中样本的中心。特征空间样本的中心向量m Φ要在特征空间中求得：1
m Φ=Φ（x i ）（8）
n i =1
其中n 是样本的个数。因为不知道映射Φ（x i ）的具体表达形式，所以无法根据式（8）求类中心向量。
引理2 已知两类模式的训练样本分别为｛x 1，x 2，…，x n 1｝和｛x' 1，x' 2，…，x' n 1｝，设经非线性映射Φ作类中心分别为m Φ和m ' Φ，则在特征空间中m Φ和m ' Φ间的距离为用，映射到特征空间H 后，
111
d （m Φ，m ' Φ）=（x i ，x j ）-K （x i ，x ' j ）+2ΣΣK （x ' i ，x ' j ）（9）ΣΣ2ΣΣK n 1n 2i =1j =1n 1i =1j =1n 2i =1j =1
引理3 已知模式的训练样本为｛x 1，x 2，…，x n ｝，经非线性映射Φ作用后，在特征空间H 中，训练样本x 到类中心m Φ的距离为
H
1
1
1
2
2
2
n
d （x ，m ' Φ）=
进而求得特征空间中的类方差：
H
21
K （x ，x i ）-ΣK （x ，x i ）+2ΣΣK （x i ，x j ）
n i =1n i =1j =1
n
H
1
n n
（10）
1
d H （x i ，m Φ）（11）σ=Σn -1i =1
由此，对非线性的训练样本集，经非线性映射Φ作用后，在特征空间H 中类i 和类j 间的分离性测度定义如下：
sm ij
H
（m i Φ，m j Φ）d H
=H
（σH i +σj
（12）
3 算法描述
基于上述分析和定义，可对传统的SVM 决策树进行改进，从而构造出性能良好的决策树结构，描述如下：
设：在各树结点生成的最优分类面是将一类和其余类分开。假设要进行k 类分类，i =1，2，…，k 组成。训练样本集X 由类X i ，
Step1 由式（12）计算特征空间中的分离性测度sm H 组成分离性测度矩阵S M H ：ij ，
Inf sm H
21H
SM =
H sm k ，1
H H
sm 12 … sm 1，k
H Inf …sm 2，k
sm H …Inf k ，2
为了编程方便，将同类间的分离性测度设为无穷大Inf 。设计数器t =k ；
Step2 选择当前X 中最易分的类，假设类号为i ，为了后续训练的需要，将分离性测度矩阵中i 行、i 列设为Inf ；
Step3 将当前最易分的类与其余各类进行分类训练，得到最优分类面，构成树结点；t =t -1；Step4 X =X -X s ，
Step5 若t >1，转Step2；否则，结束。
4 实验结果与分析
为验证改进后的SVM 决策树算法的有效性，使用三螺旋线和UCI 数据库中的wine 数据集，对改进SVM 决策树与传统SVM 决策树进行了比较实验。4. 1 三螺旋线
三螺旋线问题是一个3类划分问题，是公认的检验多类学习算法能力的“试金石”。该问题的分类要求是把x -y 坐标平面上3条不同螺旋线上的点正确地分开。螺旋线的平面坐标形式可用参数方程表示如下：
x =（k θ+α）cos θ
y =（k θ+α）sin θ
其中k 和α都是常量，分别代表速度和起始距
离。θ是以弧度为单位的相角。三螺旋线有6个参数k 1，k 2，k 3，α1，令k 1α2，α3都是待设定的。本实验中，=k 2=k 3，这是3条速度相同，α1=1，α2=16，α3=32，起始位置不同的螺旋线。在式（13）和式（14）中取θ∈［0，6π］，即取三螺旋线的3个周期的点，采用平均采样，每条线采样240点，共计720个样本点（如图2所示）。
实验分3次进行，每次随机选取每条线的160个
图2 3个周期内的三螺旋线
（13）（14）
点，共计480个作为训练样本；每条线的其余80个点，共计240个作为测试样本。两种方法对比时，训练SVM 在相同条件下进行，分类正确率取3次实验的平均值。表1给出了两种方法对三螺旋线分类的平均正确分类率比较结果。
表1 三螺旋线实验比较结果
C [1**********]0
参数σ=15σ=10σ=5
传统SVM 决策树分类正确率线1线2线397. 93%94. 20%95. 87%98. 37%94. 20%92. 93%95. 83%92. 93%91. 30%
改进SVM 决策树分类正确率
线1线2线398. 77%95. 03%96. 7%98. 37%94. 20%95. 43%96. 27%93. 37%92. 93%
4. 2 wine 数据集
wine 数据集的样本特征维数为13，总数178，分3类（类1样本数59，类2样本数71，类3样本数48）。实验分3次进行，每次随机选取每类样本的2/3作为训练样本；选取每类样本的1/3，作为测试样本。两种方法对比时，训练SVM 在相同条件下进行，分类精度取3次实验的平均值。表2给出了两种方法对wine 数据集分类的平均正确分类率比较结果。
表2 wine 数据集实验比较结果
核函数RBF RBF RBF
C 100100100
参数σ=5σ=40σ=90
传统SVM 决策树分类正确率线187. 72%89. 47%89. 47%
线272. 46%81. 16%88. 40%
线381. 25%68. 75%89. 58%
改进SVM 决策树分类正确率线189. 47%89. 47%91. 23%
线273. 91%82. 61%88. 40%
线383. 33%72. 92%93. 75%
上述两组实验结果表明了改进后的SVM 决策树算法对平均正确分类率的改善。
5 结束语
通过引入类间可分离性测度，并将其扩展到核空间，改进的SVM 决策树算法可最大程度的减少积累误差，提高推广能力。该方法中选择更好的类间可分离性测度是一个有待深入研究的问题。参考文献：
［1］ Vapnik V. The Nature of Statistical Learning Theory ［M ］. New York ：Springer -Verlag ，1995.
［2］ 王晓丹，王积勤. 支持向量机研究与应用［J ］. 空军工程大学学报（自然科学版），2004，5（3）：49-55.
［3］ Bennett K P ，Blue J A. A Support Vector Machine Approach to Decision Trees ［A ］. Proceedings of IJCNNˊ98［C ］. Anchorage
Alaska ：IEEE Press ，1998. 2396-2401.
［4］ Fumitake Takahashi ，Shigeo Abe. Decision -Tree -Based Multi -Class Support Vector Machines ［A ］. Proceeding of ICONIPˊ02
［C ］，Singapore ：IEEE Press ，2002. 1419-1422.
［5］ 焦李成，张 莉，周伟达. 支撑矢量预选取的中心距离比值法［J ］. 电子学报，2001，29（3）：383-386.
（编辑：田新华）
An Improved Algorithm for SVM Decision Tree
SHI Zhao -hui ，WANG Xiao -dan ，ZHAO Shi -min ，YANG Jian -xun
（The Missile Institute ，Air Force Engineering University ，Sanyuan ，Shaanxi 713800，China ）
Abstract ：For the multi -class classification with Support Vector Machines （SVMs ），a decision tree architecture the generalization ability depends on the has been proposed for computational efficiency. But by SVM decision tree ，
tree structure. In this paper ，to improve the generalization ability of SVM decision tree ，a novel separability meas-ure is defined based on the distribution of the training samples in the kernel space ，and an improved SVM decision tree is provided. The theoretical analysis and experimental results show that this algorithm has higher generalization ability.
Key words ：support vector machine ；SVM decision tree ；separability measure ；the kernel space
第7卷第2期2006年4月
空 军 工 程 大 学 学 报（自然科学版）
JOURNAL OF AIR FORCE ENGINEERING UNIVERSITY （NATURAL SCIENCE EDITION ）
Vol. 7No. 2Apr. 2006
改进的SVM 决策树分类算法
史朝辉， 王晓丹， 赵士敏， 杨建勋
（空军工程大学导弹学院，陕西三原 713800）
摘 要：为解决多类分类问题，在分析SVM 决策树分类器及存在问题的基础上，通过引入类间可分离性测度，并将其扩展到核空间，提出一种改进的SVM 决策树分类器。实验表明了该分类算法对提高分类正确率的有效性。
关键词：支持向量机；SVM 决策树；可分离性测度；核空间
中图分类号：TP391. 4 文献标识码：A 文章编号：1009-3516（2006）02-0032-04
［1～2］，而实际的目标分类通常是多值分类问题。为了构造有效的SVM 多值分类SVM 本质上是2值分类
［3］
，也是一种器，除采用一对一、一对多方法及其改进外，将SVM 和二叉决策树结合起来，构成SVM 决策树
有效的方法。本文分析了SVM 决策树分类器及存在问题，基于待分类的分布，定义了一种基于类分布的类间分离性测度，并将其扩展到核空间从而给出了一种改进的SVM 决策树算法。
1 SVM 决策树
与通常的方法相比，SVM 决策树方法对于一个N 值分类问题，需要寻找N -1个最优分类面。随着训练的进行，需要的训练样本数逐渐减少，因此，在训练阶段，随着训练的进行，生成最优分类面所需要的训练时间逐渐减少。在分类阶段，该方法并不像通常的方法需要计算所有分类决策函数的值，它仅需要根据决策树的结构，计算所需要的分类决策函数值。
该方法的缺点是如果在某个结点上发生分类错误，则会把分类错误延续到该结点的后续下一级结点上。因此，分类错误在越靠近树根的地方发生，分类性能就越差。为构造性能良好的决策树结构，可以考虑：将容易分（不易产生错分）的类先分割出来，然后再分不容易分的类。这样，就能够使可能出现的错分尽可能地远离树根。
2 类间分离性测度
根据训练数据估计各类间易分性，通常的做法是
［4］
用类间的Euclidean 距离作为分离性测度，但这种方
法的缺点在于类中心间的距离远近并不能够代表类间的分离度，如图1所示，图1（a ）、图1（b ）中所代表的类间的距离均相等，但是很明显图1（b ）中的两类要比图1（a ）中的两类容易分。
基于上述分析，定义了一种基于类分布的类间分离性测度。
收稿日期：2005-04-13
基金项目：陕西省自然科学基金资助项目（2004F36） 作者简介：史朝辉（1974-），男，河北博野人，讲师，硕士生，主要从事智能信息处理、模式识别、支持向量机研究；
王晓丹（1966-），女，陕西汉中人，教授，博士生导师，主要从事智能信息处理、目标识别、支持向量机研究
.
图1 类中心间距离相等类间易分析的比较
*
第2期史朝辉等：改进的SVM 决策树分类算法
33
假设要进行k 类分类，训练样本集由类X i ，i =1，2，…，k 组成。
定义1 类i 和类j 间的分离性测度sm ij 为
d ij
sm ij =
（σi +σj ）
d （j =1，2，…，k ）表示类i 和类j 中心间的距离：其中，ij i ，
d ij =‖c i -c j ‖
c i 是根据训练样本计算出的类中心：
1
c i =Σx ， i =1，2，…，k
n i x ∈X i
记n i 为类X i 中的样本个数；σi 是类方差，表明了待分类的分布：
1
i =1，2，…，k σi =‖x i -c i ‖ ，
n i -1Σx ∈X i 越好。
定义2
类i 的分离性测度：
sm i =
j =1，2，…，k
j ≠i
（1）
（2）（3）
（4）
若sm ij ≥1，则类i 和类j 间无交叠；若sm ij
min （sm ij ）
（5）
将类i 与其余各类间的最小分离性测度作为该类的类i 的分离性测度表明了类i 与其余类间的分离性，分离性测度。
定义3
最易分的类：
s =arg max （sm i ） ， i =1，2，…，k
i =1，…，k
（6）
即分离性测度值最大的类是最易分的类。
基于上述定义，在线性情况下，定义中的距离采用Euclidean 距离即可。受文献［5］启发，在非线性情况下，采用非线性映射Φ把输入空间映射到某一特征空间H 后这两点间的距离可采用如下表示：引理1 已知两个向量z 1和z 2，经非线性映射Φ作用，映射到特征空间H ，则这两个向量在特征空间的Euclidean 距离为
d H （z 1，z 2）=111222（7）其中K （・，・）是核函数。这里需要指出的是输入空间样本的中心经映射后得到的值不再是特征空间中样本的中心。特征空间样本的中心向量m Φ要在特征空间中求得：1
m Φ=Φ（x i ）（8）
n i =1
其中n 是样本的个数。因为不知道映射Φ（x i ）的具体表达形式，所以无法根据式（8）求类中心向量。
引理2 已知两类模式的训练样本分别为｛x 1，x 2，…，x n 1｝和｛x' 1，x' 2，…，x' n 1｝，设经非线性映射Φ作类中心分别为m Φ和m ' Φ，则在特征空间中m Φ和m ' Φ间的距离为用，映射到特征空间H 后，
111
d （m Φ，m ' Φ）=（x i ，x j ）-K （x i ，x ' j ）+2ΣΣK （x ' i ，x ' j ）（9）ΣΣ2ΣΣK n 1n 2i =1j =1n 1i =1j =1n 2i =1j =1
引理3 已知模式的训练样本为｛x 1，x 2，…，x n ｝，经非线性映射Φ作用后，在特征空间H 中，训练样本x 到类中心m Φ的距离为
H
1
1
1
2
2
2
n
d （x ，m ' Φ）=
进而求得特征空间中的类方差：
H
21
K （x ，x i ）-ΣK （x ，x i ）+2ΣΣK （x i ，x j ）
n i =1n i =1j =1
n
H
1
n n
（10）
1
d H （x i ，m Φ）（11）σ=Σn -1i =1
由此，对非线性的训练样本集，经非线性映射Φ作用后，在特征空间H 中类i 和类j 间的分离性测度定义如下：
sm ij
H
（m i Φ，m j Φ）d H
=H
（σH i +σj
（12）
3 算法描述
基于上述分析和定义，可对传统的SVM 决策树进行改进，从而构造出性能良好的决策树结构，描述如下：
设：在各树结点生成的最优分类面是将一类和其余类分开。假设要进行k 类分类，i =1，2，…，k 组成。训练样本集X 由类X i ，
Step1 由式（12）计算特征空间中的分离性测度sm H 组成分离性测度矩阵S M H ：ij ，
Inf sm H
21H
SM =
H sm k ，1
H H
sm 12 … sm 1，k
H Inf …sm 2，k
sm H …Inf k ，2
为了编程方便，将同类间的分离性测度设为无穷大Inf 。设计数器t =k ；
Step2 选择当前X 中最易分的类，假设类号为i ，为了后续训练的需要，将分离性测度矩阵中i 行、i 列设为Inf ；
Step3 将当前最易分的类与其余各类进行分类训练，得到最优分类面，构成树结点；t =t -1；Step4 X =X -X s ，
Step5 若t >1，转Step2；否则，结束。
4 实验结果与分析
为验证改进后的SVM 决策树算法的有效性，使用三螺旋线和UCI 数据库中的wine 数据集，对改进SVM 决策树与传统SVM 决策树进行了比较实验。4. 1 三螺旋线
三螺旋线问题是一个3类划分问题，是公认的检验多类学习算法能力的“试金石”。该问题的分类要求是把x -y 坐标平面上3条不同螺旋线上的点正确地分开。螺旋线的平面坐标形式可用参数方程表示如下：
x =（k θ+α）cos θ
y =（k θ+α）sin θ
其中k 和α都是常量，分别代表速度和起始距
离。θ是以弧度为单位的相角。三螺旋线有6个参数k 1，k 2，k 3，α1，令k 1α2，α3都是待设定的。本实验中，=k 2=k 3，这是3条速度相同，α1=1，α2=16，α3=32，起始位置不同的螺旋线。在式（13）和式（14）中取θ∈［0，6π］，即取三螺旋线的3个周期的点，采用平均采样，每条线采样240点，共计720个样本点（如图2所示）。
实验分3次进行，每次随机选取每条线的160个
图2 3个周期内的三螺旋线
（13）（14）
点，共计480个作为训练样本；每条线的其余80个点，共计240个作为测试样本。两种方法对比时，训练SVM 在相同条件下进行，分类正确率取3次实验的平均值。表1给出了两种方法对三螺旋线分类的平均正确分类率比较结果。
表1 三螺旋线实验比较结果
C [1**********]0
参数σ=15σ=10σ=5
传统SVM 决策树分类正确率线1线2线397. 93%94. 20%95. 87%98. 37%94. 20%92. 93%95. 83%92. 93%91. 30%
改进SVM 决策树分类正确率
线1线2线398. 77%95. 03%96. 7%98. 37%94. 20%95. 43%96. 27%93. 37%92. 93%
4. 2 wine 数据集
wine 数据集的样本特征维数为13，总数178，分3类（类1样本数59，类2样本数71，类3样本数48）。实验分3次进行，每次随机选取每类样本的2/3作为训练样本；选取每类样本的1/3，作为测试样本。两种方法对比时，训练SVM 在相同条件下进行，分类精度取3次实验的平均值。表2给出了两种方法对wine 数据集分类的平均正确分类率比较结果。
表2 wine 数据集实验比较结果
核函数RBF RBF RBF
C 100100100
参数σ=5σ=40σ=90
传统SVM 决策树分类正确率线187. 72%89. 47%89. 47%
线272. 46%81. 16%88. 40%
线381. 25%68. 75%89. 58%
改进SVM 决策树分类正确率线189. 47%89. 47%91. 23%
线273. 91%82. 61%88. 40%
线383. 33%72. 92%93. 75%
上述两组实验结果表明了改进后的SVM 决策树算法对平均正确分类率的改善。
5 结束语
通过引入类间可分离性测度，并将其扩展到核空间，改进的SVM 决策树算法可最大程度的减少积累误差，提高推广能力。该方法中选择更好的类间可分离性测度是一个有待深入研究的问题。参考文献：
［1］ Vapnik V. The Nature of Statistical Learning Theory ［M ］. New York ：Springer -Verlag ，1995.
［2］ 王晓丹，王积勤. 支持向量机研究与应用［J ］. 空军工程大学学报（自然科学版），2004，5（3）：49-55.
［3］ Bennett K P ，Blue J A. A Support Vector Machine Approach to Decision Trees ［A ］. Proceedings of IJCNNˊ98［C ］. Anchorage
Alaska ：IEEE Press ，1998. 2396-2401.
［4］ Fumitake Takahashi ，Shigeo Abe. Decision -Tree -Based Multi -Class Support Vector Machines ［A ］. Proceeding of ICONIPˊ02
［C ］，Singapore ：IEEE Press ，2002. 1419-1422.
［5］ 焦李成，张 莉，周伟达. 支撑矢量预选取的中心距离比值法［J ］. 电子学报，2001，29（3）：383-386.
（编辑：田新华）
An Improved Algorithm for SVM Decision Tree
SHI Zhao -hui ，WANG Xiao -dan ，ZHAO Shi -min ，YANG Jian -xun
（The Missile Institute ，Air Force Engineering University ，Sanyuan ，Shaanxi 713800，China ）
Abstract ：For the multi -class classification with Support Vector Machines （SVMs ），a decision tree architecture the generalization ability depends on the has been proposed for computational efficiency. But by SVM decision tree ，
tree structure. In this paper ，to improve the generalization ability of SVM decision tree ，a novel separability meas-ure is defined based on the distribution of the training samples in the kernel space ，and an improved SVM decision tree is provided. The theoretical analysis and experimental results show that this algorithm has higher generalization ability.
Key words ：support vector machine ；SVM decision tree ；separability measure ；the kernel space