大数据背景下的数据流挖掘技术

朱彦杰

许昌学院

数据流处理在某种程度上包含流的汇总过程，考虑如何从流中抽取有用样本，以及如何从流中过滤大部分不想要的元素。估计流中的元素个数，其中估计方法所用的存储开销远小于列举所有所见元素的开销。

Web 网站收到的流包括各种类型，如百度一天收到几亿个搜索查询，新浪各个不同网站上收到数十亿个“点击”，基于这些流数据可以学习到很多有趣的结果，如某个链接的点击率的突然上升可能意味着有些新闻连向此网页，否则的话可能意味着该链接失效急需修复。

1 流数据

Web 网站收到的流包括各种类型，如百度一天收到几亿个搜索查询，新浪各个不同网站上收到数十亿个“点击”，基于这些流数据可以学习到很多有趣的结果，如某个链接的点击率的突然上升可能意味着有些新闻连向此网页，否则的话可能意味着该链接失效急需修复。数据以一个或多个流的方式到来，如果不对数据进行及时的处理或存储，数据将会永远丢失，即是数据到来的速度太快，以致将全部数据存在传统数据库并在选定的时间进行交互是不可能的。流数据处理所受的一些限制，一方面，流元素的分发速度通常很快，必须对元素进行实时处理，否则就会永远失去处理它们的机会，除非访问归档存储器。流处理算法通常在内存中执行，一般不会或者极少数访问二级存储器；此外，即使当数据流很慢时，也可能存在多个这样的数据流，即每个流本身能够基于很小的内存就能处理，但所有数据流的内存需求加在一起可能就很容易超过内存的可用容量。所以，当内存足够大时，流数据的很多问题很容易解决，而实际情况，在一个真实规模的机器上获得现实的处理速度，问题变得相当困难，需要采用新技术解决：1）通常情况下，获得问题的近似解比精确解要高效得多；2）为了产生与精确解相当接近的近似解，需采用哈希相关技术。

2 流当中的数据抽样

从流中选择一个子集，以便能够对它进行查询并给出统计上对整个流具有代表性的结果；流由一系列n 字段元组构成，这些字段的一个子集称为关键词段，样本的选择基于它来进行，比如，一个流由三元组（user，query，time）组成，其中user 可以作为关键词段。若关键词段包含的字段不止一个，那么哈希函数就要将这些字段的值组合起来形成单一的哈希值。最后得到样本由有某些特定键值的所有元组构成。为了保证样本由键值子集所对应的所有元组组成，可以选择一个哈希函数h，将键值映射到一个很大的取值范围0，1，…，B-1。另外，维护一个阀值t，它的初始值可以设置成最大的桶编号B-1。任何时候，样本都由键值K 满足h（K）＜=t 的元组构成。当且仅当满足同样条件的情况下，流中的新元组才会加入到样本中。如果样本中存储的元组数目超过分配的空间大小，那么就将阀值降低为t-1，并将那些键值K 满足h（K）=t 的元组去掉。为提高效率，还可以将阀值降低更多。无论何时需要将某些键值从样本中丢弃时，都可以将几个具有最高哈希值的元组去掉。

3 流过滤

只想接受流中满足某个准则的元组集合。如果选择的准则基于元组的某个可计算属性得到，那么选择操作很容易完成，当选择准则中包含集合元素的查找时，特别当集合大到无法在内存中存放时，问题就变得尤其困难；对此要去掉不满足选择准则的大部分元组，可以采用布隆过滤器：布隆过滤器的目的是让所有键值在S 中的流元素通过，而阻挡大部分键值不在S 中的流元素。一个布隆过滤器由如下几部分组成：

（1）n 个位组成的数组，每个位的初始值都为0；

（2）一系列哈希函数 h1,h2,…hk组成的集合。每个哈希函数将“键”值映射到上述的n 个桶（对应于位数组中n个位）中；

（3）m 个键值组成的集合S。

位数组的所有位的初始值为0。对S 中的每个键值K，利用每个哈希函数进行处理。对于一些哈希函数 ih 及S 中的键值K，将每个 hi(K)对应的位置为1。

当键值为K 的流元素到达时，检查所有的h1(K ),h2(K),… hk(K)对应的位是否全部为1，如果是，则允许该流元素通过，若有一位或多位为0，则认为K 不可能在S 中，于是拒绝该流元素通过。另外可以将多个过滤器串联起来使用来进一步过滤。

4 流中元素的数目统计

假定流元素选自某个全集，想知道流当中从开始或某个已知的过去时刻开始所出现的不同元素数目。如百度网站，它不需要登录就可以提交搜索查询，可能只能通过用户提交查询时的URL 来识别用户。这里所有可能的URL全集可以想象成所有登录主机名的全集。这需要在内存中保存当前已有的所有流元素，但是如果不同的元素数目太多，或需要即刻处理多个流，那么就无法在内存中存储所需数据。处理策略是仅仅对独立元素数目进行估计，具体思想是：通过将全集中的元素哈希到一个足够长的位串，就可以对独立元素个数进行估计。位串必须要足够长，以致哈希函数的可能结果数目要大于全集中的元素个数。流中的不同元素越多，那么不同哈希值也越多，在众多不同哈希值中，其中有一个值变得异常，该值后面会以多个0结束。任何时候在流元素a 上应用哈希函数h 时，位串h（a）的尾部将以一些0 结束，当然也可能没有0，尾部0 的数目称为a 和h 的尾长。假设流当中目前所有已有元素a 的最大尾长为R。那么将使用2R 来估计到目前为止流中所看到的独立元素数目。

上述估计方法有直观上意义：给定流元素a 的哈希值h（a）末尾至少有r 个0 的概率为2-r 。假定流中有m个独立元素，那么任何元素的哈希值末尾都不满足至少有r 个0 的概率为(1-2-r)m，该表达式可以改为((1-2-r)2r)m2-r。当r 相当大时，上式表达式就是(1-ε)1/ε，其大小约等于1/e。因此任何元素的哈希值末尾都不满足至少有r 个0 的概率为 e-m2-r。于是可以得到如下结论：（1）如果m 远大于2r，那么发现一个尾部长度至少为r 的概率接近1；（2）如果m 远小于2r，那么发现一个尾部长度至少为r 的概率接近0；基于以上两点结论，m 的估计值2R（R 是所有流元素中的最大尾长）不可能过高或过低。

5 总结

对任一到达流元素的键值进行哈希处理，使用哈希值来确定包含该键值的全部元素会是抽样样本的一部分。采用布隆过滤器允许属于某个特定集合的流元素通过，而大部分其他元素被丢弃。为了估计流中出现的不同元素的数目，可以将元素哈希成整数，这些整数可以解释为二进制整数，任意流元素的哈希值中最长的0 序列长度作为2 的幂得到的结果会作为独立元素数目的估计值。