这本书首先简要介绍了机器学习的主题，涵盖了大数据挖掘、数据流挖掘的基本方法，以及一个简单的MOA示例。接下来进行更详细的讨论，其中有关于草图技术、变更、分类、集成方法、回归、聚类和频繁模式挖掘的章节。这些章节中的大部分内容包括练习、基于MOA的实验，或者两者都有。*后，本书讨论了MOA软件，涵盖了MOA图形用户界面、命令行、其API的使用以及MOA中新方法的开发。对于那些想要使用数据流挖掘作为工具的读者、数据流挖掘的研究人员，以及想要为MOA创建新算法的程序员来说，这本书将是一个重要的参考。

本书分成三个部分。*部分简要地介绍大数据流挖掘，包含三章。前两章介绍大数据流及其基本挖掘方法。后一章是MOA上手指南，读者可以作为参考，自行探索MOA。第二部分详细地展现了数据流挖掘中的常见问题和重要算法。由于涉及的知识面广阔，本书优先讲解MOA中已涵盖的算法。该部分*章提到了sketch技巧，本书认为数据流挖掘领域人员很有必要对该技巧加以了解。大部分章节含有一套练习题或MOA上手教程，或两者兼具。第三部分全篇讲解MOA，从用户界面开始，到命令行和API，*后讲解如何实现新方法。

1）介绍大数据挖掘和实时分析中使用的算法和技术，并用热门的免费开源软件框架MOA进行了展示。

2）重点介绍数据流的挖掘和知识发现，强调适用于高速数据流的数据分析技巧。

3）理论与实践结合，含配套习题。

译 者 序
Machine Learning for Data Streams: with Practical Examples in MOA
机器学习和数据挖掘早已是计算机领域中的热门话题，这两个领域中的优秀作品也屡见不鲜。本书的独特之处在于从数据流的角度详细介绍了机器学习模型，同时结合数据流生成和分析的开源软件MOA，为数据流挖掘从业者和学者提供了易于上手实践的理论和工具。本书的每一章不仅分析了基础数学背景和传统机器学习的算法或模型，同时为了加深读者的横向理解，还专门为此对比了相关的数据流模型。除了引用最前沿的文献和广泛使用的模型，本书的可贵之处在于，呼吁业界多加考虑使用那些尚未普及却效果不错的新算法；对于新算法和常用算法，本书对模型进行了多方面的比较；正如前言中所说，本书面向有一定编程基础、机器学习基础或数据挖掘基础的读者。对于其他背景的读者，请参考前言中的阅读方法。
本书由陈瑶负责全书翻译内容审核，姚毓夏负责翻译本书大部分章节。
每一本书的背后都关联着大同小异的故事。翻译过程中，我们克服了跨国时差的合作挑战，且至今素未谋面。翻译开始之初，从联系出版社到最终交稿，经历了各种曲折，这也让我们更加坚定了初衷。在这里，我们想要号召愿意参与翻译工作但还在观望的译者，联系我们、加入我们，这里有计算机各个领域的专家和翻译小组。每一个贡献出自己个人时间的译者，除了能在翻译中学习所翻译书籍的内容之外，还可以找到自己想要深耕的领域，默默地在中国技术发展史上留下或深或浅的印记。
最后感谢北京华章图文信息有限公司的刘锋老师在翻译过程中给予的悉心帮助和指导！

译者
2019年9月

前　　言
Machine Learning for Data Streams: with Practical Examples in MOA

