决策树误差降低剪枝算法的改进研究

• 作 者: 路逸行
• 出 处: 山东大学
• 发表日期: 2020年12期
• 关键词: 决策树 剪枝 误差降低 卡方统计量 多重检验 过拟合 泛化性能

决策树是数据挖掘中常用的分类和回归方法之一。本文主要讨论分类决策树。顾名思义,决策树为树状结构,从根结点开始逐渐开枝散叶,长成一棵具有多个分支和结点的大树。决策树遵循的是“分而治之”的策略,在分类问题中,每次划分选择一个特征变量将样本的集合分为若干部分,然后再对各部分进行相同的操作,直到特征变量全部选取完毕,每个样本都落入某个叶子结点中,这个叶子结点的类别由多数原则来决定。决策树具有计算复杂度不高、输出结果易于理解、对中间值的缺失不敏感、可以处理不相关特征数据等优点,因此在分类问题中应用较为广泛。一般来说,决策树的训练过程包括特征选择、树的生长、剪枝三个步骤。其中根据特征选择的不同标准,决策树可分为ID3、C4.5、CART三类,在实践中这三种标准生成的树的性能差异较小,几乎可以忽略不计。由于实际问题中变量的个数较多,由这些数据得到的决策树往往会变得大而复杂。然而,经验表明,大而复杂的决策树不仅解释起来较为困难,而且往往并不意味着可以得到更准确的分类结果,这说明决策树的生长具有过拟合的倾向。因此对决策树进行剪枝是很有必要的。剪枝可以简化决策树,提高泛化性能,避免对训练集的过拟合,是决策树学习中的重要研究内容。研究[1]表明,在数据中含有噪声时,剪枝甚至可以将决策树的泛化性能提升25%。目前常用的剪枝算法有误差降低剪枝(REP)、代价复杂度剪枝(CCP)、悲观误差剪枝(PEP)、最小误差剪枝(MEP)等。本文的创新点是针对误差降低剪枝(REP)算法提出了改进方案,在REP算法原有步骤的基础上增加了计算卡方统计量和多重检验修正的步骤,并在模拟数据和实际数据集上与现有的常见剪枝算法进行了比较。结果表明,改进后的REP剪枝算法相比于原算法能较好的提升决策树的泛化性能,同时改进算法没有明显的增加时间和空间复杂度,具有一定的可操作性和实践价值。