Menu
How do we calculate the Time complexity and Space complexity of FP_growth algorithm in Data Mining??
633
FP-growth is an improved version of the Apriori Algorithm which is widely used for frequent pattern mining(AKA Association Rule Mining). It is used as an analytical process that finds frequent patterns or associations from data sets.
FP-Growth (frequent-pattern growth) algorithm is a classical algorithm in association rules mining. But the FP-Growth algorithm in mining needs two times to scan database, which reduces the efficiency of algorithm.
Apriori is a Join-Based algorithm and FP-Growth is Tree-Based algorithm for frequent itemset mining or frequent pattern mining for market basket analysis.
What is the input of the FPGrowth algorithm? The input of FPGrowth is a transaction database (aka binary context) and a threshold named minsup (a value between 0 and 100 %). A transaction database is a set of transactions.
According to my understanding, the time complexity should be O(n2) if the number of unique items in the dataset is n. The complexity depends on searching of paths in FP tree for each element of the header table, which depends on the depth of the tree. Maximum depth of the tree is upper-bounded by n for each of the conditional trees. Thus the order is: O (No. of items in header table * maximum depth of tree)= O(n*n).
118
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
