决策树分类算法是分类挖掘算法中较为常用的算法, 是一种自顶向下的递归算法, 常用于分类器和预测模型. 1966年Hunt等人开发研制的CLS^[1]系统, 为许多决策树算法奠定了基础. 1979 年Quinlan 提出ID3^[2]算法, 其核心思想以最大的信息增益属性作为分裂属性. 之后的许多决策树算法都是在ID3算法的基础上衍生改进的. 其中C4.5^[3] 算法就是在 ID3 算法的基础上发展的, 采用信息增益率作为属性选择的度量依据, 在处理连续性属性的时, C4.5算法将这些连续属性“离散化”, 解决了ID3算法多值偏向性的缺点, 有效避免了取值较多的属性容易被选作分裂属性的趋势, 增强了决策树模型的有效性. 但是当测试集属性值缺失率高时, C4.5算法的分类准确率会明显下降, 而且在构造树的过程中, 该算法需要多次对数据集进行顺序扫描及排序, 在进行计算时又频繁地调用对数, 增加了算法的时间开销, 从而导致算法低效^[4].

文献[5]调整了连续阈值惩罚项, 但是并没有解决决策树过度拟合问题. 文献[6]提出双重熵平均决策树算法,采用熵值拟合的方法, 提高算法运行速度, 但是没有解决空缺属性问题. 文献[7]在连续属性离散化方面进行了改进, 但并没有很好的解决过度拟合问题. 文献[8]适用范围为变精度粗糙集, 不适合一般数据分析.

本文在研究C4.5 算法的基础上提出一种优化算法, 通过对UCI数据库中 5个数据集进行实验, 实验结果表明, 改进后的算法极大的提高了运行效率.

1 C4.5算法理论

C4.5算法是在ID3的基础上加进了对连续型属性、属性值空缺情况的处理, 通过生成树和树剪枝两个阶段来建立决策树. C4.5算法通过计算每个属性的信息增益率(information GainRatio), 最后选出具有最高信息增益率的属性给定集合S的测试属性, 再根据测试属性值建立分支, 采用递归算法, 得到初步决策树. C4.5算法的相关计算公式如下^[9]:

(1)期望信息(也称信息熵) 设S是S_i个数据样本的集合, 假定类标号属性有m个不同值, 定义m个不同类T_i (i=1, …, m). 设S_i是类T_i中的样本数. 对一个给定的样本分类所需的期望值为:

$Info(S) = - \sum\limits_{i = 1}^m {\frac{{{s_i}}}{s}} {\log _2}\frac{{{S_i}}}{S}$

(1)

(2)信息增益 由属性A划分成子集的信息量为:

$E(A) = Inf{o_A}(S) = \mathop \sum \limits_{j = 1}^v \frac{{{S_i}}}{S}Info({S_{ij}})$

(2)

信息增益为原来的信息需求与新的需求之间的差.

$\text{即}{{G}}ain(A) = Info(S) - E(A)$

(3)

(3)信息增益率C4.5算法中引入了信息增益率, 属性A的信息增益率的计算公式为:

${{GainRatio(A)}} = \frac{{{{Gain}}({{A}})}}{{{{SplitE}}({{A}})}}$

(4)

$SpliE(A) = - \mathop \sum \limits_{i = 1}^k \frac{{|{S_i}|}}{{|S|}}{\log _2}\frac{{|{S_i}|}}{{|S|}}$

(5)

C4.5算法采用后剪枝技术对生成的决策树进行剪枝操作, 形成决策树模型, 根据建立好的模型, 生成一系列IF-THEN 规则, 实现对训练集的分类.

2 改进的C4.5算法 2.1 决策分类过程中空缺属性值处理研究

(1) 延伸贝叶斯分类算法

决策树进行分类时, 测试样本数据中可能存在缺失某些属性值. 传统的决策树算法在处理缺失属性值时, 一般采用抛弃缺失属性值的样本, 或重新赋予训练样本该属性的常见值^[10]. C4.5算法采用概率分布的填充法来处理缺失属性值, 具体执行过程: 首先为某个未知属性的每个可能值赋予一个概率, 根据某节点上属性不同值的出现频率, 这些概率可以再次估计^[11]. 虽然C4.5算法有很强的处理噪声数据的能力, 但当训练集合属性值的缺失率很高时, 使用该算法构建的决策树模型的结点数更多, 模型更为复杂, 而且分类准确率也会下降^[12]. 鉴于朴素贝叶斯分类具有坚实的理论基础、较小的出错率. 本文提出一种基于朴素贝叶斯定理方法^[13], 来处理空缺属性值.

假设数据样本为n维向量空间, V={V₁, V₂, V₃, …, V_i} 若该数据样本有C₁, C₂, C₃, …, C_m个类别属性取值, 那么基本贝叶斯将未知类别的样本V归到类别C_i, 当且仅当:

