大数据存储与应用数据流挖掘-精选.ppt

大数据存储与应用数据流挖掘-精选
内容
流数据模型
系统，示例
抽样
过滤
数目统计
矩估计
窗口内计数
衰减窗口
预览
谷歌/淘宝是怎么做下面这些事情的
取样
比例取样
固定size取样
频度统计
统计item发生的次数
最后一个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次
“1”的个数：
类似前面，只是撒了ks次
n(1 – e–ks/n)
检查
来一封信，用这k个hash检查，全部为“1”才行。
False positive率
混过去一个hash函数，概率(1 – e–ks/n)
混过去全部k个hash检查，概率(1 – e–ks/n)k
K=2， 概率 ~ 1/20 << 1/8
改进了性能
K的选择
K不是越大越好
对这个例子，最优的在6的样子。
Bloom Filter总结
只会false positive
不会false negative
错杀概率 = 0
适合预处理
先筛选一些
适合硬件实现
适合并行
Map-reduce
Distinct元素统计
统计出现的不同元素个数
应用
爬网站时，边爬，边检查其网页中不同单词的个数
太多或太少，都表明是一个作弊的网站
统计一个用户，一周内，访问了多少不同的网页
统计淘宝，上周，卖了多少种不同的商品？
明显的方法
建立一个Distinct元素列表（hash表）
进来一个，和列表中已有的元素对照，如果不同，就加入
跟踪列表Size的变化
大数据情况下
存不下
维护成本很高
需要
减少存储要求
减小计算复杂度
Tradeoff：
准确性 <> 实用性
估计
Flajolet-Martin方法