数据挖掘：原理与实践

本书中文版分为基础篇和进阶篇，深入探讨了数据挖掘的各个方面，从基础知识到复杂的数据类型及其应用，涉及数据挖掘的各种问题领域。全书既有基本方法，也有进阶内容，彼此融为一体，这使得本书既可以作为数据挖掘领域的工具书，也可以作为数据科学、人工智能、计算机等相关专业本科及研究生教材。

1、大数据和人工智能时代的数据挖掘教材，将数据挖掘归纳成四个基本问题：聚类、分类、关联模式挖掘和异常分析，不仅详解数据挖掘的基础知识，而且还介绍高级数据类型，结合复杂多样的实际数据环境，探讨数据挖掘的应用场景和使用方法。

2、作译者均为数据挖掘领域资深学者。作者是IBM T. J. Watson研究中心杰出研究员阿加沃尔博士，他擅长将计算机科学问题提炼成数学问题，而且又能用计算机科学方法解决实际问题，本书是他的代表作之一。翻译工作由国内四位数据挖掘领域的翘楚，复旦大学王晓阳教授、清华大学王建勇教授、加拿大约克大学禹晓辉教授、中科院计算所陈世敏研究员历时5年时间完成，字斟句酌，精益求精。

3、全书注重原理和方法，既有基本方法，也有进阶内容，帮助读者在数据挖掘及人工智能应用方面打下良好基础。

本书中文版分为基础篇和进阶篇，深入探讨了数据挖掘的各个方面，从基础知识到复杂的数据类型及其应用，涉及数据挖掘的各种问题领域。它超越了传统上对数据挖掘问题的关注，引入了高级数据类型，例如文本、时间序列、离散序列、空间数据、图数据和社交网络数据。到目前为止，还没有一本书以如此全面和综合的方式探讨所有这些主题。

基础篇（包括原书的第1-13章）详细介绍了针对数据挖掘的四个主要问题（聚类、分类、关联模式挖掘和异常分析）的各种解决方法、用于文本数据领域的特定挖掘方法，以及对于数据流的挖掘应用。

进阶篇（包括原书的第14-20章）主要讨论了用于不同数据领域（例如时序数据、序列数据、空间数据、图数据）的特定挖掘方法，以及重要的数据挖掘应用（例如Web数据挖掘、排名、推荐、社交网络分析和隐私保护）。

本书在直观解释和数学细节上取得了很好的平衡，既包含研究人员需要的数学公式，又以简单直观的方式呈现出来，方便学生和从业人员（包括数学背景有限的人）阅读。本书包括大量插图、示例和练习，并把重点放在语义可解释的示例上，特别适合作为高级数据挖掘课程的教材。

作者简介：

查鲁·C. 阿加沃尔（Charu C. Aggarwal）是IBM T. J. Watson研究中心的杰出研究人员，于1996年获麻省理工学院博士学位。他对数据挖掘领域有着广泛的研究，在国际会议和期刊上发表了250多篇论文，拥有80多项专利。他曾三次被评为IBM的“杰出发明人”，并曾获得IBM公司奖、IBM杰出创新奖和两项IBM杰出技术成就奖。他因为提出基于冷凝的数据挖掘中的隐私保护技术而获得EDBT2014的时间检验奖。他还获得了IEEE ICDM研究贡献奖（2015），这是数据挖掘领域对具有突出贡献的研究的两个*高奖项之一。
他曾多次担任ACM/IEEE知名国际学术会议的主席或程序委员会主席，并担任大数据相关多个知名期刊的主编或编委。由于在知识发现和数据挖掘算法上的贡献，他入选SIAM、ACM和IEEE的会士。

译者简介：

