《Mining of Massive Datasets》第四章（Mining Data Streams ）知识点提要
本章 pdf 下载链接：http://infolab.stanford.edu/~ullman/mmds/ch4.pdf
本书资料链接：http://mmds.org

前言

流数据处理的若干限制
1. 数据以一个或多个流的方式到来，流元素分发速度快，必须对数据及时处理
2. 通常来说数据量十分大，无法存储整个数据流
流处理算法通常在内存中执行，一般不会或者极少访问二级存储器
数据流处理的每个算法都在某个程度上包含流的汇总过程
核心问题：How to make critical calculations about the stream using a limited amount of memory?
流处理算法的原则：通常情况下，获得问题的近似解比精确解要高效得多。

1. 流处理模型

1.1 数据流管理系统

类比数据库管理系统，流处理器实际上也可以看成是一个数据管理系统

数据流管理系统

若干个流进入系统，每个流的数据流、数据类型不必相同，流元素到达速率不受系统控制，对流数据，不及时处理会永久丢失。
归档存储器容量大，速度慢，通常进行归档处理，无法满足快速应答查询，但是同样不能存储整个数据流
有限工作存储器容量小，速度快，可存储部分流数据，用于快速应答查询
ad-hoc 查询：用户根据自己的需求，灵活的选择查询条件，系统能够根据用户的选择生成相应的统计报表，用户无需对 SQL 和数据库架构有了解

1.2 流查询

流查询主要有两种方式：固定查询（standing query）和 ad hoc 查询。

固定查询

固定查询永远不变地执行并在适当的时候产生输出结果，如查询传感器的最高温。

ad hoc 查询

通过存储数据流的合适部分或者流概要信息来为查询的应答做准备
可以在工作存储器上保存每个流的滑动窗口，将窗口看成是关系数据库而在其上执行任意的 SQL 查询

2. 数据抽样

2.1 固定比例抽样

样本的规模会随着流的增长而增长

假定搜索引擎收到查询流，流由三元组（user,query,time）组成
Question：在过去一个月用户所提交的重复查询的比率是多少？假设只能存储 1/10 的流元素

显然的做法是对每个查询产生一个 0~9 的随机数，当且仅当随机数为0时才存储该元组。大数定律会保证大部分用户所存储的查询比例接近 1/10。

但是，如果问题变成求用户提交的平均重复查询数目，上述抽样机制会带来错误。

假设某用户有 x 个搜索查询提交了一次， d 个搜索查询提交了两次，不存在超过 2 次的其他查询。

显然该问题的正确答案时：d/(x+d)

但是，如果采用上述 1/10 的抽样机制，得到的结果会是 d/( 10x+19d )

对于原本 d 个提交 2 次的搜索查询，只有 d/100 会在样本中再重复 2 次（1/10 * 1/10 * d）

而原本 d 个提交 2 次的搜索查询样本中只出现一次的概率是：1/10 * 9/10 + 9/10 * 1/10 = 18/100

因此，平均重复查询数目:

代表性样本采样

挑选1/10 的用户并将他们所有的搜索查询放入样本中，不考虑其他用户的搜索查询
使用哈希函数将用户名或用户 ID 哈希到桶中，提取一个桶的用户。
更一般的，若想得到 a/b 比例的用户，可以哈希到 b 个桶中，提取前 a 个桶。

选择哪些用户作为代表性用户至关重要

样本规模的变化

哈希函数 h，元组键值 K，阈值 t
样本由满足 h(K) <= t 的元组组成
调整样本空间大小：降低阈值 t 为 t-1，删除样本空间中 h(K) = t 的元组

2.2 固定窗口大小抽样

样本空间大小固定，不会随着流规模的扩大而增长

样本空间 S，能容纳 s 个样本
任何时候都尽可能保持足够多的元组，并且样本空间已满时，随着流增长会丢弃某些元组，丢弃元组会被新元组取代。
保证任何时候选择选择某一任意位置的概率和选择其他位置的概率相等。可用归纳法证明，n 个元素时概率是 s/n，第 n+1 个元素到达时是 s/n+1。

3. 流过滤

即只接受流中满足某个准则的元组集合。

布隆过滤器

一个布隆过滤器由以下几部分组成

n 个位组成的数组（视为 n 个桶），每个位的初始值为0。
一系列哈希函数 h1,h2 ... hk。每个哈希函数将流元组键值映射到上述 n 个桶中。
m 个键值组成的集合 S（样本准则）。

对于流中的元组，若键值在集合 S 中，则通过过滤器。
对于集合 S 中所有键值，利用每个哈希函数进行处理，将在数组的对应位置为1。
当键值K的流元素到达时，检查所有的哈希函数h对应为是否为1，如果是则允许通过。

假阳率

所有真正的负例当中被判为正例的比例，即本来不能通过的流元素却通过过滤的比例

使用飞镖投掷模型来模拟布隆过滤。假设 y 支飞镖和 x 个靶位，预计给定靶位至少被投中一次的概率。

给定飞镖不能投中给定靶位概率 (x-1)/x

y 支飞镖全部没有命中给定靶位的概率 [(x-1)/x]^y，即

根据重要极限公式

y 支飞镖全部没有命中给定靶位的概率为 e^(-y/x)，故假阳率位 1- e^(-y/x)

故对于有 k 个哈希函数的布隆过滤器，假阳率为

4. 流中独立元素的数目统计

使用若干不同的哈希算法和随机算法，在每个流空间开销较小的情况下得到近似结果

FM（Flajolet-Martin）算法

基本思想：如果流中看到的不同元素越多，那么不同的哈希值也会越多，同时，也越可能看到其中一个值变得“异常”。具体的异常性质是该值后多个0结束。
任何流元素 a 应用哈希函数 h 时，位串 h(a) 的尾部将以 0 结束（可能没有），尾部 0 的数目称为尾长，流中所有元素的最大尾长为 R。
用 2^R 来估计目前为止流中独立元素数目。

流元素 a 的哈希值 h(a) 末尾至少有 r 个 0 的概率为 2^(-r)。

假定流中有 m 个独立元素，那么任何元素的哈希值末尾不满足至少有 r 个 0 的概率为

即

可改写为

结论
1. 如果 m 远大于 2^r，那么发现一个尾长长度至少为 r 的概率接近1；
2. 如果 m 远小于 2^r，那么发现一个尾长长度至少为 r 的概率接近0。

组合估计

平均值

假定在每个哈希函数上得到不同的 2^R，然后求平均值

会受到偶然极大值得影响，即某个哈希函数得到的 2^R 过大。（ 2^R 是以指数成倍增长的）

中位数

取每个哈希函数得到不同的 2^R 的中位数。

得到的值永远都是 2 的幂，不可能得到非常近似的估值

平均值和中位数组合

先将哈希函数分成若干组，组内取平均值，组外取中位数

或

将哈希函数分成若干组，组内取中位数，组外取平均值

5. 矩估计

流的 k 阶矩：流中至少出现一次的元素出现次数的 k 次方之和

0 阶矩表示流中独立元素个数
1 阶矩表示整个流的长度，也就是元素个数
2 阶矩度量流中元素分布的非均匀性。越小越均匀。

数据流挖掘