Incremental frequent itemsets mining based on frequent pattern tree and multi-scale

摘要

Multi-scale can reveal the structure and hierarchical characteristics of the data objects to reflect their essence from different perspectives and levels. An incremental frequent itemsets mining algorithm based on frequent pattern tree is proposed by incorporating multi-scale theory(simplified to FP-tree and Multi-Scale based Incremental Mining, FPMSIM). FPMSIM uses the classic FP-Growth to construct a pattern tree and generate frequent itemsets for more fine-grained dataset which is called benchmark scale dataset. The newly added dataset is also independently mined as a benchmark scale dataset. The ultimate frequent itemsets for the target scales are derived by means of the scale-up process. In which, some unknown itemsets counts need to be estimated by comparing the similarity among benchmark scale datasets. In this way, severe dataset rescanning and tree structure adjustment overhead are avoided during the maintenance process. The experimental results show that although the support estimation error will lead to incomplete frequent itemsets mining, it can be offset by the performance gains in the mining efficiency and I/O cost, especially in the field of big data.