大数据存储与处理-数据流挖掘

大数据存储与处理大数据存储与处理-数据数据流挖掘流挖掘内容流数据模型系统，示例抽样过滤数目统计矩估计窗口内计数衰减窗口预览谷歌/淘宝是怎么做下面这些事情的取样比例取样固定size取样频度统计统计item发生的次数白名单过滤统计不同查询的个数评估用户访问的均匀性发现最热item简单的数据统计问题，在大数据场合下，新的方法流数据模型流数据模型系统示例查询问题流数据以流的方式进入搜索引擎的查询请求微博更新特点无穷非平稳流的到达速率取决于用户行为，系统无法控制元素（Element）Tuple大数据下的系统限制流源源不断地来要求实时处理系统限制存储限制，不能存这么多存得多，处理量也大，处理能力限制NSA（美国棱镜门）存几个月流处理有限存储情况下，怎么实时处理？Online learning模型两种查询1.固定查询：Standing query从不停止例：历史最高温度事先写好2.Ad-hoc查询不全存，但还是存一些内容根据这些存储的内容应答问题取样：随机取样（Sampling）过滤（白名单）：选取特定属性的元素（Filtering）计数（一定窗口内）有多少个不同的元素？（distinct elements)各元素的Popularity？特征：各阶矩谁最流行?应用Google：查询流发现最流行的查询关键字Yahoo：发现最流行的页面微博：发现最热的话题找人传感器网络电话记录美国，棱镜门网络交换机流量统计，优化路由检测DDoS攻击抽样Sampling抽样两种抽样固定比率抽样1 in 10固定Size抽样总是保持s个元素固定比率抽样应用场合搜索引擎，一个用户的搜索中，重复的有多少？存不了全部，可以存1/10最明显的办法每来一个query生成一个随机整数：09如果是0，就存起来1/10的采样然后统计其中的用户重复搜索比例对吗？有问题假设：一个用户所有搜索字符串中，x个查询了一次，d个查询了两次，没有其他查询。重复查询占比：d/(x+d)随机采样10%后，重复查询占比是怎样的？采样后，获得(x+2d)/10个查询，其中x/10个查询是属于x，肯定只出现一次针对d的2d/10个查询d中任一查询，两次都被抽中的概率为1/101/10=1/100所以，平均有d/100个查询会被抽中两次，占2d/100个查询剩下2d/10 2d/100=18d/100次查询，也只出现一次。结果不等于d/(x+d)。错误正确方法：按用户采样挑1/10的用户，观察它们的全部查询采样方法Hash(User ID)mod 10，把用户分到十个桶中选第一个桶的用户（hash后结果为0）挑2/10的用户怎么办？选前面两个桶固定Size抽样总是保持s个元素这s个元素，是对过去所有元素的均匀取样即：过去所有元素，进入这s个元素的概率相同直观方案：全存起来，然后从中随机挑s个大数据下，因为存储空间的限制，不可行流方案进来一个新元素时，新元素以概率p进入s原有的s个元素按一定的概率从s中剔除新元素进入S的概率p假设已到达n个元素，它们以s/n的概率被采样，组成s个元素的集合新进来一个元素，一共到达了n+1个元素。这n+1元素，以相同概率进入s这个概率：s/(n+1)所以，这个新元素以s/(n+1)的概率进入sp=s/(n+1)S中原元素的剔除策略原来在s个元素集合中的元素，随机剔除一个不被剔除的概率原先，这n个元素，是以s/n概率进入s的。这一轮过后，任一元素留在s中的概率和新到元素的留下概率s/(n+1)相等结果：所有n+1个元素，以s/(n+1)的概率留下新元素不进s的概率新元素进s，但在s中不被剔除的概率滑动窗口内计数Sliding windows 滑动窗另一种取样方式示例N=6应用：统计滑动窗中1的个数频率简单方案FIFO，窗口大小：N存起来然后统计但是：N太大(Billion)/流太多(Billion)，存不下。怎么办？近似方案统计滑动窗中1的个数如果1均匀分布，容易估计从流开始时刻，统计1/0个数：S/Z估计窗口N内1的个数：如果1的分布不均匀呢？DGIM方法每个流，存储 比特结果误差不超过正确结果的50%可以进一步减少DGIMDatar,Gionis,Indyk,Motwani 指数窗口每个窗口中包括 i 个1，i:2的幂（指数增长）同样i的窗口最多可以有两个窗口不重叠，可以不连续（中间可以隔0）16 8 8 4 4 2 2 1DGIM需要的存储空间每个子窗（Bucket）有一个时标，记录结束时间取值范围 1 N需要 比特存储空间每个bucket记录自己包含的1的个数取值范围：1logN需要 存储空间更新新元素到了如果一个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 filterBloom是一个人从stream中选择符合特定条件的元素例1：垃圾邮件检查白名单例2：Google AlertPub-Sub系统，每个人可以设定订阅的关键词明显的方法建立Hash表，查询，命中大数据下，filter太多，数据太多，怎么办？包括10 billion 个白名单初始化白名单中包括s个允许的key值s=1 billionn个检查位，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 es/n总共，n(1 es/n)个比特位被撒上值为“1”检查来了一个邮件，把发件人地址，hash一下，如果对应的比特位为0，肯定不在白名单里，Reject不在白名单里，也会被均匀撒在n个比特位上如果那个比特位碰巧是“1”，就会passFalse positives-假阳（FP）Pass：Positive和n中“1”的比例有关，n(1 es/n)/n=1 es/n所以，可以通过增加n，降低FP概率s=109,n=8109，概率 1-e1/8=0.1185 1/8=s/n改进：多个hash函数初始化对s中任一元素，用k个独立hash函数，分别撒k次“1”的个数：类似前面，只是撒了ks次n(1 eks/n)检查来一封信，用这k个hash检查，全部为“1”才行。False positive率混过去一个hash函数，概率(1 eks/n)混过去全部k个hash检查，概率(1 eks/n)kK=2，概率 0.0493 1/20 1/8改进了性能K的选择K不是越大越好对这个例子，最优的在6的样子。Bloom Filter总结只会false positive不会false negative错杀概率=0适合预处理先筛选一些适合硬件实现适合并行Map-reduceDistinct元素统计统计出现的不同元素个数应用爬网站时，边爬，边检查其网页中不同单词的个数太多或太少，都表明是一个作弊的网站统计一个用户，一周内，访问了多少不同的网页统计淘宝，上周，卖了多少种不同的商品？明显的方法建立一个Distinct元素列表（hash表）进来一个，和列表中已有的元素对照，如果不同，就加入跟踪列表Size的变化大数据情况下存不下维护成本很高需要减少存储要求减小计算复杂度Tradeoff：准确性 实用性估计Flajolet-Martin方法启发式算法用Hash，把N个元素，映射到至少log2(N)比特上检查映射的结果，看它们尾部连0的个数：ri例：1100 -2 1000 -3找出最大的 ri例：R=max2,3=3估计不同元素个数为2R例：23=8直觉证明(Intuition)通过Hash把元素均匀散布到M=log2(N)个比特上Hash结果为xxx0的概率为1/2Hash结果为xx00的概率为1/4当我们看到一个*100时，很可能已经pass过了4个不同的元素了。估计：4个不同元素更形式化的证明一个元素，hash后，尾部连续r个0的概率()r=2r m个不同元素hash后的m个结果，尾部都不“连续r个0”概率：(1-2r)m=出现连续r个0的概率 1-m 2r，概率为1，即总能得到连续r个0的结果。m 2r，概率为0，即得不到连续r个0所以，估计m=2r 大致上是合理的。实际应用问题：R加1，2R就涨一倍。E2R无穷大解决办法用多个hash函数，结果组合起来组合办法平均：偶尔一个大值对结果的影响很大，不好中值：估计的结果总是2的幂次，取值不连续，也不好解决方案：样本分组组内取平均组间取中值矩估计Moments矩估计N个到达的元素，统计各不同元素的流行度(Popularity)不同元素的集合A，各不同元素i出现的次数mi（流行度）流行度的K阶矩物理意义k=0，A的size，即不同元素的个数。|A|k=1，N，stream长度，元素个数k=2，Surprise number（奇异数），Popularity分布均匀的度量Surprise number（奇异数）Popularity分布的均匀程度的度量例：|A|=11：11个视频N=100：100次用户观看观看在视频上的分布Case 1：10,9,9,9,9,9,9,9,9,9,9Surprise S=910比较均匀Case 2：90,1,1,1,1,1,1,1,1,1,1 Surprise S=8110更不均匀AMS方法Alon,Matias,and Szegedy以k=2为例随机挑一个时刻，对stream采样采样获得的值存在X.el里然后对后面进来的stream中这个值计数，直到stream结尾计数c存在X.val里做多次，对最后的X.val，乘2，减1，乘n，然后求平均t=1时采，X.el=a，结束时，有 X.val=mat=3时采，X.el=b，结束时，有 X.val=mb分析a如果在最后一个a采，结束时，有X.val=1如果在倒数第二个a采，结束时，有X.val=2如果在t=1时采，结束时，有X.val=ma求这些 n(2*X.val-1)的均值因为所以正是我们要的推广背后是什么？利用了即(i+1)2 i2=2i 1同理，求(mi)3，就对样本执行再做求和平均推广，求(mi)k应用根据memory大小，尽可能多随机取样，统计个数对每个x.val(c)求分组组内平均组间中值局限对infinite stream，岂不是越加越大，直到无穷？对Infinite Stream采用前面介绍过的固定Size采样办法采样Size：k当第n个元素到达时，以k/n的概率留下在采样的k个样本中计算c近似得到一个对整个流的矩估计k=2，Surprise number（奇异数），Popularity分布均匀的度量衰减窗口发现流行找出过去1个月内，被看次数超过1000的视频？DGIM方法对每个视频，建立一个1/0流，统计1的个数然后挑出超出1000的视频大数据下，太多视频，每个视频一个streaming不现实Youtube，billions of videos指数衰减窗方法（EDW）启发式方法我们关心的是“现在”流行啥？过去的计数，让它们慢慢衰减热度=ai：计数c：衰减系数，一般取10-6,10-9权重和：等价于来一个新的a，把老热度乘1-c（即衰减），然后加上这个新a实现起来非常方便实际中，为了减少存储，设一个阈值（如1/2），权重低于该阈值的，就不跟踪了估计要跟踪多少个视频任意时刻，所有视频热度的和来一个视频观看，以前所有视频观看带来的热度乘（1-c），再给对应视频的热度+1所有视频观看带来的热度的分布，也是一个等比级数，和为因此，得分超过1/2的电影个数不会超过2/c否则，总分将超过1/c所以，最多只需要跟踪2/c个视频的热度省发现流行扩展到一篮子（项集Itemsets）如何用EDW对项集流行度进行跟踪呢？来了一篮子元素B把所有已有的元素/项集的热度乘 1 c（衰减）加新元素篮子里已有的元素和项集，热度+1热度 1/2的，扔掉B中出现的新子集，如果它的所有子集都在B到来之前被跟踪着，就新增这个子集直觉：所有子集都热，那它也可能热例：i,j都在集里了，那么，开始计数i,ji,j i,k k,j都在集里了，那么，开始计数i,j,k跟踪多少个？单item(2/c)篮子里的item数子集和Load有关总结谷歌/淘宝是怎么做下面这些事情的取样比例取样固定size取样频度统计DGIM 统计1的个数扩展到整数求和白名单过滤Bloom Filter不同元素个数FM访问均匀性分析2阶矩，AMS方法最热item发现指数衰落窗（EDW）