Mining Maximal High-Utility Itemsets from a transaction database with utility information using the MaxC-HUIM Algorithm (SPMF documentation)

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

How to run this example?

What is MaxC-HUIM?

MaxC-HUIM (Duong et al., 2022) is an algorithm for discovering maximal high-utility itemsets in a transaction database containing utility information.

There has been many work on the topic of high-utility itemset mining. A limitation of many high-utility itemset mining algorithms is that they generate too much itemsets as output. The MaxC-HUIM algorithm was designed to discover only the high-utility itemsets that are maximal. A maximal high utility itemset is an itemset that is not included in any other high utility itemsets.

There are a few algorithms for discovering maximal itemsets in SPMF. This one has the particularity that it can also find the closed itemsets at the same time and save them to a second output file but this feature is optional.

What is the input?

MaxC-HUIM takes as input a transaction database with utility information and a minimum utility threshold min_utility (a positive integer). Let's consider the following database consisting of 5 transactions (t1,t2...t5) and 7 items (1, 2, 3, 4, 5, 6, 7). This database is provided in the text file "DB_utility.txt" in the package ca.pfv.spmf.tests of the SPMF distribution.


Items Transaction utility Item utilities for this transaction
t1 3 5 1 2 4 6 30 1 3 5 10 6 5
t2 3 5 2 4 20 3 3 8 6
t3 3 1 4 8 1 5 2
t4 3 5 1 7 27 6 6 10 5
t5 3 5 2 7 11 2 3 4 2

Each line of the database is:

Note that the value in the second column for each line is the sum of the values in the third column.

What are real-life examples of such a database? There are several applications in real life. One application is a customer transaction database. Imagine that each transaction represents the items purchased by a customer. The first customer named "t1" bought items 3, 5, 1, 2, 4 and 6. The amount of money spent for each item is respectively 1 $, 3 $, 5 $, 10 $, 6 $ and 5 $. The total amount of money spent in this transaction is 1 + 3 + 5 + 10 + 6 + 5 = 30 $.

What is the output?

The output of MaxC-HUIM is the set of maximal high utility itemsets having a utility no less than a min_utility threshold (a positive integer) set by the user. To explain what is a maximal high utility itemset, it is necessary to review some definitions.

An itemset is an unordered set of distinct items. The utility of an itemset in a transaction is the sum of the utility of its items in the transaction. For example, the utility of the itemset {1 4} in transaction t1 is 5 + 6 = 11 and the utility of {1 4} in transaction t3 is 5 + 2 = 7. The utility of an itemset in a database is the sum of its utility in all transactions where it appears. For example, the utility of {1 4} in the database is the utility of {1 4} in t1 plus the utility of {1 4} in t3, for a total of 11 + 7 = 18. A high utility itemset is an itemset such that its utility is no less than min_utility.

A maximal high utility itemset (CHUI) is a high-utility itemset that not included in any other high utility itemset.

For example, if we run MaxC-HUIM with a minimum utility of 25 we obtain 2 maximal high-utility itemsets:

itemsets utility
{1, 2, 3, 4, 5, 6} 30
{1, 3, 5, 7} 27

If the database is a transaction database from a store, we could interpret these results as all the largest groups of items bought together that generated a profit of 25 $ or more.

Input file format

The input file format of MaxC-HUIM is defined as follows. It is a text file. Each lines represents a transaction. Each line is composed of three sections, as follows.

For example, for the previous example, the input file is defined as follows:

@FILETYPE="Transaction database with utility values"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
3 5 1 2 4 6:30:1 3 5 10 6 5
3 5 2 4:20:3 3 8 6
3 1 4:8:1 5 2
3 5 1 7:27:6 6 10 5
3 5 2 7:11:2 3 4 2

The first two lines are optional metadata. The first line indicate the type of file and the second line describes the source of the data. Then it is the data section. Consider the first line of data. It means that the transaction {3, 5, 1, 2, 4, 6} has a total utility of 30 and that items 3, 5, 1, 2, 4 and 6 respectively have a utility of 1, 3, 5, 10, 6 and 5 in this transaction. The following lines follow the same format.

Output file format

The output file format of MaxC-HUIM is defined as follows. It is a text file. The first two lines are metadata indicating the type of patterns in this file and the source of the data. Then the following lines provide the list of patterns, where each line represents a maximal high utility itemset. On each line, the items of the itemset are first listed. Each item is represented by an integer, followed by a single space. After, all the items, the keyword "#SUP:" appears and is followed by the support of the itemset. The support of an itemset is how many times the itemset appeared in the database. Then, the keyword #UTIL: " appears and is followed by the utility of the itemset. For example, we show below the output file for this example.

@FILETYPE="Maximal high-utility itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
6 4 2 1 5 3 #SUP: 1 #UTIL: 30
7 5 3 1 #SUP: 1 #UTIL: 27

For example, the second line indicates that the itemset {1, 3, 5, 7} has a support of 1 transaction and a utility of 27$. The other lines follows the same format.

Optional parameter

This implementation of MaxC-HUIM also allows to output closed high utility itemsets. A closed high utility itemsets is a high utility itemset that has no itemset having the same support (appearing the same number of times in the dataset). The maximal itemsets are a subset of closed itemsets.

To use this feature in the GUI of SPMF, set the second optional parameter "Closed itemset file" to "closed.txt" (or any other name) and run the algorithm. Then, the closed itemsets will be saved in a file with that name in the same directory as the output file containing the maximal itemsets. The file of closed itemsets for this example looks like this and has the same format as for maximal itemsets except for the first line of metadata:

@FILETYPE="Closed high-utility itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
1 2 3 4 5 6 #SUP: 1 #UTIL: 30
1 3 5 7 #SUP: 1 #UTIL: 27
2 3 4 5 #SUP: 2 #UTIL: 40
2 3 5 #SUP: 3 #UTIL: 37
1 3 5 #SUP: 2 #UTIL: 31
1 3 #SUP: 3 #UTIL: 28
3 5 #SUP: 4 #UTIL: 27

To use this feature from the command line write the command as follows: java -jar spmf.jar run MaxC-HUIM DB_utility.txt output.txt 25 closed.txt

Implementation details

This is not the original implementation. This implementation has been made for SPMF by reading the paper and thus it may slightly differ from the original implementation due to ambiguities and design decisions.

Where can I get more information about the MaxC-HUIM algorithm?

This is the reference of the article describing the MaxC-HUIM algorithm:

Duong, H., Hoang, T., Tran, T., Truong, T., Le, B., & Fournier-Viger, P. (2022). Efficient algorithms for mining closed and maximal high utility itemsets. Knowledge-Based Systems, 257, 109921.

Besides, for a general overview of high utility itemset mining, you may read this survey paper.