Wednesday, June 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.

61 comments:

  1. This post is a lifesaver i swear! Thanks a lot.

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

    ReplyDelete
  3. very nice explanation.... thanq very much...

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

    ReplyDelete
  5. thanks a lot... clear explanation..

    ReplyDelete
  6. 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. thanks...its really easy to understand.

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

    ReplyDelete
  8. 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
  9. so nice really thanx for such a nice explanation

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

      Delete
    2. Thank you for your kind appreciation.

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

    ReplyDelete
  11. 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
  12. 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
  13. oh very well ...
    saved me from exhaustion.... i have exam next day and your post enlightened me...
    thank you very much

    ReplyDelete
  14. Thank u... life savinng explanation..

    ReplyDelete
  15. thanks a ton, very helpful !

    ReplyDelete
  16. Great Explanation.. Thanks..

    ReplyDelete
  17. 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
  18. 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
  19. 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
  20. thanks a lot vvvvvvvvvvvvvvvvvgooddddddddddddddd

    ReplyDelete
  21. Thanks a lot.. I sware it helps to all

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

    ReplyDelete
  23. nice explanation

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

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

    ReplyDelete

Related Posts Plugin for WordPress, Blogger...