Mining Maximal High Utility Occupancy Itemsets in a Transaction Database using the MaxCloFHUOIM Algorithm (SPMF documentation)

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

How to run this example?

What is MaxCloFHUOIM?

MaxCloFHUOIM (Duong et al., 2024) is an algorithm for discovering high utility-occupancy itemsets in a transaction database containing utility information.

Traditional high utility itemset mining algorithms (such as FHM) find the itemsets that generate a large total profit. However, an itemset may have a large total utility simply because it is very frequent, even if it only represents a small portion of what customers spend in the transactions where it appears. High utility-occupancy itemset mining addresses this limitation. It looks for itemsets that are frequent and that occupy a large share of the total utility of the transactions that contain them. For example, in a retail store, such an itemset could be a group of products that customers buy together and that account for most of the money spent in the baskets where they appear.

While high utility-occupancy itemset mining can be useful, it can still find too many patterns. Hence, it was proposed to find only subsets of them that are representative, called the maximal high utility-occupancy itemsets. This is what this algorithm extracts from data. Note that this algorithm can also optionally output another subsets called the closed high utility-occupancy itemsets.

What is the input?

MaxCloFHUOIM takes as input a transaction database with utility information and two parameters:

Let's consider the following database consisting of 10 transactions (t1,t2...t10) and 5 items (1, 2, 3, 4, 5). This database is provided in the text file "DB_UtilityOccupancy.txt" in the package ca.pfv.spmf.algorithms.frequentpatterns.huo of the SPMF distribution. It is the example database used in the HUOPM paper, where each item utility was obtained by multiplying a purchase quantity by a unit profit (item 1 = 7 $, item 2 = 2 $, item 3 = 11 $, item 4 = 1 $, item 5 = 9 $).


Items Transaction utility Item utilities for this transaction
t1 1 3 4 65 14 44 7
t2 2 3 37 4 33
t3 1 2 3 4 38 21 4 11 2
t4 2 4 11 8 3
t5 1 2 3 4 5 49 7 6 22 5 9
t6 3 5 58 22 36
t7 3 4 23 22 1
t8 1 2 4 5 61 21 2 2 36
t9 1 3 4 59 14 44 1
t10 3 5 42 33 9

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.

For example, the first customer, "t1", bought items 1, 3 and 4. The profit generated by each item is respectively 14 $, 44 $ and 7 $. The total profit of this transaction is 14 + 44 + 7 = 65 $.

What is the output?

The output of MaxCloFHUOIM is the set of maximal high utility-occupancy itemsets that are frequent (their support is no less than min_support) and whose mean utility occupancy is no less than min_utility_occupancy. To explain these notions, some definitions are needed. An itemset is an unordered set of distinct items. The utility of an itemset in a transaction is the sum of the utilities of its items in that transaction. The support of an itemset is the number of transactions that contain it.

The utility occupancy of an itemset X in a transaction T is the utility of X in T divided by the total utility of T:

uo(X, T) = u(X, T) / tu(T)

For example, the utility occupancy of {3 5} in transaction t5 is (22 + 9) / 49 = 0.632, and in transaction t6 it is (22 + 36) / 58 = 1.0. The utility occupancy of an itemset X in the database is the mean of its utility occupancy over the transactions that contain it. The itemset {3 5} appears in t5, t6 and t10, where its utility occupancies are 0.632, 1.0 and 1.0. The utility occupancy of {3 5} in the database is thus (0.632 + 1.0 + 1.0) / 3 = 0.8776. The utility occupancy is always a value between 0 and 1. A value close to 1 means that the itemset accounts for most of the utility of the transactions where it appears.

A high utility-occupancy itemset is a frequent itemset whose mean utility occupancy is no less than min_utility_occupancy.
A closed high utility-occupancy itemset is a high utility-occupancy itemset that is not a subset of another itemset having the same support.
A maximal high utility-occupancy itemset is a high utility-occupancy itemset that is not a subset of another itemset that is a high utility-occupancy itemset.
For example, if we run MaxCloFHUOIM with a minimum support of 0.3 (30%) and a minimum utility occupancy of 0.3, we obtain 4 maximal high utility-occupancy itemsets:

