The FP-Growth (Frequent Pattern Growth) algorithm and data association in data mining

The FP-Growth (Frequent Pattern Growth) algorithm is a data mining algorithm used to identify frequent itemsets and generate association rules in a dataset. It is specifically designed to overcome some limitations of the Apriori algorithm in terms of computational efficiency, especially when dealing with large datasets.

[wpda_org_chart tree_id=44 theme_id=50]

The FP-Growth algorithm

The FP-Growth (Frequent Pattern Growth) algorithm was proposed by Jiawei Han, Jian Pei and Yiwen Yin in their paper entitled “Mining Frequent Patterns without Candidate Generation” published in 2000. The authors developed this algorithm as a more efficient alternative to to the Apriori algorithm, which was widely used in that period for identifying frequent itemsets and generating association rules.

The Apriori algorithm, introduced before the 1990s, was an effective method for identifying frequent itemsets and generating association rules. However, it had limitations in terms of computational efficiency, especially on large datasets. To overcome the limitations of Apriori, Han, Pei, and Yin proposed FP-Growth in their 2000 paper. The main idea was to use a tree data structure called FP-Tree to efficiently represent frequent itemsets without having to generate all candidate itemsets.

FP-Growth takes advantage of the recursion and compact structure of the FP-Tree to identify frequent itemsets without the need to generate all candidate combinations. This made the algorithm more efficient than Apriori, especially on datasets with a high number of items or transactions.

The FP-Growth algorithm has quickly gained popularity in the data mining field due to its efficiency and ability to handle large datasets. It has been used in several applications, including shopping cart analysis, product recommendation, and pattern discovery in transactional data.

FP-Growth has contributed significantly to the advancement of data mining by providing a more efficient and scalable alternative for association analysis. Its introduction stimulated further research and development in this field.

Today, the FP-Growth algorithm is still widely used in data mining and machine learning contexts, particularly when dealing with large, complex datasets.

Operation of the FP-Growth algorithm

Here’s how the FP-Growth algorithm works:

• Construction of the FP-Tree: The initial step consists in creating an FP-Tree, a tree data structure that represents the frequent patterns in the dataset. The tree is built incrementally, starting with the least frequent transaction and adding nodes as you progress through the transactions.
• Generation of Frequent Itemsets: After building the FP-Tree, the algorithm recursively explores the tree to identify frequent itemsets. This process is more efficient than the Apriori approach, as it avoids explicitly generating all candidate itemsets.
• Generation of Association Rules: Finally, the algorithm generates association rules based on the identified frequent itemsets. These rules follow the same principle as association rules in Apriori, which indicate relationships between items in the dataset.

FP-Growth vs Apriori

• Computational Efficiency: FP-Growth is generally more efficient than Apriori, especially on large datasets, as it avoids generating all candidate itemsets.
• Compact Structure: The FP-Tree allows information regarding frequent itemsets to be compactly represented, reducing the need for repeated scans of the dataset.
• Less Memory Usage: Compared to Apriori, FP-Growth often requires less memory to store intermediate data structures.

The FP-Growth algorithm is particularly useful when dealing with large, complex datasets, where scalability and efficiency are key for fast and effective analysis of association patterns.

Python implementation

As for the Python language, the implementation of this algorithm is very simple, given that there is a specific library: pyfpgrowth. Make sure you install the library before continuing:

pip install pyfpgrowth

Now we can start working with the sample code:

import pyfpgrowth

# Example dataset
dataset = [
    ['apple', 'beer', 'bread'],
    ['apple', 'milk'],
    ['milk', 'bread'],
    ['apple', 'beer', 'milk'],
]

# Set minimum support
min_support = 2

# Applying the FP-Growth algorithm
patterns = pyfpgrowth.find_frequent_patterns(dataset, min_support)

# Extracting association rules
rules = pyfpgrowth.generate_association_rules(patterns, 0.7)  # Setting a confidence threshold of 70%

# Printing the results
print("Frequent Itemsets:")
print(patterns)

print("\nAssociation Rules:")
print(rules)

In this example:

find_frequent_patterns is used to find frequent itemsets in the dataset with a specified minimum support.

generate_association_rules is used to generate association rules based on frequent itemsets with a specified confidence threshold.

You can adjust the dataset, minimum support, and confidence threshold to suit your specific needs. The results will show the itemset freq

Frequent Itemsets:
{('beer',): 2, ('apple', 'beer'): 2, ('bread',): 2, ('apple',): 3, ('milk',): 3, ('apple', 'milk'): 2}

Association Rules:
{('beer',): (('apple',), 1.0)}

Let’s analyze the results obtained and their meaning together.

Frequent itemsets indicate how frequently items appear in the dataset. For example, the single item ‘apple’ appears in three transactions, while the combination ‘milk’ and ‘apple’ appears in two transactions.

Frequent Itemsets:

• (‘beer’,): 2: Beer appears in two transactions.
• (‘beer’, ‘apple’): 2: The combination of beer and apple appears in two transactions.
• (‘bread’,): 2: Bread appears in two transactions.
• (‘apple’,): 3: The apple appears in three transactions.
• (‘milk’,): 3: Milk appears in three transactions.
• (‘milk’, ‘apple’): 2: The combination of milk and apple appears in two transactions.

Association Rules:

('beer',) => ('apple',): This rule indicates that if someone buys beer, he will also buy apple with a confidence of 100% (1.0). This means that in all transactions where beer is present, apple is also present.

For example, if we consider this association rule, it means that in all transactions where beer is present (two transactions), apple is also present. The confidence is 1.0, meaning that this association was observed in all transactions containing beer.

These results provide information about frequent itemset associations in your dataset, helping you identify patterns or co-occurrence relationships between items.