论文部分内容阅读
组合分类器学习是机器学习、模式识别和数据挖掘中非常活跃的研究领域。已有的研究表明，给定相同的训练信息，组合分类器往往表现出比单个分类器更好的泛化能力。然而，大部分组合分类器学习方法都存在共同的问题:倾向于构建大量基分类器模型。大量基分类器不仅需要大量存储空间而且增加了组合分类器预测响应时间。另外，在组合分类器中，某些基分类器不仅无助于提高组合分类器的泛化能力，而且还可能降低组合分类器的分类准确率。组合分类器剪枝是处理该问题的一种有效方法，受到了广泛关注。
组合分类器剪枝有两种方法:一种方法是从给定的基分类器中选择一个最优或次最优的子集，构建组合分类器;另一种方法是从组合分类器整体考虑，直接对每个基分类器剪枝。关于基分类器的选择，已经提出了一些算法，但仍然需要进一步研究，而第二种方法则很少有人涉及。由于两种方法都面临搜索指数级空间问题，因此穷举搜索是计算不可行的。解决这些问题的关键是(1)构建好的度量指标，评估基分类器选择和基分类器剪枝，指导搜索过程;(2)寻找合适的选择和剪枝方法。本文针对以上问题，研究组合分类器的剪枝，并进一步把剪枝的思想融入基于决策树的组合分类器的构建中，直接构建更有效的组合分类器。本文主要贡献和创新点如下:
1)提出了基于边界的组合分类器剪枝方法。根据边界理论，构造了一种基于边界的度量指标(MBM，Margin-basedMeasure)用于评估基分类器相对于组合分类器的重要性。根据MBM，设计了一种基于边界的贪心组合分类器剪枝算法(MBMEP，MBM-basedEnsemblePruning)，以降低组合分类器规模并提高它的分类准确率。实验结果表明:即使直接使用训练实例集作为剪枝集，MBMEP也能显著地降低组合分类器的规模并提高它的分类准确率;与已有的组合分类器剪枝方法相比，MBMEP在大部分数据集上都具有更好的泛化性能。
2)提出了基于置换策略的组合分类器剪枝方法(EPR，EnsemblePruningviabase-classifierReplacement)。与传统组合分类器剪枝方法不同，EPR初始化子组合分类器S为预定义大小，然后迭代地通过用较好的基分类器置换S中最差的基分类器，直到置换不能进行。为了确定是否应该进行置换，本文提出一种基于差异性的度量指标，用于度量基分类器对组合分类器的贡献。实验结果表明，EPR能够有效地降低组合分类器规模并提高它的泛化能力。
3)提出了一种基于贡献增益的森林剪枝方法FTCG(ForestTrimmingbasedonContributionGain)。基于决策树的组合分类器可以被视为一个森林。与对每棵决策树分别进行剪枝的传统剪枝方法不同，森林剪枝把所有的决策树看作一个整体，更加关注剪掉决策树的分枝对组合分类器性能的影响。为了确定森林的哪些分枝可以被剪枝，本文提出一种称作贡献增益的度量，评估剪掉决策树的一棵子树对组合分类器性能的影响。实验结果表明，无论森林是基于某种森林学习方法构建的还是某种传统组合分类器剪枝算法的结果，无论每棵决策树是剪枝过的还是未剪枝的，FTCG都能进一步降低每棵决策树的规模，并且在大部分数据集上显著地提高了的森林的分类准确率。
4)提出了一种新的基于决策树的组合分类器学习方法FL(Forest Learning)。与bagging和adaboost等传统的组合分类器学习算法不同，FL不采用抽样或加权抽样，而是直接在训练集上学习一个森林，作为组合分类器。首先，使用传统的方法构建森林的第一棵;然后，逐一构建新的决策树添加到森林中。在构建新的决策树时，结点的每次划分都考虑对组合分类器的影响。实验结果表明，与传统的组合分类器学习方法相比，FL在大部分数据集上都能构建出性能更好组合分类器。