大数据存储与处理-数据流挖掘(64页).ppt

大数据存储与应用数据流挖掘,课程主页：http:/netcomm.bjtu.edu.cn/?page_id=397陈一帅chenyishuaigmail.com,内容,流数据模型系统，示例抽样过滤数目统计矩估计窗口内计数衰减窗口,预览,谷歌/淘宝是怎么做下面这些事情的取样比例取样固定size取样频度统计统计item发生的次数白名单过滤统计不同查询的个数评估用户访问的均匀性发现最热item简单的数据统计问题，在大数据场合下，新的方法,流数据模型,流数据模型,系统示例查询问题,流,数据以流的方式进入搜索引擎的查询请求微博更新特点无穷非平稳流的到达速率取决于用户行为，系统无法控制元素（Element）Tuple,大数据下的系统限制,流源源不断地来要求实时处理系统限制存储限制，不能存这么多存得多，处理量也大，处理能力限制NSA（美国棱镜门）存几个月流处理有限存储情况下，怎么实时处理？Online learning,模型,两种查询固定查询：Standing query从不停止例：历史最高温度事先写好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%可以进一步减少,DGIM,Datar,Gionis,Indyk,Motwani 指数窗口每个窗口中包括 i 个1，i:2的幂（指数增长）同样i的窗口最多可以有两个窗口不重叠，可以不连续（中间可以隔0）,16 8 8 4 4 2 2 1,DGIM需要的存储空间,每个子窗（Bucket）有一个时标，记录结束时间取值范围 1 N需要 比特存储空间每个bucket记录自己包含的1的个数取值范围：1lo