1、流数据挖掘课程中介绍了几个主要的功能：1）抽样，2）过滤 3）计数
1）抽样：对于大量的数据进行抽样，如果抽取固定长度的数据。保持窗口的长度不变，新进入的数据以一定的概率进行替换原来窗口中的数据
具体介绍：设置固定窗口大小为Ｎ　
对于每个用户产生一个随机数，如０－９如果随机数为０　则保留，否则丢弃，这样就只保留了１/10的用户
2）过滤-布隆过滤器：垃圾邮箱的过滤，如果正常邮箱有1亿个，使用hash函数将正常邮箱中散列后到内存分配的80亿的字节中，正常邮件散列的值为1。每次新来一个邮箱的时候，进行散列，如果结果为0必定是垃圾优邮箱，如果是1则可能是垃圾邮箱，可能是正常邮件。此处会误判，但是可以过来调大部分的垃圾邮件。
优化：可是使用多个哈希函数
3）计数DGIM：二进制字节流中，如果最大可以存储的数组大小为N(滑动窗口大小) ，统计最近的k个字节中有多少个1
统计误差最大为50%

image.png

元素是从右向左进入的，右边的元素为最新的元素，桶有两个标记，桶最右边的元素的时间戳也就是位置
桶的大小
DGIM将数据分桶，需要满足的条件为：
1）每个桶中的1的个数是2的次幂，2^n n称为桶的大小
2）2的大小从右向左增大
3）相邻的桶的的大小可以相同，但最多有两个桶相同

数据不断进入的过程，DGIM的条件需要满足，
这也就是说如果新进入的数据为1 ，那么生成1个桶，如果有三个大小为1 的桶，那么合并前两个桶，
循环这个操作向前
如果桶中元素的数目超过最大数据N ,那么左边的桶丢弃

计算的过程：如果要统计最近的k个元素中1的个数，只需要根据时间戳来计算，如果中间桶分别为
d+1,d,d-1.根据时间戳 计算到桶d数量小于k.到d+1数据量就大于k了，则
计算k个元素中1的数据的方法为。右边所有桶中1的数量，加上d桶中1的数量的1/2
误差最大为50%

其他的应用：数据求和，但是要求数据为2的次幂才方便使用

4）矩估计& 独立元素统计
4)衰减窗口
统计当前最常见的元素

image.png

衰减窗口可以用来统计最近最流行的元素，如最热的电影，亚马逊最近的产品销量榜等
对于每部电影刘一个独立的位数。个人理解。可以将所有的电影的种类作为一个数组，一个元素代表一部电影，每次新来一个元素代表一个电影票房，数组元素分别标记为f1,f2,f3,f4 ....其数值为一个ai(1-c)^i的累计和。ai表示该电影票房是否是该电影，如果是那么ai=1 否则ai=0.这样如果新来一个电影票房，则首先，数组内所有电影的元素值 *（1-c）这是为了将之前的票房的权重降低，先后增加at,如果电影票对应是数组内对应的电影，那么at=1，否则at=0
来一个电影标房

image.png