Statistical Emerging Pattern Mining with Multiple Testing
Correction
Junpei Komiyama

Masakazu Ishihata

Hiroki Arimura

The University of Tokyo
junpei@komiyama.info

Hokkaido University
ishihata.masakazu@ist.hokudai.ac.jp

Hokkaido University
arim@ist.hokudai.ac.jp

Takashi Nishibayashi

Shin-ichi Minato

VOYAGE GROUP, Inc.
takashi.nishibayashi@gmail.com

Hokkaido University
minato@ist.hokudai.ac.jp

ABSTRACTEmerging patterns are patterns whose support significantly differs
between two databases. We study the problem of listing emerging patterns with a multiple testing guarantee. Recently, Terada etal. proposed the Limitless Arity Multiple-testing Procedure (LAMP)
that controls the family-wise error rate (FWER) in statistical association mining. LAMP reduces the number of “untestable” hypotheses without compromising its statistical power. Still, FWER is restrictive, and as a result, its statistical power is inherently unsatisfying when the number of patterns is large. On the other hand, thefalse discovery rate (FDR) is less restrictive than FWER, and thus
controlling FDR yields a larger number of significant patterns. We
propose two emerging pattern mining methods: the first one controls FWER, and the second one controls FDR. The effectiveness ofthe methods is verified in computer simulations with real-world
datasets.

KEYWORDS
emerging pattern mining, multiple testing, statistical pattern mining
ACM Reference format:
Junpei Komiyama, Masakazu Ishihata, Hiroki Arimura, Takashi Nishibayashi,and Shin-ichi Minato. 2017. Statistical Emerging Pattern Mining with Multiple Testing Correction. In Proceedings of KDD ’17, Halifax, NS, Canada,
August 13-17, 2017, 10 pages.
DOI: 10.1145/3097983.3098137

1

INTRODUCTION

Finding differences between two datasets is of fundamental importance in many scientific fields. Many tasks, such as binary classification, feature selection, change point detection, and concept
drift learning, boil down to finding good discriminative featuresthat explain the differences. When the structure of the problem issimple, it suffices to consider each single feature separately. However, when the problem is not straightforward, the combinatorial
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than
the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee. Request permissions from permissions@acm.org.
KDD ’17, Halifax, NS, Canada© 2017 Copyright held by the owner/author(s). Publication rights licensed to ACM.
978-1-4503-4887-4/17/08. . . $15.00
DOI: 10.1145/3097983.3098137

effect of multiple features can be fundamentally important. Since
the number of possible combinations is exponential to the numberof features, this task is inherently challenging.
Emerging pattern mining (EPM) [10] is an approach that lists
the patterns where the difference between two datasets is larger
than a given threshold. One of the greatest advantages of EPM
lies in that it can naturally find combinatorial features: each combinatorial feature corresponds to an itemset in pattern mining. Although there are many studies on EPM (for a detailed list of these
papers, see Dong and Bailey [9]. Moreover, for similar concepts
such as contrast set mining and subgroup mining, see Novak et
al. [22]), the standard formulation of EPM lacks a statistical assessment, which induces a risk that a significant fraction of found patterns are just false positives; that is, the patterns may have only
been found because of the random nature of data and are actuallyinsignificant. Statistical testing is widely used to control such risks.
In particular, a procedure of listing patterns can be verified within
the framework of multiple hypothesis testing by considering each
itemset to be a hypothesis.
Undoubtedly, we would like to find as many patterns as possible
for a given level of risk. The study of multiple testing is somewhat
paradoxical: the larger the number of patterns to test is, the lesspowerful the test becomes. This is because that the risk of finding
false discoveries rises as the number of patterns to test increases.
Since the number of possible patterns is 2ℓ to the number of theitem ℓ, testing all the patterns is unlikely to result in many patterns. Moreover, testing all possible patterns is computationallyprohibitive. In order to avoid this “combinatorial explosion curse”,
we would like to determine a set of patterns to test before conducting multiple testing. Unfortunately, most of the existing data mining approaches that take multiple testing into consideration are
not principled when it comes to determining the patterns to test:
they choose the minimum support by using implicit knowledge. If
one selects a set of hypotheses by looking into the database, thatcan cause a selection bias that devastates the entire testing process. A recently proposed method called Limitless-Arity Multipletesting Procedure (LAMP) [28] avoids this pitfall and enables us toselect the patterns to test in a principled way; it effectively reduces
the number of patterns without prior knowledge and alleviates the
combinatorial explosion curse.
There are two different targets to control in multiple testing.
Namely, the family-wise error rate (FWER) and the false discovery rate (FDR) [4]. The former value is the probability of a false
discovery among the found patterns. The aforementioned LAMP

KDD ’17, August 13-17, 2017, Halifax, NS, Canada
is designed to control FWER. Although control of FWER is crucial
in some areas such as genome association studies, where a false
discovery can cause severe harm, the restrictive nature of FWER
often limits the statistical power. We hence argue that, in manycases, some number of false discoveries is tolerable. For example,
feature selection is not harmed much when insignificant features
are added. Moreover, E-commerce data is often analyzed with thehope of making discoveries that can boost revenue; a certain number of false discoveries would be tolerable in this case as well. For
such applications, a more modern notion of FDR, i.e., is the probability of false discoveries among all discoveries, is less restrictive
and would empower one to make discoveries. Unfortunately, thereis as yet no pattern mining method for controlling FDR with anability to choose an appropriate set of patterns to test.
The statistical pattern mining is essentially comprised of twostages: the first stage selects a set of patterns to test, and the second stage tests the selected patterns. While LAMP is dependent
on Tarone’s exclusion principle [26] that excludes “untestable” patterns, there is no corresponding notion in FDR, and thus, one must
devise a principled way to reduce a set of patterns. In this paper, we
describe a way to control FDR (Table 1). The key notion for testing
FDR is ”quasi-testability”. The quasi-testability takes the adaptive
nature of FDR into consideration, and hence, it effectively reduces
the hypotheses that are very unlikely to be significant.
The contributions of this paper are as follows. We formalize theproblem of statistical emerging pattern mining (SEPM). We propose LAMP-EP, a version of LAMP for SEPM, which effectively
lists patterns while controlling FWER. Moreover, we propose QTLAMP-EP which controls FDR in SEPM. Note that the quasi-testability
based method is not only for emerging patterns and possibly beapplied to any pattern mining method. To verify the performanceof the methods, computer simulations were conducted with eightreal-world datasets. The exhaustive set of simulations shows thattolerance to a predefined FDR can lead to a significantly larger setof discoveries.

2

RELATED WORK

Some studies are based on distributional assumptions. Kirsch etal. [14] developed a multiple testing procedure that identifies thebest support threshold such that the pattern will be significant by

Table 1: Comparison of methods for controlling FWER and
FDR in pattern mining. LAMP is a statistical association
mining (SAM) method that controls FWER by applying the
Bonferroni method [7] to testable patterns. This paper proposes LAMP-EP and QT-LAMP-EP that control FWER and
FDR in the SEPM problem. QT-LAMP-EP applies the stepup method [6, 13] to quasi-testable patterns.

Mining target
Multiple Testing
Pattern Reduction
Testing method

LAMP

LAMP-EP

