Mining-of-Massive-Datasets

字数统计: 3.1k字 | 阅读时长: 11分

2021-04-28

摘要: 本文介绍一本书《斯坦福数据挖掘教程》

【对数据分析、人工智能、金融科技、风控服务感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：潮汐朝夕
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

本书资料

主页: Mining of Massive Datasets
Stanford big data courses
- CS246: Mining Massive Data Sets, graduate level course that discusses data mining and machine learning algorithms for analyzing very large amounts of data. The emphasis is on Map Reduce as a tool for creating parallel algorithms that can process very large amounts of data.
- CS341: Project in Mining Massive Data Sets, an advanced project based course.
- CS224W: Social and Information Networks, graduate level course that covers recent research on the structure and analysis of such large social and information networks and on models and algorithms that abstract their basic properties.
- CS345A, Winter 2009: Data Mining
电子版: Mining of Massive Datasets
图灵社区翻译: 斯坦福数据挖掘教程（第3版）

数据挖掘基本概念　　

数据挖掘的定义　
- 建模　
- 统计建模　
- 机器学习　
- 建模的计算方法　
- 数据概括　
- 特征抽取　
数据挖掘的统计限制　
- 整体情报预警　
- 邦弗朗尼原理　
- 邦弗朗尼原理的一个例子　
相关知识　
- 词语在文档中的重要性　
- 哈希函数　
- 索引　
- 二级存储器　
- 自然对数的底e　
- 幂定律

MapReduce和新软件栈　

分布式文件系统　
- 计算节点的物理结构　
- 大规模文件系统的结构　
MapReduce　
- Map任务　
- 按键分组　
- Reduce任务　
- 组合器　
- MapReduce的执行细节　
- 节点故障的处理　
使用MapReduce的算法　
- 基于MapReduce的矩阵—向量乘法实现　
- 向量v无法放入内存时的处理　
- 基于MapReduce的选择运算　
- 基于MapReduce的投影运算　
- 基于MapReduce的并、交和差运算　
- 基于MapReduce的自然连接运算　
- 基于MapReduce的分组和聚合运算　
- 矩阵乘法　
- 基于单步MapReduce的矩阵乘法　
MapReduce的扩展　
- 工作流系统　
- Spark　
- Spark实现　
- TensorFlow　
- MapReduce的递归扩展版本　
- 整体同步系统　
通信开销模型　
- 任务网络的通信开销　
- 时钟时间　
- 多路连接　
MapReduce复杂性理论　
- Reducer规模及复制率　
- 一个例子：相似性连接　
- MapReduce问题的一个图模型　
- 并非所有输入都存在时的处理　
- 案例分析：矩阵乘法

相似项发现　

集合相似度的应用　
- 集合的Jaccard相似度　
- 文档的相似度　
- 协同过滤——一个集合相似问题　
文档的shingling　
- k-shingle　
- shingle大小的选择　
- 对shingle进行哈希　
- 基于词的shingle　
保持相似度的集合摘要表示　
- 集合的矩阵表示　
- 最小哈希　
- 最小哈希和Jaccard相似度　
- 最小哈希签名　
- 最小哈希签名的计算　
- 对最小哈希加速　
- 使用哈希加速　
文档的局部敏感哈希算法　
- 面向最小哈希签名的LSH　
- 行条化策略的分析　
- 上述技术的综合　
距离测度　
- 距离测度的定义　
- 欧氏距离　
- Jaccard 距离　
- 余弦距离　
- 编辑距离　
- 海明距离　
局部敏感函数理论　
- 局部敏感函数　
- 面向Jaccard距离的局部敏感函数族　
- 局部敏感函数族的放大处理　
面向其他距离测度的LSH函数族　
- 面向海明距离的LSH函数族　
- 随机超平面和余弦距离　
- 梗概　
- 面向欧氏距离的LSH函数族　
- 面向欧氏空间的更多LSH函数族　
LSH函数的应用　
- 实体关联　
- 一个实体关联的例子　
- 记录匹配的验证　
- 指纹匹配　
- 适用于指纹匹配的LSH函数族　
面向高相似度的方法　
- 相等项发现　
- 集合的字符串表示方法　
- 基于长度的过滤　
- 前缀索引　
- 位置信息的使用　
- 使用位置和长度信息的索引

数据流挖掘　

