you have been blocked决策树分类优化算法的应用研究_资讯_突袭网-提供留学,移民,理财,培训,美容,整形,高考,外汇,印刷,健康,建材等信息
当前位置&:&&&&决策树分类优化算法的应用研究
热门标签：&
决策树分类优化算法的应用研究
编辑：张德勇评论：
==========以下对应文字版==========西南交通大学硕士学位论文 决策树分类优化算法的研究 姓名：吴绪玲 申请学位级别：硕士 专业：计算机应用技术 指导教师：邓平 201010 西南交通大学硕士研究生学位论文 数据挖掘就是从大量的、不完全的、有噪声的数据中，提取出有效的和潜在规律性信息的过程。数据挖掘的任务就是从数据集中发现模式，它融合了数据库、人工智 能，、机器学习、统计学等多个领域的理论和知识。在数据挖掘中，分类和预测是被广 泛研究的技术，并且己经广泛地应用于许多领域，对未来商业和人们的生活也将产生 深远的影响。决策树方法自２０世纪６０年代以来，在分类、预测、规则提取等领域有 着广泛的应用，其中以Ｑｕｉｌａｎ于１９８６年提出的ＩＤ３算法最为著名。本文主要研究决策 树Ｄ３算法及其改进。 本文深入研究了ＩＤ３算法的理论基础及构建决策树的过程等知识。Ｑｕｉｎｌａｎ提出 的ＩＤ３算法虽然很经典，但也有美中不足之处。第一，算法中使用了对数计算，而且 计算过程复杂；第二，取值较多的属性被选择的机率比较大，即多值偏向问题。为了 解决ＩＤ３的这些问题，本文引入了泰勒公式和麦克劳林公式，对原ＩＤ３算法进行化简， 不仅属性信息增益的计算步骤减少，而且使信息熵的计算公式本身变得十分简洁；对 于ＩＤ３算法偏向于选取有较多取值的属性的缺点，用一个与属性取值个数相关的函数 对简化后的属性信息增益进行修正。通过以上两个方面的优化，新算法在构建决策树 的速度上得到提高，同时也解决了ＩＤ３算法多值偏向的不足。然后，使用同一个小数 据集对改进前后的算法进行实例分析，分别得到其对应的决策树。 最后，用面向对象的ＪＡＶＡ高级语言实现了改进前后的１１）３算法，并且在不同规模 的数据集上进行仿真实验，把改进后算法分别与ＩＤ３算法、Ｃ４．５算法进行比较分析， 验证了改进后算法在构建决策树时所需的时间及分类准确率两个方面都优于其他两个 算法。’ 关键词：数据挖掘；１１）３算法；决策树；多值偏向；信息增益；信息熵 西南交通大学硕士研究生学位论文 第１Ｉ页 Ａｂｓｔｒａｃｔ． Ｄａｔａ Ｍｉｎｉｎｇ ｐｒｏｃｅｓｓｗｈｉｃｈｅｘｔｒａｃｔｓ ｅｆｆｅｃｔｉｖｅ、ｐｏｔｅｎｔｉａｌ、ｒｅｇｕｌａｒｋｎｏｗｌｅｄｇｅ ｉｎｆｏｒｍａｔｉｏｎｆｒｏｍｔｈｅｌａｒｇｅ、ｉｎｃｏｍｐｌｅｔｅ、ｎｏｉｓｙｄａｔａ．Ｆｉｎｄｉｎｇｐａｔｔｅｒｎｓ ｔｈｅｔａｓｋｏｆＤａｔａＭｉｎｉｎｇ ｆｒｏｍｄａｔａｓｅｔｓ．Ｄａｔａ Ｍｉｎｉｎｇ ｃｏｍｂｉｎｅｓｗｉｔｈ ｔｈｅｏｒｙ ｔｅｃｈｎｏｌｏｇｙｏｆｄａｔａ ｗａｒｅｈｏｕｓｅ， ａｒｔｉｆｉｃｉａｌ ｉｎｔｅｌｌｉｇｅｎｃｅ，ｍａｃｈｉｎｅｌｅａｒｎｉｎｇ，ｓｔａｔｉｓｔｉｃｓ ａｎｄｏｔｈｅｒｆｉｅｌｄｓ．Ｃｌａｓｓｉｆｉｃａｔｉｏｎ ｐｒｅｄｉｃｔｉｏｎｔｅｃｈｎｏｌｏｇｙｏｆＤａｔａ Ｍｉｎｉｎｇ ｗｉｄｅｌｙｒｅｓｅａｒｃｈｅｄａｎｄｕｓｅｄｉｎ ｍａｎｙ ｆｉｅｌｄｓ． Ｃｏｎｓｅｑｕｅｎｔｌｙｉｔ ｐｒｏｄｕｃｅｆａｒ－ｒｅａｃｈｉｎｇｉｍｐａｃｔ０１１ｆｕｔｕｒｅｃｏｍｍｅｒｃｉａｌａｎｄ ｐｅｏｐｌｅ’Ｓ ｌｉｖｅｓ． Ｓｉｎｃｅ２０ｔｈ ｃｅｎｔｕｒｙ６０ｓｊｔｈｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｍｅｔｈｏｄｉｓ ｗｉｄｅｌｙａｐｐｌｉｅｄ ｃｌａｓｓｉｆｉｃａｔｉｏｎｐｒｅｄｉｃｔｉｏｎｅｘｔｒａｃｔｉｏｎ ｒｕｌｅｓａｎｄｏｔｈｅｒｆｉｅｌｄｓ．Ｏｆｃｏｕｒｓｅ．ｔｈｅｆａｍｏｕｓｏｎｅｉｓ ＩＤ３ ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈｗａｓ ｐｒｅｓｅｎｔｅｄｂｙＱｕｉｎｌａｎ ｉｎ１９８６．Ｔｈｅ ｉｍｐｏｒｔａｎｃｅ ｏｆｔｈｉｓｔｈｅｓｉｓｉｓ ｍａｉｎｌｙ ｓｔｕｄｙＩＩ）３ ａｌｇｏｒｉｔｈｍ ｏｆｄｅｃｉｓｉｏｎｔｒｅｅａｎｄｉｔｓ ｉｍｐｒｏｖｅｍｅｎｔ． Ｆｉｒｓｔｌｙｔｈｅｏｒｅｔｉｃａｌ ｂａｓｉｓａｎｄｔｈｅ ｐｒｏｃｅｓｓ ｂｕｉｌｄｉｎｇｄｅｃｉｓｉｏｎｔｒｅｅｏｆＩＤ３ ａｌｇｏｒｉｔｈｍ ｆｕｒｔｈｅｒｒｅｓｅａｒｃｈｅｄ．ＴｈｅＩＤ３ａｌｇｏｒｉｔｈｍ ｗｈｉｃｈｗａｓ ｐｒｅｓｅｎｔｅｄｂｙＱｕｉｎｌａｎ ｏｎｌｙｍｏｓｔ ｆａｍｏｕｓ，ｂｕｔ ａｌｓｏｔｈｅｒｅａｒｅｓｏｍｅｉｔｓｄｒａｗｂａｃｋｓ：ｏｎｅｉｓｔｈａｔ ｕｓｉｎｇｌｏｇ ｉｓｎｏｔ ｅａｓｙ ｔｏｃａｌｃｕｌａｔｅ ｖｅｒｙｃｏｍｐｌｅｘｉｔｙ．Ｔｈｅｏｔｈｅｒ：ｔｈｉｓ ａｌｇｏｒｉｔｈｍ ｉｓｂｉａｓｅｄｉｎｆａｖｏｒｏｆ ｔｈｏｓｅａｔｔｒｉｂｕｔｅｓｗｈｏｓｅｖａｌｕｅｓｉｓ ｍｏｒｅ，ｎａｍｅｌｙ ｍｕｌｔｉ―ｖａｌｕｅｂｉａｓ．Ｉｎｏｒｄｅｒｔｏｓｏｌｖｅｔｈｅｓｅ ｄｉｓａｄｖａｎｔａｇｅｓ ｏｆＩＤ３ ａｌｇｏｒｉｔｈｍ，ｆｉｒｓｔ，ｔｈｅ ｔｈｅｓｉｓｉｎｔｒｏｄｕｃｅｓ Ｔａｙｌｏｒ ｆｏｒｍｕｌａａｎｄＭａｃｌａｕｒｉｎ ｆｏｒｍｕｌａｔｏ ｓｉｍｐｌｉｆｙ ＩＩ）３ａｌｇｏｒｉｔｈｍ．Ｓｏ，ｉｔ ｒｅｄｕｃｅｓｎｏｔ ｏｎｌｙ ｃａｌｃｕｌａｔｉｏｎ ｓｔｅｐｓ ｉｎｆｏｒｍａｔｉｏｎｇａｉｎ ａｔｔｒｉｂｕｔｅｓ，ｂｕｔａｌｓｏｔｈｅｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ｃｏｍｐｕｔｉｎｇｂｅｃｏｍｅｓ ｅａｓｙ． Ａｎｄｔｈｅｎ谢缸ｌｒｅｇａｒｄ ｔｏｔｈｅｄｒａｗｂａｃｋｏｆｍｕｆｔｉ―ｖａｌｕｅｂｉａｓ，ｔｈｉｓｔｈｅｓｉｓｉｎｔｒｏｄｕｃｅｓａｆｕｎｃｔｉｏｎ ｗｈｉｃｈｉｓ ａｓｓｏｃｉａｔｅｄ诵ｍｖａｌｕｅｏｆｏｎｅａｔｔｒｉｂｕｔｅｂａｓｅｄｏｎ ｓｉｍｐｌｉｆｉｅｄ ｉｎｆｏｒｍａｔｉｏｎ ｅｎｔｒｏｐｙ ａｔｔｒｉｂｕｔｅ．Ｔｈｒｏｕｇｈｏｐｔｉｍｉｚａｔｉｏｎｏｆｔｈｅａｂｏｖｅｔｗｏ ａｓｐｅｃｔｓ，ｔｈｅ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｒａｉｓｅｓｔｈｅ ｓｐｅｅｄ ｏｆｔｈｅ ｐｒｏｃｅｓｓ ｍａｋｉｎｇｄｅｃｉｓｉｏｎｔｒｅｅ．Ａｔｔｈｅｓａｍｅｔｉｍｅ，ｉｔｃａｒｌａｌｓｏｏｖｅｒｃｏｍｅｔｈｅＩＤ３’Ｓ ｗｅａｋｎｅｓｓｗｈｉｃｈｉｓ ａｐｔ ｔｏｓｅｌｅｃｔｓｏｍｅａｔｔｒｉｂｕｔｅｗｉｍｍｏｒｅ ｖａｌｕｅｓ．Ｔｈｅｎ．ｔｈｒｏｕｇｈ ａｎａｌｙｓｉｓｏｆｔｈｅｓａｍｅ ｅｘａｍｐｌｅｓ ｗｈｉｃｈｕｓｅｔｈｅｓａｎｌｅｓｍａｌｌ ｔｒａｉｎｉｎｇｓｅｔ，ｔｈｅｉｒｄｅｃｉｓｉｏｎｔｒｅｅｓｏｂｔａｉｎｅｄ ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍｂｅｆｏｒｅａｎｄａＲｅｒ． Ｆｉｎａｌｌｙａｃｃｏｒｄｉｎｇ ｔｏｔｈｅ ｏｂｊｅｃｔ－ｏｒｉｅｎｔｅｄｍｅｔｈｏｄｔｈｉｓ ｔｈｅｓｉｓＵＳｅＳＪａｖａｔｏａｃｔｕａｌｉｚｅＩＤ３ ａｌｇｏｒｉｔｈｍ ａｎｄｔｈｅ ｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ．Ａｎｄ，ｔｈｅｉｍｐｒｏｖｅｄａｌｇｏｒｉｔｈｍ，ＩＤ３ ａｎｄＣ４．５ ａｌｇｏｒｉｔｈｍ ａｌｅｕｓｅｄｉｎｔｈｅｄｉｆｆｅｒｅｎｔｓｉｚｅｓｄａｔａｓｅｔｓ． Ｔｈｒｏｕｇｈ ａｎａｌｙｓｉｓｏｆｓｉｍｕｌａｔｉｏｎａｌ ｅｘｐｅｒｉｍｅｎｔｏｕｔｃｏｍｅ，ｉｔｖａｌｉｄａｔｅｓｔｈａｔｔｈｅ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｅｘｃｅｌｓ ＩＤ３ａｎｄＣｄ４．５ ａｌｇｏｒｉｔｈｍ ｔｉｍｅｏｆｃｏｎｓｔｒｕｃｔｉｎｇ ｄｅｃｉｓｉｏｎｔｒｅｅ ｃｌａｓｓｉｆｉｃａｔｉｏｎａｃｃｕｒａｃｙ． Ｋｅｙｗｏｒｄｓ：ＤａｔａＭｉｎｉｎｇＩＤ３ ａｌｇｏｒｉｔｈｍＤｅｃｉｓｉｏｎ ｔｒｅｅＭｕｌｔｉ－ｖａｌｕｅ ｂｉａｓ， Ｉｎｆｏｒｍａｔｉｏｎ ｇａｉｎ，Ｉｎｆｏｒｍａｔｉｏｎｅｎｔｒｏｐｙ 西南交通大学硕士研究生学位论文 １．１研究背景及意义第１章前言 随着信息时代的到来，我们每天产生的信息数据越来越多，如何从大量的数据中 提取并发现有用的信息，并为管理者决策提供有利指导呢？这给人类的智能信息处理能 力提出了前所未有的挑战，数据挖掘技术就是在这种背景下产生的，数据挖掘就是从大 量的、不完全的、有噪声的数据中，提取出有效的和浅在规律性信息的过程［１】。数据 挖掘的任务就是从数据集中发现模式，它融合了数据库、人工智能、机器学习、统计 学等多个领域的理论和知识【２】。 在数据挖掘中，分类和预测是被广泛研究的技术，并且己经广泛地应用于许多领域，如对电信、银行、保险、零售、医疗、客户关系管理等诸多行业提供决策支持， 并对未来商业和人们的生活也将产生深远的影响。分类的目的是学会一个分类函数或分类模型（分类器），该模型能把数据库或其它数据集中的数据映射到给定类别中的某 一个。分类研究在国外发展的比较快，已有很多成型的算法和模型，而在国内发展相 对落后。在数据挖掘中用来处理分类的算法很多，如决策树、贝叶斯分类、规则推理、 遗传算法和神经网络等【３】，其中决策树方法自２０世纪６０年代以来，在分类、预测、 规则提取等领域有着广泛的应用。尤其在Ｑｕｉｌａｎ［１６］于１９８６年提出ＩＤ３算法以后，决 策树方法在机器学习、知识发现等领域得到了进一步应用及巨大的发展。其得以发展的原因有以下几点【４】：决策树算法的复杂度较小，速度快。比较容易转化成分类规 则，对生成的决策树，只要从树根向下沿着任何一个分枝走到叶子节点，都能唯一的 确定一条分类规则。决策树算法的抗噪声能力强决策树算法的可伸缩性强，既可 用于小数据集，也可用于海量数据集。决策树算法简单，产生的结果易于理解。对 于决策树的使用者来说，不需要具备太多的专业技术知识，因决策树生成的规则非常 简单易懂。准确性很高。与其他分类技术相比，决策树产生的分类规则的准确性更 高一些，所以，能更好地为人们的决策提供指导。正因为如此决策树算法也就成为数 据挖掘研究中最活跃的领域之一。 现在，决策树与数据挖掘相结合的技术已被广泛应用于很多领域：尤其是在零售 业，有很成功的应用案例，利用分类技术实现客户细分和交叉销售等，比如著名的啤 酒和尿布的应用案例；在电子商务领域，其在在线销售、数字销售、网络广告、客户 关系管理等诸多方面有着广泛地应用；在气象预报方面，可以根据以往的历史数据来 预测严重暴风雨；在金融领域，主要用来对客户进行信用评估以及防止欺诈等方面； 西南交通大学硕士研究生学位论文 ＩＩＩＩＩＬ 在电信业，主要是实现客户保持及发现潜在客户；在安全反恐方面，利用数据挖掘可以解决视频图，以及序列中的动作识别问题，这样，可以给专家提供很好的技术支持。 但是，基于决策树的有些数据挖掘技术还存在以下问题： （１）多值偏向问题。在决策树构造过程中，采用信息增益方法来选择最佳分裂属 性，此方法倾向于选择具有大量不同取值的属性。此问题会使构造的决策树产生过度 拟合、规模过大、产生的规则长度过长等缺陷。 （２）计算效率偏低。因为决策树算法在选择属性时采用的是信息论里熵的概念， 在计算信息熵时要用到对数计算（１０９），这使得计算复杂度增加。 （３）测试属性的约简。现有的测试属性约简算法不够成熟，决策树算法一般都是 利用原始的训练集进行构建，没有对测试属性进行约简，故而增加了算法的计算量。 （４）决策树剪枝方面。在决策树的构建阶段，生成的决策树依赖于训练样本，这 样就可能造成对训练样本的过度适应；可能会使决策树产生不必要的分枝，从而导致 在使用决策树模型对观察样本实施分类时出错。要避免这种错误，就要对决策树进行 ．修剪，去除多余的分枝。 目前的修剪算法在精度和复杂度方面都不是很好，有待做深入研究和改进。 本文主要对多值偏向和计算效率低两个问题进行研究。 １．２国内外研究现状 当今，决策树技术在数据挖掘中的应用研究，已是很热门的领域，国内外有很多 公司都推出了自己的数据挖掘系统，这其中很多都采用决策树方法。也有一些公司开 发出了数据挖掘工具，有些是专门供商业上用的；有些则是开源的，可以商用，也可 以为做数据挖掘开发的人员使用。关于这方面的内容，将在后面的章节中作详细介绍。 在决策树算法方面，国外的研究要早些。ＣＬＳ．概念学习系统【５】，它可以说是最早 的决策树学习系统，是１９６６年由ＨｕｎｔＭａｒｔｉｎ和Ｓｔｏｎｅ提出的决策树学习算法，该系统 第一次提出使用决策树进行概念学习，是后来许多决策树学习算法的基础。ＣＬＳ算法 的思想就是从一个空的决策树出发，利用规则添加新的判定节点来改善原来的决策树， 直到该决策树能正确地把训练实例分类为止。 １９８４年，Ｂｒｅｉｍａｎ．Ｌ，Ｆｒｉｅｄｍａｎ．Ｊ．Ｈ和Ｏｌｓｈｅｎ．Ｒ．Ａ提出了ＣＡＲＴ（ＣｌａｓｓｉｆｉｃａｔｉＯＲＡｎｄ ＲｅｇｒｅｓｓｉｏｎＴｒｅｅ）【６】分类算法。此算法使用具有最小基尼指数值的属性作为测试属性， 并采用二分递归分割的技术。即把当前样本集分为两个子集，使生成的决策树的每一 个非叶子节点都只有两个分枝。所以，生成的决策树是一棵结构简洁的二叉树。ＣＡＲＴ 算法使用交叉确定（ｃｒｏｓｓｖａｌｉｄａｔｉｏｎ）的后剪枝方法，此方法在小样本集上进行挖掘不 会造成过度拟合的问题。但是，ＣＡＲＴ算法最初建立的决策树也有错误，因其有些叶 西南交通大学硕士研究生学位论文 １９８６年Ｑｕｉｎｌａｎ提出了著名的ＩＤ３算法【７】，ＩＤ３算法体现了决策树分类的一些优点：算法的理论清晰，方法简单，学习能力较强。但该算法也有一些缺点，主要是不能处 理连续值属性；不能处理具有残缺值的训练集；使用信息增益作为测试属性的选择标 准，但此标准往往偏向于选择那些具有较多取值的属性。此外，ＩＤ３生成的是一棵多叉 树。所以，针对ＩＤ３存在的这些问题，学者们后来提出了针对不同问题的改进算法。 在ＩＤ３算法的基础上，１９９３年Ｑｕｉｎｌａｎ提出了Ｃ４．５算法［８】，它是ＩＤ３算法的改进。 Ｃ４．５算法不但继承了ＩＤ３算法的优点，还增加了对连续属性、缺失值属性的处理，使 用了后修剪及交叉验证等技术。 为了能处理大规模的数据集，１９９６年，ＭｅｈｔａＭ，ＡｇｒａｗａｌＲ和ＲｉｓｓａｎｅｎＪ等人提 出了高速可伸缩的有监督的ＳＬＩＱ算法；以及ＳｈａｆｃｒＪ等人提出的ＳＰＲＩＮＴ分类方法 ＳＬＩＱ（ｓｕｐｅｒｖｉｓｅｄｌｅａｒｎｉｎｇ ｑｕｅｓｔ）【９】和ＳＰＲＩＮＴ（ｓｃａｌａｂｌｅｐａｒａｌｌｅｌｉｚａｂｌｅｉｎｄｕｃｔｉｏｎｏｆ ｄｅｃｉｓｉｏｎｔｒｅｅｓ）［１０】是比较有代表性的两个算法。ＳＬＩＱ算法具有很好的伸缩性，但是它 对主存容量要求较高。于是ＪｏｈｎＳｈａｒｅｒ等人提出ＳＰＲＩＮＴ算法，提出此算法的目的就 是解决主存容量的限制问题，与ＳＬＩＱ相比，ＳＰＲＩＮＴ算法真正摆脱了主存容量的限制， 并且还具有并行性。但是，ＳＰＲＩＮＴ算法要把属性列表放在内存，这使得存储代价太高， 并且节点分割处理的过程较为复杂，加大了系统的负担。 １９９８年，Ｒａｊｅｅｖ，Ｒａｓｔｏｇｉ等人提出了ＰＵＢＬＩＣ（Ｐｒｕｎｉｎｇ Ｃｌａｓｓｉｆｉ２ｃａｔｉｏｎ）算法［１１】。它继承了ＣＡＲＴ算法在建树方面的基本原理，并且还使用了高效的剪枝策略；它是在建树的同时对决策树进行剪枝。此算法通过计算每个节点的 目标函数值，来估计该节点在以后的建树阶段是否被删除。如果该节点将要被删除， 就不会扩展该节点，否则，就扩展该节点。此方法使建树和树的剪枝在一个阶段处理， 不需要分两个阶段，从而提高了算法的执行效率。 ２００２年，Ｒｕｇｇｉｅｒｉ Ｓ提出了Ｃ４．５的改进算法一高效Ｃ４．５（ＥＣ４．５：Ｅｆｆｉｃｉｅｎｔ Ｃ４．５） 算法【１２】。ＥＣ４．５使用二分搜索法来代替线性搜索。在生成同样的一棵决策树时，ＥＣ４．５ 的效率是Ｃ４．５的５倍，但是ＥＣ４．５在执行时所占用的内存空间比Ｃ４．５要多【１３】。 ２００３年，Ｃ．Ｏｌａｒｕ提出了模糊决策树分类方法一软决策树【１４】。软决策树综合利 用决策树的生成和修剪来决定树的结构，并利用重修和磨合的方法来提高树的归纳能 力。所以，软决策树比一般的决策树分类的正确率要高些。为了进一步提高软决策树 的分类准确率，近两年来，又有人提出了模糊神经网络决策树（Ｎｅｕｒｏ．ＦＤＴ－ｎｅｕｒａｌ ｎｅｔｗｏｒｋｓ．Ｆｕｚｚｙ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ）【１５】。Ｎｅｕｒｏ．ＦＤＴ算法的分类准确率更高，提取出的分 类规则更易于理解。同时，ＳａｓｏＤｚｅｒｒｏｓｋｉ对ＭＲＤＴＬ（Ｍｕｌｔｉ．Ｒｅｌａｔｉｏｎａｌ ＤｅｃｉｓｉｏｎＴｒｅｅ ａｌｇｏｒｉｔｈｍ多关系决策树分类算法）的主要理论和研究内容进行了总结和阐述【１６】。 ２００４年，分层归纳决策树算法［１７】由ＺＨＡＯ ＨＭ和ＲＡＭＳ提出。其思想来源于 西南交通大学硕士研究生学位论文 未扩展分层归纳方法。此算法通过引入一个最大归纳深度参数来限制归纳层次，调整这个深度限制参数就可以得到各个归纳层次的决策树，从中选择性能最好的一棵树作 为分类器。 ２００５年，ＷｉｔｏｌｄＰｅｄｒｙｃｚ和ＺｅｎｏｎＡ提出了Ｃ．模糊决策树算法（Ｃ．Ｆｕｚｚｙ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ，ＣＦＤＴ）［１８】。此算法使用模糊聚类的方法（ｆｕｚｚｙｃｌｕｓｔｅｒｉｎｇ ｍｅｔｈｏｄ）进行分类， 而不是传统的信息熵或信息增益。ＣＦＤＴ算法有一些优点，如在建立决策树是可以同时 考虑多个维度，它可以处理连续性数据，不需要对连续值进行离散化等。２００７年， ＣｈｅｎｇｍｉｎｇＱｉ又提出了一种改进的模糊决策树算法（．ｍｏｄｉｆｉｅｄｆｕｚｚｙ ｄｅｃｉｓｉｏｎ ｔｒｅｅ，ＭＦＤＴ）［１９］。此算法在选择测试属性时分两种情况，对于多值属性和连续属性的 熵，先对其模糊化，然后再根据模糊理论计算得出；而其他属性的熵仍旧用传统的计 算熵的方法。作者通过实验证明，ＭＦＤＴ方法生成的决策树的效率要高，且规则易于 理解。 最近两年，ＺｈｏｎｇＭｉｎｇｙｕ等提出了ｋ－ｎｏｒｍ剪枝算法【２０】，此方法用Ｌｉｄｓｔｏｎｅ’Ｓ Ｌａｗ Ｓｕｃｃｅｓｓｉｏｎ方法来估计误差。作者通过实验证明该算法比ＣＣＰ和ＥＢＰ的准确率要高。在代价敏感决策树算法的研究上，ＤｕＪｕｎ提出了两种有效的预剪枝算法［２１１。其一 是把代价敏感决策树的深度降至两层，另一种是用一个预先制定的阀值来实现决策树 的剪枝。在决策树的构建与规则生成上，ＤｕＨａｉｚｈｏｕ，Ｍａ Ｃｈｏｎｇ［２２］提出了基于遗传学 编码技术的归纳决策树ＧＤＴ（Ｇｅｎｅｒａｌｉｚｅｄ ＤｅｃｉｓｉｏｎＴｒｅｅ）。此方法可以实现规则分类与 决策树构建过程的统一，能够避免传统的决策树的构建过程，使算法具有并行１参－． 与国外相比，国内在数据挖掘方面的研究稍晚些。但很多学者在决策树算法上进 行了深入的研究，也取得了不少成果。 １９９３年，国家自然科学基金首次提出支持数据挖掘的研究项目。目前，许多国内的科研单位和高等院校先后开展了知识发现的理论及其应用的研究，如中科院计算技 术研究所、清华大学、海军装备论证中心等等。 在关联规则方面，中国科技大学、中科院数学研究所、华中理工大学、复旦大学、 吉林大学等单位开展了对此算法的优化和改造；在非结构化数据结构以及Ｗｅｂ数据挖 掘方面，胡健、杨炳儒等人【２３】提出了一种新的Ｗｅｂ文本聚类算法一基于ＤＦＳＳＭＤＥ Ｗｅｂ文本聚类（ＷＴＣＤＦＳＳＭ）算法。南京大学、四川联合大学和上海交通大学等对此问 题也进行了探讨。在模糊方法方面，北京系统工程研究所在这方面的应用进行了比较 深入的研究。其中，北京大学还进行了对数据立方体代数的深入研究。在数据挖掘开 发平台上，中科院计算技术研究所［２４】智能信息处理重点实验室开发了他们的ＭＳ Ｍｉｎｅｒ－多策略知识发现平台，能够提供快捷有效的数据挖掘解决方案以及多种知识 发现方法。 首先，在测试属性的选择方面：洪家荣等【２５】从事例学习最优化的角度，研究了决 西南交通大学硕士研究生学位论文 策树归纳学习的优化原则，并提出了一种新的决策树构造算法――基于概率的算法ＰＩＤ。ＰＩＤ算法在决策树的规模和精度方面要好于ＩＤ３，但是在测试速度及训练速度上 比ＩＤ３要逊色些，而且用ＰＩＤ算法构建决策树时，某些属性可能会被重复使用，这样 生成的规则就不简洁。 １９９８年，刘小虎博士和李生［２６］教授认为，决策树优化是决策树学习算法中十分 重要的分支，提出改进的递归信息增益优化算法。对于ＩＤ３算法偏向于选择取值较多 属性这一缺点，２００１年，郭茂祖博士和刘扬教授１２７１针对多值偏向的问题，提出了一 种新的基于“属性一值对’’为内节点的决策树归纳算法，它所产生的决策树的大小及 对训练集的测试速度均优于ＩＤ３。此外，曲开社等人还通过引入用户兴趣度［２８】的方法 对ＩＤ３进行改进，这种方法就是在计算属性的信息熵时，通过用户兴趣度的调整来避 免ＩＤ３多值偏向的缺点。文献［２９１提出了一种基于关联度函数的决策树算法－ＡＦ （ＡｓｓｏｃｉａｔｉｏｎＦｕｎｃｔｉｏｎ）算法。．此算法在构建决策树时，用属性的关联度函数值作为选 取测试属性的标准，通过实验表明，与ＩＤ３算法性比，ＡＦ算法不仅克服了多值偏向问 题，分类正确率也有所提高。粗糙集在决策树方面的研究进来也是一个热点，文献［３０】 提出一种基于近似精度的决策树属性选择标准。即用变精度来代替近似精度，并利用 变精度正域对决策树预剪枝。这样不仅能克服噪声数据在构建决策树过程中的影响， 而且生成的决策树复杂性降低。 其次，，在构造机制方面：２００５年，黄沛【３１】等提出一种基于遗传算法的多重决策 树组合分类方法，该算法与单个决策树相比，具有更高的分类精度。 第三，在粗糙集与决策树的结合上：黄定轩【３２］等与２００５年提出一类加权连续属 性的多变量决策树构造方法。他引入粗糙集理论与模糊聚类理论来解决连续多变量属 性的选择问题，再利用聚类中心算法来解决连续变量的区间划分。２００６年张曙红［３３】 教授等则给出了一种面向连续值属性的模糊粗糙集决策树分析方法。此方法用模糊聚 类理论对属性进行离散化，通过计算模糊隶属度矩阵中的条件属性和类属性之间的模糊依赖性，来确定属性的重要性，并能发现冗余属性。文献【３４】对以往的多变量决策树 模型的不足，提出了一种基于粗糙集的改进的多变量决策树算法ＶＰＭＤＴ，该算法通过 选取属性的合理组合作为分裂属性，实验表明这样可使得树的规模相对较小。 第四，在新的决策树构造方法上：２００３年，杨宏伟博士和王熙照教授［３５】等均用 基于层次分解的方法，通过产生多层决策树来处理多类问题。２００６年，阳东升博士［３６】 等通过对组织协作网与决策树的描述分析提出了组织结构设计的新思路一基于决策个 体在任务上的协作关系设计最佳的决策树（组织决策的层次结构）。赵卫东【３７】、吴艳艳 【３８］等提出粗糙集理论应用于决策树的构造过程，并取得了很好的效果。 第五，在决策树的剪枝方面：王熙照等在预剪枝方面做了研究，实现了两种算法 【３９］，一是基于正例比的分支合并算法ＳＳＩＤ，另一个是基于最大增益补偿的分支合并 西南交通大学硕士研究生学位论文 算法ＭＣＩＤ。他们通过实验表明，用ＳＳＩＤ和ＭＣＩＤ算法的得到的决策树的可理解性和泛化精度都有所改善。同年，李卫东教授提出了一种多标准的组合评价决策树剪枝方 法［４０Ｊ。该方法通过选择每个标准分量的权重，由用户来决定所需要的决策树，丽不是 编程者。 目前及以后决策树技术研究的方向有以下几点： （１）决策树与其他技术的结合 在数据挖掘技术中，从对数据集的处理到最终输出需要的知识，要用到很多方面的技术。所以，决策树技术也需要和其他技术相结合，才能有创新。现在已有人把决 策树方法和模糊集合理论、遗传算法、神经网络等技术结合起来进行研究，都不同程 度地提高了决策树的处理效率与精度。多种技术的交叉应用必是以后决策树算法研究 的方向之之一。 （２）决策树分类的准确率 决策树的分类准确率也是研究的重点，因它是判断决策树算法优劣的标准之一。 所以，如何提高决策树分类的准确率或精度是决策树始终都要研究的方面。如多变量 决策树技术，虽是减小树的规模，但其最终目的是为了提高决策树的精度。 （３）数据集的预处理 训练集自身的情况如何，直接关系到分类结果的好坏。然而，实际的数据集往往存在大量的缺失数据、噪声数据等。当然，最简单的处理方法就是删除那些有缺失值 的记录，但这样会使分类结果不准确。目前的方法是用最常用的值来代替未知属性的 值，或是依据对象的其他属性值和类信息来预测未知属性的值。所以，对数据集缺失 值的处理也必定是以后研究的热点。 （４）决策树算法的增量学习研究 目前很多决策树算法不具有增量学习的功能，对于新的训练样本要重新建树，这 样就要花费大量的时间，降低了效率。虽然之前有一些这方面的研究，但目前有的增 量学习方法，主要是针对原有知识系统结构相同的新示例的学习，但实际上，还应包 括类别增量学习和属性增量学习【４ｌ】。类别增量学习就是分类器所用的训练样本发生了 增加，新增的训练样本的普通属性集和与原来的意义，但类别集和不同。所以，根据 新增训练样本的增加能适应类别增量及属性增量学习的决策树分类器的研究生很必要 综述，决策树算法已经有了广泛的应用，也有很多成熟的系统应用于各个领域。但决策树的各类算法，各有其优缺点。所以，在实际的应用中，应根据数据类型的特 点及数据集的大小来选择合适的算法。也正因为决策树的广泛应用，如何提高决策树 的预测精度，如何利用更好的方法来简化或改进决策树算法，如何把决策树算法与其 他技术相结合等问题，仍需进一步研究。 西南交通大学硕士研究生学位论文 １．３本文的主要研究内容论文主要研究了两项内容：以ＩＤ３算法为研究重点，主要研究其多值偏向和信息 熵的简化计算。 （１）决策树多值偏向。通过对决策树简化算法及其改进思想的研究，引入～个权 值，来解决多值偏向问题。该算法主要从时间复杂度和计算复杂度上来进行改进，在 保持分类能力不变的情况下，不需要复杂的运算就能解决在测试属性选择时的多值偏 向问题。 （２）信息熵的简化计算。由于ＩＤ３算法中涉及到比较麻烦ｌｏｇ运算，所以试图通 过应用高等数学中的麦克劳林公式对算法中的公式进行化简替换，以达到简化公式的 目的。用此方法建立的决策树与传统ＩＤ３建立的决策树在结点的属性选择上具有一致 性，所以建立的决策树是相同的，因为在很大程度上降低了时间复杂度，所以效率有 所提高。 １．４本文的组织结构 本文利用Ｗａｉｋａｔｏ大学开发的ＷＥＫＡ数据挖掘工具以及Ｆ圮］ｉｐｅ平台，并认真学习 了ＷＥＫＡ的系统结构等基础知识；在早期的决策树ＩＤ３算法的基础上，对其深入研究 并进行了改进。 本文共分为五章，内容安排如下： 第ｌ章介绍了本课题的研究背景和意义，详细介绍了决策树分类技术的国内外研 究现状，决策树分类技术的相关知识。 第２章对课题所用到的相关技术的介绍。首先，主要是数据挖掘技术、特点、过 程等的基本概念；其次研究了数据挖掘常用算法（包括分类算法和聚类算法），并介绍 了比较流行的数据挖掘工具（包括ＷＥＫＡ）。之后研究了决策树技术，分析了决策树分 类算法的基本理论，决策树的核心技术，决策树的常用算法等内容。 第３章，本章以决策树分类算法中的经典ＩＤ３算法为基础进行展开。首先介绍了 标准ＩＤ３算法的建树概念，信息论的基础知识，即熵、信息熵等相关理论。然后，重 点研究了几种选择测试属性的方法；对ＩＤ３算法进行了详细描述并举例说明其计算过 程。最后，通过实例应用分析了ＩＤ３算法的计算方法，并对其性能进行了分析，总结 出其有哪些优势，存在什么不足；对ＩＤ３存在的不足之处进行深入思考，最后提出对 ＩＤ３算法的改进思路。 第４章对ＩＤ３算法的改进研究。本章主要包括麦克劳林公式简介，它也是算法中 要用到的；ＩＤ３简化算法，ＩＤ３简化算法的信息增益的修正。首先是对原ＩＤ３算法的改 西南交通大学硕士研究生学位论文 进，通过应用麦克老林近似公式对ＩＤ３算法中信息熵的计算进行化简：使运算变得更加简单。然后继续对改进的ＩＤ３简化算法进行研究，通过对简化后属性信息熵的计算 公式增加一个函数来修正，从而避免了ＩＤ３算法偏向取值较多属性的缺点。最后，对 原算法和改进后的算法进行了总结及比较分析。 第５章，通过把开源的数据挖掘工具ＷＥＫＡ系统导入到ＪＡＶＡ开发平台Ｅｃｌｉｐｓｃ 里，对算法进行实验测试。通过比较改进前后算法在不同数据集上的分析结果，证明 改进后算法正确性及优越性，最终得出结论。 西南交通大学硕士研究生学位论文 第二章数据挖掘与决策树相关技术２．１数据挖掘的基础理论知识 ２．１．１数据挖掘的概念 目前，还没有对数据挖掘的精确科学的定义，从广义上来说，数据挖掘（ｄａｔａ ｍｉｎｉｎｇ，ＤＭ）就是先从庞大的数据体系或数据仓库里提炼出我们感兴趣的东西（它可能 在人们的预料之中，也可能在人们的预料之外），或者说，从海量的观察数据集中提炼 并分析出人们不能轻易察觉或断言的关系，最后给出一个有用的并可以被人们容易理 解的结论。简之，数据挖掘就是在数据中发现模式、知识，或数据间的关系。另外， 有一种简洁的定义，被人们普遍引用。数据挖掘就是从大量的、不完全的、有噪声的、 模糊的、随机的数据中，提取隐含在其中的，人们事先不知的，但又是潜在有用的信 息和知识的过程［４２，４３］。 数据挖掘是－１＂７综合性的学科，它结合了机器学习、统计学、模式识别、智能数 据库、知识获取、专家系统、人工智能、数据可视化以及高性能计算等领域，是－ｆ－ｊ 新兴的边缘学科；吸引了计算机专家、工程技术人员、认知科学家和统计学家的广泛 关注和极大兴趣。数据挖掘也被称为知识发现（ｋｏｎｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙＫＤ），在１９８９年， 第ｌｌ届国际人工智能的专题研讨会上，学者们首次提出了基于数据挖掘的知识发现 （ｋｏｎｗｌｅｄｇｅｄｉｓｃｏｖｅｒｙ ｄａｔａｂａｓｅｓ，ＫＤＤ）的概念【３】。２．１．２数据挖掘的特点 根据数据挖掘的定义，我们可以总结出它有如下几个特点： 第一，数据量之大。数据挖掘要处理的数据量往往都是巨大的。因此，如何高效 率地存取数据，如何使用数据集，以及根据实际数据找出高效的算法等，都是数据挖 掘研究者需要考虑的问题。 第二，数据的未知性和不完全性。企业的数据库里存储的数据，在收集时可能有 一个或几个重要的变量没有被收集，而这些变量在后来做数据挖掘时被证明是有用的， 可能还很重要。所以，数据的未知性和不完全性将会始终伴随着数据挖掘的过程。所 以，这就要用到数据仓库的数据处理技术。 第三，数据挖掘算法的新颖性。数据挖掘研究者往往不愿意把先验知识预先嵌入 算法内，他们认为这样就相当于做“假设检验＂，数据挖掘一般要求算法主动性地提示 一些数据内在的关系。所以，学者们都把算法的新颖性作为衡量一个数据挖掘算法好 坏的一个重要标准［３】。 ２．１．３数据挖掘的过程 数据挖掘的步骤如图２－１所示： 图２．１数据挖掘的基本过程 西南交通大学硕士研究生学位论文 第１１页 在上图的数据挖掘过程中，如果对每一步所得的数据不满意，则可以返回到上一 阶段重新执行相应的处理，也可以直接返回到原始数据再重新开始。比如对转换后的 的数据，如果转换后所得的数据符合预先既定的要求，则可以对该数据进行下一步骤， 即数据挖掘以及对挖掘结果的分析；否则，可以改变挖掘方法再重复挖掘过程任务或 返回到前面的步骤执行。如果所得数据符合要求，则可以进入下一步。有时需要重复 上图中的某些步骤；而且，图中的四个步骤的划分界限也不是截然分开的、孤立的。 根据上面的流程图下面逐一解释［３】： 原始数据的采集，这部分在一个系统开发的总费用中占有很大比重，为确保在以 后的工作中有良好的性能，尽量要采集到足够多的原始数据。 抽样，就是把原始数据中具有代表性的数据抽取出来，并把这些数据称为样本。 数据预处理，这个过程就是将一些不适合用来训练和学习的数据排除在系统之外， 包括不完全数据、噪声数据、与挖掘主题无关的数据以及矛盾数据等。 经过抽样和清理之后得到的结果，就是数据样本集，此时得到的样本集也可以用 来训练和学习。但此时得到的数据，其形式可能不是系统需要的，在这种情况下就需 要对数据进行转换。 数据转换，其功能就是将数据转换为适于进行数据挖掘的数据存储形式，并把转 换后的数据存储到事先建好的数据仓库里。到此，如果对转换后的数据不满意，就要 返回到上一阶段，或从原始数据重新进行抽样工作。如果满意，则可以进入下一步。 数据挖掘（ｄａｔａｍｉｒ．．．ｉｎｇ），数据进入数据仓库之后就可以利用各种数据挖掘算法来 实施数据挖掘了。此过程包括特征选择、模型选择、模型训练和评价等。 结果分析，数据挖掘结果出现后，就要对结果进行解释并评估。具体的解释与评 估方法应根据数据挖掘操作结果所制定的决策来定。因为挖掘出来的结果最终要面向 用户，故需要对发现的模式或规律进行可视化，这样更有利于分析挖掘的结果。此外， 有时还要把所得到的知识集成到企业的系统中去，这样才能使挖掘出来的知识在实际 的管理决策分析中得到应用。 ２．１．４数据挖掘的任务 数据挖掘技术可以发现多种知识：广义型知识、特征型知识、差异型知识、关联 型知识、偏离型知识和预测型知识等。在实际应用中，用户事先可能并不知道数据里 到底存在哪些有价值的知识，因此一个好的数据挖掘系统，它应该具备同时搜索发现 多种模式的知识的功能，来满足用户的实际需要。此外，数据挖掘系统还应能够挖掘 出多种层次的模式知识。数据挖掘的任务以及所能够挖掘的知识类型有如下几种 【４５，４６］－， （１）分类（ｃｌａｓｓｉｆｉｃａｔｉｏｎ）和回归分类一直都是数据挖掘中很重要的任务，它在商业上的应用也很广。分类的目的 西南交通大学硕士研究生学位论文 第１２页 是提出一个分类函数或分类模型，利用该模型，能把数据库或数据集中的数据映射到 给定类别中的某一个。分类和回归的相同点是，它们都可以用来预测，预测的目的就 是从历史数据中自动推导出给定数据的推广描述，进而对未来数据进行预测。分类和 回归不同的是，分类的输出结果是离散的类别值，而回归输出的结果是连续的数值。 ．（２）聚类（ｃｌｕｓｔｅｒｉｎｇ） 当我们不是预测数据的类别，而是把数据很自然的分组时，就要用到聚类技术。 聚类就是根据数据的不同特征，把其分成不同的数据类。聚类的目的是，使属于同一 类别的个体之间的距离尽可能的小，而不同类别的个体之间的距离尽可能的大。聚类 是概念描述和偏差分析的先决条件。与分类不同的是，在聚类操作中，对要划分的类 是事先未知的，类的形成完全是数据驱动的，属于无指导性学习方法。 （３）相关性分析 关联分析就是发现特征之间或数据之间的相互依赖关系。数据相关性关系代表了 一类重要的可被发现的知识，这类知识可被其他算法使用。数据的依赖关系有着广泛 的应用，一个典型的例子就是购物篮分析，对顾客购买的商品进行分析，确定客户的 购买偏好和规律，据此来设计商品的摆放布局；并通过商品购买关联分析的结果，实 现商品或服务的交叉销售，对客户实行主动推销策略，实现准确的商品促销。 （４）偏差分析 偏差分析或孤立点分析也是数据挖掘的主要任务之一。偏差分析就是分类中的反 常实例、例外模式、观测结果对期望值的偏离以及测量值随时间的变化等，就是找出 观察结果与参照量之间的有意义的差别。其中，异常有如下几种情况：不满足常规的 异常例子、出现在其他模式边缘的奇异点、在不同时刻发生了显著变化的某个元素或 集合、观察值与模型推测出的结果之间有显著的差异等。有些数据挖掘方法将偏差或 孤立点作为噪声或例外丢掉，然而在有些特殊应用中如欺诈检测，异常事件可能更值 得研究，针对孤立点的数据分析称为孤立点挖掘。 （５）概念描述 概念描述就是对某类对象的深层含义进行描述，并且概括这类对象的相关特征。 概念描述又可分为两类：特征性描述和区别性描述。特征性描述是对某类对象的共同 特征进行描述；区别性描述就是针对不同类对象之间的区别。若要生成一个类的特征 性描述，要用到该类对象中所有对象的共性。而生成区别性描述的方法有很多，如决 策树方法、遗传算法等。 ２．２数据挖掘的常用算法 ２．２．１神经网络（ＮＮ） 神经元网络技术是属于软计算（ｓｏｆｔｃｏｍｐｕｔｉｎｇ）领域内一种重要方法，也是一种比较 西南交通大学硕士研究生学位论文 第１３页 新的计算模型。此计算模型通过模仿人脑神经网络的结构和工作机制而构建；使用许 多简单的计算单元（称为节点ｎｏｄｅ）连成网络，来实现大规模的并行计算是神经网络 的一个特点。神经网路是以自学习的数学模型为基础的，神经网络一经建立，便可以 对大量复杂的数据进行分析；并能完成非常复杂的模式抽取和趋势分析，这些对人脑 或计算机来说都是很不容易的事［４７】。ＮＮ由彼此互相连接的输入层、中间层（或称隐 藏层）、输出层几部分组成。输入层负责处理输入的数据；由多个节点组成的中间层负 责完成大部分网络工作；输出层主要是输出数据分析与执行后的结果。神经网络的优 点是，在ＫＤＤ的应用方面，当要从复杂或不精确的数据中推导出概念或确定走向时， 利用ＮＮ技术十分有效。但是，当用ＮＮ来分析复杂的系统时，比如金融市场，ＮＮ则 需要复杂的结构以及大量的神经元和连接数，而往往现有的事例数（不同的记录数） 不能满足训练样本的要求。下图２．２是一个典型的ＢＰ（反向传播学习算法Ｂａｃｋ ＰｒｏｐａｇａｔｉｏｎＬｅａｍｉｎｇＡｌｇｏｒｉｔｈｍ）网络示意图： 图２－２两层ＢＰ网络示意图如上图２．２所示，ＢＰ模型也是有输入层、隐含层和输出层组成。输入层的节点对 应于实际应用中的预测变量；输出层的节点则是目标变量，它们都可以是多个。中间 的隐含层，是处理数据的主要部分，其层数和每层的节点数是神经网络复杂度的衡量 指标之一。如上图，其工作原理是【４４】，正向传播，在此过程中，输入信息从输入层、 经隐含层的逐层处理，数据最后传到输出层；每一层的神经元的状态只影响下一层神 经元的状态。反向传播，若在输出层得到的结果不是预期的（比如误差大于要求的 精度），可以将误差信号沿着原来的连接通道反向传播，通过修正各层神经元的权重来 使误差减小。重复上述、过程，最后可得到符合要求的期望结果再输出。 ２．２．２决策树 ．决策树【４】【４８】是一种常用的数据挖掘算法，它是从机器学习领域中发展起来的一 西南交通大学硕士研究生学位论文 第１４页 种分类函数逼近方法。其基本思想是贪心算法，即通过自顶向下的递归方式构造决策 树。决策树算法的分类模型是～棵有向无环树。决策树中的节点可以分成根节点、内 部节点和叶节点。树的最高层节点就是根节点，一棵决策树只有一个根节点。每个内 部节点都代表一个属性（取值）的测试，每个分枝代表属性的一个取值。如果节点没 有分支就是叶子节点，每个叶节点都对应一个类标号（类别）及其取值。如下图２．３ 所示，就是一个简单的决策树示意描述，该决策树描述的是根据天气的综合情况，对 是否出去打球进行分类。图中椭圆代表内部节点，矩形代表叶子节点（类别）。分枝上 的字母是属性的取值。比较常用的、成熟的决策树算法有１Ｉ）３、Ｃ４．５、ＣＡＲＴ、ＳＬＩＱ、 ＳＰＲＩＮＴ、ＣＨＬ奶和ＰＵＢＬＩＣ。 ｒａｉｎｙ ＝ｎｏｒｍａｌ－，兀瓜Ｅ 图２－３决策钳示意图２．２．３基因算法 基因算法或遗传算法（ｇｅｎｅｔｉｃａｌｇｏｒｉｔｈｍ，ＧＡ），它起源于对生物系统进行的计算机 模拟研究，是一种受生物进化的启发，利用计算机来模拟生物进化的学习方法。早在 １９６２年，Ｈｏｌｌａｎｄ教授首次提出ＧＡ算法的思想，此算法一经提出就吸引了很多研究者
（转载请注明出处和)