王晓阳 复旦大学特聘教授、博士生导师，中国计算机学会会士，ACM会员，IEEE高级会员。主要研究兴趣为大数据分析、数据安全等。于复旦大学获得计算机科学学士、硕士学位，于美国南加州大学获得计算机科学博士学位。曾在美国乔治梅森大学、美国佛蒙特大学、美国国家科学基金会任职。2011年至今在复旦大学任职。主持多项美国国家科学基金项目、中国国家重点研发计划项目、自然科学基金重点项目、上海市重大科研项目等，并发表过百余篇高质量学术论文，现任Springer DSE期刊主编，IEEE ICDE会议系列、IEEE BigComp会议系列指导委员会委员，曾任CCF上海分部主席，IEEE ICDE 2012及ACM CIKM 2014总主席，WAIM会议系列指导委员会主席。曾获得美国国家科学基金CAREER Award。

王建勇 清华大学计算机系教授，国际电器与电子工程师协会会士（IEEE Fellow），中国人工智能学会会士（CAAI Fellow），江苏省大数据安全与智能处理重点实验室首届学术委员会副主任。主要研究领域为数据挖掘及知识发现。迄今发表论文100余篇（其中单篇*高引用2000余次）。曾担任IEEE ICDM’19、WISE’15、BioMedCom’14、WAIM’13、ADMA’11、NDBC’10等会议的程序委员会联合主席以及IEEE TKDE、ACM TKDD和《软件学报》等期刊的编委。入选2007年度教育部“新世纪优秀人才”支持计划和2009年度日本大川研究基金资助计划。获得WWW’08的Best Posters Award、2009年度和2010年度HP实验室创新研究奖以及教育部2013年度自然科学奖二等奖。

禹晓辉 南京大学学士、香港中文大学硕士、加拿大多伦多大学博士，加拿大约克大学副教授，山东大学兼职教授、博士生导师，中国计算机学会大数据专委会委员、数据库专委会委员。研究工作主要集中在大数据管理和分析领域，研究方向涵盖时空大数据处理与挖掘、面向人工智能的数据管理、社交媒体挖掘等。主持加拿大自然科学与工程理事会基金、中国国家自然科学基金等多项国家和工业界资助的科研项目。在IEEE Trans. on Knowl. & Data Eng.及SIGMOD、VLDB、ICDE等国内外期刊和会议上发表高质量论文近100篇，是3项美国专利的发明人。曾任WAIM2015、CloudDM2015等知名国际会议的程序委员会主席，是国际期刊Information Systems（Elsevier）的编委、加拿大自然科学与工程理事会NSERC特邀评审专家。

陈世敏 中科院计算所研究员，中国科学院大学岗位教师，分别于1997年和1999年获得清华大学计算机系学士和硕士学位，于2005年在美国卡内基梅隆大学获得计算机科学博士学位。主要研究方向为数据库系统和大数据系统。曾在SIGMOD、ISCA、VLDB、ASPLOS、ICDE、CIDR等顶级国际会议和ACM TODS、IEEE TKDE等顶级国际期刊发表过论文，并获得ICDE’04 Best Paper、SIGMOD’01 Runner-up Best Paper和2008年体系结构国际会议年度顶级论文奖（Top Picks’08）。曾担任PVLDB 2017、ICDE 2018、ICDCS 2016、CIKM 2014等会议的PC Area Chair，长期担任大数据新硬件技术的主要Workshop HardBD的Co-Chair。

目　录

Data Mining: The Textbook

出版者的话

译者序

前言

第1章　数据挖掘导论1

1.1　引言1

1.2　数据挖掘过程2

1.2.1　数据预处理阶段4

1.2.2　分析阶段5

1.3　基本数据类型5

1.3.1　非依赖型数据5

1.3.2　依赖型数据7

1.4　主要数据挖掘模块总览11

1.4.1　关联模式挖掘12

1.4.2　数据聚类13

1.4.3　异常检测13

1.4.4　数据分类14

1.4.5　复杂数据类型对问题定义的影响15

1.5　可扩展性问题和数据流场景17

1.6　应用案例浅述17

1.6.1　商店商品布局17

1.6.2　客户推荐18

1.6.3　医疗诊断18

