挖掘数据流

  在许多数据挖掘场景中，我们预先知道整个数据集。但是有时数据输入速率是由外部决定的，例如谷歌查询和推特与脸书的状态更新，这就涉及到了数据流的挖掘。

流数据模型

  输入元组可以在一个或多个流中快速输入。要求：流不需要具有相同的数据速率，一个流的元素之间不需要是时间均匀的。随之而来的问题是系统不可能存储所有的数据。那么如何利用有限的流量进行关键计算？从需要出发先分析两个形式的查询。Ad-hoc查询：正常查询一次询问流例，如到目前为止在流中看到的最大值是多少。标准查询：询问所有时间的流的查询，例如：报告在S流中看到的每个新的最大值

应用

挖掘查询流

-谷歌想知道今天比昨天查询更频繁的是什么

挖掘点击流

-雅虎想要知道在过去一小时里，它的哪一个页面获得了异常数量的点击

IP数据包可以在交换机上被监视

-收集信息以备不时之需
-检测拒绝服务攻击

挖掘监测数据

-每台监控摄像机每隔一秒钟就会产生一系列图像
-发现安全威胁

在流中抽样数据

  在流中抽样数据的目标是从流中提取可靠的样本。举一个提示性的例子：一个搜索引擎接收到一系列查询，它希望研究典型用户的行为。这些流由元组（用户、查询、时间）组成。需要回答诸如：在过去一个月里，典型用户的问题重复了多少次，假设我们只希望存储1/10的流元素。一个很容易被想到但不对的方法：先产生一个0到9之间的随机数，如果随机数是0则存储元组
  反例：假设一个用户产生了一个s查询，其中d被查询了两次，没有一个查询超过了两次。正确答案是 d/(s+d)，用上面的解决方法我们得到的是d/(10s+19d)。

解决方法

  有键的元组流：键是每个元组主键的某个子集，例如元组（用户,搜索，时间)，键是用户；键的选择依靠应用程序。得到一个大小为a/b的样本：将每个元组的键统一哈希到b个桶；如果其哈希值a为最多，则选择该元组。

保持一个固定大小的样本

  假设我们需要保持样本的大小正好是s例如：主内存大小约束。事先不知道流的长度：事实上，流可以是无限的。假设在t时刻我们看到了n项:确保每一项在样本中都有等概率s/n。
解决方案
  存储流的所有第一个s元素。假设我们看到n- 1个元素，现在第n个元素到达(n > s)：对于概率s/n，选择第n个元素，否则就丢弃它；如果我们选择第n个元素，它会替换样本中的一个s元素，随机选择。声明:该算法用于维护一个具有所需属性的样本也就是说，在长度为n的流中，所有位置被选中的概率都相等为s/n。
用归纳法证明:假设在n个元素之后，样本包含到目前为止看到的概率为s/n的每个元素。当我们看到元素n+1时，它的概率是s/ (n+1)。对于样本中已经存在的元素，留在样本中的概率为s/(n+1)
  滑动窗口。流处理的一个有用的模型是查询是关于长度为N的窗口，即接收到的N个最近的元素。备选项:在时间间隔T内接收的元素。有趣的情况:N太大了，不能存储在主内存中。或者，有太多的流，所有的windows都不适合主内存。

过滤流

  过滤:接受流中满足条件的元组。过滤的标准：可计算的元组属性(容易)；查找集合中的成员，其中集合太大，无法存储在主内存中(有趣)，在这种情况下可以使用布鲁姆过滤器。其可以应用在Web爬虫中过滤抓取的url；在黑名单中过滤电子邮件；在黑名单中过滤恶意软件。

过滤流:布鲁姆过滤器

  布鲁姆过滤器组成：一个由n个位组成的大数组，几乎都是0；一个散列函数h1, h2……hk的集合。每个哈希函数将键值映射到n个桶，对应于位数组的n位；m个键值的集合S。
查找：假设元素y出现在流中，我们想知道是否见过y，我们需要为每个散列函数计算hi(y) 1<=i<=k。如果所有生成的位位置都是1，就说我们以前见过y。错误的假设是可能的如果这些位置中至少有一个是0，就说我们以前没见过y。这种方法当然是对的。

过滤流:Bloom Filter示例

  查找：假设我们有和之前一样的布隆过滤器，我们将过滤器设置为10100101010；查询:我们看到y=118了吗？
解决方案
y = 118 = 1110110(二进制)
h1(y)=14模11 = 3
h2(y)= 5模11 = 5
第5位是1，第3位是0，所以我们确定y不在集合中。

布隆过滤分析

  误报的概率取决于数组中1的密度和散列函数的数目，1的数量大约是插入元素的数量乘以哈希函数的数量，但是碰撞稍微降低了这个数字。

布隆滤波分析:投掷飞镖

  将随机位从0转到1就像随机地向t目标投掷d镖一样。一个镖至少击中了多少目标？给定的目标被给定的镖命中的概率= 1/t。没有被d飞镖命中给定目标的概率是(1- 1/t)^d
重写为(1- 1/t)^t(d/t) ~= e^- d/t，因为(1- 1/t)^t~=1/e对于 t很大。

布鲁姆滤波分析:投掷飞镖的例子

  假设我们使用一个10亿比特的数组,5个哈希函数,我们插入1亿个元素。即t=10的9次幂，并且d=5*10的8次幂。剩下的0的分数是e^(- 1/2)=0.607密度1 = 0.393。

