基于改进ID3算法的数据分类方法

孟雅蕾，周千明，师红宇，马 楠

(1. 西安工程大学计算机科学学院，陕西 西安 710048；2. 中国石油长庆油田分公司物资装备处，陕西 西安 710021)

1 引言

由Quinlan提出的ID3算法是目前最具有影响力的一种决策树构造算法。ID3算法由于理论清晰，方法简单，学习能力强，常用于处理大规模的学习问题，是数据挖掘和机器学习领域中一个极好的范例，也是一种知识获取的有用工具[1]。

ID3算法虽是常用的分类算法，但在选择属性时存在属性偏向的问题，偏向选择取值较多的属性作为分支节点[2]。针对ID3算法的多值偏向问题，许多学者进行了相关的改进工作：文献[3]引进属性相似度和性价比值两者对ID3算法进行改进；文献[4]提出了一种基于斯皮尔曼等级相关系数的ID3决策树构造优化算法，利用相关系数克服了ID3算法在多值属性偏向方面的问题；文献[5]利用属性偏向对ID3算法进行改进，利用凸函数的性质简化了ID3算法中信息增益的计算；文献[6] 在决策树算法的节点中增加了贝叶斯分类算法作为预处理贝叶斯节点，形成增量学习决策树，减少了决策树的修剪时间。虽然多位学者改进的ID3算法，在一定程度上克服了属性偏向问题，但效率和速度低，不能用于增量模型。本文通过研究和学习相关的改进算法，提出一种新的数据分类方法，该方法可以有效的控制属性选择时的多值偏向问题，提高预测的准确率和算法的效率，用于增量模型。

2 ID3算法的改进

ID3算法在生成相应的决策树时采用信息增益作为属性选取的标准，根据拆分前后属性信息增益的差值大小来判断属性的信息增益的变化，确定分支节点。

本文提出的数据分类方法通过对信息增益的修正和属性偏向阙确定均衡系数，利用均衡系数对ID3算法得到的信息增益进行优化，得到优化信息增益，根据优化信息增益得到决策树的根节点、各分支节点，对属性进行分类，构建决策树。信息增益的修正、属性偏向阙、均衡系数、优化信息增益的思想和论证如下文所示。

2.1 信息增益

根据ID3算法得到属性Ai在训练集S上的条件熵E(Ai)、信息增益Gain(Ai)；

条件熵E(Ai)、信息增益Gain(Ai)的计算公式如下

(1)

(2)

Gain(Ai)=I-E(Ai)

(3)

2.2 信息增益的修正

对属性Ai的信息增益Gain(Ai)进行修正，得到修正信息增益Gain′(Ai)，其表达式如下：

Gain′(Ai)=f(n1)Gain(Ai)

(4)

2.3 属性偏向阙

当某个条件属性的取值个数非常接近总数时，分裂信息度可能非常小或者为零，这会导致增益率修正补偿过度。为避免这种情况，引入属性偏向阈T，对多值偏向性的程度进行度量和控制，对于集合S，有n2个条件属性，属性偏向阈T通常取值为所有条件熵E(Ai)的平均值，其表达式如下

(5)

其中，n2表示条件属性的个数。

2.4 均衡系数

为了平衡多值偏向对信息增益的影响和信息增益修正补偿过度，本文引入均衡系数的概念。均衡系数R(Ai)由修正信息增益Gain′(Ai)和属性偏向阈T得到。通过修正参数修正后的信息增益和属性偏向阈分别对应电阻R1和R2，均衡系数对应电阻R’，本方法的均衡系数R(Ai)是运用等效电阻原理定义的。

在计算均衡系数R(Ai)之前，若属性偏向阈T小于条件熵E(Ai)，令E(Ai)=T，重新计算信息增益Gain(Ai)、修正信息增益Gain′(Ai)；对属性偏向阈T大于条件熵E(Ai)的属性选择信息增益Gain(Ai)进行计算，这样就有效避免了补偿过度的情况。均衡系数R(Ai)公式如下：

(6)

即

(7)

均衡系数R(Ai)的作用效果，等效于修正后的信息增益Gain′(Ai)和属性偏向阈T两者共同作用的效果达到的最优值。

2.5 优化信息增益

利用均衡系数R(Ai)对信息增益Gain(Ai)进行优化，得到优化信息增益Gain(Ai)new，根据优化信息增益Gain(Ai)new得到决策树的根节点，优化信息增益Gain(Ai)new公式如下：

Gain(Ai)new=Gain(Ai)×R(Ai)

(8)

重复2.1-2.5，得到决策树的各分支节点，对属性Ai进行分类。

通过本方法得到的优化信息增益Gain(Ai)new，能避免多值偏向，证明如下：

(9)

由此可知式(9)的恒成立是造成多值偏向问题的本质，所以要解决多值偏向问题只要避免式(9)恒成立即可。

(10)

3 算法实例

采用商务购车顾客数据库(如表1所示)作为训练集，对数据进行选取、预处理和转换后得到样本集合，该集合包含4个条件属性；喜欢的季节(含4个属性值：春、夏、秋、冬)、是否商务人士(含2个属性值：是、否)、收入(含3个属性值：高、中、低)、驾车水平(含2个属性值：良好、一般)。样本集合根据类别属性“是否买车”(含有2个属性值：买、不买)进行划分。

