大数据存储与处理数据流挖掘.pptx

大数据存储与应用数据流挖掘
课程主页：httppage_id=397
陈一帅
内容
流数据模型
系统，示例
抽样
过滤
数目统计
矩估计
窗口内计数
衰减窗口
预览
谷歌/淘宝是怎么做下面这些事情的
取样
比例取样
固 Gionis, Indyk, Motwani]
指数窗口
每个窗口中包括 i 个1， i : 2的幂（指数增长）
同样i的窗口最多可以有两个
窗口不重叠，可以不连续（中间可以隔0）
16 8 8 4 4 2 2 1
DGIM需要的存储空间
每个子窗（Bucket）有一个时标，记录结束时间
取值范围 1 … N
需要 比特存储空间
每个bucket记录自己包含的1的个数
取值范围：1…logN
需要 存储空间
更新
新元素到了
如果一个Bucket的end time已超过当前时刻 - N，drop它
如果新元素是0，什么也不做
如果是1
创建一个Bucket，size = 1， end time = 当前时间
如果有3个1，就合并为一个2。
依次类推，如果有3个一样的小的，就合并为一个大的。
雪崩式前滚
示例
估计1的个数
除了最后一个bucket，把其他bucket的size相加
Size就是其中1的个数
再加上最后一个Bucket size的一半
因为最后一个bucket，只是最后一位还在N里，不知道它的头还是不是在N里，所以，只能算一半。
Error bound：50%
假设最后一个bucket的size：2r
我们在统计中算了它的一半“1”，所以，最多产生2r-1的错误
比它size小的bucket有2r-1，2r-2 ，2r-3 ，…，1，每种至少有一个
所以，它们包含的“1”的个数至少为： 2r-1 + 2r-2 + 2r-3 + … + 1 = 2r – 1.
最后一个bucket在窗口中至少还有1个“1”，所以， “1”的个数至少为2r
所以，最大的错误率：2r-1/ 2r = 1/2 = 50%
扩展
同样size的bucket数目可以是r或r-1个。r > 2
最大Size的bucket，可以有1,…,r个
错误的上界1/(r-1)
实践中，根据需要选择r
应用：窗口内整数的和
把整数的每一个bit作为一个stream
统计每一个stream的1的个数，Ci
求和：
小结
百分比取样
按feature（用户）取样
固定Size取样
滑动窗取样
估计1的个数
求整数和
过滤
Bloom filter（布隆过滤器）
Bloom filter
Bloom是一个人
从stream中选择符合特定条件的元素
例1：垃圾邮件检查
白名单
例2：Google Alert
Pub-Sub系统，每个人可以设定订阅的关键词
明显的方法
建立Hash表，查询，命中
大数据下，filter太多，数据太多，怎么办？
包括10 billion 个白名单
初始化
白名单中包括s个允许的key值
s = 1 billion
n个检查位，n >> s，初始化为0
把这s个白名字Hash到1,…,n上
对应的bit位设1
最后，n中大约有s个“1”
事实上小于s个，因为会重合。
到底有几个1？
一个白名字，被均匀地撒在n个比特上
撒上概率：1/n
一个比特位，没有被撒上的概率
被1个白名字错过的概率：1 - 1/n
被所有s个白名字都错过的概率
(1-1/n)s = (1-1/n)n(s/n)
近似等于 e-s/n
所以，一个比特位，被撒上的概率
1 – e–s/n
总共，n(1 – e–s/n)个比特位被撒上
值为“1”
检查
来了一个邮件，把发件人地址，hash一下，如果对应的比特位为0，肯定不在白名单里，Reject
不在白名单里，也会被均匀撒在n个比特位上
如果那个比特位碰巧是“1”，就会pass
False positives - 假阳（FP）
Pass：Positive
和n中“1”的比例有关，
n(1 – e–s/n)/n = 1 – e–s/n
所以，可以通过增加n，降低FP概率
s = 109, n = 8×109，概率 1 - e–1/8 = ～ 1/8 = s/n
改进：多个hash函数
初始化
对s中任一元素，用k个独立hash函数，分别撒k次
“