集成学习：基础与算法

集成学习方法是一类先进的机器学习方法，这类方法训练多个学习器并将它们结合起来解决一个问题，在实践中获得了巨大成功。

《集成学习：基础与算法》分为三部分。第一部分主要介绍集成学习的背景知识；第二部分主要介绍集成学习方法的核心知识，包括Boosting、Bagging、Random Forests 等经典算法，平均、投票和Stacking 等模型和方法、相关理论分析工作，以及多样性度量和增强方面的进展；第三部分介绍集成学习方法的进阶议题，包括集成修剪、聚类集成和集成学习方法在半监督学习、主动学习、代价敏感学习、类别不平衡学习及提升可理解性方面的进展。此外，本书还在每章的“拓展阅读”部分提供了相关的进阶内容。

周志华，教授、南京大学计算机系主任、人工智能学院院长、校学术委员会委员。

欧洲科学院外籍院士，首位在人工智能相关五大主流国际学会ACM、AAAI、AAAS、IEEE、IAPR均当选为会士的华人学者。

中国计算机学会、中国人工智能学会会士。

曾获IEEE计算机学会Edward J. McCluskey技术成就奖、CCF王选奖等。

李楠，博士，毕业于南京大学计算机系机器学习与数据挖掘研究所(LAMDA)，师从周志华教授从事机器学习研究。

发表论文20余篇，并获国际数据挖掘竞赛冠军及最佳论文奖。

先后供职于阿里巴巴iDST/达摩院和微软亚洲互联网工程院，主要从事机器学习在互联网搜索、推荐和广告中的研究和应用工作。

本书是目前国内独本系统性阐述集成学习的著作。

集成学习的思路是通过结合多个学习器来解决问题，它在实践中大获成功——人称“从业者应学应会的大杀器”之一。

化繁为简：将复杂的原理简化为易于理解的表达，通俗易懂；

结构合理：兼具广度与深度。既阐述该领域的重要话题，又详释了重要算法的实现并辅以伪代码，更易上手；

注重实践：阐述集成学习在多个领域的应用，如计算机视觉、医疗、信息安全和数据挖掘竞赛等；

拓展阅读：提供丰富的参考资料，读者可按图索骥、自行深入学习；

新手通过本书很容易理解并掌握集成学习的思路与精粹；

老手通过本书能学会不少技巧并深化对集成学习的理论理解，更好地指导研究和实践。

推荐序

最近十年，机器学习领域取得了长足的进步，尤其是深度学习，在语音、机器翻译和计算机视觉等人工智能应用中均获得巨大成功。这可能会令人觉得经典机器学习方法不再有效——对于现在众多对经典机器学习方法知之甚少的学生来说，情况是这样的。事实上，尽管确实有不少经典的机器学习方法不如深度学习方法有效，但是集成学习在深度学习领域中仍然发挥着巨大作用。目前，在深度学习方法之上引入集成学习仍然是许多深度学习专家用来提升效果的重要手段。

简而言之，集成学习从数据中显式或隐式地学习多个模型，并将它们有效结合以获得更可靠和更准确的预测。因此，集成学习的关键是（a）如何从数据中学习多样且准确的模型，以及（b）如何有效地结合它们以获得更好的结果。

集成学习与其他机器学习方法（如深度学习和核学习）的核心区别在于：它专注于偏差-方差权衡（Bias-Variance Tradeoff）问题——这是所有机器学习方法，无论是深度学习，还是经典机器学习方法——与生俱来的根本问题。正是这个独特的研究视角，使集成学习对包括深度学习在内的所有机器学习方法都很有价值。

在本书中，作者充分阐述了偏差-方差权衡问题的背景知识，足以使对统计学不太了解的读者也能很好地理解该问题。此外，作者在阐述集成学习的广度(集成学习的全貌) 和深度（单个算法的实现）上做了很好的平衡，结构合理，使得本书能真正惠及广大读者。

——金榕，阿里巴巴集团副总裁、达摩院副院长

中文版序

