经典集成学习算法的有效性解释及算法改进研究

摘要

如何有效地对未知类别的新样例进行分类是数据挖掘领域中一项非常重要的研究课题。集成学习作为解决这一问题的一种强有力的技术自提出以来受到了广泛的关注和研究，并在实际应用中取得了极大的成功。集成学习已发展成数据挖掘领域中的一个重要研究分支。目前学者们已经提出了一些经典的集成学习算法，如Bagging、AdaBoost、DECORATE等，并取得了一些重要的研究成果。然而，对于这些集成学习算法的有效性，还不存在一种对其进行充分解释的较为通用的理论工具；此外，在特定训练环境下某些集成学习算法的性能还不够理想。本文致力于解决这些问题，具体的，可将本文的主要贡献总结如下。
　　（1）由于不同的集成学习算法是学者们从不同角度提出的，自然的它们具有不同的工作机理。因此，若能从理论上对现有的经典集成学习算法的有效性进行分析，可使人们对这些算法产生更深刻的理解，更重要的是有助于发现一种能对集成学习算法有效性进行解释的较为通用的理论工具，从而为设计新的有效集成学习算法提供一定的理论指导。受margin理论所启发，本文尝试使用该理论对Bagging、AdaBoost和 DECORATE这三种最有代表性的经典集成学习算法的有效性进行实证分析和比较。实验结果表明，对于探讨的每种集成学习算法，它在训练集上生成的margin分布越好，则其取得的测试精度就越高。也就是说，margin理论能够很好地解释这些算法的有效性。因此可得出结论：margin理论是对集成学习算法的有效性进行解释的一种较为通用的理论工具。基于这一发现，本文建议将margin分布作为设计新的集成学习算法时的优化目标。
　　（2）为了得到理想的泛化性能，集成学习算法通常生成大量的基分类器来构成集成系统。然而在得到的集成系统中，可能存在一些精度较低或者相似的分类器，这不仅会增加集成系统的存储和计算开销而且会降低它的分类效率和泛化性能。为解决这一问题，本文提出了一种基于平均margin排序的基分类器选择方法，以便从初始集成系统中选择一个近似最优的分类器子集。该方法使用平均margin作为性能评价度量来对初始集成中个体分类器的性能进行评估。另外，本文还将平均margin与accuracy和diversity这两种常用的性能评价度量进行了全面比较。实验结果表明，本文的基分类器选择方法能有效地提高初始集成系统的分类效率和泛化性能，并且平均margin是一种比accuracy和diversity更好的性能评价度量。这对改善数据挖掘中分类任务的性能具有重要的理论和实践意义。
　　（3）在一些多分类问题中，训练集有时会包含很多类标签被错误标记的噪声样例。集成学习算法AdaBoost对这些误标记噪声样例非常敏感并且容易产生过度拟合，从而对误标记噪声样例不具有鲁棒性。针对这一问题，本文提出了一种鲁棒的误标记噪声数据多分类方法Rob_MulAda。在 Rob_MulAda中，形式地设计了一种基于噪声检测的多分类损失函数，并通过证明一个命题求解了其最小化问题；另外，给出了一种新的权值更新方式来克服误标记噪声样例的影响。在不同的噪声水平下将Rob_MulAda与其它几种相关方法进行了详细的实验比较，实验结果表明Rob_MulAda能够很好地改善AdaBoost在多分类问题中对误标记噪声样例的鲁棒性。
　　（4）很多实际应用中收集的训练集往往具有不平衡的类分布。由于大多数基分类器学习算法被提出时都基于这一假设：训练集应该具有大体平衡的类分布，因此它们在类不平衡训练集上生成的分类器通常具有较差的泛化性能，尤其是对少数类样例不能有效地进行分类。鉴于集成学习在提高个体分类器性能方面的优势，本文尝试利用集成学习来提高分类器在类不平衡训练环境下的泛化性能，提出了一种基于进化欠抽样的Bagging集成方法EUS-Bag。在EUS-Bag中，为了使进化欠抽样EUS更加适合Bagging框架、以生成一些具有良好性能且多样化的个体分类器，本文设计了一种考虑了三个因素的新适应度函数，从而更好地将EUS和Bagging的优势进行结合。在类不平衡数据集上进行的比较实验表明，EUS-Bag能够有效地提高分类器对类不平衡数据的分类性能。

目录

声明

第一章 绪论

1.1 引言

1.2 学习任务的种类

1.3 分类任务中的研究主题

1.4 集成学习

1.5 集成学习中存在的几个重要问题

1.6 本文主要贡献及内容安排

第二章 经典集成学习算法的margin理论实证解释

2.1 引言

2.2 相关工作

2.3 margin理论

2.4 集成学习算法的margin理论实证解释

2.5 本章小结

第三章 一种基于平均margin排序的基分类器选择方法

3.1 引言

3.2 相关工作

3.3 相关的定义

3.4 基于平均margin排序的集成剪枝算法

3.5 实验研究

3.6 本章小结

第四章 一种鲁棒的误标记噪声数据多分类方法

4.1 引言

4.2 相关工作

4.3 ND_AdaBoost和SAMME

4.4 一种鲁棒的多分类AdaBoost算法Rob_MulAda

4.5 实验研究

4.6 本章小结

第五章 基于进化欠抽样Bagging集成的不平衡数据分类方法

5.1 引言

5.2 相关工作

5.3 不平衡数据分类问题中的性能评价度量

5.4 基于Bagging的集成方法回顾

5.5 基于进化欠抽样的Bagging集成算法EUS-Bag

5.6 实验研究

5.7 本章小结

第六章 总结与展望

6.1 全文工作总结

6.2 下一步的研究工作

参考文献

致谢

在学期间的研究成果及发表的学术论文