1 Introduction

Frequent itemsets discovery “is one of the most important techniques in data mining” (Zhengui Li, 2012). It can find out the association relationships among events or data objects that are hidden in the data, even if the associated events or objects seems not related at all. Digging into these relationships will help to analyze events and “may disclose useful patterns for decision support, financial forecast, marketing policies, even medical diagnosis and many other applications” (Pramod S., 2015).

The Frequent itemset mining (FIM) methodologies are most popular and very well used by various researchers for finding frequent patterns among variables in large datasets (J. Manimaran1, 2013). Literature contains many approaches that tackle the FIM problem like Apriori, FP-Growth, multi-level frequent itemsets, DHP (Direct Hashing and Pruning), maximal association rule mining, primitive association rules, soft-matching rules and Buddy Prima.

There are many data mining techniques like association rules mining, correlation, sequential pattern analysis, classification and clustering that try to find interesting patterns in datasets. “The problem of mining frequent itemsets arose first as a sub-problem of mining association rules” (Yihua Zhong, 2010). The original motivation for finding frequent itemsets came from the need to analyze the “so called supermarket transaction data, that is, to examine customer behavior in terms of the purchased products” (Pramod S., 2015). FIM describes how often items are purchased together. For example, an association rules cheese, chips (80%) states that four out of five customers that bought cheese also bought chips. Such rules can be useful for decisions concerning products pricing, promotions, store layout and many others.

This paper is organized as follows. Section 2 formulates the problem statement of the FIM problem. Section 3 briefly introduces a literature overview and related work. Section 4 presents our proposed approach. Section 5 discusses our experimental results. Finally, section 6 summarizes our conclusions and future work directions.

2 Problem Statement

“Studies of Frequent Itemset (or pattern) Mining is acknowledged in the data mining field because of its broad applications in Market basket analysis, Medical diagnosis, Protein sequences, Census data, CRM of credit card business” (Akash Rajak, 2012), graph pattern matching, sequential pattern analysis, and many other data mining tasks (Pramod S., 2015). Finding an efficient way for mining frequent itemsets are very important for mining association rules as well as for many other data mining tasks. One of the major challenges found in frequent itemset mining nowadays is the large amount of data and how to use the multicore feature in the new hardware as well as the distributed architecture with large datasets. As a result the need for new frequent itemset mining algorithms that could tackle the new trends has emerged. In this paper we propose a parallelizable algorithm for FIM that could deal with big data sets exploiting the multicore feature of the hardware.

3 Literature Review

In this section a brief overview about the well-known FIM algorithms is presented. It includes: the AIS algorithm, Apriori, FP-Growth and algorithms that depend on prime numbers representation.

“The AIS algorithm” (Qiankun Zhao, 2003) “was the first algorithm proposed by Agrawal, Imielinski, and Swami for mining association rule” (Kumbhare et al, 2014). AIS algorithm depends on scanning the databases many times to get the frequent itemsets (Kumbhare et al, 2014). “The support count of each individual item was accumulated during the first pass over the database. Based on the threshold of support count those items whose count is less than its minimum value are eliminated from the list of items. Candidate 2-itemsets are generated by extending frequent 1-itemsets with other items in the transactions” (Kumbhare et al, 2014). “During the second pass over the database, the support count of those candidate 2-itemsets are accumulated and checked against the support threshold” (Kumbhare et al, 2014). “Similarly those candidate (k + 1)-itemsets are generated by extending frequent k-itemsets with items in the same transaction. The candidate itemsets generation and frequent itemsets generation process iterates until any one of them becomes empty” (Kumbhare et al, 2014). “AIS Algorithm has efficiency problems so some modifications have been introduced to give an estimation for candidate itemsets that have no hope to be large, consequently the unnecessary effort of counting those itemsets can be avoided” (Kumbhare et al, 2014). “Also since all the candidate itemsets and frequent itemsets are assumed to be stored in the main memory, memory management is also proposed for AIS when memory is not enough” (Kumbhare et al, 2014).

