本书源自作者在斯坦福大学教授多年的“Web挖掘”课程材料,主要关注大数据环境下数据挖掘的实际算法。书中分析了海量数据集数据挖掘常用的算法,介绍了目前Web应用的许多重要话题。主要内容包括:
□ 分布式文件系统以及Map-Reduce工具;
□ 相似性搜索;
□ 数据流处理以及针对易丢失数据等特殊情况的专用处理算法;
□ 搜索引擎技术,如谷歌的PageRank;
□ 频繁项集挖掘;
□ 大规模高维数据集的聚类算法;
□ Web应用中的关键问题:广告管理和**系统。
本书配套网http://infolab.stanford.edu/~ullman/mmds.html上提供英文版初稿以及一些课件和项目作业。显示全部信息

第1章 数据挖掘基本概念 1
1.1 数据挖掘的定义 1
1.1.1 统计建模 1
1.1.2 机器学习 1
1.1.3 建模的计算方法 2
1.1.4 数据汇总 2
1.1.5 特征抽取 3
1.2 数据挖掘的统计限制 4
1.2.1 整体情报预警 4
1.2.2 邦弗朗尼原理 4
1.2.3 邦弗朗尼原理的一个例子 5
1.2.4 习题 6
1.3 相关知识 6
1.3.1 词语在文档中的重要性 6
1.3.2 哈希函数 7
1.3.3 索引 8
1.3.4 二级存储器 10
1.3.5 自然对数的底e 10
1.3.6 幂定律 11
1.3.7 习题 12
1.4 本书概要 13
1.5 小结 14
1.6 参考文献 14
第2章 大规模文件系统及Map-Reduce 16
2.1 分布式文件系统 16
2.1.1 计算节点的物理结构 17
2.1.2 大规模文件系统的结构 18
2.2 Map-Reduce 18
2.2.1 Map任务 19
2.2.2 分组和聚合 20
2.2.3 Reduce任务 20
2.2.4 组合器 21
2.2.5 Map-Reduce的执行细节 21
2.2.6 节点失效的处理 22
2.3 使用Map-Reduce的算法 22
2.3.1 基于Map-Reduce的矩阵—向量乘法实现 23
2.3.2 向量v无法放入内存时的处理 23
2.3.3 关系代数运算 24
2.3.4 基于Map-Reduce的选择运算 26
2.3.5 基于Map-Reduce的投影运算 26
2.3.6 基于Map-Reduce的并、交和差运算 27
2.3.7 基于Map-Reduce的自然连接运算 27
2.3.8 一般性的连接算法 28
2.3.9 基于Map-Reduce的分组和聚合运算 28
2.3.10 矩阵乘法 29
2.3.11 基于单步Map-Reduce的矩阵乘法 29
2.3.12 习题 30
2.4 Map-Reduce的扩展 31
2.4.1 工作流系统 31
2.4.2 Map-Reduce的递归扩展版本 32
2.4.3 Pregel系统 34
2.4.4 习题 35
2.5 集群计算算法的效率问题 35
2.5.1 集群计算的通信开销模型 35
2.5.2 实耗通信开销 36
2.5.3 多路连接 37
2.5.4 习题 40
2.6 小结 40
2.7 参考文献 42
第3章 相似项发现 44
3.1 近邻搜索的应用 44
3.1.1 集合的Jaccard相似度 44
3.1.2 文档的相似度 45
3.1.3 协同过滤——一个集合相似问题 46
3.1.4 习题 47
3.2 文档的Shingling 47
3.2.1 k-Shingle 47
3.2.2 shingle大小的选择 48
3.2.3 对shingle进行哈希 48
3.2.4 基于词的shingle 49
3.2.5 习题 49
3.3 保持相似度的集合摘要表示 49
3.3.1 集合的矩阵表示 50
3.3.2 *小哈希 50
3.3.3 *小哈希及Jaccard相似度 51
3.3.4 *小哈希签名 52
3.3.5 *小哈希签名的计算 52
3.3.6 习题 54
3.4 文档的局部敏感哈希算法 55
3.4.1 面向*小哈希签名的LSH 56
3.4.2 行条化策略的分析 57
3.4.3 上述技术的综合 58
3.4.4 习题 59
3.5 距离测度 59
3.5.1 距离测度的定义 59
3.5.2 欧氏距离 60
3.5.3 Jaccard距离 60
3.5.4 余弦距离 61
3.5.5 编辑距离 62
3.5.6 海明距离 63
3.5.7 习题 63
3.6 局部敏感函数理论 64
3.6.1 局部敏感函数 65
3.6.2 面向Jaccard距离的局部敏感函数族 66
3.6.3 局部敏感函数族的放大处理 66
3.6.4 习题 68
3.7 面向其他距离测度的LSH函数族 68
3.7.1 面向海明距离的LSH函数族 69
3.7.2 随机超平面和余弦距离 69
3.7.3 梗概 70
3.7.4 面向欧氏距离的LSH函数族 71
3.7.5 面向欧氏空间的更多LSH函数族 72
3.7.6 习题 72
3.8 LSH函数的应用 73
3.8.1 实体关联 73
3.8.2 一个实体关联的例子 74
3.8.3 记录匹配的验证 74
3.8.4 指纹匹配 75
3.8.5 适用于指纹匹配的LSH函数族 76
3.8.6 相似新闻报道检测 77
3.8.7 习题 78
3.9 面向高相似度的方法 79
3.9.1 相等项发现 79
3.9.2 集合的字符串表示方法 79
3.9.3 基于长度的过滤 80
3.9.4 前缀索引 81
3.9.5 位置信息的使用 82
3.9.6 使用位置和长度信息的索引 83
3.9.7 习题 85
3.10 小结 85
3.11 参考文献 87
第4章 数据流挖掘 89
4.1 流数据模型 89
4.1.1 一个数据流管理系统 89
4.1.2 流数据源的例子 90
4.1.3 流查询 91
4.1.4 流处理中的若干问题 92
4.2 流当中的数据抽样 92
4.2.1 一个富于启发性的例子 93
4.2.2 代表性样本的获取 93
4.2.3 一般的抽样问题 94
4.2.4 样本规模的变化 94
4.2.5 习题 95
4.3 流过滤 95
4.3.1 一个例子 95
4.3.2 布隆过滤器 96
4.3.3 布隆过滤方法的分析 96
4.3.4 习题 97
4.4 流中独立元素的数目统计 98
4.4.1 独立元素计数问题 98
4.4.2 FM算法 98
4.4.3 组合估计 99
4.4.4 空间需求 100
4.4.5 习题 100
4.5 矩估计 100
4.5.1 矩定义 100
4.5.2 二阶矩估计的AMS算法 101
4.5.3 AMS算法有效的原因 102
4.5.4 更高阶矩的估计 103
4.5.5 无限流的处理 103
4.5.6 习题 104
4.6 窗口内的计数问题 105
4.6.1 **计数的开销 105
4.6.2 DGIM算法 105
4.6.3 DGIM算法的存储需求 107
4.6.4 DGIM算法中的查询应答 107
4.6.5 DGIM条件的保持 108
4.6.6 降低错误率 109
4.6.7 窗口内计数问题的扩展 109
4.6.8 习题 110
4.7 衰减窗口 110
4.7.1 *常见元素问题 110
4.7.2 衰减窗口的定义 111
4.7.3 *流行元素的发现 111
4.8 小结 112
4.9 参考文献 113
第5章 链接分析 115
5.1 PageRank 115
5.1.1 早期的搜索引擎及词项作弊 115
5.1.2 PageRank的定义 117
5.1.3 Web结构 119
5.1.4 避免终止点 121
5.1.5 采集器陷阱及“抽税”法 123
5.1.6 PageRank在搜索引擎中的使用 125
5.1.7 习题 125
5.2 PageRank的快速计算 126
5.2.1 转移矩阵的表示 127
5.2.2 基于Map-Reduce的PageRank迭代计算 128
5.2.3 结果向量合并时的组合器使用 128
5.2.4 转移矩阵中块的表示 129
5.2.5 其他**的PageRank迭代方法 130
5.2.6 习题 131
5.3 面向主题的PageRank 131
5.3.1 动机 131
5.3.2 有偏的随机游走模型 132
5.3.3 面向主题的PageRank的使用 133
5.3.4 基于词汇的主题推断 134
5.3.5 习题 134
5.4 链接作弊 135
5.4.1 垃圾农场的架构 135
5.4.2 垃圾农场的分析 136
5.4.3 与链接作弊的斗争 137
5.4.4 TrustRank 137
5.4.5 垃圾质量 137
5.4.6 习题 138
5.5 导航页和权威页 139
5.5.1 HITS的直观意义 139
5.5.2 导航度和权威度的形式化 139
5.5.3 习题 142
5.6 小结 143
5.7 参考文献 145
第6章 频繁项集 146
6.1 购物篮模型 146
6.1.1 频繁项集的定义 146
6.1.2 频繁项集的应用 148
6.1.3 关联规则 149
6.1.4 高可信度关联规则的发现 150
6.1.5 习题 151
6.2 购物篮及A-Priori算法 152
6.2.1 购物篮数据的表示 152
6.2.2 项集计数中的内存使用 153
6.2.3 项集的单调性 154
6.2.4 二元组计数 155
6.2.5 A-Priori算法 155
6.2.6 所有频繁项集上的A-Priori算法 157
6.2.7 习题 158
6.3 更大数据集在内存中的处理 159
6.3.1 PCY算法 160
6.3.2 多阶段算法 161
6.3.3 多哈希算法 163
6.3.4 习题 164
6.4 有限扫描算法 166
6.4.1 简单的随机化算法 166
6.4.2 抽样算法中的错误规避 167
6.4.3 SON算法 168
6.4.4 SON算法和Map-Reduce 168
6.4.5 Toivonen算法 169
6.4.6 Toivonen算法的有效性分析 170
6.4.7 习题 170
6.5 流中的频繁项计数 171
6.5.1 流的抽样方法 171
6.5.2 衰减窗口中的频繁项集 172
6.5.3 混合方法 172
6.5.4 习题 173
6.6 小结 173
6.7 参考文献 175
第7章 聚类 176
7.1 聚类技术介绍 176
7.1.1 点、空间和距离 176
7.1.2 聚类策略 177
7.1.3 维数灾难 178
7.1.4 习题 179
7.2 层次聚类 179
7.2.1 欧氏空间下的层次聚类 180
7.2.2 层次聚类算法的效率 183
7.2.3 控制层次聚类的其他规则 183
7.2.4 非欧空间下的层次聚类 185
7.2.5 习题 186
7.3 k-均值算法 187
7.3.1 k-均值算法基本知识 187
7.3.2 k-均值算法的簇初始化 187
7.3.3 选择k的正确值 188
7.3.4 BFR算法 189
7.3.5 BFR算法中的数据处理 191
7.3.6 习题 192
7.4 CURE算法 193
7.4.1 CURE算法的初始化 194
7.4.2 CURE算法的完成 195
7.4.3 习题 195
7.5 非欧空间下的聚类 196
7.5.1 GRGPF算法中的簇表示 196
7.5.2 簇表示树的初始化 196
7.5.3 GRGPF算法中的点加入 197
7.5.4 簇的分裂及合并 198
7.5.5 习题 199
7.6 流聚类及并行化 199
7.6.1 流计算模型 199
7.6.2 一个流聚类算法 200
7.6.3 桶的初始化 200
7.6.4 桶合并 200
7.6.5 查询应答 202
7.6.6 并行环境下的聚类 202
7.6.7 习题 203
7.7 小结 203
7.8 参考文献 205
第8章 Web广告 207
8.1 在线广告相关问题 207
8.1.1 广告机会 207
8.1.2 直投广告 208
8.1.3 展示广告的相关问题 208
8.2 在线算法 209
8.2.1 在线和离线算法 209
8.2.2 贪心算法 210
8.2.3 竞争率 211
8.2.4 习题 211
8.3 广告匹配问题 212
8.3.1 匹配及**匹配 212
8.3.2 *大匹配贪心算法 213
8.3.3 贪心匹配算法的竞争率 213
8.3.4 习题 214
8.4 Adwords问题 214
8.4.1 搜索广告的历史 215
8.4.2 Adwords问题的定义 215
8.4.3 Adwords问题的贪心方法 216
8.4.4 Balance算法 217
8.4.5 Balance算法竞争率的一个下界 217
8.4.6 多投标者的Balance算法 219
8.4.7 一般性的Balance算法 220
8.4.8 Adwords问题的*后论述 221
8.4.9 习题 221
8.5 Adwords的实现 221
8.5.1 投标和搜索查询的匹配 222
8.5.2 更复杂的匹配问题 222
8.5.3 文档和投标之间的匹配算法 223
8.6 小结 224
8.7 参考文献 226
第9章 **系统 227
9.1 一个**系统的模型 227
9.1.1 效用矩阵 227
9.1.2 长尾现象 228
9.1.3 **系统的应用 230
9.1.4 效用矩阵的填充 230
9.2 基于内容的** 231
9.2.1 项模型 231
9.2.2 文档的特征发现 231
9.2.3 基于Tag的项特征获取 232
9.2.4 项模型的表示 233
9.2.5 用户模型 234
9.2.6 基于内容的项** 235
9.2.7 分类算法 235
9.2.8 习题 237
9.3 协同过滤 238
9.3.1 相似度计算 238
9.3.2 相似度对偶性 241
9.3.3 用户聚类和项聚类 242
9.3.4 习题 243
9.4 降维处理 243
9.4.1 UV分解 244
9.4.2 RMSE 244
9.4.3 UV分解的增量式计算 245
9.4.4 对任一元素的优化 247
9.4.5 一个完整UV分解算法的构建 248
9.4.6 习题 250
9.5 NetFlix竞赛 250
9.6 小结 251
9.7 参考文献 253
索引 254

