基于属性离散和特征度量的决策树构建算法

王磊，刘雨，刘志中，齐俊艳

(河南理工大学 计算机科学与技术学院,河南 焦作 454000)

0 引 言

决策树算法是解决分类问题最有效的方法之一[1]。传统的基于信息熵的决策树算法如ID3[2]、C4.5[3]等，在对数据进行分类时，存在多值属性偏向、生成的决策树结构过大以及算法效率较低等问题。然而在大数据时代，数据量越来越大，场景越来越复杂，导致传统的基于信息熵的决策树算法难以满足精准分类的需求[4]。

近年来，随着计算能力提升，研究人员通过不同的特征度量方法来优化决策树的分类性能。MU Y等[5]在决策树算法的基础上引入皮尔逊相关系数，利用新的特征度量方法确定构建决策树中最优分割属性和分割点，但未能考虑到属性之间的关系；YANG S等[6]在ID3算法的基础上，引入了平衡理论函数，减少不同值属性的权重，并通过一种新的数据离散化方法对属性进行转换，解决了经典的ID3算法无法处理连续数值属性的问题；王文霞[7]针对传统C4.5算法需要多次扫描，导致运算效率低的问题，提出将连续属性的简单分裂改进为最优化节点分裂，提高了算法效率；安葳鹏等[8]在决策树C4.5算法的基础上引入肯德尔和谐系数，用于解决条件属性相关性和简化计算过程，提高了算法的性能，但是在多值属性偏向的问题上未能得到很好解决；亓常松等[9]提出条件属性离散度的概念，在时间复杂度上相比基于信息熵的方法也有所提高，但是无法对含有连续性属性的数据集进行处理，所以具有一定局限性。

本文针对基于信息熵的决策树算法存在的问题，提出一种结合聚类离散化的离散比分割方法。利用离散比理论计算取值较多的属性在该条件属性中的权值，在构建决策树的过程中取值更新时，避免多值属性偏向问题，并可解决在传统基于熵过程的决策树算法中为得到分割节点，需使用大量的对数运算从而导致计算复杂度高的问题。其次，针对基于信息熵决策树算法中处理连续型数值性能不佳的问题，引进K-means聚类算法[10]对数据进行离散化处理，以期提高算法的精度。

1 基于信息熵的属性选择方法

信息熵是度量样本集合纯度最常用的一种指标[11]。经典的ID3算法和C4.5算法就是采用基于信息熵的方法来进行属性分割。

假设在样本数据集S中，有s种类别的数据。在数据集中，可以计算出该数据中的信息熵,即

(1)

式中，pi为类别i样本数量所占总样本的比例。

选择特征A作为决策树判断节点时，特征A作用后的信息熵为InfoA(S),计算式为

(2)

式中，k为样本S被分成k个部分。

信息增益表示数据集S在特征A的作用后，其信息熵减少的值。公式为

Gain (A)=Info (S)-InfoA(S)。

(3)

Gain (A)值最大的特征就是对应决策树最佳属性分割节点，对划分的每个分支执行以上操作，最后得到基于信息熵的决策树,但是可能存在决策树中某棵子树重复的问题，或者是一个属性被重复使用，这样就会降低分类的整体效率，其次是在计算熵过程中存在大量的对数运算，直接增加了算法的时间复杂度[12]。

2 融合离散比的属性选择算法

2.1 基于离散比的节点分割

本文提出一种离散比的决策树节点分割方法，计算出各个条件属性的离散值，将离散值作为决策树属性分割的标准。构造树中每一步所选择的划分属性都应使划分后的子集中样本同属一类，也就是选择对样本分类一致性程度最高的条件属性，这才有可能构造出比较小且精度高的决策树。

其中，具体算法模型的构建如下。

在条件属性Aj中属于决策属性类Bp的平均值为

(4)

第j个条件属性所有值的平均值为

(5)

两者的加权平方和为(相对重要性)

(6)

条件属性Aj中每个值与所有值的平均值之差的平方和为(整体重要性)

(7)

则最后计算离散比值的公式为

(8)

离散比算法的具体操作如下。

Step1 计算每个结果类中条件属性出现的最大频率与该类中总记录数的比值，记为该结果类中条件属性的相对重要性。

