论文部分内容阅读
数据挖掘是一门可以应用于多研究领域的交叉学科,分类分析法因其在信息化产业界中的广泛应用逐渐变成了数据挖掘中的研究热点。常用的分类算法包括决策树分类算法、贝叶斯分类算法、神经网络算法、支持向量机算法、k-最近邻分类算法等等。而决策树分类法以其速度快、精确度高、直观易懂等优点深得研究者们的喜爱,在数据挖掘领域里得到了深入的研究与应用。决策树分类算法的主要特征在四个方面：一是扩展属性选择标准,二是停止建树的准则,三是叶子结点的类标号判断准则,四是剪枝优化策略。目前,对决策树分类算法的研究主要致力于两个方面：扩展属性选择标准和剪枝优化策略。本文也是重点在这两个方面展开研究。修剪决策树的两个简单理由：一是训练数据集中存在噪声,使得生成的决策树对训练样例产生过拟合现象,从而造成对新的实际数据分类效果不理想。二是训练数据样例分布具有特殊性,造成构建出来的决策树分类器难以代表现实世界中的一般规律。本文对预剪枝和后剪枝算法做了系统阐述,并对常见的几种后剪枝算法做了分析比较。代价敏感分类学习问题的出现将对决策树分类算法的研究推到了一个崭新的高度。然而,其研究方向大都致力于对扩展属性选择标准的改进,将代价敏感学习与剪枝优化算法结合的研究还不多见。同时,代价敏感学习是以最小化代价为目标,忽略了决策过程中可能产生的收益。例如,在投资领域中,激进的投资者往往会牺牲一部分代价来换取最大的收益。针对上述代价与收益并存的应用环境,本文提出一种单位代价收益敏感决策树分类算法。其能实现在同等代价条件下最大化收益的决策目标。在此基础上,进一步提出了两种基于单位代价收益的决策树后剪枝算法,并通过实验证明所提算法的可行性和实用性。本文的主要研究工作如下：(1)基于代价与收益并存的应用环境,提出一种单位代价收益敏感决策树分类算法。为弥补代价敏感学习中忽略了正确分类可能会带来收益的不足,本文采用调和函数权衡属性信息增益与性价比重新构造了新型的扩展属性选择标准ASF。并采用“单位代价收益最大化”原则代替传统的“多数类”原则,作为叶子结点的类标号判断准则。为对该算法的实用性和有效性进行评估,通过三部分实验进行分析比较。第一部分实验将本文所提算法UCGS与C4.5以及一种代价敏感算法CS C4.5进行比较分析。结果表明在相同代价下,通过UCGS算法构建的决策树所获得的单位代价收益最大,且具有较高的分类正确率和良好的稳定性。第二部分实验表明其对于非均衡问题,也表现出了良好的分类效果,具备一定的应用价值。第三部分实验表明该算法在与其他三种代价敏感算法的比较中也表现出了良好的效果。综合来看,该算法能够在保证决策树分类正确率的前提下实现以最小代价获得最高收益的决策目标,能够很好的解决代价与收益并存的应用环境下的实际问题。(2)提出一种与预剪枝策略相结合的单位代价收益决策树剪枝算法。此算法采用单位代价收益剪枝策略与预剪枝策略相结合的方式对生成的决策树进行剪枝,使其具有代价敏感的性质。实验结果表明本文所提算法与REP、EBP两种剪枝算法相比,在绝大多数数据集上其决策树规模要小于REP和EBP算法所生成的决策树,在具有多种类别的数据集上表现尤为良好。且此算法拥有良好的分类正确率,能够提高决策树的预测准确度。此外,通过代价收益矩阵的设置,用户可以根据自己的需求调整分类决策树,从而改变了依赖固有算法的缺点,在灵活性上有一定的改善。(3)提出一种基于代价复杂度的单位代价收益敏感决策树剪枝算法(以下简称UCG-CCP)。此算法采用单位代价收益剪枝策略与代价复杂度相结合的方式,设置剪枝因子β,选择具有最小β(T)值的一棵子树作为最终剪枝后的最优决策树。实验结果表明,UCG-CCP剪枝算法所获得的决策树与CCP剪枝算法所获得的决策树相比,其在能够保证分类正确率的前提下,使复杂度进一步降低,所得分类模型更加简洁、清晰。