数据挖掘：实用机器学习工具与技术（原书第3版）

weka系统的主要开发者将丰富的研发、商业应用和教学实践的经验和技术融会贯通。

广泛覆盖在数据挖掘实践中采用的算法和机器学习技术，着眼于解决实际问题

避免过分要求理论基础和数学知识，重点在于告诉读者“如何去做”，同时包括许多算法、代码以及具体实例的实现。

将所有的概念都建立在具体实例的基础之上，促使读者首先考虑使用简单的技术。如果简单的技术不足以解决问题，再考虑提升到更为复杂的高级技术。

新版增加了大量近年来涌现的数据挖掘算法和诸如Web数据挖掘等新领域的介绍，所介绍的weka系统增加了50%的算法及大量新内容。

《数据挖掘：实用机器学习工具与技术（原书第3版）》是机器学习和数据挖掘领域的经典畅销教材，被众多国外名校选为教材。书中详细介绍用于数据挖掘领域的机器学习技术和工具以及实践方法，并且提供了一个公开的数据挖掘工作平台Weka。本书主要内容包括：数据输入/输出、知识表示、数据挖掘技术（决策树、关联规则、基于实例的学习、线性模型、聚类、多实例学习等）以及在实践中的运用。本版对上一版内容进行了全面更新，以反映自第2版出版以来数据挖掘领域的技术变革和新方法，包括数据转换、集成学习、大规模数据集、多实例学习等，以及新版的Weka机器学习软件。

Ian H.Witten，新西兰怀卡托大学计算机科学系教授，ACM Fellow和新西兰皇家学会Fellow，曾荣获2004年国际信息处理研究协会（IFIP）颁发的Namur奖项。他的研究兴趣包括语言学习、信息检索和机器学习。

Eibe Frank，新西兰怀卡托大学计算机科学系副教授，《Machine Learning Journal》和《Journal of Artificial Intelligence Research》编委。

Mark A.Hall，新西兰怀卡托大学名誉副研究员，曾获得2005年ACM SIGKDD服务奖。

译者简介：

李川，博士，副教授，四川大学计算机学院数据库知识工程研究所副所长，中国计算机学会数据库专委会委员。主持国家自然科学基金青年基金等项目多项，合作发表论文30余篇,获四川省科技成果二等奖1项。

★“本书既含理论又有实践应用，并且关注实践是本书的一大特色。对于从事数据挖掘和机器学习方面工作的每位读者，我强烈推荐本书！”
——Dorian Pyle《Data Preparation for Data Mining》和《Business Modeling for Data Mining》的作者

★“本书在数据挖掘技术领域备受推崇，是数据挖掘分析师的必读之物！”
——Herb EdelsteinTwo Crows Consulting公司首席数据挖掘咨询顾问

★“这是我最喜爱的数据挖掘书籍之一，书中不仅循序渐进地介绍了各种算法，还辅以丰富实例，详细阐述了如何应用这些算法解决实际数据挖掘问题。本书不但有益于学习使用Weka软件，而且还会帮助你了解各类机器学习算法。”
——Tom BreurXLNT Consulting公司首席咨询顾问

★“本书既含理论又有实践应用，并且关注实践是本书的一大特色。对于从事数据挖掘和机器学习方面工作的每位读者，我强烈推荐本书！”
——Dorian Pyle《Data Preparation for Data Mining》和《Business Modeling for Data Mining》的作者


★“这是我最喜爱的数据挖掘书籍之一，书中不仅循序渐进地介绍了各种算法，还辅以丰富实例，详细阐述了如何应用这些算法解决实际数据挖掘问题。本书不但有益于学习使用Weka软件，而且还会帮助你了解各类机器学习算法。”
——Tom BreurXLNT Consulting公司首席咨询顾问

★“假如你需要对数据进行分析和理解，本书以及相关的Weka工具包是一个不错的起步。
本书以非常容易理解的方式展示了这门新的学科：既是用来训练新一代实际工作者和研究者的教科书，同时又能让像我这样的专业人员受益。Witten、Frank和Hall热衷于简单而优美的解决方案。他们对每个主题都采用这样的方法，用具体的实例来讲解所有的概念，促使读者首先考虑简单的技术，当简单的技术不足以解决问题时，就提升到更为复杂的高级技术。”
——Jim Gray（图灵奖获得者）

