数据挖掘原理（第3版）

                      前    言

      《数据挖掘原理(第3版)》面向计算机科学、商业研究、市场营销、人工智能、生物信息学和法医学专业的学生，可用作本科生或硕士研究生的入门教材。同时，对于那些希望进一步提高自身能力的技术或管理人员来说，《数据挖掘原理(第3版)》也是一本极佳的自学书籍。《数据挖掘原理(第3版)》所涉及的内容远超一般的数据挖掘入门书籍。与许多其他书籍不同的是，在学习过程中你不需要拥有太多的数学知识即可理解相关内容。
        数学是一种可以表达复杂思想的语言。遗憾的是，99％的人都无法很好地掌握这门语言；很多人很早就开始在学校学习一些基础知识，但学习过程往往充满曲折。
《数据挖掘原理(第3版)》涉及数学公式较少，将重点介绍相关概念。但遗憾的是，完全不使用数学符号是不可能的。附录A给出开始学习《数据挖掘原理(第3版)》需要掌握的所有内容。对于那些在学校学习数学的人来说，这些内容应该是非常熟悉的。掌握这些内容后，其他内容就较好理解了。如果觉得某些数学符号难以理解，通常可放心地忽略它们，只需要关注结果和给出的详细示例即可。而对于那些希望更深入理解数据挖掘的数学基础知识的人来说，可参考附录C中列出的内容。
过去，没有一本关于数据挖掘的入门书可使你具备该领域的研究水平——但现在，这样的日子已经过去了。           《数据挖掘原理(第3版)》的重点是介绍基本技术，而不是展示当今的数据挖掘技术，因为大多数情况下，当拿到一《数据挖掘原理(第3版)》时，书中介绍的技术可能已被其他更新的技术取代了。一旦掌握了基本技术，你可通过多种渠道来了解该领域的进展。附录C列出一些常用资源，而其他附录包括有关《数据挖掘原理(第3版)》示例中使用的主要数据集的信息，供你在自己的项目中使用。此外附录D包括技术术语表。
       为便于检查对所学知识的掌握情况，每章都包含自我评估练习。参考答案见附录E。
       另外说明一下，《数据挖掘原理(第3版)》涉及大量数据集、属性和值，也涉及不少数学公式，字母繁多，格式复杂。为保证全书的科学性和严谨性，中文书中，字母的正斜体与英文原书基本保持统一。
书末列出全书各章正文中引用的参考文献。读者在阅读正文时，会不时看到引用；引用的形式为[*]，其中*为数字编号。遇到此类引用时，读者可跳转到书末，查阅相关信息。

      《数据挖掘原理(第3版)》深入探讨重要的数据挖掘技术。所谓数据挖掘，即从数据中自动提取隐含和潜在有用的信息；该技术正越来越多地用于商业、科学和其他应用领域。本书浓墨重彩地描述分类、关联规则挖掘和聚类。 　　

        普通读者可通过本书自学数据挖掘“黑匣子”内部的基本原理，并了解如何合理地选择商业数据挖掘包。学者和资深科研人员可通过本书了解*前沿技术并进一步推动该领域的发展。 　　

        《数据挖掘原理(第3版)》在第2版的基础上进行扩展，透彻讲解适用于平稳数据的H-Tree算法，以及适用于时间相关数据(概念漂移)的CDH-Tree算法。

        Max Bramer是英国朴次茅斯大学信息技术系荣誉教授、IFIP副主席、英国计算机学会AI专家组主席。

　　自从 “数据挖掘”“数据库中的知识发现”“大数据”和“预测分析”等技术兴起以来，Max积极参与了多个数据挖掘项目，尤其是与数据自动分类相关的项目。

        Max发表了大量技术文章，曾撰写Research and Development in Intelligent Systems等著作。Max具有多年的本科和研究生教学经验。

目    录
 
