一种小样本决策树分类器构造中的连续属性分割方法

摘要

本发明涉及一种小样本决策树分类器构造中的连续属性分割方法，包括连续属性分割点数确定和分割位置优化两部分；首先由训练样本集，构造SVM分类面模型，确定其边界点，选择合理异类边界点对，并计算各合理异类边界点对连线上的分类面点；对于连续属性，根据所有分类面点的分类间隔分布确定连续分割点数和初始分割位置；根据所有分类面模型的分类面点，对于每个SVM分类面模型，计算属性分割面与该SVM分类面的逼近误差，并对所有SVM分类面的逼近误差进行融合，进而以逼近误差为目标优化连续属性分割位置；本发明的方法具有属性分割点数与位置选择快速准确等特点，可显著减少所构造决策树的大小，提高决策树的预测精度。

权利要求

1.一种小样本决策树分类器构造中的连续属性分割方法，其特征在于，该方法的步骤如下：（1）根据训练样本集，构造SVM分类面模型；

（2）确定SVM分类面的边界点，根据决策面点沿SVM分类面均匀分布的原则，选择合理异类边界点对，并计算各合理异类边界点对连线上的决策面点；

（3）采用现有的属性选择方法选择优先扩展属性，若无扩展属性则结束，否则转步骤（4）；

（4）根据所有分类面模型的决策面点，对于离散属性，其取值点即为分割点，转步骤（3）；对于连续属性，根据所有决策面点的分类间隔分布确定连续分割点数和初始分割位置；

（5）根据所有分类面模型的决策面点，对于每个SVM分类面模型，依该模型的决策面点和决策面与分割面的逼近误差，计算属性分割面与该SVM分类面的逼近误差E(Modeli)，并依 或 进行逼近误差E(Modeli)融合；

（6）采用带约束复合型优化方法进行连续属性分割位置优化，转步骤（3）。

2.根据权利要求1所述的方法，其特征在于：所述步骤（1）中构造SVM分类面模型的方式为：对于多分类问题的每个类别，构造该类与其它类别所组成的2分类SVM分类面模型Modeli,i=1,2,...,C，其中，C为类别数；对于2分类问题，则仅构造1个SVM分类面模型。

3.根据权利要求2所述的方法，其特征在于，所述步骤（1）中对于给定的训练样本集其中 为第m个样本点的属性值向量，ym∈{-1,+1}为相应的二分类类别标号，则SVM分类面模型可表示为

其中，γ为大于0的参数；βj,b为通过SVM训练所获得的参数，βj≠0；xj为相应的支持向量点，j=1,...,l，l为支持向量点数。

4.根据权利要求3所述的方法，其特征在于，所述步骤（2）中对于给定的训练样本集S，其边界点集合SB可定义为SB={x|x∈S,|Z(x)|<θ,θ<0} (2)其中θ为给定的边界点的分类值门限。

5.根据权利要求1所述的方法，其特征在于，所述步骤（4）中确定连续分割点数和初始分割位置的过程如下：（41）置分割点数K=0；对于给定的训练样本子集SΓ， S表示训练样本集，求出样本子集SΓ所限定的属性 取值区间为 其中xki为样本子集SΓ中xk样本点的第i个属性值；

（42）求出样本子集SΓ所限定的属性取值空间中的决策面点子集或xB2∈Sr}，其中xB1、xB2为两异类边界点，xD为位于其连线上的决策面点，SD表示决策面点的集合，xB1∈SB、xB2∈SB，SB表示训练样本集S的边界点集合；

（43）对于样本子集SΓ中边界点xB，xB∈SB，过边界点xB沿分割属性 方向求出相应的决策面点，构成决策面点子集（44）依 式MV(xD)=|Φ(xDr)-Φ(xDl)|计 算 决 策 面 点 xD的 分 类 值 差MV(xD)，其中，xDl为L上xD左边最近的最大|Φ(x)|点，称为xD的左间隔边界点；xDr点为L上xD右边最近的最大|Φ(x)|点，称为xD的右间隔边界点；

K

（45）若K=0，置搜索区间 否则置搜索区间 其中c 为第K个分割点的 属性值；

（46）计算分割点 其中，xDli、xDri分别为决策面点xD的左、右间隔边界点xDl、xDr的 属性值；TMV为MV(xD)的限定值；

（47）若c存在，则K=K+1，cK=c，cK进入分割点集合SC，转步骤（45）；若c不存在，如果K>0结束，否则转步骤（48）；

