第９卷第９期 软件导刊 Ｖｏ１．９ ＮＯ．９ ２０１０年９月 Ｓｏｆｔｗａｒｅ Ｇｕｉｄｅ ＳｅＤ．２０１Ｏ 基于决策树方法的数据挖掘分析 郭亚宁，冯莎莎 （山东大学威海分校，山东威海２６４２０９） 摘要：介绍了数据挖掘与决策树算法的一些基本概念，然后对最经典也得到最广泛应用的ＩＤ３算法及其改进算法 作了详细介绍．在最后给出了该算法的一些数据结构和实现代码。 关键词：数据挖掘，决策树，分类，１０３，信息增益 ’ 中图分类号：ＴＰ３０１ 文献标识码：Ａ 文章编号：１６７２—７８００（２０１０）０９—０１０３—０２ 节点根据某种算法从该节点包含的若干测试属性中选择其中 ０引言 一个，然后由该节点伸出若干分支，不同分支对应所选测试属 近年来，数据挖掘越来越引起ＩＴ领域的关注。数据挖掘技 性的不同取值．如此做下去，直到当前决策树可以正确地分出 术的出现解决了目前数据爆炸而信息匮乏的问题。它通过分 各类训练实例。 １．１．３具体步骤 析，从大量的、不完全的、有噪声的、模糊的、随机的实际应用数 据中提取出有效的、潜在有用的信息，这些信息可用于解决如 （１）构造第一棵决策树 ｛ＪＲ｝，Ｒ为树 的根节点，也是该 医疗诊断、风险评估等决策问题。作为数据挖掘中的重要课题， 树目前的唯一节点。记 ＝（Ｄ，Ａ），Ｄ代表训练集（原始数据全 分类模式的获取和知识表达在数据挖掘领域中占有着重要地 体）．Ａ代表测试属性全体。 位。目前分类技术有很多种，如决策树、神经网络、遗传算法等， （２）判断当前决策树的叶子节点，若所有叶子节点都满足 而决策树是分类技术中的很重要的一种。决策树算法有多种 下列条件①节点中的所有训练实例都属于同一类；②节点中的 形式，其中心思想是输入已知数据（通常称为训练集），通过决 测试属性集为空之一，则算法停止。 策树算法对其进行训练，产生一棵决策树，对其进行分析，从而 （３）若步骤２不对所有的叶子节点成立，则选择其中一个 得到研究者想要的预测结果。产生决策树的过程如图１所示： 叶子节点Ｒ ＝（Ｄ ，Ａ ），根据某种规则从Ａ 中选择一个测试属性 ａ．根据ａ的ｎ个不同取值将Ｄ 划分为互不相交的ｎ个子集 Ｊｆ（ 训练集）ｆｌ［ Ｉ———’，， 算法ｒ ｆＩ Ｄ ，１≤ ≤ｎ。从节点风发出ｎ个分支，不同分支代表属性ａ的 不同取值，从而得到ｎ个新的叶子节点Ｒ ＝（Ｄ ，Ａｌ＼｛ａ｝），Ｉ≤ 图１决策树产生示意图 ｉ≤／＇ｔ。 其中决策树的中间节点代表训练集的某一测试属性，节点 （４）转回步骤２，再对新决策树的每个叶子节点调用ＣＬＳ 的后续分支代表该属性可能的取值．叶子节点代表训练实例的 算法。 分类。 １．１．４算法缺点 ＣＩＳ算法的缺点是明显的．它没有给出对叶子节点选取测 １典型决策树算法 试属性的具体规则，使得在算法执行过程对测试属性的选择是 １．１ ＣＬＳ算法 随机的，从而无法得到精简有效的决策树。在之后出现的决策 １．１．１ 简述 树算法中，都提出了对测试属性的选择标准，对ＣＬＳ算法进行 用于构造决策树的概念学习系统ＣＬＳ于１９６６年由Ｈｕｎｔ 了改进。 等人提出，它的提出是具有指导意义的，后来的许多决策树算 １．２ ＩＤ３算法 法的核心思想都是基于ＣＬＳ的。 １．２．１ 简述 １．１．２主要思想 ＩＤ３算法是在ＣＬｓ的基础上提出的最有影响力的决策树 先构造只有一个根节点决策树，这个根节点里包含全部训 算法。ＩＤ３算法中将信息增益作为了选择测试属性的标准。另 练实例和全部测试属性，之后，对于当前决策树的每一个叶子 外，ＩＤ３算法采取了增量式学习的技术，解决了训练集过大以 作者简介：郭亚宁（１９９０－），男，山东济宁人，山东大学威海分校学生，研究方向为数据挖掘；冯莎莎（１９９０一），女，山东滨州人，山东大学威海分校学 生，研究方向为数据挖掘。 ・１０４・ 软件导刊 ２０１０焦 至无法一次性装入内存的问题。 １．２．２信息增益与测试属性的选择标准 ２ ＩＩ）３算法的实现 （１）建立树的数据结构（这里用孩子兄弟表示法） ＃ｄｅｆｉｎｅ Ｎ １００ 首先介绍信息论中信息熵的概念及计算方法。 分布ｐ＝（Ｐ ，Ｐｚ，．．．，ｐ ）传递的信息量称为该分布的熵，记为 ，（ｐ），计算公式为： ， ）－＿ ｐｉ＊ｌｏｇ￣ｐｉ ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＣＳＮｏｄｅ｛ ＮｏｄｅＴｙｐｅ ｄａｔａ； ｓｔｒｕｃｔ ＣＳＮｏｄｅ＊Ｌｃｈｉｌｄ， Ｒｓｉｂｌｉｎｇ； 假设有穷向量空间Ｅ中有ｍ个例子集Ｓｉ，１≤ ≤ｍ，例子集 ｝ＣＳＮｏｄｅ，＊ＣＳＴｒｅｅ；／／决策树的数据结构 ｔｙｐｅｄｅｆ ｓｔｒｕｃｔ ＮｏｄｅＴｙｐｅ｛ Ｓｉ的大小为ｓ ，并设ｓ＝Ｅ 即ｓ表示向量空间Ｅ的大小，则该 向量的信息熵为： Ｉ（Ｓ ，Ｓｚ，…，Ｊｓ ）＝一 争ｆ０ｇ２争 若所选属性为Ａ，Ａ有 个不同的取值啦，１≤ ≤ ，根据Ａ 的不同取值将向量空间Ｅ分为 个不相交的子空间｛Ｅ ， ，．．．， 鼠｝，用 表示子空间历中包含的例子集Ｓ的个数，则以 为 测试属性所得分类的期望信息熵为： Ｅ（Ａ）一∑ ，ｓ … ） １ ｕ 其中，（５ｖ … ｆ０ｇ２ 于是得到信息增益为： ｇａｉｎ（Ａ）：，（Ｓ１，Ｓｚ，．．．，Ｓｍ）－Ｅ（Ａ） 选取测试属性时，要选取各属性中ｇａｉｎ（Ａ）最大的，因为在 Ｊ（ｓ ，Ｓ ，．．．，Ｓ ）固定的情况下，此时Ｅ（Ａ）值最小，即以Ａ为被选 测试属性所得分类的信息熵最小，此时对向量空间Ｅ分类的 稳定性最好。以Ａ为根节点，对以后的各节点不断调用上述过 程．从而构成一棵决策树。 １．２．３算法缺点 ＩＤ３算法仍有许多不足，主要有以下几个方面：①测试属 性选择过程中偏向选择属性值多的，但现实中其不一定是最优 的；②只能处理离散型的属性值，无法处理连续型的属性值；③ 无法处理属性值缺失样本的情况。 １．２．４ ＩＤ３算法的改进 鉴于ＩＤ３算法存在的上述缺点，有人对其进行了改进： （１）加权简化信息熵算法。主要在以下两个方向进行了改 进：①提高了决策树的生成效率。通过泰勒公式与麦克劳林公 式与信息熵计算公式的结合，减少了计算量，节省了计算时间； ②缓和ＴＮ试属性选择中的偏向性。通过对各属性赋予不同的 权值。使取值较多的属性与取值较少的属性拥有同样的被选择 几率。 （２）选取优值法。这一方法主要是针对ＩＤ３算法倾向选 取值较多属性这一缺点而提出的，这里引进了选取优值的概 念。 （３）属性相关性度量法。这也是针对ＩＤ３算法选属性具有 偏向性的缺点提出的改进算法，在这一方法里用属性相关性度 量代替信息熵来选取测试属性。 ｉｎｔ ａｔｔｒｎｕｍ：／／每个节点包含的属性个数 ＴＡｔｔｒ ａｔｔｒ［Ｎ］；／／每个节点包含的属性 ｄａｔａｔｙｐｅ＊ｄａｔａ；／／每个节点包含的训练集 ｝； ｔｙｐｅｄｅｆ ｓｔｒｕｅｔ ＴＡｔｔｒ｛ ｉｎｔ ａｔｔｒｖａｌｕｅｎｕｍ：／／每个属性的值的个数 ＡｔｔｒＴｙｐｅ ａｔｔｒｖａｌｕｅ［Ｎ］；／／每个属性的值 ｆ； （２）建立ＩＤ３决策树的伪代码 函数简介：＠ＩｎｉｔＣＳＴｒｅｅ（Ｔ）：初始化决策树，指明当前决策 树（或其子树）根节点包含的属性和训练集；＠Ｃａｌｇａｉｎ（Ｔ）：计算 当前决策树（或其子树）根节点所有属性的信息增益；（￣）Ｓｅｌｅｃ— ｔＡｔｔｒ（）：选择信息增益最大的属性，返回该属性，在数组ａｔｔｒ ［Ｎ］中的位置；④ＣｒｅａｔｅＬｅａｆ（Ｔ）：生成Ｔ的一个叶子节点，该叶 子节点中属性集少了上一步选择的属性，训练集为拥有该属性 值的所有训练实例组成的集合。 ｖｏｉｄ ＣｒｅａｔｅＩＤ３Ｔｒｅｅ（ＣＳＴｒｅｅ＆Ｔ）ｔ ＩｎｉｔＣＳＴｒｅｅ（Ｔ）； Ｃａｌｇａｉｎ（Ｔ）； ＬｏｃＡｔｔｒｍａｘ＝ＳｅｌｅｃｔＡｔｔｒ（）； ｆｏｒ（ｉ＝０；ｉ＜Ｔ．ｄａｔａ．ａｔｔｒ［ＬｏｃＡｔｔｒｍａｘ］．ａｔｔｒｖａｌｕｅｎｕｍ；＋＋ｉ） ＣｒｅａｔｅＬｅａｆ（Ｔ）； ＣｒｅａｔｅｌＤ３Ｔｒｅｅ（Ｔ－＞Ｌｃｈｉｌｄ）； ＣｒｅａｔｅＩＤ３Ｔｒｅｅ（Ｔ－＞Ｒｓｉｂｌｉｎｇ）； ｝ ３结束语 本文用尽可能通俗的语言尽可能详细地描述了决策树算 法中最经典的ＩＤ３算法，以求读者对其有深入的了解。算法的 软件实现是未来的一个发展方向，文章最后给出的是最基础的 实现思想。 参考文献 ［１］ 续蕾，刘玉江。基于经营决策为主题的数据挖掘的应用——决策 树算法实例研究［Ｊ］．电脑知识与技术，２００７（３）． ［２］ＨＡＮ Ｊ．Ｗ，ＫＡＭＢＥＲ Ｍ．Ｄａｔａ Ｍｉｎｉｎｇ Ｃｏｎｃｅｐｔｓ ａｎｄ Ｔｅｃｈｎｉｑｕｅｓ ［Ｍ］．Ｍｏｒｇａｎ Ｋａｕｆｍａｎｎ，２００１． ［３］ 史忠植．知识发现［Ｍ］．北京：清华大学出版社，２００２． 第９卷第９期 软件导刊 ＶＯ１．９ ＮＯ．９ ２０１０年９月 Ｓｏｆｔｗａｒｅ Ｇｕｉｄｅ … Ｓｅｏ．２Ｏｌ０ 软件工程在软件开发中的应用 王 巍．周 沫 （上海政治学院，上海２００４３５） 摘要：通过分析软件开发过程中存在的问题，引入软件工程的概念，并概括了利用软件工程进行软件开发中最重 要的３个方面。传统的软件工程方法将被面向对象的方法所取代，组件技术必将越来越倍受重视，同时更加新颖、更 加先进的方法也必将会出现。 关键词：软件工程；需求 中图分类号：ＴＰ３１１．５ 文献标识码：Ａ 文章编号：１６７２—７８００（２０１０）０９—０１０５—０２ 软件的可靠性、可维护性较差，而且往往超出开发时间的要求； ｆ ｒ【 【 １软件工程的起源 软件生产率、软件质量远远满足不了社会发展的需要，出现了 ｍ ¨ “软件危机”现象。软件工程这一术语首次出现在１９６８年由 上世纪６０年代以来，随着计算机的广泛应用，软件开发所 ＮＡＴＯ组织的一次计算机学术会议上，其目的是倡导以工程的 面临的问题域的复杂性急剧膨胀。系统的规模和复杂度空前扩 原理、原则和方法进行软件开发，以期解决当时发生的“软件危 大。但当时软件开发基本上还是依赖开发人员的个人技能，没 机”。 有可以遵循的原理、原则和方法，同时也缺乏有效的管理；软件 从软件工程的角度去指导软件开发，系统地将软件工程知 的复杂性和其中包含的错误达到了开发人员难以控制的程度， 识应用于实际问题．按软件工程思想展开工作，是解决“软件危 林杰斌，刘明德，陈湘．数据挖掘与ＯＬＡＰ理论与实务［Ｍ］．北京： 施蕾，唐艳琴，张欣星．数据挖掘中决策树方法的研究［Ｊ］．计算 清华大学出版社．２００３． 机与现代化．２００９（１Ｏ）． 杨静，张楠男，李建，等．决策树算法的研究与应用［Ｊ］．计算机技 邵峰晶，于忠清，王金龙，等．数据挖掘原理与算法（第二版） 术与发展．２０１０（２）． ［Ｍ］．北京：科学出版社，２００９． ＰＯＲＴＥＲ Ｂ Ｗ，ＢＡＲＥＳＳ Ｅ Ｒ，ＨＯＬＴＥ Ｒ．Ｃｏｎｃｅｐｔ ｌｅａｒｎｉｎｇ ａｎｄ 但小容，陈轩恕，刘飞，等．数据挖掘中决策树分类算法的研究 ｈｅｕｒｉｓｔｉｃ ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｉｎ ｗｅａｋ ｔｈｅｏｒｙ ｄｏｍａｉｎｓ［Ｊ］．Ａｒｔｉｉｆｃｉａｌ Ｉｎｔｅｌｌｉ— 与改进［Ｊ］．软件导刊，２００９（２）． ｇｅｎｃｅ，１９９０（２）． 王静红，王熙照，邵艳华．决策树算法的研究及优化［Ｊ］．微机发 陈晶，肖丁．决策树算法在数据挖掘中的应用研究［Ｊ］．软件导刊， 展．２００４（９）． ２００８（３）． 韩家新，王家华．一种以相关性确定条件属性的决策树［Ｊ］．微机 陈京民．数据仓库原理、设计与应用［Ｍ］．北京：中国水利水电出 发展，２００３（５）． 版社．２００４． （责任编辑：卓光） 路红梅．基于决策树的经典算法综述［Ｊ］．宿州学院学报，２００７（２）． Ａｎａｌｙｓｉｓ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ｂａｓｅｄ ｏｎ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ Ａｂｓｔｒａｃｔ：Ｔｈｅ ａｒｔｉｃｌｅ ｉｎｔｒｏｄｕｃｅｄ ｓｏｍｅ ｂａｓｉｃ ｃｏｎｃｅｐｔｉｏｎ ｏｆ ｄａｔａ ｍｉｎｉｎｇ ａｎｄ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｌｇｏｒｉｔｈｍ ａｔ ｆｉｒｓｔ．Ａｎｄ ｔｈｅｎ ａｎ ａｌｇｏｒｉｔｈｍ ｃａｌｌｅｄ ＩＤ３ ｗｈｉｃｈ ｉｓ ｔｈｅ ｍｏｓｔ ｃｌａｓｓｉｃａｌ ａｎｄ ｍｏｓｔ ｗｉｄｅｌｙ ｕｓｅｄ ｉｓ ｉｎｔｒｏｄｕｃｅｄ ｄｅｔａｉｌｅｄ，ａｓ ｗｅｌｌ ｉｔｓ ｉｍｐｒｏｖｅｍｅｎｔ．Ｓｏｍｅ ｄａｔａ ｓｔｒｕｃｔｕｒｅｓ ａｎｄ ｃｏｄｅｓ ａｒｅ ｇｉｖｅｎ ａｔ ｔｈｅ ｅｎｄ ｏｆ ｔｈｅ ａｒｔｉｃｌｅ． Ｋｅｙ Ｗｏｒｄｓ：Ｄａｔａ Ｍｉｎｉｎｇ，Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ，Ｃｌａｓｓｉｎｇ，Ｉｄ３，Ｉｎｆｏｒｍａｔｉｏｎ Ｇａｉｎ 作者简介：王巍（１９８２一），男，山西晋中人，上海政治学院训练部助教，研究方向为信息系统开发；周沫（１９８６一），女，河南南阳人，上海政治 学院训练部助教，研究方向为多媒体教学。
