本书从算法的角度介绍数据挖掘所使用的主要原理与技术。为了更好地理解数据挖掘技术如何用于各种类型的数据，研究这些原理与技术是至关重要的。
本书所涵盖的主题包括：数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法，为读者提供将数据挖掘应用于实际问题所需的必要背景以及使用方法。
无
自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章）中选择多种主题进行讲解。我们还建议通过数据挖掘中的项目或实践练习来强化听课效果，虽然它们要花费一些时间，但这种实践作业可以大大提高课程的价值。
支持材料 本书的读者可以在http://www-users.cs.umn.edu/~kumar/dmbook/上获取相关材料：
课程幻灯片。
学生项目建议。
数据挖掘资源，如数据挖掘算法和数据集。
联机指南，使用实际的数据集和数据分析软件，为本书介绍的部分数据挖掘技术提供例子讲解。
其他支持材料（包括习题答案）只向采纳本书做教材的教师提供。读者可通过邮箱dmbook@cs.umn.edu将意见和建议以及勘误发给作者。
致谢 许多人都为本书的出版做出了贡献。首先向家人表示感谢，这本书是献给他们的。正是有他们的耐心和支持，本书才能顺利完成。
感谢明尼苏达大学和密歇根州立大学数据挖掘小组的学生所做的贡献。Eui-Hong(Sam) Han和Mahesh Joshi帮助我们准备了最初的数据挖掘课程。他们编制的某些习题和演示幻灯片已经收录在本书及教辅幻灯片中。小组中的其他学生也为本书的初稿提出建议或以各种方式做出贡献，他们是：Shyam Boriah、Haibin Cheng、Varun Chandola、Eric Eilertson、Levent Ertz、Jing Gao、Rohit Gupta、Sridhar Iyer、Jung-Eun Lee、Benjamin Mayer、Aysel Ozgur、Uygar Oztekin、Gaurav Pandey、Kashif Riaz、Jerry Scripps、Gyorgy Simon、Hui Xiong、Jieping Ye和Pusheng Zhang。还要感谢明尼苏达大学和密歇根州立大学选修数据挖掘课程的学生，他们使用了本书的初稿，并提供了极富价值的反馈。特别感谢Bernardo Craemer、Arifin Ruslim、Jamshid Vayghan和Yu Wei的有益建议。
Joydeep Ghosh（得克萨斯大学）和Sanjay Ranka（佛罗里达大学）试用了本书的初稿。我们也直接从得克萨斯大学下列学生那里获得了许多有用的建议：Pankaj Adhikari、Rajiv Bhatia、Frederic Bosche、Arindam Chakraborty、Meghana Deodhar、Chris Everson、David Gardner、Saad Godil、Todd Hay、Clint Jones、Ajay Joshi、Joonsoo Lee、Yue Luo、Anuj Nanavati、Tyler Olsen、Sunyoung Park、Aashish Phansalkar、Geoff Prewett、Michael Ryoo、Daryl Shannon 和Mei Yang。
Ronald Kostoff（ONR）阅读了聚类部分的初稿，并提出了许多建议。George Karypis对创建索引提供了宝贵的帮助。Irene Moulitsas提供了LaTeX支持，并审阅了一些附录。Musetta Steinbach发现了图中的一些错误。
感谢明尼苏达大学和密歇根州立大学的同事，他们帮助创建了良好的数据挖掘研究环境。他们是：Arindam Banerjee、Dan Boley、Joyce Chai、Anil Jain、Ravi Janardan、Rong Jin、George Karypis、Claudia Neuhauser、Haesun Park、William F. Punch、Gyrgy Simon、Shashi Shekhar和Jaideep Srivastava。还要向我们的数据挖掘项目的合作者表示谢意，他们是：Ramesh Agrawal、Maneesh Bhargava、Steve Cannon、Alok Choudhary、Imme Ebert-Uphoff、Auroop Ganguly、Piet C. de Groen、Fran Hill、Yongdae Kim、Steve Klooster、Kerry Long、Nihar Mahapatra、Rama Nemani、Nikunj Oza、Chris Potter、Lisiane Pruinelli、Nagiza Samatova、Jonathan Shapiro、Kevin Silverstein、Brian Van Ness、Bonnie Westra、Nevin Young和Zhi-Li Zhang。
明尼苏达大学和密歇根州立大学的计算机科学与工程系为本书写作及研究提供了计算资源和支持环境。ARDA、ARL、ARO、DOE、NASA和NSF等机构为本书作者提供了研究资助。特别是Kamal Abdali、Mitra Basu、Dick Brackney、Jagdish Chandra、Joe Coughlan、Michael Coyle、Stephen Davis、Frederica Darema、Richard Hirsch、Chandrika Kamath、Tsengdar Lee、Raju Namburu、N. Radhakrishnan、James Sidoran、Sylvia Spengler、Bhavani Thuraisingham、Walt Tiernin、Maria Zemankova、Aidong Zhang和Xiaodong Zhang，他们有力地支持了我们的数据挖掘和高性能计算研究。
与培生出版集团的工作人员的合作令人愉快。具体来说，我们要感谢Matt Goldstein、Kathy Smith、Carole Snyder和Joyce Wells。还要感谢George Nichols帮助绘图，Paul Anagnostopoulos提供LaTeX支持。
感谢培生邀请的审稿人：Leman Akoglu（卡内基梅隆大学）、Chien-Chung Chan（阿克伦大学）、Zhengxin Chen（内布拉斯加大学奥马哈分校）、Chris Clifton（普度大学）、Joydeep Ghosh（得克萨斯大学奥斯汀分校）、Nazli Goharian（伊利诺伊理工学院）、J. Michael Hardin（阿拉巴马大学）、Jingrui He（亚利桑那州立大学）、James Hearne（西华盛顿大学）、Hillol Kargupta（马里兰大学巴尔的摩县分校和Agnik公司）、Eamonn Keogh（加利福尼亚大学河滨分校）、Bing Liu（伊利诺伊大学芝加哥分校）、Mariofanna Milanova（阿肯色大学小石城分校）、Srinivasan Parthasarathy（俄亥俄州立大学）、Zbigniew W.Ras（北卡罗来纳大学夏洛特分校）、Xintao Wu（北卡罗来纳大学夏洛特分校）和Mohammed J.Zaki（伦斯勒理工学院）。
自本书第1版出版以来，我们收到了许多指出错别字和其他各种问题的读者和学生的意见。在此无法列举所有人的名字，但非常感谢他们的意见，相关问题已在第2版中予以修正。
计算机\数据库
本书从算法的角度介绍数据挖掘所使用的主要原理与技术。为了更好地理解数据挖掘技术如何用于各种类型的数据，研究这些原理与技术是至关重要的。
本书所涵盖的主题包括：数据预处理、预测建模、关联分析、聚类分析、异常检测和避免错误发现。通过介绍每个主题的基本概念和算法，为读者提供将数据挖掘应用于实际问题所需的必要背景以及方法。
本书特点
·针对每个主题，从基本概念和算法的角度展开讲解。其中，分类、关联分析、聚类分析更是切割成介绍章和高级章：介绍章覆盖基本概念、代表性算法和评估技术内容；高级章深入讨论高级概念和算法。
·避免错误发现主题更是数据挖掘相关教科书中少见的，该主题讨论了关于避免虚假结果的统计概念，作为其他章节的补充，强调对数据分析结果的有效性和可重复性的关注。
·基础内容和高级内容渐进的巧妙安排，使读者能透彻地理解数据挖掘的基础，同时掌握更多重要的高级技巧。
[美]陈封能（Pang-Ning Tan）迈克尔·斯坦巴赫（Michael Steinbach）阿努吉·卡帕坦（Anuj Karpatne）维平·库玛尔（Vipin Kumar）著：陈封能（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 线性SVM 278
4.9.3 软边缘SVM 284
4.9.4 非线性SVM 290
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 DBSCAN 565
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均值和DBSCAN 614
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 BIRCH 684
8.5.3 CURE 686
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 Introduction 1
1.1 What Is Data Mining? 4
1.2 Motivating Challenges 5
1.3 The Origins of Data Mining 7
1.4 Data Mining Tasks 9
1.5 Scope and Organization of the Book 13
1.6 Bibliographic Notes 15
1.7 Exercises 21
2 Data 23
2.1 Types of Data 26
2.1.1 Attributes and Measurement 27
2.1.2 Types of Data Sets 34
2.2 Data Quality 42
2.2.1 Measurement and Data Collection Issues 42
2.2.2 Issues Related to Applications 49
2.3 Data Preprocessing 50
2.3.1 Aggregation 51
2.3.2 Sampling 52
2.3.3 Dimensionality Reduction 56
2.3.4 Feature Subset Selection 58
2.3.5 Feature Creation 61
2.3.6 Discretization and Binarization 63
2.3.7 Variable Transformation 69
2.4 Measures of Similarity and Dissimilarity 71
2.4.1 Basics 72
2.4.2 Similarity and Dissimilarity between Simple Attributes . 74
2.4.3 Dissimilarities between Data Objects 76
2.4.4 Similarities between Data Objects 78
2.4.5 Examples of Proximity Measures 79
2.4.6 Mutual Information 88
2.4.7 Kernel Functions* 90
2.4.8 Bregman Divergence* 94
2.4.9 Issues in Proximity Calculation 96
2.4.10 Selecting the Right Proximity Measure 98
2.5 Bibliographic Notes 100
2.6 Exercises 105
3 Classiftcation: Basic Concepts and Techniques 113
3.1 Basic Concepts 114
3.2 General Framework for Classi?cation 117
3.3 Decision Tree Classi?er 119
3.3.1 A Basic Algorithm to Build a Decision Tree 121
3.3.2 Methods for Expressing Attribute Test Conditions 124
3.3.3 Measures for Selecting an Attribute Test Condition 127
3.3.4 Algorithm for Decision Tree Induction 136
3.3.5 Example Application: Web Robot Detection 138
3.3.6 Characteristics of Decision Tree Classi?ers 140
3.4 Model Over?tting 147
3.5 Model Selection 156
3.5.1 Using a Validation Set 156
3.5.2 Incorporating Model Complexity 157
3.5.3 Estimating Statistical Bounds 162
3.5.4 Model Selection for Decision Trees 162
3.6 Model Evaluation 164
3.6.1 Holdout Method 165
3.6.2 Cross-Validation 165
3.7 Presence of Hyper-parameters 168
3.7.1 Hyper-parameter Selection 168
3.7.2 Nested Cross-Validation 170
3.8 Pitfalls of Model Selection and Evaluation 172
3.8.1 Overlap between Training and Test Sets 172
3.8.2 Use of Validation Error as Generalization Error 172
3.9 Model Comparison? 173
3.9.1 Estimating the Con?dence Interval for Accuracy 174
3.9.2 Comparing the Performance of Two Models 175
3.10 Bibliographic Notes 176
3.11 Exercises 185
4 Classiftcation: Alternative Techniques 193
4.1 Types of Classi?ers 193
4.2 Rule-Based Classi?er 195
4.2.1 How a Rule-Based Classi?er Works 197
4.2.2 Properties of a Rule Set 198
4.2.3 Direct Methods for Rule Extraction 199
4.2.4 Indirect Methods for Rule Extraction 204
4.2.5 Characteristics of Rule-Based Classi?ers 206
4.3 Nearest Neighbor Classi?ers 208
4.3.1 Algorithm 209
4.3.2 Characteristics of Nearest Neighbor Classi?ers 210
4.4 Na¨ive Bayes Classi?er 212
4.4.1 Basics of Probability Theory 213
4.4.2 Na¨ive Bayes Assumption 218
4.5 Bayesian Networks 227
4.5.1 Graphical Representation 227
4.5.2 Inference and Learning 233
4.5.3 Characteristics of Bayesian Networks 242
4.6 Logistic Regression 243
4.6.1 Logistic Regression as a Generalized Linear Model 244
4.6.2 Learning Model Parameters 245
4.6.3 Characteristics of Logistic Regression 248
4.7 Arti?cial Neural Network (ANN) 249
4.7.1 Perceptron 250
4.7.2 Multi-layer Neural Network 254
4.7.3 Characteristics of ANN 261
4.8 Deep Learning 262
4.8.1 Using Synergistic Loss Functions 263
4.8.2 Using Responsive Activation Functions 266
4.8.3 Regularization 268
4.8.4 Initialization of Model Parameters 271
4.8.5 Characteristics of Deep Learning 275
4.9 Support Vector Machine (SVM) 276
4.9.1 Margin of a Separating Hyperplane 276
4.9.2 Linear SVM 278
4.9.3 Soft-margin SVM 284
4.9.4 Nonlinear SVM 290
4.9.5 Characteristics of SVM 294
4.10 Ensemble Methods 296
4.10.1 Rationale for Ensemble Method 297
4.10.2 Methods for Constructing an Ensemble Classi?er 297
4.10.3 Bias-Variance Decomposition 300
4.10.4 Bagging 302
4.10.5 Boosting 305
4.10.6 Random Forests 310
4.10.7 Empirical Comparison among Ensemble Methods 312
4.11 Class Imbalance Problem 313
4.11.1 Building Classi?ers with Class Imbalance 314
4.11.2 Evaluating Performance with Class Imbalance 318
4.11.3 Finding an Optimal Score Threshold 322
4.11.4 Aggregate Evaluation of Performance 323
4.12 Multiclass Problem 330
4.13 Bibliographic Notes 333
4.14 Exercises 345
5 Association Analysis: Basic Concepts and Algorithms 357
5.1 Preliminaries 358
5.2 Frequent Itemset Generation 362
5.2.1 The Apriori Principle 363
5.2.2 Frequent Itemset Generation in the Apriori Algorithm . 364
5.2.3 Candidate Generation and Pruning 368
5.2.4 Support Counting 373
5.2.5 Computational Complexity 377
5.3 Rule Generation 380
5.3.1 Con?dence-Based Pruning 380
5.3.2 Rule Generation in Apriori Algorithm 381
5.3.3 An Example: Congressional Voting Records 382
5.4 Compact Representation of Frequent Itemsets 384
5.4.1 Maximal Frequent Itemsets 384
5.4.2 Closed Itemsets 386
5.5 Alternative Methods for Generating Frequent Itemsets* 389
5.6 FP-Growth Algorithm* 393
5.6.1 FP-Tree Representation 394
5.6.2 Frequent Itemset Generation in FP-Growth Algorithm . 397
5.7 Evaluation of Association Patterns 401
5.7.1 Objective Measures of Interestingness 402
5.7.2 Measures beyond Pairs of Binary Variables 414
5.7.3 Simpson’s Paradox 416
5.8 E?ect of Skewed Support Distribution 418
5.9 Bibliographic Notes 424
5.10 Exercises 438
6 Association Analysis: Advanced Concepts 451
6.1 Handling Categorical Attributes 451
6.2 Handling Continuous Attributes 454
6.2.1 Discretization-Based Methods 454
6.2.2 Statistics-Based Methods 458
6.2.3 Non-discretization Methods 460
6.3 Handling a Concept Hierarchy 462
6.4 Sequential Patterns 464
6.4.1 Preliminaries 465
6.4.2 Sequential Pattern Discovery 468
6.4.3 Timing Constraints? 473
6.4.4 Alternative Counting Schemes? 477
6.5 Subgraph Patterns 479
6.5.1 Preliminaries 480
6.5.2 Frequent Subgraph Mining 483
6.5.3 Candidate Generation 487
6.5.4 Candidate Pruning 493
6.5.5 Support Counting 493
6.6 Infrequent Patterns? 493
6.6.1 Negative Patterns 494
6.6.2 Negatively Correlated Patterns 495
6.6.3 Comparisons among Infrequent Patterns, Negative Patterns, and Negatively Correlated Patterns 496
6.6.4 Techniques for Mining Interesting Infrequent Patterns . 498
6.6.5 Techniques Based on Mining Negative Patterns 499
6.6.6 Techniques Based on Support Expectation 501
6.7 Bibliographic Notes 505
6.8 Exercises 510
7 Cluster Analysis: Basic Concepts and Algorithms 525
7.1 Overview 528
7.1.1 What Is Cluster Analysis? 528
7.1.2 Di?erent Types of Clusterings 529
7.1.3 Di?erent Types of Clusters 531
7.2 K-means 534
7.2.1 The Basic K-means Algorithm 535
7.2.2 K-means: Additional Issues 544
7.2.3 Bisecting K-means 547
7.2.4 K-means and Di?erent Types of Clusters 548
7.2.5 Strengths and Weaknesses 549
7.2.6 K-means as an Optimization Problem 549
7.3 Agglomerative Hierarchical Clustering 554
7.3.1 Basic Agglomerative Hierarchical Clustering Algorithm 555
7.3.2 Speci?c Techniques 557
7.3.3 The Lance-Williams Formula for Cluster Proximity 562
7.3.4 Key Issues in Hierarchical Clustering 563
7.3.5 Outliers 564
7.3.6 Strengths and Weaknesses 565
7.4 DBSCAN 565
7.4.1 Traditional Density: Center-Based Approach 565
7.4.2 The DBSCAN Algorithm 567
7.4.3 Strengths and Weaknesses 569
7.5 Cluster Evaluation 571
7.5.1 Overview 571
7.5.2 Unsupervised Cluster Evaluation Using Cohesion and Separation 574
7.5.3 Unsupervised Cluster Evaluation Using the Proximity Matrix 582
7.5.4 Unsupervised Evaluation of Hierarchical Clustering 585
7.5.5 Determining the Correct Number of Clusters 587
7.5.6 Clustering Tendency 588
7.5.7 Supervised Measures of Cluster Validity 589
7.5.8 Assessing the Signi?cance of Cluster Validity Measures . 594
7.5.9 Choosing a Cluster Validity Measure 596
7.6 Bibliographic Notes 597
7.7 Exercises 603
8 Cluster Analysis: Additional Issues and Algorithms 613
8.1 Characteristics of Data, Clusters, and Clustering Algorithms . 614
8.1.1 Example: Comparing K-means and DBSCAN 614
8.1.2 Data Characteristics 615
8.1.3 Cluster Characteristics 617
8.1.4 General Characteristics of Clustering Algorithms 619
8.2 Prototype-Based Clustering 621
8.2.1 Fuzzy Clustering 621
8.2.2 Clustering Using Mixture Models 627
8.2.3 Self-Organizing Maps (SOM) 637
8.3 Density-Based Clustering 644
8.3.1 Grid-Based Clustering 644
8.3.2 Subspace Clustering 648
8.3.3 DENCLUE: A Kernel-Based Scheme for Density-Based Clustering 652
8.4 Graph-Based Clustering 656
8.4.1 Sparsi?cation 657
8.4.2 Minimum Spanning Tree (MST) Clustering 658
8.4.3 OPOSSUM: Optimal Partitioning of Sparse Similarities Using METIS 659
8.4.4 Chameleon: Hierarchical Clustering with Dynamic Modeling 660
8.4.5 Spectral Clustering 666
8.4.6 Shared Nearest Neighbor Similarity 673
8.4.7 The Jarvis-Patrick Clustering Algorithm 676
8.4.8 SNN Density 678
8.4.9 SNN Density-Based Clustering 679
8.5 Scalable Clustering Algorithms 681
8.5.1 Scalability: General Issues and Approaches 681
8.5.2 BIRCH 684
8.5.3 CURE 686
8.6 Which Clustering Algorithm? 690
8.7 Bibliographic Notes 693
8.8 Exercises 699
9 Anomaly Detection 703
9.1 Characteristics of Anomaly Detection Problems 705
9.1.1 A De?nition of an Anomaly 705
9.1.2 Nature of Data 706
9.1.3 How Anomaly Detection is Used 707
9.2 Characteristics of Anomaly Detection Methods 708
9.3 Statistical Approaches 710
9.3.1 Using Parametric Models 710
9.3.2 Using Non-parametric Models 714
9.3.3 Modeling Normal and Anomalous Classes 715
9.3.4 Assessing Statistical Signi?cance 717
9.3.5 Strengths and Weaknesses 718
9.4 Proximity-based Approaches 719
9.4.1 Distance-based Anomaly Score 719
9.4.2 Density-based Anomaly Score 720
9.4.3 Relative Density-based Anomaly Score 722
9.4.4 Strengths and Weaknesses 723
9.5 Clustering-based Approaches 724
9.5.1 Finding Anomalous Clusters 724
9.5.2 Finding Anomalous Instances 725
9.5.3 Strengths and Weaknesses 728
9.6 Reconstruction-based Approaches 728
9.7 One-class Classi?cation 732
9.7.1 Use of Kernels 733
9.7.2 The Origin Trick 734
9.7.3 Strengths and Weaknesses 738
9.8 Information Theoretic Approaches 738
9.9 Evaluation of Anomaly Detection 740
9.10 Bibliographic Notes 742
9.11 Exercises 749
10 Avoiding False Discoveries 755
10.1 Preliminaries: Statistical Testing 756
10.1.1 Signi?cance Testing 756
10.1.2 Hypothesis Testing 761
10.1.3 Multiple Hypothesis Testing 767
10.1.4 Pitfalls in Statistical Testing 776
10.2 Modeling Null and Alternative Distributions 778
10.2.1 Generating Synthetic Data Sets 781
10.2.2 Randomizing Class Labels 782
10.2.3 Resampling Instances 782
10.2.4 Modeling the Distribution of the Test Statistic 783
10.3 Statistical Testing for Classi?cation 783
10.3.1 Evaluating Classi?cation Performance 783
10.3.2 Binary Classi?cation as Multiple Hypothesis Testing 785
10.3.3 Multiple Hypothesis Testing in Model Selection 786
10.4 Statistical Testing for Association Analysis 787
10.4.1 Using Statistical Models 788
10.4.2 Using Randomization Methods 794
10.5 Statistical Testing for Cluster Analysis 795
10.5.1 Generating a Null Distribution for Internal Indices 796
10.5.2 Generating a Null Distribution for External Indices 798
10.5.3 Enrichment 798
10.6 Statistical Testing for Anomaly Detection 800
10.7 Bibliographic Notes 803
10.8 Exercises 808