$\frac{{p({c_i})p(v|{c_i})}}{{p(v)}} > \frac{{p({c_j})p(v|{c_j})}}{{p(v)}}$

等价 $p({c_i})p(v|{c_i}) > p({c_j})p(v|{c_j})$ .

若V的m个属性互相独立, 那么

$p(v|{c_i}) = \prod\limits_{k = 1}^n {p({v_k}|{c_i})} $

继而推出:

$p({c_i})\prod\limits_{k = 1}^n {p({v_k}|{c_i})} > p({c_j})\prod\limits_{k = 1}^n {p({v_k}|{c_j})} $

所以, $\dfrac{{{s_i}}}{s}\prod\limits_{k = 1}^n {p({v_k}|{c_i})} > \dfrac{{{s_j}}}{s}\prod\limits_{k = 1}^n {p({v_k}|{c_j})}$ (因为 $p({c_i}) = \dfrac{{{s_i}}}{s}$ ).

故将未知类别的样本X归到类别Ci,当且仅当

$\frac{{{s_i}}}{s}\prod\limits_{k = 1}^n {p({v_k}|{c_i})} > \frac{{{s_j}}}{s}\prod\limits_{k = 1}^n {p({v_k}|{c_j})},\;\; \\ 1 <= {{j}} <= {{m}}\;\;\text{且}\;\;{{j}} \ne {{i}}$

根据上述原理可以实现对多维空缺属性的处理:

