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

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

How to run this example?

What is OCEAN?

OCEAN (Shen et al., PAKDD 2016) 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?

OCEAN 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 OCEAN 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 OCEAN 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 OCEAN 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 OCEAN 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 OCEAN algorithm was the first algorithm designed for this problem. It stores each item in a utility-list and prunes the search space using an upper bound on the utility occupancy that can be obtained by any extension of the current itemset. The bound is computed from the transactions with the largest potential occupancy among those needed to reach the minimum support. SPMF also offers two more recent algorithms for the same problem, HUOPM and HUOMIL, which can be compared with OCEAN on the same input files.

Implementation details

The version offered in SPMF follows the OCEAN 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 OCEAN algorithm?

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

Shen et al. (2016). OCEAN: Fast Discovery of High Utility Occupancy Itemsets. Proc. 20th Pacific-Asia Conference on Knowledge Discovery and Data Mining (PAKDD 2016), Springer, LNCS, pp. 354-365. DOI: 10.1007/978-3-319-31753-3_29

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