数据库知识发现是(Knowledge Discovery in Databases,简称KDD)是当前涉及人工智能和数据库等学科的一门相当活跃的研究领域,分类是其中的一个重要研究方向。决策树是分类中常用的模型之一,自1966年被提出以来已经得到了广泛的研究和应用。然而,由于种类偏见,过拟合等问题,使决策树优化成为研究人员关注的热点。本文基于针对可疑实例分析以及结点纯度差变化趋势两个方面分别对决策树构造算法中的过拟合问题处理展开研究,主要工作如下:1.综述并分析了现有决策树经典算法及主要优化算法。2.提出了基于可疑实例影响度分析的改进的C4.5rules算法,将可疑实例进行有效划分,并计算其全局影响度大小,使得分类规则能有效避开可疑实例而更加正确的反应数据的真实情况。3.针对传统决策树过拟合现象普遍且大多数预剪枝算法严重依赖领域知识的问题,提出基于结点纯度差(PDN,Purity Distance of Node)变化趋势的决策树优化算法,通过跟踪相邻父子结点间的最大纯度差变化趋势,判定停止建树的时机,可以独立于领域知识实现有效的预剪枝并很好地控制了过拟合的发生,同时大大减小了决策树规模。4.基于上述研究,实现了原型系统,从理论和实验上证明了所提出的算法的正确性和有效性。