（48）计算 其中 为决策面点 的右间隔边界点1

的 属性值，c 进入分割点集合SC，结束。

6.根据权利要求1所述的方法，其特征在于，所述步骤（5）中决策面与分割面ck的逼近误差为 其中， SC为分割点集合， 为决策面点的集合，XDli、XDri分别为分类面点的左、右间隔边界点的XDl、XDr的XAi属性值。

7.根据权利要求6所述的方法，其特征在于：所述步骤（5）中逼近误差 融合是采用以下两个公式：其中，i为分类面模型Modeli的标号，1≤i≤CC为类别数；

，

或

8.根据权利要求1-7中任一项所述的方法，其特征在于，所述步骤（6）采用带约束复合型优化方法依下式所示模型进行连续属性分割位置优化，优化目标：Min E

优化条件：

i i+1

(1)c

其中，MV（XD）为决策面点XD沿属性XAi方向间隔的分类值差，C、C 分别表示第i个、第i+1个分割点的XAi属性值，Γj为由属性 取值区间 和分割点集合SC所构成的k+1个区间 所限定的k+1个属性取值子空

1 2 k

间,SC={c,c,...,c}。

说明书

一种小样本决策树分类器构造中的连续属性分割方法

技术领域

[0001] 本发明属于决策树构造技术领域，涉及一种小样本决策树分类器构造中的连续属性分割方法。

背景技术

[0002] 决策树分类器构造过程是属性选择、属性分割两种操作的迭代的过程，直至决策树的分类误差足够小。因此属性分割优化是决策树构造的关键和核心技术。属性分割可分为离散属性分割和连续属性分割，由于离散属性取有限值，若离散属性取值较少，则直接利用这些取值点进行分割，否则作为连续属性处理。因此如何处理连续属性分割问题一直是国内外共同关注的问题，也是制约所构造决策树性能的关键技术问题。

[0003] 自上世纪九十年代，决策树学习一直是国内外共同关注的研究热点。经过20多年的发展，出现了一批如C4.5、CART、CHAID、SLIQ、PUBLIC等经典决策树分类器构造算法，提出了决策树分类器构造中连续属性分割等相关关键技术，有效地推动了决策树的应用，取得了显著的应用效果。深入分析现有的决策树构造方法可以看出，这些方法基本上都属于基于传统统计学的方法，属于基于经验风险最小化机器学习方法的范畴，只有在样本趋于无穷大时其性能才有理论上的保证。而在多数实际应用中，样本数目通常是有限的，这使很多方法都难于取得理想的效果。同时现有的决策树构法方法也存在有很多理论问题尚没有解决，如现有的基于信息熵、基尼系数等的连续属性分割点数与分割位置选择方法都属于经验性的，尚缺少理论依据。

[0004] 目前已提出了不少连续属性分割算法，包括基于信息熵、x2分布、基尼系数等方法。由于分类面的位置与形状特征是指导属性空间合理分割的根本依据，因此尽管基于信2
息熵的方法以及基于x 分布分析的方法具有一定程度的应用效果，但由于它们仅仅间接反映分类超曲面的位置与形状特征，从而限制了它们应用的有效性。

发明内容

[0005] 本发明的目的是提供一种小样本决策树分类器构造中的连续属性分割方法，以使决策树具有统计学习意义下的最优分类面，实现决策树性能的最优化。

[0006] 本发明的小样本决策树构造的连续属性分割方法步骤如下：

[0007] (1)根据训练样本集构造SVM分类面模型；

[0008] (2)确定SVM分类面模型的边界点，根据分类面点沿SVM分类面均匀分布的原则，选择合理异类边界点对，并计算各合理异类边界点对连线上的分类面点；

[0009] (3)采用现有的属性选择方法选择优先扩展属性，若无扩展属性则结束，否则转步骤(4)；

[0010] (4)根据所有分类面模型的分类面点，对于离散属性，其取值点即为分割点，转步骤(3)；对于连续属性，确定连续分割点数和初始分割位置；

[0011] (5)根据所有分类面模型的分类面点，对于每个SVM分类面模型，依该模型的决策面点和决策面与分割面的逼近误差，计算属性分割面与该SVM分类面的逼近误差E(Modeli)，并依 或 进行逼近误差E(Modeli)融合；

[0012] (6)采用带约束复合型优化方法进行连续属性分割位置优化，转步骤(3)。

