每周学点大数据 | No.12数据流中的频繁元素
No.12期
数据流中的频繁元素
Mr. 王：我们再来讲一个例子，数据流中的频繁元素。我们先来说说大数据的数据流模型。
小可：数据流，是流动的数据的意思吗？和我们前面说的水库抽样是不是很像？
数据流
Mr. 王点点头，说：嗯，其实水库抽样也是以数据流的思想来处理的。顾名思义，数据流意味着数据在流动，数据会不断地到达计算系统进行处理，这意味着一个数据只能被扫描一次，一旦处理过或者在内存中被放弃，就不能再访问了。你想想看，这在复杂度上意味着什么？
小可想了想，说：超过O(n)的算法肯定是不行的，只能寻找亚线性算法了。
Mr. 王：没错，而且数据流模型的数据是源源不断到来的，比如我们使用一个传感器进行感知，它就会按照一定的采样频率进行数据采集。其实传感器获得的数据就是一个典型的数据流，如果传感器一直在工作，我们就会得到源源不断的数据。但是不管是传感器使用的内存还是其他存储介质都不是无限的，这是符合客观现实的。所以对数据流进行处理，要求我们所使用的内存必须是亚线性的，最好是和数据量无关的。
小可：就像水库抽样一样吧，内存中随时保存着的都是对前面数据流的一个均匀抽样，而且所使用的内存有限，不论来了多少数据，都只保存k个，也是与数据量无关的。
Mr. 王：很好，这样用于概括数据的数据结构叫作数据概要，我们用有限的、与数据量无关的内存空间来维护这个数据概要，就是要对相关性质的当前状态做出一个有效估计。
数据流模型
我们说数据流模型是适用于大数据的，因为它仅顺序扫描数据一次，而且它的内存是亚线性的。数据流通常是来自某个域中元素的序列，<x1, x2, x3, x4,...>。
小可：这个序列里为什么没有末项xn？
Mr. 王：因为数据是源源不断的，所以没有末项。好了，我们来总结一下数据流模型的特点：
（1）数据流通常是来自某个域中元素的序列，< x1, x2, x3, x4,...>。
（2）数据量是远大于内存容量的，这意味着无法将所有的数据都放进内存中。内存的规模一般为O(logkn) 或者O(na)，显然a<1。
（3）要快速处理每一个数据，因为数据会快速地源源不断地到来，这也是很必要的一点。
小可：嗯，那我们将大数据视为数据流模型，可以拿来计算什么呢？
Mr. 王：应用就有很多了，有sum（求和）、max（最大值）、min（最小值）、count（计数）、avg（平均数）这样的基本统计量，还有比如中位数、频繁项、分析、挖掘、预警等。
我们还是举个具体的例子吧，这里有一组数字：32,12,14,32,7,12,32,7,6,12,4。
Mr. 王：你说说看，前面提到的统计量哪些是比较容易计算的？
小可：前面讲解选择排序时，讲过求min的方法，我觉得那个方法同样适用于数据流，只要拿出一个变量来保存当前的最小值，发现比它更小的就将其替换掉；max与之同理。求和sum也是很容易的，只要用一个变量来保存当前的加和，每到来一个数据，就把它加进这个变量里。至于count，初始化为0，然后每到来一个数据，就把它加1。如果要求平均数avg，就同时维护sum和count作商。
Mr. 王：很好，可以看出，这样的数据概要是单个值，同时它也是一个可合并的值。在这里，“可合并”就是指两部分数据流的数据概要可以直接通过诸如累加和比较这样的操作合并成整个数据流的概要。
小可：嗯，比如我们要求200个数据的最大值，前100个数据的最大值和后100个数据的最大值的较大者，就是200个数据的最大值。
Mr. 王：现在我们来处理一个复杂一点的问题——频繁元素。为了研究方便，我们用n来表示不同元素的个数，用m来表示元素的总个数。你先来想一想，如果要求出一个精确解的话，可以用什么方法？
小可：可以用这样的方法：
（1）为每一个单独元素设置一个计数器。
（2）当处理一个元素时，增加相应的计数器。
Mr. 王：这样做有什么问题吗？
小可：如果每个元素都有自己的计数器，就需要有n个计数器，这样没有满足o(n)的要求，相当于内存需要存储所有的数据，这对于数据流来说是不能实现的。
Mr. 王：嗯，所以我们提出如下的方法：
（1）处理一个新到来的元素x 时；
（2）If已经为其分配计数器，增加之；
（3）ElseIf 没有相应的计数器，但计数器个数少于k，为x 分配计数器k，并设为1；
（4）Else 所有的计数器值减1，删除值为0 的计数器。
这个算法称为MisraGries（MG）算法。第一种情况，如果内存中已经有新到来元素的计数器，则只需要将其值加1即可；第二种情况，如果还没有为新到来的元素提供计数器，并且内存没有被填满时，则可以为这个元素的计数器开辟新的空间；第三种情况，当新到来的元素没有被分配计数器，同时内存中的计数器个数已经达到了k个，也就是分配的内存空间已经被填满时，则将所有的计数器值减1，删除值为0的计数器，此时内存中就重新有位置了，我们再为这个新到达的元素分配一个计数器即可。当然，别忘了要将其置为1。
内容来源：灯塔大数据