September 17, 2015
FIT 2015

統計的パターンマイニング
Significant Pattern Mining
大阪大学 産業科学研究所
さきがけ研究者

杉山 麿人

Mahito Sugiyama
1/40Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

2/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

2/40

Itemset Mining• Find interesting combinatorial patterns from massive data
Database

3/40

Itemset Mining• Find interesting combinatorial patterns from massive data
Database
Itemset(combinationof colors)

Support: 6

Support: 3

3/40

Subgraph Mining• Find interesting combinatorial patterns from massive data
Database

4/40

Subgraph Mining• Find interesting combinatorial patterns from massive data
Database
Subgraph

Support: 4

Support: 2

4/40

Apriori on Itemset LatticeTransaction
database

ID 1:
ID 2:
ID 3:
ID 4:
ID 5:
ID 6:
ID 7:
ID 8:
5/40

Apriori on Itemset LatticeTransaction
database

Itemset lattice

Support: 8

ID 1:
ID 2:
ID 3:

7

7

5

ID 4:
ID 5:

6

4

4

ID 6:
ID 7:
ID 8:

3
Apriori principle:
Support is monotonically decreasing

5/40

Apriori on Itemset LatticeTransaction
database

Itemset lattice

Support: 8

ID 1:
ID 2:
ID 3:

7

Frequent
5 itemsets(minsup
σ = 5)

7

ID 4:
ID 5:

6

4

4

ID 6:
ID 7:
ID 8:

3
Apriori principle:
Support is monotonically decreasing

5/40

Discriminative Itemset Mining• Find discriminative patterns from supervised data
– e.g. Genome-wide association studies in Bioinformatics

Negative

Positive

Database

6/40

Discriminative Itemset Mining• Find discriminative patterns from supervised data
– e.g. Genome-wide association studies in Bioinformatics

Positive

Database
Discriminative
Itemset

Negative

Support: (4, 2)

Support: (3, 1)

6/40

Discriminative Subgraph Mining• Find discriminative patterns from supervised data
– e.g. Drug discovery

Negative

Positive

Database

7/40

Discriminative Subgraph Mining• Find discriminative patterns from supervised data
– e.g. Drug discovery

Positive

Database
Discriminative
Subgraph

Negative

Support: (4, 0)

Support: (0, 2)

7/40

Agenda• In discriminative pattern mining:
1. How to measure the discriminability of patterns?
2. How to enumerate all discriminative patterns?

8/40

Agenda• In discriminative pattern mining:
1. How to measure the discriminability of patterns?
2. How to enumerate all discriminative patterns?
• Answer to 1:– Compute the p-value via statistical hypothesis testing– Discriminative pattern ⟺ (Statistically) Significant pattern• Answer to 2:– Integrate evaluation of discriminability andenumeration of patterns

8/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

9/40

Computing p-value of Pattern• Given positive and negative sets of transactions X , X ′– ∣X ∣ = n , ∣X ′ ∣ = n ′ ( n ≤ n ′ )• The p-value of each pattern H is determined by
the Fisher’s exact test
– x = ∣{ X ∈ X ∣ H ⊆ X }∣𝒳 (Pos.)Occ.

Non-occ.

Total

x

n–x

n

n’ – x’𝒳’ (Neg.) x’x + x’ (n – x)Total=σ
+ (n’ – x’)
Support

n’

?

1.0
x/n
x’ / n’n + n’
0

𝒳
Pos.

𝒳’
Neg.

10/40

Fisher’s Exact Test
• The probability q(x) of obtaining x and x ′ is given by
the hypergeometric distribution:
′

′

n+n
n n
q(x) = ( x )( x ′ )/( x + x ′ )𝒳 (Pos.)Occ.

Non-occ.

Total

x

n–x

n

n’ – x’𝒳’ (Neg.) x’x + x’ (n – x)Total=σ
+ (n’ – x’)
Supportn’
n + n’

Probability q(X)0.3

p-value0xmin= max{0, x + x’ - n’}xxmax= min{x + x’, n}11/40

Hypothesis Test for Each Pattern
Alternative hypothesis Null hypothesis
is trueis true
Declaredsignificant( p-value < α )True Positive

False Positive(Type I Error)

Declared
non-significant

