论文部分内容阅读
分类问题是模式识别、机器学习、图像处理以及信息检索等数据挖掘领域中一类重要的研究课题。在大量的分类模型中,决策树（Decision Trees,DTs）模型是最受欢迎且应用最为广泛的经典算法之一,其具有易理解、参数少及分类精度高等优点,并已在商业、医疗、工业制造、金融分析、生物信息以及图像处理方面获得广泛的应用并取得了显著的成效。针对连续型数据集,传统的处理方式要么采用标准的分割标准或其衍生方法,要么先对数据进行离散化后再采用标准的分割函数来训练决策树,这样构建的决策树不是分类效果不佳,就是构建的决策树规模较大。对上述问题,本文对决策树算法进行了深入地分析,开展了以下几个方面的研究:1.传统决策树算法在多类分类问题中存在分类性能较弱且构建的决策树规模较复杂等问题,本文提出一种将决策树与一对多（one-vs-all,OVA）分解策略相结合的混合机制。该混合机制以决策树作为基分类器并通过OVA策略将多类分类问题分解为多个二分类问题,针对训练集被OVA策略分解后产生的类非均衡问题以及分割点竞争问题提出一种分割点纠正矩阵（Splitting Point Correction Matrix,SPCM）的分割标准。在每个内部结点上,该分割标准能够从多个视角评估所有分割点并从中选择最优的分割点。首先,计算内部结点中的每一个分割点的海林格距离、基于分割点的分段值和分割率;然后,把该结点内所有分割点的海林格距离、分段值和分割率组成矩阵并依据海林格距离按降序排列,将前K个分割点作为候选分割点并对矩阵截短;最后,在截短的矩阵中,将分段值最小且分割率最大的候选分割点作为该内部节点的最优分割点。实验结果表明,与其它经典的决策树算法及最新的OVA混合机制相比,本文提出的方法在分类性能上有较大地提升,同时构建的决策树规模更小。2.针对传统的决策树算法在选择内部结点的最优分割点的过程中,当面临具有多个与最优分割点相近或相等的评估值时无法确定哪个分割点才是最优分割点情况,本文将内部结点中训练样本的频率信息和排列信息相结合提出一种称为SPES（Splitting Performance and the number of Expected Segments）的混合模型。该混合模型在每一个内部节点上选择最优分割点的机制为:首先,使用C4.5算法计算每一个分割点的信息增益率并将前K个最大值对应的分割点作为候选分割点;其次,计算K个候选分割点的期望分段值;最后,使用权衡因子将两者结合在一起并把评估值最大的分割点作为最优分割点。实验结果表明,与其它经典的决策树算法及最新的分割点竞争算法相比,本文提出的混合模型在分类性能方面有明显的改善。3.决策树算法中分割标准的设计通常与数据集中的类分布有关,但在类均衡的数据集上构建决策树时,往往会忽略过程中子结点的局部类非均衡问题。针对这一问题,详细分析其特征,本文提出了一种基于多分割标准的自适应决策树算法（Adaptive Decision Tree Algorithm,AdaDT）。在内部结点中,AdaDT算法将其局部类非均衡率作为两个分割标准之间的权衡因子,因此其能够自适应地选择合适的分割标准及最优分割点。实验结果表明,与其它分割函数相比,本文提出的自适应算法不仅能够有效地提高决策树的分类性能;而且还能够提高不同类别的样本的分类准确率。上述三种不同的分割标准的提出各有其特点,但它们之间有着内在的联系。基于SPCM的决策树算法不仅能够处理类非均衡问题而且能够有效解决分割点竞争问题;SPES算法提出了一般化的分割点竞争问题解决方案;最后,AdaDT算法针对传统决策树算法（包括上述两种算法）在构建决策树过程中存在的局部类非均衡问题提出了普适性的方法。本文的工作进一步地拓展了对决策树算法的研究,为其在应用领域提供了重要的支撑。本文的创新点如下:1.针对多类分类问题,将决策树与一对多机制相结合并提出了一种基于分割点纠正矩阵（SPCM）的决策树算法。与传统方法集中在测试样本输出的聚合策略不同,本文主要集中在构建泛化性能更好的基分类器。通过对比实验表明:基于本文提出的方法构建的一对多系统与当前最好的一对多系统相比,在多个数据集上的分类准确率至少高出10个百分点;而且构建的决策树规模更小。2.针对分割点竞争问题,基于结点中训练数据的频率信息与排列信息提出一种混合模型的决策树算法（SPES）并在混合模型的基础上设计了两种不同的分割标准。对比实验结果表明:从整体上看,与当前最优的处理分割点竞争的方法相比,本文提出的两种分割标准构建的决策树在分类精度上有明显的提高,最大超过5个百分点。3.针对决策树构建过程中存在的局部类非均衡问题,提出一种基于多分割标准的自适应决策树算法（AdaDT）。该算法基于多个不同分割标准并将内部结点中的局部类非均衡率作为调节因子来权衡多个不同分割标准,然后根据结点中的数据特征自适应的选择合适的分割标准及最优分割点。对比实验结果表明:与当前最好的方法相比,基于自适应的决策树算法构建的决策树不仅在分类性能上有明显提升而且能显著改善不同类别的样本的分类正确率。具体地,AdaDT算法与其基分割标准相比,在整体上看分别提升4和5个百分点;与其它基于多分割标准算法相比,提升了 2～3个百分点。