# Mining Rare Correlated Itemsets Using the CORI Algorithm (SPMF documentation)

This example explains how to run the CORI algorithm using the SPMF open-source data mining library.

## How to run this example?

• If you are using the graphical interface, (1) choose the "CORI" algorithm, (2) select the input file "contextPasquier99.txt", (3) set the output file name (e.g. "output.txt") (4) set maxsup = 0.8 % and minbond = 20 % 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 CORI contextPasquier99.txt output.txt 80% 20% 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 "MainTestCORI_saveToFile.java" in the package ca.pfv.SPMF.tests.

## What is CORI?

CORI is an algorithm for mining rare correlated itemsets.

It is an extension of the ECLAT algorithm. It uses two measures called the support and the bond to evaluate if an itemset is interesting and should be output.

## What is the input of the CORI algorithm?

The input 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 CORI algorithm?

CORI is an algorithm for discovering itemsets (group of items) that are rare and correlated in a transaction database (rare correlated itemsets). A rare itemset is an itemset such that its support is no less than a minsup threshold set by the user. The support of an itemset is the number of transactions containing the itemset.

A correlated itemset is an itemset such that its bond is no less than a minbond threshold set by the user. The bond of an itemsets is the number of transactions containing the itemset divided by the number of transactions containing any of its items. The bond is a value in the [0,1] interval. A high value means a highly correlated itemset. Note that single items have by default a bond of 1.

For example, if CORI is run on the previous transaction database with a minsup = 80% and minbond = 20%, CORI outputs the following rare correlated itemsets:

 itemsets bond support {1} 1 3 {4} 1 1 {1, 4} 0.33 1 {3, 4} 0.25 1 {1, 3, 4} 0.25 1 {1, 2} 0.4 2 {1, 2, 3} 0.4 2 {1, 2, 5} 0.4 2 {1, 2, 3, 5} 0.4 2 {1, 3} 0.75 3 {1, 3, 5} 0.4 2 {1, 5} 0.4 2 {2, 3} 0.6 3 {2, 3, 5} 0.6 3 {3, 5} 0.6 3

## Input file format

The input file format used by CORI 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 of CORI is defined as follows. It is a text file, where each line represents a correlated rare 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. After, all the items, the keyword "#BOND:" appears, which is followed by a double value indicating the bond of the itemset. For example, we show below the output file for this example.

1 #SUP: 3 #BOND: 1.0
4 #SUP: 1 #BOND: 1.0
4 1 #SUP: 1 #BOND: 0.3333333333333333
4 3 #SUP: 1 #BOND: 0.25
4 1 3 #SUP: 1 #BOND: 0.25
1 2 #SUP: 2 #BOND: 0.4
1 2 3 #SUP: 2 #BOND: 0.4
1 2 5 #SUP: 2 #BOND: 0.4
1 2 3 5 #SUP: 2 #BOND: 0.4
1 3 #SUP: 3 #BOND: 0.75
1 3 5 #SUP: 2 #BOND: 0.4
1 5 #SUP: 2 #BOND: 0.4
2 3 #SUP: 3 #BOND: 0.6
2 3 5 #SUP: 3 #BOND: 0.6
3 5 #SUP: 3 #BOND: 0.6

The output file here consists of 15 lines. Consider the last line. It indicates that the itemset {3, 5} is a rare correlated itemset having a support and bond of respectively 3 and 0.6.

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 parameter(s)

This implementation allows to specify additional optional parameter(s) :

• "show transaction ids?" (true/false) This parameter allows to specify that transaction ids of transactions containing a pattern should be output for each pattern found. For example, if the parameter is set to true, each pattern in the output file will be followed by the keyword #TID followed by a list of transaction ids (integers separated by space). For example, a line terminated by "#TID: 0 2" means that the pattern on this line appears in the first and the third transactions of the transaction database (transactions with ids 0 and 2).
• Max pattern length (integer) : This parameter allows to set a maximum number of items to appear on the an itemset. By default, this parameter is equal to the infinity if it is not set.

These parameter(s) are available in the GUI of SPMF and also in the example(s) "MainTestCORI_SaveToFile .java" provided in the source code of SPMF.

The parameter(s) can be also used in the command line with the Jar file. If you want to use these optional parameter(s) in the command line, it can be done as follows. Consider this example:

java -jar spmf.jar run CORI contextPasquier99.txt output.txt 80% 20% true 2
This command means to apply the algorithm on the file "contextPasquier99.txt" and output the results to "output.txt". Moreover, it specifies that the user wants to find patterns for maxsup = 80%, minbond = 20%, and that transaction ids should be output for each pattern found. Moreover, only frequent itemsets having no more than 2 items should be output.

## 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
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 #SUP: 3 #BOND: 0.6
orange tomato bread #SUP: 3 #BOND: 0.6
tomato bread #SUP: 3 #BOND: 0.6

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.

## Performance

CORI is the only algorithm for mining correlated rare itemsets offered in SPMF. The implementation is well optimized. It is a quite simple extension of the ECLAT algorithm.