正版 数据挖掘导论(完整版)/图灵计算机科学丛书

目 录



第 1章 绪论 1

1.1 什么是数据挖掘 2

1.2 数据挖掘要解决的问题 2

1.3 数据挖掘的起源 3

1.4 数据挖掘任务 4

1.5 本书的内容与组织 7

文献注释 7

参考文献 8

习题 10



第 2章 数据 13

2.1 数据类型 14

2.1.1 属性与度量 15

2.1.2 数据集的类型 18

2.2 数据质量 22

2.2.1 测量和数据收集问题 22

2.2.2 关于应用的问题 26

2.3 数据预处理 27

2.3.1 聚集 27

2.3.2 抽样 28

2.3.3 维归约 30

2.3.4 特征子集选择 31

2.3.5 特征创建 33

2.3.6 离散化和二元化 34

2.3.7 变量变换 38

2.4 相似性和相异性的度量 38

2.4.1 基础 39

2.4.2 简单属性之间的相似度和相异度 40

2.4.3 数据对象之间的相异度 41

2.4.4 数据对象之间的相似度 43

2.4.5 邻近性度量的例子 43

2.4.6 邻近度计算问题 48

2.4.7 选取正确的邻近性度量 50

文献注释 50

参考文献 52

习题 53



第3章 探索数据 59

3.1 鸢尾花数据集 59

3.2 汇总统计 60

3.2.1 频率和众数 60

3.2.2 百分位数 61

3.2.3 位置度量：均值和中位数 61

3.2.4 散布度量：极差和方差 62

3.2.5 多元汇总统计 63

3.2.6 汇总数据的其他方法 64

3.3 可视化 64

3.3.1 可视化的动机 64

3.3.2 一般概念 65

3.3.3 技术 67

3.3.4 可视化高维数据 75

3.3.5 注意事项 79

3.4 OLAP和多维数据分析 79

3.4.1 用多维数组表示鸢尾花数据 80

3.4.2 多维数据：一般情况 81

3.4.3 分析多维数据 82

3.4.4 关于多维数据分析的后评述 84

文献注释 84

参考文献 85

习题 86



第4章 分类：基本概念、决策树与模型评估 89

4.1 预备知识 89

4.2 解决分类问题的一般方法 90

4.3 决策树归纳 92

4.3.1 决策树的工作原理 92

4.3.2 如何建立决策树 93

4.3.3 表示属性测试条件的方法 95

4.3.4 选择划分的度量 96

4.3.5 决策树归纳算法 101

4.3.6 例子：Web机器人检测 102

4.3.7 决策树归纳的特点 103

4.4 模型的过分拟合 106

4.4.1 噪声导致的过分拟合 107

4.4.2 缺乏代表性样本导致的过分拟合 109

4.4.3 过分拟合与多重比较过程 109

4.4.4 泛化误差估计 110

4.4.5 处理决策树归纳中的过分拟合 113

4.5 评估分类器的性能 114

4.5.1 保持方法 114

4.5.2 随机二次抽样 115

4.5.3 交叉验证 115

4.5.4 自助法 115

4.6 比较分类器的方法 116

4.6.1 估计准确度的置信区间 116

4.6.2 比较两个模型的性能 117

4.6.3 比较两种分类法的性能 118

文献注释 118

参考文献 120

习题 122



第5章 分类：其他技术 127

5.1 基于规则的分类器 127

5.1.1 基于规则的分类器的工作原理 128

5.1.2 规则的排序方案 129

5.1.3 如何建立基于规则的分类器 130

5.1.4 规则提取的直接方法 130

5.1.5 规则提取的间接方法 135

5.1.6 基于规则的分类器的特征 136

5.2 近邻分类器 137

5.2.1 算法 138

5.2.2 近邻分类器的特征 138

5.3 贝叶斯分类器 139

5.3.1 贝叶斯定理 139

5.3.2 贝叶斯定理在分类中的应用 140

5.3.3 朴素贝叶斯分类器 141

5.3.4 贝叶斯误差率 145