False Negative(Type II Error)

True Negative

Null hypothesis:

The occurence of the pattern is
independent from classes
Alternative hypothesis: The occurence of the pattern is
associated with classes

12/40

Hypothesis Test for Each Pattern
Alternative hypothesis Null hypothesis
is trueis true
Declaredsignificant( p-value < α )True Positive

False Positive(Type I Error)

Declared
False Negative
True Negative
non-significant(Type II Error)
Binary desicion (significant or not) via
the user specified threshold α
The occurence of the pattern is
Null hypothesis:
independent from classes
Alternative hypothesis: The occurence of the pattern is
associated with classes

12/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

13/40

Multiple Testing

Pattern:Occ. Non-occ. Total
Positive 4
Negative 2

0
2

4
4

Total

2

8

6

Fisher’s exact test: p-value = 0.429

14/40

Multiple Testing

Pattern:
Pattern:Occ. Non-occ. Total

Positive
Occ. 3Non-occ.1 Total 4
Negative 1
Positive4
0 3 4 4
Total 2 4 2 4 4 8
Negative
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

14/40

Multiple Testing

Pattern:
Pattern:
Pattern:Occ. Non-occ. Total

Positive
Occ. 2Non-occ.2 Total 4
Negative 22
4
Positive
Occ. 3Non-occ.1 Total 4
Total 1 4 3 4 4 8
Negative
Positive 40
4

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

14/40

Multiple Testing
Pattern:Occ. Non-occ. Total
Positive

Pattern:
Pattern:
Pattern:

4
Negative 3

0
1

4
4

Total

4

8

7

Fisher’s exact test: p-value = 1.0
Non-occ.
Occ.
Total

Positive
Occ. 2Non-occ.2 Total 4
Negative 22
4
Positive
Occ. 3Non-occ.1 Total 4
Total 1 4 3 4 4 8
Negative
Positive 40
4

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

14/40

Multiple Testing
Pattern:Occ. Non-occ. Total
Positive

Pattern:
Pattern:
Pattern:

4
Negative 3

0
1

4
4

Total

4

8

7

Task: Enumerate all
significant patterns

Fisher’s exact test: p-value = 1.0
Non-occ.
Occ.
Total

Positive
Occ. 2Non-occ.2 Total 4
Negative 22
4
Positive
Occ. 3Non-occ.1 Total 4
Total 1 4 3 4 4 8
Negative
Positive 40
4

TotalFisher’s
4 p-value
Negative
2 4 exact
2 test:
4 8 = 1.0
TotalFisher’s6 exact test:
2 p-value
8 = 0.486
Fisher’s exact test: p-value = 0.429

Massive number of patterns(Combinatorial explosion!)

14/40

Multiple Testing Correction• In each test, [probability of having a false positive] ≤ α• If we repeat m tests, αm patterns can be false positives– Too many if m is large!
– Example in itemset mining:
100000◦ For 100000 items, #patterns = 2◦ Set significance level α = 0.01
10000030101◦ Number of false positives: 0.01 ⋅ 2
= 10

15/40

Multiple Testing Correction• In each test, [probability of having a false positive] ≤ α• If we repeat m tests, αm patterns can be false positives– Too many if m is large!
– Example in itemset mining:
100000◦ For 100000 items, #patterns = 2◦ Set significance level α = 0.01
10000030101◦ Number of false positives: 0.01 ⋅ 2= 10• FWER (family-wise error rate): Probability of having
more than one false positives among all patterns– One of the standard criteria in multiple testing– FWER = 1 − (1 − α)m if patterns are independent
15/40

Controlling the FWER
• FWER = Pr(FP > 0)
– FP: Number of false positives• To achieve FWER = α , change the significance levelfor each pattern from α to δ (δ ≤ α )– δ : corrected significance level

16/40

Controlling the FWER
• FWER = Pr(FP > 0)
– FP: Number of false positives• To achieve FWER = α , change the significance levelfor each pattern from α to δ (δ ≤ α )– δ : corrected significance level• Objective: Optimize (maximize) δ∗δ = argmax FWER(δ) s.t. FWER(δ) ≤ αδ– FWER(δ): FWER at corrected significance level δ◦ Cannot be evaluated in closed form (simple but not easy!)∗– Bonferroni correction is popular: δBon
= α/m
16/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