Original Apriori Algorithm is one of the well-known algorithms for mining frequent itemsets. It was introduced in (R. Agrawal, 1993). “The name of the algorithm is based on the fact that the algorithm uses prior knowledge of frequent itemsets properties” (G.S Almasi, 1989). “Apriori employs an iterative approach known as a level-wise search, where k-itemsets are used to explore (k + 1)-itemsets. First, the frequent 1-itemset is found, this is denoted by L₁, which is used to find the frequent 2-itemset L₂ and so on” (Pramod S., 2015). “To improve the efficiency of the level-wise generation of frequent itemsets, a property called Apriori property is used to reduce the search space” (R. Agrawal, 1993). “This property states that all nonempty subsets of a frequent itemset must also be frequent” (Pramod S., 2015). A two-step process is used to find L_k from L_k–1 1)

The join step: To find L_k, a set of k-itemsets is generated by joining L_k–1 with itself (G.S Almasi, 1989). Suppose L_k–1 contains items (A, B, C) then L_k set will contain (AB, AC, BC). This set of candidate itemsets is denoted C_k. 2)

The prune step: C_k is a superset of L_k that contains all frequent and non-frequent k-itemsets.

A scan of the database is done to determine the frequency of each candidate which exists in Ck, those who satisfy the minimum support is added to L_k for the next iteration and the other items are pruned.

