数据挖掘导论（英文版·原书第2版）

本书从算法的角度介绍数据挖掘所使用的主要原理与技术。为了更好地理解数据挖掘技术如何用于各种类型的数据，研究这些原理与技术是至关重要的。
本书所涵盖的主题包括：数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法，为读者提供将数据挖掘应用于实际问题所需的必要背景以及使用方法。

陈封能（Pang-Ning Tan） 密歇根州立大学计算机科学与工程系教授，主要研究方向是数据挖掘、数据库系统、网络空间安全、网络分析等。

第1章　绪论 1
11　什么是数据挖掘 4
12　数据挖掘要解决的问题 5
13　数据挖掘的起源 7
14　数据挖掘任务 9
15　本书组织结构 13
16　文献注释 15
17　习题 21
第2章　数据 23
21　数据类型 26
211　属性与度量 27
212　数据集的类型 34
22　数据质量 42
221　测量和数据收集问题 42
222　关于应用的问题 49
23　数据预处理 50
231　聚集 51
232　抽样 52
233　维归约 56
234　特征子集选择 58
235　特征创建 61
236　离散化和二元化 63
237　变量变换 69
24　相似性和相异性的度量 71
241　基础 72
242　简单属性之间的相似度和相异度 74
243　数据对象之间的相异度 76
244　数据对象之间的相似度 78
245　邻近度度量的例子 79
246　互信息 88
* 247　核函数 90
* 248　Bregman散度 94
249　邻近度计算问题 96
2410　选择正确的邻近度度量 98
25　文献注释 100
26　习题 105
第3章　分类：基本概念和技术 113
31　基本概念 114
32　一般的分类框架 117
33　决策树分类器 119
331　构建决策树的基本算法 121
332　表示属性测试条件的方法 124
333　选择属性测试条件的方法 127
334　决策树归纳算法 136
335　示例：Web机器人检测 138
336　决策树分类器的特征 140
34　模型的过拟 147
35　模型选择 156
351　验证集应用 156
352　模型复杂度合并 157
353　统计范围估计 162
354　决策树的模型选择 162
36　模型评估 164
361　保持方法 165
362　交叉验证 165
37　超参数的使用 168
371　超参数选择 168
372　嵌套交叉验证 170
38　模型选择和评估中的陷阱 172
381　训练集和测试集之间的重叠 172
382　使用验证错误率作为泛化错误率
*39　模型比较 173
391　估计准确率的置信区间 174
392　比较两个模型的性能 175
310　文献注释 176
311　习题 185
第4章　分类：其他技术 193
41　分类器的种类 193
42　基于规则的分类器 195
421　基于规则的分类器原理 197
422　规则集的属性 198
423　规则提取的直接方法 199
424　规则提取的间接方法 204
425　基于规则的分类器的特点 206
43　最近邻分类器 208
431　算法 209
432　最近邻分类器的特点 210
44　朴素贝叶斯分类器 212
441　概率论基础 213
442　朴素贝叶斯假设 218
45　贝叶斯网络 227
451　图表示 227
452　推理与学习 233
453　贝叶斯网络的特点 242
46　logistic回归 243
461　logistic回归用作广义线性模型 244
462　学习模型参数 245
463　logistic回归模型的特点 248
47　人工神经网络 249
471　感知机 250
472　多层神经网络 254
473　人工神经网络的特点 261
48　深度学习 262
481　使用协同损失函数 263
482　使用响应激活函数 266
483　正则化 268
484　模型参数的初始化 271
485　深度学习的特点 275
49　支持向量机 276
491　分离超平面的边缘 276
492　线性SVM 278
493　软边缘SVM 284
494　非线性SVM 290
495　SVM的特点 294
410　组合方法 296
4101　组合方法的基本原理 297
4102　构建组合分类器的方法 297
4103　偏置–方差分解 300
4104　装袋 302
4105　提升 305
4106　随机森林 310
4107　组合方法的实验比较 312
411　类不平衡问题 313
4111　类不平衡的分类器构建 314
4112　带类不平衡的性能评估 318
4113　寻找最优的评分阈值 322
4114　综合评估性能 323
412　多类问题 330
413　文献注释 333
414　习题 345
第5章　关联分析：基本概念和算法 357
51　预备知识 358
52　频繁项集的产生 362
521　先验原理 363
522　Apriori算法的频繁项集产生 364
523　候选项集的产生与剪枝 368
524　支持度计数 373
525　计算复杂度 377
53　规则的产生 380
531　基于置信度的剪枝 380
532　Apriori算法中规则的产生 381
533　示例：美国国会投票记录 382
54　频繁项集的紧凑表示 384
541　极大频繁项集 384
542　闭项集 386
*55　其他产生频繁项集的方法 389
*56　FP增长算法 393
561　FP树表示法 394
562　FP增长算法的频繁项集产生 397
57　关联模式的评估 401
571　兴趣度的客观度量 402
572　多个二元变量的度量 414
573　辛普森悖论 416
58　倾斜支持度分布的影响 418
59　文献注释 424
510　习题 438
第6章　关联分析：高级概念 451
61　处理分类属性 451
62　处理连续属性 454
621　基于离散化的方法 454
622　基于统计学的方法 458
623　非离散化方法 460
63　处理概念分层 462
64　序列模式 464
641　预备知识 465
642　序列模式发现 468
* 643　时限约束 473
* 644　可选计数方案 477
65　子图模式 479
651　预备知识 480
652　频繁子图挖掘 483
653　候选生成 487
654　候选剪枝 493
655　支持度计数 493
*66　非频繁模式 493
661　负模式 494
662　负相关模式 495
663　非频繁模式、负模式和负相关模式比较 496
664　挖掘有趣的非频繁模式的技术 498
665　基于挖掘负模式的技术 499
666　基于支持度期望的技术 501
67　文献注释 505
68　习题 510
第7章　聚类分析：基本概念和算法 525
71　概述 528
711　什么是聚类分析 528
712　聚类的不同类型 529
713　簇的不同类型 531
72　K均值 534
721　K均值算法 535
722　K均值：附加的问题 544
723　二分K均值 547
724　K均值和不同的簇类型 548
725　优点与缺点 549
726　K均值作为优化问题 549
73　凝聚层次聚类 554
731　基本凝聚层次聚类算法 555
732　特殊技术 557
733　簇邻近度的Lance-Williams公式 562
734　层次聚类的主要问题 563
735　离群点 564
736　优点与缺点 565
74　DBSCAN 565
741　传统的密度：基于中心的方法 565
742　DBSCAN算法 567
743　优点与缺点 569
75　簇评估 571
751　概述 571
752　无监督簇评估：使用凝聚度和分离度 574
753　无监督簇评估：使用邻近度矩阵 582
754　层次聚类的无监督评估 585
755　确定正确的簇个数 587
756　聚类趋势 588
757　簇有效性的监督度量 589
758　评估簇有效性度量的显著性 594
759　簇有效性度量的选择 596
76　文献注释 597
77　习题 603
第8章　聚类分析：其他问题与算法 613
81　数据、簇和聚类算法的特性 614
811　示例：比较K均值和DBSCAN 614
812　数据特性 615
813　簇特性 617
814　聚类算法的一般特性 619
82　基于原型的聚类 621
821　模糊聚类 621
822　使用混合模型的聚类 627
823　自组织映射 637
83　基于密度的聚类 644
831　基于网格的聚类 644
832　子空间聚类 648
833　DENCLUE：基于密度聚类的一种基于核的方案 652
84　基于图的聚类 656
841　稀疏化 657
842　最小生成树聚类 658
843　OPOSSUM：使用METIS的稀疏相似度最优划分 659
844　Chameleon：使用动态建模的层次聚类 660
845　谱聚类 666
846　共享最近邻相似度 673
847　Jarvis-Patrick聚类算法 676
848　SNN密度 678
849　基于SNN密度的聚类 679
85　可伸缩的聚类算法 681
851　可伸缩：一般问题和方法 681
852　BIRCH 684
853　CURE 686
86　使用哪种聚类算法 690
87　文献注释 693
88　习题 699
第9章　异常检测 703
91　异常检测问题的特性 705
911　异常的定义 705
912　数据的性质 706
913　如何使用异常检测 707
92　异常检测方法的特性 708
93　统计方法 710
931　使用参数模型 710
932　使用非参数模型 714
933　对正常类和异常类建模 715
934　评估统计意义 717
935　优点与缺点 718
94　基于邻近度的方法 719
941　基于距离的异常分数 719
942　基于密度的异常分数 720
943　基于相对密度的异常分数 722
944　优点与缺点 723
95　基于聚类的方法 724
951　发现异常簇 724
952　发现异常实例 725
953　优点与缺点 728
96　基于重构的方法 728
97　单类分类 732
971　核函数的使用 733
972　原点技巧 734
973　优点与缺点 738
98　信息论方法 738
99　异常检测评估 740
910　文献注释 742
911　习题 749
第10章　避免错误发现 755
101　预备知识：统计检验 756
1011　显著性检验 756
1012　假设检验 761
1013　多重假设检验 767
1014　统计检验中的陷阱 776
102　对零分布和替代分布建模 778
1021　生成合成数据集 781
1022　随机化类标 782
1023　实例重采样 782
1024　对检验统计量的分布建模 783
103　分类问题的统计检验 783
1031　评估分类性能 783
1032　以多重假设检 验处理二分类问题 785
1033　模型选择中的多重假设检验 786
104　关联分析的统计检验 787
1041　使用统计模型 788
1042　使用随机化方法 794
105　聚类分析的统计检验 795
1051　为内部指标生成零分布 796
1052　为外部指标生成零分布 798
1053　富集 798
106　异常检测的统计检验 800
107　文献注释 803
108　习题 808



