Statistical Emerging Pattern Mining
with Multiple Testing Correction
Junpei Komiyama1, Masakazu Ishihata2,Hiroki Arimura2, Takashi Nishibayashi3,Shin-Ichi Minato2
1. U-Tokyo
2. Hokkaido Univ.
3. VOYAGE GROUP Inc.
(to appear in KDD2017 research track)

Single-page Summary
p We study Emerging Pattern Mining(EPM) with statistical guarantee.
p EPM is also known as contrast set mining,
subgroup mining.

p We propose two-stage mining methods
that control FWER or FDR.
p FWER: Family-Wise Error Ratep FDR: False Discovery Rate
2017/8/3

ERATO感謝祭2Emerging Pattern Mining
p Items: I = {1,…,|I|}p Pattern: e ⊆ I
p Emerging Pattern:p e that appears frequently in D+ but not in D−.

2017/8/3{1, 2}{1, 3, 4}{1, 2, 3}…

ERATO感謝祭{1, 3}{2, 4}{1, 3, 4}…

3

Emerging Pattern Mining
p Database:ppp

D = { (xi, yi) : i = 1,…,N } where xi ⊆ I, yi ∈{0,1}
D+ = { (x, y) ∈ D : y = 1 }D− = { (x, y) ∈ D : y = 0}

p Emerging Pattern: e s.t. Ne+ / Ne− > app
pNe+ = |{ (x, y) ∈ D+ : e ⊆ x }|Ne− = |{ (x, y) ∈ D− : e ⊆ x }|a = a given thresholdp Problems of Emerging Pattern Mining:
1. Too many insignificant patterns are found.
2. Not sure whether the found patterns are justrandom fluctuation of D or truly significant.
2017/8/3

ERATO感謝祭

4Statistical Emerging Pattern Mining
p Assumption: (x, y) ~i.i.d.~ IP[x, y]p IP[x, y] = unknown true distribution

p Positive label prob.: µe = IP[y = 1 | e ⊆x]p True / False Emerging Pattern:
p εtrue = {e ∈ 2I : µe > a}p εfalse = {e ∈ 2I : µe ≦ a}p SEMP: Estimate εtrue from D.
2017/8/3

ERATO感謝祭

5

Statistical Emerging Pattern Miningp εalg = outputs of an algorithm
p Family-wise error rate (FWER):
p FWER = IP[ |εalg ∩ εfalse| ≧ 1 ]p False discovery rate (FDR):
p FDR = IE [ |εalg ∩ εfalse| / |εalg| ]We propose two-stage mining methods
that satisfy FWER ≦ q or FDR ≦ q.
2017/8/3

ERATO感謝祭

6Pattern as a hypothesis
p Null hypothesis (e ∈ εfalse):p He0 : µe = ap Alternative hypothesis (e ∈ εtrue):p He1 : µe > ap P-value:

2017/8/3

ERATO感謝祭

7

Multiple Testing Correction
p P-value:pp

How data is likely to be generated under He0.
Small p-value à Rare eventp Single Hypothesis:
pp

Reject e if pe ≦ q è We think e is a True EP.
Control FWER (and FDR) ≦ q.

p Multiple hypotheses:pp

Probability of including “false positive” gets fairly high.
Peeking p-values causes “selection bias”.

Need multiple testing correction.
2017/8/3ERATO感謝祭

8Bonferroni correction for FWER
p Reject e if pe ≦ q / m.
p m = # of patterns to test.

p Control FWER at level q.

2017/8/3

ERATO感謝祭

9

Step-up correction for FDR
p Reject e(1),…,e(k)p p(i) = the i-th smaller p-valuep e(i) = its corresponding pattern
pp BH : c(m) = 1
p BY : c(m) = Σmi=1 (1 / i)

Step-uprejectionLevel

p Control FDR at level q,
p under independence among hypotheses (BH)p or under arbitrary correlations (BY).
2017/8/3

ERATO感謝祭

