大数据 互联网大规模数据挖掘与分布式处理 第2版PDF|Epub|txt|kindle电子书版本网盘下载

大数据 互联网大规模数据挖掘与分布式处理 第2版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

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

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 MapReduce19

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

3.2.1 k-shingle58

3.2.2 shingle大小的选择59

3.2.3 对shingle进行哈希59

3.2.4 基于词的shingle60

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

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 PageRank126

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

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 TrustRank148

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算法和MapReduce179

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 RMSE255

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 Simrank290

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 基于梯度下降法求解SVM359

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