5.3.5 贝叶斯信念网络 147

5.4 人工神经网络 150

5.4.1 感知器 151

5.4.2 多层人工神经网络 153

5.4.3 人工神经网络的特点 155

5.5 支持向量机 156

5.5.1 边缘超平面 156

5.5.2 线性支持向量机：可分情况 157

5.5.3 线性支持向量机：不可分情况 162

5.5.4 非线性支持向量机 164

5.5.5 支持向量机的特征 168

5.6 组合方法 168

5.6.1 组合方法的基本原理 168

5.6.2 构建组合分类器的方法 169

5.6.3 偏倚-方差分解 171

5.6.4 装袋 173

5.6.5 提升 175

5.6.6 随机森林 178

5.6.7 组合方法的实验比较 179

5.7 不平衡类问题 180

5.7.1 可选度量 180

5.7.2 接受者操作特征曲线 182

5.7.3 代价敏感学习 184

5.7.4 基于抽样的方法 186

5.8 多类问题 187

文献注释 189

参考文献 190

习题 193



第6章 关联分析：基本概念和算法 201

6.1 问题定义 202

6.2 频繁项集的产生 204

6.2.1 先验原理 205

6.2.2 Apriori算法的频繁项集产生 206

6.2.3 候选的产生与剪枝 208

6.2.4 支持度计数 210

6.2.5 计算复杂度 213

6.3 规则产生 215

6.3.1 基于置信度的剪枝 215

6.3.2 Apriori算法中规则的产生 215

6.3.3 例：美国国会投票记录 217

6.4 频繁项集的紧凑表示 217

6.4.1 极大频繁项集 217

6.4.2 闭频繁项集 219

6.5 产生频繁项集的其他方法 221

6.6 FP增长算法 223

6.6.1 FP树表示法 224

6.6.2 FP增长算法的频繁项集产生 225

6.7 关联模式的评估 228

6.7.1 兴趣度的客观度量 228

6.7.2 多个二元变量的度量 235

6.7.3 辛普森悖论 236

6.8 倾斜支持度分布的影响 237

文献注释 240

参考文献 244

习题 250



第7章 关联分析：概念 259

7.1 处理分类属性 259

7.2 处理连续属性 261

7.2.1 基于离散化的方法 261

7.2.2 基于统计学的方法 263

7.2.3 非离散化方法 265

7.3 处理概念分层 266

7.4 序列模式 267

7.4.1 问题描述 267

7.4.2 序列模式发现 269

7.4.3 时限约束 271

7.4.4 可选计数方案 274

7.5 子图模式 275

7.5.1 图与子图 276

7.5.2 频繁子图挖掘 277

7.5.3 类Apriori方法 278

7.5.4 候选产生 279

7.5.5 候选剪枝 282

7.5.6 支持度计数 285

7.6 非频繁模式 285

7.6.1 负模式 285

7.6.2 负相关模式 286

7.6.3 非频繁模式、负模式和负相关模式比较 287

7.6.4 挖掘有趣的非频繁模式的技术 288

7.6.5 基于挖掘负模式的技术 288

7.6.6 基于支持度期望的技术 290

文献注释 292

参考文献 293

习题 295



第8章 聚类分析：基本概念和算法 305

8.1 概述 306

8.1.1 什么是聚类分析 306

8.1.2 不同的聚类类型 307

8.1.3 不同的簇类型 308

8.2 K均值 310

8.2.1 基本K均值算法 310

8.2.2 K均值：附加的问题 315

8.2.3 二分K均值 316

8.2.4 K均值和不同的簇类型 317

8.2.5 优点与缺点 318

8.2.6 K均值作为优化问题 319

8.3 凝聚层次聚类 320

8.3.1 基本凝聚层次聚类算法 321

8.3.2 特殊技术 322

8.3.3 簇邻近度的Lance-Williams公式 325

8.3.4 层次聚类的主要问题 326

8.3.5 优点与缺点 327

8.4 DBSCAN 327

8.4.1 传统的密度：基于中心的方法 327

