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

大数据存储与应用数据流挖掘课程主页：@gmail.com内容•流数据模型•系统，示例•抽样•过滤•数目统计•矩估计•窗口内计数•衰减窗口预览•谷歌/淘宝是怎么做下面这些事情的•取样•比例取样•固定size取样•频度统计•统计item发生的次数•白名单过滤•统计不同查询的个数•评估用户访问的均匀性•发现最热item•简单的数据统计问题，在大数据场合下，新的方法流数据模型流数据模型•系统•示例•查询•问题流•数据以流的方式进入•搜索引擎的查询请求•微博更新•特点•无穷•非平稳•流的到达速率取决于用户行为，系统无法控制•元素（Element）•Tuple大数据下的系统限制•流源源不断地来•要求实时处理•系统限制•存储限制，不能存这么多•存得多，处理量也大，处理能力限制•NSA（美国棱镜门）•存几个月•流处理•有限存储情况下，怎么实时处理？•Onlinelearning模型两种查询1.固定查询：•Standingquery•从不停止•例：•历史最高温度•事先写好2.Ad-hoc查询•不全存，但还是存一些内容•根据这些存储的内容应答问题•取样：•随机取样（Sampling）•过滤（白名单）：选取特定属性的元素（Filtering）•计数（一定窗口内）•有多少个不同的元素？（distinctelements)•各元素的Popularity？•特征：各阶矩•谁最流行?应用•Google：•查询流•发现最流行的查询关键字•Yahoo：•发现最流行的页面•微博：•发现最热的话题•找人•传感器网络•电话记录•美国，棱镜门•网络交换机•流量统计，优化路由•检测DDoS攻击抽样Sampling抽样•两种抽样•固定比率抽样•1in10•固定Size抽样•总是保持s个元素固定比率抽样•应用场合•搜索引擎，一个用户的搜索中，重复的有多少？•存不了全部，可以存1/10•最明显的办法•每来一个query•生成一个随机整数：0…9•如果是0，就存起来•1/10的采样•然后统计其中的用户重复搜索比例•对吗？有问题•假设：一个用户所有搜索字符串中，x个查询了一次，d个查询了两次，没有其他查询。•重复查询占比：d/(x+d)•随机采样10%后，重复查询占比是怎样的？•采样后，获得(x+2d)/10个查询，其中x/10个查询是属于x，肯定只出现一次•针对d的2d/10个查询•d中任一查询，两次都被抽中的概率为1/10×1/10=1/100•所以，平均有d/100个查询会被抽中两次，占2d/100个查询•剩下2d/10–2d/100=18d/100次查询，也只出现一次。•结果•不等于d/(x+d)。错误正确方法：按用户采样•挑1/10的用户，观察它们的全部查询•采样方法•Hash(UserID)mod10，把用户分到十个桶中•选第一个桶的用户（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)的概率进入s•p=s/(n+1)S中原元素的剔除策略•原来在s个元素集合中的元素，随机剔除一个•不被剔除的概率•原先，这n个元素，是以s/n概率进入s的。•这一轮过后，任一元素留在s中的概率•和新到元素的留下概率s/(n+1)相等•结果：所有n+1个元素，以s/(n+1)的概率留下新元素不进s的概率新元素进s，但在s中不被剔除的概率滑动窗口内计数Slidingwindows滑动窗另一种取样方式示例•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）168844221DGIM需要的存储空间•每个子窗（Bucket）有一个时标，记录结束时间•取值范围1…N•需要比特存储空间•每个bucket记录自己包含的1的个数•取值范围：1…logN•需要存储空间更新•新元素到了•如果一个Bucket的endtime已超过当前时刻-N，drop它•如果新元素是0，什么也不做•如果是1•创建一个Bucket，size=1，endtime=当前时间•如果有3个1，就合并为一个2。•依次类推，如果有3个一样的小的，就合并为一个大的。•雪崩式前滚示例估计1的个数•除了最后一个bucket，把其他bucket的size相加•Size就是其中1的个数•再加上最后一个Bucketsize的一半•因为最后一个bucket，只是最后一位还在N里，不知道它的头还是不是在N里，所以，只能算一半。Errorbound：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个。r2•最大Size的bucket，可以有1,…,r个•错误的上界1/(r-1)•实践中，根据需要选择r应用：窗口内整数的和•把整数的每一个bit作为一个stream•统计每一个stream的1的个数，Ci•求和：小结•百分比取样•按feature（用户）取样•固定Size取样•滑动窗取样•估计1的个数•求整数和过滤Bloomfilter（布隆过滤器）Bloomfilter•Bloom是一个人•从stream中选择符合特定条件的元素•例1：垃圾邮件检查•白名单•例2：GoogleAlert•Pub-Sub系统，每个人可以设定订阅的关键词•明显的方法•建立Hash表，查询，命中•大数据下，filter太多，数据太多，怎么办？•包括10billion个白名单初始化•白名单中包括s个允许的key值•s=1billion•n个检查位，ns，初始化为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•Falsepositives-假阳（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=0.1185～1/8=s/n改进：多个hash函数•初始化•对s中任一元素，用k个独立hash函数，分别撒k次•“1”的个数：•类似前面，只是撒了ks次•n(1–e–ks/n)•检查•来一封信，用这k个hash检查，全部为“1”才行。•Falsepositive率•混过去一个hash函数，概率(1–e–ks/n)•混过去全部k个hash检查，概率(1–e–ks/n)k•K=2，概率0.0493~1/201/8•改进了性能K的选择•K不是越大越好•对这个例子，最优的在6的样子。BloomFilter总结•只会falsepositive•不会falsenegative•错杀概率=0•适合预处理•先筛选一些•适合硬件实现•适合并行•Map-reduceDistinct元素统计统计出现的不同元素个数应用•爬网站时，边爬，边检查其网页中不同单词的个数•太多或太少，都表明是一个作弊的网站•统计一个用户，一周内，访问了多少不同的网页•统计淘宝，上周，卖了多少种不同的商品？明显的方法•建立一个Distinct元素列表（hash表）•进来一个，和列表中已有的元素对照，如果不同，就加入•跟踪列表Size的变化大数据情况下•存不下•维护成本很高•需要•减少存储要求•减小计算复杂度•Tradeoff：•准确性实用性•估计Flajolet-Martin方法•启发式算法•用Hash，把N个元素，映射到至少log2(N)比特上•检查映射的结果，看它们尾部连0的个数：ri•例：1100-2•1000-3•找出最大的ri•例：R=max{2,3}=3•估计不同元素个数为2R•例：23=8直觉证明(Intuition)•通过Hash把元素均匀散布到M=log2(N)个比特上•Hash结果为xxx0的概率为1/2•Hash结果为xx00的概率为1/4•当我们看到一个*100时，很可能已经pass过了4个不同的元素了。•估计：4个不同元素更形式化的证明•一个元素，hash后，尾部连续r个0的概率•(½)r=2–r•m个不同元素hash后的m个结果，尾部都不“连续r个0”•概率：(1-2–r)m==•出现连续r个0的概率1-•m2r，概率为1，即总能得到连续r个0的结果。•m2r，概率为0，即得不到连续r个0•所以，估计m=2r大致上是合理的。实际应用•问题：•R加1，2R就涨一倍。•E[2R]无穷大•解决办法•用多个hash函数，结果组合起来•组合办法•平均：偶尔一个大值对结果的影响很大，不好•中值：估计的结果总是2的幂次，取值不连续，也不好•解决方案：•样本分组•组内取平均•组间取中值矩估计Moments矩估计•N个到达的元素，统计各不同元素的流行度(Popularity)•不同元素的集合A，•各不同元素i出现的次数mi（流行度）•流行度的K阶矩•物理意义•k=0，A的size，即不同元素的个数。|A|•k=1，N，stream长度，元素个数•k=2，Surprisenumber（奇异数），Popularity分布均匀的度量Surprisenumber（奇异数）•Popularity分布的均匀程度的度量•例：•|A|=11：11个视频•N=100：100次用户观看•观看在视频上的分布•Case1：10,9,9,9,9,9,9,9,9,9,9•SurpriseS=910•比较均匀•Case2：90,1,1,1,1,1,1,1,1,1,1•SurpriseS=8110•更不均匀AMS方法•Alon,Matias,andSzegedy•以k=2为例•随机挑一个时刻，对stream采样•采样获得的值存在X.el里•然后对后面进来的stream中这个值计数，直到stream结尾•计数c存在X.val里•做多次，对最后的X.val，乘2，减1，乘n，然后求平