# MISFP-Growth: Hadoop-Based Frequent Pattern Mining with Multiple Item Support
## 3 Hadoop-Based Frequent Pattern Mining Architecture  
To enhance the efficiency of FP mining with multiple item support, we propose an architecture (named the MISFP-growth algorithm) based on a distributed computing environment, known as Hadoop MapReduce. The main idea of the MISFP-growth algorithm is to split the transaction datasets into sub-transaction DBs according to item support, and then to analyze them respectively. More specifically, transactions that contained items with identical item support would be grouped to form a sub-transaction DB. Then, the FP-growth algorithm constructed an FP-tree from these sub-transaction DB and then mine the frequency patterns. To further improve efficiency, we implement the MISFP-growth algorithm on distributed architecture, which enables individual analysis of the sub-transaction DBs. Finally, the analysis results from each reducer were further aggregated to generate association rules for the entire dataset. The proposed Hadoop MapReduce-based MISFP-growth \begin{table}
\begin{tabular}{c c c} \hline \hline
**Algorithm** & **Criteria** & **Algorithm Description** \\ \hline Apriori [PERSON] and [PERSON] (2006) & Single support & Generates candidate itemsets by scanning the database repeatedly to successfully mine the frequent patterns. \\  & & Scans the database only twice and without generating the candidate itemsets. Creates an FP-tree from which to mine the frequent patterns. However, when the MIN updates, the FP-tree must be reconstructed. \\  & & Sets different thresholds of support to identify more rare items. \\ MSApriori [PERSON] and [PERSON] (2006) & Multi-support & However, candidate itemsets are repeatedly created and this increases memory requirements and reduces performance. \\  & & The arrangement of the position and order of items in the \\ CFP-growth [PERSON] and [PERSON] (2006) & Multi-support & MIS-tree can be repeatedly adjusted by tuning the MIS. This method can increase search space requirements. \\ MISFP-growth [PERSON] and [PERSON] (2006) & Multi-support & Improves efficiency by discarding two major steps, \\  & & post-pruning and reconstruction. \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Comparison of frequent patterns mining algorithm. algorithm consists of two phases, a counting support phase and an analytics phase, executed in seven steps, as depicted in Figure 1, and detailed below. Step 1: data preprocessing. Step 1 cleans the original transactional DB and enables the decision maker to set multiple item supports. As shown in 1 of Figure 1, the concept of \"divide and conquer\" is applied to the original transactional DB, which is divided into several blocks. Then, each data block is assigned to different mapper nodes for further item support counting. Step 2: item support counting by mapper nodes. Step 2 calculates the actual frequency for each item. As 2 of Figure 1 illustrates, each mapper node scans the sub-transaction DB for item frequency statistics. In the traditional FP-growth algorithm, this operation is exceedingly time consuming. As expected, the proposed Hadoop-based architecture can release such loading efficiency because the item support counting occurs in parallel. Then, the counting results from the mapper nodes are shuffled to the reducer nodes in Step 3 for further aggregation. Step 3: item support aggregation by reducer nodes. Step 3 scans the support of all items from the mappers to find the minimum of the multiple item supports (MIN-MIS). As shown in 3 of Figure 1, each item support is compared with the MIN-MIS, if the item support is less than MIN-MIS, then the item is discarded. Step 4: item sorting. The transaction is sorted in ascending order according to the support value and formed into new data groups. As shown in 4 of Figure 1, Step 4 generates new sub-transaction DBs based on item supports, assigning transactions from itemsets with identical support to the same sub-transaction DB and corresponding mapper nodes. Step 5: construction of MISFP-trees by mappers.