CS计算机代考程序代写 DNA data mining algorithm decision tree database Data Mining (EECS 4412)

Data Mining (EECS 4412)
Sequential Pattern Mining
Parke Godfrey
EECS
Lassonde School of Engineering York University

Thanks to
Professor Aijun An
for creation & use of these slides.
2

Outline
Basic concepts of sequential pattern mining A Simplified Version of GSP Algorithm PrefixSpan
3

An Example Sequence Database
A sequence database consists of a set of sequences
A sequence is an ordered list of itemsets
Itemset: a set of items Items within an itemset are
unordered.
Element: an itemset in a sequence
4

Example of a Sequential Pattern
Database of an online book store Contains data sequences
Each sequence corresponds to a list of transactions by a given customer.
Each transaction contains the books selected by the customer in one order.
A sequential pattern
5% of customers bought “Foundation”, then “Foundation
and Empire” and “Ringworld”, then “Second Foundation”.
Usefulness
Making recommendations. Knowing what to stock.
5

Mining Sequential Patterns
Objective
Finding (interesting) frequent sequences from a sequence database.
Applications
Customer shopping sequence analysis
Web log analysis
DNA or protein analysis
Stock market analysis
Medical domain
Predict outset of a disease from a sequence of symptoms, etc.
Earthquake prediction etc.
6

Basic Concepts
A sequence áa1, a2, …, anñ is contained in (or is a subsequence of) another sequence áb1, b2, …, bmñ if there exist integers i1?
Frequent sequences (also called sequential patterns) sequences that satisfy a minimum support (min_sup).
Customer Id
Customer Sequence
1 2 3 4 5
á(30) (90)ñ
á(10 20) (30) (20 60 70)ñ á(30 50 70)ñ
á(30) (40 60 70) (90)ñ á(90)ñ
7

Sequential Pattern Mining
What is sequential pattern mining
Given a sequence database, find the set of frequent sequences that satisfy a minimum support (min_sup).
Algorithms
Initial Apriori-like algorithms (Agrawal and Srikant, 95)
AprioriAll, AprioriSome, and DynamicSome
GSP – an Apriori-like, influential mining method (Srikant and Agrawal, 96)
PrefixSpan (Pei, et al, 01)
SPADE (Zaki, 01)
Mining sequential patterns with constraints (Pei, et al, 02) etc.
8

Apriori Property
The Apriori property in sequential patterns:
Any nonempty subsequence of a frequent sequence must be frequent
If a sequence is infrequent, then none of its super-sequences is frequent.
i.e., if á(3) (4 5)ñ is infrequent, so are á(3) (4 5) (8)ñ and á(3 6) (4 5)ñ
9

GSP
GSP: Generalized Sequential Pattern Mining
Proposed in
R. Srikant and R. Agrawal. Mining Sequential Patterns: Generalizations and Performance Improvements. In Proc. of EDBT’96.
Can be downloaded from the course web site
GSP considers some time constraints and item taxonomy
More general than simply mining sequential patterns
10

A Simplified Version of GSP
GSP without the generalizations
Problem statement:
find all frequent sequences from a database of sequences
given a min_sup
Length of a sequence = number of items in the sequence
Length of <(a)(b)> is 2 Length of <(a b)> is 2 Length of <(a b) (c)> is 3
A length-k sequence is also called k-sequence.
11

General Description of Simplified GSP
Method
Take sequences in form of <(x)> as length-1 candidates
Scan database once, find L1, the set of length-1 sequential patterns
Let k=1; while Lk is not empty do
Form Ck+1, the set of length-(k+1) candidates from Lk;
If Ck+1 is not empty, scan database once, find Lk+1, the set of length-(k+1) sequential patterns
Let k=k+1;
12

Finding Length-1 Sequential Patterns
Initial candidates
<(a)>, <(b)>, <(c)>, <(d)>, <(e)>, <(f)>, <(g)>, <(h)>
Scan database once
count support for candidates
min_sup =40%
min_sup_count =2
Cand
Sup
<(a)>
3
<(b)>
5
<(c)>
4
<(d)>
3
<(e)>
3
<(f)>
2
<(g)>
1
<(h)>
1
Seq-id
Sequence
10
<(bd)(c)(b)(ac)>
20
<(bf)(ce)(b)(fg)>
30
<(ah)(bf)(a)(b)(f)>
40
<(be)(ce)(d)>
50
<(a)(bd)(b)(c)(b)(ade)>
13

Length-2 Candidate Generation
How to generate C2 from L1
Merge every pair of frequent length-1 sequences.
Merging two frequent length-1 sequences <(i1)> and <(i2)> will produce three candidate 2-sequences:
<(i1) (i2)> <(i2) (i1)> and <(i1 i2)> assuming that i1 is different from i2.
Every frequent length-1 sequence <(i)> can join with itself to produce <(i)(i)>.
14

Length-2 Candidates (Cont’d from the example on Slide 13)
Length of a sequence= the number of items







<(a)(a)>
<(a)(b)>
<(a)(c)>
<(a)(d)>
<(a)(e)>
<(a)(f)>

<(b)(a)>
<(b)(b)>
<(b)(c)>
<(b)(d)>
<(b)(e)>
<(b)(f)>

<(c)(a)>
<(c)(b)>
<(c)(c)>
<(c)(d)>
<(c)(e)>
<(c)(f)>

<(d)(a)>
<(d)(b)>
<(d)(c)>
<(d)(d)>
<(d)(e)>
<(d)(f)>

<(e)(a)>
<(e)(b)>
<(e)(c)>
<(e)(d)>
<(e)(e)>
<(e)(f)>

<(f)(a)>
<(f)(b)>
<(f)(c)>
<(f)(d)>
<(f)(e)>
<(f)(f)>
51 length-2 Candidates







<(ab)>
<(ac)>
<(ad)>
<(ae)>
<(af)>

<(bc)>
<(bd)>
<(be)>
<(bf)>

<(cd)>
<(ce)>
<(cf)>

<(de)>
<(df)>

<(ef)>

Without Apriori
property,
8*8+8*7/2=92
candidates
Apriori prunes
44.57% candidates
15