November 17, 2017

Supervised Pattern Mining
Data Mining 04 (データマイニング)

Mahito Sugiyama (杉山麿人)

Today’s Outline• Pattern mining with class labels (supervision)– Various measures• Significant pattern mining– Statistical tests– Testable patterns– Controlling the FWER (Family-Wise Error Rate) by
Tarone’s testability trick

1/24

Itemset Mining• Find interesting combinatorial patterns from massive data

2/24

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

Support: 6

Support: 3

2/24

Itemset Mining (Binary Representation)• Find interesting combinatorial patterns from massive data
ID1 1ID2 1
ID3 1ID4 1
ID5 1
ID6 0
ID7 1
ID8 1111111010101011
1Itemset(combinationof colors)

Support: 6Support: 33/24

Itemset Mining (Binary Representation)• Find interesting combinatorial patterns from massive data
ID1 1ID2 1ID3 1
ID4 1
ID5 1
ID6 0
ID7 1
ID8 1111111010
10
10111

Itemset(combinationof colors)

Support: 6

Support: 33/24

Subgraph Mining• Find interesting combinatorial patterns from massive data

4/24

Subgraph Mining• Find interesting combinatorial patterns from massive data
Subgraph

Support: 4

Support: 2

4/24

Supervised Itemset Mining

Positive• Find discriminative patterns from supervised data
Discriminative
itemset

Negative

Support: (4, 2)

Support: (3, 1)

5/24

Supervised Subgraph Mining

Positive• Find discriminative patterns from supervised data
Discriminative
subgraphs

Negative

Support: (4, 0)

Support: (0, 2)

6/24

Contingency Table
Occurrence

Non-occurrence

Total

Positive

suppC (x)∣C∣ − suppC (x)∣C∣

NegativesuppC̄ (x)∣C̄∣ − suppC̄ (x)

∣C̄∣

Total

supp(x)= suppC (x) + suppC (x)∣D∣ − supp(x)

∣D∣

7/24

Contingency Table
Occurrence

Non-occurrence

Total

Positive

n11

n12

c1

Negative

n21

n22

c2

Total

ss′

d

7/24

Various Measures• Confidence: n11 /d• Growth rate (relative risk): n11 /n21
• Support difference (risk difference): n11 − n21• Mutual information:
n11 /dn12 /dn21 /dn22 /dn11n12n21
n22log+log+log+log2′22dddd
c1 s/dc1 s /dc2 s/dc2 s ′ /d 2
• Subgroup discovery measure (weighted relative accuracy):(c1 /d) ((n11 /c1 ) − (c1 /d))

8/24

Computing p-value of Pattern• Given positive and negative sample sets C, C̄ such that D = C ∪ C̄• The p-value of each pattern s is assessed by the Fisher’s exact test
Occ.
C (Pos.)Non-occ. Total?

1.0
suppC(s) / |C|

suppC(s) |C|–suppC(s) |C|C (Neg.) suppC(s) |C|–suppC(s) |C|
D (Total) supp(s) |D|–supp(s)suppC(s) / |C||D|
0CCPos.

Neg.

9/24

Fisher’s Exact Test• Probability q(suppC (s)) is given by hypergeometric distribution:
∣C∣
∣C̄∣
∣D∣
q(suppC (s)) = ()()/()
supp(s)suppC (s) suppC̄ (s)C (Pos.)Non-occ. Total

suppC(s) |C|–suppC(s) |C|C (Neg.) suppC(s) |C|–suppC(s) |C|
D (Total) supp(s) |D|–supp(s)|D|Probability q

Occ.

0.3

0p-value

suppC(s)10/24Hypothesis Test for Each Pattern
Alternative hypothesis
is true

Null hypothesis
is true

Declared significant(p-value < α)True Positive

False Positive(Type I Error)

Declared
non-significant

False Negative(Type II Error)

True Negative

Occurence of pattern is independent from classes
Null:
Alternative: Occurence of pattern is associated with classes 11/24

Significant Pattern (Itemset) Mining

Positive• Find discriminative patterns from supervised dataSignificant
itemset

Negative

Support: (4, 2)
p-value = 0.214

Support: (3, 1)
p-value = 0.243

12/24

Significant Subgraph Mining

Positive• Find discriminative patterns from supervised dataSigniciant
subgraphs

Negative

Support: (4, 0)
p-value = 0.0143
Support: (0, 2)
p-value = 0.214

13/24

Challenges and Solutions of SPM
1. (Computational) How to check all patterns
with avoiding combinatorial explosion?
2. (Statistical) How to measure the statistical association(i.e. p-value) with correcting for multiple testingwith avoiding combinatorial explosion?
• Answer: Tarone’s trick + Apriori principle– The Tarone’s trick to define patterns that are irrelevant– The Apriori principle to efficiently prune such patterns using
the partial order structure of patterns
13/24

Timeline
1990

2000

2010

Tarone’s testability
Itemset mining
Subgraph mining
Data mining
in computer science2017
Significantpattern mining
LAMP
WY lightFACS
FastCHM
14/24

Summary of SPM Methods(itemset)

LAMP[Terada et al.
PNAS 2013](speed-up)

LAMP ver.2[Minato et al. ECML 2014](subgraph, speed-up)

Testability on
subgraphs[Sugiyama et al. SDM 2015]

FastWY(categorial covariate)

FACS(speed-up +[Papaxanthos et al.
permutation test + NIPS 2016]
itemset + subgraph)