QT-LAMP-EP

SAM
FWER
Testable
Bonferroni

SEPM
FWER
Testable
Bonferroni

SEPM
FDR
Quasi-Testable
Step-up

J. Komiyama et. al.
assuming the supports of patterns are Poisson-distributed. LowKam et al. [18] proposed a mining method that measures the significance of a pattern by the deviation from the null model. In thispaper, we do not assume such models; the only essential assumption we rely on is the i.i.d. property of the transactions.
Unlike most of the existing work, the LAMP algorithm [28] does
not require a stringent distributional assumption and is capable ofdetermining the minimum support threshold. Some subsequentstudies were inspired by LAMP: Sugiyama et al. [25] considered
statistical association in subgraph mining. Terada et al. [27] andFelipe et al. [17] integrate the Westfall-Young permutation method[32] into the pattern selection and showed that it empirically yields
more discoveries than LAMP. Note that the Westfall-Young method
exploits subset pivotality of SAM [20] and not applicable to EPM.
Papaxanthos et al. [23] extended LAMP to cases where categoricalcovariates exist. Webb et al. [31] studied association rule mining
and proposed two methods to control the error rate. One method
uses explanatory and holdout datasets: the explanatory dataset isfor pattern discovery and the holdout dataset is for pattern testing. Although this method is only for association rule mining,
our method is partly inspired by theirs in that it uses several independent datasets. Riondato and Vandin [24] studied the association rule mining. They conducted a statistical learning theory
based analysis that is distribution-free and derived a guaranteethat is similar to FWER. Their analysis requires a minimum support threshold. Hanhijärvi [12] proposed a procedure to adjust the
Bonferroni correction factor to control FWER by using randomization under the assumption of subset pivotality. Lallich et al. [15, 16]
proposed a bootstrap-based algorithm for association mining that
controls a version of FWER that tolerates a fixed number of false
discoveries.

3 PROBLEM SETUP
In this section, we first briefly review the frequent pattern mining (FPM) and emerging pattern mining (EPM) problems. Then, we
propose a new problem called statistical emerging pattern mining(SEPM), which is an extension of EPM that assesses the chance ofa discovered pattern being a true discovery.

3.1

Frequent Pattern Mining (FPM)

Let D be a database, which is a set of transactions. Each transaction is a tuple (x, y), where x is a pattern and y ∈ {0, 1} is alabel of pattern x. Each pattern x is a subset of ℓ items indexed as
I = {1, 2, . . . , ℓ}; namely, x ∈ 2I . A pattern with a label 0 (resp. 1)
is said to be negative (resp. positive). Given a dataset D, we use
D + and D − to denote sub-datasets of D that consist of positive
and negative patterns; namely,
D + = {(x, y) ∈ D : y = 1},(1)

D − = {(x, y) ∈ D : y = 0}.

(2)

We assume that each transaction (x, y) ∈ D is an i.i.d. sample froman unknown joint distribution P[x, y] on 2I × {0, 1}; namely, D isa random variable. All probability and expectations in this paper
are taken on this distribution.
Given a database D and a pattern e ∈ 2I , the occurrences of ecomprise a set of transactions in D that contains e. The support of eStatistical Emerging Pattern Mining with Multiple Testing Correctionis the number of occurrences of e. We use Occ(e; D) and Sup(e; D)to denote the occurrences and the support of e:
Occ(e; D) = {(x, y) ∈ D : e ⊆ x },(3)

Sup(e; D) = |Occ(e; D) |.

(4)

Given a dataset D and a minimum support τ (τ = 0, 1, . . . , |D|),a frequent pattern (FP) is a pattern that appears τ or more times in
D. We use EFP (τ ; D) to denote the set of all frequent patterns:
EFP (τ ; D) = {e ∈ 2I : Sup(e; D) ≥ τ }.

(5)

The goal of the frequent pattern mining (FPM) [1, 3] is to find EFP (τ ; D)given τ and D. An item i ∈ I is said to be redundant in D if
Occ({i}; D) = D; in other words, i appears in all transactions
in D. In this paper, we assume that the given dataset D contains no redundant item. Consequently, the only pattern e ∈ 2I
that satisfies Occ(e; D) = D is the empty pattern e = φ; namely,
EFP (|D|; D) = {φ}.

3.2

Since µ e is unobservable, we need to estimate whether or not eachpattern e lies within Etrue from the observed dataset D.
Here, we describe a new problem, called statistical emerging pattern mining (SEPM), which is to find a fraction of the true emerging patterns Etrue from the given dataset D with a statistical error
bound. Ultimately, we would like to construct an algorithm thatexactly finds Etrue ; however, this is impossible because of the random nature of D. Instead of finding the whole Etrue , we attempt
to construct an algorithm that finds a set of appropriate patterns
Ealg ⊆ 2I and keeps its error rate under the given significancelevel q ∈ (0, 1). We consider two types of error rate, the familywise error rate (FWER) and the false discovery rate (FDR), defined
as follows:
Definition 3.1 (FWER). Given a significance level q, an SEPM algorithm is said to control FWER if[]
P |Ealg ∩ Efalse | ≥ 1 ≤ q.
(11)
FWER is the probability that Ealg contains a false pattern e ∈ Efalse .

Emerging Pattern Mining (EPM)

Whereas FPM does not consider the labels of patterns, the goalof emerging pattern mining (EPM) [10] is to list all patterns which
frequently appear in D + but not in D − . Let GR(e; D) be the growthrate of pattern e that is defined as follows:()
0(Sup e; D + = 0 and Sup(e; D − ) = 0),




