shartoo +

大数据之流数据挖掘

本文总阅读量
欢迎star我的博客

一 流数据的特征

  1. 分发速度非常快,必须及时处理,否则将永远丢失。
  2. 即使分发速度较慢,同时多个数据流一起则超过了内存最大容量。

二 流数据的处理方法

2.1 流数据抽样

问题描述:过去的一个月中典型用户提交的重复查询比率是多少。假设我们只存储其中十分之一的流元素。
典型做法:对每个搜索查询产生一个随机数(比如0-9中间的一个随机数),并当且仅当为0时才存储。如果用户提交的查询足够多,大数定律会保证大部分用户所存储的比例非常接近1/10.

2.1.1 误区

   如果想得到用户提交的平均重复查询数目,上述抽样会得到错误结果。
   假设某个用户在你过去一个月中有s个查询只提交过一次,d个查询提交两次,不存在超过两次的提交。那么提交过一次查询数目达到我们所期望的s/10,而在出现过两次的d个查询中,只有d/100会在样本中出现2次,该值等于d乘以该查询两次出现在1/10样本中的概率。于是在整个中出现2次的d个查询中,有18d/100个查询样本在样本中出现一次。 本来,在所有搜索查询中重复搜索查询的比率正确答案是d/(s+d).但是,如果采用上述方法,我们得到的值为 d/10+18d/100个查询出现一次。

2.1.2 正确思路

   我们不能从每个用户的搜索查询的抽样样本中得到正确答案。因此,必须要挑出1/10的用户并将它们所有的查询放入样本,而不考虑其他用户的搜索查询。每当一个新的查询到达流中时,我们会查找用户以判断其是否在已有样本中出现,若出现则放入样本,否则丢弃。如果没有出现该用户,我们产生一个0-9随机数,若为0则加入用户列表,并将其标记为”in”,否则,也加入用户列表,但是标记为”out”。
   注意:引入哈希函数将每个用户哈希到编号0-9的10个桶中之一。但是桶中并不保存真正用户,事实上桶中没有任何数据。只是将哈希函数作为随机数生成器来使用。该哈希函数的一个重要特点就是,即使在相同用户上应用多次,其生成的随机数也相同。即,对任何用户都不需要存储其in/out决策,因为任何查询到来时都可以重构该决策。

2.2 流过滤

  主要讨论的是使用布隆过滤器。

2.2.1 布隆过滤器简介

布隆过滤器也即Bloom Filter算法 一个布隆过滤器由以下几个部分组成

布隆过滤器的目的是让所有键值在S中的流元素通过,而阻挡大部分键值不再S中的流元素,哈希函数hi及S中的键值K,将每个 $h_i(K)$对应的位置为1。

当键值为K的流元素到达时,检查所有的 $h_1(k), h_2(k) ,h_3(k)….h_k(k)$ 对应的位是否全部都是1.如果是则允许该元素通过,如果有一位或多位为0,则认为K不可能在S中。则拒绝该元素通过。如果元素键值在S中出现一定会通过布隆过滤器,但是元素键值不在S中的元素也有可能会通过。我们需要了解如何基于位数组长度n,集合S的元素数目m及哈希函数的数目k来计算false positive概率。

2.2.1 Bloom Filter算法思路

  1. 我们有一个长度为n的比特数组,开始的时候将这个比特数组里所有的元素都初始化为0。

    00000000000000000000

    上面的比特数组n为20。
  2. 然后选取k个哈希函数,这k个哈希函数产生的结果的值的范围在0到n-1之间(对于上面的比特数组,即0到19)。对每个要添加进集合的对象进行哈希运算,然后将哈希计算结果作为数组的索引,将索引位置的比特位设置为1(不管该比特位原先为0还是为1)。
    比如我们选取三个哈希函数,对于对象A哈希值为0,5,7。那么比特数组就为:

    10000101000000000000

    对象B的值为2,8,13,那么添加B后的比特数组为:

    10100101100001000000

    对象C为0,4,7(对象C的第一个哈希函数的值与对象A的相同了,没关系我们还是设置为1就可以了):

    10101101100001000000

    现在我们的Bloom Filter里已经有3个元素了。现在我们要判断某元素X是否在该集合中。就相当于我们要实现一个contains方法。
    对元素X采用相同的三个哈希函数哈希,然后以这三个哈希值为索引去比特数组里找。如果三个索引位置的比特位都为1我们就认为该元素在集合中,否则不是。