WestfallYoung light[Llinares-López et al.
KDD 2015][Terada et al.
BIBM 2013](interval)(interval +categorial covariate)(permutation test)

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

FastCHM[Llinares-López et al.
Bioinformatics 2017]

15/24

Multiple Testing

Occ. Non-occ. Total
Positive 4
Negative 2Total
6022448

Fisher’s exact test: p-value = 0.429

16/24

Multiple Testing

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

16/24

Multiple Testing
Occ. Non-occ. Total
Positive 404
Negative 3
14Total748
Non-occ.
Occ.
Fisher’s
exactTotaltest: p-value = 1.0

Positive
31 Total 4Occ. Non-occ.
Negative
Positive
4 1 0 3 4 4Total 2 4 2 4 4 8
Negative

Total exact
Fisher’s
6 test: p-value
28= 0.486
Fisher’s exact test: p-value = 0.429

16/24

Multiple Testing
Occ. Non-occ. Total
Positive 404
Negative 314Total
748
Non-occ.
Occ.
Fisher’s
exactTotal
test: p-value = 1.0

Positive
31 Total 4Occ. Non-occ.
Negative
Positive
4 1 0 3 4 4Total 2 4 2 4 4 8
Negative

Total exact
Fisher’s
6 test: p-value
28= 0.486
Fisher’s exact test: p-value = 0.429

Task: Enumerate all
significant patterns
while controlling
the FWER

Massive number of(infinitely many) patterns(Combinatorial explosion!)
16/24

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! For example in itemset mining:
100000◦ For 100000 items, #patterns = 2◦ Set significance level α = 0.01
10000030101◦ Number of false positives: 0.01 ⋅ 2
= 10

17/24

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! For 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– FWER = 1 − (1 − α)m if patterns are independent
17/24

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

18/24

Controlling the FWER
• FWER = Pr(FP > 0)
– FP: Number of false positives• To achieve FWER = α , change the significance level for each patternfrom α to δ (δ ≤ α ), the corrected significance level• Objective: Maximize FWER(δ) subject to FWER(δ) ≤ α– FWER(δ): FWER at corrected significance level δ◦ Cannot be evaluated in closed form (simple but not easy!)∗– Bonferroni correction is popular: δBon= α/m
18/24

Minimum Achievable p-value Ψ(σ)• Consider the minimum achievable p-value Ψ(s) of a pattern sfor its support supp(s)C (Pos.)C (Neg.)Non-occ. Total

supp(s) |C|–suppC(s) |C|
0|C|–suppC(s) |C|

D (Total) supp(s) |D|–supp(s)|D|Probability q

Occ.

0.3

Minimumachievablep-value

0suppC(s)Most biased case that achieves the minium p-value
19/24

Computing Ψ(σ)∣C∣
∣D∣
Minimum achievable p-value Ψ(s) = ()/()
supp(s)supp(s)C (Pos.)C (Neg.)Non-occ. Total

supp(s) |C|–suppC(s) |C|
0|C|–suppC(s) |C|

D (Total) supp(s) |D|–supp(s)|D|Probability q

Occ.

0.3

Minimumachievablep-value

0suppC(s)Most biased case that achieves the minium p-value
20/24

Tarone’s Testability Trick∣C∣∣D∣
Minimum achievable p-value Ψ(s) = ()/()
supp(s)supp(s)• Tarone (1990) pointed out (and Terada et al. (2013) revisited):
For a pattern s with its support supp(s), if the minimum achievablep-value Ψ(s) is larger than the significance threshold, this isuntestable and we can ignore it– Significance threshold = α / [# testable subgraphs]– Untestable subgraphs can never be significant
21/24

Number of patterns
whose support is σ

Finding Testable Patterns

Support σΨ(σ) decreases
22/24

Number of patterns
whose support is σ

Finding Testable Patterns<α?

Ψ(σ1) ·Testable patterns?

σ1

Support σΨ(σ) decreases
22/24

Number of patterns
whose support is σ

Finding Testable Patterns<α?

Ψ(σ2) ·Testable patterns?

σ2

Support σΨ(σ) decreases
22/24

Number of patterns
whose support is σ

Finding Testable Patterns<α?

Ψ(σ3) ·Testablepatterns?

σ3

Support σΨ(σ) decreases
22/24

Number of patterns
whose support is σ

Finding Testable Patterns<α?

Ψ(σ3) ·Testable Computing this area is possible
patterns? by “frequent pattern mining”
using the Apriori principle

σ3Support σΨ(σ) decreases
22/24Power of Testability
Correction factor
Bonferroni
Ours
107
105
103
51015 Limitless
Maximum size ofsubgraph nodes

Number of significant
Running time (second)
subgraphs
4Bonferroni
Bonferroni
Ours
Ours
105
3103
21

1000.151015 Limitless
Maximum size ofsubgraph nodes

51015 Limitless
Maximum size ofsubgraph nodes

The PTC (Predictive Toxicology Challenge) dataset with 601 chemical compounds

23/24

Conclusion• Significant pattern mining is introduced– Find statistically significant subgraphs while controlling the FWER
– pattern mining (data mining) + multiple testing correction (statistics)• Open problems: How to treat continuous data?
– Continuous features → mostly solved
M. Sugiyama and K. Borgwardt:
Finding Significant Combinations of Continuous Features,
arXiv:1702.08694– Continuous response values → not solved yet
24/24