1.6.4　Web日志异常检测19

1.7　小结19

1.8　文献注释19

1.9　练习题20

第2章　数据准备21

2.1　引言21

2.2　特征提取和类型转换22

2.2.1　特征提取22

2.2.2　数据类型转换23

2.3　数据清洗26

2.3.1　缺失项的处理27

2.3.2　错误项和不一致项的处理28

2.3.3　缩放与标准化29

2.4　数据约简和转换29

2.4.1　采样30

2.4.2　特征子集选取32

2.4.3　基于坐标轴旋转的维度约简32

2.4.4　基于类型转换的降维39

2.5　小结47

2.6　文献注释48

2.7　练习题48

第3章　相似度和距离50

3.1　引言50

3.2　多维数据50

3.2.1　定量型数据51

3.2.2　类别型数据58

3.2.3　定量型和类别型的混合数据59

3.3　文本相似性度量60

3.4　时态的相似性度量61

3.4.1　时间序列相似性度量61

3.4.2　离散序列相似性度量65

3.5　图的相似性度量67

3.5.1　单个图中两个节点之间的相似度67

3.5.2　两个图之间的相似度68

3.6　有监督的相似度函数69

3.7　小结70

3.8　文献注释70

3.9　练习题71

第4章　关联模式挖掘73

4.1　引言73

4.2　频繁模式挖掘模型74

4.3　关联规则的生成框架76

4.4　频繁项集挖掘算法77

4.4.1　暴力算法78

4.4.2　Apriori算法78

4.4.3　枚举树算法81

4.4.4　递归的基于后缀的模式生长方法89

4.5　替代模型：有趣模式96

4.5.1　统计相关系数97

4.5.2　χ2度量97

4.5.3　兴趣比率98

4.5.4　对称置信度98

4.5.5　列的余弦系数98

4.5.6　Jaccard系数和min-hash技巧98

4.5.7　集体强度100

4.5.8　与负模式挖掘的关系100

4.6　有用的元算法100

4.6.1　采样方法101

4.6.2　数据划分集成法101

4.6.3　推广到其他数据类型101

4.7　小结102

4.8　文献注释102

4.9　练习题104

第5章　关联模式挖掘：高级概念106

5.1　引言106

5.2　模式汇总106

5.2.1　最大模式107

5.2.2　闭包模式108

5.2.3　近似频繁模式109

5.3　模式查询110

5.3.1　一次预处理多次查询111

5.3.2　把限制条件放入模式挖掘115

5.4　关联模式挖掘的应用115

5.4.1　与其他数据挖掘问题的关系115

5.4.2　购物篮分析116

5.4.3　用户信息分析116

5.4.4　推荐和协同过滤116

5.4.5　Web日志分析117

5.4.6　生物信息学117

5.4.7　应用于其他复杂数据类型117

5.5　小结118

5.6　文献注释118

5.7　练习题119

第6章　聚类分析120

6.1　引言120

6.2　聚类的特征选取121

6.2.1　过滤模型121

6.2.2　包装模型124

6.3　基于代表点的算法124

6.3.1　k-means算法127

6.3.2　k-means内核算法128

6.3.3　k-medians算法128

6.3.4　k-medoids算法129

6.4　层次聚类算法130

6.4.1　自底向上凝聚的方法131

6.4.2　自顶向下分裂的方法135

6.5　基于概率模型的算法135

6.6　基于网格和基于密度的算法139

6.6.1　基于网格的算法139

6.6.2　DBSCAN141

6.6.3　DENCLUE143

6.7　基于图的算法147

6.8　非负矩阵分解149

6.9　聚类验证153

6.9.1　内部验证度量153

6.9.2　外部验证度量155

6.9.3　评价158

6.10　小结158

6.11　文献注释158

6.12　练习题159

第7章　聚类分析：高级概念161

7.1　引言161

7.2　类别型数据的聚类162

7.2.1　基于代表点的算法162

7.2.2　层次算法164

7.2.3　概率算法165