AprioriTID algorithm (Manisha Girotra et al, 2013) tries to improve the performance of Apriori by avoiding multiple DB hits in the reading process. “AprioriTID doesn’t use the database for counting the support of candidate itemsets after the first pass” (Kumbhare et al, 2014). “The process of candidate itemset generation is the same like the original Apriori algorithm. Another set C′ is generated of which each member has the Transaction ID (TID) of each transaction and the frequent itemsets (present in this transaction where C_k^′ are in the form <TID, {X_k}> and each X_k is a potentially frequent k-itemset present in the transaction with identifier TID” (Kumbhare et al, 2014). “This set is used to count the support of each candidate itemset” (Kumbhare et al, 2014). Suppose that the original transaction database contains the following transactions associated with its transactions IDs

<TID, items > {(100, 1 3 4), (200, 2 3 5), (300, 1 2 3 5), (400, 2 5)}.

Then C₁ will be in form of (X_k=1, Support Count).

C₁ = {({1}, 2), ({2}, 3),({3}, 3), ({5}, 3)}.

C₁ frequent itemsets are used to generate itemsets for C₂ and the support count for each itemset generated in C₂ is calculated using another subset called C₂^′.

C₂ (itemsets) = {{1,2}, {1,3}, {1,5}, {2,3}, {2,5}, {3,5}}.

C₂^′ is derived from the original database taken into consideration only items equal or more than support threshold.

C₂^′ = {(100, {1 3}), (200, {2 3}{2 5}{3 5}), (300, {1 2}{1 3}{1 5} {2 3} {2 5} {3 5}), (400, {2 5}),………}.

To get the frequency of C₂ elements the search is done in C₂^′.

C₂ = {({1,2}, 1), ({1,3}, 2), ({1,5}, 1), ({2,3}, 2), ({2,5}, 3), ({3,5}, 2)}.

This method may lead to less number of scans.

“FP-Growth Algorithm is the most popular frequent itemset mining algorithm that was introduced in” (J. Han, 2000). “The main aim of this algorithm was to remove the bottlenecks of the Apriori algorithm in generating and testing candidate sets” (Pramod S., 2015). “The problem of the Apriori algorithm was dealt with by introducing a novel, compact data structure called frequent pattern tree or FP-tree” (Pramod S., 2015). “Then based on this structure an FP-tree based pattern fragment growth method was developed” (Pramod S., 2015). “FP-Growth uses a combination of the vertical and horizontal database layout to store the database in main memory” (Anjana Gosain, 2013). “Instead of storing the ID for every transaction in the database, it stores the actual transactions from the database in a tree structure and every item has a linked list going through all transactions that contain that item” (Anjana Gosain, 2013). “This new data structure is denoted by FP-tree (Frequent Pattern tree)” (J. Han, 2003).

CARMA Algorithm (C. Hidber et al, 1999) Continuous Association Rule Mining Algorithm. The algorithm mainly aims to process large online datasets (C. Hidber et al, 1999). CARMA algorithm comprises two phases during its operation: in the first phase CARMA builds “lattice of all potential large itemsets with respect to the scanned part of data” (C. Hidber et al, 1999). “For each set on the lattice CARMA determines the lower and upper limits of its support” (V. Pudi, 2001). The deduced association rules are displayed to the user after processing transactions and the user is free to adjust the support count (C. Hidber et al, 1999). In the second phase after getting the user’s feedback CARMA fully scans all the dataset to determine exactly the occurrences of each itemset and removes all the itemsets below the user’s specified threshold (V. Pudi, 2001).

4 The Proposed Algorithm (POBPA)

In this paper, we applied a new approach to parallelize Buddy Prima algorithm and optimize it to work more efficiently with Big Data and exploit the hardware parallelism capabilities. The new algorithm, called “Parallelizable Optimized Buddy Prima Algorithm” POBPA for short depends on greatest common divisor calculation between different transactions in the transaction database. Generally speaking, POBPA consists of two main steps:

1. Data preparation:
   Items and accordingly transactions are represented in the same manner as done by the Buddy Prima algorithm illustrated in the previous section. POBPA analyzes the transaction dataset and extracts single items with frequency equal to or higher than the support count specified by the user. Also it prepares ignore list for infrequent items and their combinatorials. After removing these infrequent items from the original dataset it calculates prime multiplications and string representation.
2. Frequent Itemsets Deduction (Greatest Common Divisor calculation (GCD)):
   By calculating the GCD between two transactions we can get the common items between these two transactions and by counting the highest repeated GCDs we get the frequent itemsets in the transaction dataset.

POBPA is not an architecture dependent algorithm it could be applied using different architectures like distributed environments, multiple core processors or GPUs. In this study POBPA exploits the multithreading feature which exists in JAVA to take the advantage of multithreading and multicore processors. POBPA works as multiple data single instruction (MDSI) with all nodes participating equally in the mining process to avoid any communication overhead between different nodes. POBA creates lightweight processes as the overhead of switching between threads is less. The Java Virtual Machine (JVM) spawns threads when the algorithm is run. Each thread works with part of the data and JVM takes the responsibility of orchestrating between them and consolidating the results.

5 Experimental Results

We experimented with datasets from different applications. These datasets were obtained from the UCI repository of machine learning databases (C.L. Blake, 1998). Table 5 below shows the characteristics of the datasets selected for the experiment. Our algorithm has the capability to work with datasets with a huge number of items (more than 15000 items per transaction). We used Retail dataset to show this capability for the proposed algorithm POBPA.

We compared the execution time of the proposed algorithm with FP-Growth and Parallel Apriori. The performance metric in the experiments is the total execution time taken and it was shown that POBA made a tremendous improvement especially with datasets that have huge number of items. We applied our experiments on the previously illustrated datasets using 30% to 70% minimum support threshold.

Table 6 compares the FP-Growth algorithm, Parallel Apriori algorithm and POBPA with respect to processing time using the Retail dataset. The Algorithms ran over the same machine (4 cores, 8 GB RAM).

Table 7, 8 and 9 make the same comparison using the Mushroom, Letter Recognition and Adult datasets respectively.

In Table 6 we could observe the interesting behavior of POBPA with the Retail dataset which includes a huge number of items. Our algorithm by far outperformed the FP-Growth and the parallel Apriori algorithms. The processing time ranges of both algorithms vary greatly as our distribution feature which fits multiprocessors results in great time enhancement which is more evident with increasing the dataset size. Tables 7, 8 and 9 also support the same observation.

6 Conclusion and future work

In this paper we have introduced a new technique for FIM. Our approach, POBPA, proved to excel other approaches found in the literature. POBPA is not an architecture dependent algorithm it could be applied using different architectures like distributed environments and multiple core processors. It aims to parallelize the Buddy Prima algorithm and also to optimize it to work more efficiently with Big Data exploiting the hardware parallelism capabilities. It depends on GCD calculation between different transactions in the transaction database. It assigns prime numbers in inverse proportional relationship to the item frequency which guarantees less value for prime multiplication and hence less storage and less computational complexity. POBPA achieves excellent results when comparing its execution time with FP-Growth and Parallel Apriori especially for dataset with large number of items.

Future work directions include applying POBPA to a distributed architecture with datasets containing millions of records. It could be applied using Hadoop Distributed File System (HDFS) and Map Reduce technique. Hadoop uses distributed file system method, which basically implements a mapping system to locate data in a cluster then MapReduce programming is used in the same servers which allows faster processing of data. It can deal with large volumes of unstructured data. Hadoop MapReduce takes minutes to process terabytes of data. POBPA could be applied on stream analytics to identify the response of social media to a certain topic.