$\begin{split} &\dfrac{{{s_i}^\prime }}{s}\prod\limits_{k = 1}^n {p({{v''}_k}|{{c'}_i})} > \dfrac{{{{s'}_j}}}{s}\prod\limits_{k = 1}^n {p({{v''}_k}|{{c'}_j})} \\ &1 <= {{j}} <= {{m}}\;\;\text{且}\;\;{{j}} \ne {{i}} \end{split}$

(2) 空缺属性值处理过程

本文采用上述算法处理空缺属性, 大致流程如下:

① 读入测试数据.

② 若数据集中没有空缺属性值, 则把数据压入D_i集合; 如果测试数据集中含有空缺属性值, 采用“样本空缺属性个数排序, 越少越排前, 反之则排后. ”的原则插入到D₂集合.

③ 返回第一步, 直到测试数据集中所有数据都检测结束. 最后形成D_i、D₂两个集合. 其中D_i中存放没有空缺属性值, D₂中存放包含空缺属性的信息.

④ 取出D₂中的记录数据, 为缺失属性赋值计入D_i.

⑤ 递归调用上述第④步, 直到D₂中记录为0.

2.2 改进思想及改进计算方式

虽然C4.5算法具有建模速度快、准确率高、易于理解、灵活简单等优点, 但是该算法在构造树的过程中, 需要多次对数据集进行顺序扫描及排序,在进行计算时又频繁地调用对数, 增加了算法的时间开销, 从而导致算法低效. 针对以上缺点, 本文对C4.5算法的计算公式进行精简优化, 从减小计算时间上提出一种改进算法命名为N-C4.5算法. 公式简化如下:

假设S是n维有穷离散数据集, S中只有正反两种情形, 分别表示为YS 、NS, 其中正例YS的记录数为m, 反例NS的记录数为n, 根据式(1)数据集S分类所需的期望值为:

$Info(S) = - \frac{m}{{m + n}}\log _2^{\frac{m}{{m + n}}} - \frac{n}{{m + n}}\log _2^{\frac{n}{{m + n}}}$

假设决策树的根为A属性, A属性的取值为{A₁, A₂, …, A_i}, 利用属性A将数据集S分为{S₁,S₂, …, S_i}个子集, 其中S_i为S中属性A取A_i值的样本实例数据, 那么由属性A划分成子集的信息量为

$I({S_i}) = - {\frac{{{m_i}}}{{{m_i} + n_i}}}\log _2^{\frac{{{m_i}}}{{{m_i} + {n_i}}}} - {\frac{{{n_i}}}{{{m_i} + n_i}}}\log _2^{{{\frac{{{n_i}}}{{{m_i} + n_i}}}}}$

在数据集D中计算属性X的信息熵公式为

$\begin{split}Inf{o_A}(S) &= \sum\limits_{i = 1}^v {\frac{{{m_i} + {n_i}}}{{m + n}}} I({S_i})\\ &= \frac{1}{{(m + n)\ln 2}}\sum\limits_{i = 1}^v { - {m_i}\ln \frac{{{m_i}}}{{{m_i} + {n_i}}} - {n_i}\ln \frac{{{n_i}}}{{{m_i} + {n_i}}}}\end{split}$

$\begin{split} Inf{o_A}(S) &= \sum\limits_{i = 1}^v {\frac{{{m_i} + {n_i}}}{{m + n}}} I({S_i}) \\ & = \frac{1}{{(m + n)\ln 2}}\sum\limits_{i = 1}^v {( - {m_i}\ln \frac{{{m_i}}}{{{m_i} + {n_i}}} - {n_i}\ln \frac{{{n_i}}}{{{m_i} + {n_i}}}} ) \end{split} $

$Inf{o_A}(S) = \sum\limits_{i = 1}^v {( - {m_i}\ln \frac{{{m_i}}}{{{m_i} + {n_i}}} - {n_i}\ln \frac{{{n_i}}}{{{m_i} + {n_i}}})} $

(由于 $\dfrac{1}{{(m + n)\ln 2}}$ 为常数, 故可以简化).

根据无穷小原理 $\ln (1 + x) \approx x$ , 那么:

$\ln \frac{{{m_i}}}{{{m_i} + {n_i}}} = \ln (1 - \frac{{{n_i}}}{{{m_i} + {n_i}}}) = - \frac{{{n_i}}}{{{m_i} + {n_i}}}$

$\text{同理},\ln \dfrac{{{n_i}}}{{{m_i} + {n_i}}} = = - \dfrac{{{m_i}}}{{{m_i} + {n_i}}} $ .

$\begin{split}Inf{o_A}(S) &= \sum\limits_{i = 1}^v {\left( - {m_i}\ln \frac{{{m_i}}}{{{m_i} + {n_i}}} - {n_i}\ln \frac{{{n_i}}}{{{m_i} + {n_i}}}\right)}\\ &= \sum\limits_{i = 1}^v \left({\frac{{{m_i}{n_i}}}{{{m_i} + {n_i}}}} + \frac{{{m_i}{n_i}}}{{{m_i} + {n_i}}}\right) = \sum\limits_{i = 1}^v {\frac{{2{m_i}{n_i}}}{{{m_i} + {n_i}}}} \end{split}$

$Inf{o_A}(S) = \sum\limits_{i = 1}^v {\frac{{{m_i}{n_i}}}{{{m_i} + {n_i}}}} (\text{常数2省略})$

信息增益: $Gain(A) = Info(S) - Inf{o_A}(S)$ .

$\begin{split} SplitE(A) &= - \frac{{{n_i}}}{{{m_i} + {n_i}}}\log _2^{\frac{{{n_i}}}{{{m_i} + {n_i}}}} - \frac{{{m_i}}}{{{m_i} + {n_i}}}\log _2^{\frac{{{m_i}}}{{{m_i} + {n_i}}}} \\ &= \sum\limits_{i = 1}^v {\frac{{2{m_i}{n_i}}}{{\ln 2{{({m_i} + n{}_i)}^2}}}} \end{split} $

$ SplitE(A) = \sum\limits_{i = 1}^v {\frac{{{m_i}{n_i}}}{{{{({m_i} + n{}_i)}^2}}}} \left(\text{因为}\frac{2}{{\ln 2}}\text{为常数可简化}\right) $

信息增益率: $GainRatio(A) = \dfrac{{Info(S) - Inf{o_A}(S)}}{{SplitE(A)}}$ .

改进后的计算公式使用四则混合运算代替原来的对数运算, 可以使计算效率得到提升. 原C4.5算法的时间复杂度为O $({n^2}\log _2^n)$ , 改进后的算法时间复杂度为O $({n^2})$ , 新算法去掉了对数运算, 优化了时间复杂度.

2.3 N-C4.5算法实际应用

为了验证算法正确性, 这里以顾客购买计算机的样本信息S为例, 具体样本记录如表1所示. 使用改进后的算法构建决策树, 命名为N-C4.5算法. 该数据集S有age、income、student、credit_rating、buy 5个属性, 其中buy为类标号属性, 有两个取值{yes,no}, S数据集的前4个属性为分裂属性, 并且每个属性都是离散化的. 这里根据每个人的age、income、student、credit_rating 来进行分类, 判断顾客是否购买计算机.

对客户购买计算机的样本信息按照改进以后的算法构建决策树, 利用改进后的公式计算信息熵、信息增益、分裂信息量、以及信息增益率, 同时选择最大信息增益率作为分裂结点, 采用递归算法构建决策树. 在数据集S中属于类别“yes”的有9个, 属于类别“no”的有5个, 根据改进后的公式计算过程分如下五步.

Step1. 计算分类所需的期望信息

$ Info(S) = \frac{{mn}}{{{{(m + n)}^2}}} = \frac{{9 \times 5}}{{{{(9 + 5)}^2}}} = 0.230 $

Step2. 计算每个属性的信息熵

$\begin{split} &Info(age) = \frac{{2 \times 3}}{{2 + 3}} + \frac{{4 \times 0}}{{4 + 0}} + \frac{{3 \times 2}}{{3 + 2}} = 2.4\\ &Info(income) = 3.083\\ &Info(student) = 2.571\\ &Info(credit\_rating) = 3.0 \end{split}$

Step3. 计算每个属性的信息增益

$\begin{split} Gain(age) &= Info(S) - Info(age) \\ & = 0.{\rm{23}}0 - {\rm{2}}.{\rm{4}} = - {\rm{2}}.{\rm{17}}0 \end{split} $

$Gain(income) = 0.{\rm{23}}0 - 3.083 = - {\rm{2}}.783$

$Gain(student) = 0.{\rm{23}}0 - 2.571 = - {\rm{2}}.341$

$Gain(credit\_rating) = 0.{\rm{23}}0 - 3.0 = - {\rm{2}}.8$

Step4. 计算每个属性的分裂信息度量

$\begin{split} &SplitE(age) = \frac{{5 \times 4 \times 5}}{{{{(5 + 4 + 5)}^2}}} = 0.510\\ &SplitE(income) = 0.490\\ &SplitE(student) = 0.250\\ &SplitE(credit\_rating) = 0.245 \end{split}$

Step5. 信息增益率

$ \begin{split}&GainRatio(age) = \frac{{ - 2.170}}{{0.510}} = - 4.255\\ &GainRatio(income) = - 5.680\\ &GainRatio(student) = - 9.346\\ &GainRatio(credit\_rating) = - 11.430 \end{split}$

由计算结果可知, age 属性的信息增益率最大, 所以选择age 作为分裂属性, 将原数据集分为youth、middle、senior三个子集, 采用递归算法计算每个属性的信息熵、信息增益、分裂信息量、信息增益率, 对于youth子集, 经计算得出student信息增益率最大, 选择student作为测试属性; 对于middle子集全部归为yes 类, 所以不需要进行分类; 而对于senior子集, 通过计算得知, credit_rating信息增益率最大, 因此选择credit_rating作为测试属性, 根据所有结点, 可以得出购买计算机数据集采用N-C4.5算法构造的决策树如图1.

由图1可以看出采用N-C4.5算法构造的决策树与使用原C4.5算法得到的决策树结构完全相同, 但C4.5算在计算的过程中调用了大量的对数, 而N-C4.5算法却只需要采用简单的混合运算即可, 因此运算效率大幅度提高.

3 实验结果比较分析

为了验证N-C4.5算法的性能, 本实验选择UCI数据库中 5个数据集进行仿真实验, 实验数据的基本信息见表2 , 实验硬件配置: 内存 4 GB, CPU 2.50 GHz , 使用Window7 操作系统, 采用Java 语言在WEKA 平台中进行仿真实验. 仿真实验时, 首先利用延伸的贝叶斯分类算法填充多维空缺属性, 该方法会生成空缺属性的各种可能取值组合, 接着遍历各种组合, 按公式计算值并记录最大值即可; 然后利用改进后的公式计算信息熵、信息增益、分裂信息量、以及信息增益率, 最后选择最大信息增益率作为分裂结点, 采用递归算法构建决策树.

Iris数据集是构建决策树挖掘中最典型的一组数据, 共有150条记录, 有4个分裂属性, 类标记属性为3种, 人为添加部分缺失信息, 缺失属性为sepal width, 共有30条缺失记录, 使用Iris数据集对改进前后的算法进行5次仿真实验, 实验结果如图2所示.

由图2可以看出, 对于Iris 数据, N-C4.5算法的运行时间短, 优化效果明显. 为了验证N-C4.5算法算法的效率, 对于其他4组数据集, 同样都分别使用改进后的N-C4.5算法与C4.5算法进行仿真实验, 测试时每个数据集都运行5次, 建模时间取5次的平均值, 建模时间如表3所示.

由表中可以看出, 数据样本的大小会影响算法的运行时间, 一般情况下, 测试数据样本数据量越大, 需要运行的时间越长. 算法改进前后的比率都大于1, 正确率的提升都是正值, 可以得出结论: N-C4.5算法的建模时间明显优于C4.5算法, 分类准确率也高于原C4.5算法.

4 总结

虽然C4.5算法具有建模速度快、准确率高、易于理解、灵活简单、以及处理噪声数据的能力强等优点, 但当属性值缺失率高时, 分类准确率会明显下降; 在构建决策树时, 需要多次扫描、排序数据集、以及频繁调用对数等缺点. 本文提出一种改进的决策树分类算法. 采用一种基于朴素贝叶斯定理方法, 来处理空缺属性值, 提高分类准确率. 通过优化计算公式, 改进后的N-C4.5算法使用四则混合运算代替原来的对数运算, 减少构建决策树模型的运行时间, 使计算效率得到提升.