本书从算法的角度介绍数据挖掘所使用的主要原理与技术。为了更好地理解数据挖掘技术如何用于各种类型的数据,研究这些原理与技术是至关重要的。
本书所涵盖的主题包括:数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法,为读者提供将数据挖掘应用于实际问题所需的必要背景以及使用方法。
自12年前的第1版以来,数据分析领域发生了很大的变化。采集数据和用数据做决策的速率不断提高,采集到的数据数量和种类也在不断增加。事实上,“大数据”这个术语已被用于指代那些可获得的海量、多样的数据集。此外,“数据科学”这个术语也被用于描述一个新兴领域,其中,数据挖掘、机器学习、统计学等诸多领域的工具和技术,被用于从数据(通常是大数据)中提取出可实际应用的见解。
数据的增长为数据分析的各领域创造了大量的机会。其中,有着广泛应用的预测建模领域的发展最引人注目。例如,在神经网络(也称为深度学习)方面取得的最新进展,已经在许多具有挑战性的领域(如图像分类、语音识别以及文本分类和理解)表现出令人瞩目的成果。即使那些发展不是特别显著的领域(例如聚类、关联分析和异常检测等)也在不断前进。这个新版本就是对这些发展的响应。
概述 与第1版相同,本书第2版全面介绍了数据挖掘,方便学生、教师、研究人员和专业人士理解有关概念和技术。本书涵盖的主题包括:数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法,为读者提供将数据挖掘应用于实际问题所需的必要背景。与第1版一样,分类、关联分析和聚类分析都分两章讲述。前面一章(介绍章)讲述基本概念、代表性算法和评估技术,后面一章(高级章)深入讨论高级概念和算法。同第1版一样,这样做的目的是使读者透彻地理解数据挖掘的基础知识,同时论述更多重要的高级主题。由于这种安排,本书既可用作教材也可用作参考书。
为了帮助读者更好地理解书中讲述的概念,我们提供了大量的示例、图表和习题,并在网上公开了原有习题的答案。除了第10章的新习题,其余习题与第1版的基本一致。教师可以通过网络获取各章的新习题及其答案。对更高级的主题、重要的历史文献和当前趋势感兴趣的读者,可以在每一章结尾找到文献注释,本版对这部分内容做了较大的更新。此外,还提供了一个覆盖本书所有主题的索引。
第2版的新内容 内容上主要的更新是与分类相关的两章内容(第3章和第4章)。第3章仍使用决策树分类器进行讲解,但对适用于各种分类方法的主题讨论进行了大量的扩充,这些主题包括:过拟合、欠拟合、训练规模的影响、模型复杂度、模型选择以及模型评估中常见的缺陷等。第4章的每一节几乎都进行了重大更新,着重扩展了贝叶斯网络、支持向量机和人工神经网络的内容。对深度网络,我们单独增加了一节来介绍该领域当前的发展。我们还更新了4.11节“类不平衡问题”中有关评估方法的讨论。
关联分析内容的改进则更具体。我们对关联模式评估部分(第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章)中选择多种主题进行讲解。我们还建议通过数据挖掘中的项目或实践练习来强化听课效果,虽然它们要花费一些时间,但这种实践作业可以大
陈封能(Pang-Ning Tan) 密歇根州立大学计算机科学与工程系教授,主要研究方向是数据挖掘、数据库系统、网络空间安全、网络分析等。
第1章 绪论1
1.1 什么是数据挖掘4
1.2 数据挖掘要解决的问题5
1.3 数据挖掘的起源7
1.4 数据挖掘任务9
1.5 本书组织结构13
1.6 文献注释15
1.7 习题21
第2章 数据23
2.1 数据类型26
2.1.1 属性与度量27
2.1.2 数据集的类型34
2.2 数据质量42
2.2.1 测量和数据收集问题42
2.2.2 关于应用的问题49
2.3 数据预处理50
2.3.1 聚集51
2.3.2 抽样52
2.3.3 维归约56
2.3.4 特征子集选择58
2.3.5 特征创建61
2.3.6 离散化和二元化63
2.3.7 变量变换69
2.4 相似性和相异性的度量71
2.4.1 基础72
2.4.2 简单属性之间的相似度和相异度74
2.4.3 数据对象之间的相异度76
2.4.4 数据对象之间的相似度78
2.4.5 邻近度度量的例子79
2.4.6 互信息88
* 2.4.7 核函数90
* 2.4.8 Bregman散度94
2.4.9 邻近度计算问题96
2.4.10 选择正确的邻近度度量98
2.5 文献注释100
2.6 习题105
第3章 分类:基本概念和技术113
3.1 基本概念114
3.2 一般的分类框架117
3.3 决策树分类器119
3.3.1 构建决策树的基本算法121
3.3.2 表示属性测试条件的方法124
3.3.3 选择属性测试条件的方法127
3.3.4 决策树归纳算法136
3.3.5 示例:Web机器人检测138
3.3.6 决策树分类器的特征140
3.4 模型的过拟147
3.5 模型选择156
3.5.1 验证集应用156
3.5.2 模型复杂度合并157
3.5.3 统计范围估计162
3.5.4 决策树的模型选择162
3.6 模型评估164
3.6.1 保持方法165
3.6.2 交叉验证165
3.7 超参数的使用168
3.7.1 超参数选择168
3.7.2 嵌套交叉验证170
3.8 模型选择和评估中的陷阱172
3.8.1 训练集和测试集之间的重叠172
3.8.2 使用验证错误率作为泛化错误率
*3.9 模型比较173
3.9.1 估计准确率的置信区间174
3.9.2 比较两个模型的性能175
3.10 文献注释176
3.11 习题185
第4章 分类:其他技术193
4.1 分类器的种类193
4.2 基于规则的分类器195
4.2.1 基于规则的分类器原理197
4.2.2 规则集的属性198
4.2.3 规则提取的直接方法199
4.2.4 规则提取的间接方法204
4.2.5 基于规则的分类器的特点206
4.3 最近邻分类器208
4.3.1 算法209
4.3.2 最近邻分类器的特点210
4.4 朴素贝叶斯分类器212
4.4.1 概率论基础213
4.4.2 朴素贝叶斯假设218
4.5 贝叶斯网络227
4.5.1 图表示227
4.5.2 推理与学习233
4.5.3 贝叶斯网络的特点242
4.6 logistic回归243
4.6.1 logistic回归用作广义线性模型244
4.6.2 学习模型参数245
4.6.3 logistic回归模型的特点248
4.7 人工神经网络249
4.7.1 感知机250
4.7.2 多层神经网络254
4.7.3 人工神经网络的特点261
4.8 深度学习262
4.8.1 使用协同损失函数263
4.8.2 使用响应激活函数266
4.8.3 正则化268
4.8.4 模型参数的初始化271
4.8.5 深度学习的特点275
4.9 支持向量机276
4.9.1 分离超平面的边缘276
4.9.2 线性SVM278
4.9.3 软边缘SVM284
4.9.4 非线性SVM290
4.9.5 SVM的特点294
4.10 组合方法296
4.10.1 组合方法的基本原理297
4.10.2 构建组合分类器的方法297
4.10.3 偏置–方差分解300
4.10.4 装袋302
4.10.5 提升305
4.10.6 随机森林310
4.10.7 组合方法的实验比较312
4.11 类不平衡问题313
4.11.1 类不平衡的分类器构建314
4.11.2 带类不平衡的性能评估318
4.11.3 寻找最优的评分阈值322
4.11.4 综合评估性能323
4.12 多类问题330
4.13 文献注释333
4.14 习题345
第5章 关联分析:基本概念和算法357
5.1 预备知识358
5.2 频繁项集的产生362
5.2.1 先验原理363
5.2.2 Apriori算法的频繁项集产生364
5.2.3 候选项集的产生与剪枝368
5.2.4 支持度计数373
5.2.5 计算复杂度377
5.3 规则的产生380
5.3.1 基于置信度的剪枝380
5.3.2 Apriori算法中规则的产生381
5.3.3 示例:美国国会投票记录382
5.4 频繁项集的紧凑表示384
5.4.1 极大频繁项集384
5.4.2 闭项集386
*5.5 其他产生频繁项集的方法389
*5.6 FP增长算法393
5.6.1 FP树表示法394
5.6.2 FP增长算法的频繁项集产生397
5.7 关联模式的评估401
5.7.1 兴趣度的客观度量402
5.7.2 多个二元变量的度量414
5.7.3 辛普森悖论416
5.8 倾斜支持度分布的影响418
5.9 文献注释424
5.10 习题438
第6章 关联分析:高级概念451
6.1 处理分类属性451
6.2 处理连续属性454
6.2.1 基于离散化的方法454
6.2.2 基于统计学的方法458
6.2.3 非离散化方法460
6.3 处理概念分层462
6.4 序列模式464
6.4.1 预备知识465
6.4.2 序列模式发现468
* 6.4.3 时限约束473
* 6.4.4 可选计数方案477
6.5 子图模式479
6.5.1 预备知识480
6.5.2 频繁子图挖掘483
6.5.3 候选生成487
6.5.4 候选剪枝493
6.5.5 支持度计数493
*6.6 非频繁模式493
6.6.1 负模式494
6.6.2 负相关模式495
6.6.3 非频繁模式、负模式和负相关模式比较496
6.6.4 挖掘有趣的非频繁模式的技术498
6.6.5 基于挖掘负模式的技术499
6.6.6 基于支持度期望的技术501
6.7 文献注释505
6.8 习题510
第7章 聚类分析:基本概念和算法525
7.1 概述528
7.1.1 什么是聚类分析528
7.1.2 聚类的不同类型529
7.1.3 簇的不同类型531
7.2 K均值534
7.2.1 K均值算法535
7.2.2 K均值:附加的问题544
7.2.3 二分K均值547
7.2.4 K均值和不同的簇类型548
7.2.5 优点与缺点549
7.2.6 K均值作为优化问题549
7.3 凝聚层次聚类554
7.3.1 基本凝聚层次聚类算法555
7.3.2 特殊技术557
7.3.3 簇邻近度的Lance-Williams公式562
7.3.4 层次聚类的主要问题563
7.3.5 离群点564
7.3.6 优点与缺点565
7.4 DBSCAN565
7.4.1 传统的密度:基于中心的方法565
7.4.2 DBSCAN算法567
7.4.3 优点与缺点569
7.5 簇评估571
7.5.1 概述571
7.5.2 无监督簇评估:使用凝聚度和分离度574
7.5.3 无监督簇评估:使用邻近度矩阵582
7.5.4 层次聚类的无监督评估585
7.5.5 确定正确的簇个数587
7.5.6 聚类趋势588
7.5.7 簇有效性的监督度量589
7.5.8 评估簇有效性度量的显著性594
7.5.9 簇有效性度量的选择596
7.6 文献注释597
7.7 习题603
第8章 聚类分析:其他问题与算法613
8.1 数据、簇和聚类算法的特性614
8.1.1 示例:比较K均值和DBSCAN614
8.1.2 数据特性615
8.1.3 簇特性617
8.1.4 聚类算法的一般特性619
8.2 基于原型的聚类621
8.2.1 模糊聚类621
8.2.2 使用混合模型的聚类627
8.2.3 自组织映射637
8.3 基于密度的聚类644
8.3.1 基于网格的聚类644
8.3.2 子空间聚类648
8.3.3 DENCLUE:基于密度聚类的一种基于核的方案652
8.4 基于图的聚类656
8.4.1 稀疏化657
8.4.2 最小生成树聚类658
8.4.3 OPOSSUM:使用METIS的稀疏相似度最优划分659
8.4.4 Chameleon:使用动态建模的层次聚类660
8.4.5 谱聚类666
8.4.6 共享最近邻相似度673
8.4.7 Jarvis-Patrick聚类算法676
8.4.8 SNN密度678
8.4.9 基于SNN密度的聚类679
8.5 可伸缩的聚类算法681
8.5.1 可伸缩:一般问题和方法681
8.5.2 BIRCH684
8.5.3 CURE686
8.6 使用哪种聚类算法690
8.7 文献注释693
8.8 习题699
第9章 异常检测703
9.1 异常检测问题的特性705
9.1.1 异常的定义705
9.1.2 数据的性质706
9.1.3 如何使用异常检测707
9.2 异常检测方法的特性708
9.3 统计方法710
9.3.1 使用参数模型710
9.3.2 使用非参数模型714
9.3.3 对正常类和异常类建模715
9.3.4 评估统计意义717
9.3.5 优点与缺点718
9.4 基于邻近度的方法719
9.4.1 基于距离的异常分数719
9.4.2 基于密度的异常分数720
9.4.3 基于相对密度的异常分数722
9.4.4 优点与缺点723
9.5 基于聚类的方法724
9.5.1 发现异常簇724
9.5.2 发现异常实例725
9.5.3 优点与缺点728
9.6 基于重构的方法728
9.7 单类分类732
9.7.1 核函数的使用733
9.7.2 原点技巧734
9.7.3 优点与缺点738
9.8 信息论方法738
9.9 异常检测评估740
9.10 文献注释742
9.11 习题749
第10章 避免错误发现755
10.1 预备知识:统计检验756
10.1.1 显著性检验756
10.1.2 假设检验761
10.1.3 多重假设检验767
10.1.4 统计检验中的陷阱776
10.2 对零分布和替代分布建模778
10.2.1 生成合成数据集781
10.2.2 随机化类标782
10.2.3 实例重采样782
10.2.4 对检验统计量的分布建模783
10.3 分类问题的统计检验783
10.3.1 评估分类性能783
10.3.2 以多重假设检 验处理二分类问题785
10.3.3 模型选择中的多重假设检验786
10.4 关联分析的统计检验787
10.4.1 使用统计模型788
10.4.2 使用随机化方法794
10.5 聚类分析的统计检验795
10.5.1 为内部指标生成零分布796
10.5.2 为外部指标生成零分布798
10.5.3 富集798
10.6 异常检测的统计检验800
10.7 文献注释803
10.8 习题808
Contents
1 Introduction1
1.1 What Is Data Mining?4
1.2 Motivating Challenges5
1.3 The Origins of Data Mining7
1.4 Data Mining Tasks9
1.5 Scope and Organization of the Book13
1.6 Bibliographic Notes15
1.7 Exercises21
2 Data23
2.1 Types of Data26
2.1.1 Attributes and Measurement27
2.1.2 Types of Data Sets34
2.2 Data Quality42
2.2.1 Measurement and Data Collection Issues42
2.2.2 Issues Related to Applications49
2.3 Data Preprocessing50
2.3.1 Aggregation51
2.3.2 Sampling52
2.3.3 Dimensionality Reduction56