数据挖掘基本概念 本章为全书的导论部分,首先阐述数据挖掘的本质,并讨论其在多个相关学科中的不同理解。接着介绍邦弗朗尼原理(Bonferroni’s principle),该原理实际上对数据挖掘的过度使用提出了警告。本章还概述了一些非常有用的思想,它们未必都属于数据挖掘的范畴,但是却有利于理解数据挖掘中的某些重要概念。这些思想包括度量词语重要性的TF.IDF权重、哈希函数及索引结构的性质、包含自然对数底e的恒等式等。*后,简要介绍了后续章节所要涉及的主题。
1.1 数据挖掘的定义
*广为接受的定义是,数据挖掘(data mining)是数据“模型”的发现过程。而“模型”却可以有多种含义。下面介绍在建模方面*重要的几个方向。
1.1.1 统计建模
*早使用“data mining”术语的人是统计学家。术语“data mining”或者“data dredging”*初是贬义词,意指试图抽取出数据本身不支持的信息的过程。1.2节给出了这种挖掘情况下可能犯的几类错误。当然,现在术语“data mining”的意义已经是正面的了。目前,统计学家认为数据挖掘就是统计模型(statistical model)的构建过程,而这个统计模型指的就是可见数据所遵从的总体分布。
例1.1 假定现有的数据是一系列数字。这种数据相对于常用的挖掘数据而言显得过于简单,但这只是为了说明问题而采用的例子。统计学家可能会判定这些数字来自一个高斯分布(即正态分布),并利用公式来计算该分布*有可能的参数值。该高斯分布的均值和标准差能够完整地刻画整个分布,因而成为上述数据的一个模型。
1.1.2 机器学习
有些人将数据挖掘看成是机器学习的同义词。毫无疑问,一些数据挖掘方法中适当使用了机器学习算法。机器学习的实践者将数据当成训练集来训练某类算法,比如贝叶斯网络、支持向量机、决策树、隐马尔可夫模型等。
某些场景下上述的数据利用方式是合理的。机器学习擅长的典型场景是人们对数据中的寻找目标几乎一无所知。比如,我们并不清楚到底是影片的什么因素导致某些观众喜欢或者厌恶该影片。因此,在Netflix竞赛要求设计一个算法来预测观众对影片的评分时,基于已有评分样本的机器学习算法获得了巨大成功。在9.4节中,我们将讨论此类算法的一个简单形式。
另一方面,当挖掘的目标能够更直接地描述时,机器学习方法并不成功。一个有趣的例子是,WhizBang!实验室曾试图使用机器学习方法在Web上定位人们的简历。但是不管使用什���机器学习算法,*后的效果都比不过人工设计的直接通过典型关键词和短语来查找简历的算法。由于看过或者写过简历的人都对简历包含哪些内容非常清楚, Web页面是否包含简历毫无秘密可言。因此,使用机器学习方法相对于直接设计的简历发现算法而言并无任何优势。
1.1.3 建模的计算方法
近年来,计算机科学家已将数据挖掘看成一个算法问题。这种情况下,数据模型仅仅就是复杂查询的答案。例如,给定例1.1中的一系列数字,我们可以计算它们的均值和标准差。需要注意的是,这样计算出的参数可能并不是这组数据的*佳高斯分布拟合参数,尽管在数据集规模很大时两者非常接近。
数据建模有很多不同的方法。前面我们已经提到,数据可以通过其生成所可能遵从的统计过程构建来建模。而其他的大部分数据建模方法可以描述为下列两种做法之一:
(1) 对数据进行简洁的近似汇总描述;
(2) 从数据中抽取出*突出的特征来代替数据并将剩余内容忽略。
在接下来的内容中,我们将探究上述两种做法。
1.1.4 数据汇总
一种*有趣的数据汇总形式是PageRank,它也是使谷歌成功的关键算法之一,我们将在第5章对它进行详细介绍。在这种形式的Web挖掘当中,Web的整个复杂结构可由每个页面所对应的一个数字归纳而成。这种数字就是网页的PageRank值,即一个Web结构上的随机游走者在任意给定时刻处于该页的概率(这是极其简化的一种说法)。PageRank的一个非常好的特性就是它能够很好地反映网页的重要性,即典型用户在搜索时期望返回某个页面的程度。
另一种重要的数据汇总形式是聚类,第7章将予以介绍。在聚类中,数据被看成是多维空间下的点,空间中相互邻近的点将被赋予相同的类别。这些类别本身也会被概括表示,比如通过类别质心及类别中的点到质心的平均距离来描述。这些类别的概括信息综合在一起形成了全体数据集合的数据汇总结果。 例1.2 一个利用聚类来解决问题的**实例发生在很久以前的伦敦,在整个问题的解决中并没有使用计算机 。内科医生John Snow在处理霍乱爆发时在城市地图上标出了病例的发生地点。图1-1给出了该图的一个小片段,展示了病例的传播情况。