第 1 章  数据挖掘简介   1
1.1  数据爆炸   1
1.2  知识发现   2
1.3  数据挖掘的应用   3
1.4  标签和无标签数据   4
1.5  监督学习：分类   4
1.6  监督学习：数值预测   5
1.7  无监督学习：关联规则   6
1.8  无监督学习：聚类   7
第 2 章  用于挖掘的数据   9
2.1  标准制定   9
2.2  变量的类型   10
2.3  数据准备   11
2.4  缺失值   13
2.4.1  丢弃实例   13
2.4.2  用频繁值/平均值替换   13
2.5  减少属性个数   14
2.6  数据集的UCI存储库   15
2.7  本章小结   15
2.8  自我评估练习   15
第 3 章  分类简介：朴素贝叶斯和近邻算法   17
3.1  什么是分类   17
3.2  朴素贝叶斯分类器   18
3.3  近邻分类   24
3.3.1  距离测量   26
3.3.2  标准化   28
3.3.3  处理分类属性   29
3.4  急切式和懒惰式学习   30
3.5  本章小结   30
3.6  自我评估练习   30
第 4 章  使用决策树进行分类   31
4.1  决策规则和决策树   31
4.1.1  决策树：高尔夫示例   31
4.1.2  术语   33
4.1.3  degrees数据集   33
4.2  TDIDT算法   36
4.3  推理类型   38
4.4  本章小结   38
4.5  自我评估练习   39
第 5 章  决策树归纳：使用熵进行属性选择   41
5.1  属性选择：一个实验   41
5.2  替代决策树   42
5.2.1  足球/无板篮球示例   42
5.2.2  匿名数据集   44
5.3  选择要分裂的属性：使用熵   46
5.3.1  lens24数据集   46
5.3.2  熵   47
5.3.3  使用熵进行属性选择   48
5.3.4  信息增益化   50
5.4  本章小结   51
5.5  自我评估练习   51
第 6 章  决策树归纳：使用频率表进行属性选择   53
6.1  实践中的熵计算   53
6.1.1  等效性证明   55
6.1.2  关于零值的说明   56
6.2  其他属性选择标准：多样性基尼指数   56
6.3  χ2属性选择准则   57
6.4  归纳偏好   60
6.5  使用增益比进行属性选择   61
6.5.1  分裂信息的属性   62
6.5.2  总结   63
6.6  不同属性选择标准生成的规则数   63
6.7  缺失分支   64
6.8  本章小结   65
6.9  自我评估练习   65
第 7 章  估计分类器的预测精度   67
7.1  简介   67
7.2  方法1：将数据划分为训练集和测试集   68
7.2.1  标准误差   68
7.2.2  重复训练和测试   69
7.3  方法2：k-折交叉验证   70
7.4  方法3：N -折交叉验证   70
7.5  实验结果I   71
7.6  实验结果II：包含缺失值的数据集   73
7.6.1  策略1：丢弃实例   73
7.6.2  策略2：用频繁值/平均值替换   74
7.6.3  类别缺失   75
7.7  混淆矩阵   75
7.8  本章小结   77
7.9  自我评估练习   77
第 8 章  连续属性   79
8.1  简介   79
8.2  局部与全局离散化   81
8.3  向TDIDT添加局部离散化   81
8.3.1  计算一组伪属性的信息增益   82
8.3.2  计算效率   86
8.4  使用ChiMerge算法进行全局离散化   88
8.4.1  计算期望值和χ2   90
8.4.2  查找阈值   94
8.4.3  设置minIntervals和maxIntervals   95
8.4.4  ChiMerge算法：总结   96
8.4.5  对ChiMerge算法的评述   96
8.5  比较树归纳法的全局离散化和局部离散化   97
8.6  本章小结   98
8.7  自我评估练习   98
第 9 章  避免决策树的过度拟合   99
9.1  处理训练集中的冲突   99
9.2  关于过度拟合数据的更多规则   103
9.3  预剪枝决策树   104
9.4  后剪枝决策树   106
9.5  本章小结   111
9.6  自我评估练习   111
第 10 章  关于熵的更多信息   113
10.1  简介   113
10.2  使用位的编码信息   116
10.3  区分值   117
10.4  对“非等可能”的值进行编码   118
10.5  训练集的熵   121
10.6  信息增益必须为正数或零   122
10.7  使用信息增益来简化分类任务的特征   123
10.7.1  示例1：genetics数据集   124
10.7.2  示例2：bcst96数据集   126
10.8  本章小结   128
10.9  自我评估练习   128
第 11 章  归纳分类的模块化规则   129
11.1  规则后剪枝   129
11.2  冲突解决   130
11.3  决策树的问题   133
11.4  Prism算法   135
11.4.1  基本Prism算法的变化   141
11.4.2  将Prism算法与TDIDT算法进行比较   142
11.5  本章小结   143
11.6  自我评估练习   143
第 12 章  度量分类器的性能   145
12.1  真假正例和真假负例   146
12.2  性能度量   147
12.3  真假正例率与预测精度   150
12.4  ROC图   151
12.5  ROC曲线   153
12.6  寻找分类器   153
12.7  本章小结   155
12.8  自我评估练习   155
第 13 章  处理大量数据   157
13.1  简介   157
13.2  将数据分发到多个处理器   159
13.3  案例研究：PMCRI   161
13.4  评估分布式系统PMCRI的有效性   163
13.5  逐步修改分类器   167
13.6  本章小结   171
13.7  自我评估练习   171
第 14 章  集成分类   173
14.1  简介   173
14.2  估计分类器的性能   175
14.3  为每个分类器选择不同的训练集   176
14.4  为每个分类器选择一组不同的属性   177
14.5  组合分类：替代投票系统   177
14.6  并行集成分类器   180
14.7  本章小结   181
14.8  自我评估练习   181
第 15 章  比较分类器   183
15.1  简介   183
15.2  配对t检验   184
15.3  为比较评估选择数据集   189
15.4  抽样   191
15.5  “无显著差异”的结果有多糟糕?   193
15.6  本章小结   194
15.7  自我评估练习   194
第 16 章  关联规则挖掘I   195
16.1  简介   195
16.2  规则兴趣度的衡量标准   196
16.2.1  Piatetsky-Shapiro标准和RI度量   198
16.2.2  规则兴趣度度量应用于chess数据集   200
16.2.3  使用规则兴趣度度量来解决冲突   201
16.3  关联规则挖掘任务   202
16.4  找到N条规则   202
16.4.1  J-Measure：度量规则的信息内容   203
16.4.2  搜索策略   204
16.5  本章小结   207
16.6  自我评估练习   207
第 17 章  关联规则挖掘II   209
17.1  简介   209
17.2  事务和项目集   209
17.3  对项目集的支持   211
17.4  关联规则   211
17.5  生成关联规则   213
17.6  Apriori   214
17.7  生成支持项目集：一个示例   217
17.8  为支持项目集生成规则   219
17.9  规则兴趣度度量：提升度和杠杆率   220
17.10  本章小结   222
17.11  自我评估练习   222
第 18 章  关联规则挖掘III：频繁模式树   225
18.1  简介：FP-growth   225
18.2  构造FP-tree   227
18.2.1  预处理事务数据库   227
18.2.2  初始化   229
18.2.3  处理事务1：f, c, a, m, p   230
18.2.4  处理事务2：f, c, a, b, m   231
18.2.5  处理事务3：f, b   235
18.2.6  处理事务4：c, b, p   236
18.2.7  处理事务5：f, c, a, m, p   236
18.3  从FP-tree中查找频繁项目集   238
18.3.1  以项目p结尾的项目集   240
18.3.2  以项目m结尾的项目集   248
18.4  本章小结   254
18.5  自我评估练习   254
第 19 章  聚类   255
19.1  简介   255
19.2  k-means聚类   257
19.2.1  示例   258
19.2.2  找到簇集   262
19.3  凝聚式层次聚类   263
19.3.1  记录簇间距离   265
19.3.2  终止聚类过程   268
19.4  本章小结   268
19.5  自我评估练习   268
第 20 章  文本挖掘   269
20.1  多重分类   269
20.2  表示数据挖掘的文本文档   270
20.3  停用词和词干   271
20.4  使用信息增益来减少特征   272
20.5  表示文本文档：构建向量空间模型   272
20.6  规范权重   273
20.7  测量两个向量之间的距离   274
20.8  度量文本分类器的性能   275
20.9  超文本分类   275
20.9.1  对网页进行分类   276
20.9.2  超文本分类与文本分类   277
20.10  本章小结   279
20.11  自我评估练习   280
第 21 章  分类流数据   281
21.1  简介   281