Contents
1 Introduction 1
11 What Is Data Mining? 4
12 Motivating Challenges 5
13 The Origins of Data Mining 7
14 Data Mining Tasks 9
15 Scope and Organization of the Book 13
16 Bibliographic Notes 15
17 Exercises 21
2 Data 23
21 Types of Data 26
211 Attributes and Measurement 27
212 Types of Data Sets 34
22 Data Quality 42
221 Measurement and Data Collection Issues 42
222 Issues Related to Applications 49
23 Data Preprocessing 50
231 Aggregation 51
232 Sampling 52
233 Dimensionality Reduction 56

自12年前的第1版以来，数据分析领域发生了很大的变化。采集数据和用数据做决策的速率不断提高，采集到的数据数量和种类也在不断增加。事实上，“大数据”这个术语已被用于指代那些可获得的海量、多样的数据集。此外，“数据科学”这个术语也被用于描述一个新兴领域，其中，数据挖掘、机器学习、统计学等诸多领域的工具和技术，被用于从数据（通常是大数据）中提取出可实际应用的见解。
数据的增长为数据分析的各领域创造了大量的机会。其中，有着广泛应用的预测建模领域的发展最引人注目。例如，在神经网络（也称为深度学习）方面取得的最新进展，已经在许多具有挑战性的领域（如图像分类、语音识别以及文本分类和理解）表现出令人瞩目的成果。即使那些发展不是特别显著的领域（例如聚类、关联分析和异常检测等）也在不断前进。这个新版本就是对这些发展的响应。
概述　与第1版相同，本书第2版全面介绍了数据挖掘，方便学生、教师、研究人员和专业人士理解有关概念和技术。本书涵盖的主题包括：数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法，为读者提供将数据挖掘应用于实际问题所需的必要背景。与第1版一样，分类、关联分析和聚类分析都分两章讲述。前面一章（介绍章）讲述基本概念、代表性算法和评估技术，后面一章（高级章）深入讨论高级概念和算法。同第1版一样，这样做的目的是使读者透彻地理解数据挖掘的基础知识，同时论述更多重要的高级主题。由于这种安排，本书既可用作教材也可用作参考书。
为了帮助读者更好地理解书中讲述的概念，我们提供了大量的示例、图表和习题，并在网上公开了原有习题的答案。除了第10章的新习题，其余习题与第1版的基本一致。教师可以通过网络获取各章的新习题及其答案。对更高级的主题、重要的历史文献和当前趋势感兴趣的读者，可以在每一章结尾找到文献注释，本版对这部分内容做了较大的更新。此外，还提供了一个覆盖本书所有主题的索引。
第2版的新内容　内容上主要的更新是与分类相关的两章内容（第3章和第4章）。第3章仍使用决策树分类器进行讲解，但对适用于各种分类方法的主题讨论进行了大量的扩充，这些主题包括：过拟合、欠拟合、训练规模的影响、模型复杂度、模型选择以及模型评估中常见的缺陷等。第4章的每一节几乎都进行了重大更新，着重扩展了贝叶斯网络、支持向量机和人工神经网络的内容。对深度网络，我们单独增加了一节来介绍该领域当前的发展。我们还更新了411节“类不平衡问题”中有关评估方法的讨论。
关联分析内容的改进则更具体。我们对关联模式评估部分（第5章）以及序列和图形挖掘部分（第6章）进行了全面修订。对聚类分析的修订也很具体。在聚类分析的介绍章（第7章）增添了K均值初始化技术并更新了簇评估的讨论。聚类分析的高级章（第8章）新添了关于谱图聚类的内容。对异常检测部分也进行了大量的修订和扩展。我们保留并更新了现有方法，如统计学、基于最近邻/密度方法和基于聚类方法，同时介绍了基于重构的方法、单类分类和信息论方法。基于重构的方法通过深度学习范畴中的自编码网络进行阐述。关于数据的第2章也进行了更新，更新内容包括对互信息的讨论和基于核技术的讨论。
第10章讨论了如何避免错误发现并产生正确的结果，这一章的内容是全新的并且在当前关于数据挖掘的教科书中也是新颖的。该章讨论了关于避免虚假结果的统计概念（统计显著性、p值、错误发现率、置换检验等），这些是对其他章中相关内容的补充，然后在介绍数据挖掘技术的内容中对这些概念进行了阐述。这一章还强调了对数据分析结果的有效性和可重复性的关注。新增的最后一章，是认识到这个主题的重要性后的产物，同时也是对“在分析数据时需要对相关领域有更深入的理解”这一观点的认可。
本版纸书删除了数据探索章节以及附录，但仍将其保留在网上。本版附录对大数据环境下的可伸缩性进行了简要讨论。
致教师　作为一本教材，本书广泛适用于高年级本科生和研究生教学。由于学习这门课程的学生背景不同，他们可能不具备广博的统计学和数据库知识，因此本书只要求最低限度的预备知识。数据库知识不是必需的，但我们假定读者有一定的统计学或数学背景，这些背景会让他们更容易学习某些内容。与以前一样，本书或者更确切地说是讨论主要数据挖掘主题的各章，都尽可能自成一体。因此，这些主题的讲授次序相当灵活。其中第2章、第3章、第5章、第7章和第9章是核心内容。对于第10章，建议至少给出粗略的介绍，以在学生解释他们的数据分析结果时引起一些注意。尽管应先介绍数据（第2章），但可以按任意顺序来讲授基本分类（第3章）、关联分析（第5章）和聚类分析（第7章）。由于异常检测（第9章）与分类（第3章）和聚类分析（第7章）具备先后关系，所以后两章应先于第9章进行讲解。同时，可以根据时间安排和兴趣，从高级分类、关联分析和聚类分析章节（第4章、第6章、第8章）中选择多种主题进行讲解。我们还建议通过数据挖掘中的项目或实践练习来强化听课效果，虽然它们要花费一些时间，但这种实践作业可以大