# MISFP-Growth: Hadoop-Based Frequent Pattern Mining with Multiple Item Support
## 4 Hadoop MapReduce-Based MISFP Growth Algorithm  
This section demonstrates the proposed MISFP-growth algorithm with an example implementation. Continuing the example given in the previous section, the transactional database as shown in Table 4a,b lists the actual support values and MIS of each item.  
As illustrated in Figure 3, first, the MISFP-growth algorithm scans the transactional database once to find the support value and determine the MIN-MIS = _MINlMIS(A)_, _MIS(B)_,..., _MIS(J)_} = 2 as shown in Table 4b. Next, the MISFP-growth algorithm sorts item {A} to item {Z} in ascending order according to item support to satisfy MIN-MIS. Therefore, items {D} and {F} are removed because their support is less than MIN_MIS. The results are presented in Table 4c. The MISFP-growth algorithm splits the transaction dataset into subgroups according to MIS values and assigns the subgroups to different mapper nodes. Each mapper node then scans the assigned sub-transaction DB to obtain the support value of each item and construct an MISFP-tree. This process resembles that of the frequency pattern tree constructed by the FP-growth algorithm.  
For example, a given mapper node handles the sub-transaction DB named Block \"A\" for which item support is two. The first root is created and labeled with a null node of the MISFP-tree. Then, additional nodes are inserted for the leading itemsets {E, G, H, I} of Block A. Figure 4 displays all the node links of each item.  
Each mapper node constructs an MISFP-tree and conducts frequency pattern mining. Using the node links of item {J} as an example, we establish a conditional pattern subtree with the following conditional pattern base: {A, B, I :1}, {A, B, C :1}, and {C, E, G :1}. Nonetheless, the MIS of item {J} equals two. Hence, frequency patterns involve items {A} and {B}, thus we mine (<A :2, B :2 > |J). As a result, we mine all the frequency patterns of item {J}, which are {B, J :2}, {A, B, J :2}, {A, J :2}.  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline \multicolumn{2}{c}{**(a)**} & \multicolumn{3}{c}{**(b)**} & \multicolumn{3}{c}{**(c)**} \\ \hline
**Transaction ID.** & **Transaction** & **Items.** & **Support** & **MIS** & **TID.** & **Trans. (ordered)** \\ \hline
1 & B, A, C & A & 6 & 4 & 1 & A, B, C \\
2 & E, D, H, G, I & B & 6 & 4 & 2 & E, G, H, I \\
3 & C, A, B, J & C & 5 & 4 & 3 & A, B, C, J \\
4 & E, C, G & D & 1 & 5 & 4 & C, E, G \\
5 & B, A, J, I & E & 4 & 3 & 5 & A, B, I, J \\
6 & A, B & F & 1 & 4 & 6 & A, B \\
7 & G, C, F, E, J & G & 4 & 3 & 7 & C, E, G, J \\
8 & B, A, G & H & 2 & 2 & 8 & A, B, G \\
9 & H, A, I & I & 3 & 2 & 9 & A, H, I \\
10 & C, E, B & J & 3 & 2 & 10 & B, C, E \\ \hline \hline \end{tabular}
\end{table}
Table 4: Transaction database, actual support and multiple item supports (MIS) of each item.  
Next, we combine the mined frequent patterns results obtained by all the different mapper nodes. Duplicate items are merged to obtain an aggregate output. According to the data mining output generated by this example, the results of the mining process are shown in Table 5. The most interesting output of the proposed algorithm was its detection of rare patterns. General association rules using a single item support, would also have identify itemsets like {plastic gloves, toothbrush}, {polymeric glass detergent, plastic gloves, toothbrush}, and {polymeric glass detergent, toothbrush}, namely items {A}, {B}, and {J}. However, we also discovered the rare patterns of items {A} and {I}, which represent the polymeric glass detergent and baking soda. This might indicate that baking soda is used to clean glass or other household surfaces.  
As demonstrated in the Figure 4, the proposed model was implemented in Hadoop-based environment. In addition, the proposed model enables decision makers set up multiple item support. Therefore, the MISFP-growth can generate valuable patterns of rare item without numerous meaningless patterns.  
Figure 4: MISFP-tree with new data groups in different mapper nodes.  
Figure 3: Demonstration of the proposed model.