7.2.4　基于图的算法166

7.3　可扩展的数据聚类167

7.3.1　CLARANS167

7.3.2　BIRCH168

7.3.3　CURE169

7.4　高维数据聚类170

7.4.1　CLIQUE172

7.4.2　PROCLUS172

7.4.3　ORCLUS174

7.5　半监督聚类176

7.5.1　单点监督177

7.5.2　成对监督177

7.6　用户监督聚类与可视化监督聚类178

7.6.1　现有聚类算法的变体178

7.6.2　可视化聚类179

7.7　集成聚类181

7.7.1　选择不同的集成组件181

7.7.2　组合不同的集成组件182

7.8　聚类应用183

7.8.1　应用到其他数据挖掘问题183

7.8.2　客户分类与协同过滤183

7.8.3　文本应用184

7.8.4　多媒体应用184

7.8.5　时态与序列应用184

7.8.6　社交网络分析184

7.9　小结184

7.10　文献注释184

7.11　练习题185

第8章　异常分析186

8.1　引言186

8.2　极值分析187

8.2.1　单变量极值分析188

8.2.2　多变量极值190

8.2.3　基于深度的方法191

8.3　概率模型192

8.4　异常检测的聚类方法193

8.5　基于距离的异常检测195

8.5.1　剪枝方法195

8.5.2　局部距离修正方法197

8.6　基于密度的方法200

8.6.1　基于统计直方图和网格的技术200

8.6.2　核密度估计201

8.7　信息论模型201

8.8　异常点正确性203

8.8.1　方法论上的挑战203

8.8.2　接收者工作特征（ROC）曲线203

8.8.3　常见错误205

8.9　小结205

8.10　文献注释205

8.11　练习题206

第9章　异常分析：高级概念208

9.1　引言208

9.2　类别型数据上的异常检测208

9.2.1　概率模型209

9.2.2　聚类和基于距离的方法210

9.2.3　二元和集合取值的数据210

9.3　高维异常检测210

9.3.1　基于网格的罕见子空间探索212

9.3.2　随机子空间采样214

9.4　异常点集成分析215

9.4.1　根据成员独立性的分类216

9.4.2　根据构成成员的分类217

9.4.3　归一化与合并218

9.5　异常分析的应用219

9.5.1　质量控制和故障检测219

9.5.2　金融诈骗和异常事件219

9.5.3　网站日志分析219

9.5.4　入侵检测应用219

9.5.5　生物学和医学应用220

9.5.6　地球科学应用220

9.6　小结220

9.7　文献注释220

9.8　练习题221

第10章　数据分类222

10.1　引言222

10.2　分类的特征选择224

10.2.1　过滤模型224

10.2.2　包装模型227

10.2.3　嵌入式模型228

10.3　决策树228

10.3.1　划分准则231

10.3.2　停止准则与剪枝232

10.4　基于规则的分类器233

10.4.1　决策树规则生成234

10.4.2　顺序覆盖算法235

10.4.3　规则剪枝238

10.4.4　关联分类器238

10.5　概率分类器239

10.5.1　朴素贝叶斯分类器239

10.5.2　逻辑回归242

10.6　SVM245

10.6.1　线性可分数据的SVM245

10.6.2　不可分数据的SVM软间隔实现250

10.6.3　非线性SVM252

10.6.4　内核技巧253

10.7　神经网络256

10.7.1　单层神经网络：感知器257

10.7.2　多层神经网络258

10.7.3　不同线性模型的比较260

10.8　基于实例的学习261

10.8.1　最近邻分类器的设计差异261

10.9　分类器评估263

10.9.1　方法论问题263

10.9.2　量化问题265

10.10　小结269

10.11　文献注释269

10.12　练习题270

第11章　数据分类：高级概念272

11.1　引言272

11.2　多类别学习273

11.3　稀有类别学习274

11.3.1　样例重加权275

11.3.2　样例重采样275

11.4　可扩展分类276

