Mining Association Rules from Rare Itemsets found by the RP-Growth Algorithm (SPMF documentation)

This example explains how to run the RP-Growth algorithm to extract association rules using the SPMF open-source data mining library.

How to run this example?

What is RPGrowth?

RPGrowth is an adaptation of the FPGrowth algorithm for discovering rare itemsets in a transaction database. FPGrowth was proposed by Han et al. (2000) and the adaptation of the FPGrowth to find rare itemsets was proposed by Sidney Tsang, Yun Sing Koh, and Gillian Dobbie (2011). Being modified from the FPGrowth algorithm, it retains the speed, memory efficiency, and the usage of the FP-Tree.

This example describes how to extract rare itemsets with RPGrowth and derive association rules from them. There is another example in the documentation that describe only the first step (extracting rare itemsets).

What is the input of the RPGrowth algorithm for association rule mining?

The input of RPGrowth is a transaction database (aka binary context) and three thresholds:


Transaction id

Items

t1

{1, 2, 4}

t2

{1, 3}

t3

{1, 2, 3, 5}

t4

{2, 3, 5}

t5

{1, 2, 3, 5}

What is the output of the RPGrowth algorithm?

RPGrowth is an algorithm for discovering rare itemsets (group of items) occurring infrequently in a transaction database (rare itemsets). A rare itemset is an itemset appearing within the minraresup and minsup range (e.g. minraresup is set to 10% and minsup is set to 60%), where both minraresup and minsup are parameters defined by the user. NOTE: RPGrowth has the requirement that any “rare” itemset of size 2 or greater contain at least one item (itemset of size 1) that was considered “rare”. For example, if RPGrowth is run on the previous transaction database with a minsup of 50% (4 transactions) and minraresup 10% (1 transaction), RPGrowth first extracts the following rare itemsets:


Itemsets

Support

{4}

1

{1, 4}

1

{2, 4}

1

{1, 2, 4}

1

 

Then, association rules are derived from these rare itemsets. To explain what is the result, it is necessary to explain a few definitions.

An association rule X==>Y is a relationship between two itemsets (sets of items) X and Y such that the intersection of X and Y is empty. The support of a rule is the number of transactions that contains X∪Y. The confidence of a rule is the number of transactions that contains X∪Y divided by the number of transactions that contain X. The output of association rule mining algorithm is a set of association rules respecting the user-specified minconf threshold. This means that all rules are output that have a confidence that is no less than 60% in this example. For example, by deriving association rules from the rare itemsets found by RPGrowth we obtains 4 associations rules:


Itemsets 		Support

Confidence

4 ==> 1

1

 100%

4 ==> 3

1

 100%

3 4 ==> 1

1

 100%

1 4 ==> 3

1

 100%
4 ==> 1 3 1 100%

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 {1, 2, 4} has a support of 1 because it appears in only t1. It is a rare itemset because it falls within the user determined range of what is considered “rare” (and meets previously mentioned constraints).

Input file format:

The input file format used by the RPGrowth 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 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 2 4
1 3
1 2 3 5
2 3 5
1 2 3 5

Output file format:

The output file format is defined as follows. It is a text file, where each line represents an association rule. On each line, the items of the rule antecedent are first listed. Each item is represented by an integer, followed by a single space. After, that the keyword "==>" appears followed by a space. Then, the items of the rule consequent are listed. Each item is represented by an integer, followed by a single space. Then, the keyword " #SUP: " appears followed by the support of the rule represented by an integer. Then, the keyword " #CONF: " appears followed by the confidence of the rule represented by a double value (a value between 0 and 1, inclusively). For example, here is a few lines from the output file for this example:

4 ==> 1 #SUP: 1 #CONF: 1.0
4 ==> 3 #SUP: 1 #CONF: 1.0
3 4 ==> 1 #SUP: 1 #CONF: 1.0
1 4 ==> 3 #SUP: 1 #CONF: 1.0
4 ==> 1 3 #SUP: 1 #CONF: 1.0

For example, the first line indicates that the association rule {4} --> {1,3} has a support of 1 transaction and a confidence of 100 %. The other lines follow the same format.

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: constraints on the size of association rules

Sometimes, there may be just too many association rules, and rules containing many items may not be interesting. Thus, it is also possible to specify two optional parameters in the user interface of SPMF:

If you are using the command line interface of SPMF, it is also possible to use these optional parameters by adding them at the end of the command. For example:
java –jar spmf.jar run RPGrowth_association_rules contextRP.txt output.txt 60% 10% 60% 2 3
means to run the above example with a maximum antecedent length of 2 items and a maximum consequent length of 3 items.

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 "contextRP.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 four sequences 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:

milk ==> apple #SUP: 1 #CONF: 1.0
milk ==> 3 #SUP: 1 #CONF: 1.0
tomato milk ==> apple #SUP: 1 #CONF: 1.0
apple milk ==> tomato #SUP: 1 #CONF: 1.0
milk ==> apple tomato #SUP: 1 #CONF: 1.0

Performance

RPGrowth is the only algorithm for all rare itemsets that branch off initial singleton rare items offered in SPMF. Being an extension of FPGrowth; RPGrowth retains the speed, memory efficiency, and the usage of the FP-Tree.

Where can I get more information about the RPGrowth algorithm?

This is the journal article describing the original FPGrowth algorithm:

Jiawei Han, Jian Pei, Yiwen Yin, Runying Mao: Mining Frequent Patterns without Candidate Generation: A Frequent-Pattern Tree Approach. Data Min. Knowl. Discov. 8(1): 53-87 (2004)

This is the journal article describing the modification of the FPGrowth algorithm and FP-Tree to handle rare itemsets rather than frequent itemsets:

Sidney Tsang, Yun Sing Koh, Gillian Dobbie, RP-Tree: Rare Pattern Tree Mining, International Conference of Data Warehousing and Knowledge Discovery, 277-288 (2011)
https://link.springer.com/chapter/10.1007/978-3-642-23544-3_21

<< Return to table of contents of SPMF documentation

Copyright © 2008-2026 Philippe Fournier-Viger. All rights reserved.