图1-1 在伦敦市地图上标出的霍乱病例的传播情况示意图
图中显示,病例聚集在某些交叉路口。这些路口的水井已经被污染,离这些水井*近的居民染上了疾病,而清洁的水井附近的居民则没有染病。如果没对这些数据进行聚类,霍乱的病因就难以揭开。
1.1.5 特征抽取
典型的基于特征的模型会从数据中寻找某个现象的***样例,并使用这些样例来表示数据。熟悉机器学习的一个分支——贝叶斯网络(并不在本书的讨论范围内)的读者应该会知道,在贝叶斯网络中,可以利用寻找对象间的*强统计依赖来表示所有统计关联,从而表示出对象之间的复杂关系。我们将要介绍大规模数据集下的一些重要的特征抽取类型,它们包括以下两种。
(1) 频繁项集(frequent itemset) 该模型适用于多个小规模项集组成的数据,就像我们将在第6章讨论的购物篮问题(market-basket problem)一样。我们寻找那些在很多购物篮中同时出现的小规模项集,这些频繁项集就是我们要找的刻画数据的特征。这种挖掘的原始应用的的确确发生在真实的购物篮场景下:在商店或者超市收银台结账的时候确实会发现某些物品会被顾客同时购买,例如汉堡包和番茄酱,这些物品就组成所谓的项集。
(2) 相似项(similar item) 很多时候,数据往往看上去相当于一系列集合,我们的目标是寻找那些共同元素比例较高的集合对。一个例子是将在线商店(如Amazon)的顾客看成是其已购买的商品的集合。为了使Amazon能够向某顾客**他可能感兴趣的其他商品,Amazon可以寻找与该顾客相似的顾客群,并把他们当中大部分人购买过的商品也**给他。该过程称为协同过滤(collaborative filtering)。如果顾客的兴趣都很单一,即他们只购买某一类的商品,那么将顾客聚类的方法可能会起作用。然而,由于顾客大都对许多不同的商品感兴趣,因此对每个顾客而言,寻找兴趣相似的那部分顾客并根据这些关联对数据进行表示的做法会更有用。我们将在第3章讨论相似性。
1.2 数据挖掘的统计限制
一类常见的数据挖掘问题涉及在大量数据中发现隐藏的异常事件。本节主要讨论这个问题,并介绍对数据挖掘的过度使用进行警告的邦弗朗尼原理。
1.2.1 整体情报预警
2002年,美国布什政府提出了一项针对所有可获得的数据进行挖掘的计划,目的用于追踪恐怖活动,这些数据包括信用卡收据、酒店记录、旅行数据以及许多其他类型的情报。该计划被称为整体情报预警(Total Information Awareness,TIA)。TIA计划无疑在隐私倡导者当中受到了极大关注,虽然*终它并没有被国会通过,但其实我们并不清楚这种计划是否已被冠以其他名称而得以真正实施。隐私和**的折中困难姑且不在本书的讨论目的之列,然而,TIA或类似系统若想进一步发展,在其可行性和所依赖假设的现实性方面还需做更多的技术改进。
很多人关心的是,如果浏览了这么多数据,并且想从这些数据当中发现疑似的恐怖行为,那么难道*终就不会找出很多无辜的行为?乃至虽然非法但不是恐怖行为的行为?这些发现会导致警察的登门造访甚至更糟的情形。答案取决于所定义行为的严密程度。统计学家已经发现了该问题的各种伪装形式,并且提出了一个理论。该理论将在下一节介绍。
1.2.2 邦弗朗尼原理
假定人们有一定量的数据并期望从该数据中找到某个特定类型的事件。即使数据完全随机,也可以期望该类型事件会发生。随着数据规模的增长,这类事件出现的数目也随之上升。任何随机数据往往都会有一些不同寻常的特征,这些特征看上去虽然很重要,但是实际上并不重要,除此之外,别无他由,从这个意义上说,这些事件的出现纯属“臆造”。统计学上有一个称为邦弗朗尼校正(Bonferroni correction)的定理,该定理给出一个在统计上可行的方法来避免在搜索数据时出现的大部分“臆造”正响应。这里并不打算介绍定理的统计细节,只给出一个非正式的称为邦弗朗尼原理的版本,该原理可以帮助我们避免将随机出现看成真正出现。在数据随机性假设的基础上,可以计算所寻找事件出现次数的期望值。如果该结果显著高于你所希望找到的真正实例的数目,那么可以预期,寻找到的几乎任何事物都是臆造的,也就是说,它们是在统计上出现的假象,而不是你所寻找事件的凭证。上述观察现象是邦弗朗尼原理的非正式阐述。
以寻找恐怖分子为例,可以预期在任何时候都几乎没有恐怖分子在活动。按照邦弗朗尼原理,只需要寻找那些几乎不可能出现在随机数据中的罕见事件来发现恐怖分子即可。下一节将给出一个扩展的例子。
1.2.3 邦弗朗尼原理的一个例子
假设我们确信在某个地方有一群恶人,目标是把他们揪出来。再假定我们有理由相信,这些恶人会定期在某个宾馆聚会来商讨他们的作恶计划。为限定问题的规模,我们再给出如下假设:
(1) 恶人数目可能有10亿;
(2) 每个人每100天当中会有**去宾馆;
(3) 一个宾馆*多容纳100个人。因此,100 000个宾馆已足够容纳10亿人中的1%在某个给定的日子入住宾馆;
(4) 我们将对1000天的宾馆入住记录进行核查。
为了在上述数据中发现恶人的踪迹,我们可以找出那些在两个不同日子入住同一宾馆的人。但是假设并没有恶人,也就是说,给定某**,对每个人来说,他们都是随机地确定是否去宾馆(概率为0.01),然后又是随机地从105个宾馆中选择一个。从上述数据中,我们能否推断出某两个人可能是恶人?
接下来我们做个简单的近似计算。给定某天,任意两个人都决定去宾馆的概率为0.000 1,而他们入住同一宾馆的概率应该在0.000 1基础上除以105(宾馆的数量)。因此,在给定某天的情况下,两个人同时入住同一宾馆的概率是10?9。而在任意给定的不同的两个日子,两人入住同一宾馆的概率就是10?9的平方,即10?18。需要指出的是,上述推理中只需要两人两次中每次住的宾馆相同即可,并不需要两次都是同一家宾馆。
基于上述计算,我们必须要考虑到底事件出现多少次才意味着作恶事件的发生。上例中,“事件”的含义是指“两个人在两天中的每**入住相同宾馆”。为简化数字运算,对于较大的n,大概等于n2/2。下面我们都采用这个近似值。因此在109中的人员组对个数为 =5×1017,而在1000天内任意两天的组合个数为 =5×105。疑似作恶事件的期望数目应该是上述两者的乘积再乘上“两个人在两天中的每**入住相同宾馆”的概率,结果为
5 × 1017 × 5 × 105 × 10?18 = 250 000
也就是说,大概有25万对人员看上去像恶人,即使他们根本不是。
现在假定实际上只有10对人员是真正的恶人。警察局需要调查25万对人员来寻找他们。除了会侵犯近50万无辜人们的生活外,所需的工作量非常大,以至于上述做法几乎是不可行的。
1.2.4 习题
习题1.2.1 基于1.2.3节的信息,如果对数据做如下改变(其他数据保持不变),那么可能的嫌疑人员对的数目是多少?
(1) 观察的天数从1000天增加到2000天。
(2) 要观察的总人员数目上升到20亿(因此需要200 000个宾馆)。
(3) 只有在不同的三天内的同一时刻两个人入住相同宾馆的情况下,才进行嫌疑报告。
! 习题1.2.2 假定有1亿人的超市购物记录,每个人每年都会去超市100次,每次都会买超市中1000种商品中的10种。我们相信,两个恐怖分子会在一年中的某个时段购买相同的10种商品(比如制造炸弹的材料)。如果对购买相同商品集合的人员对进行搜索,那么能否期望我们发现的任何这类人员都是真正的恐怖分子?
1.3 相关知识
本节中,我们将简要介绍一些有用的主题,读者可能在其他课程的研究中接触过或者根本没有接触过这些主题,但是它们却对于数据挖掘的研究相当有益。这些主题包括:
(1) 用于度量词语重要性的TF.IDF指标;
(2) 哈希函数及其使用;
(3) 二级存储器(磁盘)及其对算法运行时间的影响;
(4) 自然对数的底e及包含它的一系列恒等式;
(5) 幂定律(power law)。
1.3.1 词语在文档中的重要性
数据挖掘的不少应用都会涉及根据主题对文档(词语的序列)进行分类的问题。一般来说,文档的主题主要通过找到一些特定的能够体现主题的词语来刻画。例如,有关棒球(baseball)的文章当中往往会出现类似“ball”(球)、“bat”(球棒)、“pitch”(投球)以及“run”(跑垒)之类的词语。一旦将文档分到确实是关于棒球的主题类中,不难发现上述词语在文档当中的出现往往十分频繁。但是,在没有分类之前,并不能确定这些词语就刻画了棒球的主题类别。
因此,分类的**步往往是考察文档并从中找出重要的词语。为达到这个目的,我们首先猜测文档中*频繁出现的词语应该*重要。但是,这个直觉和实际情况恰恰相反。出现*频繁的大部分词语肯定都是那些类似于“the”或者“and”的常见词,这些词通常都用于辅助表达但本身不携带任何含义。实际上,英语中几百个*常见的词(称为停用词)往往都在文档分类之前就被去掉。
事实上,描述主题的词语往往都相对罕见。但是,并非所有罕见词在做指示词时都同等重要。一方面,某些在整个文档集合中极少出现的词语(如“notwithstanding”或“albeit”)并不能提供多少有用的信息。另一方面,某个如“chukker”(马球比赛中的一局)的词虽然和上述词语一样罕见,但是该词语却能提示我们文档明显和马球运动有关。上述两类罕见词的区别与它们是否在部分文档中反复出现有关。也就是说,类似“albeit”的词语在文档中出现并不会增加它多次出现的可能性。但是,如果一篇文章有一次提到“chukker”,那么文档可能会提到“first chukker”(**局)发生什么,接着提到“second chukker”(第二局)发生什么,以此类推。也就是说,如果这类词在文档中出现那么它们很可能会反复出现。
这种度量给定词语在少数文档中反复出现程度的形式化指标称为TF.IDF(TF指词项频率,是Term Frequency的缩写,IDF指逆文档频率,是Inverse Document Frequency的缩写,TF.IDF表示词项频率乘以逆文档频率)。它通常采用如下方式计算。假定文档集中有N篇文档,fij为词项i在文档j中出现的频率(即次数),于是,词项i在文档j中的词项频率TFij定义为

