一种基于动态属性权值的ID3算法改进

武文廷

摘要：该文对决策树ID3算法进行分析，针对原有ID3算法的不足之处做了一些改进，一是ID3算法多值偏差的缺点，对每个属性的信息熵引入了一个动态属性权值，使信息增益的计算结果不太依赖于属性的取值个数，且避免了类似用户兴趣度之类改进的主观性，二是对改进的基于属性权值的ID3算法在解决学生职业发展分析问题上进行可行性和有效性验证。

关键词：数据挖掘；决策树算法；ID3算法；算法改进

中图分类号：TP302 文献标识码：A 文章编号：1009-3044（2019）06-0223-03

决策树是一种基于策略选择的树型结构图，该图表示着属性和值之间的映射关系。每个节点表示着一个对象，对象的属性值则由每个分支路径表示[1]，作为非常重要的人工智能技术，在分类问题上十分常用。

决策树算法类型较多，但最有影响力的当属ID3（IterativeDiehotomieversion3）算法，即迭代二叉树生成算法3代。ID3算法的优点是通过信息增益来选择分类属性，更加的简单直观，分类的效率也较高。但也暴露出一些问题，信息增益的计算依赖于特征数目较多的特征，然而属性取值较多的那个特征不一定是全部特征中最佳的。

1 ID3算法原理

ID3算法是一种基于Occam的剃刀原理的决策树算法。它使用尽可能少的工具去做更多的事，常用于构建决策树。决策树中每个非叶子节点都对应于一个属性，分支节点用来表示属性值；叶子节点表示与从根到叶子节点的路径相对应的类型属性的值；每个非叶子节点将与属性中信息量最丰富的特征属性相关联，用信息熵的减少率是做选择测试属性的标准，即选择具有最高信息增益但尚未用于将节点作为划分属性的标准，然后该过程继续，直到生成的决策树能够对训练样本完全进行分类。

ID3算法的重点思想是通过信息增益来测量属性的选择，并在分割后选择其信息增益值最大的属性。该算法使用自顶向下的贪心搜索来遍历可能的决策范围。系统越有序，信息的熵值就越低，不然，系统越是混乱，其熵则高。因此，信息熵可以被视为系统顺序的度量。

ID3算法通过特征差异构造子节点；递归调用子节点上构造的决策树；在所有特征的信息增益很小或者不能选择任何特征之前，最终获得决策树。信息增益计算如下：

把信息增益当作是信息熵的减少值，在分类时，通过原公式和修改后的增益式（1）～式（6），计算每个属性的增益，选取所有属性中增益值是最大的属性作为决策树的根节点，属性的不同值构成树的不同分支。用与决策树的根节点相同的方法计算该子集中的增益最大的属性，递归直到每个数据集属于相同的子集，迭代地生成决策树。新数据遍历此树直到叶节点，从而完成对新数据的预测。

然而，修改后的增益具有以下限制：它可能不是总被定义（分母有可能为零），并且它可以选择具有非常低IV（Ak）的属性，而不是具有高增益的属性。为了避免这种情况，Quinlan建议从那些初始（未修改）增益中与所有属性的平均增益差不多一样高的属性中进行选择应用增益比率。

2 ID3算法优缺点

从ID3算法的描述和原理中可以看出，ID3算法有以下优、缺点：

2.1 ID3算法的优点

（1）ID3算法使用了样本集中的全部样本，提高了分类决策的准确率，也降低了由于异常数据、噪声数据所带来的错误。

（2）ID3算法采用的是自上而下的分类策略，使得分类的时间复杂度较低。

（3）ID3算法非常适用于处理离散的数据，结果呈现分层树结构，可以轻松提取“IF...Then...”分类规则，这个规则很容易理解。

2.2 ID3算法的缺点

（1）ID3算法在建树的过程中，如果选择了一个特征作为分类属性，则不会选择两次，可能导致结果局部最优，但可能不是全局的最优选择。

（2）ID3算法使用基于互信息的方法。此方法倾向于使用具有更多属性值的属性，即很容易倾向于多属性值项，但具有最多属性值的属性不一定是最佳的属性。

（3）ID3算法可以很好地处理离散化数据，但它却对连续数据处理能力非常有限，因此在对连续数据分类之前，需要进行离散化处理。

总之，ID3算法简单易于理解，很适合用于处理数据规模较大的问题，应用价值较大。

