有损计数算法如何查找频繁项？

用户支持两个输入参数，包括最小支持阈值σ和先前指示的误差范围ε。理论上，传入的数据流被划分为宽度为w = [1/ε]的桶。

设N为当前数据流长度，即到目前为止查看的项目数。该算法需要一个频率列表数据结构来存储所有频率高于0的元素。对于每个项目，列表支持f（近似频率计数）和∆（f的最大可能误差）。

该算法如下所示对项目进行分桶。当一个新的桶到达时，桶中的项目将被插入到频率列表中。如果列表中存在给定项目，则可以简单地增加其频率计数f。否则，可以将其添加到列表中，频率计数为1。如果新项目来自第b个桶，则可以将其频率计数的最大可能误差∆设置为b-1。

每当获得桶边界（即N达到宽度的倍数w，包括w、2w、3w等）时，就会确定频率列表。设b为当前桶号。如果对于某个条目，f + ∆ ≤ b，则删除该条目。通过这种方法，算法的目标是保持频率列表较小，以便它可以放入主内存中。为每个项目保存的频率计数将是项目的真实频率或其最小值。

近似算法中的重要因素是近似比（或误差范围）。让我们看看删除项目的情况。当项目的f + ∆ ≤ b时出现这种情况，其中b是当前桶号。

可以理解的是b ≤ N/w，即b ≤ εN。项目的实际频率最多为f+∆。因此，可以最小化项目的εN。如果该项目的实际支持度为σ（这是将其视为频繁项目的最小支持度或下界），则实际频率为σN，而频率列表上的频率f应至少为(σN −εN)。

因此，如果我们输出频率列表中所有f值至少为(σN −εN)的项目，则将输出一些频繁项。此外，还将输出一些非频繁项（实际频率至少为σN −εN，但小于σN）。

Ginni

更新于：2022年2月17日

820 次浏览

开启你的职业生涯

完成课程获得认证

开始学习