Mining Probabilistic Periodic Frequent Patterns in an Uncertain Transaction Database using the PPFP-Growth Algorithm (SPMF documentation)

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

How to run this example?

What is PPFP-Growth?

PPFP-Growth (Hamimid et al., 2026) is an algorithm for discovering probabilistic periodic frequent patterns in an uncertain transaction database, that is a database where each item of each transaction exists only with some probability.

Besides the expected support and the periodicity of an itemset, PPFP-Growth computes the probability that the itemset is periodic, that is, the probability that the largest gap between two consecutive occurrences of the itemset does not exceed a maximum periodicity. It only keeps the itemsets whose probability of periodicity reaches a threshold set by the user.

The algorithm uses a prefix tree, as the FP-Growth algorithm does. To compute the probability of periodicity of an itemset, it decomposes the occurrences of the itemset at the transactions where the itemset is certain (probability 1), and multiplies the probabilities obtained for each part.

Why mine periodic patterns in uncertain data? In many applications, data is uncertain (e.g. data collected by noisy sensors, or items that are predicted rather than observed). In such data, an itemset may appear frequently, but it may be impossible to say with confidence that it appears regularly. By considering the probability of periodicity, PPFP-Growth finds patterns that are frequent and that appear regularly with a high probability.

What is the input?

PPFP-Growth takes as input an uncertain transaction database and the following parameters:

Parameter Meaning Example
Maximum periodicity (maxPer) The largest allowed gap between two consecutive occurrences of an itemset, in number of transactions (an integer ≥ 1) 4
Minimum expected support (minSup) A fraction of the number of transactions, in [0, 1], which can also be written as a percentage 35%
Minimum probability of periodicity (β) A real number in [0, 1] 0.6
Maximum pattern length (optional) The largest number of items in a pattern (an integer ≥ 1) 3

An uncertain transaction database is a sequence of transactions. Each transaction is a set of items, and each item has an existential probability in the interval (0, 1], which is the probability that the item really appears in that transaction. 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 "contextUncertainPPFP.txt" in the package ca.pfv.spmf.tests of the SPMF distribution.


Transaction (item with its probability)
t1 1(1.0) 2(0.9) 3(0.8) 4(1.0)
t2 2(0.9) 3(0.8) 4(1.0)
t3 1(1.0) 3(0.8) 5(0.5)
t4 2(0.9) 3(0.8)
t5 1(0.6) 3(1.0) 5(0.5)
t6 3(0.8)
t7 1(1.0) 2(0.9) 3(0.8) 4(0.9)
t8 4(1.0) 5(0.3)
t9 2(0.9) 3(0.8) 4(0.9)
t10 1(0.6) 3(1.0)

For example, the first transaction indicates that item 1 and item 4 appear for sure in t1 (probability 1.0), while item 2 appears with a probability of 0.9 and item 3 with a probability of 0.8. Items are assumed to be independent.

What are real-life examples of such a database? One example is a database of events detected by sensors, where each detection has a confidence value. Another example is a customer database where the items that a customer is likely to buy are predicted with some probability.

What is the output?

The output of PPFP-Growth is the set of probabilistic periodic frequent patterns. An itemset is an unordered set of distinct items. An itemset X is a probabilistic periodic frequent pattern if all three of the following conditions are met, where n is the number of transactions:

The measures used above are defined as follows:

For example, if we run PPFP-Growth with maxPer = 4, minSup = 35% (that is an expected support of at least 3.5, since there are 10 transactions) and β = 0.6, we obtain the following 4 patterns:

itemsets expected support periodicity probability of periodicity
{1} 4.2 3 1
{1 3} 3.6 3 0.7168
{2} 4.5 3 0.81
{3} 7.6 2 0.9904128

