第３ｌ卷第４期 ２０ｌ１年８月 辽宁工业大学学报（自然科学版）
Ｊｏｕｒｎａｌ ｏｆＬｉａｏｎｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ（Ｎａｔｕｒａｌ Ｓｃｉｅｎｃｅ Ｅｄｉｔｉｏｎ） 、ｂ１．３１．Ｎｏ．４ Ａｕｇ．２０１１
本刊核心层次论文
一个改进的决策树算法
佟玉军，曹光辉，陈文实，刘鸿沈
（辽宁工业大学电子与信息工程学院，辽宁锦州 １２１００１）
摘要：Ｉｔｅｒａｔｉｖｅ Ｄｉｃｈｏｔｏｍｉｓｅｒ ｖｅｒｓｉｏｎ３（ＩＤ３）算法是数据挖掘中经典的决策树分类算法，其核心是分裂训练集
属性的选择标准，即分裂前后的信息增益量最大，用该标准选择属性时对于取值较多的属性具有较强依赖性。剖
析了ＩＤ３算法存在的不足并加以改进，引入了属性关注度，提出了改进算法ＡＡＩＤ３算法。实验表明改进算法对
原ＩＤ３算法的取值偏向问题有所克服并使分类更加准确，决策树更加简明。
关键词：ＩＤ３算法：属性关注度；信息增益；ＡＡＩＤ３算法
中图分类号：ＴＰ３１ １ 文献标识码：Ａ 文章编号：１６７４—３２６１（２０１ １）０４－０２２５・０３
Ａｎ Ｅｎｈａｎｃｅｄ ＩＤ３ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅｄ ｏｎ Ａｔｔｒｉｂｕｔｅ Ａｔｔｅｎｔｉｏｎ
ＴＯＮＧ Ｙｕ－ｊｕｎ，ＣＡＯ Ｇｕａｎｇ—ｈｕｉ，ＣＨＥＮ Ｗｅｎ—ｓｈｉ，ＬＩＵ Ｈｏｎｇ－ｓｈｅｎ
（Ｅｌｅｃｔｒｏｎ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｄｎｇ Ｃｏｌｌｅｇｅ，Ｌｉａｏｎｉｎｇ Ｕｎｉｖｅｒｓｉｔｙ ｏｆＴｅｃｈｎｏｌｏｇｙ，Ｊｉｎｚｈｏｕ １２１００１，Ｃｈｉｎａ）
Ｋｅｙ ｗｏｒｄｓ：ＩＤ３ ａｌｇｏｒｉｔｈｍ；ａｔｔｒｉｂｕｔｅ ａｔｔｅｎｔｉｏｎ；ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ；ＡＡＩＤ３ ａｌｇｏｒｉｔｈｍ
Ａｂｓｔｒａｃｔ：Ｉｎ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｓｏｒｔｉｎｇ，Ｉｔｅｒａｔｉｖｅ Ｄｉｃｈｏｔｏｍｉｓｅｒ ｖｅｒｓｉｏｎ ３（ＩＤ３）ｉｓ ａ ｃｌａｓｓｉｃａｌ ａｌｇｏｒｉｔｈｍ
ｕｓｅｄ ｔｏ ｇｅｎｅｒａｔｅ ａ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｉｎｖｅｎｔｅｄ ｂｙ Ｒｏｓｓ Ｑｕｉｎｌａｎ．Ｉｔｓ ｃｏｒｅ ｌｉｅｓ ｉｎ ｔｈｅ ｓｐｌｉｔ－ｏｆｆ ｔｒａｉｎｉｎｇ ｗｈｉｃｈ
ｌｕｍｐｅｄ ｔｈｅ ｓｔａｎｄａｒｄ ｏｆ ａｔｔｒｉｂｕｔｅｓ ｐｒｅｆｅｒｅｎｃｅ，ｎａｍｅｌｙ，ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ ｉｓ ｏｆ ｍａｘｉｍｕｍ ｑｕａｎｔｉｔｙ ｂｏｔｈ
ｂｅｆｏｒｅ ｓｐｌｉｔ－ｏｆｆ ａｎｄ ａｆｔｅｒ ｓｐｌｉｔ－ｏｆｆ．Ｔｈｅ ｕｓｅ ｏｆ ｔｈｉｓ ｐｒｅｆｅｒｅｎｃｅ ｓｔａｎｄａｒｄ ｔｏ ｓｅｌｅｃｔ ａｔｔｒｉｂｕｔｅｓ ｈａｓ ａ ｓｔｒｏｎｇ
ｄｅｐｅｎｄｅｎｃｅ ｉｎ ｒｅｇａｒｄ ｏｆ ｔｈｅ ｍｉｌｔｉ－ｖａｌｕｅｄ ａｔｔｒｉｂｕｔｅｓ ｐｒｅｆｅｒｅｎｃｅ．Ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆ ＩＤ３ ａｌｇｏｒｉｔｈｍ ｗｅｒｅ
ａｎａｌｙｚｅｄ ａｎｄ ｉｍｐｒｏｖｅｄ ｔｈｒｏｕｇｈ ｉｎｔｒｏｄｕｃｉｎｇ ａｔｔｒｉｂｕｔｅ ａｔｔｅｎｔｉｏｎ．Ｔｏ ｔｈｅ ｅｆｆｅｃｔ，ＡＡＩＤ３ ａｌｇｏｒｉｔｈｍ ｗａｓ
ｐｒｏｐｏｓｅｄ．Ｅｘｐｅｒｉｍｅｎｔａｌ ｒｅｓｕｌｔｓ ｅｘｐａｔｉａｔｅｄ ＡＡＩＤ３ ａｌｇｏｒｉｔｈｍ ｉｓ ｓｕｐｅｒｉｏｒ ｔｏ ｔｈｅ ＩＤ３ ｉｎ ａｃｃｕｒａｃｙ ｏｆ
ｃｌａｓｓｉｆｉｃａｔｉｏｎ，ｃｏｎｃｉｓｉｏｎ ｏｆ ｄｅｃｉｓｉｏｎ ｔｒｅｅ，ａｎｄ ｉｎｄｅｐｅｎｄｅｎｃｅ ｆｒｏｍ ｍｕｌｔｉ－ｖａｌｕｅｄ ａｔｔｒｉｂｕｔｅｓ．
１ ＩＤ３算法原理
随着网络与信息技术的不断发展，如何从海量
数据中挖掘知识日益重要，决策树是知识发现［１］
的重要工具之一，而ＩＤ３算法是决策树中代表性算 法，它首选找出最大信息增益的属性【ｌ】，将给定学
习训练集分裂为若干子集，接下来以同样选择标准
对每个子集进行分裂，递归执行以上操作，终止条
件为任何子集包含数据类型相同，算法返回值为一
棵决策树，可以用它来对新的数据集进行分类学 习。该算法建立在奥卡姆剃刀定律【２】（如无必要，勿
增实体）基础上，该定律阐述了信息熵的概念。若
收稿日期：２０１１－０６－２４ 作者简介：佟玉军（１９７０一），男（满族），辽宁凌海人，副教授。 信源有，１种消息，且每个消息是以相等可能产生的，
则该信源信息量可表示为
１＝ｌｏｇ，（ ） （１）
设有数据集Ｄ，分类属性Ｃ｛ｃｌ，Ｃ２，．．．，ｃ ｝可将数据
集Ｄ分解成｛ ， ，．．．， ），则期望的信息需求量称
为Ｄ的熵，记为
卫 Ｅｎｔｒｏｐｙ（Ｄ）＝一∑ｐｉｌｏｇ２（Ｐｉ） （２） Ｉ＝ｌ １．１训练集划分前的熵
假设分裂前的训练数据集Ｄ有一个分类属性
和至少一个非分类属性，并假设分类属性Ｃ包含ｍ
个不同的离散值，那么根据属性ｃ，训练数据集Ｄ 辽宁工业大学学报（自然科学版） 第３ｌ卷
中的元素可以被划分成ｍ个不同的类别，因此训练
集划分前的熵可计算如公式（２）。
１．２训练集划分后的熵
设属性Ａ有ｗ个离散值，将数据集Ｊ［）分成ｆ ，
…．，ｄｗ｝，同时设分类属性Ｃ有ｍ个离散值ｆｃ１，
ｃ２，．．．，Ｃｍ），则 就可以被分类属性Ｃ分裂成｛ ，，
…， ），其中 的样本规模记为｛巧Ｊ， 的熵计
算如下
Ｅｎｔｒｏｐｙ（ｄ／）＝＿∑Ｐｏ．１ｏｇ２（ ） Ｊ＝ｌ 式中：Ｐ 为任一记录属于类别Ｃ 的概率。
由公式可知，属于不同类别的记录的信息量的
加权平均值就是划分之后信源总熵，记为
Ｅｎｔｒｏｐｙ（Ａ，Ｄ）＝∑ｗｆ Ｅｎｔｒｏｐｙ（ｄ，） （３） 习
式中：ｗ，是 样本规模与Ｄ样本规模之商，记为
Ｈ ．，叶 １）／Ｉｒ￣
１．３信息增益
所谓信息增益就是由于系统因为分类而获得
的信息量。由系统分裂前的熵与根据某一属性如属
性Ａ分裂系统后的熵值之差来描述，记为
Ｇａｉｎ（Ａ）＝Ｅｎｔｒｏｐｙ（Ｄ）一Ｅｎｔｒｏｐｙ（Ａ，Ｄ１ （４）
由公式（４）可以看出，系统分裂后的熵值Ｅｎｔｒｏｐｙ（Ａ，
Ｄ）越小则由此获得的信息增益Ｏａｉｎ（Ａ）就越大，这表
明如果选择属性Ａ对系统进行分类，分类后系统的
噪音就小。
ＩＤ３是基于信息熵的决策树分类算法，采用自
顶向下的贪心算法与深度优先遍历算法递归搜索
可能的决策空间，信息增益是ＩＤ３算法用来选择分
裂属性的核心，即选用某一属性分裂训练集，能够
使得训练集被分类后的熵值最小【４】，也就获得了最
大的信息增益量。
２ ＡＡＩＤ３算法
２．１传统１１）３算法缺陷
传统ＩＤ３算法递归搜索全部分裂属性采用的是
自顶向下不回溯策略，该递归算法代码行数少、容
易理解、执行速度快【５Ｊ，且生成的决策树层次少。
但它的选择某个属性作为分裂属性的原则却存在
一个问题，总是偏向于选取多值属性作为分裂属
性，但取值较多的属性却不总是首选的属性，也就
是说，即使按照该原则根据传统ＩＤ３算法计算为优
先选取的分裂属性，在现实情况中却并不一定非常
重要，同样对这些分裂属性进行系统测试也不会获
取太多有用信息。 ２．２属性关注度
基于上述传统ＩＤ３算法存在的不足，引入属性
关注度概念以期改进ＩＤ３算法选择属性时对多值属
性依赖问题。关注度反映的是个人或群体对特定领
域、事物或信息的认知偏好，这种意愿、倾向和偏
好具有促成具体行动的可能性。通过统计关注群体
对某些产品、服务信息的认知偏好，获知对这些产
品和服务信息的关注状况。属性关注度是指关注群
体对某一信源中相关属性的认知、倾向和偏好的程
度，记为
口ｆ＝ （１一詈） （５）
式中：Ⅳ为非分类属性集合总数， 为关注群体总
数，Ｓ 为某个非分类属性的关注群体数，且在各非
分类属性上的ａ／之和为１．通过该公式的引入，可
以将某一信源中所有非分类属性权重从另一新角
度进行计算以消缓原算法对多值属性的依赖度。
２．３ ＡＡＩＤ３的信息增益
改进算法ＡＡＩＤ３算法是针对原算法中属性选
择标准进行改进，对公式（２）进行修改，引入属性
关注度参数研，引入属性关注度后的信息增益为
Ｇａｉｎ＇（Ａ）＝Ｅｎｔｒｏｐｙ（Ｄ）－ａｉ木Ｅｎｔｒｏｐｙ（Ａ， ）） （６）
改进算法根据新的信息增益计算方法来选出
所有属性中信息增益最大的作为分裂属性，接下来
以同样的方法计算选出后继的分裂属性并最终产
生一颗决策树，新算法的终止条件与原算法相同。
改进算法同时采用剪枝技术【３．４】使在生成决策树时
取值数量偏少的数据元素不会被剪枝掉，同时新算
法比原ＩＤ３算法生成的决策树的结点数量减少且决
策树简洁。
３实验结果及分析
３．１ ＩＤ３算法生成决策树
下面的实验是对某一部门部分医疗保健数据
进行分类，训练数据集如表１（以前ｌ５例数据集为 例），其中分类属性值【６】有ｙ和Ⅳ两种。由公式（１）
和（２）可计算与信息增益相关熵值如下
Ｅｎｔｒｏｐｙ（Ｙ，Ｎ）＝－（９／１５） ｌｏｇ２（９／１５）一（６／１５） ｌｏｇ２（６／１５）＝
０．９７０ ９５位
同理计算Ｅｎｔｒｏｐｙ（月收入）：０．８位，Ｅｎ－ｔｒｏｐｙ（健康状
态）－ｏ．７２３ ６５５位，Ｅｎｔｒｏｐｙ（性别） ．８９２４５４位。由此
得到前算法各属性信息增益：Ｇａｉｎ（月收入）＝
０．１ ７０９５位，Ｇａｉｎ（健康状态）＝０．２４７ ２９９位，Ｇａｉｎ（性
别）＝０．０７８ ４９９位。由此得出属性健康状态的信息增
益最大。在决策树的构建过程中，首先选择健康状