11.4.1　可扩展的决策树276

11.4.2　可扩展的SVM277

11.5　数值型类别的回归模型278

11.5.1　线性回归278

11.5.2　主成分回归281

11.5.3　广义线性模型282

11.5.4　非线性和多项式回归283

11.5.5　由决策树至回归树284

11.5.6　模型有效性评估285

11.6　半监督学习285

11.6.1　通用元算法287

11.6.2　分类算法的具体变种288

11.6.3　基于图的半监督学习290

11.6.4　对半监督学习的讨论291

11.7　主动学习291

11.7.1　基于异构性的模型293

11.7.2　基于性能的模型294

11.7.3　基于代表性的模型295

11.8　集成方法296

11.8.1　为什么集成分析有效297

11.8.2　偏差-方差折中的正式表述299

11.8.3　集成学习的具体实例化301

11.9　小结305

11.10　文献注释305

11.11　练习题306

第12章　数据流挖掘308

12.1　引言308

12.2　流中的概要数据结构309

12.2.1　蓄水池采样309

12.2.2　海量域场景的概述结构315

12.3　数据流中的频繁模式挖掘325

12.3.1　利用概要结构325

12.3.2　有损计数算法325

12.4　数据流聚类326

12.4.1　STREAM算法326

12.4.2　CluStream算法328

12.4.3　海量域场景的流聚类331

12.5　流的异常检测332

12.5.1　单个数据点作为异常点332

12.5.2　聚集变化点作为异常点333

12.6　流分类335

12.6.1　VFDT家族335

12.6.2　有监督的微簇方法337

12.6.3　集成方法337

12.6.4　海量域流的分类337

12.7　小结338

12.8　文献注释338

12.9　练习题338

第13章　文本数据挖掘340

13.1　引言340

13.2　文档准备和相似度计算341

13.2.1　文档归一化和相似度计算342

13.2.2　专用于Web文档的预处理343

13.3　专用于文本的聚类方法344

13.3.1　基于代表点的算法344

13.3.2　概率算法346

13.3.3　同步发现文档簇和词簇347

13.4　主题建模349

13.4.1　维度约简中的使用以及与潜在语义分析的对比351

13.4.2　聚类中的使用以及与概率聚类的对比353

13.4.3　PLSA的局限性354

13.5　专用于文本的分类方法354

13.5.1　基于实例的分类器354

13.5.2　贝叶斯分类器356

13.5.3　高维稀疏数据的SVM分类器358

13.6　新事物和首发故事检测360

13.7　小结360

13.8　文献注释361

13.9　练习题361

参考文献362

译者序

Data Mining: The Textbook

在当今的人工智能时代，数据分析和挖掘似乎已经是一个很古老的话题。这也难怪，对数据的分析甚至可以追溯到中国第一经—《易经》这部远古文明的产物，至少17世纪就开始的数理统计学为数据分析准备了齐全的数学工具，而领域公认的第一个数据挖掘算法也早在27年前就发表了。相关领域现在流行的是机器学习，尤其是深度学习。那么在这个时候出版这本几年前就出版的原著译本，意义又何在？

事实上，目前的人工智能的发展是由数据驱动的。从数据中挖掘得到的知识在很大程度上成就了人工智能的奇妙，比如机器翻译、人脸识别、对话机器人等。目前人工智能所面临的问题是推广，也就是需要在各行各业将人工智能的能力发挥出来。这个能力的发挥在很大程度上依赖于数据的使用能力。而数据使用的难度源于数据的复杂性和多样性，我们需要一系列处理数据的工具，也就是数据挖掘工具，它是人工智能、机器学习任务的一个重要部分。

本书的一个特点是篇幅长、字数多，但它更重要的特点是打破了数据挖掘就是几个算法的错觉。它将数据挖掘工具放在实际的、复杂多样的数据环境中，总结各种方法的使用场景、使用方法，乃至可能的使用效果。各种方法与各种场景的组合纵横交错，形成了丰富的内容。

