论文部分内容阅读
决策树分类学习算法是使用最广泛、实用性很强的归纳推理方法之一，在机器学习、数据挖掘等人工智能领域有相当重要的理论意义与实用价值。 在各种决策树学习算法当中，最有影响力的是采用信息熵的下降速度作为选择测试属性的标准的ID3算法。但是ID3算法存在学习简单逻辑表达式的能力较差、偏向属性取值数目较多等缺陷。论文企图在ID3的基础上，针对其中的一些不足加以改进。 本文首先介绍了示例学习的扩张矩阵理论与决策树学习的最优化问题、ID3算法的信息论原理与实现以及C4.5算法的剪枝原理。然后针对ID3学习逻辑表达式方面的不足，提出了一种对ID3学习到的决策树进行简化的算法——基于蕴含规则的决策树简化算法(DTSA-BOIR，简记为BOIR)，BOIR以ID3算法构造的决策树为基础，先序遍历由ID3构造出来的决策树的各个节点，并对其子树进行比较，如果各子树的根属性都相同而且存在某些相应的分支对于各子树完全相同，则改变决策树中相应属性的层次关系并把相同的分支分别合并起来。 本文实现了BOIR对逻辑表达式的学习，并利用FAMn家族数据集对该简化算法进行了测试，实验所取得的数据验证了该算法的有效性。