November 17, 2023

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 1
ID4 1
ID5 1
ID6 0
ID7 1
ID8 1111111010101011
1Itemset(combinationof colors)

Support: 6

Support: 3

3/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 11111110
10
1010111

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: (2, 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

supp𝐶 (𝑥)|𝐶| − supp𝐶 (𝑥)|𝐶|

Negativesupp𝐶̄ (𝑥)̄ − supp ̄ (𝑥)
|𝐶|𝐶̄
|𝐶|

Total

supp(𝑥)= supp𝐶 (𝑥) + supp𝐶 (𝑥)|𝐷| − supp(𝑥)

|𝐷|

7/24

Contingency Table
Occurrence

Non-occurrence

Total

Positive

𝑛11

𝑛12

𝑐1

Negative

𝑛21

𝑛22

𝑐2

Total𝑠𝑠′𝑑

7/24

Various Measures• Confidence: 𝑛11 ∕𝑑• Growth rate (relative risk): 𝑛11 ∕𝑛21
• Support difference (risk difference): 𝑛11 − 𝑛21• Mutual information:𝑛11 ∕𝑑𝑛12 ∕𝑑𝑛21 ∕𝑑𝑛22 ∕𝑑𝑛11𝑛12𝑛21
𝑛22loglog
loglog+++2′22𝑑𝑑𝑑𝑑
𝑐1 𝑠∕𝑑𝑐1 𝑠 ∕𝑑𝑐2 𝑠∕𝑑𝑐2 𝑠′ ∕𝑑2
• Subgroup discovery measure (weighted relative accuracy):(𝑐1 ∕𝑑) ((𝑛11 ∕𝑐1 ) − (𝑐1 ∕𝑑))8/24

Computing p-value of Pattern• Given positive and negative sample sets 𝐶, 𝐶̄ such that 𝐷 = 𝐶 ∪ 𝐶̄• The 𝑝-value of each pattern 𝑠 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 𝑞(supp𝐶 (𝑠)) is given by hypergeometric distribution:/)( |𝐷| )
( |𝐶| )( |𝐶|̄𝑞(supp𝐶 (𝑠)) =supp(𝑠)supp𝐶 (𝑠) supp𝐶̄ (𝑠)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 qOcc.

0.3

0p-value

suppC(s)10/24Hypothesis Test for Each PatternAlternative 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: (2, 1)
p-value = 0.5

12/24

Significant Subgraph MiningPositive• 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. 𝑝-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

Timeline1990

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
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

16/24

Multiple Testing
Occ. Non-occ. Total
Positive 404
Negative 3
14Total748
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 𝑚 tests, 𝛼𝑚 patterns can be false positives– Too many if 𝑚 is large! For example in itemset mining:◦ For 100000 items, #patterns = 2100000◦ Set significance level 𝛼 = 0.01
◦ Number of false positives: 0.01 ⋅ 2100000 = 1030101

17/24

Multiple Testing Correction• In each test, [probability of having a false positive] ≤ 𝛼• If we repeat 𝑚 tests, 𝛼𝑚 patterns can be false positives– Too many if 𝑚 is large! For example in itemset mining:◦ For 100000 items, #patterns = 2100000◦ Set significance level 𝛼 = 0.01
◦ Number of false positives: 0.01 ⋅ 2100000 = 1030101• FWER (family-wise error rate): Probability of having more than
one false positives among all patterns– FWER = 1 − (1 − 𝛼)𝑚 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 eachpatternfrom 𝛼 to 𝛿 (𝛿 ≤ 𝛼), the corrected significance level18/24

Controlling the FWER
• FWER = Pr(FP > 0)
– FP: Number of false positives• To achieve FWER = 𝛼, change the significance level for eachpatternfrom 𝛼 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= 𝛼∕𝑚

18/24

Minimum Achievable p-value Ψ(𝜎)• Consider the minimum achievable 𝑝-value Ψ(𝑠) of a pattern 𝑠for its support supp(𝑠)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 Ψ(𝑠)( |𝐶| )
Minimum achievable 𝑝-value Ψ(𝑠) =supp(𝑠)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|( |𝐷| )supp(𝑠)0.3
Probability q

Occ.

/Minimumachievablep-value

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

Tarone’s Testability Trickℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d(ψ(ℱi) ≤ ψ(ℱi+1))

21/24

Tarone’s Testability Trickm ψ(ℱm) < α and (m + 1)ψ(ℱm+1) ≥ αℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d(ψ(ℱi) ≤ ψ(ℱi+1))

21/24

Tarone’s Testability Trickm ψ(ℱm) < α and (m + 1)ψ(ℱm+1) ≥ αℱ1 , ℱ2 , ℱ3 ,..., ℱm–1 , ℱm , ℱm+1 ,..., ℱ2d
Testablepatterns

Untestablepatternsℱi is significant if: p-value(ℱi) < α / m(ψ(ℱi) ≤ ψ(ℱi+1))
Prune without testing
Correction factor
21/24

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3...
...

Fd–1,Fd
Fd
22/24

Enumeration Algorithm Based on Apriori

...
F1,F2
Threshold for η F1 F2 F3Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
22/24

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3Smaller η

Larger ψ...
...

Fd–1,Fd
Fd
22/24

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3
Smaller ηLarger ψ...
...

Fd–1,Fd
Fd
22/24

Enumeration Algorithm Based on Apriori

...
F1,F2
F1 F2 F3
Smaller ηLarger ψ...
...

Fd–1,Fd
Fd

Testablepatterns
22/24

Power of Testability (Subgraph Mining)
Correction factor
Bonferroni
Ours
107105103
51015 Limitless
Maximum size ofsubgraph nodes

Number of significant
Running time (second)
subgraphs
4Bonferroni
Bonferroni
Ours
Ours
105
3103
211000.151015 Limitless
Maximum size of
subgraph nodes

51015 Limitless
Maximum size ofsubgraph nodes

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

23/24

Conclusion• Supervised pattern mining has been considered• Significant pattern mining is introduced– Find statistically significant patterns while controlling the FWER
– pattern mining (data mining) + multiple testing correction (statistics)– Key technique: Tarone’s trick

24/24