Scribd
Upload
25 views

Recursive Functions Description

The document discusses two topics: 1) Recursive functions using the Fibonacci sequence as an example, where each term is the sum of the previous two terms. 2) Applying sequence pattern mining to find frequent patterns in transaction data using depth first search and support thresholds. It extracts patterns from example sequence data, calculating the support of single items and pairs to determine which patterns satisfy the minimum support.

Uploaded by

Raya Revanza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
25 views

Recursive Functions Description

The document discusses two topics: 1) Recursive functions using the Fibonacci sequence as an example, where each term is the sum of the previous two terms. 2) Applying sequence pattern mining to find frequent patterns in transaction data using depth first search and support thresholds. It extracts patterns from example sequence data, calculating the support of single items and pairs to determine which patterns satisfy the minimum support.

Uploaded by

Raya Revanza
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 3

Recursive Functions (Assignment)

1. Fibonacci Sequence
f ( n )=f ( n−1 ) + f (n−2)
Illustration
We have initial sequences f ( 0 )=0 , f ( 1 )=1
f ( 2 ) =f ( 1 ) +f ( 0 )=0+1=1
f ( 3 )=f ( 2 ) + f (1 ) =1+ 1=2
f ( 4 ) =f ( 3 ) + f (2 )=2+1=3
⋯
2. Application on Sequence pattern mining based on depth first search
Prepare the data

Sequence ID Sequence Class label


1 CBAB Pos
2 AACCB Pos
3 BBAAC Pos
4 BCAB Neg
5 ABACB Neg

Parameters
δ =0.5 and α =0.5

Step 1 :
Find the distinct items A, B, C from the above table
Calculate each item
supp(A, pos) = A occurs on the above table at pos / the number of sequence at pos
= 3 / 3 = 1 ≥ 0.5 ok
supp(A, neg) = A occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail-> extend
supp(B, pos) = B occurs on the above table at pos / the number of sequence at pos
= 3 / 3 = 1 ≥ 0.5 ok
supp(B, neg) = B occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail-> extend
supp(C, pos) = C occurs on the above table at pos / the number of sequence at pos
= 3 / 3 = 1 ≥ 0.5 ok
supp(C, neg) = C occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail-> extend

Step 2 :
Extend the previous items AA, AB, AC, BA, BB, BC, CA, CB, CC
supp(AA, pos) = AA occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok (2 -> can be found sequence ID 2 and 3)
supp(AA, neg) = AA occurs on the above table at neg / the number of sequence at neg
= 1/ 2 =1 ≤ 0.5 ok
Save AA in a variable Pattern -> PP={AA}
supp(AB, pos) = AB occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok (2 -> can be found sequence ID 1 and 2)
supp(AB, neg) = AB occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail -> extend
supp(AC, pos) = AC occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok (2 -> can be found sequence ID 2 and 3)
supp(AC, neg) = AC occurs on the above table at neg / the number of sequence at neg
= 1 / 2 =0.5 ≤ 0.5 ok
Save AC in a variable Pattern -> PP={AA, AC}
supp(BA, pos) = BA occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok (2 -> can be found sequence ID 2 and 3)
supp(BA, neg) = BA occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail -> extend
supp(BB, pos) = BB occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok (2 -> can be found sequence ID 1 and 3)
supp(BB, neg) = BB occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail -> extend
supp(BC, pos) = BC occurs on the above table at pos / the number of sequence at pos
= 1 / 3 = 0.33 ≥ 0.5 fail -> not extend
supp(BC, neg) = BC occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail

supp(CA, pos) = CA occurs on the above table at pos / the number of sequence at pos
= 1 / 3 = 0.33 ≥ 0.5 fail -> not extend
supp(CA, neg) = CA occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail
supp(CB, pos) = CB occurs on the above table at pos / the number of sequence at pos
= 2 / 3 = 0.67 ≥ 0.5 ok
supp(CB, neg) = CB occurs on the above table at neg / the number of sequence at neg
= 2 / 2 =1 ≤ 0.5 fail -> extend
supp(CC, pos) = CC occurs on the above table at pos / the number of sequence at pos
= 1 / 3 = 0.33 ≥ 0.5 fail -> not extend
supp(CC, neg) = CC occurs on the above table at neg / the number of sequence at neg
= 0 / 2 =0 ≤ 0.5 fail

Step 3 :
Extend the possible previous items ABA, ABB, ABC, BAA, BAB, BAC, BBA, BBB, BBC, CBA, CBB,
CBC.

So on until there is no previous items can be extended

You might also like