3 几种现有的ID3算法的改进分析

ID3算法在信息增益的求解过程很容易受到多值依赖问题的影响，如果属性需要很多值，那么它在分类中的作用将非常明显，仅根据计算信息增益值来盲目地选取具有大量属性的特征是不客观的。针对此现象人们在传统ID3算法的基础上提出了不少改进方法，如引入了修正函数、属性优先值等。

3.1 基于修正函数的算法

由文献[2]可知，ID3算法所产生多值依赖的原因，是Gain（A）≥Gain（A）恒成立导致的，而多值依赖影响的改进就是破坏该平衡。文献中首先将修正函数f（n）与原始计算的属性增益相乘，并通过该修正函数对属性的信息增益进行多值修正，使结果更加客观。

由以式可以得出，由于算法中引入了修正函数[sin1n]和[sin1n+1]的作用.使得[GainA']≥[GainA]不再始终成立，当属性的取值n>4时，通过修正函数的修正作用，降低了多值属性的影响，使得计算信息增益的结果更为客观。但是此方法当属性的数量小于4时校正函数不起作用，因此没有完全解决多值依赖问题。

3.2 基于固定的屬性优先值的改进算法

对于同一问题，在文献[3]中引入属性优先值。根据用户以有经验和应用需求，为属性设置属性优先值，从而影响决策树生成过程。

对每个属性Ai，定义其优先值为ai，使得满足：

该方法加重了重要属性对分类产生的影响，在生成决策树过程中属性值个数较小的属性会被放大而不被忽略。但该方法的属性优先值的概念中用户主观因素过多，可能会影响决策树的准确性。

4 一种新的基于动态属性权值的改进ID3算法

对于决策树中ID3算法的缺点，本文依赖于具有更多属性值的属性和用于计算信息增益的数学公式的特征，引入动态的属性权值，对ID3算法进一步优化改进，并使增益计算轻量化。

4.1 引入动态属性权值函數

譬如，在学生就业情况分类预测中，其数据集来分类属性的重要性相差不是太大，但属性取值个数可能有较大差别[4]，因此本文中引入一个属性权值ωi，用来减少因属性取值个数较多的特征对模型分类结果所产生的较大影响。ωi用来在属性重要性相差不大的情况下，减少取值数较多的属性的分类权重，同时加大取值数较少的属性的分类权重，以克服其多值依赖的不足。属性权值参与计算来自动矫正分类属性权重，该过程因无过的多人为参与度及干扰，从而避免了决策结果受用户主观思想的影响。

属性值个数越多，经过公式计算所得属性的权值则越小，一定程度上会抵消属性多值偏向对决策结果带来的影响。此公式在解决数据集中大量数据覆盖了小量数据的重要程度方面具有一些优势，解决了ID3算法多值依赖性的问题，且不会出现因用户主观因素过多造成影响决策树的准确性的问题。

4.2 实验验证及分析

本文通过研究甘肃林业职业技术学院信息工程学院就业信息样本集及相应属性权值，计算结果如表1所示：

其对应的属性权值曲线如图1所示，不难看出，改进的基于属性权值的ID3决策树优化算法，该算法可以适当降低取值个数较多的属性权重，且取值个数相差越大效果越明显，克服了ID3算法多值依赖的影响，且规避了类似于用户兴趣度之类改进中因主观权值参数而导致做出适用范围不大、做出个人主观性过强的决策的情况。

5 结语

本文对决策树分类中的ID3算法相关理论做了详细介绍，对比了两个现有的ID3的改进算法，针对存在的不足，从两个方面对ID3算法进行了改进优化，针对ID3算法多值偏向的缺点，对每个属性的信息熵乘以动态属性权值，使信息熵的结果不太依赖于属性的取值个数，也避免了因采用类似用户兴趣度之类的主观权值参数而导致做出不适合实际情况的决策。

参考文献：

[1] 任天成.基于数据流的相似计算及其行为预测[D].南京邮电大学，2016.

[2] 韩松来，张辉，周华平.基于关联度函数的决策树分类算法[J].计算机应用，2005（11）：197-199.

[3] 盛俊.决策树ID3算法的改进及其应用[J].扬州职业大学学报，2011（04）：38-40.

[4] 郑碧嶷.基于数据挖掘技术的高校辅助决策系统设计与实现[D].北京工业大学，2014.

【通联编辑：代影】