[0013] 进一步的，所述步骤(1)中构造SVM分类面模型的方式为：对于多分类问题的每个类别，构造该类与其它类别所组成的2分类SVM分类面模型Modeli，i＝1，2，...，C，其中，C为类别数；对于2分类问题，则仅构造1个SVM分类面模型。

[0014] 进一步的，所述步骤(1)中对于给定的训练样本集 其中xm∈Rn为第m个样本点的属性值向量，ym∈{-1，+1}为相应的二分类类别标号，则SVM分类面模型可表示为

[0015]

[0016] 其中，γ为大于0的参数；βj，b为通过SVM训练所获得的参数，βj≠0；xj为相应的支持向量点，j＝1，...，l，l为支持向量点数。

[0017] 进一步的，所述步骤(2)中对于给定的训练样本集S，其边界点集合SB可定义为[0018] SB＝{x|x∈S，|Z(x)|＜θ，θ＜0} (2)[0019] 其中θ为给定的边界点的分类值门限。

[0020] 进一步的，所述步骤(4)中确定连续分割点数和初始分割位置的过程如下：

[0021] (41)置分割点数K＝0；对于给定的训练样本子集SΓ， 求出样本子集SΓ所限定的属性 取值区间为 其中 xki为样本子集SΓ中xk样本点的第i个属性值；

[0022] (42)求出样本子集SΓ所限定的属性取值空间中的分类面点子集其中xB1、xB2为两异类边界点，xD为位于
其连线上的分类面点，xB1∈SB、xB2∈SB；

[0023] (43)对于样本子集SΓ中边界点xB，xB∈SB，过边界点xB沿分割属性 方向求出相应的分类面点，构成分类面点子集

[0024] (44)依式MV(xD)＝|Φ(xDr)-Φ(xDl)|计算决策面点xD的分类值差MV(xD)，其中，xDl为L上xD左边最近的最大|Φ(x)|点，称为xD的左间隔边界点；xDr点为L上xD右边最近的最大|Φ(x)|点，称为xD的右间隔边界点；

[0025] (45)若K＝0，置搜索区间 否则置搜索区间 其中cK为第K个分割点的 属性值；

[0026] (46)计算分割点 其中，xDli、xDri分别为分类面点xD的左、右间隔边界点xDl、xDr的 属性值；TMV为MV(xD)的限定值；

[0027] (47)若c存在，则K＝K+1，cK＝c，cK进入分割点集合SC，转步骤(45)；若c不存在，如果K＞0结束，否则转步骤(48)；

[0028] (48)计算 其中 为分类面点 的右间隔边界点1 k
的 属性值，c 进入分割点集合SC，结束。进一步的，所述步骤(5)中决策面与分割面c 的逼近误差为 其中 SC为分割点
集合， 为分类面点的集合。

[0029] 进一步的，所述步骤(5)中逼近误差E(Modeli)融合是采用以下两个公式：

[0030]

[0031] 其中，i为分类面模型Modeli的标号，1≤i≤C；或

[0032]

[0033] 进一步的，所述步骤(6)采用带约束复合型优化方法依下式所示模型进行连续属性分割位置优化，

[0034] 优化目标：MinE

[0035] 优化条件：

[0036] (1)ci＜ci+1 i＝1，2，....，k-1 (15)[0037] (2)

[0038] 其中，Γj为由属性 取值区间 和分割点集合SC所构成的k+1个区间1 2 k
所限定的k+1个属性取值子空间，SC＝{c，c，...，c}。

[0039] 本发明针对小样本数据的决策树构造中连续属性分割问题，提出了基于SVM最优分类模型的连续属性分割点数与位置选择的新方法，所提出方法可使决策树具有统计学习意义下的最优分类面，以实现决策树性能的最优化。该方法包括连续属性分割点数选择与分割位置初选、分割位置优化方法以及相应的快速计算方法三部分，该连续属性分割方法具有属性分割点数与位置选择准确快速、实用性强、数据噪声和样本点数量与分布的影响小等特点，可满足小样本数据决策树构造中的连续属性分割实际需要，实际应用证明与其它经典决策树构造算法相比，所提出的连续属性分割方法所构造的决策树可平均减少测试误差40％以上，从而为提高决策树性能提供了新的有效技术。

附图说明

[0040] 图1是分类间隔表示示意图；

[0041] 图2是属性分割点与分类误差的关系图；

[0042] 图3是分割点表示示意图；k

[0043] 图4是e(xD，c)的取值分布图；k

[0044] 图5是调整后e(xD，c)的取值分布图。