Step2 计算每个结果类中的最大频率之和与条件属性中总记录数的比值，记为该属性的整体重要性。

Step3 计算结果类中条件属性的相对重要性离散度与该属性的整体离散度的比值。

Step4 其比值的平方根为该条件属性的离散比值。

2.2 基于离散比的决策性能分析

若D2(λ′)-D2(λ)的取值恒小于0，则该算法能够很好地解决多值偏向问题。

(9)

(10)

故可以对式(10)进行约减，即

(11)

由于t1-t2<0，则可以得到D2(λ′)-D2(λ)<0恒成立，即提出的算法可以有效地解决多值属性偏向问题。

同时，由上述推算过程可以得出,基于离散比决策树算法的时间复杂度为O(n)，而基于信息熵算法的时间复杂度为O(n2)，基于离散比决策树算法有效地降低了算法的时间复杂度。

2.3 基于K-means聚类的连续属性离散化

基于离散比的属性分割方法可以对数值型数据进行处理，但是首先需要对这些数据进行离散化处理[14]。在无监督离散化中，最常用的3种方法分别是:等宽法、等频法、K-means聚类算法[15]。其中K-means聚类方法在处理数据集时表现出良好的性能：(1)算法需要参数的数量少；(2)在数据分布中不需要任何先验假设；(3)算法简单，易实现；(4)聚类簇的个数可以自己确定等优点[16]。离散化处理的具体过程如下。

Step1 输入训练数据集D=x(1),x(2),…,x(m)，聚类簇数k，从D中随机选择k个样本作为初始“簇中心”向量：μ(1),μ(2),…，μ(k)。

Step2 令Ci=φ(1≤i≤k)，当1≤j≤m时，计算样本x(j)与各“簇中心”向量μ(i)(1≤i≤k)的欧式距离：

(12)

根据距离最近的“簇中心”向量确定x(j)的簇标记：λj=argmini∈{1,2,…,k}dij，将样本x(j)划入相应的簇：Cλj=Cλj∪{x(j)}。

Step4 直到当前的“簇中心”向量均未更新，结束循环。

Step5 结束离散化过程，输出簇划分结果：C=C1,C2,…,Ck。

聚类算法实现数据离散化的主要核心思想就是将同一个簇内的属性值做统一标记，其主要步骤流程如图1所示。

图1 K-means聚类离散化流程图

2.4 基于离散比的决策树构建

在构建树的过程中，选取离散比[17]作为属性分割的标准，选取离散值最大的属性作为根节点，其他节点根据离散比的大小依次按照构造决策树的规则进行划分，具体构建决策树的步骤为如下。

Step1 在数据集D中，将所有特征看作分开的节点。

Step2 遍历所有的特征，遍历当前特征的所有分割方式，根据离散比分割方法找到最佳分割点，将数据划分为不同的子节点，计算每个子节点的离散比。

Step3 在遍历所有特征时，寻找最优特征以及最优分割方式，若当前属性离散比最大，则对该组数据进行划分操作。

Step4 对新的节点递归操作,步骤(2)和(3)，直到每个子节点集为空。

Step5 完成决策树的构建。

3 结果与分析

3.1 离散比方法具体实现

以一组天气信息数据为例，详细介绍算法实现过程，数据集中包括条件属性“天气”、“温度”、“湿度”和“风速”以及决策属性“活动”，决策属性“活动”中包括“取消”和“进行”，如表1所示。

表1 样本数据集

其中，“天气”的好坏是决定活动是否进行、取消的一方面因素。决策属性为“进行”和“取消”，条件属性“天气”中有3个子属性分别为“晴”、“阴”、“雨”(表2)，天气的离散比计算过程如下。

表2 天气数据

则

同理，可得

D(温度)=0.388 5，D(湿度)=0.248 0，D(风速)=0.147 0。

根据计算结果可知，D(天气)>D(温度)>D(湿度)>D(风速)，因此，选取天气作为根节点，根据决策树构造方法生成的树结构如图2所示。

图2 决策树结构图

3.2 UCI数据集实验与分析

3.2.1 实验数据集

