论文部分内容阅读
决策树算法是应用最广泛的归纳学习算法之一,是一种逼近离散值目标函数的方法,它自顶向下运用递归方式,构造一棵揭示数据内部关系的树,进而得出决策规则。单调分类是一种重要的分类任务,在这种任务中需要考虑条件属性和决策之间的单调性约束:当一个对象的所有条件属性上的取值都不比另一个对象差时,它的决策也不会比另一个对象的决策差。Hu等人提出基于有序信息熵的决策树算法REMT,该算法用于单调分类问题,只要训练数据是单调的,就能生成单调一致的决策树,即使数据中包含噪声,也能够获得较好的结果。为了得到精度和分类效率更高的分类器,本文在REMT算法的基础上,研究了基于决策树的单调分类算法,主要工作如下:(1)在决策树算法中引入了前向有序互信息和后向有序互信息,讨论了它们在不同噪声等级下的变化情况,提出用前向和后向有序互信息分别构造前向和后向有序决策树的决策树生成算法,并利用规则精度将两者集结构造了分类器。在人造数据集和真实数据集中分别进行了实验,实验证明该算法不但保证了单调分类问题上决策规则的单调一致性,还提高了分类器的分类精度,并通过适当放宽决策树的终止条件,减少了决策树的深度以及分类规则的长度,避免了决策树的过度拟合。(2)借鉴决策森林的思想,提出了基于决策森林的单调分类算法,算法中引入了重采样技术,对训练集进行重采样获得多个训练子集,从不同的角度构造决策森林中的每棵决策树,得到了既有一定的相似性,又能较大程度的覆盖原始训练集中数据对象的多棵决策树。在人造数据集和真实数据集中分别进行了实验,实验证明由于决策森林减小了训练子集的规模,因而缩短了分类器的分类规则,避免了过度拟合,也可以用于数据集稍大的情况。本文中构造多个有序决策树再集结的算法都能够在单调的训练样本上得到单调一致的决策树,相对于单棵有序决策树,本文算法不仅提高了分类精度,降低了平均绝对误差,还缩短了分类规则的长度,提高了分类效率,避免了过度拟合。