# MISFP-Growth: Hadoop-Based Frequent Pattern Mining with Multiple Item Support
## 2 Literature Review  
This section summarizes association rule mining algorithms with single support and multi-support, and the Hadoop MapReduce architecture is explained.  
Association analysis attempts to determine the frequency patterns consisting of items in a dataset. The most well-known association mining algorithm is the Apriori algorithm [8; 9], which is developed to scan transactional databases iteratively and generate candidate frequent itemsets. Then, a threshold known as the support filters items to form the candidate itemsets based on their frequency of occurrence. When no additional candidate itemsets can be generated, the frequency patterns (FP) and associated rules are constructed for decision makers' reference. To improve the efficiency of FP mining, many researchers have attempted to reduce the effort for repeated database (DB) scanning. Thus, the FP-growth algorithm [10] emerged to facilitate FP mining by scanning the DB twice and without generating candidate itemsets. Both the Apriori and FP-growth algorithms have been shown to successfully mine frequent patterns.  
However, single item support cannot comprehensively address the complexity of items in large datasets. To apply the same single support to all items is unreasonable and insufficient. For this reason, since 1999, a considerable amount of research has focused on the MS-Apriori algorithm. The MS-Apriori algorithm applies the concept of multiple item support values to the traditional Apriori algorithm. Setting different values of support, the multiple item support (MIS) can realize decision makers' demands for highly detailed analysis [17]. The first step in MISFP mining is to pre-formulate the MIS for each item and sort all items in ascending order of magnitude. When using the Apriori algorithm in FP mining, the dataset is scanned to obtain candidate itemsets.  
Mining association rules with multiple item support (MIS) has become an imperative research topic. [PERSON] and [PERSON] (2006) proposed the Complete Frequent Pattern (CFP)-growth algorithm to improve the FP-growth calculation mechanism [PERSON] and [PERSON] (2006). The CFP-growth algorithm creates a MIS-tree that stores key messages with frequent item patterns. To improve the efficiency of the CFP-growth algorithm, the MISFP-growth algorithm discards two stages of the FP calculation, post-pruning and reconstruction [PERSON] and [PERSON] (2006). The MISFP-growth algorithm finds the minimum value of the multiple threshold values (MIN-MIS) and then drops the items that with less item support than the MIN-MIS. Thus, the search space is reduced. A comparison of FP mining algorithms is given in Table 1.  
Apache Hadoop is a cluster system of open source software framework composed of a series of function modules. The cloud service platform can store and manage big data, and is characterized by scalability, reliability, flexibility, and cost-effectiveness. The platform implements MapReduce distributed parallel computing architecture on the Hadoop Distributed File System (HDFS), which efficiently analyzes and stores large datasets [PERSON] et al. (2012); [PERSON] et al. (2012). The primary Hadoop operation applies the concept of \"divide and conquer.\" Through the map and reduce functions, the problem data from each node is decomposed into several smaller blocks for calculation. Then the calculation results from all nodes are transferred, collected, and arranged. One application of MapReduce incorporates the Apriori algorithm to understand the purchase requirements of customers and attract clients from competitor e-commerce websites [PERSON] et al. (2012).  
In summary, this study proposes advantages of using the Hadoop's parallel computing framework to overcome the drawbacks of existing single support association rule mining methods, and expresses the characteristics of each item. Using the MISFP-growth calculation method, we realize a two-stage solution that efficiently mines frequent patterns and association rules.