大数据：互联网大规模数据挖掘与分布式处理 PDF 第2版

大数据-互联网大规模数据挖掘与分布式处理(第2版)由斯坦福大学“Web 挖掘”课程的内容总结而成，主要关注极大规模数据的挖掘。主要内容包括分布式文件系统、相似性搜索、搜索引擎技术、频繁项集挖掘、聚类算法、广告管理及推荐系统、社会网络图挖掘和大规模机器学习等。其中每一章节有对应的习题，以巩固所讲解的内容。读者更可以从网上获取相关拓展材料。

目录

• 第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 二级存储器　　9
• 1.3.5 自然对数的底e　　10
• 1.3.6 幂定律　　11
• 1.3.7 习题　　12
• 1.4 本书概要　　13
• 1.5 小结　　14
• 1.6 参考文献　　15
• 第2章 MapReduce及新软件栈　　16
• 2.1 分布式文件系统　　17
• 2.1.1 计算节点的物理结构　　17
• 2.1.2 大规模文件系统的结构　　18
• 2.2 MapReduce　　19
• 2.2.1 Map任务　　20
• 2.2.2 按键分组　　20
• 2.2.3 Reduce任务　　21
• 2.2.4 组合器　　21
• 2.2.5 MapReduce的执行细节　　22
• 2.2.6 节点失效的处理　　23
• 2.2.7 习题　　23
• 2.3 使用MapReduce的算法　　23
• 2.3.1 基于MapReduce的矩阵—向量乘法实现　　24
• 2.3.2 向量v无法放入内存时的处理　　 24
• 2.3.3 关系代数运算　　25
• 2.3.4 基于MapReduce的选择运算27
• 2.3.5 基于MapReduce的投影运算27
• 2.3.6 基于MapReduce的并、交和差运算　　28
• 2.3.7 基于MapReduce的自然连接运算　　28
• 2.3.8 基于MapReduce的分组和聚合运算　　29
• 2.3.9 矩阵乘法　　29
• 2.3.10 基于单步MapReduce的矩阵乘法　　30
• 2.3.11 习题　　31
• 2.4 MapReduce的扩展　　31
• 2.4.1 工作流系统　　32
• 2.4.2 MapReduce的递归扩展版本.33
• 2.4.3 Pregel系统　　35
• 2.4.4 习题　　35
• 2.5 通信开销模型　　36
• 2.5.1 任务网络的通信开销　　36
• 2.5.2 时钟时间　　37
• 2.5.3 多路连接　　38
• 2.5.4 习题　　41
• 2.6 MapReduce复杂性理论　　41
• 2.6.1 Reducer规模及复制率　　41
• 2.6.2 一个例子：相似性连接　　42
• 2.6.3 MapReduce问题的一个图模型　　 44
• 2.6.4 映射模式　　45
• 2.6.5 并非所有输入都存在时的处理　　 46
• 2.6.6 复制率的下界　　46
• 2.6.7 案例分析：矩阵乘法　　48
• 2.6.8 习题　　51
• 2.7 小结　　51
• 2.8 参考文献　　53
• 第3章 相似项发现　　55
• 3.1 近邻搜索的应用　　55
• 3.1.1 集合的Jaccard相似度　　55
• 3.1.2 文档的相似度　　56
• 3.1.3 协同过滤——一个集合相似问题　　57
• 3.1.4 习题　　58
• 3.2 文档的shingling　　58
• 3.2.1 k-shingle　　58
• 3.2.2 shingle大小的选择　　59
• 3.2.3 对shingle进行哈希　　59
• 3.2.4 基于词的shingle　　60
• 3.2.5 习题　　60
• 3.3 保持相似度的集合摘要表示　　61
• 3.3.1 集合的矩阵表示　　61
• 3.3.2 最小哈希　　62
• 3.3.3 最小哈希及Jaccard相似度　　62
• 3.3.4 最小哈希签名　　63
• 3.3.5 最小哈希签名的计算　　63
• 3.3.6 习题　　66
• 3.4 文档的局部敏感哈希算法　　67
• 3.4.1 面向最小哈希签名的LSH　　67
• 3.4.2 行条化策略的分析　　68
• 3.4.3 上述技术的综合　　69
• 3.4.4 习题　　70
• 3.5 距离测度　　70
• 3.5.1 距离测度的定义　　71
• 3.5.2 欧氏距离　　71
• 3.5.3 Jaccard距离　　72
• 3.5.4 余弦距离　　72
• 3.5.5 编辑距离　　73
• 3.5.6 海明距离　　74
• 3.5.7 习题　　74
• 3.6 局部敏感函数理论　　75
• 3.6.1 局部敏感函数　　76
• 3.6.2 面向Jaccard距离的局部敏感函数族　　77
• 3.6.3 局部敏感函数族的放大处理.77
• 3.6.4 习题　　79
• 3.7 面向其他距离测度的LSH函数族　　80
• 3.7.1 面向海明距离的LSH函数族　　 80
• 3.7.2 随机超平面和余弦距离　　80
• 3.7.3 梗概　　81
• 3.7.4 面向欧氏距离的LSH函数族　　 82
• 3.7.5 面向欧氏空间的更多LSH函数族　　83
• 3.7.6 习题　　83
• 3.8 LSH 函数的应用　　84
• 3.8.1 实体关联　　84
• 3.8.2 一个实体关联的例子　　85
• 3.8.3 记录匹配的验证　　86
• 3.8.4 指纹匹配　　87
• 3.8.5 适用于指纹匹配的LSH函数族　　87
• 3.8.6 相似新闻报道检测　　88
• 3.8.7 习题　　89
• 3.9 面向高相似度的方法　　90
• 3.9.1 相等项发现　　90
• 3.9.2 集合的字符串表示方法　　91
• 3.9.3 基于长度的过滤　　91
• 3.9.4 前缀索引　　92
• 3.9.5 位置信息的使用　　93
• 3.9.6 使用位置和长度信息的索引.94
• 3.9.7 习题　　96
• 3.10 小结　　97
• 3.11 参考文献　　98
• 第4章 数据流挖掘　　100
• 4.1 流数据模型　　100
• 4.1.1 一个数据流管理系统　　100
• 4.1.2 流数据源的例子　　101
• 4.1.3 流查询　　102
• 4.1.4 流处理中的若干问题　　103
• 4.2 流当中的数据抽样　　103
• 4.2.1 一个富于启发性的例子　　104
• 4.2.2 代表性样本的获取　　104
• 4.2.3 一般的抽样问题　　105
• 4.2.4 样本规模的变化　　105
• 4.2.5 习题　　106
• 4.3 流过滤　　106
• 4.3.1 一个例子　　106
• 4.3.2 布隆过滤器　　107
• 4.3.3 布隆过滤方法的分析　　107
• 4.3.4 习题　　108
• 4.4 流中独立元素的数目统计　　109
• 4.4.1 独立元素计数问题　　109
• 4.4.2 FM 算法　　109
• 4.4.3 组合估计　　110
• 4.4.4 空间需求　　111
• 4.4.5 习题　　111
• 4.5 矩估计　　111
• 4.5.1 矩定义　　111
• 4.5.2 二阶矩估计的AMS算法　　112
• 4.5.3 AMS算法有效的原因　　113
• 4.5.4 更高阶矩的估计　　113
• 4.5.5 无限流的处理　　114
• 4.5.6 习题　　115
• 4.6 窗口内的计数问题　　116
• 4.6.1 精确计数的开销　　116
• 4.6.2 DGIM算法　　116
• 4.6.3 DGIM算法的存储需求　　118
• 4.6.4 DGIM算法中的查询应答　　118
• 4.6.5 DGIM条件的保持　　119
• 4.6.6 降低错误率　　120
• 4.6.7 窗口内计数问题的扩展　　120
• 4.6.8 习题　　121
• 4.7 衰减窗口　　121
• 4.7.1 最常见元素问题　　121
• 4.7.2 衰减窗口的定义　　122
• 4.7.3 最流行元素的发现　　123
• 4.8 小结　　123
• 4.9 参考文献　　124
• 第5章 链接分析　　126
• 5.1 PageRank　　126
• 5.1.1 早期的搜索引擎及词项作弊　　 126
• 5.1.2 PageRank 的定义　　128
• 5.1.3 Web结构　　130
• 5.1.4 避免终止点　　132
• 5.1.5 采集器陷阱及“抽税”法　　134
• 5.1.6 PageRank 在搜索引擎中的使用　　136
• 5.1.7 习题　　136
• 5.2 PageRank的快速计算　　137
• 5.2.1 转移矩阵的表示　　137
• 5.2.2 基于MapReduce的PageRank迭代计算　　138
• 5.2.3 结果向量合并时的组合器使用　　139
• 5.2.4 转移矩阵中块的表示　　140
• 5.2.5 其他高效的PageRank迭代方法　　141
• 5.2.6 习题　　142
• 5.3 面向主题的PageRank　　142
• 5.3.1 动机　　142
• 5.3.2 有偏的随机游走模型　　143
• 5.3.3 面向主题的PageRank 的使用　　 144
• 5.3.4 基于词汇的主题推断　　144
• 5.3.5 习题　　145
• 5.4 链接作弊　　145
• 5.4.1 垃圾农场的架构　　145
• 5.4.2 垃圾农场的分析　　147
• 5.4.3 与链接作弊的斗争　　147
• 5.4.4 TrustRank　　148
• 5.4.5 垃圾质量　　148
• 5.4.6 习题　　149
• 5.5 导航页和权威页　　149
• 5.5.1 HITS的直观意义　　150
• 5.5.2 导航度和权威度的形式化　　150
• 5.5.3 习题　　153
• 5.6 小结　　153
• 5.7 参考文献　　155
• 第6章 频繁项集　　157
• 6.1 购物篮模型　　157
• 6.1.1 频繁项集的定义　　157
• 6.1.2 频繁项集的应用　　159
• 6.1.3 关联规则　　160
• 6.1.4 高可信度关联规则的发现　　161
• 6.1.5 习题　　162
• 6.2 购物篮及A-Priori算法　　163
• 6.2.1 购物篮数据的表示　　163
• 6.2.2 项集计数中的内存使用　　164
• 6.2.3 项集的单调性　　165
• 6.2.4 二元组计数　　166
• 6.2.5 A-Priori算法　　166
• 6.2.6 所有频繁项集上的A-Priori算法　　168
• 6.2.7 习题　　169
• 6.3 更大数据集在内存中的处理　　170
• 6.3.1 PCY算法　　171
• 6.3.2 多阶段算法　　172
• 6.3.3 多哈希算法　　174
• 6.3.4 习题　　175
• 6.4 有限扫描算法　　177
• 6.4.1 简单的随机化算法　　177
• 6.4.2 抽样算法中的错误规避　　178
• 6.4.3 SON算法　　179
• 6.4.4 SON算法和MapReduce　　179
• 6.4.5 Toivonen算法　　180
• 6.4.6 Toivonen算法的有效性分析　　 181
• 6.4.7 习题　　181
• 6.5 流中的频繁项计数　　182
• 6.5.1 流的抽样方法　　182
• 6.5.2 衰减窗口中的频繁项集　　183
• 6.5.3 混合方法　　183
• 6.5.4 习题　　184
• 6.6 小结　　184
• 6.7 参考文献　　186
• 第7章 聚类　　187
• 7.1 聚类技术介绍　　187
• 7.1.1 点、空间和距离　　187
• 7.1.2 聚类策略　　188
• 7.1.3 维数灾难　　189
• 7.1.4 习题　　190
• 7.2 层次聚类　　190
• 7.2.1 欧氏空间下的层次聚类　　191
• 7.2.2 层次聚类算法的效率　　194
• 7.2.3 控制层次聚类的其他规则　　194
• 7.2.4 非欧空间下的层次聚类　　196
• 7.2.5 习题　　197
• 7.3 k-均值算法　　198
• 7.3.1 k-均值算法基本知识　　198
• 7.3.2 k-均值算法的簇初始化　　198
• 7.3.3 选择正确的k值　　199
• 7.3.4 BFR算法　　200
• 7.3.5 BFR算法中的数据处理　　202
• 7.3.6 习题　　203
• 7.4 CURE算法　　204
• 7.4.1 CURE算法的初始化　　205
• 7.4.2 CURE算法的完成　　206
• 7.4.3 习题　　206
• 7.5 非欧空间下的聚类　　207
• 7.5.1 GRGPF算法中的簇表示　　207
• 7.5.2 簇表示树的初始化　　207
• 7.5.3 GRGPF算法中的点加入　　208
• 7.5.4 簇的分裂及合并　　209
• 7.5.5 习题　　210
• 7.6 流聚类及并行化　　210
• 7.6.1 流计算模型　　210
• 7.6.2 一个流聚类算法　　211
• 7.6.3 桶的初始化　　211
• 7.6.4 桶合并　　211
• 7.6.5 查询应答　　213
• 7.6.6 并行环境下的聚类　　213
• 7.6.7 习题　　214
• 7.7 小结　　214
• 7.8 参考文献　　216
• 第8章 Web广告　　218
• 8.1 在线广告相关问题　　218
• 8.1.1 广告机会　　218
• 8.1.2 直投广告　　219
• 8.1.3 展示广告的相关问题　　219
• 8.2 在线算法　　220
• 8.2.1 在线和离线算法　　220
• 8.2.2 贪心算法　　221
• 8.2.3 竞争率　　222
• 8.2.4 习题　　222
• 8.3 广告匹配问题　　223
• 8.3.1 匹配及完美匹配　　223
• 8.3.2 最大匹配贪心算法　　224
• 8.3.3 贪心匹配算法的竞争率　　224
• 8.3.4 习题　　225
• 8.4 adwords问题　　225
• 8.4.1 搜索广告的历史　　226
• 8.4.2 adwords问题的定义　　226
• 8.4.3 adwords问题的贪心方法　　227
• 8.4.4 Balance算法　　228
• 8.4.5 Balance算法竞争率的一个下界　　228
• 8.4.6 多投标者的Balance算法　　230
• 8.4.7 一般性的Balance算法　　231
• 8.4.8 adwords问题的最后论述　　232
• 8.4.9 习题　　232
• 8.5 adwords的实现　　232
• 8.5.1 投标和搜索查询的匹配　　233
• 8.5.2 更复杂的匹配问题　　233
• 8.5.3 文档和投标之间的匹配算法　　 234
• 8.6 小结　　235
• 8.7 参考文献　　237
• 第9章 推荐系统　　238
• 9.1 一个推荐系统的模型　　238
• 9.1.1 效用矩阵　　238
• 9.1.2 长尾现象　　239
• 9.1.3 推荐系统的应用　　241
• 9.1.4 效用矩阵的填充　　241
• 9.2 基于内容的推荐　　242
• 9.2.1 项模型　　242
• 9.2.2 文档的特征发现　　242
• 9.2.3 基于Tag的项特征获取　　243
• 9.2.4 项模型的表示　　244
• 9.2.5 用户模型　　245
• 9.2.6 基于内容的项推荐　　246
• 9.2.7 分类算法　　247
• 9.2.8 习题　　248
• 9.3 协同过滤　　249
• 9.3.1 相似度计算　　249
• 9.3.2 相似度对偶性　　252
• 9.3.3 用户聚类和项聚类　　253
• 9.3.4 习题　　254
• 9.4 降维处理　　254
• 9.4.1 UV分解　　255
• 9.4.2 RMSE　　255
• 9.4.3 UV分解的增量式计算　　256
• 9.4.4 对任一元素的优化　　259
• 9.4.5 一个完整UV 分解算法的构建　　259
• 9.4.6 习题　　261
• 9.5 NetFlix竞赛　　262
• 9.6 小结　　263
• 9.7 参考文献　　264
• 第10章 社会网络图挖掘　　265
• 10.1 将社会网络看成图　　265
• 10.1.1 社会网络的概念　　265
• 10.1.2 将社会网络看成图　　266
• 10.1.3 各种社会网络的例子　　267
• 10.1.4 多类型节点构成的图　　268
• 10.1.5 习题　　269
• 10.2 社会网络图的聚类　　269
• 10.2.1 社会网络图的距离计算　　269
• 10.2.2 应用标准的聚类算法　　270
• 10.2.3 中介度　　271
• 10.2.4 Girvan-Newman算法　　271
• 10.2.5 利用中介度来发现社区　　274
• 10.2.6 习题　　275
• 10.3 社区的直接发现　　275
• 10.3.1 团的发现　　276
• 10.3.2 完全二部图　　276
• 10.3.3 发现完全二部子图　　277
• 10.3.4 完全二部子图一定存在的原因　　277
• 10.3.5 习题　　279
• 10.4 图划分　　280
• 10.4.1 图划分的好坏标准　　280
• 10.4.2 归一化割　　280
• 10.4.3 描述图的一些矩阵　　281
• 10.4.4 拉普拉斯矩阵的特征值　　282
• 10.4.5 其他图划分方法　　284
• 10.4.6 习题　　284
• 10.5 重叠社区的发现　　285
• 10.5.1 社区的本质　　285
• 10.5.2 极大似然估计　　286
• 10.5.3 关系图模型　　287
• 10.5.4 避免成员隶属关系的离散式变化　　288
• 10.5.5 习题　　290
• 10.6 Simrank　　290
• 10.6.1 社会网络上的随机游走者　　 290
• 10.6.2 带重启的随机游走　　291
• 10.6.3 习题　　293
• 10.7 三角形计数问题　　293
• 10.7.1 为什么要对三角形计数　　294
• 10.7.2 一个寻找三角形的算法　　294
• 10.7.3 三角形寻找算法的最优性　　 295
• 10.7.4 基于MapReduce寻找三角形　　295
• 10.7.5 使用更少的Reduce任务.297
• 10.7.6 习题　　297
• 10.8 图的邻居性质　　298
• 10.8.1 有向图和邻居　　298
• 10.8.2 图的直径　　299
• 10.8.3 传递闭包和可达性　　300
• 10.8.4 基于MapReduce的传递闭包求解　　301
• 10.8.5 智能传递闭包　　303
• 10.8.6 基于图归约的传递闭包　　304
• 10.8.7 邻居规模的近似计算　　305
• 10.8.8 习题　　306
• 10.9 小结　　307
• 10.10 参考文献　　310
• 第11章 降维处理　　312
• 11.1 特征值和特征向量　　312
• 11.1.1 定义　　312
• 11.1.2 特征值与特征向量计算　　313
• 11.1.3 基于幂迭代方法的特征对求解　　315
• 11.1.4 特征向量矩阵　　317
• 11.1.5 习题　　317
• 11.2 主成分分析　　318
• 11.2.1 一个示例　　318
• 11.2.2 利用特征向量进行降维　　321
• 11.2.3 距离矩阵　　322
• 11.2.4 习题　　323
• 11.3 奇异值分解　　323
• 11.3.1 SVD的定义　　323
• 11.3.2 SVD解析　　325
• 11.3.3 基于SVD的降维　　326
• 11.3.4 将较低奇异值置为0后有效的原因　　327
• 11.3.5 使用概念进行查询处理　　328
• 11.3.6 矩阵SVD的计算　　329
• 11.3.7 习题　　330
• 11.4 CUR 分解　　331
• 11.4.1 CUR 的定义　　331
• 11.4.2 合理选择行和列　　332
• 11.4.3 构建中间矩阵　　333
• 11.4.4 完整的CUR 分解　　334
• 11.4.5 去除重复行和列　　335
• 11.4.6 习题　　335
• 11.5 小结　　336
• 11.6 参考文献　　337
• 第12章 大规模机器学习　　338
• 12.1 机器学习模型　　338
• 12.1.1 训练集　　338
• 12.1.2 一些例子　　339
• 12.1.3 机器学习方法　　341
• 12.1.4 机器学习架构　　342
• 12.1.5 习题　　344
• 12.2 感知机　　344
• 12.2.1 训练阈值为0 的感知机　　344
• 12.2.2 感知机的收敛性　　347
• 12.2.3 Winnow算法　　347
• 12.2.4 允许阈值变化的情况　　349
• 12.2.5 多类感知机　　350
• 12.2.6 变换训练集　　351
• 12.2.7 感知机的问题　　351
• 12.2.8 感知机的并行实现　　353
• 12.2.9 习题　　354
• 12.3 支持向量机　　354
• 12.3.1 支持向量机的构成　　354
• 12.3.2 超平面归一化　　356
• 12.3.3 寻找最优逼近分界面　　357
• 12.3.4 基于梯度下降法求解SVM　　 359
• 12.3.5 随机梯度下降　　363
• 12.3.6 SVM的并行实现　　363
• 12.3.7 习题　　363
• 12.4 近邻学习　　364
• 12.4.1 近邻计算的框架　　364
• 12.4.2 最近邻学习　　365
• 12.4.3 学习一维函数　　365
• 12.4.4 核回归　　367
• 12.4.5 处理高维欧氏空间数据　　368
• 12.4.6 对非欧距离的处理　　369
• 12.4.7 习题　　369
• 12.5 各种学习方法的比较　　370
• 12.6 小结　　371
• 12.7 参考文献　　372