在窗口中计数

  你可以表明，如果坚持对窗口中的元素进行精确的求和或计数，那么就不能使用比窗口本身更少的空间。但是如果你愿意接受一个近似，你可以使用更少的空间。我们将把计算某种类型的元素的简单情况视为特殊情况。和是相当直接的延伸。
  计算部分：问题:给定一个0 s和1 s的流，准备回答以下问题:在最近的k位中有多少个1 ?其中k <= N；简单解决方案:存储最近的N位；但是回答这个问题需要很O(K)时间，这个时间很可能要太长。例如:一些计算，像计算一个站点的url最近的点击率。流是URL 的序列，窗口大小N= 10亿。将数据看作多个流——每个URL对应一个流。URL x的流上的位是0，除非实际的流有x，那么则为1。

DGIM方法

  每个流只存储O(2logN)位，其中N是窗口大小。给出大概的答案，不要超过50%。使用更复杂和按比例增加的存储位，误差因子可以减少到任何大于0的数。

时间戳

  流中的每个位都有一个时间戳，开始0,1，……。记录时间戳的模N(窗口大小)，因此我们可以用O(log2N)位表示任何相关的时间戳。

存储桶

  桶是窗口的一部分;它由一个记录组成：它的时间戳的端点O(logN)位，在它的开始和结尾之间1的数目等于桶的大小。桶大小限制:1的数目必须是2的幂。因此，此计数只需要O(loglogN)位。

用桶表示流

  桶的要求： 桶的右端总是1和1的正数；每个带1的正数都在某个桶里；一个或两个桶任意大小，直到某个最大大小；所有尺寸都必须是2的幂；桶不重叠；桶是按大小排序的:旧桶并不比新桶小；更新桶：当一个新比特进来时，如果最后一个(最老的)桶的结束时间在当前时间之前的N个时间单位之前，则将其丢弃。如果当前位为0，则不需要进行其他更改;如果当前位是1,为这个位创建一个大小为1的新桶 结束时间戳=当前时间。如果现在有3个桶大小为1，那么将生成时间最久的2个桶合并为2个桶，如果现在有3个2码的桶,将生成时间最久的2码的桶合并成4码的桶，依次类推。

查询

  估计最近k<=N位中1的个数，找到具有最早的时间戳的桶b，该时间戳至少包含k个最近的位。估计1 s的个数是所有桶的大小之和比桶b最近，加上桶b本身的一半大小。误差范围：假设范围内最老的桶的大小是2^i。然后通过假设2 ^(i- 1)的1仍在窗口中,我们使错误最多2 ^ (i- 1)。因为每个大小小于2ⁱ的桶至少有一个，而且最老的桶至少有一个，所以真正的和不小于2^i。因此，错误最多为50%。空间要求:我们可以用O(logN)位表示一个桶;任何桶的大小都不能大于N;最多有两个桶大小相同(范围1到logN);最多有2logN桶;因此，所需空间为O(log2N)。

流的聚类

集群的流

  某些空间中的数据点流(欧几里得或非欧几里得)问题：对于任何m<=N，从该点的最后m个点组成的最佳簇的中心或簇(簇的代表点)。我们将考虑一些可能的解决方案，这取决于我们对集群如何在流中演化的假设。

BDMO算法

  BDMO算法是在DGIM算法的基础上构建的。关键的相似点和不同点是：和DGIM一样，流的点也被分成若干块，用桶来概括。在这里，桶的大小是它表示的点的数量，而不是流元素的数量是1。和以前一样，桶的大小遵守每个大小都有一个或两个的限制，直到某个限制。我们不假设允许桶大小的顺序从1开始。相反，它们只需要形成一个序列，其中每个大小是以前大小的两倍。例如:3,6,12,24。桶的大小不会随着时间的推移而减小。
  桶的内容包括桶的大小，桶的时间戳，一组记录，它们表示已将桶的点分区到的集群：群集中的点数；星团的质心或团簇；合并集群和保持与合并集群的完整参数集近似所需的任何其他参数。
  初始化桶：最小的桶大小是p乘以(2的幂)。因此，每一个p流元素，我们用最近的p点创建一个桶。每个桶的时间戳是桶中最近一点的时间戳。存储桶中的集群点(或者将它们作为一个集群保留)，计算集群的中心或clustroid并计算每个集群中的点。
  合并桶:类似于在流的计数为1的问题中合并桶。如果某个bucket的时间戳在当前时间之前超过N个时间单位，则删除它。如果有3个p大小的桶，合并3个中最老的两个。如果现在有3个大小为2p的桶，合并3个桶中最大的2个。如果现在有3个桶大小是4p，……
  合并桶(合并两个连续的桶):新桶的大小是正在合并的两个桶的两倍。新桶的大小是正在合并的两个桶的两倍。合并桶的时间戳是两个连续桶中最近的时间戳。考虑在两个桶中合并集群(取决于聚类算法)。

回答查询

  查询:请求流中最近m个点的集群(m<=N)。解决方案：选择覆盖m个点的最小的桶集。这些桶可能不超过2百万个点。假设:2m和m+1之间的点与最近的m点没有根本不同(为了更好的近似)。从选定的桶中收集所有集群，例如:如果您要求K- cluster，我们将继续合并，直到使用上面内容中合并桶的方法得到K- cluster。