8.4.2 DBSCAN算法 328

8.4.3 优点与缺点 329

8.5 簇评估 330

8.5.1 概述 332

8.5.2 非监督簇评估：使用凝聚度和分离度 332

8.5.3 非监督簇评估：使用邻近度矩阵 336

8.5.4 层次聚类的非监督评估 338

8.5.5 确定正确的簇个数 339

8.5.6 聚类趋势 339

8.5.7 簇有效性的监督度量 340

8.5.8 评估簇有效性度量的显著性 343

文献注释 344

参考文献 345

习题 347



第9章 聚类分析：其他问题与算法 355

9.1 数据、簇和聚类算法的特性 355

9.1.1 例子：比较K均值和DBSCAN 355

9.1.2 数据特性 356

9.1.3 簇特性 357

9.1.4 聚类算法的一般特性 358

9.2 基于原型的聚类 359

9.2.1 模糊聚类 359

9.2.2 使用混合模型的聚类 362

9.2.3 自组织映射 369

9.3 基于密度的聚类 372

9.3.1 基于网格的聚类 372

9.3.2 子空间聚类 374

9.3.3 DENCLUE：基于密度聚类的一种基于核的方案 377

9.4 基于图的聚类 379

9.4.1 稀疏化 379

9.4.2 小生成树聚类 380

9.4.3 OPOSSUM：使用METIS的稀疏相似度划分 381

9.4.4 Chameleon：使用动态建模的层次聚类 381

9.4.5 共享近邻相似度 385

9.4.6 Jarvis-Patrick聚类算法 387

9.4.7 SNN密度 388

9.4.8 基于SNN密度的聚类 389

9.5 可伸缩的聚类算法 390

9.5.1 可伸缩：一般问题和方法 391

9.5.2 BIRCH 392

9.5.3 CURE 393

9.6 使用哪种聚类算法 395

文献注释 397

参考文献 398

习题 400



第 10章 异常检测 403

10.1 预备知识 404

10.1.1 异常的成因 404

10.1.2 异常检测方法 404

10.1.3 类标号的使用 405

10.1.4 问题 405

10.2 统计方法 406

10.2.1 检测一元正态分布中的离群点 407

10.2.2 多元正态分布的离群点 408

10.2.3 异常检测的混合模型方法 410

10.2.4 优点与缺点 411

10.3 基于邻近度的离群点检测 411

10.4 基于密度的离群点检测 412

10.4.1 使用相对密度的离群点检测 413

10.4.2 优点与缺点 414

10.5 基于聚类的技术 414

10.5.1 评估对象属于簇的程度 415

10.5.2 离群点对初始聚类的影响 416

10.5.3 使用簇的个数 416

10.5.4 优点与缺点 416

文献注释 417

参考文献 418

习题 420



附录A 线性代数 423

附录B 维归约 433

附录C 概率统计 445

附录D 回归 451

附录E 优化 457

陈封能（Pang-Ning Tan），现为密歇根州立大学计算机与工程系助理教授，主要教授数据挖掘、数据库系统等课程。此前，他曾是明尼苏达大学美国陆军高性能计算研究中心副研究员（2002-2003）。
斯坦巴赫（Michael Steinbach），明尼苏达大学计算机与工程系研究员，在读博士。
库玛尔（Vipin Kumar），明尼苏达大学计算机科学与工程系主任，曾任美国陆军高性能计算研究中心主任。他拥有马里兰大学博士学位，是数据挖掘和高性能计算方面的研究人员，IEEE会士。

范明，郑州大学信息工程学院教授，中国计算机学会数据库专业委员会委员、人工智能与模式识别专业委员会委员，长期从事计算机软件与理论教学和研究。先后发表论史40余篇。
范宏建 澳大利亚墨尔本大学计算机科学博士。先后在WWW、PAKDD、RSFDGrC、IEEE GrC和Australian AI等靠前学术会议和IEEE Transactions on Knowledge and Data Engineering发表论文10余篇。目前是澳大利亚AUSTRAC的分析师。