本书将数据挖掘归纳成四个基本问题：聚类、分类、关联模式挖掘和异常分析。同时作者对数据类型从多个方面进行考虑，包括是连续的还是离散的、是定量的还是定性的、是依赖于上下文的还是非依赖的，有文本数据和图数据，也有时间序列、与时间无关的序列、多维时间序列、数据流，以及各种交叉组合等，而且各种组合下的数据可能都需要进行聚类、分类、关联模式挖掘和异常分析。这就使数据挖掘任务变得异常复杂及困难，需要在本质上把这些类型之间的关系、各基本方法之间的关系，以及各类型与各方法之间的关系做一个梳理。另外，本书特别强调在解决上述问题时的计算及存储效率问题，在数据挖掘的实用性方面也有很好的分析。这些内容可帮助读者在数据挖掘及人工智能应用方面打下良好的基础。从这个角度来讲，本书对数据挖掘领域的描述相当完整。

本书作者是一位严谨的计算机科学家和高产的作家。译者在研究生涯中多次接触过他，他擅长将计算机科学问题提炼成数学问题，而且又能用计算机科学方法解决实际问题。从他撰写的书籍来看，他是一个在科研方面十分细致且思路宽广的人。本书注重原理、方法，有助于读者深入理解数据挖掘的各个方面，同时本书也可以作为一本“原理型菜单”，为各类数据的转换及四个基本方法的使用提供解决思路。既有基本方法，也有进阶内容，彼此融为一体，这使得本书既可以作为数据挖掘领域的工具书，也可以作为本科及研究生各个年级的教科书。

本书的翻译由本人与三位领域内翘楚王建勇、禹晓辉、陈世敏共同完成。整个翻译过程经过了较长的时间，其间得到了很多同事、学生的帮助，在这里一并感谢。同时也感谢机械工业出版社华章公司编辑们的极大耐心，“苦苦”等待本书翻译成稿。特别感谢本书策划编辑朱劼的支持与鼓励，使得冗长的翻译过程变得不再那么无望。最后，还要感谢本书责任编辑游静的出色工作，她使本书的成书质量得到了明显的提升。感谢各位。

王晓阳

2020年5月于上海

前　言

Data Mining: The Textbook

“数据是新时代的石油。”

—Clive Humby

在过去二十多年中，数据挖掘领域取得了很大的进步，从计算机科学的角度来看尤其明显。尽管传统的概率与统计领域对数据分析已经有了广泛和深入的研究，但数据挖掘这个术语是由计算机科学相关的社区所创立的。对计算机科学家来说，计算的可扩展性、可用性和计算的执行都是极为重要的。

作为一门学科，数据科学需要一本超越传统的、仅专注于基本数据挖掘的教科书。最近几年，“数据科学家”这样的工作职位已经在市场上出现，这些人的工作职责就是从海量数据中窥探知识。在典型的应用中，数据类型倾向于异构及多样，基于多维数据类型的基本方法可能会失去效用，因此我们更需要将重点放在这些不同的数据类型以及使用这些数据类型的应用上。一本全面覆盖数据挖掘内容的书必须探索数据挖掘的不同方面，从基本技术出发，进而探讨复杂的数据类型，以及这些数据类型与基本技术的关系。虽然基本技术构成数据挖掘的良好基础，但它们并没有展示出数据分析真正复杂的全貌。本书在不影响介绍基本技术的情况下，研究这些高级的话题，因此本书可以同时用于初级和高级数据挖掘课程。到目前为止，还没有一本书用这种全面、综合的方式来覆盖所有这些话题。

本书假设读者已经有了一些概率统计和线性代数方面的基础知识，一般掌握了理工科本科时期学习的相关内容就足够了。对业界的从业者来说，只要对这些基础知识有一定的实际经验，就可以使用本书。较强的数学背景对学习那些高级话题的章节显然会有所帮助，但并不是必需的。有些章节专门介绍特殊的数据挖掘场景，比如文本数据、时序数据、离散序列、图数据等，这种专门的处理是为了更好地展示数据挖掘在多种应用领域有用武之地。