itemsets support utility occupancy
{1 2 4} 30 % (3 transactions) 0.4959
{2 3} 30 % (3 transactions) 0.6554
{3 5} 30 % (3 transactions) 0.8776
{1 3 4} 40 % (4 transactions) 0.8972

For example, the itemset {2 3} appears in 3 transactions (t2, t3, and t5 ). Its mean utility occupancy is 0.4959.

If the database is a transaction database from a store, we could interpret these results as all the groups of items that are bought together by at least 30% of the customers, and that represent on average at least 30% of the amount spent by the customers who bought them.

Input file format

The input file format of MaxCloFHUOIM is the standard SPMF format for transaction databases with utility values. It is a text file.The first two lines are metadata indicating the type of file and the source of the file. Then, the following lines represents transactions, where each line is a transaction composed of three sections, defined as follows.

The transaction utility on each line is used as the denominator when calculating utility occupancy, so it should equal the sum of the item utilities on that line. 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/
1 3 4:65:14 44 7
2 3:37:4 33
1 2 3 4:38:21 4 11 2
2 4:11:8 3
1 2 3 4 5:49:7 6 22 5 9
3 5:58:22 36
3 4:23:22 1
1 2 4 5:61:21 2 2 36
1 3 4:59:14 44 1
3 5:42:33 9

Consider the first transaction. It means that the transaction {1, 3, 4} has a total utility of 65 and that items 1, 3 and 4 respectively have a utility of 14, 44 and 7 in this transaction. The following lines follow the same format.

Output file format

The output file format of MaxCloFHUOIM is defined as follows. It is a text file, where each line represents a high utility-occupancy itemset. On each line, the items of the itemset are first listed in ascending order, each separated by a single space. After the items, the keyword " #SUP: " appears and is followed by the support of the itemset (a number of transactions). Then, the keyword " #UO: " appears and is followed by the mean utility occupancy of the itemset (a number between 0 and 1). For example, we show below the output file for this example.

@FILETYPE="Maximal high utility-occupancy itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
3 5 #SUP: 3 #UO: 0.8775510204081632
1 2 4 #SUP: 3 #UO: 0.4959031067129181
1 3 4 #SUP: 4 #UO: 0.8971535982814178
2 3 #SUP: 3 #UO: 0.6553884711779449

For example, the first line indicates that the itemset {3, 5} appears in 3 transactions and has a mean utility occupancy of about 0.8776. The following lines follow the same format. Note that the itemsets are not written in any particular order of size or support, because they are output in the order in which the depth-first search discovers them.

Optional parameter

This implementation can optionally also 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" and run the algorithm. Then, the closed itemsets will be saved in the file "closed.txt" 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-occupancy itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
5 #SUP: 4 #UO: 0.4022031933180282
3 5 #SUP: 3 #UO: 0.8775510204081632
1 2 4 #SUP: 3 #UO: 0.4959031067129181
1 4 #SUP: 5 #UO: 0.3609049017237591
1 3 4 #SUP: 4 #UO: 0.8971535982814178
2 4 #SUP: 4 #UO: 0.361989575813069
2 3 #SUP: 3 #UO: 0.6553884711779449
3 4 #SUP: 5 #UO: 0.6880905840686649
3 #SUP: 8 #UO: 0.646822165799868

 

To use this feature from the command line write the command as follows: java -jar spmf.jar run MaxCloFHUOIM DB_utility.txt output.txt 0.3 0.3 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 MaxCloFHUOIM algorithm?

This is the reference of the article describing the MaxCloFHUOIM algorithm:

Duong, H., Pham, H., Truong, T., & Fournier-Viger, P. (2024). Efficient algorithms to mine concise representations of frequent high utility occupancy patterns. Applied Intelligence, 54(5), 4012-4042.

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