流数据模型　
- 一个数据流管理系统　
- 流数据源的例子　
- 流查询　
- 流处理中的若干问题　
流当中的数据抽样　
- 一个富有启发性的例子　
- 代表性样本的获取　
- 一般的抽样问题　
- 样本规模的变化　
流过滤　
- 一个例子　
- 布隆过滤器　
- 布隆过滤方法的分析　
流中独立元素的数目统计　
- 独立元素计数问题　
- FM算法　
- 组合估计　
- 空间需求　
矩估计　
- 矩定义　
- 二阶矩估计的AMS算法　
- AMS算法有效的原因　
- 更高阶矩的估计　
- 无限流的处理　
窗口内的计数问题　
- 精确计数的开销　
- DGIM算法　
- DGIM算法的存储需求　
- DGIM算法中的查询应答　
- DGIM条件的保持　
- 降低错误率　
- 窗口内计数问题的扩展　
衰减窗口　
- 最常见元素问题　
- 衰减窗口的定义　
- 最流行元素的发现

链接分析　

PageRank　
- 早期的搜索引擎及词项作弊　
- PageRank的定义　
- Web结构　
- 避免终止点　
- 采集器陷阱和“抽税”法　
- PageRank在搜索引擎中的使用　
PageRank的快速计算　
- 转移矩阵的表示　
- 基于MapReduce的PageRank迭代计算　
- 结果向量合并时的组合器使用　
- 转移矩阵中块的表示　
- 其他高效的PageRank迭代方法　
面向主题的PageRank　
- 动机　
- 有偏的随机游走模型　
- 面向主题的PageRank的使用　
链接作弊　
- 垃圾农场的架构　
- 垃圾农场的分析　
- 与链接作弊的斗争　
- TrustRank　
- 垃圾质量　
导航页和权威页　
- HITS的直观意义　
- 导航度和权威度的形式化

频繁项集　

购物篮模型　
- 频繁项集的定义　
- 频繁项集的应用　
- 关联规则　
- 高可信度关联规则的发现　
购物篮和A-Priori算法　
- 购物篮数据的表示　
- 项集计数中的内存使用　
- 项集的单调性　
- 二元组计数　
- A-Priori算法　
- 所有频繁项集上的A-Priori算法　
更大数据集在内存中的处理　
- PCY算法　
- 多阶段算法　
- 多哈希算法　
有限扫描算法　
- 简单的随机化算法　
- 抽样算法中的错误规避　
- SON算法　
- SON算法和MapReduce　
- Toivonen算法　
- Toivonen算法的有效性分析　
流中的频繁项计数　
- 流的抽样方法　
- 衰减窗口中的频繁项集　
- 混合方法

聚类　

聚类技术介绍　
- 点、空间和距离　
- 聚类策略　
- 维数灾难　
层次聚类　
- 欧氏空间下的层次聚类　
- 层次聚类算法的效率　
- 控制层次聚类的其他规则　
- 非欧空间下的层次聚类　
k-均值算法　
- k-均值算法基本知识　
- k-均值算法的簇初始化　
- 选择正确的k值　
- BFR算法　
- BFR算法中的数据处理　
CURE算法　
- CURE算法的初始化　
- CURE算法的完成　
非欧空间下的聚类　
- GRGPF算法中的簇表示　
- 簇表示树的初始化　
- GRGPF算法中的点加入　
- 簇的分裂及合并　
流聚类及并行化　
- 流计算模型　
- 一个流聚类算法　
- 桶的初始化　
- 桶合并　
- 查询应答　
- 并行环境下的聚类

Web广告　

在线广告相关问题　
- 广告机会　
- 直投广告　
- 展示广告的相关问题　
在线算法　
- 在线和离线算法　
- 贪心算法　
- 竞争率　
广告匹配问题　
- 匹配及完美匹配　
- 极大匹配贪心算法　
- 贪心匹配算法的竞争率　
adwords问题　
- 搜索广告的历史　
- adwords问题的定义　
- adwords问题的贪心方法　
- Balance算法　
- Balance算法竞争率的一个下界　
- 多投标者的Balance算法　
- 一般性的Balance算法　
- adwords问题的最后论述　
adwords的实现　
- 投标和搜索查询的匹配　
- 更复杂的匹配问题　
- 文档和投标之间的匹配算法

社会网络图挖掘　

