Research On Maximum Frequent Itemsets Based On FP-Tree

Association rules is one of the important research field of data mining. The main solution is the relationship between the data and many other interesting patterns. Maximum frequent itemsets algorithm is a classical algorithm of association rule algorithm, contains all information of frequent itemsets, and some data mining’s applications only need to mining maximal frequent itemsets. So it has very important significance for mining maximal frequent itemsets. But there are some problems in the classical maximum frequent itemsets algorithm: to generate recursively a lot of conditional FP-Tree; to check superset before storing current frequent itemsets every time; to run the mining algorithm again when updating the database.By studying the literature about association rule domestic and abroad, we found that the algorithm problems of time and space efficiency, and put forward three improvements, and prove the validity of the algorithm by experiment.(1) A new one-way sequential FP-Tree (OWSFP-Tree) is put forward to improve the efficiency. This thesis mainly introduces the properties, construction process and construction example of the OWSFP-Tree. Then by comparing with FP-Tree, we can find that the tree has the following advantages:a) saves the space resource; b) reduces the number of recursive algorithm; c) provides a basis for avoiding superset checking before each store the current frequent itemsets.(2) A new maximal frequent itemsets mining algorithm NCFP-Max(Not generating Conditional FP-Tree to obtain MFS), which based on OWSFP-Tree and the item form is proposed. This thesis mainly introduces the properties、 strategy、algorithm flow and algorithm example of NCFP-Max algorithm. Experimental results show that the NCFP-Max algorithm in the same mining environment can improve mining efficiency and reduce computational time about50%than FP-Max.(3) An Incremental updating algorithm for mining maximum frequent itemsets based on decreasing dimension of frequent itemsets is proposed to generate new maximum frequent itemsets using the maximum frequent itemsets and OWSFP-Tree in the context of adding new records to the transaction database accidentally. This thesis introduces the properties, algorithm flow and algorithm example of the incremental updating algorithm. Experiments show that the incremental updating algorithm for mining maximum frequent itemsets based on decreasing dimension of frequent itemsets has a higher efficiency than FP-Max and NCFP-Max algorithm in the context of adding new records to the transaction database.Finally, this thesis summarizes all the work, and put forwards the future research direction.