17/40

Minimum Achievable p-value Ψ(σ)• Consider the minimum achievable p-value Ψ(σ) ofa pattern H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣– Ψ(σ) = min{ p(x) ∣ x min ≤ x ≤ x max }′◦ x min = max{0, σ − n }, x max = min{σ, n}𝒳 (Pos.)Occ.

Non-occ.

Total

x

n–x

n

n’ – x’𝒳’ (Neg.) x’x + x’ (n – x)Total=σ
+ (n’ – x’)
Supportn’
n + n’

Probability q(X)0.3
Minimumachievablep-value0xmin= max{0, f(H) – n’}xxmax= min{f(H), n}

18/40

Computing Ψ(σ)• Consider the minimum achievable p-value Ψ(σ) ofa pattern H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣′nn+n
Ψ(σ) = (σ ) / ( σ )Occ.

Non-occ.

Total

𝒳 (Pos.) σn–σn𝒳’ (Neg.) 0

n’

n’

σ

(n – σ)+ n’

n + n’

Total

Most biased case (σ < n)Probability q(X)0.3
Minimumachievablep-value0xmin= max{0, f(H) – n’}xxmax= min{f(H), n}

19/40

Testability• Consider the minimum achievable p-value Ψ(σ) ofa pattern H for its support σ = ∣{ X ∈ X ∪ X ′ ∣ H ⊆ X }∣′nn+n
Ψ(σ) = (σ ) / ( σ )• Tarone (1990) pointed out (and Terada et al. (2013) revisited):
For a pattern H, if Ψ(σ) is larger than the significancethreshold, this is untestable and we can ignore it– Significance threshold = α / [# testable patterns]
20/40

Number of patterns
whose support is σ

Finding Testable Patterns

Support σ

21/40

Number of patterns
whose support is σ

Finding Testable Patterns

Ψ(σ1) < α /?
Testablepatterns?

σ1

Support σ

22/40

Number of patterns
whose support is σ

Finding Testable Patterns

Ψ(σ2) < α /?
Testablepatterns?

σ2

Support σ

22/40

Number of patterns
whose support is σ

Finding Testable Patterns

Ψ(σ3) < α /?

Testablepatterns?

σ3

Support σ

22/40

Probability

Finding Testable Patterns

Minimum achievablep-value Ψ(σ)

Solution#patterns
whose
αsupport ≥ σSupport σ

23/40

State-of-the-art(Itemset)(Speed-up)

LAMP

LAMP ver.2[Terada et al.
PNAS 2013][Minato et al. ECML 2014](Subgraph, Speed-up)

Testability on
subgraphs[Sugiyama et al. SDM 2015]

FastWY[Terada et al.
BIBM 2013](Permutation test)

Testability
Permutation(Speed-up +Permutation test +Itemset +Subgraph)

WestfallYoung light[Llinares-López et al.
KDD 2015](Interval)

FAIS (FAIS-WY)[Llinares-López et al.
ISMB 2015]24/40

Number of patterns
whose support is σ

How to Find Testable Patterns?

Ψ(σ3) < α /?

Testablepatterns?

σ3

Support σ

25/40

Number of patterns
whose support is σ

How to Find Testable Patterns?

< α / Ψ(σ3) ?
Testablepatterns?

σ3This is the number of“frequent patterns”
Support σ

25/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)

1

5

10

Support σ
26/40

LAMP ver.2 [Minato et al. ECML PKDD 2014]# of patterns
Increment minsup σ in pattern miner
if # of patterns detected so far
exceeds α / Ψ(σ)
Pruned untestable patterns
Testable patterns
δ = α / # testable patterns
1

5

10

Support σ
26/40

# Testable Patterns in Subgraph Mining
Correction factor

PTC(MR)
106

107
105

104

103

102
5

Correction factor

MUTAG

109

10
15 Limitless
NCI1
108

107
105
103

107
106
105
104

D&D

109
108
107
106
105

5

10
15 Limitless
NCI167109

5

10
15 Limitless
NCI220107
Bonferroni 105
Testable
103

5
10
15
5
10
15 Limitless
510
15 Limitless
Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraph nodes

from [Sugiyama et al. SDM2015]27/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