★“本书既含理论又有实践应用，并且关注实践是本书的一大特色。对于从事数据挖掘和机器学习方面工作的每位读者，我强烈推荐本书！”
——Dorian Pyle《Data Preparation for Data Mining》和《Business Modeling for Data Mining》的作者

Data Mining：Practical Machine Learning Tools and Techniques，Third Edition
出版者的话
译者序
前言
致谢
第一部分数据挖掘简介
第1章绪论2
1.1数据挖掘和机器学习2
1.1.1描述结构模式3
1.1.2机器学习5
1.1.3数据挖掘6
1.2简单的例子：天气问题和其他问题6
1.2.1天气问题7
1.2.2隐形眼镜：一个理想化的问题8
1.2.3鸢尾花：一个经典的数值型数据集10
1.2.4CPU性能：介绍数值预测11
1.2.5劳资协商：一个更真实的例子11
1.2.6大豆分类：一个经典的机器学习的成功例子13
1.3应用领域14
1.3.1Web挖掘15
1.3.2包含评判的决策15
1.3.3图像筛选16
1.3.4负载预测17
1.3.5诊断17
1.3.6市场和销售18
1.3.7其他应用19
1.4机器学习和统计学20
1.5将泛化看做搜索21
1.5.1枚举概念空间22
1.5.2偏差22
1.6数据挖掘和道德24
1.6.1再识别25
1.6.2使用个人信息25
1.6.3其他问题26
1.7补充读物27

第2章输入：概念、实例和属性29
2.1概念29
2.2样本31
2.2.1关系32
2.2.2其他实例类型34
2.3属性35
2.4输入准备37
2.4.1数据收集37
2.4.2ARFF格式38
2.4.3稀疏数据40
2.4.4属性类型40
2.4.5缺失值41
2.4.6不正确的值42
2.4.7了解数据43
2.5补充读物43

第3章输出：知识表达44
3.1表44
3.2线性模型44
3.3树45
3.4规则48
3.4.1分类规则49
3.4.2关联规则52
3.4.3包含例外的规则52
3.4.4表达能力更强的规则54
3.5基于实例的表达56
3.6聚类58
3.7补充读物60

第4章算法：基本方法61
4.1推断基本规则61
4.1.1缺失值和数值属性62
4.1.2讨论64
4.2统计建模64
4.2.1缺失值和数值属性67
4.2.2用于文档分类的朴素贝叶斯68
4.2.3讨论70
4.3分治法：建立决策树70
4.3.1计算信息量73
4.3.2高度分支属性74
4.3.3讨论75
4.4覆盖算法：建立规则76
4.4.1规则与树77
4.4.2一个简单的覆盖算法77
4.4.3规则与决策列表80
4.5挖掘关联规则81
4.5.1项集81
4.5.2关联规则83
4.5.3有效地生成规则85
4.5.4讨论87
4.6线性模型87
4.6.1数值预测：线性回归87
4.6.2线性分类：Logistic回归88
4.6.3使用感知机的线性分类90
4.6.4使用Winnow的线性分类91
4.7基于实例的学习92
4.7.1距离函数93
4.7.2有效寻找最近邻93
4.7.3讨论97
4.8聚类97
4.8.1基于距离的迭代聚类98
4.8.2快速距离计算99
4.8.3讨论100
4.9多实例学习100
4.9.1聚集输入100
4.9.2聚集输出100
4.9.3讨论101
4.10补充读物101
4.11Weka实现103

第5章可信度：评估学习结果104
5.1训练和测试104
5.2预测性能106
5.3交叉验证108
5.4其他评估方法109
5.4.1留一交叉验证109
5.4.2自助法109
5.5数据挖掘方法比较110
5.6预测概率113
5.6.1二次损失函数114
5.6.2信息损失函数115
5.6.3讨论115
5.7计算成本116
5.7.1成本敏感分类117
5.7.2成本敏感学习118
5.7.3提升图119
5.7.4ROC曲线122
5.7.5召回率-精确率曲线124
5.7.6讨论124
5.7.7成本曲线125
5.8评估数值预测127
5.9最小描述长度原理129
5.10在聚类方法中应用MDL原理131
5.11补充读物132

