Pattern-based classification of demographic sequences

Pattern-Based Classification of Demographic Sequences
Dmitry I. Ignatov1, Danil Gizdatullin1, Ekaterina Mitrofanova1, Anna
Muratova1, Jaume Baixeries2
1National Research University Higher School of Economics, Moscow
2Universitat Politècnica de Catalunya, Barcelona
Intelligent Data Processing 2016, Barcelona
Ignatov et al. (HSE) Classification of Demographic Sequences IDP 2016 1 / 27

Possible life events
First job (job)
The highest education degree is obtained (education)
Leaving parents’ home (separation)
First partner (partner)
First marriage (marriage)
First child birth (children)
Break-up (parting)
... (divorce)

Data and problem statement
[Ignatov et al., 2015],[Blockeel et al., 2001]
Generation and Gender Survey (GGS): three waves panel data for 11
generations of Russian citizens starting from 30s
Binary classiﬁcation
1545 men
3312 women
Examples of sequential patterns
{education, separation}, {work}, {marriage}, {children} (m)
{work}, {marriage}, {children}{education} (f )
{partner}, {marriage, separation}, {children} (f )

Basic deﬁnitions
Texbooks of Han et al., Zaki & Meira, Aggarwal et al., etc
s = s1, ..., sk is the subsequence of s = s1, ..., sk (s s ) if
k ≤ k and there exist 1 ≤ r1 < r2 < ... < rk ≤ k such sj = srj for all
1 ≤ j ≤ k.
support(s, D) is the support of a sequence s in D, i.e. the number of
sequences in D such that s is their subsequence.
support(s, D) = |{s |s ∈ D, s s }|
s is a frequent closed sequence (sequential pattern) if there is no
s such that s s and
support(s, D) = support(s , D)

Example
Let D be a set of sequences:
Table: Dataset D.
s1 {a, b, c}{a, b}{b}
s2 {a}{a, c}{a}
s3 {a, b}{b, c}
I = {a, b, c} is the set of all items (atomic events)
{a, b}{b} belongs to s1 and s3 but it is missing in s2
supportD( {a, b}{b} ) = 2
{ {a} , {c} , {a}{c} , {a, b}{b} , {a, c}{a} } is the set of closed
sequences.

CAEP: Classiﬁcation by Aggregating Emerging Patterns
G. Dong et al., 1999
Growth Rate
growth rateD →D (X) =



suppD (X)
suppD (X)
if suppD (X) = 0
0 if suppD (X) = supp(X) = 0
∞ if suppD (X) = 0 and suppD (X) = 0
Class score
score(s, C) =
e⊆s,e∈E(c)
growth rateC (e)
growth rateC (e) + 1
· suppc(e)

CAEP: Classiﬁcation by Aggregating Emerging Patterns
Score normalization
normal score(s, C) =
score(s, C)
median({growth rateC (ei )})
Classiﬁcation rule
class(s) =



C1, if normal score(s, C1) > normal score(s, C2)
C2, if normal score(s, C1) < normal score(s, C2)
undetermined if normal score(s, C1) = normal score(s, C2)

Gapless prefix-based sequential patterns
s = s1, ..., sk is a gapless prefix-based subsequence of
s = s1, ..., sk (s∗ = s ) if k ≤ k and ∀i ∈ k : si = si .
Support of gapless prefix-based sequences
Let T be a set of sequences.
support(s, T) =
|{s |s ∈ T, s∗ = s }|
|T|

Gapless sequential patterns
Let 0 < minSup ≤ 1 be a minimal support parameter and D is a set
of sequences then searching for prefix-based gapless sequential
patterns is the task of enumeration of all prefix-based gapless
sequences s such that support(s, D) ≥ minSup. Every sequence s
with support(s, D) ≥ minSup is called a prefix-based gapless
sequential pattern.
Prefix-based gapless sequential pattern (PGSP) p is called closed if
there is no PGSP d of greater of equal support such that d = p∗.

Gapless sequential patterns
Example
Table: D is a set of sequences.
s1 {a}{b}{d}
s2 {a}{b}{c}
s3 {a, b}{b, c}
s = {a}{b}
I = {a, b, c} is the set of all items (atomic events)
s1 = s∗; s2 = s∗
s3 = s∗
SuppD(s) =
2
3
{a}{b} is closed, {a} is not closed.

Pattern Structures
Ganter & Kuznetsov, 2001
(S, (D, ), δ) is a pattern structure
S is a set of objects, D is a set of their their possible descriptions
δ(g) is the description of g from S
Galois connection is given by operator as follows:
A :=
g∈A
δ(g) for A ⊆ S
d := {s ∈ S|d δ(g)} for d ∈ D
For two sequences may result in their largest common preﬁx
subsequence

Pattern concepts
A pair (A, d) is called a pattern concept of a pattern structure
(S, (D, ), δ) if
1 A ⊆ S
2 d ∈ D
3 A = d
4 d = A

