6/29/2011

FP tree example (How to identify frequent patterns using FP tree algorithm)



FP tree algorithm, which use to identify frequent patterns in the area of Data Mining. I'm sure! after this tutorial you can draw a FP tree and to identify frequent patterns from that tree you have to read my next post, How to identify frequent patterns from FP tree.

Suppose you got a question as follows:

Question :Find all frequent itemsets or frequent patterns in the following database using FP-growth algorithm. Take minimum support as 30%.
Table 1 - Snapshot of the Database

Step 1 - Calculate Minimum support


First should calculate the minimum support count. Question says minimum support should be 30%. It calculate as follows:

Minimum support count(30/100 * 8) = 2.4

As a result, 2.4 appears but to empower the easy calculation it can be rounded to to the ceiling value. Now,

Minimum support count is ceiling(30/100 * 8) = 3

 Step 2 - Find frequency of occurrence

Now time to find the frequency of occurrence of each item in the Database table. For example, item A occurs in row 1,row 2,row 3,row 4 and row 7. Totally 5 times occurs in the Database table. You can see the counted frequency of occurrence of each item in Table 2.

Table2 -Frequency of Occurrence
 Step 3 - Prioritize the items


In Table 2 you can see the numbers written in Red pen. Those are the priority of each item according to it's frequency of occurrence. Item B got the highest priority (1) due to it's highest number of occurrences. At the same time you have opportunity to drop the items which not fulfill the minimum support requirement.For instance, if Database contain F which has frequency 1, then you can drop it.


*Some people display the frequent items using list instead of table. The frequent item list for the above table will be B:6, D:6, A: 5, E:4, C: 3.

Step 4 -Order the items according to priority

As you see in the Table 3 new column added to the Table 1. In the Ordered Items column  all the items are queued according to it's priority, which mentioned in the Red ink in Table 2. For example, in the case of ordering  row 1, the highest priority item is B and after that D, A and E respectively.

Table 3 - New version of the Table 1

Step 5 -Order the items according to priority

As a result of previous steps we got a ordered items table (Table 3). Now it's time to draw the FP tree. I'll mention it row by row.



Row 1:
Note that all FP trees have 'null' node as the root node. So draw the root node first and attach the items of the  row 1 one by one respectively. (See the Figure 1) And write their occurrences in front of it. (write using a pencil dear,because next time we have to erase it. :D)

Figure  1- FP tree for  Row 1
Row 2:
Then update the above tree (Figure 1) by entering the items of row 2. The items of row 2 are B,D,A,E,C. Then without creating another branch you can go through the previous branch up to E and then you have to create new node after that for C. This case same as a scenario of traveling through a road to visit the towns of the country. You should go through the same road to achieve another town near to the particular town.
When you going through the branch  second time you should erase one and write two for indicating the two times you visit to that node.If you visit through three times then write three after erase two. Figure 2 shows the FP tree after adding row 1 and row 2. Note that the red underlines which indicate the traverse times through the each node.

Figure  2- FP tree for Row 1,2
Row 3:
In row 3 you have to visit B,A,E and C respectively.  So you may think you can follow the same branch again by replacing the values of B,A,E and C . But you can't do that you have opportunity to come through the  B. But  can't connect B to existing A overtaking D. As a result you should draw another A and connect it to B and then connect new E to that A and new C to new E. See Figure 3.

Row 4:
Then row 4 contain B,D,A. Now we can just rename the frequency of occurrences in the existing branch. As B:4,D,A:3.


 Row 5:
Figure 3 - After adding third row
In fifth raw have only item D. Now we have opportunity draw new branch from 'null' node. See Figure 4.
Figure 4- Connect D to null node

Row 6:
B and D appears in row 6. So just change the B:4 to B:5 and D:3 to D:4.

Row 7:
Attach two new nodes A and E to the D node which hanging on the null node. Then mark D,A,E as D:2,A:1 and E:1.

 Row 8 :(Ohh.. last row)
Attach new node C to B. Change the traverse times.(B:6,C:1)


Figure 5 - Final FP tree
Step 6 - Validation


After the five steps the final FP tree as follows: Figure 5.

How we know is this correct?

Now count the frequency of occurrence of each item of the FP tree and compare it with Table 2. If both counts equal, then it is positive point to indicate your tree is correct.


I'm going to end this tutorial now. But we have to do some more to find frequent patterns. I will detail it in next post.

If there is any problem feel free to contact me via a comment.