集成学习是机器学习的一个分支领域，研究如何通过构建并结合多个学习器来完成学习任务。该领域产生的技术已在人工智能实践中被广泛使用，如在许多应用任务中性能优异的随机森林、XGBoost 等。KDD Cup 历届冠军几乎都用到集成学习技术，Kaggle 竞赛高分榜上集成学习技术亦为常客。

笔者在集成学习领域修学多年，Chapman & Hall 出版社2008 年邀约出版专著。该社曾出版随机森林发明人Leo Breiman 的Classification and Regression Trees、自助采样发明人Bradley Efron 的An Introduction to the Bootstrap 等名著，于是笔者应邀于2012 年出版了Ensemble Methods: Foundations and Algorithms 一书。拙著问世后，不少朋友提议出中文版，然而笔者懵懂间中文版权已不在手，且彼时开始构思“西瓜书”，精力所限难以兼济，于是作罢。2017年偶见日本近代科学社之日文版，杂感交集。

欣闻电子工业出版社购得原著中文版权并邀得李楠博士担任译者。李楠青年才俊，师从于吾，主攻集成学习，勤于钻研、硕果累累；曾获首届百度奖学金、入选IBM 博士生英才计划等。2015 年博士毕业后就职于阿里iDST、达摩院，近期加入微软，繁忙工作之余拨冗译著，甚为不易。李楠博士曾兼任苏州大学数学科学学院计算数学系主任，经验丰富，佳译可待。

笔者学识粗陋，译本或因原著庸薄而致佶聱，敬请读者诸君不吝赐正。

—周志华

2020年5月

译者序

近年来，机器学习技术的快速发展推动了语音、自然语言处理、机器视觉等多个领域获得巨大进步，也带动了人工智能相关产业的蓬勃发展。回顾机器学习最近30 年的发展历程，各种学习方法“你方唱罢我登场”——从多层感知机到决策树，从支持向量机再到深度神经网络，推陈出新、不断演进。但是，在此历程中，通过构建并结合多个学习器来完成学习任务的集成学习方法，始终是提升学习效果的重要手段，成为机器学习领域的“常青树”，受到学术界和产业界的广泛关注。

译者是在南京大学读研期间开始接触集成学习的，当时在导师周志华教授指导下从事选择性集成和集成多样性方面的研究工作。回首来看，这段研究经历从两个方面对我影响颇深。第一，译者最初曾认为集成学习是一系列具有“三个臭皮匠顶个诸葛亮”朴素想法的启发式方法，缺乏理论基础，但后来对偏差-方差分解、Boosting 间隔理论、集成多样性等课题的学习和研究，使我彻底抛弃了这种想法；更重要的是，这段研究经历所积累的理论知识为我后来快速学习掌握其他机器学习方法提供了莫大的帮助，至今仍受益良多。第二，机器学习是面向实践的学科，集成学习在实践中的优异效果让人印象深刻。正是这段对集成学习的研究经历，使我掌握了多种构建高效集成的方法和技巧，为后来的实践夯实了基础。

译者2015 年博士毕业后进入产业界，先后在阿里巴巴iDST、达摩院和微软从事搜索、推荐、广告等领域的工作。在此过程中，译者亲身经历并见证了集成学习在产业界的巨大成功。例如，对搜索、推荐、广告的核心任务——点击率预估而言，GBDT（Gradient Boosting Decision Trees）因其稳定、优异的效果一直是事实上的工业标准；在语音识别领域，基于集成深度学习的声学模型极大提升了识别效果；在异常检测上，iForest 因其极高的检测效率在实践中备受关注。工作期间，多有同事问及集成学习方向的专业书籍，无奈当时国内并

无相关专著，而本书原著在国内很难买到，只能作罢。后来，欣闻电子工业出版社购得原著中文版权，并邀请我翻译，便欣然应允。

感谢导师周志华教授在我读硕读博期间给予的悉心指导：这段宝贵的学习经历不仅极大地开阔了我的视野，也为我此后的研究和实践工作奠定了基础。如果没有这些积累，我将难以完成翻译。同时，感谢东南大学张敏灵教授、南京航空航天大学黄圣君教授通读此译本并提出很有见地的建议和意见；感谢胡鹏、梁晨、吴西竹、杨子旭、赵鹏、周宇航等同学提供帮助和建设性意见；感谢家人付克红女士、李佳智、李佳慧的支持和鼓励。电子工业出版社刘皎编辑及同事为本书的翻译出版做了大量工作，在此深表谢意。