实时数据流分析正变得越来越常见，已经成为从现实中获取有用信息的标准手段。数据流分析可以让组织迅速应对问题并探测未来趋势，从而提升自身的运营效率。本书将充分展现数据流挖掘领域中常用的算法和技术，并且详细地介绍MOA软件：一个包含这些算法和技术的开源框架。
本书展示的数据流挖掘领域中的算法，面向以下3类特定的读者群体：
第一类读者希望在实际中应用数据流挖掘。他们有数据挖掘基础，但往往没有很强的算法或编程背景，比如管理、商务智能和市场营销领域的学生和教授。本书充分考虑了这些读者的需求，提供了MOA的上手教程，以任务为导向而不是以算法为导向。
第二类读者是那些在数据流挖掘领域的研究者和创新者。他们需要详细地了解算法和评估方法，才能更恰当地运用现有的算法，评估其性能，并把算法融入应用，甚至是创造新的算法。这群读者往往是计算机或数据科学专业的高年级本科生、研究生和博士，以及创新型开发者。
第三类读者想要在MOA中加入新的算法，从而对这个开源项目做出贡献。这些读者需要理解MOA的类结构和创建学习任务的方法。
为了充分满足这3类读者群体的需求，本书分成三个部分。第一部分简单地介绍大数据流挖掘，包含三章。前两章介绍大数据流及其基本挖掘方法。后一章是MOA上手指南，读者可以作为参考，自行探索MOA。
本书的第二部分更详细地展现了数据流挖掘中的常见问题和重要算法。由于涉及知识面广阔，本书优先讲解MOA中已涵盖的算法。第4章提到了sketch技术，本书认为数据流挖掘领域人员很有必要对该技术加以了解。大部分章节含有一套练习题或MOA上手教程，或两者兼具。
第三部分全篇讲解MOA，从用户界面开始，到命令行和API，最后讲解如何实现新方法。
综上所述，第一类读者应该阅读第一部分，有时间可以把第11章和第12章作为延伸阅读，以了解MOA的软件体系和其他可选参数。
第二类读者也应该阅读第一部分，然后至少应该阅读4.1节至4.3节（如果对sketch数据结构有兴趣，应该反复阅读第4章）、第5章和第6章。可以根据兴趣，自行选读第7章到第10章。如果需要在实际中运用MOA，还应该继续阅读第11章至第14章。
第三类读者在阅读以上部分的基础上，还应该阅读第15章。
本书的网站地址是https://mitpress.mit.edu/books/data-stream-mining，其中会持续更新书中的内容和一些辅助资源，包括讲稿、习题、软件上手教程和其他阅读材料。欢迎各位读者阅读参考并提出建议。
过去十年中，已经出现了好几本关于数据流挖掘的书。由Garofalakis、Gehrke和Rastogi编写的Data Stream ManagementProcessing Lligh-Speed Data Streams [118]，还有Aggarwal编写的Data StreamsModels and Algorithms [4]，这两本书涵盖的内容与本书部分相同，但是这些书往往从大数据库社区的角度出发，而不是数据流挖掘社区或者机器学习社区。
Gama编写的Knowledge Discovery from Data Streams [110]一书从数据流挖掘及机器学习社区的角度讲解算法，但是并没有提到MOA的开发和评估框架。该书展现了算法的伪代码，其中有些算法已经在MOA中实现了。因此，读者可以考虑在阅读本书的同时参考Gama的书。
为了跟上数据流挖掘领域日新月异的变化，我们极力推荐以下会议的论文和报告：KDD（数据库知识发现）、ICDM（国际数据挖掘会议）、SAC（应用计算研讨会）。这些会议都设有数据流挖掘的分会场。此外，还有ECML PKDD（机器学习及数据库知识发掘原理和实践欧洲会议）、SDM（数据挖掘SIAM会议），以及IEEE DSAA（电气电子工程师协会的数据科学和高级分析会议）。
在杂志方面，至今为止还没有一本数据流挖掘的专门杂志，而刊登过数据流挖掘文章的杂志又数不胜数，在此就不一一列举了。
致谢
我们向所有为这本书和相关软件做出了贡献的人员表示感谢。我们希望罗列所有贡献者的名字，但难免由于姓名不详（如审阅者）、名单过长（比如MOA共同作者、通过提问和指出bug而改进MOA的学生，及直接贡献代码的人）以及我们的疏忽，而难以列全，希望得到读者的谅解。在此，我们事先向未被本书提及的数据流挖掘作者致歉。由于篇幅限制和选择不够明智而没能提及你的作品，希望得到理解。
我们要感谢麻省理工学院出版社（MIT Press），特别要感谢Marie Lufkin Lee、Christine Bridget Savage和Kathleen Hensle的协助。
在此特别告知，本书的灵感来自于具有奠基意义的WEKA机器学习工具。
本书共同作者Ricard Gavaldà的撰写部分由加泰罗尼亚政府（Generalitat de Catalunya）的MACDA项目（SGR2014-0890）和西班牙政府经济竞争部门（MINECO）的APCOM项目（TIN2014-57226）提供部分赞助。

