大数据

目录

第1章　 数据挖掘基本概念1

1.1　 数据挖掘的定义1

1.1.1　 统计建模1

1.1.2　 机器学习1

1.1....

目录

第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　 自然对数的底e10

1.3.6　 幂定律11

1.3.7　 习题12

1.4　 本书概要13

1.5　 小结14

1.6　 参考文献14

第2章　 大规模文件系统及Map-Reduce16

2.1　 分布式文件系统16

2.1.1　 计算节点的物理结构17

2.1.2　 大规模文件系统的结构18

2.2　 Map-Reduce18

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　 文档的Shingling47

3.2.1　 k-Shingle47

3.2.2　 shingle大小的选择48

3.2.3　 对shingle进行哈希48

3.2.4　 基于词的shingle49

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　 面向最小哈希签名的LSH56

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　 PageRank115

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　 面向主题的PageRank131

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　 TrustRank137

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-Reduce168

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　 RMSE244

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

本书是在Anand Rajaraman和Jeff Ullman于斯坦福大学教授多年的一门季度课程的材料基础上总结而成的。该课程名为“Web挖掘”（编号CS345A），尽管它已经成为高年级本科生能接受并感兴趣的课程之一，但其原本是一门为高年级研究生设计的课程。 本书内容 简单来说，本书是关于数据挖掘的。但是，本书主要关注极大规模数据的挖掘，也就是说这些数据大到无法在内存中存放。由于重点强...

(查看全部试读)