面向情报大数据的决策树增量学习算法研究

由于具有易于理解的优势,决策树成为最流行的分类方法之一。然而,利用已经存在的方法构建的决策树一般都会过于庞大、复杂化,因此在实际应用中实用性受到限制。此外,当今社会数据通常都是不断增加的,如果使用传统的决策树算法,即新增一批样本之后,将历史数据和新增数据再放在一起重新学习一遍,这种方式会把以前的知识遗忘掉,使得之前学习到的决策树没有任何意义。因此,这时候增量学习就变得尤为重要,即利用新增样本对以前学习到的决策树进行更新调整。在深入研究决策树方法和增量学习方法的基础上,本文提出一个新的决策树算法NOLCDT。在分裂结点之前,NOLCDT算法把结点中每个候选属性的多个属性值分别合并成两组,选择信息增益最大的候选属性将结点分为两个分支,这种方式可以避免生成太多的分支,进而防止决策树过于庞大。NOLCDT算法在选择下一个将要分裂的结点方面也有所改进,该算法为所有候选分裂结点计算对应的结点分裂度量值,并且总是选择结点分裂度量值最大的候选结点作为下一个分裂结点,使得每次分裂都有最大的信息增益。此外,本文在决策树增量学习算法ID5R的基础上,提出一种改进算法IID5R,IID5R增加了评估分类属性质量的功能,且推导出分类属性被候选属性替代的最小样本数的计算公式。将NOLCDT与IID5R相结合,提出了一个混合分类器算法HCS,HCS算法主要有两个阶段组成:构建初始决策树和增量学习。根据NOLCDT建立初始决策树,然后使用IID5R进行增量学习。HCS算法综合了决策树以及增量学习方法的优点,既便于理解又适于增量学习。选用UCI数据库中的数据集作为实验的数据来源,将传统的决策树算法与本文提出的混合分类器算法进行实验对比,结果表明HCS可以很好的解决增量问题,构建的决策树更简单便于理解,增量阶段消耗的时间减少。