How to identify frequent patterns from FP tree

Before reading this post it is valuable for reading my previous post about FP tree. In that post I mentioned how to draw a FP tree using a given database table. If you already know how to draw a FP tree it's OK.

Figure 1

In that post we got the final output(Fp tree) as displays in Figure 1. And I think you remember that the Minimum support count is 3.

Let's find the Frequent Patterns(FPs) from FP tree.

The Items of the DB and there frequency of occurrences can be listed as
B:6
D:6
A:5
E:4
C:3

Note that the order of the list defined according to the priorities given in the Table2 of previous post. To observe the FPs we have to go through bottom to top, from C to B.

C

Figure 2

First need to find the conditional pattern base for C:3. If you wonder how 3 comes, it is due to frequency of occurrence of C. Now go to Figure 1 and check the Cs. There are 3 Cs and one occurrence for each. Now traverse bottom to top and get the branches which have Cs with the occurrence of C. For more clarification you can see Figure 2. We got 3 branches and they are
BDAE: 1 - The branch which surrounded in Blue.
B: 1 - The branch which surrounded in Red.
BAE: 1 - The branch which surrounded in Brown.

These branches regard as Conditional Pattern Base for C. You have to note three facts.
1. Even we traverse bottom to top we write the branches in top to bottom manner.
2. C is not there.
3. 1 came after each branch to represent the frequency of occurrence of C in each branch. You will more clear about this lately.

To ensure you correctly got all the occurrences of C in FP tree, add occurrences of C in each branch and compare with all the occurrences of C in FP tree; for this case 1+1+1 = 3 it is correct.

Then we have to find F-list from the Conditional Pattern Base of C. The list of items are B:3,D:1,A:2,E:2 but B:3 only eligible for sitting on the F-list due to fulfill the Minimum Support Count.So the F-list is
B:3

Now draw the Conditional FP tree for C. It is in Figure 3. When drawing the conditional FP tree you have to make sure to get Conditional Pattern Base as Ordered Items which mentioned in previous post Table 3. Now we can find C:3, BC:3 as identified FPs from tree.

Figure 3

If you answer a question paper the answer will be

Conditional pattern base for C:3

BDAE: 1; B: 1; BAE: 1

F-list: B:3

Conditional FP-tree for C (Draw Figure 3.)

Frequent patterns

C:3, BC:3

Wait..Wait..this is not full answer.
Then we will find FPs by using item E.

E

Let's find Conditional Pattern Base for E:4. It depicts on Figure 4 and due to the previous explanation I think you already have the idea. If not ask as a comment.

Figure 4

BDA: 2 - Red line
BA:1 - Brown line
DA:1 - Blue line

And F-list will be
A:4
B:3
D:3

3 comes to B by 2 Bs coming from BDA: 2 and 1 B coming from BA:1. And 4 As and 3 Ds also according to that manner. Why A appears before the B in F-list even B appears before previously? That have a reason. We got a list from this Conditional Pattern Base as B:3, D:3, A:4. But in F-list they should appear according to their frequency of occurrences in Conditional Pattern Base. So A coming to front and others going to back. Then it is easy to use for creating conditional FP tree for E.

Figure 5

Figure 5 displays Conditional FP tree for E according to the same method described in previous post. Make sure to use Conditional Pattern Base as Ordered Items.

For a moment forget the FP tree and conditional FP tree for E put on to your mind. So think we only have this FP tree and need to find FPs from this.

Items in this FP tree are
A:4
B:3
D:3

Let's go bottom to top.

DE

From where DE comes ? Even we deleted FP tree it remains in the Recycled Bin. :) We are going to identify FPs for DE. Because of we use conditional FP tree for E, E comes to back.

Figure 6

Conditional pattern base for DE:3
A:1, AB:2
F-list: A:3
Conditional FP-tree for DE : Figure 6
Frequent patterns
DE:3, ADE:3

I think you don't need explanation. Then we are going to find FPs by using BE.

BE

Conditional pattern base for BE:3
A:3
F-list: A:3
Conditional FP-tree for DE : Figure 6
Frequent patterns
BE:3, ABE:3

Then move to AE.

AE

Conditional pattern base for AE:4
NULL
Conditional FP-tree for DE
NULL
Frequent patterns
AE:4

We find all FPs of conditional FP tree for E. Next step is remind the previous or main tree. And before leave E we can write E:4 also as a FP. Let's move to A.

A

Figure 7

Conditional pattern base for A:5
BD: 3; B:1; D:1
F-list: B:4, D:4
Conditional FP-tree for A : Figure 7

Then we will go on the conditional FP tree for A as like as previous trip.

AD

Conditional pattern base for AD:4
B:3
F-list :B:3
Conditional FP-tree for AD : Figure 3
Frequent patterns
AD:4, ABD:3

AB

Conditional pattern base for AB:4
NULL
Frequent patterns
AB:4

And also can get A:5 as a FP.

Figure 8

D

Conditional pattern base for D:6
B: 4
F-list : B:4
Conditional FP-tree for D : Figure 8
Frequent patterns
D:6, BD:4

Then last item, B.

B

Conditional pattern base for B:6
NULL
Conditional FP-tree for B
NULL
Frequent patterns
B:6

Hurray! We finish all items and this is time to collect all bins in to a single bin. The identified frequent itemsets from the Database (Table 1 in Previous post) with minimum support as 30% are C:3, BC:3, DE:3, ADE:3 , BE:3, ABE:3, AE:4, E:4, AD:4, ABD:3, AB:4, A:5, D:6, BD:4, B:6.

I'm sure you don't need any support for creating full answer. Please leave your comments below if this is valuable to you.