paulfedorow / fim

fim is a collection of some popular frequent itemset mining algorithms implemented in Go.

fim

fim is a collection of some popular frequent itemset mining algorithms implemented in Go.

fim contains the implementations of the following algorithms:

• apriori: Based on Fast Algorithms for Mining Associations Rules. As an optimization, the approach to determine the support of the candidates with a hash-tree and a transaction bitmap was replaced with an approach based on a trie. As a further optimization, the generation of candidates of length 2 is omitted in favor of counting each occurring item pair in a 2D map.
• eclat: As described in Scalable Algorithms for Association Mining. The paper describes and analyses several approaches. The eclat algorithm is implemented based on the approach named Eclat. For the determination of frequent itemsets of length 2, a 2D map is used instead of a 2D array as described in the paper.
• fpgrowth: Based on Mining Frequent Patterns without Candidate Generation. Implemented mostly as described in the paper. The only difference is that there is no special-casing implemented for FP-trees that are paths.

Build

Execute the following commands to build the fim tool:

git clone https://github.com/paulfedorow/fim.git
cd fim
make

Usage

To see which arguments fim supports execute the following command:

build/fim -h

The following example finds all frequent itemsets with a minimal support of 1% in the dataset contained in datasets/retail.dat:

build/fim -a fpgrowth -i datasets/retail.dat -s 0.01 

Dataset format

fims dataset file format is as follows:

File = {Transaction}
Transaction = Item {" " Item} "\n"
Item = {"0" ... "9"}

Each line in the file is a transaction. A line is expected to be a series of integers separated by a single space. Each integer is an item of the corresponding transaction.

Performance

To determine which algorithm is the most efficient, the runtime of each algorithm was measured with different datasets and decreasing minimal support. The datasets that were used are retail.dat and chess.dat from FIMI Dataset Repository. The datasets are respectively sparse and dense. The results are shown below. The algorithm fpgrowth is best in terms of runtime.