受译者水平和能力所限，译文的表述可能不如原著流畅，原著思想的一些精微之处可能未能精确传达，恳请读者批评指正。

——李楠

2020年6月于苏州

前 言

集成学习方法是一类先进的机器学习方法，这类方法会训练多个学习器并将它们结合起来解决一个问题，其中的典型代表是Bagging 和Boosting。通常，一个结合了多个学习器的集成会比单个学习器更加精确，集成学习方法在很多的实际任务中获得了巨大成功。由于使用多个模型解决问题的基本想法在人类社会中有着悠久的历史，我们难以对集成学习方法的历史进行溯源。但是，很明显，自从20 世纪90 年代以来，集成学习方法就成为一个热门的研究课题，吸引了来自机器学习、模式识别、数据挖掘、神经网络和统计等领域的众多研究人员。

本书面向研究人员、学生和实践者介绍集成学习方法。全书共8章，分为三部分。

第一部分即第1 章。虽然本书的主要受众是具有一定机器学习和模式识别基础知识的读者，但是为了使对相关内容不了解的读者也能够读懂本书的主要内容，我们在第1 章介绍了集成学习的背景知识。由于不可能在一章内穷尽所有背景知识，本章主要作为对进一步了解相关内容的指引。另外，为了避免混淆相关领域术语，本章还约定了本书使用的相关术语。

第二部分由第2 到5 章构成，介绍集成学习方法的核心知识。第2章和第3章分别介绍了Boosting 和Bagging。由于经典的Boosting 是针对二分类问题设计的，且对噪声比较敏感，因此第2 章除介绍Boosting 的相关算法和理论外，还介绍了其多类扩展和容噪扩展。由于Bagging 天然支持多分类场景且对噪声具有一定的鲁棒性，第3 章就没有再介绍相关内容，而是介绍了随机森林（Random Forests）和其他的随机决策树集成方法，这类方法都可以看成Bagging的变种。第4章介绍了结合方法，除各种平均和投票方法外，本章还介绍了Stacking 方法及一些相关方法，如混合专家模型等。第5 章专门介绍了集成多样性。在介绍“误差-分歧分解”和“偏差-方差-协方差分解”后，本章介绍了多样性度量指标，并且阐述了近年在信息论多样性和多样性增强方法方面的进展。第三部分由第6到8章构成，介绍集成学习方法的进阶议题。第6章介绍集成修剪，即如何通过缩减一个训练好的集成以达到更好的效果。第7 章介绍聚类集成，即如何通过结合多个聚类结果获取更好的聚类。第8 章介绍集成学

习方法在半监督学习、主动学习、代价敏感学习、类别不平衡学习，以及提升可理解性方面的一些进展。

本书的目的不是覆盖集成学习方法的所有知识。有兴趣的读者可以从每章的“拓展阅读”部分获取进一步的信息。

在本书之前，已有两本集成学习方面的专著[Kuncheva，2004；Rokach，2010]。为了反映本领域的快速发展，本人曾尝试做一个更新的深入回顾。但在成书过程中发现，这是一项比预想要困难得多的任务。尽管在集成学习方法方面有大量研究工作，但业界对一些核心要素还缺乏深入理解，对相关技术的实验研究也并不充分。因此，书中的有些章节仅介绍了一些相关算法，甚至在一些讨论理论问题的章节中，还存在一些重要但不清楚的问题。一方面，这种情

况反映了集成学习领域还在快速发展中；另一方面，也为进一步研究提供了好的机遇。

本书如果没有大家的帮助则难以成稿。在此，衷心感谢Tom Dietterich 教授通读此书并且给出了非常有见地的建议和意见；感谢陈松灿、李楠、刘胥影、Fabio Roli、吴建鑫、俞扬和张敏灵提供有建设性的意见。同时，感谢RandiCohen 女士和Chapman & Hall/CRC 出版社的同事所提供的协助。

最后，感谢我的家人、朋友和学生的耐心、支持和鼓励！

——周志华

中国，南京

第1章 绪 论 1

