决策树论文20篇060203.pdf

收稿日期 2005 01 04 基金项目 国家自然科学基金资助项目 69873007 作者简介 宫义山 1964 男 吉林德惠人 博士生 主要从事信息融合方面的研究 赵海 1959 男 辽宁沈阳人 教授 博士 生导师 主要从事信息融合 嵌入式 Internet 等方面的研究 信息科学与工程 文章编号 1000 1646 2006 02 0127 05 多源信息的模糊决策树融合算法研究 宫义山1 2 赵海1 哈铁军1 张永庆1 徐峰1 1 东北大学 信息科学与工程学院 沈阳 110004 2 沈阳工业大学 软件学院 沈阳 110023 摘要 针对不确定性问题 提出了一种新的基于知识发现的信息融合的方法 对不确定问题采用 精确的数学方法解决会得到不精确的结论 模糊决策树算法可以很好地解决这类问题 并能有效 地提取出模糊规则 即利用模糊决策树的 ID3 算法对测试空间中的大量不确定多源信息数据进行 综合分析 处理 建立准确的评估模型 提取隐含其中的规则 最终获取新的知识 此方法已成功应 用于吉林丰满水电数字仿真系统中的考核系统 实验证明 这种知识提取方法对处理大量无序 不 确定的数据很有效 关键词 信息融合 决策树 模糊 ID3 算法 水电仿真 考核系统 中图分类号 TP 391文献标识码 A Study on fusion algorithm of fuzzy decision tree for multi source information GONG Yi shan1 2 ZHAO Hai1 HA Tie jun1 ZHANG Yong qing1 XU Feng1 1 School of Information Science and Engineering Northeastern University Shenyang 110004 China 2 School of Software Engineering Shenyang University of Technology Shenyang 110023 China Abstract An imprecise result will be got if exact math method is adopted to solve uncertain problems Aiming at processing vast uncertain information in system a new information fusion method based on knowledge discovery is proposed Fuzzy decision tree arithmetic can be used for solving the kind of problems very well and fuzzy rules can be extracted effectively ID3 algorithm is employed for analyzing disposing vast uncertain multi source data synthetically in the given test space and correct evaluation model can build up new knowledge can be acquired by extracting the rules The method has been used in the examining system of Jilin Fengman hydropower digital simulation system The method is effective to dispose vast uncertain information Key words information fusion decision tree fuzzy ID3 arithmetic hydropower digital simulation examining system 对知识的提取是一个对提供数据进行评估的 过程 以往仅是对单一信源数据进行处理并获得评 估的结果 这样做的最大缺点是评估结果不客观 不准确 本文基于信息融合的思想 提出采用模糊 ID3 决策树算法对大量的多源不确定数据进行综 合分析 1 建立准确的评估模型 并获取新的知识 和规则的方法 这种方法克服了只靠单一信源数据 评估不准确的问题 解决了测试空间中信息数据不 确定的问题 并在文中给出了解决丰满水电数字仿 真系统的考核系统中不确定问题的实例 1模糊决策树算法 决策树算法是一种归纳推理算法 是逼近离 第 28 卷 第 2 期 2 0 0 6 年 4 月 沈阳工业大学学报 Journal of Shenyang University of Technology Vol 28No 2 Apr 2 0 0 6 散值的函数 对噪声数据有很好的健壮性 模糊决 策树算法是决策树算法的一种推广 用于处理测 试集和训练集的属性和分类都不确定的不确定性 问题 在模糊决策树建立过程中 以模糊信息熵作 为启发式 在结点上选取具有最大模糊信息增益 的属性作为扩展属性 每个扩展属性都有交集部 分 树中的结点被看作是此决策空间的模糊子集 本文采用的是模糊 ID3 决策树算法 2基于模糊决策树算法的融合模型 2 1融合系统的结构模型 信息融合技术是由传感器融合技术发展而来 的 是智能信息技术的核心基础之一 它利用多传 感器获得多源数据 从多信息视角研究信息处理 从而得出对目标更为准确 可靠的评估过程 近年 来已在各个领域获得了广泛的应用 2 本文采用分布式多传感器融合结构获得多源 数据 并对获得的大量不确定性数据进行分析 处 理 最终获取规则 融合结构如图 1 所示 图 1 信息融合结构图 Fig 1Schematic fusion process 图 1 所示的融合过程中 通过各个传感器实 时获得多源数据 并通过预处理单元对连续数据 信息进行离散 模糊处理 经过模糊 ID3 决策树 算法进行建模 修剪 准确率检测等步骤提取出模 糊规则 2 2融合系统的融合算法 2 2 1模糊决策树建模方法 模糊决策树是树状结构的一种 每个树叶结点 代表模糊类集合 每个内部节点表示训练例子空间 的一个模糊子集 每个分支代表一个模糊输出 3 模糊 ID3 决策树算法是以自顶向下各个击 破的方式构造树型结构的 算法的基本策略为 树叶代表训练样本的单个节点开始 选取模糊信 息熵最小的属性作为该树的根节点 如果样本 都在同一个类 且该类的置信度大于给定的阈值 则该节点成为树叶 并用该类标记 如果一个结点 上的属性全部使用过 则产生叶子 否则 选取 没有用过的具有最高模糊信息增益的属性作为扩 展属性 如果信息增益小于给定阈值 则产生叶 子 使用信息增益的基于熵的度量作为启发信 息 选择能够最好地将样本分类的属性 该属性成 为该节点的测试属性 对测试属性的每个已知的 值按扩展属性值进行模糊划分 并产生其结点 递归上述 步 形成每个划分上的模糊决 策树 一旦一个属性出现在一个节点上 就不必考 虑该节点的任何后代 将产生的模糊决策树转 换成模糊规则的形式 首先对示例的属性进行预处理 根据经验给 出不同的示例在不同属性集中的隶属度 i 其次开始训练 即从训练示例中产生模糊决 策树 设 S 是融合模型中的 s 个数据样本的模糊 集合 假设类标号属性具有 m 个不同值 定义 m 个不同类Ci i 1 2 m 设 si是类Ci中的样本 数 对一个给定的样本分类所需的期望信息由式 1 给出 I s1 s 2 sm m pi log 2 pi 1 式中 pi是任意样本属于 Ci的概率 并用 si S 估计 设 A 是此融合模型中的模糊属性 具有 v 个 不同值 a1 a 2 a 3 av 可以用属性 A 将 S 划 分为 v 个模糊子集 S1 S 2 S 3 Sv 其中 Sj包 含 S 中这样一些样本 它们在 A 上具有值aj 如果 A 选作模糊测试属性 即最好的分裂属性 则这 些子集对应于由包含模糊集合 S 的节点生长出 来的分支 设 s ij 是子集 Sj中类 Ci的样本数 根据 由 A 划分成子集的熵或期望信息由式 2 给出 E A v i 1 s 1 j s 2 j s mj s I s 1 j s 2 j s mj 2 其中 s 1 j s 2 j s mj s 充当第j个子集的权 并且等于子集 即 A 值为aj 中的样本个数除以 S 中的样本总数 模糊熵值越小 子集的划分纯度越 高 对于给定的模糊子集 Sj I s 1 j s2 j s mj m i 1 p ij log 2 p ij 3 其中 p ij s ij S j 是 S j中的样本属于类 Ci的概率 在 A 上分枝将获得的编码信息是 Gain A I s1 s 2 sm E A 4 即 Gain A 是由于知道属性 A 的值而导致的熵 的期望压缩 821 沈阳工业大学学报第 28 卷 此算法计算每个属性的模糊信息增益 具有 最高模糊信息增益的属性选作给定集合 S 的测 试属性 创建一个节点 并以该属性标记 对属性 的每个值创建分支 并据此划分样本 2 2 2模糊决策树修剪 完整的模糊决策树形成以后 一般不能立即 用于对新数据的分类或预测 4 因为 此时的这 棵完整的树并不是一棵分析新数据对象的最佳决 策树 这种现象一般称为 过度拟和 解决这个问 题的主要方法是对决策树进行必要修剪 常用的修剪技术有预修剪和后修剪两种 本 文采用后修剪技术进行决策树的修剪 后修剪技 术在允许决策树过渡拟和的基础上 根据一定的 规则 剪去决策树中的那些不具有一般代表性的 叶结点或分枝 一般规则是 在模糊决策树不断剪 枝的过程中 利用训练样本集或检验样本集数据 检验决策子树对目标变量的预测精度 并计算出 相应的错误率 5 用户可以事先指定一个最大的 允许错误率 决策树的后修剪过程如图 2 所示 图 2 决策树的后修剪示意图 Fig 2Schematic post pruning of the decision tree 2 2 3模糊决策树准确率的判定 对模糊决策树分类法的准确率的评估是非常 重要的 分类准确率是评价决策树模型性能的一 个重要标准 在保持方法中 给定的数据随机地划分为两 个集合 训练集和测试集 见图3 通常三分之二 的数据分配到训练集 其余三分之一的数据分配 到测试集 使用模糊训练集导出分类法 其准确率 图 3 保持法评估决策树分类 Fig 3Classification of conservation evaluate decision tree 用测试集评估 本文使用保持方法进行准确率评估 从数据 库中随机选择 50 条记录的数据集进行考核 实现 对模糊决策树的准确率评估 6 分别使用灵敏性 s 特效性 f 和精度 r 度量 7 这些度量定义为 s t p p 5 f t n n 6 r t p t p f p 7 其中 t p 真正样本数 p 正样本数 t n 真负样本数 n 负样本数 f p 假正样本数 样本正确率 a 为灵敏性和特效性度量的函 数 即 a s p p n f n p n 8 3实验分析 3 1成绩考核系统模糊决策树模型的实现 针对丰满水电仿真系统中考核系统存在的不 确定问题 根据数据样本建立总成绩分类的模糊 决策树模型 使用这种分析方法使教师可以掌握 不同工龄 不同班级 不同学历的学员对某个操作 规程的掌握情况 利用手动开机和调速器切手动 两个工况的考核票进行考核 从得出的考核结果 中取出 5 000 个数据进行模糊决策树训练 9 10 首先给定样本分类所需的期望信息 分类模 糊属性 成绩 具有三个不同值 好 中 差 由式 1 2 3 得 I s1 s 2 s 3 I 32 34 33 1 计算按每个属性划分数据样本所需的期望信 息及信息增益 由于工龄属性具有最高信息增益 所以它被 选作测试属性 从前面的叙述可以看出 建立模糊决策树是 一个递归的过程 所有的样本使用工龄属性分类 后 形成三个模糊样本集合 使用同样的方法分别 分析这三个样本 对于 工龄 老手 的集合 计算期望信息为 I s1 s 2 s 3 I 25 7 1 0 645 2 在 工龄 老手 的样本集合中由于学历属性 921 第 2 期宫义山 等 多源信息的模糊决策树融合算法研究 具有最高模糊信息增益 被选作测试属性 这时发 现在 工龄 老手 学历 职高 的样本集合中 所 有样本的成绩属性的值都为好 所以建立一个叶 子节点 同样分析其他两个集合 在 工龄 一般 的样本集合中 期望信息 I s1 s 2 s 3 I 7 19 14 0 959 8 在 工龄 生手 的样本集合中 没有成绩属 性为好的记录 期望信息 I s1 s 2 I 8 18 0 617 2 可知所有情况的第二个测试属性都选择为 学历 同时出现了两个叶子节点 通过所有模糊信息增益的计算 可以得到一 个使用后修剪技术修剪的模糊决策树 见图 4 图 4 总成绩分类决策树 Fig 4Decision tree of general grade classification 3 2根据考核结果决策树提取分类规则 根据考核结果提取模糊决策树表示的知识 并以 IF THEN 形式的分类规则表示 对从根到 树叶的每条路径创建一条模糊规则 沿着给定路 径上的每个属性 值对形成规则前件的一个合取 项 叶节点包含类预测 形成规则后件 总成绩模 糊决策树提取的模糊分类规则如表 1 所示 可以说 加入了数据分析功能的考核系统功能 更加强大 随着培训的不断深入 考核结果记录集迅 速膨胀 如果不采用有效的数据分析方法 这些数据 将失去任何价值 变为一堆 数据垃圾 采用基于决 策树分类的数据挖掘方法对这些数据进行分析 可 以从中有效地提取出 兴趣度 很高的信息 帮助教 师了解不同情况学员的培训效果 找出学员具体情 况与教师感兴趣的分类属性之间的关系规则 3 3实验结果 在丰满水电仿真系统的教学实践中 对一期 培训学员考核结果数据使用该数据分析方法进行 分析 并对二期培训的培训方式进行指导 采用两 种方式进行培训 原培训方法和经过指导的培训 方法 在人员总数为 168 人 考核内容为手动开机 操作规程的条件下 使用原来的培训方式进行培 训的学员成绩如表 2 所示 表 1总成绩决策树提取的分类规则 Tab 1Classification rules extracted from the count decision tree IF 工龄 老手 THEN 成绩 好 CF 1 00 IF 工龄 一般 AND 学历 本科 AND 培训 长 THEN 成绩 好 CF 0 93 IF 工龄 一般 AND 学历 本科 AND 培训 中 THEN 成绩 中 CF 0 87 IF 工龄 一般 AND 学历 本科 AND 培训 短 THEN 成绩 差 CF 0 64 IF 工龄 一般 AND 学历 专科 AND 培训 长 THEN 成绩 好 CF 0 78 IF 工龄 一般 AND 学历 专科 AND 培训 中 THEN 成绩 中 CF 0 87 IF 工龄 一般 AND 学历 专科 AND 培训 短 THEN 成绩 差 CF 0 77 IF 工龄 一般 AND 学历 职高 AND 培训 长 THEN 成绩 好 CF 0 43 IF 工龄 一般 AND 学历 职高 AND 培训 中 THEN 成绩 中 CF 0 64 IF 工龄 一般 AND 学历 职高 AND 培训 短 THEN 成绩 差 CF 0 91 IF 工龄 短 AND 学历 本科 AND 培训 长 THEN 成绩 好 CF 0 71 IF 工龄 短 AND 学历 本科 AND 培训 中 THEN 成绩 中 CF 0 63 IF 工龄 短 AND 学历 本科 AND 培训 短 THEN 成绩 差 CF 0 90 IF 工龄 短 AND 学历 专科 THEN 成绩 差 CF 0 75 IF 工龄 短 AND 学历 专科 THEN 成绩 差 CF 0 97 031 沈阳工业大学学报第 28 卷 表 2 原来的培训方式培训的学员情况 Tab 2Situation of students trained by the former training method 客观条件 人数 平均成绩对调速器切手动掌握情况 工龄长4687 327 人正确 占总数 58 7 工龄一般7175 949 人正确 占总数 69 0 工龄短5164 526 人正确 占总数 51 1 在人员总数为 187 人 考核内容为手动开机 操作规程的条件下 采用经过指导的培训方式培 训的学员成绩如表 3 所示 表 3 经过指导的培训方式培训的学员情况 Tab 3Situation of students trained by the fusion method 客观条件 人数 平均成绩对调速器切手动掌握情况 工龄长4889 734 人正确 占总数 70 8 工龄一般7677 659 人正确 占总数 77 6 工龄短6370 240 人正确 占总数 63 5 从数据中可以看出 采用了基于模糊决策树 分类方法进行考核结果数据分析后 教练员根据 指导信息制定出有针对性的培训计划 提高了培 训质量 使用改进的培训方式培训的学员 相比使 用原有培训方式培训的学员 无论是总成绩还是 对具体步骤的掌握程度 都有了明显的提高 4结论 本文基于信息融合的思想并结合仿真系统的 特点提出了用模糊决策树分析结果数据的方法 扩展了考核系统的功能 此方法已经在丰满水电 仿真系统的培训中得到成功验证 结论如下 1 信息融合是分析处理大量数据 提取有用 知识的技术 能有效地完成复杂的数据分析工作 2 对系统中存在的大量不确定性信息 如果 采用精确的数学方法会得到错误的结论 模糊决 策树算法可以很好地解决数据不确定问题 并能 有效地提取出模糊规则 3 本文很好地解决了水电仿真系统中考核 系统存在的信息不确定性问题 参考文献 1 Hall D L Mathematical techniques in multi sensor data fusion M Boston Artech House 1992 2 Fedotov G A Information fusion for turbulence mea surements in hydro physical applications A Proceed ings of the 4th International Conference on Informa tion Fusion C Montreal LM Canada 2001 3 9 3 Xu L Y Du X D Zhao H Application of neural fusion to accident forecast in hydropower station A Pro ceedings of the Second International Conference on In formation Fusion C California Omnipress 1999 1166 1171 4 Waltz E Linas J Multi sensor data fusion M Artech House 1991 5 谢彦红 杨理践 王向东 基于小波分析的管道缺陷 量化识别研究 J 沈阳工业大学学报 2005 12 648 651 Xie Y H Yang L J Wang X D Research on pipeline disfigurementquantitativerecognitionbasedon warelet analysis J Journal of Shenyang University of Technology 2005 12