也就是词项i在文档j中的词项频率fij归一化结果,其中归一化通过fij除以同一文档中出现*多的词项(可能不考虑停用词的频率)的频率来计算。因此,文档j中出现频率*大的词项的TF值为1,而其他词项的TF值都是分数。
假定词项i在文档集的ni篇文档中出现,那么词项i的IDF定义如下:

于是,词项i在文档j中的得分被定义为TFij×IDFi,具有*高TF.IDF得分的那些词项通常都是刻画文档主题的*佳词项。
例1.3 假定文档集中有220 = 1 048 576 篇文档,假定词语w在其中的210 = 1024篇文档中出现,那么IDFw = log2(220/210) = log2(210) = 10。考虑一篇文档j,w在该文档中出现20次,这也是文档当中出现*多的词(停用词可能已经去掉)。那么TFwj =1,于是w在文档j中的TF.IDF得分为10。
假定在文档k中,词语w出现一次,而该文档中任一词语*多出现20次。于是有TFwk = 1/20,w在文档k中的TF.IDF得分为1/2。
1.3.2 哈希函数
读者或许听说过哈希表,也可能在Java类或类似软件包当中使用过哈希表。实现哈希表的哈希函数在多个数据挖掘算法中都是核心要素,不过在这些数据挖掘算法中,哈希表却和一般常见的形式有所不同。下面我们将介绍哈希函数的基本知识。
首先,哈希函数h的输入是一个哈希键值(hash-key),输出是一个桶编号(bucket number)。假定桶的个数为整数B,则桶编号通常是0到B-1之间的整数。哈希键值可以是任何类型的数据。哈希函数的一个直观性质是它们将哈希键值“随机化”(randomize)。更**地说,如果哈希键值随机地从某个合理的可能的哈希键分布中抽样而成,那么函数h将会把数目近似相等的哈希键值分配到每个桶中。这一点有可能做不到,比如当所有可能的哈希键值数目少于桶数目B时就是如此。当然我们可以认为该总体不具有“合理”分布。然而,可能存在更细微的原因导致哈希函数的结果不能近似均匀地分布。
例1.4 假设所有的哈希键都是正整数。一个普遍且简单的哈希函数是h(x) = x mod B,即x除以B之后的余数。如果哈希键的总体是所有的正整数,那么上述哈希函数产生的结果会非常均匀,即1/B的整数将被分到每个桶中。但是,如果哈希键只能是偶数值,并且如果B=10,那么h(x)的结果只能是0、2、4、6和8,也就是说,此时哈希函数的行为明显不够随机。另一方面,如果选择B=11,那么会有1/11的偶数会分到每个桶中,这时候哈希函数的效果又会很好。
对上例进行一般化,当哈希键都是整数时,如果选用一个与所有可能的哈希键(或者大部分)都具有公因子的B时,将会导致分配到桶中的结果不随机。因此,通常都**将B取为素数。尽管这种情况下我们还必须要考虑所有的哈希键以B为因子的可能性,但是上述选择方法减少了非随机行为的可能性。当然,还有很多其他类型的哈希函数并不基于取模运算。这里也并不打算概括所有可能的哈希函数类型,但是在*后一节的参考文献讨论当中也提到了一些相关的信息来源。
如果哈希键不是整数,要如何处理呢?在某种意义上说,所有数据类型的值都由比特位组成,而比特位序列常常可以解释成整数。但是,有一些简单的规则可以将通用的类型转化成整数。例如,如果哈希键是字符串,那么可以将每个字符转换成其对应的ASCII码或Unicode码,每个码可以解释为一个小整数。在除以B之前可以将这些整数求和,只要B小于字符串总体中各字节字符码的典型求和结果,那么*后对B取模的结果相对还是比较均匀的。如果B更大,那么可以将字符串拆分成多个组,每个组包含多个字符,一组字符可以连在一起看成一个整数。然后,将每组字符对应的整数求和之后对B取模。比如,如果B在10亿上下或者说230,那么每四个字符合成一组对应一个32位的整数,多个32位整数的求和结果将会相当均匀地分配到10亿个桶中去。
? 对于更复杂的数据类型,可以对上述字符串转化为整数的思路进行扩展来递归式处理。
? 对于记录型数据,记录中每个字段都有自己的类型,那么可以采用适合该类型的算法将每个字段递归地转换成整数,然后将所有字段转换出的整数求和,*后对B取模来将整数分配到不同桶中去。
? 对于数组型、集合型或包(bag)型数据,数据中的每一个元素都是相同类型。可以先将每个元素的值转换成整数,然后求和并对B取模。
1.3.3 索引
给定某种对象的一个或多个元素值,索引是一种能够支持对象**查找的数据结构。*常见的一种情况是对象都是记录,而索引按照记录中的某个字段来建立。给定该字段的值v,基于索引能够快速返回该字段值等于v的所有记录。例如,假定有一个由一系列三元组<姓名, 地址, 电话号码>组成的档案记录表以及基于电话号码字段建立的索引。当给定一个电话号码时,基于索引就能快速找到包含该号码的一条或者多条记录。
实现索引的方法有很多,这里并不打算给出全面的介绍。参考文献部分给出了扩展阅读的建议。但是,哈希表是一种简单的索引构建方法。哈希函数的输入键是用于建立索引的一个或者多个字段。对于某条记录来说,哈希函数会基于其中哈希键的值进行计算,然后将整条记录分配到某个桶中,而桶的号码取决于哈希函数的结果。举例来说,这里的桶可以是内存或磁盘块中的一个记录表。
于是,给定一个哈希键值,我们可以先求哈希函数的值,然后根据该值寻找相应的桶,*后只须在该桶中寻找包含给定哈希键值的记录即可。如果我们选取的桶数目B和档案中所有记录的数目大体相当,那么分配到每个桶的记录数目都会较小,这样在桶内部的搜索速度就会很快。
例1.5 图1-2给出了包含姓名(name)、地址(address)和电话号码(phone)字段的记录的内存索引结构的大概样子。这里,索引基于电话号码字段构建,而桶采用链表结构。图中展示电话号码800-555-1212所对应的哈希到桶号码为17。对于桶头(bucket header)构成的数组,其第i个元素实际上是第i个桶对应链表的头指针。图中展开了链表中的一个元素,它包含姓名、地址和电话号码字段的一条记录。事实上,该元素对应记录包含的电话号码正好是800-555-1212,但是该桶中的其他记录可能包含也可能不包含这个电话号码,我们只知道这些记录中的电话号码经过哈希变换之后结果都是17。