28/40

FWER Is Still Too Low!

Empirical FWER

Empirical FWER

PTC(MR)

MUTAG

0.03

0.015

0.02

0.010

0.01

0.005

0

0

0.03

5

10
15 Limitless
NCI1

5

D&D

0.05
0.04
0.03
0.02
0.01
0
10
15 Limitless
NCI167

0.04

0.04

0.03

0.01

0.01

0.03
Bonferroni
0.02
Testable
0.01

0

0

0

0.02

0.02

5

10
15 Limitless
NCI2205
10
15 Limitless
510
15 Limitless
510
15 Limitless
Max. size of subgraph nodes Max. size of subgraph nodes Max. size of subgraph nodes

from [Sugiyama et al. SDM2015]29/40

Take Dependencies into Account• Problem: Dependencies between patterns are notconsidered• Solution: Permutation test
– Repeat random permutation of class labels (103 ∼ 104 times)– Get the null distribution of p-values– The optimal correction factor can be obtained

30/40

State-of-the-art(Itemset)(Speed-up)

LAMP

LAMP ver.2[Terada et al.
PNAS 2013][Minato et al. ECML 2014](Subgraph, Speed-up)

Testability on
subgraphs[Sugiyama et al. SDM 2015]

FastWY[Terada et al.
BIBM 2013](Permutation test)

Testability
Permutation(Speed-up +Permutation test +Itemset +Subgraph)

WestfallYoung light[Llinares-López et al.
KDD 2015](Interval)

FAIS (FAIS-WY)[Llinares-López et al.
ISMB 2015]

31/40

Westfall-Young Permutation
1. Randomly permute class labels
2. Compute p-values for all patterns using the permutedclass labels
3. Find the minimum p-value p min among them
– FP > 0 ⟺ p min < δ◦ FP: Number of false positives
12h
4. Repeat steps 1 to 3 h times and obtain p min , p min , . . . , p mini– FWER(δ) ≈ ∣{ i ∶ p min≤ δ }∣ / h

5. δ

∗

1
2
h
is the α -quantile of p min , p min , . . . , p min

32/40

Westfall-Young Permutation

p12
p22
p32

p13
p23
p33

...
...
...

p1m
p2m
p3m

...

...

...

...

Permutation
...

h

p11
p21
p31

...

1
2
3

Sort andfind α-quantile
α
p1min

...

Patterns (Hypotheses)
H1
H2
H3 ...
Hm

ph1

ph2

ph3

...

phm

phmin

p2min
p3min

33/40

Using Support for Estimating FWER

p22
p32

p23
p33

...
...

p2m
p3m

p2min
p3min

...

...

...

...

...

Permutation
...

h

p21
p31

...

1
2
3

Patterns (Hypotheses)
SupportH1
H2
H3 ...
Hm
Sort andσ1 ≤ σ2 ≤ σ3 ≤ ... ≤ σmfind α-quantileα
p11 p12 p13 ... p1m
p1min

ph1

ph2

ph3

...

phm

phmin
34/40

Estimating FWER

p12
p22
p32

p13
p23
p33

...
...
...

p1m
p2m
p3m

p1min
p2min
p3min

...

...

...

...

Permutation
...

h

p11
p21
p31

...

1
2
3

...

Patterns (Hypotheses)
SupportH1
H2
H3 ...
Hm
σ1 ≤ σ2 ≤ σ3 ≤ ... ≤ σm

ph1

ph2

ph3

...

phm

phmin

Ψ(σ)

Estimator of FWER = |{i : pimin ≤ Ψ(σ)}| / h
35/40

Estimating FWER

p12
p22
p32

p13
p23
p33

...
...
...

p1m
p2m
p3m

p1min
p2min
p3min

...

...

...

...

Permutation
...

h

p11
p21
p31

...

1
2
3

...

Patterns (Hypotheses)
SupportH1
H2
H3 ...
Hmσσ1 ≤ σ2 ≤ σ3 ≤ ... ≤ σm

ph1

ph2

ph3

...

phm

phmin

Ψ(σ)

Estimator of FWER = |{i : pimin ≤ Ψ(σ)}| / h
35/40