具体实施方式

[0045] 小样本决策树构造的连续属性分割方法详述如下。

[0046] 1.连续属性分割点数选择与分割位置初选方法

[0047] 不失一般性，下面以二分类问题进行讨论。对于给定的训练样本集n其中xm∈R 为第m个样本点的属性值向量，ym∈{-1，+1}为相应的二分类类别标号，则SVM的最优分类面模型可表示为

[0048]

[0049] 其中，γ为大于0的参数；βj，b为通过SVM训练所获得的参数，βj≠0；xj为相应的支持向量点，j＝1，...，l。

[0050] 根据SVM的分类面的特性，对于任一样本点x，若x属于-1类，则必有Z(x)＜-1，若x属于+1类，则必有Z(x)＞1，因此，|Z(x)|＝1的邻近区域为分类边界区域。因此对于给定的训练样本集S，其边界点集合SB可定义为

[0051] SB＝{x|x∈S，|Z(x)|＜θ，θ＜0} (2)[0052] 其中θ为给定的边界点的分类值门限，一般取θ＜1.2。

[0053] 显然，异类边界点间连线与最优分类面的交点是SVM分类面上的理想代表性点。同时，由于利用任意两个异类边界点可以获得一个分类面点，因此直接利用各异类边界点对计算分类面点将会导致分类面点局部过密，降低计算效率，影响决策树的性能，因此需要对分类面点进行选择，使各分类面点间具有适当的距离，以限制分类面点的数量。在所有异类边界点间连线与最优分类面的交点中，根据沿SVM分类面均匀分布的原则，选择部分点作为SVM分类面上的代表性点。

[0054] 假定决策树构造过程中，对于给定的训练样本子集SΓ， 连续属性 被选择为最佳扩展属性，沿属性 的样本分布情况如图1所示，其中-1类区域和+1类区域分别为SVM分类值小于零和大于零的区域，H1、H2分别为-1类和+1类区域的边界面，H为式(1)所示的SVM最优分类面，xD为位于异类边界点xB1、xB2连线上的分类面点。过点xD作平行于属性轴的直线L，显然对于直线L上任意一点，除 属性值不同外，其它所有属性值均与xD相同。直线L与-1类边界面H1的交点为xDl，与+1类边界面H2的交点为xDr，显然Z(xDl)＝-1，Z(xDr)＝+1。

[0055] 对于直线L上任意一点x，由于除 属性值不同外，其它所有属性值均与xD相同，假设分类面点xD的 属性值为xDi，则由式(1)可以推出

[0056]

