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.