计算机科学丛书数据挖掘:原理与实践(基础篇)

目　录

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