第二部分高级数据挖掘
第6章实现：真正的机器学习方案134
6.1决策树135
6.1.1数值属性135
6.1.2缺失值136
6.1.3剪枝137
6.1.4估计误差率138
6.1.5决策树归纳的复杂度140
6.1.6从决策树到规则140
6.1.7C4.5:选择和选项141
6.1.8成本-复杂度剪枝141
6.1.9讨论142
6.2分类规则142
6.2.1选择测试的标准143
6.2.2缺失值和数值属性143
6.2.3生成好的规则144
6.2.4使用全局优化146
6.2.5从局部决策树中获得规则146
6.2.6包含例外的规则149
6.2.7讨论151
6.3关联规则152
6.3.1建立频繁模式树152
6.3.2寻找大项集157
6.3.3讨论157
6.4扩展线性模型158
6.4.1最大间隔超平面159
6.4.2非线性类边界160
6.4.3支持向量回归161
6.4.4核岭回归163
6.4.5核感知机164
6.4.6多层感知机165
6.4.7径向基函数网络171
6.4.8随机梯度下降172
6.4.9讨论173
6.5基于实例的学习174
6.5.1减少样本集的数量174
6.5.2对噪声样本集剪枝174
6.5.3属性加权175
6.5.4泛化样本集176
6.5.5用于泛化样本集的距离函数176
6.5.6泛化的距离函数177
6.5.7讨论178
6.6局部线性模型用于数值预测178
6.6.1模型树179
6.6.2构建树179
6.6.3对树剪枝180
6.6.4名目属性180
6.6.5缺失值181
6.6.6模型树归纳的伪代码181
6.6.7从模型树到规则184
6.6.8局部加权线性回归184
6.6.9讨论185
6.7贝叶斯网络186
6.7.1预测186
6.7.2学习贝叶斯网络189
6.7.3算法细节190
6.7.4用于快速学习的数据结构192
6.7.5讨论194
6.8聚类194
6.8.1选择聚类的个数195
6.8.2层次聚类195
6.8.3层次聚类的例子196
6.8.4增量聚类199
6.8.5分类效用203
6.8.6基于概率的聚类204
6.8.7EM算法205
6.8.8扩展混合模型206
6.8.9贝叶斯聚类207
6.8.10讨论209
6.9半监督学习210
6.9.1用于分类的聚类210
6.9.2协同训练212
6.9.3EM和协同训练212
6.9.4讨论213
6.10多实例学习213
6.10.1转换为单实例学习213
6.10.2升级学习算法215
6.10.3专用多实例方法215
6.10.4讨论216
6.11Weka实现216

第7章数据转换218
7.1属性选择219
7.1.1独立于方案的选择220
7.1.2搜索属性空间222
7.1.3具体方案相关的选择223
7.2离散化数值属性225
7.2.1无监督离散化226
7.2.2基于熵的离散化226
7.2.3其他离散化方法229
7.2.4基于熵的离散化与基于误差的离散化229
7.2.5离散属性转换成数值属性230
7.3投影230
7.3.1主成分分析231
7.3.2随机投影233
7.3.3偏最小二乘回归233
7.3.4从文本到属性向量235
7.3.5时间序列236
7.4抽样236
7.5数据清洗237
7.5.1改进决策树237
7.5.2稳健回归238
7.5.3检测异常239
7.5.4一分类学习239
7.6多分类问题转换成二分类问题242
7.6.1简单方法242
7.6.2误差校正输出编码243
7.6.3集成嵌套二分法244
7.7校准类概率246
7.8补充读物247
7.9Weka实现249

第8章集成学习250
8.1组合多种模型250
8.2装袋251
8.2.1偏差-方差分解251
8.2.2考虑成本的装袋253
8.3随机化253
8.3.1随机化与装袋254
8.3.2旋转森林254
8.4提升255
8.4.1AdaBoost算法255
8.4.2提升算法的威力257
8.5累加回归258
8.5.1数值预测258
8.5.2累加Logistic回归259
8.6可解释的集成器260
8.6.1选择树260
8.6.2Logistic模型树262
8.7堆栈262
8.8补充读物264
8.9Weka实现265

