第２１卷第２期 计算机技术与发展 Ｖ０１．２ｌ Ｎｏ．２ ２０１１年２月 ＣＯＭＰＵＴＥＲ ＴＥＣＨＮＯＬＯＧＹ ＡＮＤ ＤＥＶＥＬＯＰＭＥＮＴ Ｆｅｂ．２０１１ 增量式的多变量决策树构造算法研究 常志玲 ，张晓玲 （１．洛阳师范学院信息技术学院，河南洛阳４７１０２２； ２．河南科技大学电子信息工程学院，河南洛阳４７３０００） 摘要：针对增量数据集，结合粗糙集理论和多变最决策树的优点，给出了增量式的多变量决策树构造算法。该算法针对 新增样本与已有规则集产生矛盾，即条什属性相匹配，而决策属性不匹配的情况，计算条件属性相对于决策属性的核，如 果核不为空，则计算核相对丁决策属性的相对泛化，根据不同的结果形成不同的子集，最终形成不同的决策树分支。该算 法很好地避免了在处理增量数据集时，不断重构决策树。实例证明该算法的正确性，对处理小增量数据集具有良好的性 能。 关键词：增量式学习；多变量决策树；粗糙集；相对泛化 中图分类号：ＴＰ１８ 文献标识码：Ａ 文章编号：１６７３—６２９Ｘ（２０１１）０２—００９０—０４ Ｓｔｕｄｙ ｏｆ Ｂｕｉｌｄｉｎｇ Ｉｎｃｒｅｍｅｎｔａｌ Ｍｕｌｔｉｖａｒｉａｔｅ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ ＣＨＡＮＧ Ｚｈｉ—ｌｉｎｇ ，ＺＨＡＮＧ Ｘｉａｏ—ｌｉｎｇ （１．Ａｃａｄｅｍｙ ｏｆ Ｉｎｆｏｒｍａｔｉｏｎ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｕｏｙａｎｇ Ｎｏｒｍａｌ Ｕｎｉｖｅｒｓｉｔｙ，Ｌｕｏｙａｎｇ ４７ １０２２，Ｃｈｉｎａ； ２．Ｅｌｅｃｔｒｏｎｉｃ＆Ｉｎｆｏｒｍａｔｉｏｎ Ｅｎｇｉｎｅｅｒｉｎｇ Ｃｏｌｌｅｇｅ ｏｆ Ｈｅｎａｎ Ｕｎｉｖｅｒｓｉｔｙ ｏｆ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ，Ｌｕｏｙａｎｇ ４７３０００，Ｃｈｉｎａ） Ａｂｓｔｒａｃｔ：Ｉｎ ｔｈｉｓ ｐａｐｅｒ，ａ ｎｅｗ ａｌｇｏｒｉｔｈｍ ｔｏ ｂｕｉｌｄ ｉｎｃｒｅｍｅｎｔａｌ ｍｕｌｔｉｖａｒｉａｔｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｉｓ ｐｒｏｐｏｓｅｄ．Ｔｈｅ ａｄｖａｎｔａｇｅｓ ｏｆ ｔｈｅ ｒｏｕｇｈ ｓｅｔ ｔｈｅ・ ｏｒｙ ａｎｄ ｔｈｅ ｍｕｌｉｔｖａｒｉａｔｅ ｄｅｃｉｓｉｏｎ ｒｔｅｅ ａ／＇ｅ ｃｏｍｂｉｎｅｄ ｉｎ ｔｈｉｓ ｍｅｔｈｏｄ．Ａｉｍｉｎｇ ａｔ ｔｈｅ ｉｎｃｏｎｓｉｓｔｅｎｃｙ ｂｅｔｗｅｅｎ ｈｔｅ ｎｅｗ ｓａｍｐｌｅ ａｎｄ ｔｈｅ ｏｌｄ ｓａｎｌ－ ｐｉｅ，ｔｈｅ ｃｏｒｅ ｉｓ ｃｏｍｐｕｔｅｄ．Ｉｆ ｈｔｅ ｃｏｒｅ ｉｓ ｅｍｐｔｙ，ｔｈｅ ｇｅｎｅｒａｌｉｚａｔｉｏｎ ｂｅｔｗｅｅｎ ｃｏｒｅ ａｎｄ ｄｅｃｉｓｉｏｎ ａｔｔｒｉｂｕｔｅ ｗｉｌｌ ｂｅ ｃｏｍｐｕｍｄ，ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｒｅ‘ ｓｕｌｔｓ ｗｉｌｌ ｂｅ ｔｈｅ ｄｉｆｆｅｒｅｎｔ ｂｒａｎｃｈｅｓ ｏｆ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ａｔ ｌａｓｔ．Ｔｈｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅ ｒｅｂｕｉｌｄｉｎｇ ｉｓ ａｖｏｉｄｅｄ ｉｎ ｔｈｅ ａｌｇｏｒｉｔｈｍ ａｎｄ ｔｈｅ ｖａｌｉｄｉｔｙ ｏｆ ｈｔｅ ｌａｇｏｒｉｔｈｍ ｉｓ ｐｒｏｖｅｄ ｂｙ ｔｈｅ ｅｘａｍｐｌｅ． Ｋｅｙ ｗｏｒｄｓ：ｉｎｃｒｅｍｅｎｔａｌ ｌｅａｒｎｉｎｇ；ｍｕｌｔｉｖａｒｉａｔｅ ｄｅｃｉｓｉｏｎ ｔｒｅｅ；ｒｏｕｇｈ ｓｅｔ；ｇｅｎｅｒａｌｉｚａｔｉｏｎ Ｏ 引 言 些算法 ’ 等。另外还有关于增量决策树的一些应用 所谓增量式学习…，就是针对一个数据集，当增加 研究 ，但这些算法构造出来的都是增量式的单变量 新样本时，仅仅在原数据集的基础上作由新样本引起 决策树。决策树有单变量和多变量之分，单变量决策 的更新，而不需要重建所有的数据集。这样数据集随 树就是在每个节点上只检验单个属性，不考虑属性间 着样本数据的增加就处于时常更新状态，就能够在原 的相关性，这一限制使得有些属性在一棵决策树中某 有知识的基础上进行快速的学习，进而节省了大量的 一路径上被多次检验。多变量决策树在树的节点上可 时间。而现实生活中，数据集就是不断增加的，例如超 以同时检验多个属性，其优点是叶节点数和深度比较 市、银行等行业数据一天就有上万条记录增加，因此增 小。 量式的学习更符合人们的思维。 文中针对上述问题，应用粗糙集理论” ，针对动态 从２０世纪８０年代中期开始，一些学者对决策树 增长的数据集，提出了增量式的多变量决策树构造算 的增量学习能力进行了研究，主要研究成果有：ＩＤ 增 法，实例表明随着样本的增加，本算法并不需要对决策 量学习算法 、ＩＤ Ｒ算法 及ＩＴＩ算法，还有其他的一 树进行重新构造，而只需要重构与样本相关的子树，大 大降低了建树的复杂性，并且获得很好的分类能力。 收稿日期：２０１０—０６—０４；修回日期：２０１０—０９—２８ 基金项目：河南省自然科学研究计划项目（２ｏ１０Ａ５２ｏ０３ｏ） １ 相关概念介绍 作者简介：常志玲（１９７６一），女，河南濮阳人，硕士研究生，讲师，主要 １．１ 决策树 研究方向为粗糙集理论、数据挖掘；张晓玲，硕士，讲师，研究方向为 决策树 。 是指用树形结构来表示决策集合，是 数据挖掘。 一种直观的知识表达方法，同时也是高效的分类器，可 第２期 常志玲等：增量式的多变量决策树构造算法研究 ．９１． 以非常容易地产生关联规则。其中每个内部节点表示 在一个属性上的测试，每个分枝代表一个测试输出，而 为Ｐ的Ｑ一核，记为ｃｏｒｅ。（Ｐ） 。对于整个决策表来 说，核属性是非常重要的，去掉核中属性将改变整个决 每个树叶节点代表类或类分布。树的最顶层节点是根 节点。构造决策树的主要思想是以信息论 为工具， 策表的决策。 １．５相对泛化的定义 在各非叶节点选择重要的属性或属性组，自上而下分 割训练实例集，直到满足某种终止条件，即节点中的实 例属于同一类。 理想的决策树分为３种 。。ｉ（１）叶节点数最少； （２）叶子节点深度最小；（３）叶节点数最少且叶子节点 相对泛化是定义在两个等价关系之间的，那么一 个等价关系相对于另外一个等价关系的泛化定义 为 ： 设Ｐ和Ｑ是 上的两个等价关系簇，且 Ｐ＝｛ｘｉ，ｘ２，…， ｝ Ｕ／Ｑ：｛ｙＩ，】，２，…，ｙ ｝ 令 ｚ ＝ｕ｛ ：置 ｘ Ｅｕ，ｐ 深度最小。但是最优决策树已经被证明是一个ＮＰ－ ｈａｒｄ问题。 １．２粗糙集 ｝ ｉ＝１，２，…，ｍ ，Ｖ ｉ｝ （３） （４） Ｚ ＋。＝ｕ｛ ： ＥＵ／Ｐ 粗糙集（Ｒｏｕｇｈ ｓｅｔｓ）理论是由波兰科学家Ｐａｗ— 则称｛ｚ。， ，…，ｚ ｝在 上确定的等价关系为Ｐ相 对于Ｑ的泛化，记为ＧＥＮ。（Ｐ）。 ｌａｋ 于２Ｏ世纪８０年代提出的一种处理不确定问题 的方法，它的观点就是 ：知识（即人的智能）就是一 种对对象进行分类的能力，可以用等价类形式化表示 ２增量式的多变量决策树构造算法 ２．１算法描述 分类，可以这样理解：知识是用等价类（记为Ｒ）对离 散空间的一种划分，记为Ｕ／Ｒ＝｛ ，Ｘ２，…，Ｘ ），其中 针对决策表Ｓ＝（ ，ｃ ｕ Ｄ， ，其中Ｃ＝｛Ⅱ ， 就是Ｕ／Ｒ的一个等价类。 １．３决策表 一ｏ ，…，ｏ ｝是条件属性集，Ｄ＝｛ｄ。，ｄ ，…，ｄ ｝是决策 属性集，假定决策表中样本是动态增长的。那么新增 一个决策表可以形式化定义为 ：Ｓ＝＜Ｕ，Ｃ Ｕ 个样本，存在三种情形： 情形１：新增样本与已有规则集相容。 情形２：新增样本与已有规则集相容，但不包含。 情形３：新增样本与已有规则集产生矛盾，即条件 Ｄ， ＞，其中Ｕ＝｛ｕ．，Ｍ …．，ｕ ｝是所感兴趣对象 的有限集合，Ｃ Ｕ Ｄ是属性的有限集，其中Ｃ为条件属 性集，Ｄ为决策属性集，并且Ｃ ｎ Ｄ＝ ，Ｖ为属性集 Ｃ Ｕ Ｄ的值域，－厂：Ｕ ｘ（Ｃ Ｕ Ｄ）一 为一个信息函数， 属性相匹配，而决策属性不匹配。 针对这三种情形，结合核相对于决策类的泛化对 该决策表进行多变量决策树的构造。其算法描述如 下： 表示任一对象的属性在 上的取值，即 它指定了 中每一对象 的属性值。 ，ｒ）∈ ， 为表达语言中的决策规则，其中 和 分别称为 一 的因和果。对于一个决策表５，当所有规则 一 为真时，则称决策表｜ｓ是相容的，否则称不相容。 １．４核 算法：增量式多变量决策树构造（ＩＭＤＴ） 输入：动态增长的决策表Ｓ＝（ｕ，ｃ ｕ Ｄ， 输出：增量式的多变量决策树 （１）如果根节点为空，则把样本放入根节点的样 对于任何子集 ，称为一个概念。对于每个 — ＝ｕ｛Ｘｆ∈Ｕ： 本集，任选一属性ａｉ作为根节点的分裂属性； （２）否则，将样本沿树进行匹配，直到到达一个叶 概念 可以定义上、下近似为 ： Ｘ＝Ｕ｛Ｘ ∈Ｕ：Ｘ Ｘ｝ 节点。如果新增样本与已有规则集相容，则决策树无 需任何修改转（９）；如果新增样本与已有规则集相容， 但不包含，则需要增加新的分支转（９）；如果新增样本 ，ｎ ≠（２ｊ｝ 其中Ｒ— 是由 上在现有知识Ｒ下肯定属于 的元素组成的集合；Ｒ—Ｘ是可能属于 的元素组成的 与已有规则集产生矛盾，则转（３）； （３）对开始不匹配的节点所包含的子集，计算Ｃ 相对于Ｄ的核，即ｃｏｒｅ。（Ｃ）。若ｃｏＦｅ。（Ｃ）＝ 则转 （４）；否则，不妨设ｃｏｒｅ。（Ｇ）：｛ｏ，，ｏ ，…，。 ｝，如果 集合。设Ｐ和Ｑ是 上的两个等价关系，那么Ｑ的Ｐ 一正域定义为： ＰＯＳ （Ｑ）＝ｕ Ｐ—Ｘ ＥＵ／Ｑ （１） ＰＯＳ （Ｑ）是 中所有那些通过知识ｌＰ被肯定属 ｃｏｒｅ。（Ｃ）与作为子树节点的分裂属性组不相同则转 （５），否则，转（６）； 于Ｕ／Ｑ的元素组成的集合。如果 ｐｏｓ （Ｑ）＝ｐｏｓ （Ｑ） （２） 成立，则称ｒ∈Ｐ是Ｑ一不必要的，否则ｒ在Ｐ中是Ｑ一 （４）用ＩＤ 的方法选择一个最佳属性，作为根节 点，根据属性的不同取值将｜ｓ分裂为Ｓ。，Ｓ ，…Ｓ…， 针对子集Ｓ （ｉ＝１，２，…，ＩⅣ１），如果｜Ｓ 中的所有样本 必要的。Ｐ中所有９一必要的等价关系组成的集合称 ・９２・ 计算机技术与发展 第２１卷 都在同一决策类则转（７），否则如果用于划分的属性 不为空则令ｃ＝Ｃ ，Ｄ＝Ｄ 转（３）； （５）Ｐ＝ａ。八ａ ＾…＾ａ ，作为子树节点，计算Ｐ 相对于Ｄ的泛化ＧＥＮ。（Ｐ），根据不同的结果形成不 同的子集，记为ｓ ，ｓ ，…ｓ…，针对子集Ｓｉ（ｉ＝１，２， …，Ｉ ＮＩ），如果 中的所有样本都在同一决策类则转 图１ 样本１生成的决策树 （７），否则如果用于划分的属性不为空则令Ｃ：Ｃ ，Ｄ ＝Ｄ 转（３）； （６）针对与新增样本产生不相容规则的子树所有 ３．输入样本３，样本４，新增样本与已有规则集相 容，但不包含，则需要增加新的分支，如图２所示。 样本和新增样本合为一新的子集，计算该子集中Ｐ相 对于Ｄ的泛化ＧＥＮｏ（Ｐ），根据不同的结果形成不同 的子集，记为ｓ。，ｓ ，…ｓ ，针对子集ｓｌ（ｉ＝１，２，…， ｌⅣ１），如果ｓ 中的所有样本都在同一决策类则转 （７），否则如果用于划分的属性不为空则令Ｃ＝Ｃ ，Ｄ ＝Ｄ 转（３）； （７）返回Ⅳ为叶节点，以类Ｃ标记； （８）如果多个分支包含了分类属性组的所有取 图２样本２生成的决策树 ４．输入样本５，新增样本与已有规则集相容，则决 值，则合并该多个分支为一个分支； （９）返回一棵增量式的多变量决策树。 ２．２实例分析 策树无需任何修改，只把样本５放入样本４所在的子 集即可。 ５．输入样本６，新增样本与已有规则集产生矛盾， 并且是从根节点开始就不匹配，此时计算包括６个样 本在内的决策表的核，通过简单计算可得： 利用文献［１２］中一个相容决策表如表１所示，属 性集Ｃ＝｛ａ。，ａ ，ａ，，ａ ｝是条件属性集，属性集Ｄ＝ Ｕ／Ｃ＝｛｛１｝｛２｝｛３｝｛４｝｛５｝｝６｝｝ Ｕ／Ｄ＝｛｛１２，６｝｛３，４，５｝｝ ｛ｄ｝是决策属性集。决策树的内部节点（又名分裂节 点）用椭圆形表示；决策树的叶节点用它的决策类代 表，并用矩形表示，同时为了清楚起见，在矩形框中标 示出所包含子集。利用文中、给出的算法构造增量式 多变量决策树的执行过程如下： 由公式（１）可得： ＰＯＳ。（Ｄ）＝｛１，２，３，４，５，６｝ 考察ａ （ｉ＝１，２，３，４），在ｃ中相对于Ｄ来说是否 必要。为此，从Ｃ中去掉ａ．，可得： ＰＯＳ（ｃ＿ｌｄｌｌ１（Ｄ）＝ ｛２，４，５，６｝ ≠ ＰＯＳ。（ ） 由公式（２）可得ａ．在Ｃ中是Ｄ一必 要的。同理可以计算ａ 在ｃ中是Ｄ一必 要的，而口：和ａ，在ｃ中是 一不必要的， 由此可得ＣＯＲＥ。（Ｃ）＝｛ａ。，口．｝。由于核 和根节分裂属性ａ。不一致，因此要计算 核相对于决策类的泛化： 令Ｐ＝ａ，Ａ ａ ，下面计算Ｐ相对于Ｄ 的泛化在 上导出的划分： Ｕ／Ｐ＝｛｛１｝｝２｝｛３｝｝４，５｝ｉ６｝｝ 由公式（３）和（４）可以计算出： ＧＥＮ （Ｐ）＝｛｛１，２，６｝｛３，４，５｝｝ １．输人样本ｌ（ｓｕｎｎｙ，ｈｏｔ，ｈｉｇｈ，ｆａｌｓｅ，Ｎ），由于根节 点为空，任选ａ。作为分裂属性开始建立决策树如图１ 所示。 由算法可知以ＧＥＮ （Ｐ）为决策树 的根节点，根据所求泛化结果，把决策表中的样本分成 不同的对象集。其中子集｛１，２，６｝都在同一决策类Ⅳ ２．输入样本２，新增样本与已有规则集相容，则决 策树无需任何修改，只把样本２放人样本１所在的子 集即可。 中，因返回叶节点并以Ⅳ作为标记，同理子集ｉ３，４，５ｆ 都在同一决策类Ｐ中，返回叶节点并以Ⅳ作为标记，返 回决策树如图３所示。 第２期 常志玲等：增量式的多变量决策树构造算法研究 ．９３． 需要对决策树进行重新构造，而只需要重构与样本相 关的子树，大大降低了建树的复杂性，从实例可以看 出，文中构造的增量式的多变量决策树最终结果和文 献［１２］算法所构造的静态多变量决策树相同，因此具 图３输入样本６后生成的决策树 有相同的分类能力，为考察本算法的有效性，又对文献 ［１２］等多个经典数据集进行增量式的多变量决策树 ６．输入样本７和样本８，新增样本与已有规则集 相容，则决策树无需任何修改，只把样本７和样本８分 别放人所在的子集即可。 构造，结果表明都能够构造出分类能力相同的决策树。 ７．输入样本９，新增样本与已有规则集产生矛盾， ３ 结束语 并且是从根节点开始就不匹配，此时计算包括９个样 增量式的多变量决策树算法结合粗糙集理论和多 本在内的决策表的核，计算得出其核和根节点分裂属 变量决策树的优点，处理增量数据集的多变量决策树 性组相同，即：ＣＯＲＥ （Ｃ）＝｛。。，。 ｝，所以只修改产生 构造问题，解决了传统的多变量决策树构造算法不能 矛盾的分支即可，即在核不变的情况下，重新计算子集 处理增量数据集的缺点。通过实例分析，利用增量算 （１，２，６，８，９）核相对于决策类的泛化，并以泛化为基 法可以一次完成决策树的构造，避免了对数据集的重 ］●Ｊ础进行重建子树，在子树重建过程中子集（１，８，９）决 复扫描和决策树的不断重构问题，而且可以构造出与 策类不一致，并且还存在未用于划分的属性｛ｎ，，ｎ ｝， 静态多变量决策树相同的分类能力的决策树。 则对此子集重新调用本算法选择ｎ 为分裂属性，如图 ４所示。 参考文献： ［１］王利，张喜平，郭林．增量式知识获取算法 综述［Ｊ］．重庆邮电大学学报，２００７，７（增刊）： ９９—１０２． １ ［２］ Ｕｔｇｏｆ Ｐ Ｅ．Ａｎ ｉｍｐｒｏｖｅｄ ａｌｇｏｒｉｔｈｍ ｆｏｒ ｉｎｃｒｅｍｅｎｔａｌ ｉｎｄｕｃｔｉｏｎ ｏｆ ｄｅｃｉｓｉｏｎ ｔｒｅｅｓ［Ｃ］／／Ｉｎ：Ｐｒｏｃｅｅｄｉｎｇｓ ｏｆ ｔｈｅ Ｅｌｅｖｅｎｔｈ Ｉｎｔ． Ｃｏｎｆｅｒｅｎｃｅ ｏｎ Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ．Ｎｅｗ Ｊｅｒｓｅｙ：ＩＥＥＥ，１９９４：３１８—４２３． ［３］ Ｕｔｇｏｆ Ｐ Ｅ．Ｉｎｃｒｅｍｅｎｔａｌ Ｉｎｄｕｃｔｉｏｎ ｏｆ Ｄｅｃｉｓｉｏｎ Ｔｒ－ 图４输入样本９之后的决策树 ｅｅｓ［Ｊ］．Ｍａｃｈｉｎｅ Ｌｅａｒｎｉｎｇ，１９８９（４）：１６１一ｌ８６． ８．输入样本１０，新增样本与已有规则集相 Ｙｉｎ Ｄ Ｓ，Ｗａｎｇ Ｇ Ｙ，Ｙｕ Ｙ．Ｄａｔａ－ｄｒｉｖｅｎ Ｄｅｃｉｓｉｏｎ Ｔｒｅｅ Ｌｅａｒｎ— 容，则决策树无需任何修改，只需把样本分别放入所在 ｉｎｇ Ａｌｇｏｒｉｔｈｍ Ｂａｓｅ Ｏｎ Ｒｏｕｇｈ Ｓｅｔ Ｔｈｅｏｒｙ［Ｃ］／／Ｉｎ：Ｐｍｃｅｅｄ— ｉｎｇ ｏｆ ｔｈｅ ｔｈｉｒｄ Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｃｏｎｆｅｒｅｎｃｅ ｏｎ ＭＬＣ．Ｓｈａｎｇｈａｉ： 的子集即可； ＩＥＥＥ，２００５：２１４０－２１４５． ９．输入样本１１，新增样本与已有规则集产生矛 蔡晨，李凡长．动态模糊决策树学习算法研究［Ｊ］．计算 盾，其情况和步骤７相同，采用同样的处理方法，构造 机技术与发展，２００７，１７（７）：７３—７６． 的决策树如图５所示（只是在图５的基础上去除还未 刘波，粱活民．基于增量决策树的快速ＩＤＳ研究与实现 输入的样本ｌ２，１３，１４）。 ［Ｊ］．计算机工程与应用，２００８，４４（７）：１４１—１４３． １０．分别输入样本１２，ｌ３，ｌ４后，新增样本与已有 Ｐａｗｌａｋ Ｚ．Ｗ．Ｒｏｕｇｈ Ｓｅｔｓ［Ｊ］．Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｍａｌ ｏｆ ｉｎｆｏｒ－ 规则集相容，则决策树无需任何修改，只需把样本分别 ｍａｒｉｏｎ ａｎｄ Ｃｏｍｐｕｔｅｒ Ｓｃｉｅｎｃｅ，１９８２，１１（５）：３１４—３５６． 放入所在的子集即可；最终获得的决策树如图５所示。 常志玲，周庆敏．基于变精度粗糙集的决策树优化算法［Ｊ］． 计算机工程与设计，２００５，２７（１７）：３１７５—３１７７． ［９］Ｈａｎ Ｊｉａｗｅｉ，Ｋａｍｂｅｒ Ｍ．Ｄａｔａ Ｍｉｎｉｎｇ Ｃｏｎｃｅｐｔｓ ａｎｄ ’Ｔｅｃｈｎｉｑｕｅｓ［Ｍ］．北京：机械工业出版社，２００１． ［１Ｏ］洪家荣，丁明峰，李星原，等．…种新的决策树 归纳学习算法［Ｊ］．计算机学报，１９９５，ｌ８（６）： ４７０－４７４． ［１１］苗夺谦，李道国．粗糙集理沦、算法与应用 ［Ｍ］．北京：清华大学出版社，２００８． 图５输入样本１４之后的决策树 ［１２］苗夺谦，王珏．基于粗糙集的多变量决策树构造方法 ２．３结果分析 ［Ｊ］．软件学报，１９９７，８（６）：４２５—４３１． 从决策树的构造过程来看，随着样本的增加，并不 ］』