1.1 基本概念 1

1.2 常用学习算法 3

1.2.1 线性判别分析 3

1.2.2 决策树 4

1.2.3 神经网络 6

1.2.4 朴素贝叶斯 8

1.2.5 k-近邻 9

1.2.6 支持向量机和核方法 9

1.3 评估和对比 12

1.4 集成学习方法 14

1.5 集成学习方法的应用 16

1.6 拓展阅读 19

第2章 Boosting 21

2.1 Boosting 过程 21

2.2 AdaBoost 算法 22

2.3 说明性举例 26

2.4 理论探讨 29

2.4.1 基本分析 29

2.4.2 间隔解释 30

2.4.3 统计视角 32

2.5 多分类问题 35

2.6 容噪能力 37

2.7 拓展阅读 40

第3章 Bagging 43

3.1 两种集成范式 43

3.2 Bagging 算法 44

3.3 说明性举例 45

3.4 理论探讨 48

3.5 随机树集成 52

3.5.1 随机森林 52

3.5.2 随机化谱 55

3.5.3 随机森林用于密度估计 56

3.5.4 随机森林用于异常检测 58

3.6 拓展阅读 60

第4章 结合方法 61

4.1 结合带来的益处 61

4.2 均值法 62

4.2.1 简单平均法 62

4.2.2 加权平均法 63

4.3 投票法 65

4.3.1 绝对多数投票法 65

4.3.2 相对多数投票法 66

4.3.3 加权投票法 67

4.3.4 软投票法 68

4.3.5 理论探讨 70

4.4 学习结合法 76

4.4.1 Stacking 76

4.4.2 无限集成 78

4.5 其他结合方法 79

4.5.1 代数法 80

4.5.2 行为知识空间法 81

4.5.3 决策模板法 81

4.6 相关方法 82

4.6.1 纠错输出编码法 82

4.6.2 动态分类器选择法 85

4.6.3 混合专家模型 86

4.7 拓展阅读 87

第5章 多样性 91

5.1 集成多样性 91

5.2 误差分解 92

5.2.1 误差-分歧分解 92

5.2.2 偏差-方差-协方差分解 94

5.3 多样性度量 96

5.3.1 成对度量 96

5.3.2 非成对度量 97

5.3.3 小结和可视化 100

5.3.4 多样性度量的局限 101

5.4 信息论多样性 102

5.4.1 信息论和集成 102

5.4.2 交互信息多样性 103

5.4.3 多信息多样性 104

5.4.4 估计方法 105

5.5 多样性增强 106

5.6 拓展阅读 108

第6章 集成修剪 109

6.1 何谓集成修剪 109

6.2 多比全好 110

6.3 修剪方法分类 113

6.4 基于排序的修剪 114

6.5 基于聚类的修剪 117

6.6 基于优化的修剪 117

6.6.1 启发式优化修剪 118

6.6.2 数学规划修剪 118

6.6.3 概率修剪 121

6.7 拓展阅读 122

第7章 聚类集成 125

7.1 聚类 125

7.1.1 聚类方法 125

7.1.2 聚类评估 127

7.1.3 为什么要做聚类集成 129

7.2 聚类集成方法分类 130

7.3 基于相似度的方法 132

7.4 基于图的方法 133

7.5 基于重标记的方法 136

7.6 基于变换的方法 140

7.7 拓展阅读 143

第8章 进阶议题 145

8.1 半监督学习 145

8.1.1 未标记数据的效用 145

8.1.2 半监督学习的集成学习方法 146

8.2 主动学习 151

8.2.1 人为介入的效用 151

8.2.2 基于集成的主动学习 152

8.3 代价敏感学习 153

8.3.1 不均等代价下的学习 153

8.3.2 代价敏感学习的集成方法 154

8.4 类别不平衡学习 158

8.4.1 类别不平衡 158

8.4.2 类别不平衡学习的性能评估 160

8.4.3 类别不平衡学习的集成方法 163

8.5 提升可解释性 166

8.5.1 集成约简 166

8.5.2 规则抽取 167

8.5.3 可视化 168

8.6 未来的研究方向 169

8.7 拓展阅读 171

参考文献 173

索引 203