图1-2 一个使用哈希表的索引,其中电话号码经过哈希函数映射到不同桶中,
桶的编号就是哈希结果值
1.3.4 二级存储器
当处理大规模数据时,数据一开始在磁盘还是在内存那么计算的时间开销相差很大,很好地理解这一点相当重要。磁盘的物理特性是另外一个话题,对于这个话题有说不完的内容,但是本书当中只给出一点点介绍,感兴趣的读者可以按照参考文献的提示查阅相关资料。
磁盘组织成块结构,每个块是操作系统用于在内存和磁盘之间传输数据的*小单元。例如,Windows操作系统使用的块大小为64 KB(即216=65 536字节)。需要大概10毫秒的时间来访问(将磁头移到块所在的磁道并等待在该磁头下进行块旋转)和读取一个磁盘块。相对于从内存中读取一个字的时间,磁盘的读取延迟大概要慢5个数量级(即存在因子105)。因此,如果只需要访问若干字节,那么将数据放在内存中将具压倒性优势。实际上,假如我们要对一个磁盘块中的每个字节做简单的处理,比如,将块看成哈希表中的桶,我们要在桶的所有记录当中寻找某个特定的哈希键值,那么将块从磁盘移到内存的时间会大大高于计算的时间。
我们可以将相关的数据组织到磁盘的单个柱面(cylinder)上,因为所有的块集合都可以在磁盘**的固定半径内可达,因此可以不通过移动磁头就可以访问,这样可以以每块显著小于10ms的速度将柱面上的所有块读入内存。假设不论数据采用何种磁盘组织方式,磁盘上数据到内存的传送速度不可能超过100 MB/s。当数据集规模仅为1 MB时,这不是个问题,但是,当数据集在100 GB或者1 TB规模时,仅仅进行访问就存在问题,更何况还要利用它来做其他有用的事情了。
1.3.5 自然对数的底e
常数e = 2.718 281 8 ? ? ? 具有一些非常有用的特性。具体来讲,e是当x趋向于无穷大时,的极限。当x分别等于1、2、3和4时,上式的值分别近似为2、2.25、2.37和2.44,很容易相信该序列的极限大概在2.72左右。
一些看上去比较复杂的表达式可以通过代数公式来得到近似值。考虑(1+a)b,其中a很小(a > 0)。该式子可以重写成(1+a)(1/a)(ab),于是可以将a替换为1/x,即x=1/a,得到 ,即

