Mining Erasable Itemsets from a Product Database with the VME algorithm (SPMF documentation)
This example explains how to run the VME algorithm using the SPMF open-source data mining library.
How to run this example?
- If you are using the graphical interface, (1) choose the "VME" algorithm, (2) select the input file "contextVME.txt", (3) set the output file name (e.g. "output.txt"), (4) set the threshold to 15%, 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 VME contextVME.txt output.txt 15% in a folder containing spmf.jar and the example input file contextVME.txt. - If you are using the source code version of SPMF, launch the file "MainTestVME.java" in the package ca.pfv.spmf.algorithms.frequentpatterns.vme.
What is the VME algorithm?
VME (Deng & Xu, 2010) is an algorithm for mining erasable itemsets from a product database with profit information. It is based on the AprioriTID algorithm and uses a vertical tid-list representation to efficiently compute the loss of profit of candidate itemsets without rescanning the database at each level.
What is the input?
VME takes as input a product database and a threshold (a value between 0 and 100%). A product is defined as a set of items that are used to assemble the product. Moreover, each product is annotated with a profit (a positive integer) that indicates how much money this product generates for the company. For example, let's consider the following product database, consisting of 6 products and 7 items (this example is taken from the article of Deng & Xu, 2010). Each product is annotated with profit information. For example, the first line indicates that product 1 generates a total profit of 50 $ for the company and that its assembly requires parts 2, 3, 4 and 6. This product database is provided in the file "contextVME.txt" of the SPMF distribution:
| profit | items | |
| product 1 | 50$ | {2, 3, 4, 6} |
| product 2 | 20$ | {2, 5, 7} |
| product 3 | 50$ | {1, 2, 3, 5} |
| product 4 | 800$ | {1, 2, 4} |
| product 5 | 30$ | {6, 7} |
| product 6 | 50$ | {3, 4} |
What is the output?
The output is the set of erasable itemsets whose loss of profit is lower than or equal to the user-specified threshold. The idea is to discover sets of items that the company could stop purchasing and that would minimize the amount of profit lost by being unable to build certain products.
To explain what an erasable itemset is more formally, it is necessary to review some definitions. An itemset is an unordered set of distinct items. The loss of profit generated by an itemset is defined as the sum of the product profits for all products containing at least one item from this itemset. For example, the loss of profit of itemset {5, 6} is the sum of the profits of products containing 5 and/or 6: 50 $ + 20 $ + 50 $ + 30 $ = 150 $. The loss of profit can also be expressed as a percentage of the total profit of the database. In this database the total profit is 50 + 20 + 50 + 800 + 30 + 50 = 1000 $. Therefore, the loss of profit caused by itemset {5, 6} can be expressed as 15% (150 / 1000 × 100).
By running VME with a threshold of 15%, we obtain 8 erasable itemsets (having a profit loss less than or equal to 15% × 1000 $ = 150 $):
| erasable itemsets | loss of profit |
| {3} | 150.0 |
| {5} | 70.0 |
| {6} | 80.0 |
| {7} | 50.0 |
| {5, 6} | 150.0 |
| {5, 7} | 100.0 |
| {6, 7} | 100.0 |
| {5, 6, 7} | 150.0 |
This means that if the items from one of those erasable itemsets are no longer purchased, the loss of profit will be lower than or equal to 15%.
Input file format
The input file format of VME is defined as follows. It is a text file. Each line represents a transaction (product). Each line is composed of two sections:
- First, the profit of the transaction is indicated by an integer number, followed by a single space.
- Second, the items in the transaction are listed. An item is represented by a positive integer. Each item is separated from the following item by a space. It is assumed that items are sorted according to a total order and that no item can appear twice in the same transaction.
For example, the input file for the previous example is defined as follows:
50 2 3 4 6
20 2 5 7
50 1 2 3 5
800 1 2 4
30 6 7
50 3 4
Consider the first line. It means that the transaction {2, 3, 4, 6} has a profit of 50 and contains the items 2, 3, 4 and 6. The following lines follow the same format.
Output file format
The output file format of VME is defined as follows. It is a text file where each line represents an erasable 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 "#LOSS:" appears, followed by a numeric value indicating the loss of profit for that itemset.
3 #LOSS: 150.0
5 #LOSS: 70.0
6 #LOSS: 80.0
7 #LOSS: 50.0
5 6 #LOSS: 150.0
5 7 #LOSS: 100.0
6 7 #LOSS: 100.0
5 6 7 #LOSS: 150.0
For example, the first line indicates that the itemset {3} would generate a loss of profit of 150.0. The following lines follow the same format.
Performance
The VME algorithm is Apriori-based and uses a vertical tid-list representation to avoid rescanning the database at every level. It is one of the earliest algorithms proposed for this problem. For larger databases or higher numbers of erasable itemsets, more recent algorithms such as MEI and META may offer better performance.
Where can I get more information about the VME algorithm?
Here is the article describing the VME algorithm:
Z. Deng, X. Xu: An Efficient Algorithm for Mining Erasable Itemsets. ADMA (1) 2010: 214–225.
For a good overview of frequent itemset mining algorithms, you may read this survey paper.