Mining High Utility Occupancy Itemsets in a Transaction Database using the HUOPM Algorithm (SPMF documentation)
This example explains how to run the HUOPM algorithm using the SPMF open-source data mining library.
How to run this example?
- If you are using the graphical interface, (1) choose the "HUOPM" algorithm, (2) select the input file "DB_UtilityOccupancy.txt", (3) set the output file name (e.g. "output.txt"), (4) set the minimum support to 0.3 (30%), (5) set the minimum utility occupancy to 0.3 and (6) click "Run algorithm".
- If you want to execute this example from the command line,
then execute this command:
java -jar spmf.jar run HUOPM DB_UtilityOccupancy.txt output.txt 0.3 0.3 in a folder containing spmf.jar and the example input file DB_UtilityOccupancy.txt. - If you are using the source code version of SPMF, launch the file "MainTestHUOPM.java" in the package ca.pfv.spmf.test
What is HUOPM?
HUOPM (Gan et al., 2019) 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.
What is the input?
HUOPM takes as input a transaction database with utility information and two parameters:
- min_support, a relative minimum support threshold, which is a number in the interval (0, 1]. For example, 0.3 means that an itemset must appear in at least 30% of the transactions. The threshold is inclusive. In this example, 10 transactions and 0.3 give an absolute minimum support of 3 transactions.
- min_utility_occupancy, a minimum mean utility occupancy threshold, which is a number in the interval (0, 1]. The threshold is inclusive.
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:
- a set of items (the first column of the table),
- the sum of the utilities (e.g. profit) of these items in this transaction (the second column of the table),
- the utility of each item for this transaction (e.g. profit generated by this item for this transaction)(the third column of the table).
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 HUOPM is the set of 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. For example, if we run HUOPM with a minimum support of 0.3 (30%) and a minimum utility occupancy of 0.3, we obtain 11 high utility-occupancy itemsets:
| itemsets | support | utility occupancy |
| {1 2} | 30 % (3 transactions) | 0.4334 |
| {1 2 4} | 30 % (3 transactions) | 0.4959 |
| {2 4} | 40 % (4 transactions) | 0.3620 |
| {2 3} | 30 % (3 transactions) | 0.6554 |
| {5} | 40 % (4 transactions) | 0.4022 |
| {3 5} | 30 % (3 transactions) | 0.8776 |
| {1 4} | 50 % (5 transactions) | 0.3609 |
| {1 3 4} | 40 % (4 transactions) | 0.8972 |
| {1 3} | 40 % (4 transactions) | 0.8273 |
| {3 4} | 50 % (5 transactions) | 0.6881 |
| {3} | 80 % (8 transactions) | 0.6468 |
Some itemsets are not in the output, although they are frequent. For example, the itemset {2} appears in 5 transactions (t2, t3, t4, t5 and t8), but its utility occupancies in these transactions are 0.108, 0.105, 0.727, 0.122 and 0.033. Its mean utility occupancy is therefore only 0.219, which is less than 0.3. Similarly, the itemset {1} is frequent (5 transactions) but has a mean utility occupancy of 0.298, just below the threshold.
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 HUOPM 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.
- First, the items contained in the transaction are listed. An item is represented by a positive integer. Each item is separated from the next item by a single space. No item can appear twice within the same transaction.
- Second, the symbol ":" appears and is followed by the transaction utility (a positive integer).
- Third, the symbol ":" appears and is followed by the utility of each item in this transaction (a non-negative integer), separated by single spaces.
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 HUOPM 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="High utility-occupancy itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
1 2 #SUP: 3 #UO: 0.4334166798729846
1 2 4 #SUP: 3 #UO: 0.4959031067129181
2 4 #SUP: 4 #UO: 0.361989575813069
2 3 #SUP: 3 #UO: 0.6553884711779449
5 #SUP: 4 #UO: 0.4022031933180282
3 5 #SUP: 3 #UO: 0.8775510204081632
1 4 #SUP: 5 #UO: 0.36090490172375905
1 3 4 #SUP: 4 #UO: 0.8971535982814178
1 3 #SUP: 4 #UO: 0.8273251344042729
3 4 #SUP: 5 #UO: 0.6880905840686649
3 #SUP: 8 #UO: 0.646822165799868
For example, the sixth 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.
Performance
The HUOPM algorithm is a recent algorithm for this problem. SPMF also offers other algorithms for the same problem, HUOPM and OCEAN, which can be compared with HUOMIL on the same input files.
Implementation details
The version offered in SPMF follows the HUOPM paper and tries to be as faithful as possible to the paper. But there may be some differences due to implementation decisions.
Where can I get more information about the HUOPM algorithm?
This is the reference of the article describing the HUOPM algorithm:
Gan, W., Lin, J. C. W., Fournier-Viger, P., Chao, H. C., & Yu, P. S. (2019). HUOPM: High-utility occupancy pattern mining. IEEE transactions on cybernetics, 50(3), 1195-1208.
Besides, for a general overview of high utility itemset mining, you may read this survey paper.