由于已经假定a很小,所以x很大,因此 接近极限e,于是上式可以通过eab来近似。
当a为负值时,类似的等式也成立。也就是说,当x趋向无穷大时,的极限为1/e。于是,当a是一个**值很小的负数时,(1+a)b仍然近似等于eab。换句话说,当a很小b很大时(a > 0),(1?a)b近似等于e?ab。
一些其他有用的等式来自ex的泰勒展开公式,即ex= 或者说ex=1+x+x2/2+x3/6+ x4/24+…。当x很大时,上述数列收敛速度较慢。当然对于任何常数x,由于n!会比xn增长得快得多,所以该数列一定会收敛。然而,当x较小时,不论它是正是负,上述数列都会快速收敛,也就是说不需要计算太多项就可以得到较好的近似值。
例1.6 令x=1/2,有
e1/2 = 1 +1/2+1/8+1/48+1/384+…
或约为e1/2=1.648 44
令x = ?1,有
e?1 = 1 ? 1 +1/2?1/6+1/24?1/120+1/720?1/5040+…
或约为e?1=0.367 86。
1.3.6 幂定律
在很多现象中,两个变量之间通过幂定律(power law,也称幂律)关联起来,也就是说,两个变量在对数空间下呈现出线性关系。图1-3给出了这样的一种关系。该图中横坐标x和纵坐标y之间的关系为log10y = 6?2log10x。