(
)
(Sup e; D + , 0 and Sup(e; D − ) = 0),GR(e; D) = ∞+)Sup(e;D Sup(e;D − ) (otherwise).
(6)
Given a growth rate threshold a > 0, emerging patterns (EPs) aredefined as follows:{}(7)
EEP (a; D) = e ∈ 2I : GR(e; D) > a .
The EPM problem is to find EEP (a; D) given a and D. Because
listing the entire EEP (a; D) is often computationally prohibitive,
many algorithms() for EPM [2, 10, 19] set a minimum support τ forboth Sup e; D + and Sup(e; D − ); (in other) words, usually( only) patterns e ∈ EEP (a; D) such that Sup e; D + ≥ τ and Sup e; D + ≥ τare enumerated.
The above formulation lacks a statistical assessment: for example, how many of the found EPs are reproducible when we conduct
an EPM with another dataset D ′ generated by the same process?
In the next section, we extend EPM to statistically assess the foundpatterns.

3.3

KDD ’17, August 13-17, 2017, Halifax, NS, Canada

Statistical Emerging Pattern Mining (SEPM)

We first define the true emerging patterns independently of the observed dataset D. Let µ e be the positive label probability of patterne ∈ 2I that is defined as follows:∑[]µ e = P[y = 1 | e ⊆ x] ∝P y = 1, x = e ′ .
(8)
e ′ ∈2I :e ⊆e ′Given a positive label probability threshold a ∈ (0, 1), we define thetrue emerging patterns Etrue and false patterns Efalse as follows:
Etrue = {e ∈ 2I : µ e > a},(9)

Efalse = {e ∈ 2I : µ e ≤ a}.

(10)

Definition 3.2 (FDR). Given a significance level q, an SEPM algorithm is said to control FDR if[]|Ealg ∩ Efalse |
E
≤ q,
(12)
|Ealg |
where we define 0/0 = 0. FDR is the expected ratio of false patterns
in Ealg .
Note that an SEPM algorithm that controls FWER at significancelevel q also controls FDR at the same level q, but not vice versa. To
guarantee that an SEPM algorithm controls FWER or FDR, we formulate this problem as multiple hypothesis testing in the following
section.

4 MULTIPLE HYPOTHESIS TESTING
In this section, we first formulate an SEPM problem as multiple hypothesis testing. We then discuss the Bonferroni method and thestep-up method for controlling FWER and FDR, respectively. After
that, we discuss the procedure for reducing the number of hypotheses by testability, which we generalize into two-stage mining.

4.1

SEPM as Multiple Hypothesis Testing

4.1.1 Hypothesis. Section 3.3 formalized SEPM. Considering eachpattern as a hypothesis, SEPM naturally fits into the framework ofmultiple hypothesis testing. In SEPM, a null hypothesis that corresponds to pattern e is
He0 : µ e = a.

(13)

Rejecting the null hypothesis He0 implies that the following alternative hypothesis is supported:
He1 : µ e > a.

(14)

The alternative hypothesis He1 states that pattern e is considered
to be the true emerging pattern: e ∈ Etrue . Whether the null hypothesis He0 is rejected or not at a given significance level q is determined by the p-value of pattern e. The p-value is described in
Section 4.1.2. Note that thanks to the monotonicity of the p-value,
the case of µ e < a is also covered by evaluating its null hypothesis
He0 .

KDD ’17, August 13-17, 2017, Halifax, NS, Canada
A discovered pattern e ∈ Ealg is called a true discovery if e isa true emerging pattern: e ∈ Etrue . On the other hand, e ∈ Ealgis called a false discovery, or Type I error, if e is a false pattern:e ∈ Efalse . A true emerging pattern e ∈ Etrue that fails to be rejected (not discovered) is called a Type II error. Obviously, an algorithm that rejects no hypothesis contains no false discovery andalways controls FWER and FDR at any significance level q. Such analgorithm is, however, utterly useless. In general, there is a tradeoff between the number of Type I errors and the number of TypeII errors. We are interested in a multiple hypothesis testing algorithm that controls FWER or FDR at q and while providing highstatistical power, i.e., few Type II errors.
4.1.2 p-value. Under the null hypothesis He0 , the labels corresponding to pattern e follow a Bernoulli distribution with probability a. Thus, the number of positive samples given the total number+of samples follows a Binomial distribution. We( denote) Ne and Ne
as the realized values of Sup(e; D) and Sup e; D + . Then, the pvalue of pattern e is defined as the probability that Ne+ or more
samples out of Ne samples have positively labeled under the null
hypothesis He0 . We use pe to denote the p-value of e, which is computed as follows:[]()
pe = P Sup e; D + ≥ Ne+ | Sup(e; D) = Ne , He0
)
Ne (
∑
Ne n
(15)
=
a (1 − a)Ne −n .
n
+
n=N e

Obtaining the above pe requires an exponential computation in Ne
and is quite hard when Ne is large. Let µ̂ e = Ne+ /Ne be the empirical positive label probability of e. Then, pe can be approximatedby the following Chernoff bound:{exp(−Ne d KL (µ̂ e , a)) (µ̂ e > a),
C
pe ≤
(16)
1
(otherwise),
where d KL (p, q) = p log (p/q) + (1 − p) log((1 − p)/(1 − q)) is the
KL divergence between two Bernoulli distributions with their parameters p and q. Note that the exponential factor of the Chernoff
bound is optimal [8], and thus the approximation using the boundis very tight for a sufficiently large value of |D|. In this paper, we
use the above peC as a proxy of the true p-value pe when we needto compute pe for |D| > 100.
In the case of single hypothesis testing, we reject the null hypothesis He0 if its p-value pe is lower than the given significancelevel q; however, in the case of multiple hypothesis testing, weneed to correct the significance level q based on the basis of thenumber of hypotheses.

4.2

Bonferroni Method for FWER

For a single null hypothesis He0 , the probability of a false discovery
is upper-bounded by its p-value pe . However, the probability offinding a false pattern (e ∈ Efalse ) with pe smaller than any level q,
converges to 1 as the number of hypotheses increases. Therefore,a multiple hypothesis testing correction is necessary for bounding
FWER.
Let e 1 , . . . , em be a set of m patterns that we would like to test.
FWER can be controlled by adapting Bonferroni’s correction [7],J. Komiyama et. al.
which simply divides the required significance level q by the number of patterns m. Then, the discovered patterns Ealg by the Bonferroni method is
{
q}
(17)
Ealg = e ∈ {e 1 , . . . , em } : pe ≤,mand the Bonferroni method correctly controls FWER at significancelevel q.

4.3

The Step-Up Method for FDR

Unlike FWER, a simple correction factor, such as q/m, is not able tocontrol FDR appropriately because the ratio of the expected number of false discoveries depends on all p-values of the patterns to
test. For example, suppose we have tested some patterns and rejected k out of them. If all rejected patterns have low p-values, theexpected number of false discoveries in the k rejected patterns is
also low. In such a case, we can safely reject the next pattern even
if its p-value is not very low because the average p-value of therejected patterns is smaller than the given threshold. Conversely,
if some of the rejected patterns have high p-values, we have to require a small p-value for other patterns to be rejected so as to keep
the average p-value of the rejected patterns small. Consequently,
in the case of controlling FDR, whether or not to reject a patterndepends on the p-values of the other patterns.
The step-up method [13] is widely used for controlling FDR.
Given m patterns e 1 , . . . , em and their p-values pe1 , . . . , pem , weuse e (i) to refer the pattern with the ith smaller p-value and p(i) todenote the p-value of e (i) ; namely, p(1) ≤ · · · ≤ p(m) . Accordingly,
the step-up method outputs the following patterns as discoveries:{}(18)
Ealg = e ∈ {e 1 , . . . , em } : pe ≤ p(k) ,
}
{
q i
,
k = arg max p(i) ≤(19)c(m) m0≤i ≤mwhere c(m) is an adjustment function. The correction factor in the
step-up method is proportional the number of rejected hypotheses.
When each hypothesis is independent, setting c(m) = 1 suffices to control FDR at a significance level q, which we call the
Benjamini-Hochberg (BH) method [4]. On the other hand, the∑Benjamini-Yekutieli (BY) method [6], which uses c(m) = m
i=1 (1/i),
controls FDR when hypotheses have an arbitrary dependence.

4.4

Two-Stage Procedure for Improving theStatistical PowerIn SEPM, each pattern is naturally associated with a hypothesis,
and the number of possible patterns is exponential to the numberof items. The larger the number of patterns m to test is, the weaker
the power of finding significant patterns becomes, as indicated bym in the denominator of (17) and (19). It may be the case that the
number of hypotheses is so large that a simple application of the
Bonferroni or step-up method yields no pattern.
In the context of statistical association mining, LAMP [28] controls FWER and uses Tarone’s exclusion principle for improving its
statistical power.
Tarone’s Exclusion Principle [26]: a pattern e is said to be untestablewith respect to significance level q if the lower bound of its p-value
is greater than q. Untestable patterns do not increase FWER and
can be ignored before running a multiple hypothesis test.

Statistical Emerging Pattern Mining with Multiple Testing Correction
The notion of testability is generalized in the following twostage procedure:
Selection Stage: Find Eselect ⊆ 2I : each e ∈ Eselect is testable.
Testing Stage: Conduct a multiple hypothesis test on the selected
testable patterns Eselect and output Ealg ⊆ Eselect where e ∈ Ealgis rejected at a corrected significance level.
Taking this into consideration, in the next section, we propose
two-stage methods for controlling FWER and FDR in SEPM. We
should point out that checking testability in FDR is not a trivial exercise because the correction factor of the step-up method depends
not only on the number of hypotheses but also on the p-values ofall patterns. To put it differently, we cannot judge whether the
lower-bound of the p-value is greater than the corrected significance level or not in the selection stage. To solve this problem,
we put forward a new notion called quasi-testability and use it toselect a subset of patterns to test.

5

PROPOSED METHODS

We propose two SEPM algorithms: LAMP-EP to control FWER and
QT-LAMP-EP to control FDR. Both algorithms are based on the
two-stage procedure discussed above.

5.1

LAMP-EP for FWER

LAMP-EP is a version of LAMP for statistical emerging patternmining (SEPM). Testability is critical for reducing the number ofpatterns to test: under Bonferroni’s correction, a pattern e is said
to be untestable if the lower bound of its p-value pe is greater thanthe corrected significance level q/m, where q is a given significancelevel and m is the number of patterns to test. In SEPM, from thedefinition of the p-values shown in Equation (15), the p-value ofe can be lower-bounded as pe ≥ a Sup(e;D) , where Sup(e; D) isthe number of occurrences of e in D. Let ψ (τ ) = aτ . Given q
and m, a pattern e is said to be testable with respect to q and m if
ψ (Sup(e; D)) ≤ (q/m). Furthermore, the untestable patterns canbe safely removed from the candidates thanks to Tarone’s exclusion principle [26].
In the selection stage, we find Eselect ⊆ 2I that only consistsof testable patterns. As the support of a pattern determines its
testability, we want to find an appropriate threshold τ such that
EFP (τ ; D) contains no untestable pattern, and choose Eselect =∗EFP (τ ; D). We here introduce the optimal selection threshold τFWER
defined as follows:∗τFWER= min {τ : ψ (τ ) ≤ δ FWER (τ ; q, D)} ,τqδ FWER (τ ; q, D) =,|EFP (τ ; D) |KDD ’17, August 13-17, 2017, Halifax, NS, Canada

Proof. Let LHS(τ ) = φ(τ ) and RHS(τ ) = δ FWER (τ ; q, D). LHS(τ )and RHS(τ ) are decreasing and increasing functions of τ , respectively. Namely, if τ satisfies LHS(τ ) ≤ RHS(τ ), all τ ′ > τ alsosatisfy the same inequation. For τ = 0, LHS(τ ) > RHS(τ ) holds because ψ (0) = 1 and δ FWER (0; q, D) ≤ q < 1. For τ = |D |, LHS(τ ) <RHS(τ ) holds because ψ (|D|) = a | D | < q = δ FWER (|D|; q, D),
where we have used the fact that |EFP (|D|; D) | = |{φ}| = 1 in thelast transformation. Combining the above facts, we see that there
exists the unique threshold value τ such that LHS(τ ) > RHS(τ ) andLHS(τ + 1) ≤ RHS(τ + 1).
□∗
It is easy to see that τFWER
in Eq. (22) and Eq. (23) corresponds
the selection threshold defined in Eq. (20). Due to the monotonic∗
ity of each side of the inequality, τFWER
can be found by using abisection search.
Taking the above fact into consideration, we propose LAMP-EP
as the following two-stage procedure:()∗∗
Selection Stage: Find τFWER
and obtain Eselect = EFP τFWER;D
by using a frequent pattern mining algorithm.
Testing Stage: Conduct a multiple test with the Bonferroni’s method
for Eselect and output the rejected patterns as Ealg .
The LAMP-EP correctly controls FWER at a significance level q.

5.2

QT-LAMP-EP for FDR(20)

In the case of FWER, thanks to Tarone’s exclusion principle, we areable to remove untestable patterns from the candidate patterns andconduct Bonferroni’s correction on the remaining patterns. Gilbert[11] showed that a Tarone-like exclusion principle can also be used
for controlling FDR when the patterns are independent. However,when the patterns are dependent, which is the case in SEPM, it
is not known whether the same principle applies or not. In order to improve the statistical power under a controlled FDR, weneed a new exclusion principle that reduces the number of patterns before conducting the step-up correction. In the following,
we propose an unbiasedness condition that is sufficient for controlling FDR. After that, we propose quasi-testability for optimizing
statistical power. Following the introduction of these notions, we
describe QT-LAMP-EP that controls FDR.
Let Eselect be a set of selected patterns in the selection stage.
Eselect is said to be unbiased with respect to dataset D ′ if, for any
transaction (x, y) ∈ D ′ ,(21)

P[y | e ⊆ x] = P[y | e ⊆ x, Eselect ] .

where δ FWER (τ( ; q, D) is )the corrected significance level. Choosing∗
Eselect = EFP τFWER; D is reasonable because it is the largest setof frequent patterns that only consists of testable patterns. The∗
following proposition clarifies the optimization problem of τFWER.

Proposition 5.1. Given a dataset D and significance level q such∗that a | D | < q, there exists a unique τFWER
such that()∗∗ψ (τFWER− 1) > δ FWER τFWER− 1; q, D ,
(22)
( ∗
)
∗
(23)
ψ (τFWER) ≤ δ FWER τFWER; q, D ,(24)

If an unbiased Eselect can be obtained in the selecting stage, we canapply the step-up method for Eselect in the testing stage because
p-value conditioned on the selection is correctly controlled: theresulting two-stage procedure always controls FDR.
To guarantee unbiasedness, we first split the given dataset D
into two sub-datasets: the calibration dataset Dcarib and the main
datasets Dmain . In the selection stage, we first compute a selection threshold τFDR from Dcarib and set Eselect = EFP (τFDR ; Dmain ).
Then, we conduct the step-up method for Eselect using Dmain in thetesting stage. This two-stage procedure satisfies the above unbiasedness condition with respect to Dmain ; because of the assumed

KDD ’17, August 13-17, 2017, Halifax, NS, Canada

J. Komiyama et. al.

i.i.d. property of the transactions in D, τFDR is determined independent of the realization of the main dataset Dmain . Therefore,
whether or not a pattern e is selected is determined solely on its
support size. Since the p-value is defined by the conditional probability on Sup(e; D) = Ne (Section 4.1.2) and no information on thelabels of these pattern is exploited, the p-value correctly represents
the tail probability if e is a null hypothesis.
Inspired by testability, we propose a new notion called quasitestability: e is quasi-testable with respect to q, k̂, and m̂ if
ψ (Sup(e; Dcarib )) ≤q k̂.
c(m̂) m̂(25)

If we can set k̂ = k and m̂ = m in Equation (19), quasi-testability
is a sufficient condition for the pattern not to be rejected by the
step-up method. We estimate these values from Dcarib . In the selection stage, we find Eselect ⊆ 2I such that Eselect consists of only
quasi-testable patterns. Similar to the LAMP-EP (Section 5.1) that
selects the largest set of testable patterns, we would like to find∗τFDRdefined as follows:∗τFDR= min {τ : ψ (τ ) ≤ δ FDR (τ ; q, Dcarib )} ,(26)qk̂(τ ; Dcarib ),c(|EFP (τ ; Dcarib ) |) |EFP (τ ; Dcarib ) |

(27)

τ

δ FDR (τ ; q, Dcarib ) =where k̂(τ ; Dcarib ) is an estimator of k of Equation (19), which iscomputed by conducting the step-up correction on EFP (τ ; Dcarib )by using Dcarib , and δ FDR (τ ; q, Dcarib ) is the corrected significance∗ :level. The following proposition clarifies the optimization of τFDR
Proposition 5.2. Given a dataset Dcarib and a significance levelq such that a | Dcarib | < q, there exists a threshold τFDR such thatψ (τFDR − 1) > δ FDR (τFDR − 1; q, Dcarib )(28)

ψ (τFDR ) ≤ δ FDR (τFDR ; q, Dcarib )(29)

selection stage. Note that a bisection search over threshold values
can be used for finding one of τFDR .
Finally, we propose QT-LAMP-EP as the following two-stage
procedure:
Selection Stage: Find τFDR by using calibration dataset Dcarib andobtain Eselect = EFP (τFDR ; Dmain ) by using a frequent pattern mining algorithm.
Testing Stage: Conduct a multiple hypothesis test with the stepup method for Eselect with dataset Dmain and output the rejected
patterns as Ealg .
The following Theorem 5.3 states that QT-LAMP-EP strictly controls FDR for a given error rate q.
Theorem 5.3. Assume that Eselect satisfies the unbiased property∑(Ineq. (24)). With c(m) = m
i=1 (1/i), The FDR of QT-LAMP-EP is q
or smaller.
Proof. Let the total patterns be 2I . Let S ⊆ 2I be a subset ofpatterns. Let Q = V /R be the rate of false discoveries, where V and
R are the numbers of rejected true null hypotheses and rejected
null hypotheses, respectively. To prove Theorem 5.3, we use thefollowing lemma.
Lemma 5.4. (Theorem 1.3 in Benjamini and Yekutieli [6]) For arbitrary δ ∈ [0, 1], if P[pe ≤ δ | Eselect = S] ≤ δ holds for a true
hypothesis, then E[Q | Eselect = S] ≤ q holds by applying the stepup method with the BY correction at the second stage.
Note that P[pe ≤ q | Eselect = S] ≤ q holds if Eselect has the unbiased property. Therefore, the FDR is bounded as follow:∑
FDR = E[Q] =E[Q | Eselect = S]P[Eselect = S]
S ⊆2I

≤

∑

qP[Eselect = S]

= q.

∗and τFDR
defined by Eq. (26) is the minimum of such τFDR .

Proof. Let LHS(τ ) = φ(τ ) and RHS(τ ) = δ FDR (τ ; q, Dcarib ). Because ψ (0) = 1 and δ FDR (τ ; q, Dcarib ) ≤ q < 1 hold, LHS(0) >RHS(0) holds. For τ = |Dcarib |, LHS(τ ) < RHS(τ ) holds because
ψ (|Dcarib |) = a | Dcarib | and δ FDR (τ ; q, Dcarib ) = q. From the above
facts, there exists at least one τ such that LHS(τ ) > RHS(τ ) and∗LHS(τ + 1) ≤ RHS(τ + 1). By definition, τFDR
is the minimum ofsuch τFDR .
□Note that the above τFDR is not necessary unique. This uniqueness is due to the inherent nature of FDR: the corrected significancelevel δ FDR (τ ; q, Dcarib ) is not monotone to the addition of patterns.
This non-monotonicity is closely related to the following fact. In
the step-up method, non-significant patterns can become significant if we add more patterns with very small p-values. Unfortu∗ , which results a largest set of quasi-testable
nately, finding τFDR
patterns among the possibly non-unique values of τFDR , requires
an incremental search over τ [21, 25], which is not very efficientwhen no early termination is applied. In practice, we observed that∗
τFDR is usually unique and thus corresponds to τFDR
(see Figure 3
in Section 6). Here, therefore, we will look for one of τFDR instead∗of the τFDR
and use the found τFDR to select the patterns in the(By Lemma 5.4)

S ⊆2I

□

6 EXPERIMENTS
This section describes the results of computer simulations. First,
we show the results for a synthetic dataset on which we measured
the false discovery rate. Second, we show the results for eight realworld datasets to verify the statistical power of our algorithms.

6.1

Hardware and Software

We used a Linux machine with two 12-Core 2.40GHz Intel Xeon
(E5-2620 v3) CPUs and 132GB of memory for running all the experiments. LAMP-EP and QT-LAMP-EP each used an FPM algorithm as a building block. We implemented our algorithms on top
of LCM++1 , an open source C++ implementation of the LCM [29]algorithm. LCM is an award-winning2 algorithm for frequent pattern mining and is known as one of the fastest one for FPM. LCM++
is a little bit slower than the original implementation of LCM but
has improved readability; it enables each of our experiment thatinvolves from thousands to a half a million transactions to be completed within a day. For the ease of computation, we restricted our1 https://code.google.com/archive/p/lcmplusplus/
2 http://fimi.ua.ac.be/fimi04/

2.0
1.5
1.0
0.5
0.0

3.0
2.5
2.0
1.5
1.0
0.5
0.0

2

4

6

8 10

+∞

# of found patterns

×10

8 10

+∞

6
5
4
3
2
1
0

×10

4

6

6

8 10

+∞

8 10

+∞

1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

×10

2

6

8 10

+∞

# of max itemset size

# of max itemset size

# of max itemset size(d) phishing(e) ijcnn1(f) cod-rna

×10

2

4

4

6

8 10

+∞

3.0
2.5
2.0
1.5
1.0
0.5
0.0

×10

2

5

4

6

8 10

+∞

# of max itemset size

# of max itemset size(g) splatoon(h) covtype

BH
QT-LAMP-EP(BH)
QT-LAMP-EP(BY)
LAMP-EP

Figure 1: Number of discovered patterns. The horizontal
axis indicates the maximum size of the patterns to search,where +∞ indicates a limitless procedure where all patterns
are searched.
interest to closed itemsets that had no superset of the same occurrence. We used a bisection search over threshold values to find∗
τFWERand τFDR for LAMP-EP and QT-LAMP-EP, respectively.

6.2

Experimental Settings

Throughout the experiments, the significance level q was set to be
0.05 for both FWER and FDR mining.
We compared the following algorithms as to their numbers of
discoveries and corrected significance levels: EPM is a traditional
emerging pattern mining algorithm for finding EEP (a; D); we set
its minimum support to 10 for the sake of a short enough computation. LAMP-EP and QT-LAMP-EP are our methods. We tested∑
the BH and BY corrections (i.e., c(m) = 1 and mi=1 (1/i), resp.)
for QT-LAMP-EP. BH is the standard BH correction that where
the number of hypotheses m is all the possible patterns 2I . We
did not use the standard Bonferroni’s method that tests all the patterns because it always finds the same number or fewer discoveries than BH does. In QT-LAMP-EP, we used 80% of D as the main
dataset Dmain . The calibration dataset Dcarib was resampled fromthe other 20% of D until its size reaches the size of Dmain . Namely,
we spend 20% of the dataset to determine an appropriate value ofτFDR . Although this splitting generated a randomness in the algorithm, the randomness had little effect on the large databases. The
other algorithms used the entire D.

6.3

6 8 10 +∞Synthetic Dataset

To show how many true and false discoveries were found by thealgorithms listed in Section 6.2, we conducted simulations with asynthetic dataset. The dataset consisted of 100, 000 transactions
that involved itemsets with |I | = 100. 10% of the transactions

10-2
10-3
10-4
10-5
10-6
10-7

2 4

6 8 10 +

∞

10-2
10-3
10-4
10-5
10-6
10-7
10-8

6 8 10 +∞2 4

6 8 10 +

4

∞

10-1
10-2
10-3
10-4
10-5
10-6

(e) ijcnn1∞# of max itemset size(g) splatoon

10-1
10-2
10-3
10-4
10-5
10-6
10-7
10-8

2 4

6 8 10 +6 8 10 +∞# of max itemset size(c) mushroom# of max itemset size(d) phishing

2 4

6 8 10 +

10-1
10-2
10-3
10-4
10-5
10-6
10-7

(b) a1a# of max itemset size

10-2
10-3
10-4
10-5
10-6
10-7
10-8

2 4

# of max itemset size(a) svmguide3

3

4

2 4

# of max itemset size(c) mushroom

4

2

4

# of max itemset size

10-2
10-3
10-4
10-5
10-6
10-7

Corrected significance level6(b) a1a5# of found patterns# of found patterns# of found patterns(a) svmguide3
2.5

4

10-2
10-3
10-4
10-5
10-6
10-7
10-8

Corrected significance level2# of max itemset size

4

Corrected significance level

+∞

×10

Corrected significance level

8 10

6
5
4
3
2
1
0

Corrected significance level

6

3

Corrected significance level4# of max itemset size

×10

Corrected significance level

2

7
6
5
4
3
2
1
0

KDD ’17, August 13-17, 2017, Halifax, NS, Canada

Corrected significance level4# of found patterns

×10# of found patterns

1.8
1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

# of found patterns# of found patterns

Statistical Emerging Pattern Mining with Multiple Testing Correction

2 4

6 8 10 +∞# of max itemset size(f) cod-rna

QT-LAMP-EP(BH)
QT-LAMP-EP(BY)
LAMP-EP∞# of max itemset size(h) covtype

Figure 2: Corrected significance level of algorithms. The
horizontal axis is the same as in Figure 1, and the verticalaxis is the significance level. The LAMP-EP results show thecorrected significance level. The QT-LAMP-EP results showqk/(c(m)m), where k is the number of rejected hypotheses
among m ones. We omit presenting the significance of BH
because its significance level was too low to draw in the figure.
contained some of items {1, . . . , 10} and P[y | x] = 0.7 for thesetransactions. The other 90% of the transactions contained items{11, 12, . . . , 100} and P[y | x] = 0.5. The value of a was set to be
0.5, and thus, the patterns that contained items in {11, 12, . . . , 100}
were false patterns.
Table 2 shows the results of the experiment. EPM, which lacks
a statistical assessment, finds the largest set of true discoveries but
suffers a very high family-wise error rate. LAMP-EP controls both
FDR and FWER. QT-LAMP-EP with both BH and BY adjustments
factor maintains FDR at a level less than q.
Necessity of BY adjustment: The BY adjustment (i.e., c(m) =∑mi=1 1/i) is theoretically required for controlling FDR. However,in Benjamini and Yekutieli [6], it is noted that the BY adjustment
is “very often unneeded, and yields too conservative a procedure”.
This remark is consistent with our result that QT-LAMP-EP (BY)
Table 2: Performance of the procedures. TDs and FDs correspond to true and false discoveries, respectively. The results
are empirical averages over 100 runs.
algorithms# of TDs# of FDs

FDR

FWER

EPM
LAMP-EP
QT-LAMP-EP (BH)
QT-LAMP-EP (BY)

516.50166.32230.87184.103848.61
0.01
4.10
0.40

0.88
6.02e-05
0.017
2.13e-03

1.00
0.01
0.99
0.32

4

τFDR

100

5.5
5.0
4.5
4.0
3.5
3.0
2.5

tau

2.5

×10

2.0
1.5
1.0
0.5
0.0

τFDR

150

6.0

# of found patterns# of found patterns

50(g) splatoon

×10

4.5
4.0
3.5

τFDR

2.64
2.62
2.60
2.58
2.56
2.54
2.52

6.0
5.5
5.0
4.5
4.0
3.5
3.0
2.5
2.0

×10

4

τFDR

25
tau

(c) mushroom

4

25
tau

(e) ijcnn1

4

tau

25

J. Komiyama et. al.

tau

5.0

tau

×10

τFDR

τFDR

5.5

(d) phishing
3.0
2.8
2.6
2.4
2.2
2.0
1.8
1.6
1.4

3

(b) a1a5# of found patterns# of found patterns(a) svmguide3

×10# of found patterns

×10# of found patterns

1.8
1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0

# of found patterns# of found patterns

KDD ’17, August 13-17, 2017, Halifax, NS, Canada

1.50
1.49
1.48
1.47
1.46
1.45
1.44
1.43

×10

3

τFDR

25
tau

(f) cod-rna

×10

5

τFDR

25
tau

(h) covtype

Figure 3: Appropriateness of τFDR . The horizontal axis is
the minimum support τ of FPM, and the vertical axis is thenumber of discovered patterns when we conducted the BH
method on the frequent patterns EFP (τ ; Dmain ). The horizontal line indicates τFDR that is optimized by QT-LAMP-EP.
has much smaller FDR than q: even on this synthetic dataset where
the correlation among patterns is very large, the BH adjustment(i.e., c(m) = 1) alone is enough to control FDR.
Gap between the actual FDR and q: There are several reasonsfor the gap between the actual FDR and q = 0.05: First, the step-up
method actually controls FDR at a level q(m 0 /m) ≤ q, where m 0
is the number of true null hypotheses (i.e., insignificant patterns)
that are selected in the first stage [5]. Second, the discreteness of
the Binomial probability implies that P[pe ≤ δ ] is smaller than δ .
Third, since the p-values in our experiment were highly dependent,
the probability of having an extremely low p-value was not verylarge. For these reasons, it is not surprising that the actual false
discovery rate of QT-LAMP-EP was smaller than q.

6.4

class was converted into an item. The statistics of the datasets areshown in Table 3. We set the value of a to 0.3 for A1a, IJCNN1, andSVMGuide3, 0.4 for Cod-RNA, 0.5 for Mushroom, 0.55 for Covtype,
0.6 for Splatoon, and 0.8 for Phishing. These values are set so as
the number of the found patterns are modest.
Figure 1 shows the number of found patterns. The BH procedurethat takes all possible patterns into consideration performed worst.
This means our algorithms were effective at boosting the statistical power of finding patterns. For all datasets, when the maximum
size of patterns to search was large, QT-LAMP-EP with both the
BH and BY correction outperformed LAMP-EP. QT-LAMP-EP with
the BH adjustment always finds more patterns than the QT-LAMPEP with the BY adjustment; this result is natural since the BH adjustment admits a larger significance level. The advantage of QTLAMP-EP is even larger in terms of the significance level (Figure2). In the limitless case, QT-LAMP-EP (BY), which strictly controls
FDR (Theorem 5.3), admitted about a 102 to 103 times larger significance level than that of LAMP-EP. QT-LAMP-EP (BH), which
is very likely to control FDR as shown in the synthetic data, evenadmitted a 10 times larger significance level on many datasets.

6.5

Appropriateness of the Selection ThresholdTo verify the appropriateness of the selection threshold τFDR interms of its power to make discoveries, we varied the minimum
support τ and conducted a BH over all frequent patterns with τ .
Figure 3 shows the number of found patterns as a function of τ :Here, the τFDR selected by QT-LAMP-EP does not always maximize
the number of patterns but was always a very close-to-optimal
choice of τ . This result empirically supports the proposed criteria
based on quasi-testability.

6.6

Sensitivity on the Value of a

We also conducted simulations with different values of the positive label probability threshold a and no maximum pattern sizes.
Figure 4 shows the results of that experiment. The definition of
SEPM means that it natural that the number of found patterns isthe decreasing as a increases. The fact that QT-LAMP-EP finds
more pattern than LAMP-EP is consistent with all the values of aand datasets.

Real-world Datasets

The simulations involved eight datasets. Mushroom dataset was
obtained from the UCI repository3 . The Splatoon4 dataset consisted of the results of online multi-player games. We gathered
the results of about 400, 000 Splatoon matches on Stat.ink5 from
October 31, 2015 to January 30, 2016. We converted the players’
weapons, ranks, and the features related to the battle arena into
items. The other six datasets (A1a, Cod-RNA, Covtype, IJCNN1,
Phishing, and SVMGuide3) were obtained from the libSVM dataset
repository6 . The real-valued features of some datasets were divided into two classes by thresholding at the median, and each
3 https://archive.ics.uci.edu/ml/datasets/Mushroom
4 https://www.nintendo.com/games/detail/splatoon-wii-u
5 https://stat.ink/
6 https://www.csie.ntu.edu.tw/ cjlin/libsvmtools/datasets/

Table 3: Statistics of the datasets. |D| and |I | are the numbersof transactions and items (features), respectively. Avg |x | isthe averaged number of items in a datapoint.
dataset

|D |

|I |

Avg |x || D + |/ | D |svmguide3
a1amushroomphishing
ijcnn1
codrnasplatooncovtype

1,243
1605
8,124
11,05549,99059,535404,515581,012

42
174
117
813
44
16
54
64

20.9
13.9
22.0
30.0
13.0
8.0
11.0
11.9

0.24
0.25
0.48
0.56
0.10
0.33
0.50
0.49

4

0.5

a

0.6

0.7

3

0.4

×

0.8

a

0.7

0.9

4

5
4
3
2
1
0
0.55 0.60 0.65 0.70 0.75a(g) splatoon

0.4

a

0.5

0.6

(e) ijcnn1# of found patterns

×10
6

5

0.3

×10

6
5
4
3
2
1
0
0.5

4

0.6

0.7

a

0.8

0.9

×10

1.6
1.4
1.2
1.0
0.8
0.6
0.4
0.4

3

0.5

a

0.6

0.7

(f) cod-rna

5

2.0
1.0
0.5
0.0
0.6

0.7

a

0.8

0.9

QT-LAMP-EP(BH)
QT-LAMP-EP(BY)
LAMP-EP(h) covtype

Figure 4: Number of patterns found as a function of a. The
horizontal axis is the value of a, and the vertical axis is thecorresponding number of found patterns.

7This work was supported in part by JSPS KAKENHI Grant number 17K12736 and 15H05711. This work was supported in part by
the Research and Development on Real World Big Data Integration and Analysis Program of MEXT. We thank Masashi Toyoda
for letting us use their computing resources. We thank anonymous
reviewers for their insightful comments.

REFERENCES

×10
2.5
1.5

KDD ’17, August 13-17, 2017, Halifax, NS, Canada

8 ACKNOWLEDGEMENT(c) mushroom

×10

1.4
1.2
1.0
0.8
0.6
0.4
0.2
0.0
0.2

(d) phishing# of found patterns

0.6a(b) a1a5# of found patterns# of found patterns(a) svmguide3
7 10
6
5
4
3
2
1
0
0.7

0.5

# of found patterns

0.4

×10

6
5
4
3
2
1
0
0.3

# of found patterns

×10

3.0
2.5
2.0
1.5
1.0
0.5
0.0
0.3

# of found patterns# of found patterns

Statistical Emerging Pattern Mining with Multiple Testing Correction

CONCLUSION

We studied the problem of finding emerging patterns that are significant in the sense of multiple testing. We devised procedures,
called LAMP-EP and QT-LAMP-EP to control FWER and FDR. The
difficulty of multiple testing stems from the fact that the number ofhypotheses is exponential to the size of the itemset; this motivatedus to select a subset of patterns to test. In controlling FWER, as
is done in previous papers [25, 28], our procedure selects testable
hypotheses. For controlling FDR, we proposed the criteria of quasitestability that effectively eliminates most of the hypotheses by estimating the corrected significance level. Notably, ours is the first
method that controls FDR in combinatorial pattern mining withadaptive selection of hypotheses. It is not very difficult to apply
our QT-LAMP-EP to other pattern mining tasks such as statisticalassociation mining. The following are important directions of future works:
A cleverer data splitting: in deriving τFDR , we used a calibration dataset that is different from the main dataset. This restriction comes from the requirement of unbiasedness (Ineq. (24)). If
one can fully utilize the entire dataset for the testing by relaxing
the requirement, it will increase the efficiency of how the dataset
is used.
A more efficient computation of τFDR : Sugiyama et al. [25] discussed that an incremental search with an efficient early termination rule runs faster than a bisection search. An incremental searchalgorithm for QT-LAMP-EP, preferably with a one-pass modification [21], would enable QT-LAMP-EP to be applied to datasets withbillions of transactions. Alternatively, a bisection search that starts
with an estimated lower bound [30] of τFDR can be much fastersince it can avoid computing FPs with low support thresholds.

[1] Charu C. Aggarwal and Jiawei Han (Eds.). 2014. Frequent Pattern Mining.
Springer.
[2] James Bailey, Thomas Manoukian, and Kotagiri Ramamohanarao. 2002. Fast
Algorithms for Mining Emerging Patterns. Springer Berlin Heidelberg, Berlin,
Heidelberg, 39–50.
[3] Roberto J. Bayardo, Jr. 1998. Efficiently Mining Long Patterns from Databases. In
Proceedings of the 1998 ACM SIGMOD International Conference on Managementof Data (SIGMOD ’98). ACM, New York, NY, USA, 85–93.
[4] Yoav Benjamini and Yosef Hochberg. 1995. Controlling the False Discovery
Rate: A Practical and Powerful Approach to Multiple Testing. Journal of theRoyal Statistical Society. Series B (Methodological) 57, 1 (1995), 289–300.
[5] Yoav Benjamini, Abba M. Krieger, and Daniel Yekutieli. 2006. Adaptive linear
step-up procedures that control the false discovery rate. Biometrika 93, 3 (2006),
491–507.
[6] Yoav Benjamini and Daniel Yekutieli. 2001. The control of the false discovery
rate in multiple testing under dependency. Ann. Statist. 29, 4 (08 2001), 1165–
1188.
[7] C. E. Bonferroni. 1936. Teoria statistica delle classi e calcolo delle probabilità.
Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerciali diFirenze 8 (1936), 3–62.
[8] Amir Dembo and Ofer Zeitouni. 1998. Large deviations techniques and applications. Springer, New York, Berlin, Heidelberg.
[9] Guozhu Dong and James Bailey. 2012. Contrast Data Mining: Concepts, Algorithms, and Applications (1st ed.). Chapman & Hall/CRC.
[10] Guozhu Dong and Jinyan Li. 1999. Efficient Mining of Emerging Patterns: Discovering Trends and Differences. In Proceedings of the Fifth ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, San Diego, CA,
USA, August 15-18, 1999. 43–52.
[11] Peter B. Gilbert. 2005. A Modified False Discovery Rate Multiple-Comparisons
Procedure for Discrete Data, Applied to Human Immunodeficiency Virus Genetics. Journal of the Royal Statistical Society. Series C (Applied Statistics) 54, 1(2005), 143–158.
[12] Sami Hanhijärvi. 2011. Multiple Hypothesis Testing in Pattern Discovery. Springer
Berlin Heidelberg, Berlin, Heidelberg, 122–134.
[13] Yosef Hochberg. 1988. A sharper Bonferroni procedure for multiple tests ofsignificance. Biometrika 75, 4 (1988), 800.
[14] Adam Kirsch, Michael Mitzenmacher, Andrea Pietracaprina, Geppino Pucci, Eli
Upfal, and Fabio Vandin. 2012. An Efficient Rigorous Approach for Identifying
Statistically Significant Frequent Itemsets. J. ACM 59, 3 (2012), 12:1–12:22.
[15] Stéphane Lallich, Olivier Teytaud, and Elie Prudhomme. 2006. Statistical inference and data mining: false discoveries control. Physica-Verlag HD, Heidelberg,
325–336.
[16] Stephane Lallich, Olivier Teytaud, and Elie Prudhomme. 2007. Association Rule
Interestingness: Measure and Statistical Validation. Springer Berlin Heidelberg,
Berlin, Heidelberg, 251–275.
[17] Felipe Llinares-López, Mahito Sugiyama, Laetitia Papaxanthos, and Karsten M.
Borgwardt. 2015. Fast and Memory-Efficient Significant Pattern Mining via Permutation Testing. In Proceedings of the 21th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, Sydney, NSW, Australia, August
10-13, 2015. 725–734.
[18] Cécile Low-Kam, Chedy Raı̈ssi, Mehdi Kaytoue, and Jian Pei. 2013. Mining Statistically Significant Sequential Patterns. In 2013 IEEE 13th International Conference on Data Mining, Dallas, TX, USA, December 7-10, 2013. 488–497.
[19] Shihong Mao and Guozhu Dong. 2005. Discovery of Highly Differentiative Gene
Groups from Microarray Gene Expression Data Using the Gene Club Approach.
Journal of Bioinformatics and Computational Biology 03, 06 (2005), 1263–1280.
[20] Nicolai Meinshausen, Marloes H. Maathuis, and Peter Bhlmann. 2011. Asymptotic optimality of the Westfall–Young permutation procedure for multiple testing under dependence. Ann. Statist. 39, 6 (12 2011), 3369–3391.
[21] Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese. 2014.
A Fast Method of Statistical Assessment for Combinatorial Hypotheses Based on
Frequent Itemset Enumeration. Springer Berlin Heidelberg, Berlin, Heidelberg,
422–436.
[22] Petra Kralj Novak, Nada Lavrač, and Geoffrey I. Webb. 2009. Supervised Descriptive Rule Discovery: A Unifying Survey of Contrast Set, Emerging Pattern

KDD ’17, August 13-17, 2017, Halifax, NS, Canada
and Subgroup Mining. J. Mach. Learn. Res. 10 (June 2009), 377–403.
[23] Laetitia Papaxanthos, Felipe Llinares-López, Dean A. Bodenham, and Karsten M.
Borgwardt. 2016. Finding significant combinations of features in the presenceof categorical covariates. In Advances in Neural Information Processing Systems
29: Annual Conference on Neural Information Processing Systems 2016, December
5-10, 2016, Barcelona, Spain. 2271–2279.
[24] Matteo Riondato and Fabio Vandin. 2014. Finding the True Frequent Itemsets. In
Proceedings of the 2014 SIAM International Conference on Data Mining, Philadelphia, Pennsylvania, USA, April 24-26, 2014. 497–505.
[25] Mahito Sugiyama, Felipe Llinares-López, Niklas Kasenburg, and Karsten M.
Borgwardt. 2015. Significant Subgraph Mining with Multiple Testing Correction. In Proceedings of the 2015 SIAM International Conference on Data Mining,
Vancouver, BC, Canada, April 30 - May 2, 2015. 37–45.
[26] R. E. Tarone. 1990. A Modified Bonferroni Method for Discrete Data. Biometrics
46, 2 (1990), 515–522.
[27] Aika Terada, Hanyoung Kim, and Jun Sese. 2015. High-speed Westfall-young
Permutation Procedure for Genome-wide Association Studies. In Proceedings of
the 6th ACM Conference on Bioinformatics, Computational Biology and Health
Informatics (BCB ’15). ACM, New York, NY, USA, 17–26.
[28] Aika Terada, Mariko Okada-Hatakeyama, Koji Tsuda, and Jun Sese. 2013. Statistical significance of combinatorial regulations. Proceedings of the National
Academy of Sciences 110, 32 (2013), 12996–13001.
[29] Takeaki Uno, Tatsuya Asai, Yuzo Uchida, and Hiroki Arimura. 2003. LCM: An
Efficient Algorithm for Enumerating Frequent Closed Item Sets. In FIMI ’03,
Frequent Itemset Mining Implementations, Proceedings of the ICDM 2003 Workshop on Frequent Itemset Mining Implementations, 19 December 2003, Melbourne,
Florida, USA.
[30] Matthijs van Leeuwen and Antti Ukkonen. 2014.
Fast Estimation of
the Pattern Frequency Spectrum. In Machine Learning and Knowledge Discovery in Databases - European Conference, ECML PKDD 2014, Nancy,
France, September 15-19, 2014. Proceedings, Part II. 114–129.
DOI:
http://dx.doi.org/10.1007/978-3-662-44851-9 8[31] Geoffrey I. Webb. 2007. Discovering Significant Patterns. Machine Learning 68,
1 (2007), 1–33.
[32] P.H. Westfall and S.S. Young. 1993. Resampling-Based Multiple Testing: Examples
and Methods for P-Value Adjustment. Wiley.

J. Komiyama et. al.