Pattern Structures
Example
s1 : a, b, c
s2 : a, b, c
s3 : a, b, d
Tree
0
a(3)
b(3)
c(2) d(1)
Pattern concepts (PCs)
({s1, s2, s3}, a, b ); ({s1, s2}, a, b, c )
({s1}, a, b, c ) is not a PC; ({s3}, a, b, d )

Pattern-based JSM-hypotheses
[Finn, 1981], [Kuznetsov, 1993], [Ganter et al, 2004]
Positive, negative and undetermined pattern structures
K⊕ = (S⊕, (D, ), δ⊕)
K = (S , (D, ), δ )
There is a pattern structure of undetermined examples:
Kτ = (Sτ , (D, ), δτ )
Hypothesis
A hypothesis is a pattern intent that belongs to examples from a ﬁxed
class only
A pattern intent h is a positive hypothesis (dually for negative hypotheses)
if
∀s ∈ S (s ∈ S⊕) : h s (h s⊕
)

Hypotheses generation: An example
Sequential classiﬁcation rules
s1 : a, b, c - class 0
s2 : a, b, c - class 0
s3 : a, b, d - class 1
Preﬁx-tree
0
a(2; 1)
b(2; 1)
c(2; 0) d(0; 1)
Hypotheses
{a}, {b}, {c} is a hypothesis of class 0
{a}, {b}, {d} is a hypothesis of class 1

Classiﬁcation via hypotheses
class(gτ ) =



positive if ∃h⊕, h⊕ δ(gτ ) and h , h δ(gτ )
negative if h⊕, h⊕ δ(gτ ) and ∃h , h δ(gτ )
undetermined if ∃h⊕, h⊕ δ(gτ ) and ∃h , h δ(gτ )
undetermined if h⊕, h⊕ δ(gτ ) and h , h δ(gτ )

Emerging patterns based on pattern structures
Growth Rate
GrowthRate(g, K⊕, K ) =
SupK⊕ (g)
SupK (g)
Emerging patterns
A pattern is called emerging pattern if its growth rate is greater than or
equal to Θmin
GrowthRate(g, K⊕, K ) > Θmin

Emerging patterns for classiﬁcation
s is a new object
normal score⊕(s) =
p∈P⊕
GrowthRate(p, K⊕, K )
median(GrowthRate(P⊕))
: p s
normal score (s) =
p∈P GrowthRate(p, K , K⊕)
median(GrowthRate(P ))
: p s
Classiﬁcation via emerging patterns
class(s) =



positive if normal score⊕(s) > score (s)
negative if normal score⊕(s) < score (s)
undetermined if normal score⊕(s) = normal score (s)

Classification algorithm for gapless prefix-based sequential
patterns
1 Build the prefix tree for the input sequences.
2 For each tree node calculate its Growth Rate.
3 For every new sequence traverse the tree and compute the Score for
each class.
4 Compare the Score value for different classes and classify the new
sequence.

Execution example
Input sequences
class 0 : { {a}{b}{c} , {b}{a}{c} , {b}{a}{c} , {b}{c} }
class 1 : { {a}{c}{b} , {b}{c}{a} , {b}{c}{a} }
Preﬁx tree
0
a(1; 1)
b(1; 0)
c(1; 0)
c(0; 1)
b(0; 1)
b(2; 2)
a(2; 0)
c(2; 0)
c(1; 2)
a(0; 2)

Counting Growth Rate
0
a(0.75; 1.33)
b(∞; 0)
c(∞; 0)
c(0; ∞)
b(0; ∞)
b(0.75; 1.33)
a(∞; 0)
c(∞; 0)
c(0.38; 2.67)
a(0; ∞)
New sequence
{b}; {c}; {a} −???
Score0 = 0
Score1 = 2.67 + ∞ = ∞

Comparison of closed and non-closed patterns
Figure: TPR vs FPR for closed and non-closed patterns

Experiments and results
Figure: TPR-FPR for classiﬁcation via gapless preﬁx-based patterns

Interesting patterns (women)
( {work, separation}, {marriage}, {children}, {education} , [inf , 0.006])
( {separation, partner}, {marriage} , [inf , 0.006])
( {work, separation}, {marriage}, {children} , [inf , 0.008])
( {work, separation}, {marriage} , [inf , 0.009])

Interesting patterns (men)
( {education}, {marriage}, {work}, {children}, {separation} , [10.6, 0.006])
( {education}, {marriage}, {work}, {children} , [12.7, 0.007])
( {educ}, {work}, {part}, {mar}, {sep}, {ch} , [10.6, 0.006])

Conclusion
1 We have studied several pattern mining techniques for demographic
sequences including pattern-based classification in particular.
2 We have fitted existing approaches for sequence mining of a special
type (gapless and prefix-based ones).
3 The results for different demographic groups (classes) have been
obtained and interpreted.
4 In particular, a classifier based on emerging sequences and pattern
structures has been proposed.

Conclusion
Thank you!
Questions?

Pattern-based classification of demographic sequences

Recommended

More Related Content

What's hot (20)

Viewers also liked (18)

Similar to Pattern-based classification of demographic sequences (20)

More from Dmitrii Ignatov (11)

Recently uploaded (20)

Pattern-based classification of demographic sequences