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?
- If you are using the graphical interface, (1) choose the "PPFP-Growth" algorithm, (2) select the input file "contextUncertainPPFP.txt", (3) set the output file name (e.g. "output.txt"), (4) set the maximum periodicity to 4, (5) set the minimum expected support to 35%, (6) set the minimum probability of periodicity to 0.6 (7) optionally, set the maximum pattern length (leave it empty for no limit) and (8) click "Run algorithm".
- If you want to execute this example from the command line,
then execute this command:
java -jar spmf.jar run PPFP-Growth contextUncertainPPFP.txt output.txt 4 35% 0.6 in a folder containing spmf.jar and the example input file contextUncertainPPFP.txt.
The maximum pattern length is an optional fifth parameter. For example, ... output.txt 4 35% 0.6 3 limits the patterns to at most 3 items. - If you are using the source code version of SPMF, launch the file "MainTestPPFPgrowth_saveToFile.java" in the package ca.pfv.spmf.tests.
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:
- expSup(X) ≥ minSup × n (it is frequent),
- per(X) ≤ maxPer (it is periodic),
- P(X) ≥ β (it is periodic with a sufficient probability).
The measures used above are defined as follows:
- The existential probability of an itemset X in a transaction t, denoted Et(X), is the product of the probabilities of the items of X in t (if t contains all the items of X). For example, the existential probability of {1, 3} in t5 is 0.6 × 1.0 = 0.6.
- The expected support expSup(X) is the sum of Et(X) over all the transactions that contain every item of X. For example, the expected support of {1, 3} is 0.8 + 0.8 + 0.6 + 0.8 + 0.6 = 3.6.
- The periodicity per(X) is the largest period between two consecutive transactions containing X. The period from the beginning of the database (TID 0) to the first occurrence, and the period from the last occurrence to the end of the database (TID n), are also counted. For example, item 1 appears in t1, t3, t5, t7 and t10, so its periods are 1, 2, 2, 2, 3 and 0 and its periodicity is 3.
- The probability of periodicity P(X) is the total probability of the possible worlds (the possible ways in which the occurrences of X are present or absent) in which every period of X is at most maxPer. When an occurrence is absent, its two neighbouring periods are merged into a longer period.
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...).
- Items are written as item(probability) and are separated from each other by single spaces. For example, 1(0.6) means that item 1 appears with a probability of 0.6. The notation with item and probability pairs (e.g. 1 0.6 2 0.9) is also accepted.
- An item is a non-negative integer, and an item can appear at most once in a transaction.
- A probability must be a real number in the interval (0, 1].
- Empty lines, and lines starting with the characters #, % or @, are ignored and are not counted as transactions.
- If a line is malformed, the algorithm stops with a message giving the number of the line.
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:
- Exponential worst case. The probability of periodicity is computed exactly, by enumerating the possible worlds of each part of the decomposition. The cost is thus exponential in the number of uncertain occurrences between two certain occurrences of an itemset. Large maxPer values, low minSup values, and data with few certain occurrences can make the algorithm very slow. For example, on an uncertain version of the Mushroom dataset (8,124 transactions, with about 30% of uncertain occurrences), running the algorithm with maxPer = 100, minSup = 5% and β = 0.95 did not finish within 2 minutes, while running it with maxPer = 30 and minSup = 20% finished in less than 1 second for β = 1, and in about 1 minute for β = 0.
- Long runs of uncertain occurrences. Very long runs of uncertain occurrences can exhaust the Java stack (a StackOverflowError). This was observed in a test with 10,000 consecutive uncertain occurrences. In such a case, the Java stack size can be increased (e.g. using the -Xss option of the Java virtual machine).
- Positional TIDs. Transactions are identified by their position in the file. Timestamps are not supported.
- Independence. Items and transactions are assumed to be independent (possible-world model).
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