Mining Frequent Itemsets using the PrePost / PrePost+ Algorithms (SPMF documentation)
This example explains how to run the PrePost / PrePost+ Algorithms using the SPMF open-source data mining library.
How to run this example?
- If you are using the graphical interface, (1) choose the "PrePost" or "PrePost+" algorithm, (2) select the input file "contextPasquier99.txt", (3) set the output file name (e.g. "output.txt") (4) set minsup to 40% and (5) click "Run algorithm".
- If you want to execute this example from the command line,
then execute this command:
java -jar spmf.jar run PrePost contextPasquier99.txt output.txt 0.4 in a folder containing spmf.jar and the example input file contextPasquier99.txt
or
java -jar spmf.jar run PrePost+ contextPasquier99.txt output.txt 0.4 in a folder containing spmf.jar and the example input file contextPasquier99.txt - If you are using the source code version of SPMF, launch the file "MainTestPrePost.java" or "MainTestPrePost+.java" in the package ca.pfv.SPMF.tests.
What is PrePost / PrePost+?
PrePost is a very recent algorithm (2012) for discovering frequent itemsets in transaction databases, proposed by Deng et al. (2012).
PrePost+ is a variation designed by Deng et al. (2015). It is reported to be faster than PrePost. Both implementations are offered in SPMF.
These implementations are faithful to the original. They were converted from the original C++ source code provided by Deng et al, and only contains some minor modifications.
What is the input of the PrePost / PrePost+ algorithms?
The input of PrePost and PrePost+ is a transaction database (aka binary context) and a threshold named minsup (a value between 0 and 100 %).
A transaction database is a set of transactions. Each transaction is a set of items. For example, consider the following transaction database. It contains 5 transactions (t1, t2, ..., t5) and 5 items (1,2, 3, 4, 5). For example, the first transaction represents the set of items 1, 3 and 4. This database is provided as the file contextPasquier99.txt in the SPMF distribution. It is important to note that an item is not allowed to appear twice in the same transaction and that items are assumed to be sorted by lexicographical order in a transaction.
Transaction id | Items |
t1 | {1, 3, 4} |
t2 | {2, 3, 5} |
t3 | {1, 2, 3, 5} |
t4 | {2, 5} |
t5 | {1, 2, 3, 5} |
What is the output of the PrePost / PrePost+ algorithms?
PrePost and PrePost+ are algorithms for discovering itemsets (group of items) occurring frequently in a transaction database (frequent itemsets). A frequent itemset is an itemset appearing in at least minsup transactions from the transaction database, where minsup is a parameter given by the user.
For example, if PrePost or PrePost+ are run on the previous transaction database with a minsup of 40 % (2 transactions), they produce the following result:
itemsets | support |
{1} | 3 |
{2} | 4 |
{3} | 4 |
{5} | 4 |
{1, 2} | 2 |
{1, 3} | 3 |
{1, 5} | 2 |
{2, 3} | 3 |
{2, 5} | 4 |
{3, 5} | 3 |
{1, 2, 3} | 2 |
{1, 2, 5} | 2 |
{1, 3, 5} | 2 |
{2, 3, 5} | 3 |
{1, 2, 3, 5} | 2 |
How should I interpret the results?
In the results, each itemset is annotated with its support. The support of an itemset is how many times the itemset appears in the transaction database. For example, the itemset {2, 3 5} has a support of 3 because it appears in transactions t2, t3 and t5. It is a frequent itemset because its support is higher or equal to the minsup parameter.Performance
There exists several algorithms for mining frequent itemsets. PrePost is claimed to be one of the best by their author. The PrePost+ algorithm by the same authors is supposed to be faster though (also offered in SPMF).
Input file format
The input file format used by PrePost is defined as follows. It is a text file. An item is represented by a positive integer. A transaction is a line in the text file. In each line (transaction), items are separated by a single space. It is assumed that all items within a same transaction (line) are sorted according to a total order (e.g. ascending order) and that no item can appear twice within the same line.
For example, for the previous example, the input file is defined as follows:
1 3 4
2 3 5
1 2 3 5
2 5
1 2 3 5
Note that it is also possible to use the ARFF format as an alternative to the default input format. The specification of the ARFF format can be found here. Most features of the ARFF format are supported except that (1) the character "=" is forbidden and (2) escape characters are not considered. Note that when the ARFF format is used, the performance of the data mining algorithms will be slightly less than if the native SPMF file format is used because a conversion of the input file will be automatically performed before launching the algorithm and the result will also have to be converted. This cost however should be small.
Output file format
The output file format is defined as follows. It is a text file, where each line represents a frequent itemset. On each line, the items of the itemset are first listed. Each item is represented by an integer and it is followed by a single space. After, all the items, the keyword "#SUP:" appears, which is followed by an integer indicating the support of the itemset, expressed as a number of transactions. For example, here is the output file for this example. The first line indicates the frequent itemset consisting of the item 1 and it indicates that this itemset has a support of 3 transactions.
1 #SUP: 3
2 #SUP: 4
3 #SUP: 4
5 #SUP: 4
1 2 #SUP: 2
1 3 #SUP: 3
1 5 #SUP: 2
2 3 #SUP: 3
2 5 #SUP: 4
3 5 #SUP: 3
1 2 3 #SUP: 2
1 2 5 #SUP: 2
1 3 5 #SUP: 2
2 3 5 #SUP: 3
1 2 3 5 #SUP: 2
Note that if the ARFF format is used as input instead of the default input format, the output format will be the same except that items will be represented by strings instead of integers.
Optional feature: giving names to items
Some users have requested the feature of given names to items instead of using numbers. This feature is offered in the user interface of SPMF and in the command line of SPMF. To use this feature, your file must include @CONVERTED_FROM_TEXT as first line and then several lines to define the names of items in your file. For example, consider the example database "contextPasquier99.txt". Here we have modified the file to give names to the items:
@CONVERTED_FROM_TEXT
@ITEM=1=apple
@ITEM=2=orange
@ITEM=3=tomato
@ITEM=4=milk
@ITEM=5=bread
1 3 4
2 3 5
1 2 3 5
2 5
1 2 3 5
In this file, the first line indicates, that it is a file where names are given to items. Then, the second line indicates that the item 1 is called "apple". The third line indicates that the item 2 is called "orange". Then the following lines define transactions in the SPMF format.
Then, if we apply the algorithm using this file using the user interface of SPMF or the command line, the output file contains several patterns, including the following ones:
orange tomato bread #SUP: 3
orange bread #SUP: 4
apple orange tomato bread #SUP: 2
Note that this feature could be also used from the source code of SPMF using the ResultConverter class. However, there is currently no example provided for using it from the source code.
Where can I get more information about the PrePost / PrePost+ algorithm?
Here is an article describing the PrePost algorithm:
Zhihong Deng, Zhonghui Wang, Jia-Jian Jiang: A new algorithm for fast mining frequent itemsets using N-lists. SCIENCE CHINA Information Sciences 55(9): 2008-2030 (2012)
And another describing PrePost+:
Zhihong Deng, Sheng-Dong Lv: PrePost + : An efficient N-lists-based algorithm for mining frequent itemsets via Children–Parent Equivalence pruning. Expert Systems and Applications, 42: 5424- 5432 (2015)
Also, for a good overview of frequent itemset mining algorithms, you may read this survey paper.