Fast Frequent Patterns Mining by Multiple Sampling With Tight Guarantee Under Bayesian Statistics
提出MSFP算法，通过多次采样和贝叶斯统计，仅稳定频繁模式的支持度而非所有模式，从而用更小样本高效挖掘频繁模式，并保证质量。
Sampling from large dataset is commonly used in the frequent patterns (FPs) mining. To tightly and theoretically guarantee the quality of the FPs obtained from samples, current methods theoretically stabilize the supports of all the patterns in random samples, despite only FPs do matter, so they always overestimate the sample size. We propose an algorithm called multiple sampling-based FPs mining (MSFP). The MSFP first generates the set of approximate frequent items ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AFI$ </tex-math></inline-formula> ), and uses the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AFI$ </tex-math></inline-formula> to form the set of approximate FPs without supports ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathrm{ AFP}}^{*}$ </tex-math></inline-formula> ), where it does not stabilize the value of any item’s or pattern’s support, but only stabilizes the relationship <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\ge $ </tex-math></inline-formula> or < between the support and the minimum support, so the MSFP can use small samples to successively obtain the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AFI$ </tex-math></inline-formula> and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathrm{ AFP}}^{*}$ </tex-math></inline-formula> , and can successively prune the patterns not contained by the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$AFI$ </tex-math></inline-formula> and not in the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathrm{ AFP}}^{*}$ </tex-math></inline-formula> . Then, the MSFP introduces the Bayesian statistics to only stabilize the values of supports of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">${\mathrm{ AFP}}^{*}$ </tex-math></inline-formula> ’s patterns. If a pattern’s support in the original dataset is unknown, the MSFP regards it as random, and keeps updating its distribution by its approximations obtained from the samples taken in the progressive sampling, so the error probability can be bound better. Furthermore, to reduce the I/O processes in the progressive sampling, the MSFP stores a large enough random sample in memory in advance. The experiments show that the MSFP is reliable and efficient.