本书的章节可以分为三类。

基础章节：数据挖掘主要有四个“超级问题”，即聚类、分类、关联模式挖掘和异常分析，它们的重要性体现为许许多多的实际应用把它们当成基本构件。由此，数据挖掘研究者和实践者非常重视为这些问题设计有效且高效的方法。这些基础章节详细地讨论了数据挖掘领域针对这几个超级问题所提出的各类解决方法。

领域章节：这些章节讨论不同领域的特殊方法，包括文本数据、时序数据、序列数据、图数据、空间数据等。这些章节多数可以认为是应用性章节，因为它们探索特定领域的特殊性问题。

应用章节：计算机硬件技术和软件平台的发展导致了一些数据密集型应用的产生，如数据流系统、Web挖掘、社交网络和隐私保护。应用章节对这些话题进行了详细的介绍。前面所说的那些领域章节其实也集中讨论了由这些不同的数据类型而产生的各类应用。

给使用本书的教师的一点建议

本书的撰写特点使得它特别适用于数据挖掘基础和高级两门课程的教学。通过对不同重点的关注，本书也可用于不同类型的数据挖掘课程。具体来说，使用各种章节组合可提供的课程包括下面几种。

基础课程：数据挖掘基础课程应侧重于数据挖掘的基础知识。这门课可以使用本书的第1、2、3、4、6、8、10章。事实上，一门课可能无法覆盖这些章节中的所有内容，任课教师可根据需要从这些章节中选择他们感兴趣的话题。这门课也可以考虑使用本书的第5、7、9、11章的部分内容，这些章节确实是为高级课程准备的，但不妨在基础课程中引入一部分。

高级课程（基础）：这门课将涵盖数据挖掘基础中的高级话题，并假定学生已经熟悉了本书第1～3章的内容，及第4、6、8、10章中的部分内容。这门课将主要关注第5、7、9、11章，如集成分析这样的内容对一门高级课程是有益的。此外，在基础课程中没来得及教授的第4、6、8、10章中的内容也可以在这门课中使用，并考虑增加第20章的隐私话题。

高级课程（数据类型）：这门课可以教授文本挖掘、时序、序列、图数据和空间数据等内容，使用本书的第13、14、15、16、17章。也可以考虑增加第19章（如图聚类部分）和第12章（数据流）的内容。

高级课程（应用）：应用课程可以与数据类型课程有所重叠，但有不同的侧重点。例如，在一个以应用为中心的课程中，重点应该放在建模而非算法方面。因此，第 13、14、15、16、17章中的内容可以保留，但可以跳过一些算法细节。因为对具体算法关注得少些，这几章可以比较快地介绍，建议把省下来的时间分配给重要的三章，即数据流（第12章）、Web挖掘（第18章）以及社交网络分析（第19章）。

本书的撰写风格简单，便于数学背景不多的本科生和业界从业人员使用。因此，对于学生、业界从业者以及科研人员，本书既可以作为初级的介绍性课本，也可以作为高级课程的课本。

在本书中，向量与多维数据点（包括类别型属性）都用上划线标注，如或y。向量或多维数据点可以由小写字母或大写字母来表示，只要有上划线标注即可。向量点积由中心点表示，如。矩阵用大写字母表示，不用上划线标注，如R。在整本书中，n×d的数据矩阵用D表示，包含n个d维的点，因此D中的各个数据点是一个d维列向量。若数据点是只包含一项的向量（即一维向量），那么n个数据点即可表示为一个n维列向量。比如，n个数据点的类别变量就是一个n维的列向量y。

致谢

感谢太太及女儿，感谢她们在我写这本书时所表达的爱与支持。写这本书需要大量的时间，这些时间都是从我的家人那里拿来的，所以这本书也是这段时间她们对我耐心支持的结果。