《数据挖掘导论（完整版）》介绍了数据挖掘，涵盖了五个主题：数据、分类、关联分析、聚类和异常检测。除异常检测外，每个主题具有两章。前一章涵盖基本概念、代表性算法和评估技术，而后一章讨论概念和算法。这样读者在透彻地理解数据挖掘的基础的同时，还能够了解更多重要的主题。《数据挖掘导论（完整版）》是明尼苏达大学和密歇根州立大学数据挖掘课程的教材，由于独具特色，正式出版之前已经被斯坦福大学、得克萨斯大学奥斯汀分校等众多名校采用。《数据挖掘导论（完整版）》特色与许多其他同类图书不同，《数据挖掘导论（完整版）》将重点放在如何用数据挖掘知识解决各种实际问题。 只要求具备很少的预备知识——不需要数据库背景，只需要很少的统计学或数学背景知识。 书中包含大量的图表、综合示例和丰富的习题，并且使用示例、关键算法的简洁描述和习题，尽可能直接聚焦于数据挖掘的主要概念。 教辅内容极为丰富，包括课程幻灯片、学生课题建议、数据挖掘资源（如数据挖掘算法和数据集）、联机指南（使用实际的数据集和数据分析软件，《数据挖掘导论（完整版）》介绍的部分数据挖掘技术提供例子讲解）。

本书全面介绍了数据挖掘的理论和方法，旨在为读者提供将数据挖掘应用于实际问题所必需的知识。本书涵盖五个主题：数据、分类、关联分析、聚类和异常检测。除异常检测外，每个主题都包含两章：前面一章讲述基本概念、代表性算法和评估技术，后面一章较深入地讨论不错概念和算法。目的是使读者在透彻地理解数据挖掘基础的同时，还能了解更多重要的不错主题。此外，书中还提供了大量示例、图表和习题。


本书适合作为相关专业高年级本科生和研究生数据挖掘课程的教材，同时也可作为数据挖掘研究和应用开发人员的参考书。

    《数据挖掘导论（完整版）》介绍了数据挖掘，涵盖了五个主题：数据、分类、关联分析、聚类和异常检测。除异常检测外，每个主题具有两章。前一章涵盖基本概念、代表性算法和评估技术，而后一章讨论概念和算法。这样读者在透彻地理解数据挖掘的基础的同时，还能够了解更多重要的主题。《数据挖掘导论（完整版）》是明尼苏达大学和密歇根州立大学数据挖掘课程的教材，由于独具特色，正式出版之前已经被斯坦福大学、得克萨斯大学奥斯汀分校等众多名校采用。《数据挖掘导论（完整版）》特色与许多其他同类图书不同，《数据挖掘导论（完整版）》将重点放在如何用数据挖掘知识解决各种实际问题。     只要求具备很少的预备知识——不需要数据库背景，只需要很少的统计学或数学背景知识。     书中包含大量的图表、综合示例和丰富的习题，并且使用示例、关键算法的简洁描述和习题，尽可能直接聚焦于数据挖掘的主要概念。     教辅内容极为丰富，包括课程幻灯片、学生课题建议、数据挖掘资源（如数据挖掘算法和数据集）、联机指南（使用实际的数据集和数据分析软件，《数据挖掘导论（完整版）》介绍的部分数据挖掘技术提供例子讲解）。

　　《数据挖掘导论（完整版）》介绍了数据挖掘的理论和方法，旨在为读者提供将数据挖掘应用于实际问题所需的知识。《数据挖掘导论（完整版）》涵盖五个主题：数据、分类、关联分析、聚类和异常检测。除异常检测外，每个主题包含两章：前面一章讲述基本概念、代表性算法和评估技术，后面一章较深入地讨概念和算法。目的是使读者在透彻地理解数据挖掘基础的同时，还能了解更多重要的主题。此外，书中还提供了大量示例、图表和习题。

　　《数据挖掘导论（完整版）》适合作为相关专业高年级本科生和研究生数据挖掘课程的教材，同时也可作为数据挖掘研究和应用开发人员的参考书。