Example of The FP tree algorithm. Explained each and every steps

OnkarChavan24 779 views 13 slides Jun 10, 2021
Slide 1
Slide 1 of 13
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13

About This Presentation

Frequent Pattern Growth Algorithm is the method of finding frequent patterns without candidate generation.


Slide Content

FP TREE ALGORITHM - Sanket Pandharkar - [email protected] - ROHIT rote - [email protected] - NIRANT NAIK - [email protected] - ONKAR CHAVAN - [email protected] PRESENTED BY Modern College Of Arts, Science & Commerce Ganeshkhind Pune-16. Department of Computer Science Data Mining Assignment Guided By : Dr. Dipali Meher

Example : Find all frequent itemsets in the database using FP-growth algorithm. Take minimum support = 2 Transaction Id Items T1 Milk, Sugar, Bread, Egg T2 Sugar, Bread, Butter T3 Milk, Egg, Sugar T4 Bread, Butter, Egg T5 Bread, Butter, Milk T6 Bread, Butter T7 Milk, Sugar, Egg T8 Bread, Egg Now we will build a FP Tree of that database Item Sets are considered in order of their descending value of support count

Find Frequency of occurrence : Transaction Id Frequency Milk 4 Sugar 4 Bread 6 Egg 5 Butter 4 Priority the items : Transaction Id Frequency Priority Milk 4 3 Sugar 4 4 Bread 6 1 Egg 5 2 Butter 4 5 Since min_sup = 2

● Ordering each itemsets as per the priorities Transaction Id Items Ordered Items T1 Milk, Sugar, Bread, Egg Bread, Egg, Milk, Sugar T2 Sugar, Bread, Butter Bread, Sugar, Butter T3 Milk, Egg, Sugar Egg, Milk, Sugar T4 Bread, Butter, Egg Bread, Egg, Butter T5 Bread, Butter, Milk Bread, Milk, Butter T6 Bread, Butter Bread, Butter T7 Milk, Sugar, Egg Egg, Milk, Sugar T8 Bread, Egg Bread, Sugar

● Now drawing FP-tree by using ordered itemsets one by one : Row 1 Null Bread : 1 Egg : 1 Milk : 1 Sugar : 1

For, Row 2 : Null Butter : 1 Sugar : 1 Sugar : 1 Milk : 1 Egg : 1 Bread : 2

For, Row 3 : Null Sugar : 1 Milk : 1 Egg : 1 Bread : 2 Egg : 1 Milk : 1 Sugar : 1 Sugar : 1 Butter : 1

For, Row 4 : Null Egg : 1 Butter : 1 Bread : 3 Egg : 2 Milk : 1 Sugar : 1 Sugar : 1 Butter : 1 Sugar : 1 Milk : 1

For, Row 5 : Null Bread : 1 Milk : 1 Sugar : 1 Bread : 4 Egg : 2 Egg : 1 Milk : 1 Sugar : 1 Butter : 1 Milk : 1 Butter : 1 Sugar : 1

For, Row 6 : Null Bread : 5 Sugar : 1 Milk : 1 Egg : 1 Butter : 1 Butter : 1 Egg : 2 Milk : 1 Sugar : 1 Sugar : 1 Butter : 1 Milk : 1 Butter : 1

For, Row 7 : Null Butter : 1 Egg : 2 Milk : 2 Sugar : 2 Butter : 1 Bread : 5 Egg : 2 Milk : 1 Sugar : 1 Sugar : 1 Butter : 1 Milk : 1 Butter : 1

For, Row 8 : Final FP Tree => Null Sugar : 2 Milk : 2 Egg : 2 Butter : 1 Butter : 1 Bread : 6 Egg : 3 Milk : 1 Sugar : 1 Sugar : 1 Butter : 1 Milk : 1 Butter : 1

Thank-you!!!