The Data Mining Forum 
IMPORTANT: This is the old Data Mining forum.
I keep it online so that you can read the old messages.
Please post your new messages in the new forum: https://forum2.philippe-fournier-viger.com/index.php
Can someone explain to me FPGrowth and FPTrees?
Posted by:
Simon
Date: May 03, 2011 09:44PM
Can someone explain to me FPGrowth and FPTrees?
Re: Can someone explain to me FPGrowth and FPTrees?
Posted by:
webmasterphilfv
Date: May 03, 2011 09:50PM
Hello,
FP-Growth is a little bit complicated to explain. The best way to understand it is to take the time to read the paper. You can even draw some fp-trees on paper to make sure that you understand how it works. But I can give you a brief description of the main process.
FPGrowth takes as input a transaction database. It outputs all the frequent itemsets (itemsets that appear in at least minsup transactions).
FPGROWTH performs two steps.
STEP1: BUILD FP-TREE: First, FP-GROWTH build the FP-TREE. You should consider the FP-TREE as an intermediary product produced by the algorithm. The FP-TREE is a compact representation of the database that is convenient for discovering the frequent itemsets.
STEP2: MINE FP-TREE: Second, FP-GROWTH use the FP-TREE to discover the frequent itemsets. This is performed by recursively calling the FP-GROWTH(tree, alpha) method described in the paper. Initially the method considers itemsets containing a single item. Then, the method is called recursively with each of these items to see if each item can be extended into a frequent itemset containing 2 items. Then, for each frequent itemset containing 2 items, the method will be called recursively to see if each one can be extended for 3 items... then 4 items... and so on. Discovering frequent itemsets is a recursive process.
That is the main idea. But for the details, you need to read the paper ;-)
By the way, I have some Java source code for FP-Growth and many other algorithms. Check my website SPMF to get it.
Edited 3 time(s). Last edit at 05/03/2011 09:53PM by webmasterphilfv.
FP-Growth is a little bit complicated to explain. The best way to understand it is to take the time to read the paper. You can even draw some fp-trees on paper to make sure that you understand how it works. But I can give you a brief description of the main process.
FPGrowth takes as input a transaction database. It outputs all the frequent itemsets (itemsets that appear in at least minsup transactions).
FPGROWTH performs two steps.
STEP1: BUILD FP-TREE: First, FP-GROWTH build the FP-TREE. You should consider the FP-TREE as an intermediary product produced by the algorithm. The FP-TREE is a compact representation of the database that is convenient for discovering the frequent itemsets.
STEP2: MINE FP-TREE: Second, FP-GROWTH use the FP-TREE to discover the frequent itemsets. This is performed by recursively calling the FP-GROWTH(tree, alpha) method described in the paper. Initially the method considers itemsets containing a single item. Then, the method is called recursively with each of these items to see if each item can be extended into a frequent itemset containing 2 items. Then, for each frequent itemset containing 2 items, the method will be called recursively to see if each one can be extended for 3 items... then 4 items... and so on. Discovering frequent itemsets is a recursive process.
That is the main idea. But for the details, you need to read the paper ;-)
By the way, I have some Java source code for FP-Growth and many other algorithms. Check my website SPMF to get it.
Edited 3 time(s). Last edit at 05/03/2011 09:53PM by webmasterphilfv.