数据流挖掘

读书笔记

【Rajaraman A, Ullman J D. 大数据: 互联网大规模数据挖掘与分布式处理[J]. 2012.】

流数据源示例

1、传感器数据

例如，各类传感器（温度传感器、距离传感器等）都会以一定的频率实时的反馈数据，这些数据如果积累一定的时间就不可能全部放进内存。这时，就必须要考虑哪些数据要存放在工作存储器而哪些数据只能放在归档存储器中。

2、图像数据

卫星往往每天都会给地球传回多个太字节的图像流数据。监控摄像机也类似，数据巨大的摄像机能够连续不断的产生图像流。

3、互联网及Web流量

互联网当中的交换节点从很多输入源接收IP包流并将它们路由到输出目标。Web网站受到的流包括各种类型。如谷歌一天能收到几亿个搜索查询，雅虎的各个不同网站上受到数十亿个“点击”。

流当中的数据抽样

1、例子

一个需要解决的一般性问题是从流中选择一个子集，以便能够对它进行查询并给出统计性上对整个流具有代表性的结果。具体例子如下：搜索引擎收到查询流，这些数据可以用于研究典型用户的行为。假定这个流由三元组$（user，query，time）$组成，假设我们只希望存储$1/10$的流元素。我们需要回答查询“在过去一个月中典型用户提交的重复查询比率是多少”。
两个思路。第一，对每个搜索查询产生一个随机数（比如0~9中的一个整数），并当且仅当随机数为0时才存储该元组。这样，大数定律可以保证当查询数目足够多的时候，大部分用户所存储的查询比例会非常接近$1/10$。然而，如果我们想得到用户提交的平均重复查询数目，那么这个抽样机制会有错误的结果。比如，某用户过去一个有s个查询提交过一次，d个查询提交过2次。那么这个抽样的结果会使得出现2次的d个查询中，只有d/100会在样本中出现2次。所以显然原本的重复查询比例应该是$d/（s+d）$，由于这个抽样变成了$d/（10s+19d）$。因此，就有了第二个思路、挑出$1/10$个用户并将它们的所有搜索查询放入样本，而不考虑其他用户的搜索查询。

2、一般抽样问题

假定抽样之后的样本规模为a/b，那么久可以将每个元组的键值哈希到b个桶中的一个，然后将哈希值小于a的元组放入样本。

布隆过滤器

1、定义

一个布隆过滤器由如下几个部分组成：
1. n个位组成的数组，每个位的初始值都为0。
2. 一系列哈希函数$h_1，h_2，…，h_k$组成的集合。每个哈希函数将键值映射到上述的n个桶中。
3. m个键值组成的集合S。
布隆过滤器的目的是让所有键值在S中的流元素通过，而阻挡大部分键值不在S中的流元素。
如，位数组的所有位的初始值为0。对S中的每个键值K，利用每个哈希函数进行处理。对于一个哈希函数$h_i$及S中的键值K，将每个$h_i(K)$对应的位置为1。当键值为K的流元素到达时，检查所有的$h_1(K)，h_2(K)，…，h_k(K)$对应的位是否全部为1，如果是，则允许该流元素通过，如果有一位或多位为0，则认为K不可能在S中，于是拒绝该元素通过。