《大数据：互联网大规模数据挖掘与分布式处理》

机器学习 读书笔记

前言

该书来源于斯坦福大学的课程（CS345A，Web挖掘）

资料：http://infolab.stanford.edu/~ullman/mining/mining.html
http://www.mmds.org/

第1章 数据挖掘基本概念

1.1 数据挖掘的含义

目前统计学家认为数据挖掘就是统计模型的构建过程（statistical model），而这个统计模型指的是可见数据所遵循的总体分布。

大部分数据建模使用如下两种方法：

• 对数据进行简洁的近似汇总描述；
• 从数据中抽取出最突出的特征来代替数据并将剩余内容忽略；

1.2 数据挖掘的统计限制

邦弗朗尼原理

假定人们有一定量的数据并期望从该数据中找到某个特定类型的事件，即使数据完全随机，也可以期望该类型事件会发生。邦弗朗尼校正定理给出一个统计学上可行的方法来避免在搜索数据时出现的大部分“臆造”的正响应。

例如：如果考察的时间和范围过广，会很容易发现一些人同住一家酒店，而两者没有什么关系。

1.3 相关知识

TF-IDF

词频-逆文档频率，词项i在文档j中的词项频率 $$TF_{ij}={f_{ij}\over \max_k f_{kj}}$$ 词项i在文档集中的ni篇文档中出现，那么词项的IDF如下 $$IDF_i=\log_2{N\over n_i}$$

哈希函数

输入是一个哈希键值，输出是一个桶编号，哈希函数的一个直观性质是其将哈希键值“随机化”。

索引

索引是一种能够支持对象高效查找的数据结构。哈希表是一种简单的索引构建方法。

自然对数的e

e是x趋向无穷大时$(1+{1\over x})^x$的极限，同样$(1-{1\over x})^x$的极限为1/e。
可以利用e来进行计算，如$(1+a)^b$在a很小时可以换为计算$e^{ab}$。
$e^x=\sum_{i=0}^\infty{x^i\over i!}$，该数列一定会收敛，则x较小时，收敛很快。

幂定律

两个变量在对数空间下呈现出线性关系。一般形式 $$\log y=b+a\log x\rightarrow y=e^bx^a\rightarrow y=cx^a$$ 满足幂定律的例子：Web图当中节点的度；商品的销量；Web网站的大小；Zipf定律，文档集的词频统计；

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

2.1 分布式文件系统

集群计算防止故障的办法：

• 文件必须多副本存储；
• 计算过程必须要分成多个任务，任何一个任务失败，即可重启；

分布式文件系统（DFS，Distributed File System）的典型使用方式：

• 文件非常大
• 文件极少更新

2.2 Map-Reduce

基于Map-Reduce的计算过程如下：

1. 有多个Map任务，每个任务的输入是DFS的一个或多个文件块，Map将文件块转换成key-value对序列，具体产生方式由用户编写的Map函数决定；
2. 主控制器（master controller）从每个Map任务中收集一系列key-value对，并将它们按照key大小排序，这些key又被分到所有的Reduce任务中，所以具有相同key的key-value对应该归到同一Reduce任务中；
3. Reduce每次作用于一个key，并将与此key关联的所有值以某种方式组合起来，具体组合方式取决于用户所编写的Reduce函数；

Map任务的输入文件可以看着由多个元素组成，而元素可以是任意类型。键不要求唯一性，一个Map可以产生多个具有相同键的key-value对，即使来自同一元素。

主控器按照哈希函数用以将key-value序列写到r个本地文件中的一个，每个文件划分给不同的Reduce任务。

所有Reduce任务的输出结果会合并成单个文件。通常Reduce函数满足交换率和结合律。某些时候可以在Map函数中使用Reduce函数进行初步处理。

2.3 使用Map-Reduce的算法

基于Map-Reduce的矩阵-向量乘法的实现

矩阵乘法 M(n*n)×N(n*1)，$x_i=\sum_{j=1}^nm_{ij}v_j$
Map函数：将V和M的一个文件块作为输入，Map任务产生$(i,m_{ij}v_j)$
Reduce函数：将所有与指定键i相关的值相加

向量V无法放入内存时的处理

简单方法：多次读V
替代方案：将M划分为多个宽度相等的垂直条，将V划分为同样数目的水平条，Map-Reduce与之前类似

关系代数运算

基于Map-Reduce的选择运算

Map函数：对R中的每个元组t，检查其是否满足C，满足则产生(t,t)
Reduce函数：将键-值传递到输出部分

基于Map-Reduce的投影运算

Map函数：对R中的每个元组t，通过剔除t中属性不在S中的字段得到元组t'，输出(t',t')
Reduce函数：将存在多余的去掉，(t',[t',t',...])->(t',t')

基于Map-Reduce的并、交、差运算