基于计数的数据流频繁项挖掘算法

Algorithm Based on Counting for Mining Frequent Items over Data Stream

挖掘数据流的频繁项已受到广泛关注,经典的频繁项挖掘算法尽管能够比较好地找到频繁项,但对频繁项频数的估计往往存在较大误差.SRoEC(segment rotative efficient count),SReEC(segment reserve efficient count)和RFreq(reserve frequent)算法针对该问题,继承基于计数的算法思想,将计数器进行划分并定义相应的操作,以期提高频数统计准确度并减小"噪音"影响.实验和数据分析表明,这些算法不仅能够保证频数超过阈值的数据项都能被找到,而且大大提高了频繁项频数统计的准确性.在同样空间代价下,算法无论在模拟数据集和真实数据集实验中,都表现出较高的频数准确率、较低的频数偏差率和较高的频数保有率,尤其是数据分布较平缓时,算法优势更加明显.

Mining frequent items over data stream has drawn great attention, and large amount of efficient algorithms have been proposed by many researchers over the past decades. Although the classical algorithms are well suited to find frequent items, usually they do not perform well when estimating items＇ approximate frequency. To solve this problem, we introduce a series of counter- based algorithms called SRoEC （segment rotative efficient count）, SReEC （segment reserve efficient count） and RFreq （reserve frequent）. They divide the counter used in classical algorithms and define operations for counters to improve the accuracy of item frequency and avoid the effect of low frequency items. As the experience shows, these algorithms can find Top-K items above the threshold correctly and return their approximate frequency as accurate as possible. Both analysis and experiments demonstrate that under same cost of space, these algorithms return higher count accuracy rate, lower frequency error rate and higher frequency reserve rate on both simulated data set and real data set when compared with the two best classical algorithms （frequent algorithm and space saving algorithm） nowadays. Amongst them, RFreq algorithm shows obvious advantages. What＇s more, the algorithms perform much better than classical ones when the data distribution is smooth.