为了验证离散比算法的泛化能力及适应性，选取UCI[18]数据集中的Energy Efficiency(E.E.),Drug Review(D.R.),EMG Gestures(E.G.),Mechanical Analysis(M.A.),Parking Birmingham(P.B.),User Knowledge (U.K.)6个公开数据集，数据集的样本数量从768到3 571不等，同时条件属性个数和决策属性个数也不同，并对6个数据集中的部分连续属性数值进行K-means聚类离散化处理，使离散比决策树分类模型的验证更具说服力。数据集的具体特征信息如表3所示。

表3 UCI数据集特征信息

3.2.2 实验评价指标

在本文实验中，笔者采用4种性能评价指标：正确率(Accuracy)、精确率(Precision)、召回率(Recall)和F1(F-score)值。其中精确率衡量分类效果，召回率衡量分类效率，F1值用来衡量分类算法的性能[18]。各评价指标的计算公式为

(13)

(14)

式中：TP为预测结果的真正例；FN为假反例；FP为假正例；TN为真反例。

3.2.3 实验环境及结果分析

根据以上性能评价指标进行实验，本实验是在Pycharm平台上进行，采用python语言。实验硬件环境：CPU-Intel(R)Core(TM)i5-7200U，3.40 GHz，内存为8 GB。由于改变了基于信息熵决策树的计算方法，所以将本文提出的决策树改进算法(D-decision)与两种基于信息熵决策树改进算法(K_C4.5算法[8])(Id3_improved算法[6])进行对比，检验D-decision算法在数据集上的分类性能，并观察在不同数据集上各评测指标的精度。其实验结果如表4所示。

表4 UCI数据集的分类准确率

在实验中，通过10折交叉验证计算分类的准确率，从表4可以看出，D-decision模型的准确率在各个数据集中都普遍优于基于信息熵的分类模型，在U.K.数据集中准确率可达98.5%，由此可以看出该方法的有效性。同样算法复杂度低是算法的另一个优点，为了验证模型在时间复杂度方面的优势，采取模拟数据的方式，并将模拟数据容量不断增大，检验3种算法在不同数据集下时间复杂度方面的特性，实验结果如图3所示。

图3 3种算法运行时间对比

实验结果表明，在3种算法的运行时间对比中，随着样本容量的增加,算法运行时间都随之增加，但在相同的样本容量情况下，D-decision算法在不同数据集下的运行时间都是最少的，ID3_improved运行时间次之，K_C4.5运行时间最长。由此可以证明，在基于离散比的计算方法下，减少了冗余的对数运算，对分类效率有了明显的提高。

通过计算数据集的精确率(P)，召回率(R)和F1数值，对提出的决策模型性能进行分析，将改进算法(D-decision)与基于熵运算的ID3_improved算法和K_C4.5算法进行比较,实验结果如表5所示。

表5 3种算法性能比较

实验结果表明，对于E.G.数据集，K_C4.5和D-decision算法在精确率上结果一致，ID3_improved和D-decision算法在召回率上结果一致。在其他5个数据集中，提出的D-decision算法在精确率、召回率方面均比其他2种基于信息熵的算法高。对于F1值，D-decision算法比另外2个算法都略高。由此可以表明，结合K-means聚类离散化和离散比理论的决策树分类效果与效率有了明显提高。

为了更直观观察和分析各种评测指标，使用折线图比较3种算法在不同特征集上的分类结果。从图4～6可以看出,本文提出的方法，在各种评测指标上均优于基于熵过程的决策树算法。

图4 3种算法的精确率对比

图5 3种算法的召回率对比

4 结 语

本文提出了一种新的基于离散比理论的属性分割方法，与传统需要大量对数运算的基于信息熵决策树算法不同，主要通过对连续性属性进行K-means聚类离散化及运用离散比的方法进行属性分割，使选择属性时不仅仅只参照属性取值出现的次数，避免了多值属性偏向的问题，同时省去了计算熵过程中大量的对数运算，明显降低算法时间复杂度，提高运算效率。根据此思想，通过对6个公开数据集以及与最近提出的具有代表性的决策树改进算法进行实验对比，结果表明，进行数据分类时D-decision算法在时间复杂度和准确率上都更具有优势。

图6 3种算法的F1值对比

此外，改进的决策树算法针对某些特征不平衡数据集的拟合仍存在类别分布不均匀的问题，如何在分类拟合适应性强的前提下，提高算法性能，使决策树算法在分类上更加智能化和精确化是下一步研究目标。