Albert Bifet是巴黎高等电信学院的计算机科学教授，数据、智能和图形组的负责人，他的研究兴趣主要集中在人工智能、大数据科学和数据流的机器学习方面。

Richard Gavaldà是加泰罗尼亚理工大学的计算机科学教授。

Geoffrey Holmes是怀卡托大学的计算机科学系主任和教授。

Bernhard Pfahringer是奥克兰大学的计算机科学教授。

译者序
前言
第一部分　概述
第1章　简介 2
1.1　大数据 2
1.1.1　工具：开源革命 4
1.1.2　大数据带来的挑战 4
1.2　实时分析 6
1.2.1　数据流 6
1.2.2　时间和内存 6
1.2.3　应用一览 6
1.3　关于本书 7
第2章　大数据流挖掘 8
2.1　算法 8
2.2　分类算法 9
2.2.1　如何在数据流中评估分类器 10
2.2.2　多数类分类器 11
2.2.3　无变化分类器 11
2.2.4　惰性分类器 11
2.2.5　朴素贝叶斯分类器 12
2.2.6　决策树分类器 12
2.2.7　集成分类器 13
2.3　回归算法 13
2.4　聚类算法 14
2.5　频繁模式挖掘 14
第3章　MOA的实际操作介绍 16
3.1　入门开始 16
3.2　分类模型的图形用户界面 18
3.3　用命令行操作 23
第二部分　数据流挖掘
第4章　数据流和Sketch数据结构 26
4.1　背景知识：近似算法 27
4.2　集中不等式 28
4.3　取样 30
4.4　统计总数 31
4.5　去重统计 32
4.5.1　线性计数 33
4.5.2　科恩对数计数器 33
4.5.3　Flajolet-Martin计数器和HyperLogLog算法 34
4.5.4　应用：图论的计算距离函数 36
4.5.5　讨论：对数与线性 37
4.6　频率问题 37
4.6.1　SpaceSaving sketch 38
4.6.2　CM-Sketch算法 40
4.6.3　CountSketch算法 42
4.6.4　时刻计算 44
4.7　滑动窗口的指数矩形图 45
4.8　分布式sketch计算的可合并性 47
4.9　一些技术方面的讨论和其他资料 48
4.9.1　哈希函数 48
4.9.2　创建(, )近似算法 49
4.9.3　其他sketch技术 49
4.10　练习 50
第5章　处理变化 52
5.1　数据流中变化的定义 52
5.2　评估器 56
5.2.1　滑动窗口和线性评估器 57
5.2.2　指数加权移动平均评估器 57
5.2.3　单维度卡尔曼滤波器 58
5.3　变化探测 58
5.3.1　评估变化探测 59
5.3.2　CUSUM测试和Page-Hinkley测试 59
5.3.3　统计测试 60
5.3.4　漂移探测法 61
5.3.5　自适应滑动窗口算法 62
5.4　与其他Sketch和多维数据结合 64
5.5　练习 64
第6章　分类 66
6.1　分类器评估 67
6.1.1　误差估算 68
6.1.2　分布评估 69
6.1.3　性能的评估测量 70
6.1.4　统计显著性 72
6.1.5　测量挖掘成本 73
6.2　基线分类器 73
6.2.1　多数类 73
6.2.2　无变化分类器 74
6.2.3　朴素贝叶斯 74
6.2.4　多项式朴素贝叶斯 77
6.3　决策树 78
6.3.1　估算切分标准 79
6.3.2　Hoeffding决策树 80
6.3.3　CVFDT 82
6.3.4　VFDTc和UFFT 83
6.3.5　Hoeffding适应树 84
6.4　处理数字属性 85
6.4.1　VFML 85
6.4.2　穷举二叉树 86
6.4.3　Greenwald和 Khanna的分位数摘要 86
6.4.4　高斯近似 87
6.5　感知器模型 88
6.6　惰性学习 89
6.7　多标签分类器 89
6.8　主动学习 91
6.8.1　随机策略 92
6.8.2　固定不确定策略 93
6.8.3　可变不确定策略 93
6.8.4　随机不确定策略 94
6.9　概念演变 94
6.10　MOA实战操作 95
第7章　集成方法 99
7.1　准确率加权集成 99
7.2　加权多数算法 100
7.3　堆叠算法 102
7.4　装袋算法 102
7.4.1　在线装袋算法 103
7.4.2　装袋算法如何应对数据流变化 103
7.4.3　杠杆装袋算法 103
7.5　提升算法 104
7.6　Hoeffding树集成算法 105
7.6.1　Hoeffding选项树算法 105
7.6.2　随机森林算法 105
7.6.3　有限的Hoeffding树的感知器堆叠 106
7.6.4　自适应大小的Hoeffding树算法 107
7.7　重复性概念 107
7.8　MOA实战操作 108
第8章　回归 110
8.1　什么是回归 110
8.2　如何评估回归 111
8.3　感知器学习 112
8.4　惰性学习 112
8.5　决策树学习 112
8.6　决策规则 113
8.7　MOA中的回归 114
第9章　聚类 115
9.1　聚类的评估方法 116
9.2　k-means算法 117
9.3　BIRCH、BICO和CluStream 118
9.4　基于密度的方法： DBSCAN和Den-Stream 120
9.5　ClusTree 121
9.6　StreamKM ：核心集 122
9.7　延伸阅读 123
9.8　MOA实战操作 124
第10章　频繁模式挖掘 127
10.1　什么是模式挖掘 127
10.1.1　模式的定义和例子 127
10.1.2　频繁模式挖掘的批量算法 129
10.1.3　闭合模式和最大模式 131
10.2　数据流中频繁模式挖掘的方法 131
10.3　如何在数据流中进行频繁项集挖掘 134
10.3.1　简化为高频繁项 134
10.3.2　Moment算法 135
10.3.3　频繁模式数据流算法 135
10.3.4　IncMine算法 136
10.4　数据流的频繁子图挖掘 137
10.4.1　WinGraphMiner框架 138
10.4.2　AdaGraphMiner框架 139
10.5　延伸阅读 140
10.6　练习 141
第三部分　MOA软件
第11章　MOA及其软件体系 144
11.1　MOA架构 145
11.2　安装 145
11.3　MOA的近期发展 145
11.4　MOA扩展包 146
11.5　ADAMS优化 147
11.6　MEKA优化 149
11.7　OpenML环境 150
11.8　StreamDM软件 150
11.9　Streams工具 151
11.10　Apache SAMOA 流媒体ML库 151
第12章　图形用户界面 154
12.1　初识图形用户界面 154
12.2　分类和回归 154
12.2.1　主要任务一览 156
12.2.2　数据源和数据生成器 157
12.2.3　贝叶斯分类器一览 160
12.2.4　决策树一览 160
12.2.5　元分类器（集成）一览 161
12.2.6　函数分类器一览 162
12.2.7　漂移分类器一览 162
12.2.8　主动学习分类器 163
12.3　聚类 163
12.3.1　数据源和数据生成器 163
12.3.2　数据流聚类算法一览 163
12.3.3　如何进行可视化和数据分析 164
第13章　用命令行操作 166
13.1　给分类和回归创建学习任务 166
13.2　给分类和回归创建评估任务 167
13.3　给分类和回归创建学习与评估任务 167
13.4　两种分类器的对比 168
第14章　调用API 170
14.1　MOA对象 170
14.2　选项 170
14.3　示例：先序评估 173
第15章　在MOA中开发新的方法 175
15.1　MOA中的主要类 175
15.2　创建新的分类器 176
15.3　编译分类器 183
15.4　MOA中的良好编程方法 183
参考文献 185