Mining Frequent Maximal or Closed Itemsets using the MISAMiner Algorithm (SPMF documentation)

This example explains how to run the MISAMiner algorithm using the SPMF open-source data mining library. to mine frequent maximal itemsets (MFIs) or frequent closed itemsets (CFIs) from a transaction database.

How to run this example?

Mining Frequent Maximal Itemsets (MFIs)

Mining Frequent Closed Itemsets (CFIs)

What is MISAMiner?

MISAMiner is an algorithm for discovering frequent maximal itemsets (MFIs) and frequent closed itemsets (CFIs) in a transaction database. It is built on a missing-set representation: instead of describing an itemset by the transactions that contain it (the classical tidset / vertical representation), MISAMiner records the transactions that do not contain it. Under this formulation the support of an itemset equals the total number of transactions minus the size of the union of its items' missing-sets, and both frequency testing and closure checking reduce to fast bitset union and subset operations.

For MFI mining, MISAMiner organises depth-first search around an anchor set derived from inclusion-minimal single-item missing-sets. Items whose missing-set is already covered by the current prefix are immediately absorbed into the prefix without branching, which often collapses many items into a single step. At a leaf, a global maximality test decides whether to output the prefix as an MFI.

For CFI mining, MISAMiner performs depth-first Close-by-One (CbO) enumeration in the closure space. The closure of a node with missing-set M is the set of all frequent items whose own missing-set is a subset of M, and the standard CbO canonicity rule ensures that each closed itemset is generated exactly once.

What is the input of MISAMiner?

The input is a transaction database (also called a binary context) and a threshold named minsup (a percentage between 0 and 100 %).

A transaction database is a set of transactions, where each transaction is a set of items. Consider the following example database. It contains 5 transactions (t1–t5) and 5 items (1–5). This database is provided as the file contextPasquier99.txt in the SPMF distribution. Items within a transaction are assumed to be distinct and listed in lexicographical order.

Transaction id Items
t1{1, 3, 4}
t2{2, 3, 5}
t3{1, 2, 3, 5}
t4{2, 5}
t5{1, 2, 3, 5}

What is the output of MISAMiner?

MISAMiner outputs either frequent maximal itemsets or frequent closed itemsets, depending on the mode chosen.

To understand these concepts, recall the following definitions.

An itemset is an unordered set of distinct items. The support of an itemset is the number of transactions that contain all items in the set. For example, the itemset {1, 3} has a support of 3 because it appears in transactions t1, t3, and t5.

A frequent itemset is an itemset whose support is at least minsup. A frequent closed itemset (CFI) is a frequent itemset that has no proper superset with the same support. A frequent maximal itemset (MFI) is a frequent itemset that has no proper superset that is itself frequent. Therefore:

Example output – MFI mode (minsup = 40 %, i.e. 2 transactions)

Frequent maximal itemset Support
{1, 2, 3, 5} 2

There is only one MFI. The itemset {1, 2, 3, 5} appears in transactions t3 and t5, giving it a support of 2. For instance, {2, 5} is frequent (support 4) but is not maximal because it is a subset of the frequent itemset {2, 3, 5}.

Example output – CFI mode (minsup = 40 %, i.e. 2 transactions)

Frequent closed itemset Support
{1, 2, 3, 5}2
{2, 3, 5}3
{1, 3}3
{2, 5}4
{3}4

Each closed itemset has no proper superset with an identical support count. Note that the CFI set is a superset of the MFI set: {1, 2, 3, 5} appears in both, while the remaining CFIs are not maximal because each is contained in a larger frequent itemset.

Input file format

The input file format used by MISAMiner is a plain text file in which each line represents one transaction. Items are positive integers separated by single spaces. Items within a line are assumed to be sorted in ascending order and to appear at most once per line.

@FILETYPE="Simple transaction database"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
1 3 4
2 3 5
1 2 3 5
2 5
1 2 3 5

The first two lines are optional metadata. The first line identifies the file type and the second identifies the data source. The remaining lines are the transactions.

It is also possible to use the ARFF format as an alternative input format. The ARFF specification can be found here. Most ARFF features are supported except that (1) the character "=" is forbidden and (2) escape characters are not interpreted. When ARFF is used, a format conversion is performed automatically before and after the algorithm runs, which adds a small overhead.

Output file format

The output file is a plain text file. The first two lines are optional metadata. Each subsequent line describes one frequent maximal or closed itemset. On each line, the items of the itemset are listed first (integers separated by spaces), followed by the keyword #SUP: and an integer giving the support of the itemset as a transaction count.

Example output file for MFI mode:

@FILETYPE="Frequent maximal itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
1 2 3 5 #SUP: 2

Example output file for CFI mode:

@FILETYPE="Frequent closed itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
2 5 #SUP: 4
3 #SUP: 4
1 3 #SUP: 3
2 3 5 #SUP: 3
1 2 3 5 #SUP: 2

If the ARFF format is used as input, items in the output will be represented by strings instead of integers.

Optional feature: giving names to items

Some users prefer to assign readable names to items rather than using integer identifiers. This feature is available in both the graphical interface and the command line of SPMF. To use it, add @CONVERTED_FROM_TEXT as the first line of your input file, followed by one @ITEM line per item that maps its integer id to a name. For example:

@CONVERTED_FROM_TEXT
@FILETYPE="Simple transaction database"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
@ITEM=1=apple
@ITEM=2=orange
@ITEM=3=tomato
@ITEM=4=milk
@ITEM=5=bread
1 3 4
2 3 5
1 2 3 5
2 5
1 2 3 5

When this file is used, the output will display item names instead of numbers. For example, the MFI result would appear as:

apple orange tomato bread  #SUP: 2

Note that this feature can also be used programmatically from the SPMF source code via the ResultConverter class, though no dedicated source-code example is currently provided.

Performance

MISAMiner is designed for efficiency on dense datasets, where frequent items appear in many transactions and missing-sets are therefore small. In this regime the missing-set unions grow slowly, anchor-driven partitioning and absorption reduce the search space substantially, and the early-exiting frequency test rejects most candidate extensions after scanning only a fraction of each bit vector.

On very large sparse datasets, missing-sets may be close to the full transaction universe, which increases both the vector length B and the cost of each bitset operation. In that regime other methods may be more competitive.

Where can I get more information about MISAMiner?

The MISAMiner algorithm is described in the following paper:

Liyuan Wang and Jing Yang (2026) "MiSA-Miner An Anchor-Driven Missing-Set Framework for Maximal and Closed Frequent Itemset Mining." Proceedings of the 22nd International Conference on Intelligent Computing (ICIC 2026), Poster Volume I..

For a broad overview of frequent itemset mining algorithms, you may also read this survey paper.

<< Return to table of contents of SPMF documentation

Copyright © 2008-2026 Philippe Fournier-Viger. All rights reserved.