Downloaded 1,926 times
Uploaded byShihab Rahman
Data mining fp growth
The document discusses the FP-Growth algorithm for frequent pattern mining. It improves upon the Apriori algorithm by not requiring candidate generation and only requiring two scans of the database. FP-Growth works by first building a compact FP-tree structure using two passes over the data, then extracting frequent itemsets directly from the FP-tree. An example is provided where an FP-tree is constructed from a sample transaction database and frequent patterns are generated from the tree. Advantages of FP-Growth include only needing two scans of data and faster runtime than Apriori, while a disadvantage is the FP-tree may not fit in memory.
In this document
Powered by AI
Presentation by Shihab Rahman and Dolon Chanpa introduces FP Growth as a scalable technique for mining frequent patterns in databases.
FP Growth improves upon Apriori by eliminating candidate generation and requiring only two database scans through building an FP-tree.
Illustrates a transaction table and the process of constructing an FP-tree based on transactions and support counts.
Details the step-by-step process of building an FP-tree with support counts from various transactions and emphasizes item frequency.
Discusses conditional pattern bases and FP trees for each item derived from the primary FP-tree, showing their structure.
Lists frequent patterns generated from the FP-tree, outlining the advantages and disadvantages of FP-Growth technique.
Ends with a thank you to the audience, concluding the presentation.
Data mining fp growth
- 1. Presented By: Shihab Rahman DolonChanpa Department Of Computer Science And Engineering, University of Dhaka
- 2. FP GrowthStands for frequent pattern growth It is a scalable technique for mining frequent pattern in a database
- 3. FP growthimproves Apriority to a big extent Frequent Item set Mining is possible without candidate generation Only “two scan” to the database is needed BUT HOW?
- 4. Simply atwo step procedure – Step 1: Build a compact data structure called the FP-tree • Built using 2 passes over the data-set. – Step 2: Extracts frequent item sets directly from the FP- tree
- 5. Now LetsConsider the following transaction table TID List of item IDs T100 I1,I2,I3 T200 I2,I4 T300 I2,I3 T400 I1,I2,I4 T500 I1,I3 T600 I2,I3 T700 I1,I3 T800 I1,I2,I3,I5 T900 I1,I2,I3
- 6. Now wewill build a FP tree of that database Item sets are considered in order of their descending value of support count.
- 7.
- 8.
- 9.
- 10.
- 11.
- 12.
- 13.
- 14.
- 15.
- 16. I2 7 I1 6 I36 I4 2 I5 2 null I2:7 I1:4 I3:2 I3:2 I5:1 I4:1 I4:1 To facilitate tree traversal, an item header table is built so that each item points to its occurrences in the tree via a chain of node-links. I1:2 I3:2 I5:1 FP Tree Construction Over!! Now we need to find conditional pattern base and Conditional FP Tree for each item
- 17. null I2:7 I1:4 I3:2 I3:2 I5:1 I4:1 I4:1 I1:2 I3:2 I5:1 Conditional Pattern Base I5{{I2,I1:1},{I2,I1,I3:1}} Conditional FP Tree for I5:{I2:2,I1:2}
- 18. null I2:7 I1:4 I3:2 I3:2 I5:1 I4:1 I4:1 I1:2 I3:2 I5:1 Conditional Pattern Base I4{{I2,I1:1},{I2:1}} Conditional FP Tree for I4:{I2:2}
- 19. null I2:7 I14 I3:2 I3:2 I5:1 I4:1 I4:1 I1:2 I3:2 I5:1 Conditional Pattern Base I3{{I2,I1:2},{I2:2},{I1:2}} Conditional FP Tree for I3:{I2:4,I1:2},{I1:2}
- 20. null I2:7 I1:4 I3:2 I3:2 I5:1 I4:1 I4:1 I1:2 I3:2 I5:1 Conditional Pattern Base I1{{I2:4}} Conditional FP Tree for I1:{I2:4}
- 21. Frequent Pattern Generated I5{I2, I5: 2}, {I1, I5: 2}, {I2, I1, I5: 2} I4 {I2, I4: 2} I3 {I2, I3: 4}, {I1, I3: 4}, {I2, I1, I3: 2} I1 {I2, I1: 4}
- 22. Advantages ofFP-Growth only 2 passes over data-set “compresses” data-set no candidate generation much faster than Apriori Disadvantages of FP-Growth FP-Tree may not fit in memory!! FP-Tree is expensive to build 0 10 20 30 40 50 60 70 80 90 100 0 0.5 1 1.5 2 2.5 3 Support threshold(%) Runtime(sec.) D1 FP-grow th runtime D1 Apriori runtime
- 23.