Chernoff Bound Based Approximate Frequent Itemset Mining Method over Streams
一种基于Chernoff Bound的数据流上近似频繁项集的挖掘方法

A data stream is fast, unlimited and dynamic, these characteristics constraint the computational resources and storages when mining frectuent itemsets. This paper addressed this problem and proposed a simple and effective algorithm 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 parameterbased 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, arc 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 statcof-thcart algorithms.