表1 数据训练集

利用本文提出的数据分类方法对训练集中的各个属性进行分类，具体过程如下：

步骤1：根据ID3算法得到各个属性在训练集上的信息熵I、条件熵E(Ai)及信息增益Gain(Ai)：

步骤1.1：根据式(1)计算分类属性“买车”的信息熵I。

根据上表可以看到，分类属性“买车”共有11条记录，其中7条记录为“买”，4条记录为“不买”，根据公式计算分类属性“买车”的信息熵为

步骤1.2：根据式(2)计算各条件属性的条件熵E(Ai)。

测试的训练集共有四个条件属性“喜欢的季节”、“是否商务人士”、“收入”、和“驾车水平”。计算分两个过程，首先计算出不同属性值的条件熵，如“喜欢的季节”为“春”、“夏”、“秋”和“冬”，接着再计算整个属性的条件熵。

属性“喜欢的季节”包括四个属性值“春”、“夏”、“秋”和“冬”，它们的条件熵分别为：

由“春”、“夏”、“秋”和“冬”的条件熵，可以求出属性“喜欢的季节”的条件熵为

同理，可计算出E(是否商务人士)=0.796，E(收入)=0.5898，E(驾车水平)=0.796。

步骤1.3：根据式(3)计算各条件属性的信息增益。

Gain(喜欢的季节)=I(买车)-E(喜欢的季节)=0.4，

Gain(是否商务人士)=I(买车)-E(是否商务人士)=0.149，

Gain(收入)=I(买车)-E(收入)=0.355，

Gain(驾车水平)=I(买车)-E(驾车水平)=0.149。

步骤2：根据式(4)对每个条件属性的信息增益进行修正，修正后的每个条件属性的信息增益Gain′(Ai)为：

当属性为“喜欢的季节”时，包括四个决策属性“春”、“夏”、“秋”和“冬”，则

当属性为“是否商务人士”时，包括两个决策属性“是”、“否”，则

当属性为“收入”时，包括三个决策属性“高”、“中”及“低”，则

当属性为“驾车水平”时，包括两个决策属性“良好”、“一般”，则

步骤3：根据式(5)计算属性偏向阈T，共有四个条件属性，则：

步骤4：根据式(6)计算各条件属性的均衡系数。

计算各条件属性的均衡系数前，将每个条件属性的属性偏向阈T与条件熵进行比较，对各属性的信息增益进行重新选择。

当属性为“是否商务人士”时：E(是否商务人士)=0.796>T，令E(是否商务人士)=T，即E(是否商务人士)=0.682，重新利用步骤1、步骤2计算信息增益Gain(是否是商务人士)、修正信息增益Gain′(是否是商务人士)

Gain(是否是商务人士)=0.945-0.682=0.263，

同理，可计算出R(收入)=0.1，R(驾车水平)=0.11。

步骤5：根据式(8)计算各条件属性的优化信息增益Gain(Ai)new：

Gain(喜欢的季节)new=0.4×0.087=0.035，

Gain(是否是商务人士)new=0.263×0.11=0.029，

Gain(收入)new=0.355×0.1=0.036，

Gain(驾车水平)new=0.263×0.11=0.029，

则根节点的属性为“收入”。

完成了根节点的选择后接下来重复上述步骤1-5选择各内部节点、叶节点(即各分支节点)，最终得到训练集的决策树构建如图1所示。

图1 改进ID3算法决策树图

根据传统ID3算法画出的原始决策树如图2所示，比较图1和图2，从原始决策树图2第一层可以看出决策条件具有多值偏向性，属性“喜欢的季节”属性值个数最多，有 “春”、“夏”、“秋”、“冬”四个决策属性，由于多值偏向使其成为决策树的根节点，但“喜欢的季节”是一种主观想法，并不是购车的决定性因素。现实生活中，“收入”在一定程度上更能决定是否购车，由图1可看出，本文提出的数据分类方法令“喜欢的季节”属性离决策树根结点的距离变远，降低其重要性；而“收入”属性作为决策树根结点，提高其重要性，符合实际情况。在传统ID3算法构建的决策树的第二层，当“是否商务人士”作为决策条件时，属性值为“是”则“不买”，属性值为“否”则“买”，这与实际情况是相违背的。而本文改进的ID3算法构建的决策树的第二层，当决策条件为“驾车水平”时，属性值为“良好”则“买”，属性值为“一般”则“不买”，这更符合现实情况。因此本文提出的数据分类方法不仅克服了多值偏向问题而且提升了算法的准确性和实用性。

图2 ID3算法决策树图

4 结束语

本文提出的基于改进ID3算法的数据分类方法，通过修正信息增益，引入均衡系数、属性偏向阈，实现对多值偏向程度的控制和度量，解决了现有ID3算法存在的多值偏向性问题，避免信息增益偏向取值较多的属性，提高了预测的准确率，降低了算法的运行时间。