2.2.3 Bloom Filter算法应用

   比如假设我们有一个缓存服务器集群,集群里的不同的服务器承担的缓存也不尽相同。如果一个用户请求过来了,我们如何能快速的判断出用户请求的这个url在集群里哪台服务器上呢?因为每台服务器上缓存的url对应的页面非常庞大,我们全部弄到内存里代价也很高。我们就可以在每台服务器上放一个Bloom Filter,里面添加的都是本服务器上有缓存的那些url。这样即使Bloom Filter误报了,那就是把一个url发到了一个并不持有该url对应的缓存的服务器上,结果就是缓存未命中,缓存服务器只需要将该url打到后端的上游服务器就好了。

三 独立元素数目估计

3.1 FM算法(Flajolet-Martin)

   基本思想是:如果流中看到的不同元素越多,那么我们看到的不同的哈希值也越多。我们看到的不同哈希值越多时,哈希函数的性质是对同一个数哈希结果都是一样的。
   理想中的是:对同一批数据使用多个哈希函数,每个哈希函数上得到不同的 $2^R$ 的值(对流元素a应用哈希函数h,h(a)的尾部将以一些0结束,尾部0的数目成为a和h的尾长,假设目前所有已有元素a的最大尾长为R, $2^R$ 用来估计流中独立元素数目),然后求它们的平均值即可得到真实的m的近似值。

3.2 FM算法的问题

   假设一个r,使得2^远大于m。存在某个概率p发现r是流中最大尾长,于是发现r+1是流中最大尾长的概率至少为p/2.因此,随着R的增长,每个可能的R对2^R的期望贡献也越大。2^R的期望值实际是无限大。

3.3 完美解决方案

   取所有估计值得中位数,由于中位数不会受到偶然极大的2^R影响。缺陷是:它永远都是2的幂值,不论用多少哈希函数,都是在两个2 的幂之间,那么小至少是log2(m)的一个小的倍数。
我们可以:首先将哈希函数分成小组,每个小组内取平均值。然后再所有平均值中取中位数,组间取中位数可以将中位数的缺陷的影响降低到几乎没有的地步。每个组的大小至少是log2(m)的一个小的倍数。

四 矩估计

   上述独立流元素计数推广到一般的问题,该问题称为矩计算,包括不同流元素出现的频率分布的计算。

4.1 矩定义

   假定一个流由选自某个全集的元素够成,并假定该全集中所有元素都排好序,这样我们通过整数 i 来标记该序列中的第i 个元素,假设该元素出现的次数为mi,则流的k 阶矩是所有 i 上的(mi)^k 之和。
   流的一阶矩是所有元素mi之和,也即整个流的长度,当前流所有元素个数;二阶矩是所有元素mi的平方和。

4.2 二阶矩的AMS算法

   假设没有足够空间来计算流中所有元素的mi。我们仍然可以使用有限空间来估计流的二阶矩,空间越多结果越精确。对每个变量X 我们保存一下内容。

  1. 全集当中的一个特定元素,记为X.element。
  2. 一个整数,记为X.value,它是变量X的值。在流中均匀的随机选择1到n之间的一个位置。将X.element置为该位置上的元素,X.value初始为1,每再看到一个X.element 就将其对应的X.value 值加1。

   假定流 a,b,c,b,d,a,c,d,a,b,d,c,a,a,b,流长度为15。由于a 出现5次,b 出现4次,c和d各出现3次。因此二阶矩为 $5^2+4^2+3^2+3^2=59$ .假定维护3个变量 $X_1,X_2,X_3$ .假定随机位置为3,8,13。当到达位置3时,对应的元素为c,于是 $X_1.element=c$ ,此时 $X_1.value=1$ ,而位置4为b,5为d,6为a,X1的值均不改变,在位置7元素c再次出现,继续往后的话,位置12再出现c,因此 $X_1.value=3$ 。据此可以得到 $X_2.value=2$ 和 $X_3.value=2$ (注意,他们都是从该元素第一次出现之后,往后出现的才算)。
基于任意一个变量X,我们可以导出二阶矩的一个估计值为: n(2X.value-1)
根据本例中的值,我们可以通过二阶矩估算值得平均值为:(15(23-1)+15(22-1)+15(22-1))/3=55 可知与精确值 59相当接近了。

4.3 无限流的处理

   对于二阶矩以及多阶矩的估计当中,我们是假定流长度n 是一个常数。实际应用当中,n 会不断随着时间增长。因此在变量位置选择的时候需要谨慎。

  1. 一方面,如果只对所有元素做一次选择,流不断增长时,计算会偏向早期的元素
  2. 另一发面,如果选择的等待时间太久,那么早期的元素位置上变量不多,从而造成估算的可靠性不高。
  3. 比较合理的选择是,任何时候都尽可能保持足够多的变量,并在流增长时丢弃某些变量(在选择某个位置的概率和其他位置的概率必须相等)。

我的博客

观点

源码