一种基于Chernoff Bound的数据流上近似频繁项集的挖掘方法

摘要

数据流高速、无限和动态的特点决定了必须在有限的内存中以尽快的计算速度完成流数据上的频繁项集挖掘.将数据流中的数据按照段进行划分,采用二元组列表的数据结构进行保存,提出了一种基于滑动窗口的近似频繁项集挖掘方法AFIoDS,以实时获取频繁项集集合的真子集,并引入了概率参数,利用Chernoff Bound来动态改变支持度的近似值,保证真子集中的频繁项集被限制在一定的误差范围之内.此外,为了进一步节省内存,AFIoDS采用闭合项集的形式压缩每个段中获取的频繁项集.通过在3种真实数据集上的实验表明,AFIoDS算法与现有算法相比,在精度没有下降的情况下,具有更快的处理速度,同时其存储开销大大降低.%A data stream is fast, unlimited and dynamic, these characteristics constraint the computational resources and storages when mining frequent itemsets. This paper addressed this problem and proposed a simple and effective algorithrn AFIoDS, AFIoDS is an approximate algorithm based on sliding window model,which splits stream data into batches and maintains them with 2-tuple lists;thus,a false negative result can be obtained using a probabilistic parameter based on chernoff bound. The approximation will be changed dynamically to guarantee the mining frequent itemsets are error controllable. Plus, a compression of frequent itemsets, the closed frequent itemsets, are employed to represent the results of each batch for further memory saving. Our experimental results on 3 real world data show that without precision reduction, AFIoDS achieves a faster speed and a much reduced memory cost in comparison with the state-of-the-art algorithrna.