97 comments:

  1. Anonymous29/9/11 12:35

    Very nice

    ReplyDelete
  2. This post is a lifesaver i swear! Thanks a lot.

    ReplyDelete
  3. @ 2nd Ano : your comment motivate me to complete this post... thankx for comment..........

    ReplyDelete
  4. very nice explanation.... thanq very much...

    ReplyDelete
  5. Thank you so much,, it’s really helpful.

    ReplyDelete
  6. A nice one & helpful to us !

    ReplyDelete
  7. thanks a lot... clear explanation..

    ReplyDelete
  8. You helped me pass in my final year exam. BEST EXPLANATION. YOU ARE THE BEST TEACHER SIR....

    ReplyDelete
    Replies
    1. You are Welcome! Thanks for comment

      Delete
    2. Anonymous3/4/13 11:16

      thanks...its really easy to understand.

      Delete
  9. It was helpful ..Thaaanks

    ReplyDelete
  10. Anonymous26/3/12 19:32

    http://hareenlaks.blogspot.in/2011/06/fp-tree-example-how-to-identify.html

    ReplyDelete
  11. Anonymous7/8/12 09:52

    hareendra baba aapke ashirwad se humne zindagi ki katinaiyon se moksh paa liya........humari teacher ne kya sikhaya kuch nahi samjha..........thnx 4 your post .....it was a life changer

    ReplyDelete
    Replies
    1. I understand somewhat Hindi because I'm watching bollywood movies... :)

      shukriya...

      Delete
  12. Anonymous24/9/12 07:03

    so nice really thanx for such a nice explanation

    ReplyDelete
    Replies
    1. Dhritiman3/10/12 12:12

      Thanks Man .. Very Nice and Flawless .. Amazing Flow and Language .. Impressed . :)

      Delete
    2. Thank you for your kind appreciation.

      Delete
  13. Thank You very much for such a nice explanation..

    ReplyDelete
  14. thank you.. i was struggling through my lecturer's explanation for 20 minutes. your page turned up on google and this saved so much hassle and confusion!

    ReplyDelete
  15. Thank u very very much dear

    ReplyDelete
  16. Thank you, may God bless you for your efforts. You have helped me understand a concept for which I will have a major exam this week.

    ReplyDelete
    Replies
    1. Sorry, I'm late to send my best wishes to you. How was it?

      Delete
  17. Anonymous25/3/13 15:04

    Thank you

    ReplyDelete
  18. oh very well ...
    saved me from exhaustion.... i have exam next day and your post enlightened me...
    thank you very much

    ReplyDelete
  19. Anonymous7/5/13 14:05

    Thank u... life savinng explanation..

    ReplyDelete
  20. Anonymous13/5/13 04:32

    thanks a ton, very helpful !

    ReplyDelete
  21. Anonymous4/6/13 21:12

    Great Explanation.. Thanks..

    ReplyDelete
  22. amazing sir,
    but i hd an query that sir alwayz FP-Tree works like this or ur code works like this .........
    i mean sir i m using rapid miner tool to generate association rules using FP-Tree and will it also works in same manner........
    do rply sir

    ReplyDelete
    Replies
    1. I feel difficulty to understand your question..

      Can you explain it again?

      Delete
  23. Anonymous8/7/13 20:26

    FIRST OF ALL I THANK U FOR THIS POST.
    SECOND I IMPLEMENT FP-GROWTH IN C# BUT WHEN THE DATA GETS BIGGER IT GETS VERY SLOW IN STEP OF COMBINATION.
    Can u tell me a better way to generate combinations of 50 items in small time thank u again.

    ReplyDelete
    Replies
    1. You are welcome!

      sorry I have no experience of coding FP-trees. But I'll try to find something for you when I free.

      Delete
  24. Sir...thank you so much for sharing this info....this is possibly the best explanation i have ever come across..once again thank you.... :)

    ReplyDelete
  25. thanks a lot vvvvvvvvvvvvvvvvvgooddddddddddddddd

    ReplyDelete
  26. Anonymous28/1/14 11:33

    Thanx a lot....

    ReplyDelete
  27. Anonymous11/4/14 20:10

    Thanks a lot.. I sware it helps to all

    ReplyDelete
  28. Very valuable

    ReplyDelete
  29. Anonymous20/5/14 02:01

    Vie good explanation ...book's stuff confused me....

    ReplyDelete
  30. Anonymous9/7/14 10:47

    nice explanation

    ReplyDelete
  31. thanks so much...really u have explained it in very nice way and in systematic manner...

    ReplyDelete
  32. Thank you very much for nice explanation!!

    ReplyDelete
  33. good job brother.. well done!!

    ReplyDelete
  34. Anonymous16/2/15 09:52

    You have made it very clear. It is the first clear example I have found. Great job. Thanks.

    ReplyDelete
  35. Very descriptive but with easy steps. Good work and keep it up (Y)

    ReplyDelete
  36. Replies
    1. This comment has been removed by the author.

      Delete
  37. Anonymous18/1/17 12:54

    great!!
    thank u

    ReplyDelete
  38. Anonymous23/1/17 15:04

    I'm studying for my Data Mining exam and it's hard to find good examples for some algorithms. Thank you for this great, detailed example - it is appreciated.

    ReplyDelete
  39. just got everything in one go

    ReplyDelete
  40. Anonymous31/3/17 15:54

    You made it so easy to understand. You're an awesome teacher. Thank you

    ReplyDelete
  41. Anonymous11/7/17 14:54

    it is FP tree construction. How to write frequent patterns from the tree?

    ReplyDelete
  42. Anonymous27/7/17 10:57

    Very nice post for construction blog.
    construction magazine in India

    ReplyDelete
  43. Nice tutorial...thanks !

    ReplyDelete
  44. Very Good Explanation. Nice walkthrough and example!

    ReplyDelete
  45. How to implement this in R

    ReplyDelete
  46. Anonymous2/2/18 20:46

    Very helpful. I read this in other sites. But it is very easy and simple and very useful. Thanks alot

    ReplyDelete
  47. Thank you very much. This post really helpful.

    ReplyDelete
  48. Completely understand in easy way

    ReplyDelete
  49. Completely understand in easy way

    ReplyDelete
  50. Thank you very much. Can you explain generation of frequent itemsets using fptree

    ReplyDelete
  51. Thus is a great writeup with detailed step by step. I think no book or article lays this out in so details. Just awesome.. Thank you for helping me learn this the easy way

    ReplyDelete
  52. Its very easy to understand...!

    ReplyDelete
  53. How to prioritize if 2 items have equal frequencies? Ex- B=6 and D=6, Why do you B the first priorty?

    ReplyDelete
  54. Thank you, this was extremely helpful.

    ReplyDelete