挖掘数据流 Mining Data Stream

Notes on MMDS on Coursera

数据流挖掘:

  1. 输入元组通过一个或多个端口快速地进入
  2. 系统无法存储整个数据流
  3. 在有限内存的条件下对数据流做出一些计算

对数据流的两类Query:

  1. Ad-hoc queries,例如当前数据流中的最大值是多少
  2. standing queries, 例如每当数据流中出现了新的最大值就汇报一次

滑动窗口:

  • Query时总是针对数据流中固定长度N的一个窗口(最新进入系统的N个数据)
  • 或者:最近T时间内进入系统的数据

当窗口的长度大到无法存储于主存内时,或者有太多不同数据流,内存不够存储多个窗口,则需要更有趣的方法。

例子:平均数

  • 数据流为一个个整数
  • 窗口尺寸N
  • standing query: 当前窗口中数字的平均值为多少?

方法:

  1. 对于前N个数据,计算其平均值A
  2. 对于每一个新来的数据i,找到当前窗口中最旧的数据j,更新平均值为Aleftarrow A + (i-j)/N

Counting Bits 问题:

  • 给定一个数据为01的数据流,希望回答的问题是:最近k个数据中有多少个1kleq N
  • 如果存储最近的N个数据,很容易回答。
  • 假设N,k均很大,并且有非常多数据流同时流入并且需要计算,无法这样做。

DGIM算法:

  • 对每一个数据进行timestamp
  • 对窗口内的数据进行summary为一个个bucket
  • 每个bucket代表窗口内报括了2^i1的一段数据流,记录为(该段的末尾位置,2^i2^i为该bucket的大小
  • 如果同样大小的bucket出现了3次,就进行合并,丢掉时间戳较老的,更新较新的那个味(该段的末尾位置,2^{i+1})

QQ截图20150226231451

Query,最近k个数据中有多少个1

  • 只看结尾时间在最近k时间以内的bucket
  • 将所有bucket的大小加起来,最旧的一个bucket的值只算一半
  • 这样的误差,最大可能会有50%

Bloom Filter

例如现在有一个网页爬虫,每当遇到一个新的URL的时候希望爬虫能较快地知道(不用去检索过去是否爬过)是否曾经见过该URL。(可以有False Positive)

  1. Bloom Filter是一个bit array和若干hash function
  2. 哈希函数返回的是bit array中的一个位置
  3. 当输入x进入的时候,将array中各个哈希函数h(x)所表示的位置标记为1

例子:

  1. array 的长度N为11
  2. 输入的数据流是一个个整数
  3. 有两个哈希函数:
    h1(x) 是取x的二进制表示的奇数位置构成一个新的数,转换为十进制后%11
    h2(x) 是取x的二进制表示的偶数位置构成一个新的数,转换为十进制后%11

检索时:

  1. 新输入设为y
  2. 计算h1(y)和h2(y)
  3. 如果array中的相应位置全部都为1,就认为曾经见过,否则认为y是从未见过的

Bloom Filter的FP率:

  • 取决于array中1的密度,以及哈希函数的数量
  • P(text{false negative}) = (text{fraction of 1's})^{number of hash functions}
  • 例如array长度10^9,哈希函数5个,目前进来了10^8个数据
    则:剩余的0的个数为:approx exp(-frac{5times 10^8}{10^9})= exp(-0.5) = 0.607
    1的密度为:1-0.607 = 0.393
    false positive的概率为:0.393^5=0.00937

 

Leave a Reply

Your email address will not be published. Required fields are marked *