图1-3 一个斜率为?2的幂定律关系图
例1.7 我们来考察Amazon.com上的图书销售情况,令x表示图书的**排名,y对应的是销售排名为x的畅销图书在某个时间段的**。图1-3表明,销售排行第1位的图书的**是1 000 000册,而排行第10位的图书的**为10 000册,排行第100位的图书**为100册,以此类推可以得出排名中所有图书的**。从图中可以看到,排名超过1000的图书的**是一个分数,这有些**,实际上我们预测排名远远超过1000的图书**的曲线应该变得比较平。
马太效应
当幂值大于1时,幂定律的存在往往通过马太效应(Matthew effect)来解释,在《圣经?马太福音》中,存在关于“富者越富”的一段话。很多现象都表现出类似特性,即一旦在某个特性获得高价值,那么会导致该特性获得更大的价值。例如,如果某个Web网页有很多入链,那么人们更可能找到该网页并从他们自己的某个网页链向它。另一个例子是,如果一本书在Amazon上卖得很好,那么它很可能会登广告,而当顾客访问Amazon网站时会看到这则广告,其中的一些人会选择购买这本书,从而造成**的继续增长。
关于x和y的幂定律的一般形式为log y = b+ a log x,如果增大对数的底(实际上没有影响),比如采用自然对数e作为方程两边的值,则有y = ebealog x = ebxa,由于eb是一个常数,所以可以用常数c代替,于是幂定律可以写成y = cxa ,其中a和c都是常数。
例1.8 在图1-3中,当x = 1时y = 106,当x = 1000时y = 1。**次代入后有106 = c ,第二次代入后有1 = c(1000)a,我们知道c = 106 ,通过第二次代入后,得出1=106(1000)a,于是 a=?2。也就是说,图1-3表示的幂定律可以表示为 y = 106x?2或 y = 106/x2。
本书中将有多处数据都满足幂定律,举例如下。
(1) Web图当中节点的度 按照网页的入链数对所有网页排序,令x为网页在排序结果的序
号,y为序号为x的网页的入链数。则y和x之间的关系和图1-3非常类似,只是这里的幂要稍大于图中的幂?2,已经发现在这种现象中的幂值接近2.1。
(2) 商品的** 将商品(如Amazon.com上的图书)按照去年一年的**多少来排序,假定**第x位的商品的实际**为y。那么y和x的函数关系和图1-3也类似。在9.1.2节中,我们将讨论这种**分布的影响,那时我们还会提到其中的“长尾”现象。
(3) Web网站的大小 计算Web站点上的网页数目,根据该数目对网站排序。假定第x个网站的网页数目为y,那么函数y(x)也服从幂定律。
(4) Zipf定律 该幂定律*初来源于文档集中的词频统计。如果将词语按照出现频率排序,y表示排名第x位的词出现的次数,则可以得到一个幂定律,不过其坡度比图1-3的要平缓得多。Zipf的观察结果为y = cx?1/2。有趣的是,有不少其他类型的数据也满足这个特定的幂定律。比如,如果将美国的州按照人口数量排序,令y为人口第x多的州的人口数,则y和x近似地满足Zipf定律。
1.3.7 习题
习题1.3.1 假定一个由1000万篇文档组成的文档集,如果单词出现在(a) 40篇或(b)10 000篇文档中,那么它的IDF值是多少(给出*接近的整数值)?
习题1.3.2 假定一个由1000万篇文档组成的文档集,某个词w出现在其中的320篇文档中。且在一篇具体的文档d中,出现*多的词出现了15次,那么w出现(a) 1次或(b) 5次情况下的TF.IDF得分分别是多少?
!习题1.3.3 假定哈希键都来自某个常数c的所有非负整数倍,而哈希函数为h(x)= x mod 15,那么常数c取何值时,h是一个合适的哈希函数?也就是说,此时大量随机的哈希键选择能够近乎均匀地分到不同桶当中。
习题1.3.4 基于e的形式来近似表示下列数值。
(a) (1.01)500 (b) (1.05)1000 (c) (0.9)40
习题1.3.5 采用ex的泰勒展开公式计算下列表达式直到小数点后3位小数。
(a) e1/10 (b)e?1/10 (c) e2