Example of computation. Item 3 occurs in every transaction except t8. It is certain in t5 and t10. Its periodicity is therefore not larger than 4 unless (1) transactions t1 to t4 are all absent (the period from TID 0 to t5 would be 5), or (2) transactions t6, t7 and t9 are all absent (the period from t5 to the end of the database would be 5). Since each of these occurrences is absent with a probability of 0.2, the probability of periodicity is P({3}) = (1 − 0.24) × (1 − 0.23) = 0.9904128.

Examples of itemsets that are not output. The itemset {2, 3} has an expected support of 3.6 and a periodicity of 3, but its probability of periodicity is 0.5184, which is less than β = 0.6. Item 4 has an expected support of 4.8, but there is a period of 5 between its occurrences in t2 and t7 (so it can never be periodic with maxPer = 4). Item 5 has an expected support of only 1.3.

Input file format

The input file format of PPFP-Growth is defined as follows. It is a text file. The two first lines are optional metadata indicating the type of data and the source of the data. Then the following lines each represents a transaction. The TID (transaction identifier) of a transaction is its position among the transaction lines (1, 2, 3...).

For example, for the previous example, the input file is defined as follows:

@FILETYPE="Uncertain transaction database"
@SOURCE="Example database of the PPFP-growth paper (items a..e encoded as 1..5)"
1(1.0) 2(0.9) 3(0.8) 4(1.0)
2(0.9) 3(0.8) 4(1.0)
1(1.0) 3(0.8) 5(0.5)
2(0.9) 3(0.8)
1(0.6) 3(1.0) 5(0.5)
3(0.8)
1(1.0) 2(0.9) 3(0.8) 4(0.9)
4(1.0) 5(0.3)
2(0.9) 3(0.8) 4(0.9)
1(0.6) 3(1.0)

The first line means that the transaction t1 contains item 1 with a probability of 1.0, item 2 with a probability of 0.9, item 3 with a probability of 0.8 and item 4 with a probability of 1.0. The following lines follow the same format.

Output file format

The output file format of PPFP-Growth is defined as follows. It is a text file. The two first lines are metadata indicating the type of patterns and the software that has generated the patterns. Then the following line is the list of patterns, where each line represents a probabilistic periodic frequent pattern. On each line, the items of the pattern are listed in ascending order, each followed by a single space. Then, the keyword "#SUP:" appears and is followed by the expected support of the pattern, then the keyword "#MAXPER:" appears and is followed by the periodicity of the pattern, and finally the keyword "#PROBPER:" appears and is followed by the probability of periodicity of the pattern. Real values are written with at most 12 significant digits. For example, we show below the output file for this example.

@FILETYPE="Probabilistic periodic frequent itemsets"
@SOURCE="SPMF SOFTWARE https://philippe-fournier-viger.com/spmf/"
1 #SUP: 4.2 #MAXPER: 3 #PROBPER: 1
1 3 #SUP: 3.6 #MAXPER: 3 #PROBPER: 0.7168
2 #SUP: 4.5 #MAXPER: 3 #PROBPER: 0.81
3 #SUP: 7.6 #MAXPER: 2 #PROBPER: 0.9904128

For example, the second line indicates that the itemset {1, 3} has an expected support of 3.6, a periodicity of 3 and a probability of periodicity of 0.7168. The following lines follow the same format. Note that the order of the lines may differ from the one shown above.

Performance and limitations

PPFP-Growth is more complex than algorithms for periodic frequent pattern mining in certain databases, because it must compute the probability that an itemset is periodic. Some important points should be considered:

Implementation details

This is the original implementation of the algorithm.

The input format of PPFP-Growth is different from the format of the other algorithms of SPMF that take a transaction database as input. It is the format of a uncertain transaction database, where each item is associated with an existential probability.

Where can I get more information about the PPFP-Growth algorithm?

This is the reference of the article describing the PPFP-Growth algorithm:

Hamimid, I., Nouioua, F., Boutouhami, S., Fournier-Viger, P. (2026). Probabilistic Periodic Frequent Pattern Mining in Uncertain Databases. Applied Intelligence, to appear. DOI: 10.1007/s10489-026-07388-7