有损计数算法如何查找频繁项?
data miningdatabasedata structure
用户支持两个输入参数，包括最小支持度阈值 σ 和先前表示的误差界限 (用 ε 表示)。理论上，传入流被划分为宽度为 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)。