[0057] 其中，β′j＝βjexp(-γ(||xD-xj||2-(xDi-xji)2)； 为x点的 属性值；xji为第j个支持向量的 属性值。显然对于给定的SVM的分类面模型、分类面点xD和属性 直线L上所有点的β′j为固定值。因此，在属性数量多的情况下，利用式(3)计算直线L上x点的Z(x)值可显著减少计算量。

[0058] 定义函数Φ(x)为

[0059]

[0060] 对于给定的训练样本子集SΓ， 在样本子集SΓ所限定的属性取值空间Γ内，决策面点xD沿属性 方向间隔的分类值差MV(xD)定义为

[0061] MV(xD)＝|Ф(xDr)-Φ(xDl) (5)[0062] 其中，xDl为L上xD左边最近的最大|Φ(x)|点，称为xD的左间隔边界点；xDr点为L上xD右边最近的最大|Φ(x)|点，称为xD的右间隔边界点。

[0063] 从式(4)和式(5)可以看出，0≤MV(xD)≤2，对于给定的区域，分类面点的MV(xD)取值分布与区域Γ、分类面的形状与位置等因素有关。在图1中，显然Z(xDl)＝-1，Z(xDr)＝+1，因此分类面点xD沿属性 方向间隔的分类值差MV(xD)为2。

[0064] 对于图2所示的分类问题，假设水平轴为待分割的连续属性 其中C为属性 的分割面，其 属性值为c，分类面点xD的右间隔边界点xDr的 属性值为xDri。在图2(a)中，分类面点xD位于分割面的左区域，则在该区域内MV(xD)＝2，且xDri＜c。根据决策树的特性，在这种情况下，对于图中的a0和a1区域，将会出现a0区域的点与a1区域的点仅 属性值不同，而其它属性值则都相同。由于a0和a1区域被分割为决策树同一个 值区间，则必然导致无论后续其它属性如何分割，a0或a1区域的点将无法正确分类，且c-xDri越大，错分类的程度也将越大。

[0065] 在图2(b)中，此时在分割面的左区域内MV(xD)＜2，垂直属性轴的分类间隔为My。显然My越大，决策树的泛化能力越强，但决策树越大。若分割点c→xDri，则必有MV(xD)→2，My→0，这样决策树会变小，但势必会降低决策树的泛化能力。

[0066] 对于给定的样本子集SΓ和分割属性 使分割后所有分类面点xD均有MV(xD)≤2的最小分割点数为属性 的最小分割点数。

[0067] 对于给定的样本子集SΓ和分割属性 在SΓ所限定的属性取值空间内，对于任意两个决策面点，若其中一个决策面点的右间隔边界点的 属性值小于另一个决策面点的左间隔边界点的 属性值，则称两个决策面点沿属性 方向间隔不重叠。

[0068] 根据上述可以得出，对于给定的样本子集SΓ和分割属性 ，连续属性 的分割点数取决于SΓ所限定区域Γ内的MV(xD)取值分布。使分割后所形成的各区域内所有MV(xD)＜2为分割点数选择的基本依据，也是保证决策树分类性能的必要条件。为了保证决策树的分类正确性和泛化能力，连续属性 的分割点数应不少于沿属性 方向VM(xD)＝2且间隔互不重叠的分类面点数。

[0069] 为了保证属性的合理分割，在本文发明中，采用两类分类面点，其一是异类边界点连线上的决策面点，如图1中的决策面点xD，其二是过单个边界样本点沿分割属性 方向所求出决策面点，如图1中的决策面点xD0和xD1。

[0070] 基于以上分析，本发明提出的连续属性分割点确定与分割位置初选过程如下。

[0071] Step 1.置分割点数K＝0；对于给定的训练样本子集SΓ， 求出样本子集SΓ所限定的属性 取值区间为 其中 xki为样本子集SΓ中xk样本点的第i个属性值；

[0072] Step 2.求出样本子集SΓ所限定的属性取值空间中的分类面点子集其中xB1、xB2为两异类边界点，xD为位于其连线上的分类面点，xB1∈SB、xB2∈SB；

[0073] Step 3.对于样本子集SΓ中边界点xB，xB∈SB，过边界点xB沿分割属性 方向求出相应的分类面点，构成分类面点子集

[0074] Step 4.依式(5)计算决策面点xD的MV(xD)，

[0075] Step 5.若K＝0，置搜索区间 否则置搜索区间 其中K
c 为第K个分割点的 属性值；

[0076] Step 6.计算分割点 其中，xDli、xDri分别为分类面点xD的左、右间隔边界点xDl、xDr的 属性值；TMV为MV(xD)的限定值，一般取TMV＝1-2；

[0077] Step 7.若c存在，则K＝K+1，cK＝c，cK进入分割点集合SC，转Step 5。若c不存在，如果K＞0结束，否则转Step 8；

[0078] Step 8.计算 其中 为分类面点 的右间隔边界1
点的 属性值，c 进入分割点集合SC，结束。

[0079] 2.连续属性分割位置优化模型

[0080] 对于给定的训练样本子集SΓ， 在SΓ所限定的属性取值空间Γ中，分类面点的集合为 属性 为分割属性，利用算法1所求出的沿属性 的分割点集合为SC，SC1 2 k
＝{c，c，...，c}。在属性取值空间Γ中，沿属性 的每个分割点代表了一个分割面，分割面的优化目标旨在实现这些分割面与SVM决策面最优逼近，从而实现两者在性能上的逼近。下面讨论分割面的优化模型。

[0081] 对于分割点集合SC，Γ中各分类面点xD与分割点的位置关系如图3所示，图中，ck为分割面与属性轴 交点处属性 的值，直线L为过点xD作平行于属性 轴的直线， 为分k割面与直线L的交点， 点的 属性值为c，其它属性值均与决策面点xD相同。

[0082] 对于给定的分割点集合SC和分类面点xD，xD处SVM决策面与分割面ck的逼近误差定义为

[0083]

[0084] 其中，xDli、xDri分别为分类面点xD的左、右间隔边界点xDl、xDr的 属性值；Φ(ck)k k k见式(4)。e(xD，c)的取值分布如图4所示，显然e(xD，c)表示分割面c 与分类面点xD的k k
距离，当分割面c 过分类面点xD时，e(xD，c)＝0，在xD的左、右间隔边界点之间时，e(xD，k k
c)≤1，在xD的左、右间隔边界点之外时，e(xD，c)＝1。

[0085] 对于给定的分割点集合SC和决策面点xD，xD处SVM决策面与分割面集合SC的逼近误差定义为

[0086]

[0087] 对于给定的分割点集合SC和分类面点的集合为 SVM决策面与分割面的逼近误差定义为

[0088]

[0089] 同时，为了减少逼近误差波动，可将式(6)调整为

[0090]

[0091] 在本文研究中，取v＝4。调整后的e(xD，ck)的取值分布如图5所示。

[0092] 对于给定的训练样本子集SΓ， 决策面点的集合为 分割属性 和沿属性 的分割点集合为SC，连续属性位置优化模型为

[0093]

[0094] 约束条件为：

[0095] (1)ci＜ci+1 i＝1，2，...，k-1 (11)

[0096] (2)

[0097] (12)

[0098] 其中，Γj为由属性 取值区间 和分割点集合SC所构成的k+1个区间1 2 k
所限定的k+1个属性取值子空间，SC＝{c，c，...，c}。

[0099] 综上所述，本发明所提出的连续属性分割方法包括2个步骤，首先依算法1确定分割点数和初始分割位置，然后依式(10)至(12)所示的连续属性位置优化模型优化分割点位置。在本发明的研究中，所采用的优化方法为复合形约束优化方法。

[0100] 3.多分类问题连续属性分割方法

[0101] 对于多分类问题，对于每个类别，构造该类与其它类别所组成的2分类SVM分类面模型Modeli，i＝1，2，...，C，其中，C为类别数。对于2分类问题，则仅需构造1个SVM分类面模型。对于每个分类面模型Modeli，依式(2)确定模型Modeli的边界点，依根据沿SVM分类面分类面点均匀分布的原则，选择合理异类边界点对并计算各合理异类边界点对连线上的分类面点。根据所有分类面模型的分类面点。对于每个分类面模型Modeli，依该模型的决策面点和式(8)式计算属性分割面与该SVM分类面的逼近误差E(Modeli)。按式(13)或式(14)进行逼近误差E(Modeli)融合。

[0102]

[0103] 其中，i为分类面模型Modeli的标号，1≤i≤C。

[0104]

[0105] 依式(15)所示模型进行连续属性分割位置优化。

[0106] 优化目标：MinE

[0107] 优化条件：

[0108] (1)ci＜ci+1 i＝1，2，...，k-1 (15)[0109] (2)

[0110] 其中，Γj为由属性 取值区间 和分割点集合SC所构成的k+1个区间1 2 k
所限定的k+1个属性取值子空间，SC＝{c，c，...，c}。

[0111] 4.实验结果

[0112] 以双螺旋分类问题和UCI数据集中的balance scale(简称balance)、[0113] 表1计算实例

[0114]双螺旋 balance voting hepatitis iris credit-a
样本总数 168 625 232 80 150 690
训练样本数 84 157 78 53 50 173
测试样本数 84 468 154 27 100 517
分类数 2 3 2 2 3 2
属性总数 2 4 16 19 4 15
离散属性数 0 0 16 13 0 9
连续属性数 2 4 0 6 4 6

[0115] 表2计算结果对比

[0116]

[0117] congressional voting records(简称voting)、hepatitis、iris plant(简称iris)、statlog australian credit approval(简称credit-a)作为计算实例，如表1所示，基于所提出的连续属性分割方法所构造决策树计算结果与经典C4.5算法的对比如表2所示。

[0118] 从表2可以看出，对于表1所示的6个计算实例，其中4个为2分类实例，2个为多分类实例，新算法所构造决策树的总训练样本集分类误差为30.4，总测试样本集分类误差为46.7，决策树总结数为117。C4.5算法所构造决策树的总训练样本集分类误差为57.9，总测试样本集分类误差为123.9，决策树总结点数为120。SVM的总训练样本集分类误差为0，总测试样本集分类误差为53.18。与C4.5算法相比，新方法所构造决策树的大小没有明显变化，但平均训练样本集分类误差减少了47.4％，。平均测试样本集分类误差减少了
62.3％。因此，与C4.5算法相比，所提出的新方法没有明显增大决策树大小的情况下，可以显著提高所构造决策树的泛化能力。同时，与SVM相比，尽管提出方法构造的决策树的平均训练样本集分类误差有所增大，但平均测试样本集分类误差也有所减少。