SPM(Sequential Pattern Mining)

Sequential pattern mining is the mining of frequently appearing series events or subsequences as patterns. An instance of a sequential pattern is users who purchase a Canon digital camera are to purchase an HP color printer within a month.

A sequence is an ordered series of events. A sequence s is indicated {e1, e2, e3 … eJ} where event e1 appears before e2, which appears before e3, etc. The event is an itemset, and an itemset is a nonempty set of items. For example, I = {I1, I2,..., Ip}.

For example, in the case of user purchase information, an event defines a shopping trip in which a customer purchases items at a specific store. i.e., an unordered list of items that the customer purchased during the trip.

Sequential Pattern Mining (SPM) is one of the most well-known data mining activities that can be performed on sequences. Finding relevant subsequences within a set of sequences is the goal of this process. The interestingness of a subsequence can be evaluated based on Minimum Support.

Subsequences and Super sequences

A sequence is an ordered list of items, like <a1, a2, …, an>. If there are two sequences A = <a1,a2,a3…,an> and B = <b1,b2,b3,…bm>, then A is a subsequence of B if every element of A is a subset of a unique element of B, and the order should be maintained. If A is a subsequence of B, then B is a supersequence of A.

Example:

A = <(abcd),(gh),(yz)> and B = <(abcd),(efgh),(lmn),(xyz)>.

Here, as you can see, every element of A is a subset of at least one unique element of B (as indicated by the bold letters) and is in the correct order. Thus, A is the subsequence of B and B is the supersequence of A.

Sequence Database

A Sequence Pattern Mining Database is an ordered collection of elements or events. It is represented as a set of tuples <SID, S> where SID is the Sequence ID and S is the Sequence.

SID	S (sequence)
10	<a(abc)(ac)d(cf)>
20	<(ad)c(bc)(ae)>
30	<(ef)(ab)(df)cb>

Minimum Support

The minimum number of times a sequence should appear in the dataset for it to be considered frequent.

Example:

SID	S (sequence)
10	< a, (abc),(ac) >
20	< (ad), c >
30	< (ef), (ab) >

Minimum support is 2.

The following are the possible sequential patterns from the above sequence database along with support count.

Finding Length-1 Sequential Patterns:

Initial candidates:

– < a >, < b >, < c >, < d >, < e >, < f >

Scan database once, count support for candidates

Sequential Pattern	Support Count
< a >	3
< b >	2
< c >	2
< d >	1
< e >	1
< f >	1

From the above table, the 1-length candidates < d >, < e > and < f > don’t meet minimum support i.e. 2. Thus those are removed.

Finding Length-2 Sequential Patterns:

Candidates:

– < (a,a) >, < (a,b) >, < (a,c) >, < (b,b) >, < (b,c) >, < (c,c) >, < (b,a) >, < (c,a) >, < (c,b) >

Scan database one more time, collect support count for each length-2 candidate.

Sequential Pattern	Support Count
< (a,a) >	1
< (a,b) >	2
< (a,c) >	2
< (b,b) >	0
< (b,c) >	1
< (c,c) >	1
< (b,a) >	1
< (c,a) >	1
< (c,b) >	0

From the above table, the 2-length candidates < (a,a) >, < (b,b) >, < (b,c) >, < (c,c) >, < (b,a) >, < (c,a) > and < (c,b) > don’t meet minimum support i.e. 2. Thus those are removed.