论文部分内容阅读
决策树算法因它简单高效、知识提取简单、生成规则易于理解等优点,在数据挖掘领域占据十分重要的地位。然而,现实生活中涉及代价的问题普遍存在,传统的决策树算法已无法满足代价的需求。因此,将决策树和代价敏感学习相结合的算法研究显得尤为重要。在已有的代价敏感决策树算法中还存在很多不足,例如:用于属性结点选择的启发函数中参数值难以确定;已有算法在小数据集上表现不错,但在大数据集上效率明显降低;决策树模型由于没有使用恰当的剪枝策略导致出现过拟合现象,泛化能力较低。本文针对已有代价敏感决策算法的不足,提出以下优化方法:(1)本文针对已有代价敏感决策树算法中分类代价偏高以及存在多值属性偏颇问题,引用了 CS-C4.5算法的启发函数,并对其进行了优化,优化后启发函数的特点是当一个属性再次被测试的时候退化成了 C4.5算法;并引入自适应选择参数机制,构建了 ADP算法。实验证明,优化后的ADP算法在构建树的过程中能折中考虑模型自身的分类能力、测试代价和误分类代价三方面信息。(2)受“概率坚持剪枝”策略的启发,本文对它的对偶策略——“概率拒绝剪枝”策略进行了研究,该剪枝策略的思想为:根据剪枝规则确定决策树应该被剪枝时,算法仍然以一定的概率拒绝剪枝。对比实验证明,“概率拒绝剪枝”策略能够进一步减小模型的平均分类代价,以及解决决策树模型的过拟合问题,提高模型的泛化能力。(3)本文针对已有代价敏感决策树算法在高维性、不平衡性的数据集上效率较低的不足,在决策树的构建过程中引入了自适应选择切分点(Adaptive Selecting the Cut Point,ASCP)机制和自适应删除属性(Adaptive Removing the Attribute,ARA)机制。ASCP机制可以大大减小计算的复杂度,提高算法效率。ARA机制可以在建树过程中自适应的除去一些对决策树影响较小的属性,简化了属性选择的过程。对比实验证明,新机制的引入可以大大提高决策树的构建效率,在大数据集上表现更优。