“Westfall-Young light”[Llinares-López et al. KDD’15]
i• Precompute h permuted labels; σ ← 1; p min←1• Westfall-Young light does the following whenevera miner (like LCM) finds a new frequent pattern H:– for i ← 1 to h do:i◦ p ← the p-value of H for i th permutationiii◦ p min ← min{p min , p }i– FWER ← ∣{ i ∶ p min≤ Ψ(σ) }∣ / h– while FWER > α do:◦ σ ← σ + 1 // σ is the minimum supporti◦ FWER ← ∣{ i ∶ p min ≤ Ψ(σ) }∣ / h– Go children of H

36/40

FWER in Itemset Mining
BmsWebview

T40I10D100K

from [Llinares-López et al. KDD2015]

37/40

FWER in Subgraph Mining
ENZYMES

NCI220from [Llinares-López et al. KDD2015]38/40

Outline• (Discriminative) Pattern mining• Statistical hypothesis testing of patterns• Multiple hypothesis testing in pattern mining• Testable patterns• Permutation testing in pattern mining• Conclusion

39/40

Conclusion• The area of significant pattern mining is emerging– Find statistically significant combinatorial patterns
while controlling false positive rate

• Pattern mining, a classical yet central topic in data mining,can be enriched by introducing statistical assessment– Can be applied in scientific fields such as biology

40/40

Appendix

A-1/A-5

Papers about Testability• Tarone, R.E.:
A modified Bonferroni method for discrete data
Biometrics (1990)• [LAMP] Terada, A., Okada-Hatakeyama, M., Tsuda, K., Sese, J.:
Statistical significance of combinatorial regulations,
Proc. Natl. Acad. Sci. USA (2013).
• [LAMP ver.2] Minato, S., Uno, T., Tsuda, K., Terada, A., Sese, J.:
Fast Statistical Assessment for Combinatorial Hypotheses
Based on Frequent Itemset Mining
ECML PKDD 2014
• Sugiyama, M., Llinares-López, F., Kasenburg, N., Borgwardt, K.:
Significant Subgraph Mining with Multiple Testing Correction,
SIAM SDM 2015
A-2/A-5

Papers about Permutation Testing• Westfall, P. H. and Young, S. S.
Resampling-based multiple testing: Examples and methods
for p-value adjustment
John Wiley & Sons (1993)• [FastWY] Terada, A. and Tsuda, K. and Sese, J.:
Fast Westfall-Young permutation procedure for combinatorial
regulation discovery, IEEE BIBM 2013
• [Westfall-Young light] Llinares-López, F., Sugiyama, M.,
Papaxanthos, L., Borgwardt, K.:
Fast and Memory-Efficient Significant Pattern Mining via
Permutation Testing, ACM SIGKDD 2015
• [FAIS-WY] Llinares-López, F., et al.:Genome-Wide Detection of Intervals of Genetic
Heterogeneity Associated with Complex Traits, ISMB 2015
A-3/A-5

Frequent Itemset Miners• [Apriori] Agrawal, R. and Imieliński, T. and Swami, A.:
Mining association rules between sets of items in large
databases,
ACM SIGMOD 1993
• [FP-Growth] Han, J. and Pei, J. and Yin, Y.:
Mining frequent patterns without candidate generation,
ACM SIGMOD 2000
• [LCM] Uno, T. and Asai, T. and Uchida, Y. and Arimura, H.:
An efficient algorithm for enumerating closed patterns intransaction databases,
DS 2004(won FIMI’04 competition)

A-4/A-5

Frequent Subgraph Miners• [AGM] Inokuchi, A. and Washio, T. and Motoda, H.:
An Apriori-Based Algorithm for Mining Frequent
Substructures from Graph Data, PKDD 2000
• [gSpan] Yan, X. and Han, J.:
gSpan: Graph-based substructure pattern mining,
ICDM 2002• [GASTON] Nijssen, S. and Kok, J. N.:
A Quickstart in Frequent Structure Mining Can Make a
Difference, KDD 2004
• (comparison) Wörlein, M. and Meinl, T. and Fischer, I. andPhilippsen, M.
A Quantitative Comparison of the Subgraph Miners MoFa,
gSpan, FFSM, and Gaston, PKDD 2005
– We used GASTON as it is the fastest
A-5/A-5