基于渐近取样的频繁项集挖掘近似算法

Research of Frequent Items Mining Approximate Algorithm Based on Progressive Sampling

为提高频繁项集挖掘性能,提出了基于渐近取样的频繁项集挖掘近似算法(Frequent Itemsets Mining Approximate Algorithm based on Progressive Sampling,FIMAA-PS),该算法使用渐近取样方法实现数据集的样本提取,基于当前样本输出结果自动配置下一轮循环挖掘的样本大小,并使用Rademacher均值对输出结果的频率偏差上限进行理论估计从而得到终止条件,最后通过单次样本快速扫描判断算法终止条件,输出挖掘结果。实验结果表明,不同于传统挖掘精确算法和使用静态取样的挖掘近似算法,FIMAA-PS在输出结果精准度和运行时间方面具有显著优势。

In order to improve the mining performance of frequent item sets, a frequent item set mining approximate algorithm based on progressive sampling （FIMAA-PS） is proposed. In FIMAA-PS process, it employs progressive sampling to extract the sample from the dataset, and then automatically configures the mining sample size during next iteration according to the current output, and then uses Rademacher average to compute the bound to frequency bias of output results to obtain the stopping condition. Finally, FIMAA-PS judges the stopping condition by single fast scanning of samples to output the mining results. The experimental result demonstrates that, different from the traditional mining exact algorithm and mining approximate algorithm based on static sampling, FIMAA-PS has a significant advantage in terms of accuracy and running time.