第9章继续：扩展和应用266
9.1应用数据挖掘266
9.2从大型的数据集里学习268
9.3数据流学习270
9.4融合领域知识272
9.5文本挖掘273
9.6Web挖掘276
9.7对抗情形278
9.8无处不在的数据挖掘280
9.9补充读物281

第三部分Weka数据挖掘平台
第10章Weka简介284
10.1Weka中包含了什么284
10.2如何使用Weka285
10.3Weka的其他应用286
10.4如何得到Weka286
……
第11章Explorer界面287
第12章Knowledge Flow界面351
第13章Experimenter界面358
第14章命令行界面368
第15章嵌入式机器学习376
第16章编写新的学习方案382
第17章Weka Explorer的辅导练习397
参考文献416
索引431

第一部分数据挖掘简介
第1章绪论
人工受精的过程是从妇女的卵巢中收集卵子，再与丈夫或捐赠人的精液结合后产生胚胎，然后从中选择几个胚胎移植到妇女的子宫里。关键是要选出那些存活可能性最大的胚胎。选择根据60个左右的胚胎特征记录做出，这些特征包括它们的形态、卵母细胞、滤泡和精液样品。特征属性的数量非常大，胚胎学家很难同时对所有属性进行评估，并结合历史数据得出最终结论：这个胚胎是否能够产生一个活的婴儿。在英格兰的一个研究项目中，研究者探索运用机器学习技术，使用历史记录和它们的输出作为训练数据。
每年，新西兰奶牛场主都要面临艰难的商业决策：哪些牛应该留在牧场，哪些牛需要卖到屠宰场。随着饲料储备的减少，每年牧场在接近挤奶季节末期时只留下1/5的奶牛。每头牛的生育和牛奶产量的历史数据都会影响这个决定。除此以外还要考虑的因素有：年龄（每头牛都将在8岁后接近生育期的终结）、健康问题、难产的历史数据、不良的性情特征（如尥蹶子、跳栅栏）、在下一个季节里不产牛犊。在过去的几年中，几百万头牛中的每一头牛都用700多个属性记录下来。机器学习正是用来考察成功的农场主在做决定的时候需要考虑哪些因素，不是为了使决策自动化，而是向其他人推广这些农场主的技术和经验。
机器学习是从数据中挖掘知识。它是一个正在萌芽的新技术，范围涉及生与死、从欧洲到两极、家庭和事业，正逐渐引起人们的重视。
1.1数据挖掘和机器学习
我们正在被数据所淹没。存在于这个世界和我们生活中的数据总量似乎在不断地增长，而且没有停止的迹象。个人计算机的普及将那些以前会丢弃的数据保存起来。便宜的硬盘和网络硬盘，3使得很容易以后再决定用这些数据做什么，因为我们可以买更多的硬盘来保存数据。无处不在的电子器件记录了我们的决策，如超市里的商品选择、个人的理财习惯，以及收入和消费。我们以自己的方式生活在这个世界上，而每一个行为又成为一条数据库里的记录保存下来。如今互联网用信息将我们淹没，我们在网上所做的每一个选择都被记录下来。所有的这些信息记录了个人的选择，而在商业和企业领域存在着数不清的相似案例。我们都知道我们对数据的掌握永远无法赶上数据升级的速度。而且在数据量增加的同时，无情地伴随着人们对它理解的降低。隐藏在这些数据后的是信息，具有潜在用处的信息，而这些信息却很少被显现出来或者被开发利用。
本书介绍如何在数据中寻找模式。这并不稀奇，人们从一开始，就试图在数据中寻找模式。猎人在动物迁徙的行为中寻找模式；农夫在庄稼的生长中寻找模式；政客在选民的意见上寻找模式；恋人在对方的反应中寻找模式。科学家的工作（像一个婴儿）是理解数据，从数据中找出模式，并用它们来指导在真实世界中如何运作，然后把它们概括成理论，这些理论能够预测出在新的情况下会发生什么。企业家的工作是要辨别出机会，就是那些可以转变成有利可图的生意的行为中的一些模式，并且利用这些机会。
在数据挖掘（data mining）中，计算机以电子化的形式存储数据，并且能自动地查询数据，或至少扩增数据。这仍算不得新鲜事。经济学家、统计学家、预测家和信息工程师长久以来相信，存在于数据中的模式能够被自动地找到、识别、确认并能用于预测。该理论的最新发展使得由数据中找出模式的机遇剧增。在最近几年，数据库急剧膨胀，如每天记录顾客选择商品行为的数据库，正把数据挖掘带到新的商业应用技术的前沿。据估计，存储在全世界数据库里的数据量正以每20个月翻一倍的速度增长。尽管很难从量的意义上真正验证这个数字，但是我们可以从质上把握这个增长速度。随着数据量的膨胀，以及利用机器承担数据搜索工作已变得普通，数据挖掘的机会正在增长。世界正越来越丰富多彩，从中产生的数据淹没了我们，数据挖掘技术成为我们洞察构成数据的模式的唯一希望。被充分研究过的数据是宝贵的资源。它能够引导人们去获得新的洞察力，用商业语言来讲就是获得竞争优势。
数据挖掘就是通过分析存在于数据库里的数据来解决问题。例如，在激烈竞争的市场上，客户忠诚度摇摆问题就是一个经常提到的事例。一个有关客户商品选择以及客户个人资料的数据库是解决这个问题的关键。以前客户的行为模式能够用来分析并识别那些喜欢选购不同商品和那些喜欢选择同种商品的客户的特性。一旦这些特性被发现，它们将被用于当前实际的客户群中，鉴别出那些善变的客户群体，并加以特殊对待，须知对整个客户群都加以特殊对待的成本是高昂的。4更确切地说，同样的技术还能够用来辨别出那些对企业当前提供的服务并不满意，但是有可能对其他服务感兴趣的客户群，并向他们提供特殊建议，从而推广这些服务。在当代竞争激烈、以客户和服务为中心的经济中，如果数据能够被挖掘，它将成为推动企业发展的原材料。
数据挖掘被定义为找出数据中的模式的过程。这个过程必须是自动的或（更常见的是）半自动的。数据的总量总是相当可观的，但从中发现的模式必须是有意义的，并能产生出一些效益，通常是经济上的效益。
如何表示数据模式？有价值的模式能够让我们对新数据做出非平凡的预测。表示一个模式有两种极端方法：一种是内部结构很难被理解的黑匣子；一种是展示模式结构的透明匣子，它的结构揭示了模式的结构。我们假设两种方法都能做出好的预测，它们的区别在于被挖掘出的模式能否以结构的形式表现，这个结构是否能够经得起分析，理由是否充分，能否用来形成未来的决策。如果模式能够以显而易见的方法获得决策结构，就称为结构模式，换句话说，它们能帮助解释有关数据的一些现象。
现在我们可以说，本书是有关寻找、描述存在于数据中的结构模式的技术。我们所涉及的大部分技术已经在被称为机器学习的领域里开发出来。这里我们首先介绍什么是结构模式。
1.1.1描述结构模式
结构模式（structural pattern）是什么？如何描述它们？用什么形式输入？我们将以举例的形式来回答这个问题，而不是尝试给出正式的、最终的死板定义。本章后面将给出很多例子，现在让我们从一个例子入手来体验我们正在讲解的内容。
表1-1给出了隐形眼镜的一组数据。这组数据是验光师针对病人的情况做出的诊断：使用软的隐形眼镜，硬的隐形眼镜，或不能佩戴隐形眼镜。我们将在以后详细讨论属性的单独意义。表中的每一行代表一个例子。下面是有关这个信息的部分结构描述。
表1-1隐形眼镜数据
结构描述不一定像以上这样以规则的形式来表达。另一种流行的表达方法是决策树，它明确了需要做出的决策序列以及伴随的建议。
这是一个非常简单的例子。首先，这个表呈现了所有可能值的组合。属性age（年龄）有3种可能值，属性spectacle prescription（视力诊断）、astigmatism（散光）和tear production rate（眼泪流速）分别有2种可能值。所以这个表有24行记录（3×2×2×2＝24）。上面所提到的规则并不是真正从数据中概括出来的，而只是对数据的总结。在多数学习的情况下，所给出的样本集非常不完整，所以我们的一部分工作就是将其推广到其他新的样本上实现一般化。用户可以想象，如果从上面的表格中忽略一些tear production rate的值是reduced的行，仍然可以得出规则：
这个规则可以推广到那些遗失的行，并且能正确地把它们填充到表里去。其次，样本中的每一个属性都指定了一个值。现实的数据集不可避免地存在一些样本，这些样本中的某些属性值因为一些原因而不可知，例如数据没有被测量、丢失或其他原因。再次，上面所提到的规则能正确地对例子进行分类，但是通常情况下，因为数据中存在一些错误或者噪声（noise），即使在用来训练分类器的数据上也会发生分类错误的情况。
1.1.2机器学习
现在我们已经有一些输入和输出的概念，下面我们将转入机器学习的主题。究竟什么是学习？什么是机器学习（machine learning）？这是哲学范畴的问题，在本书中，我们将不涉及有关哲学的问题，而着重立足于实践。然而，在着手开始研究机器学习之前，值得花一些时间从一些基本的问题入手，弄清其中的微妙之处。我们的字典所给出的“学习”的定义如下：
通过学习、体验或者被教授得到知识。
从信息或观察中得知。
获得记忆。
被告知或查明。
接受指令。
当涉及计算机的时候，这些定义就存在一些缺陷。对于前两条，事实上不可能检测学习是否完成。我们怎么能知道一台机器是否拥有某种知识？我们也不大可能向机器提出问题；即使我们能，那也只是在测试机器回答问题的能力，而不可能测试它学习的能力。我们又如何知道它是否意识到什么？有关计算机是否能意识到或有知觉的问题是一个激烈争论的哲学问题。
对于后三条定义，用人类的术语来说，我们看到它们做出的贡献局限于记忆和接受指令，这个定义对我们所指的机器学习似乎太简单了，也太被动了，对于计算机来说，这些任务太平凡了。而我们只对在新情况中性能的改善，或至少性能所具有的潜力感兴趣。你可以通过死记硬背的学习方法来记忆或得知某事，但却没有能力在新的情况下运用新的知识。换句话说，你也能够得到指导却毫无收益。
以前我们是从可操作的角度上定义机器学习：机器学习是从大量的数据中自动或半自动地寻找模式的过程，而且这个模式必须是有用的。我们可以用同样的方法为学习建立一个可操作的定义：
当事物以令其自身在将来表现更好为标准来改变其行为时，它学到了东西。
这个定义将学习和表现而不是知识捆绑在一起。你可以通过观察和比较现在和过去的行为来评估学习。这是一个非常客观的看上去也满意得多的定义。7
但是仍然存在一些问题。学习是一个有点圆滑的概念。很多事物都能以多种途径改变它们的行为，以使它们能在未来做得更好，但是我们不愿意说它们已经真正学到了。一只舒服的拖鞋就是一个很好的例子。拖鞋学到了脚的形状了吗？当然拖鞋确实改变了它的外形从而使它成为一只很舒服的拖鞋。我们不想称其为学习。在日常语言中，我们往往使用训练这个词引申出一个不用大脑的学习。我们训练动物甚至植物，尽管这个概念可从训练像拖鞋一类没有生命的事物上得到拓展。但是学习是不同的。学习意味着思考和目的，并且学习必须有意去做一些事。这就是为什么我们不愿说一个葡萄藤学会了沿着葡萄园的架子生长，而说它已经被训练。没有目的的学习只能是训练，或者进一步说，在学习中，目的是学习者的目的，而在训练中，目的是老师的目的。
因此从计算机的视角出发，以可操作的、性能为指导的原则进一步审视第二种学习的定义时，就存在一些问题。当判断是否真正学到一些东西时，需要看它是否打算去学，是否其中包含一些目的。当应用到机器上时，它使概念抽象化，因为我们无法弄清楚人工制品是否能够做出有目的的举动。哲学上有关学习真正意味着什么的讨论，就像有关目的或打算真正意味什么一样充满困难。甚至法院也很难把握“企图”的含义。
……