大数据时代的及时雨
全球**数据库技术专家*新力作
理论与实际算法实现并重

Anand Rajaraman 数据库和Web技术领域权威,创业投资基金Cambrian联合创始人,斯坦福大学计算机科学系助理教授。Rajaraman职业生涯非常成功:1996年创办Junglee公司,两年后该公司被亚马逊以2.5亿美元收购,Rajaraman被聘为亚马逊技术总监,推动亚马逊从一个零售商转型为零售平台;2000年与人合创Cambrian,孵化出几个后来被谷歌收购的公司;2005年创办Kosmix公司并任CEO,该公司2011年被沃尔玛集团收购。Rajaraman生于印度,在斯坦福大学获得计算机科学硕士和博士学位。求学期间与人合著的一篇论文荣列近20年来被引用次数*多的论文之一。博客地址http://anand.typepad.com/datawocky/。 Jeffrey David Ullman 美国**工程院院士,计算机科学家,斯坦福大学教授。Ullman早年在贝尔实验室工作,之后任教于普林斯顿大学,十年后加入斯坦福大学直至退休,一生的科研、著书和育人成果**。他是ACM会员,曾获SIGMOD贡献奖、Knuth奖等多项科研大奖;他是“龙书”《编译原理》、数据库领域权威指南《数据库系统实现》的合著者;麾下多名学生成为了数据库领域的专家,其中*有名的当属谷歌创始人Sergey Brin;本书**作者也是他的得意弟子。Ullman目前任Gradiance公司CEO。 译者简介:
王斌 博士,中国科学院计算技术研究所博士生导师。中国科学院信息工程研究所客座研究员。主要研究方向为信息检索、自然语言处理和数据挖掘。《信息检索导论》译者。主持**973、863、**自然科学基金、国际合作基金、**支撑计划等课题20余项,发表学术论文120余篇。现为ACM会员、中国中文信息学会理事、中文信息学会信息检索专委会委员、《中文信息学报》编委、中国计算机学会**会员及计算机学会中文信息处理专委会委员。自2006年起在中国科学院研究生院(现改名“中国科学院大学”)讲授《现代信息检索》研究生课程,选课人数累计近千人。2010年开始指导研究生,迄今培养博士、硕士研究生30余名。