也感谢我的经理Nagui Halim，他给了我莫大的帮助，他在专业方面的支持对本书以及过去我所写的多本书都至关重要。

在撰写本书时，我得到了很多人的帮助，特别是下列人士给了我很好的反馈：Kanishka Bhaduri、Alain Biem、Graham Cormode、Hongbo Deng、Amit Dhurandhar、Bart Goethals、Alexander Hinneburg、Ramakrishnan Kannan、George Karypis、Dominique LaSalle、Abdullah Mueen、Guojun Qi、Pierangela Samarati、Saket Sathe、Karthik Subbian、Jiliang Tang、Deepak Turaga、Jilles Vreeken、Jieping Ye和Peixiang Zhao。感谢他们给了我很多具有建设性的反馈和建议。在过去的许多年中，我受益于许多合作者的真知灼见，这些对本书都有直接或间接的影响。首先要感谢我的长期合作者Philip S. Yu，我们一起合作了多年。其他与我有过深度合作关系的研究者还包括Tarek F. Abdelzaher、Jing Gao、Quanquan Gu、Manish Gupta、Jiawei Han、Alexander Hinneburg、Thomas Huang、Nan Li、Huan Liu、Ruoming Jin、Daniel Keim、Arijit Khan、Latifur Khan、Mohammad M. Masud、Jian Pei、Magda Procopiuc、Guo-jun Qi、Chandan Reddy、Jaideep Srivastava、Karthik Subbian、Yizhou Sun、Jiliang Tang、Min-Hsuan Tsai、Haixun Wang、Jianyong Wang、Min Wang、Joel Wolf、Xifeng Yan、Moha-mmed Zaki、ChengXiang Zhai和Peixiang Zhao。

还要感谢我的导师James B. Orlin，感谢他在我早期研究中所给予的指导。尽管我已经不在原来的研究领域里工作，但我从他那里学到的东西形成了我解决问题的关键方式，特别是他告诉我在科研中依赖直觉并使用简洁思路是很重要的。这种做法在科研中的重要性其实还没有受到广泛的重视。本书就是用了一种简单、直观的方法撰写的，这样科研人员及业界从业者都能更容易理解本领域的研究内容。

感谢Lata Aggarwal帮我用微软的PowerPoint画了书中的一些图。

作者简介

Charu C. Aggarwal 在纽约约克顿高地的IBM托马斯·J.沃森研究中心工作，是一位杰出研究员（DRSM）。他于1993年从坎普尔理工学院（IIT）获得学士学位，于1996年从麻省理工学院获得博士学位，并长期耕耘在数据挖掘领域。他发表了250多篇论文，撰写了80多篇专利文献，并编著和撰写了14本著作，其中包括第一部完整从计算机科学角度撰写的异常分析著作。由于他的专利具有很好的商用价值，IBM三次授予他“创新大师”称号。另外，他在生物威胁探测方面的工作于2003年获得IBM企业奖，在隐私技术方面的工作于2008年获得IBM杰出创新奖，在数据流方面的工作于2009年获得IBM杰出技术成就奖，在系统S中的贡献于2008年获得IBM研究部门奖。他的基于冷凝方法进行隐私保护下的数据挖掘方法获得了EDBT会议于2014年颁发的“久经考验”奖。

他曾担任2014年IEEE大数据会议的联席总主席，并从2004年至2008年担任IEEE Transactions on Knowledge and Data Engineering（TKDE）的副主编。他目前是ACM Transac-tions on Knowledge Discovery from Data（TKDD）的副主编，Data Mining and Knowledge Dis-

covery（DMKD）的执行主编，ACM SIGKDD Explorations的主编，以及Knowledge and Infor-mation Systems（KAIS）的副主编。他同时还担任由Springer出版的社交网络系列丛刊（LNSN）的顾问委员会成员。他曾担任过SIAM数据挖掘工作组的副主任。他由于对知识发现和数据挖掘算法的贡献而当选为ACM会士和IEEE会士。