10But patterns are exponentially large…
p m (= # of patterns to test) can be
exponentially large : 2|I|.
p Naïve Bonferroni / Step-up corrections
cannot find much patterns.
p Both corrections have q / m factor

Needs to reduce # of patterns to test.
2017/8/3

ERATO感謝祭

11

Existing statistical pattern mining andour result
Existing

Our result
Two-stage Mining methods

p LAMP [Terada+ 13]
p Proposed for statistical association mining (SAM)p Selects testable patterns before correction, andp Controls FWER.
2017/8/3

ERATO感謝祭12Two-stage Mining Method
1. Find a “appropriate” threshold τ.
2. Test patterns {e : Ne > τ} withmultiple testing correction.
How to choose “appropriate” τ?
We use “testability” just like LAMP!
2017/8/3

ERATO感謝祭

13Testability for FWER
p Taroneʼs exclusion principle:
p Patterns with large p-value can be omitted
without testing; it cannot be significant.
p FWER can be controlled by q / mtest (not m).
•mtest = # of “testable” patternsp ψ(Ne) = a lower bound of pep ψ(N) = aN

p e is testable if ψ(pe) ≦ q / mtest
2017/8/3

ERATO感謝祭

14

LAMP-EP (LAMP for SEPM)
p Finding the largest testable set boils down
to finding the following thresholds.t.:
…(1)
…(2)

: Frequent patterns with min-support 𝜏.

(1)…patterns of support < 𝜏%&'( are untestable.
(2)…patterns of support ≥ 𝜏%&'( are testable.

2017/8/3

ERATO感謝祭

15

Next : Controlling FDR
p No principled method yet.
p Major challenges:
1. No Taroneʼs exclusion in FDR:
Ø We solve this by splitting the dataset into
calibration and main datasets.

2. Not sure how to select a “testable” set.
Ø We introduce “quasi-testablity”(approximated testability).

2017/8/3

ERATO感謝祭

16

Quasi-testability for FDR
p Step-up Correction for FDR:
p Reject e(1),…,e(k)•p(i) = the i-th smaller p-value.

•e(i) = its corresponding pattern.

•p e is testable if ψ(Ne) ≦ p(k)p But p(k) must be unknown to avoid selection bias.

p e is quasi-testable if ψ(Ne) ≦ pestpp
2017/8/3

Instead of true p(k), we use an estimator pest.
We split D into Dmain and Dcarib, and use Dcarib to estimate pest.
ERATO感謝祭

17

QT-LAMP-EP for controlling FDR
p Find threshold value

such that…(1)
…(2)
…(3)
= # of patterns rejected if step-up method isconducted for.

(1)…patterns of support < 𝜏*+, are untestable,(2)…patterns of support ≥ 𝜏*+, are testable,
under estimated step-up
rejection level of (3). 18
2017/8/3
ERATO感謝祭

Computer Simulations
p Statistical powers of LAMP-EP and QTLAMP-EP are compared.
p LAMP-EP used the entire dataset fortesting.
p QT-LAMP-EP used 20% of D as Dcarib for
obtaining pest, and 80% as Dmain for testing.
2017/8/3

ERATO感謝祭

19FWER/FDR in synthetic dataset.
p Synthetic patterns, 𝑎 = 0.5, 𝑞 = 0.05.
p True SEPs: subset of {1, … , 10}: 𝜇8 = 0.7
p Other patterns: subset of {11, … , 100}, 𝜇8 = 0.5.
p, 10% of patterns are true SEPs.

Results:

2017/8/3

ERATO感謝祭

Controlled ≦ q20

Number of discoveries in aclassification (mushroom) dataset

Morediscoveries →p Controlling FDR yields more patterns
than FWER.

• Similar results hold for other 7 datasets.
2017/8/3
ERATO感謝祭
21Conclusion
p We formulated statistical emerging
pattern mining.
p We propose two-stage mining methods:
p LAMP-EP controls FWER.
p QT-LAMP-EP controls FDR.

p We empirically verified their statistical power.

Thanks!
2017/8/3

ERATO感謝祭

22

Contact us
Paper and software are available.
Paper:
http://www.tkl.iis.u-tokyo.ac.jp/~jkomiyama/pdf/kddstatistical-emerging.pdf
Software:https://github.com/jkomiyama/qtlamp

Contact:
Junpei Komiyama
junpei@komiyama.info
2017/8/3

ERATO感謝祭

23