将社会网络看成图　
- 社会网络的概念　
- 将社会网络看成图　
- 各种社会网络的例子　
- 多类型节点构成的图　
社会网络图的聚类　
- 社会网络图的距离计算　
- 应用标准的聚类算法　
- 中介度　
- Girvan-Newman算法　
- 利用中介度来发现社区　
社区的直接发现　
- 团的发现　
- 完全二部图　
- 发现完全二部子图　
- 完全二部子图一定存在的原因　
- 习题　
图划分　
- 图划分的好坏标准　
- 归一化割　
- 描述图的一些矩阵　
- 拉普拉斯矩阵的特征值　
- 其他图划分方法　
重叠社区的发现　
- 社区的本质　
- 极大似然估计　
- 关系图模型　
- 社区分配的离散优化　
- 避免成员隶属关系的离散式变化　
Simrank　
- 社会网络上的随机游走者　
- 带重启的随机游走　
- 近似Simrank　
- 近似Simrank有效的原因　
- Simrank在社区发现中的应用　
三角形计数问题.　
- 为什么要对三角形计数　
- 一个寻找三角形的算法　
- 三角形寻找算法的最优性　
- 基于MapReduce寻找三角形　
- 使用更少的Reduce任务　
图的邻居性质　
- 有向图和邻居　
- 图的直径　
- 传递闭包和可达性　
- 基于MapReduce的可达性计算　
- 半朴素求值　
- 线性传递闭包　
- 基于双重递归的传递闭包　
- 智能传递闭包　
- 多种方法的比较　
- 基于图归约的传递闭包　
- 邻居规模的近似计算

降维处理　

特征值和特征向量　
- 定义　
- 特征值与特征向量计算　
- 基于幂迭代方法的特征对求解　
- 特征向量矩阵　
主成分分析　
- 一个示例　
- 利用特征向量进行降维　
- 距离矩阵　
奇异值分解　
- SVD的定义　
- SVD解析　
- 基于SVD的降维　
- 将较低奇异值置为0后有效的原因　
- 使用概念进行查询处理　
- 矩阵SVD的计算　
CUR分解　
- CUR的定义　
- 合理选择行
- 构建中间矩阵　
- 完整的CUR分解　
- 去除重复行和列

大规模机器学习　

机器学习模型　
- 训练集　
- 一些例子　
- 机器学习方法　
- 机器学习架构　
感知机　
- 训练阈值为0的感知机　
- 感知机的收敛性　
- Winnow算法　
- 允许阈值变化的情况　
- 多类感知机　
- 变换训练集　
- 感知机的问题　
- 感知机的并行实现　
支持向量机　
- 支持向量机的机理　
- 超平面归一化　
- 寻找最优逼近分界面　
- 基于梯度下降法求解SVM　
- SVM的并行实现　
近邻学习　
- 近邻计算的框架　
- 最近邻学习　
- 学习一维函数　
- 核回归　
- 处理高维欧氏空间数据　
- 对非欧距离的处理　
决策树　
- 使用决策树　
- 不纯度度量方法　
- 决策树节点的设计　
- 选择基于数值型特征的测试　
- 选择基于分类型特征的测试　
- 决策树的并行设计　
- 节点剪枝　
- 随机森林　
各种学习方法的比较

神经网络与深度学习　

神经网络简介　
- 神经网络概述　
- 节点间的连接　
- 卷积神经网络　
- 神经网络的设计事项　
密集型前馈网络　
- 基于线性代数的记法　
- 激活函数　
- sigmoid函数　
- 双曲正切函数　
- softmax函数　
- 修正线性单元　
- 损失函数　
- 回归损失函数　
- 分类损失函数　
反向传播与梯度下降　
- 计算图　
- 梯度、雅可比矩阵与链式法则　
- 反向传播算法　
- 梯度下降的迭代计算　
- 张量　
卷积神经网络　
- 卷积层　
- 卷积与互相关　
- 池化层　
- CNN架构　
- 实现与训练　
循环神经网络　
- RNN的训练　
- 梯度消失与爆炸　
- 长短期记忆网络　
正则化　
- 范式惩罚　
- dropout　
- 提前停止　
- 数据增强

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

AI业务数据挖掘

Mining-of-Massive-Datasets

本书资料

数据挖掘基本概念

MapReduce和新软件栈

相似项发现

数据流挖掘

链接分析

频繁项集

聚类

Web广告

推荐系统

社会网络图挖掘

降维处理

大规模机器学习

神经网络与深度学习