Misra-Gries算法

前言

Misra-Gries算法是频繁项挖掘中一个著名的算法。频繁项就是在数据流中出现频率最高的数据项。频繁项挖掘，这个看似简单的任务却是很多复杂算法的基础，同时也有着广泛的应用。

对于频繁项挖掘而言，一个简单的想法是，为所有的数据项分配计数器，当一个数据项到达，我们即增加相应计数器的值。但当数据流的规模较大时，出于内存的限制，我们往往不可能为每个数据项分配计数器。而Misra-Gries算法则是以一种清奇的思路解决了这个问题，实现了在内存受限的情况下，以较小的错误率统计数据流中的频繁项。

算法作者

Misra-Gries算法在1982年由华威大学的Misra和Gries提出。

频繁项

我们首先对频繁项进行形式化的定义。

给定一系列数据项，频繁项挖掘的目的只是简单地找到那些出现最频繁的数据项。通常我们定义这个问题为找到那些出现频率超过具体阈值的数据项。

定义1. 给定一个数据流 $S$ ，它包含 $n$ 个数据项 $t_1,\cdots,t_n$ ，那么一个数据项 $i$ 的频数为 $f_i=|\{j|t_j=i\}|$ 。而集合 $\{i|f_i>\phi n\}$ 中的元素，我们称为 $\phi-$ 频繁项。

例子. 对于数据流 $S=(a,b,a,c,c,a,b,d)$ ，有 $f_a=3,f_b=2,f_c=2,f_d=1$ 。如果设 $\phi=0.2$ ，那么频繁项有 $a,b$ 和 $c$ 。

Misra-Gries算法

即使 $\phi$ 的值很大，解决这个问题的算法也至少要花费 $O(n)$ 的空间。在这种情况下，一个错误率为 $\epsilon$ 的近似算法被提出。这就是我们的Misra-Gries算法。它的具体步骤如下：

Misra-Gries算法的伪代码

首先建立一个大小为 $k$ 的数组 $T$ 。

对于数据流中依次到达的项 $i$ 进行如下处理：如果项 $i$ 在数组 $T$ 中，则其对应的计数器 $c_i++$ ；如果项 $i$ 不在数组 $T$ 中，且数组 $T$ 中的元素个数小于 $k-1$ ，则将项 $i$ 加入数组 $T$ ，并为其分配计数器 $c_i=1$ ；其他情况，将数组 $T$ 中所有元素的计数器减1，此时如果数组 $T$ 中存在元素的计数器值为0，则从数组 $T$ 移除这个元素。

当完成对数据流的扫描后，数据 $T$ 中保存的 $k’(k’≤k-1)$ 个元素即是数据流中的频繁项。

Python实现

下面使用python3进行实现，其中数组 $T$ 和计数器 $c_i$ 使用字典实现。

def misra_gries(S,k):
    c = {}
    for i in S:
        if i in c:
            c[i]+=1
        elif len(c)<k-1:
            c[i]=1
        else:
            for j in list(c):
                c[j]-=1
                if c[j]==0:
                    c.pop(j)
        print (c)
    return list(c)

假设 $k=3,S=[1,2,1,4,2,1,5,2]$ ，那么程序的输出结果如下

{1: 1}
{1: 1, 2: 1}
{1: 2, 2: 1}
{1: 1}
{1: 1, 2: 1}
{1: 2, 2: 1}
{1: 1}
{1: 1, 2: 1}
[1, 2]
[Finished in 0.2s]

正确性证明

上面说到了这个算法是一个近似算法，这表明算法输出的结果并不一定是频繁项。Misra-Gries算法的错误率为 $\epsilon$ 。

定义2. 给定一个包含 $n$ 个数据项的数据流 $S$ ，上述的 $\epsilon-$ 近似算法返回一个集合 $F$ 。对于所有满足 $i\in F$ 数据项 $i$ ，都有 $f_i>(\phi-\epsilon)n$ ；并且不存在 $i \notin F$ 的数据项 $i$ ，使得 $f_i>\phi n$ 。

上面的定义表明，Misra-Gries算法输出的数据项并不一定是频繁项，但是频繁项一定在输出结果之中。后一句便是问题的关键了，它表明Misra-Gries算法可以确保找到数据流中的频繁项。下面我们对这一点进行简要的证明。

定理1. 计数器减一的操作最多执行了 $n/k$ 轮。

证明：当数组 $T$ 中元素的个数等于 $k-1$ 时，才会出现计数器减一的操作。此时，计数器值共减少 $k-1$ ，包括被舍弃的新数据项，计数器值之和共比实际到达的数据项的个数少 $k$ 。由于最后的计数器值之和是大于 $0$ 的，且数据流中数据项的个数为 $n$ ，所以计数器减一的操作最多执行了 $n/k$ 轮。

定理2. 当 $k=\left\lceil\frac{1}{\phi}\right\rceil$ ，所有的 $\phi-$ 频繁项都会被Misra-Gries算法检测出。

证明：由定理1可知，计数器减一的操作最多执行了 $n/k$ 轮。因此，算法结束时，数据项 $i$ 计数器的值 $c_i$ ，满足 $c_i\leq f_i\leq c_i+n/k$ 。对于所有不在数组 $T$ 中的数据项 $i$ ，有 $c_i=0$ ，于是 $f_i\leq n/k\leq \phi n$ 。故所有满足 $f_j>\phi n$ 的数据项 $j$ ，即所有的 $\phi-$ 频繁项都会被Misra-Gries算法检测出。

参考

[1] Cormode G. Misra-Gries Summaries[M]. Springer US, 2014.
http://dimacs.rutgers.edu/~graham/pubs/papers/encalgs-mg.pdf。