TCS -TR-A-14-72

TCS Technical Report

Fast Statistical Assessment for Combinatorial
Hypotheses Based on Frequent Itemset MiningbyShin-ichi Minato, Takeaki Uno, Koji Tsuda,
Aika Terada, and Jun Sese

Division of Computer Science
Report Series A
April 22, 2014

Hokkaido University
Graduate School ofInformation Science and Technology
Email:

minato@ist.hokudai.ac.jp

Phone:+81-011-706-7682

Fax:+81-011-706-7682

Fast Statistical Assessment for Combinatorial
Hypotheses Based on Frequent Itemset Mining
Shin-ichi Minato∗

Takeaki Uno

Grad. School of Info. Sci. and Tech.
Hokkaido University
Sapporo 060–0814, Japan

National Institute of Informatics
Tokyo 101–8430, Japan

Koji Tsuda†

Aika Terada

Grad. School of Frontier Sciences,
The University of Tokyo
Kashiwa, 277–8561 Japan

Grad. School of Humanities and Sciences,
Ochanomizu University
Tokyo, 112–8610 Japan,

Jun Sese
Grad. School of Humanities and Sciences,
Ochanomizu University
Tokyo, 112–8610 Japan,

April 22, 2014

(Abstract) In many scientiﬁc communities using experiment databases, one of the
crucial problem is how to assess the statistical signiﬁcance (P-value) of a discovered hypothesis. Especially, combinatorial hypothesis assessment is a hard problem because it requires a multiple-testing procedure with a very large factor of
the P-value correction. Recently, Terada et al. proposed a novel method of the
P-value correction, called “Limitless Arity Multiple-testing Procedure” (LAMP),
which is based on frequent itemset enumeration to exclude meaninglessly infrequent itemsets which never be signiﬁcant. The LAMP makes much more accurate
P-value correction than previous method, and it empowers the scientiﬁc discovery.
However, the original LAMP implementation is sometimes too time-consuming forpractical databases. We propose a new LAMP algorithm that essentially executes
itemset mining algorithm once, while the previous one executes many times. Our
experimental results show that the proposed method is much (10 to 100 times)
faster than the original LAMP. This algorithm enables us to discover signiﬁcantP-value patterns in quite short time even for very large-scale databases.

∗

He also works for JST ERATO Minato Project.
He also works for JST ERATO Minato Project and National Institute of Advanced Industrial
Science and Technology.
†

1

2

1

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

Introduction

Discovering useful knowledge from large-scale databases has attracted considerable
attention during the last decade. Such knowledge discovery techniques are widely
utilized in many areas of experimental sciences, such as biochemistry, materialscience, medical science, etc. In those scientiﬁc communities using experiment
databases, one of the crucial problem is how to assess the statistical signiﬁcance (Pvalue) of a discovered hypothesis. The P-value-based assessment is one of the mostimportant factors in the paper review process of academic journals in experimental
sciences [9].
For those scientiﬁc applications, detecting a combinatorial regulation of multiple
factors is sometimes a very important issue. For example, it is well known thata key to generate iPS cells consists of the four factors of genes [13]. However,statistical assessment of a hypothesis for detected combinatorial eﬀect is a hard
problem because it requires a multiple-testing procedure with a very large factorof the P-value correction. This correction is necessary to avoid a false discovery
caused by repetition of statistical tests. When we consider the combinations ofj out of n hypotheses, the number of tested combinations increases exponentiallyas O(nj ), and if we use a naive correction method in j = 4 or more, it is tooconservative since almost all discoveries becomes extremely unlikely.
Recently, Terada et al. developed a novel P-value correction procedure, called“Limitless Arity Multiple-testing Procedure” (LAMP). Their paper [16] was published in PNAS, a leading journal in scientiﬁc community. This new procedure
excludes meaninglessly infrequent hypotheses which never be signiﬁcant. The Pvalue correction factor calculated by LAMP is much more accurate than previous
method, and it empowers the scientiﬁc discovery from the experiment databases.
However, the original LAMP implementation is sometimes too time-consuming forpractical databases, and a state-of-the-art algorithm has been desired.
The LAMP is based on the techniques of frequent itemset mining, to enumerate
all frequent itemsets included in at least σ transactions of the database for a given
threshold σ. Since the pioneering work by Agrawal et al. [1], various algorithms
have been proposed to solve this problem [7, 11, 22]. Among those state-of-the-art
algorithms, LCM (Linear time Closed itemset Miner)[20, 18, 19] by Uno et al. is
known as one of the fastest algorithm, which is based on a depth-ﬁrst traversal ofa search tree for the combinatorial space.
In this paper, we propose a fast itemset enumeration algorithm to ﬁnd the minimum support for satisfying the LAMP condition. Our new algorithm essentially
executes itemset mining algorithm once, while the previous one executes manytimes. We show that LAMP condition is a kind of threshold function which ismonotonically decreasing or increasing. We developed a general scheme to explore
the maximum frequency satisfying a given threshold function. We successfully
applied this new scheme to the LAMP condition. Those new procedures are implemented into the newest version of the LCM program. Our experimental results

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 3

show that the proposed method is much (10 to 100 times) faster than the original
LAMP. This algorithm enables us to discover signiﬁcant P-value patterns in quite
short time even for very large-scale databases.
In the rest of this paper, we ﬁrst explain the preliminaries on frequent itemset
mining algorithms. In Section 3, we then present the problem of statistical assessment for combinatorial hypotheses and the idea of LAMP. Section 4 describes our
proposed methods for ﬁnding the minimum frequency for satisfying threshold function and the LAMP condition. Section 5 shows our experimental results, followedby conclusion.

2

Preliminary

Here we start with some basic deﬁnitions of itemset databases and frequent itemset
mining.
Let E = {1, . . . , n} be a set of items. A subset of E is called an itemset. A
transaction database is a database composed of transactions where a transaction is
an itemset. A transaction database can include two or more identical transactions.
For a transaction database D, |D| denotes the number of transactions in D, and||D|| denotes the size of D, that is the sum of the size of the transactions in D, i.e.,||D|| = T ∈D |T |.
For an itemset X and a transaction database D, an occurrence of X in D is atransaction including X. The occurrence set of X, denoted by Occ(X) is the setof all occurrences of X in D. The frequency of X is the number of occurrences ofX, and is denoted by f rq(X). For a given constant number σ called minimum
support, an itemset X is called frequent. The frequent itemset mining problem isto enumerate all frequent itemsets for given database D and threshold σ.
Without confusions, an item e also represents the itemset {e}, hence f rq(e),X ∪ e and X \ e denote f rq({e}), X ∪ {e} and X \ {e}, respectively. Let κ(σ) bethe number of frequent patterns whose frequencies are no less than σ.

2.1

Frequent Itemset Mining Algorithm

The set system given by the set of frequent itemsets is anti-monotone, i.e., any
subset Y of a frequent itemset X is always frequent. Thus, enumeration of frequent
itemsets is done eﬃciently by hill-climbing algorithms, that start from the emptyset
and recursively add items unless the itemset is infrequent. In particular, depthﬁrst search type algorithms (backtracking) are known to be eﬃcient [7]. In the
backtracking way, we add an item e to the current itemset X, and explore all
itemsets generated from X ∪ e before processing X ∪ e , e = e. To avoid duplicatedsolutions such that an itemset is output twice, backtracking adds only item e >tail(X) where tail(X) is the maximum item in X. By this derive, any item Y isgenerated from the itemset Y \ tail(X), thus no duplication occurs. The pseudocode of backtracking is written as follows.

4Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

T ∈D
3 4
3
2 3 4
2
4
2 3
2
4
2 3
2
4
3 4
2

1
1
1
1
1

5
5
5

5
5

C(T )
neg
pos
pos
neg
pos
neg
pos
neg
neg

Figure 1: An example oftransaction database withpositive-negative class

Occ(X)
Occ(X)
all

pos
(σp )
3
(p − σp )1

neg(σ − σp )1(m − p − σ + σp )
4

all
(σ)
4
(m − σ)5(p)4(m − p)5(m)
9Figure 2: Contingency table (X = {2, 3})

ALGORITHM BackTracking Basic (X)
1. output X
2. for each item e > tail(X),if f rq(X ∪ e) ≥ σ then call BackTracking Basic (X ∪ e)
The most heavy computation in this algorithm is the computation of f rq(X ∪e) on Step 2 of the algorithm. There are several techniques for reducing thiscomputation. Especially, recursive database reduction techniques, such as FP-tree
representation of the database [10] and anytime database reduction [18], are quite
eﬃcient. These techniques can be applied only to depth-ﬁrst type algorithm, thus
this is why breadth-ﬁrst search type algorithm is slow compared to backtracking
on real-world data [8]. There is one more important technique so called equisupport (see for example [20] written as hypercube decomposition). For an itemset
X, we call an item e ∈ X addible if f rq(X ∪ e) = f rq(X). Eq(X) denotes theset of addible items e of X that satisfy e > tail(X). We can see that any itemset
X ∪S, S ⊆ Eq(X) satisﬁes f rq(X) = f rq(X ∪S), thus we output all these itemsets
without the computation of their frequency. Using this observation, a more eﬃcientalgorithm can be written as follows. Duplications can be avoided by not generating
recursive calls for X ∪ e with e ∈ Eq(X).
ALGORITHM BackTracking (X)
1. output X ∪ S for all S ⊆ Eq(X)
2. for each item e > tail(X), e ∈ Eq(S),if f rq(X ∪ e) ≥ σ then call BackTracking (X ∪ e)
Fast implementations of backtracking ﬁnd up to one million solutions in a second[8].

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 5

3

Statistical Assessment for Combinatorial Hypotheses

In this paper, we discuss a fast method of statistical assessment using the techniques of frequent itemset mining. First we assume the following experimental
scenario.
Now we have a scientiﬁc database including experimental results for a numberof human gene samples, and each sample shows a set of expressions of targetedfactors. Here we assume only one expression level (exist or not) for each factor.
We also have another classiﬁcation result for each sample whether it is positiveor negative, for example, the gene sample is given by a patient of breast cancer
or a normal person. Then we want to discover a combination of factors which ishighly correlated to incidence of a breast cancer. This is a quite simple scenario
and many similar cases may commonly appear in various areas of experimental
sciences. Since we assume only binary values in the database, we can represent it
as a transaction database D as shown in Fig. 1. Here we also assume a classiﬁer
C : D → {pos, neg}, which classify each transaction into a positive or a negative
one. Suppose that the database has n items for the expressions of factors, mtransactions in total, and p positive transactions.
Now we consider the assessment whether a given itemset has a strong correlation
to appear in the positive transactions. Figure 2 shows a contingency table between
the occurrence of the itemset X and the positive class of transactions. Here wenote σ = f rq(X) and σp is a number of positive transactions in Occ(X). We also
show the value of each cell when X = {2, 3} for the database shown in Fig. 1.
If the distribution of the contingency table is very biased, we may consider
this is a kind of knowledge discovery because it is unlikely happened incidentally.
The P-value represents the probability that such a biased distribution incidentally
happens. In other words, it is the probability of a false discovery, and we canaccept the statistical signiﬁcance if the P-value is smaller than a threshold α.
(α = 0.05 is often used.) The P-value is quite important in the paper review
process of academic journals in experimental sciences. Fisher’s exact test is one of
the major method for calculating the P-value for a given contingency table. This
testing method assumes that each experimental result is independent and has anequal weight. Then, the P-value is calculated by counting all combinatorial cases
to generate equally or more biased distributions of the contingency table.

3.1

P-value Correction in Multiple Tests

If we repeatedly calculate P-values for many diﬀerent factors in a same database,
we may more likely ﬁnd a factor with an incidentally low P-value. For example, if
we explore a family of hundred hypotheses each of which might be a false discovery
in p=0.05, then at least one false discovery can be found in p=0.994. It is wellknown that such multiple tests may cause serious false positive problems [14].

6Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

Hence, multiple testing correction must be used in order to avoid a false discovery.
The family-wise error rate (FWER) indicates the probability that at least one
false discovery happens in multiple tests. This rate increases at most linearly as
the number of tests increases, which motivates the Bonferroni correction [6] thatmultiplies the raw P-value by the number of tests. In other words, we must compare
the raw P-values with the adjusted threshold δ = α/k, where k is number of tests.
The Bonferroni correction is a very conservative method, which likely causes false
negative but hardly causes false positive, and often used in academic articles inexperimental sciences.
When we consider the combinations of j out of n items, the number of tested
combinations increases exponentially as O(nj ), and if we naively use Bonferroni
correction in j = 4 or more, most of the discoveries of combinatorial hypotheses
becomes extremely unlikely. However, in many practical cases, not all the combinations occur in the databases, so the ideal size of hypothesis family would bemuch smaller than the naive combinatorial number. This is a motivation of the
LAMP.

3.2

Idea of LAMP

Recently, Terada et al. developed a novel P-value correction procedure, called“Limitless Arity Multiple-testing Procedure” (LAMP) [16]. This new procedure isbased on frequent itemset enumeration for checking the two principles:(1) Meaninglessly infrequent itemsets which never be signiﬁcant can be excluded
from the number of hypotheses to be counted.
(2) Any diﬀerent itemsets having completely the same occurrence set can becounted as one hypothesis in the family.
The principle (2) means that we may enumerate only the closed itemsets, and we
can just use existing state-of-the-art algorithms of closed itemset mining [20, 18,19]. Here we explain in detail how to check the principle (1).
Suppose an itemset X with a very low frequency σ(< p). Using Fisher’s exact
test, the raw P-value cannot be smaller than

 

p
m
f (σ) =/,
(1)σσwhich means the most biased case that all Occ(X) are classiﬁed into the positiveclass. Note that f (σ) is monotonically decreasing, namely, the less frequent itemsets has the larger f (σ). This observation means that all the infrequent itemsetssatisfying f (σ) > δ can never be signiﬁcant, regardless of the classiﬁcation result.
Thus, we can exclude such itemsets from the number of hypotheses to be counted.
This is the key idea of the LAMP.

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 7

Figure 3: An example of a breadth-ﬁrst searchLet κc (σ) be the number of all closed itemsets not less frequent than σ. Then,the adjusted threshold of Bonferroni correction can be written as δ = α/κc (σ).
Now our subject is to ﬁnd the maximum frequency σmax which satisﬁes:αα
and f (σmax ) ≤.
(2)f (σmax − 1) >κc (σmax )κc (σmax + 1)

3.3

Current Implementation of LAMP

In the above inequation of the LAMP condition, the left side f (σ − 1) is monotonically decreasing and the right side α/κc (σ) is monotonically increasing in the range
1 ≤ σ ≤ p. Thus, a naive idea is to enumerate all the itemsets in an order from thehighest σ to the lowest one, and we may stop the enumeration procedure when thecurrent σ ﬁrst satisﬁes the condition. This is well known as the breadth-ﬁrst search
approach used in the “Apriori-type” [1] frequent itemset mining algorithms. Figure 3 illustrates the execution steps of a breadth-ﬁrst search on the same databasein Fig. 1. This approach requires a large memories to store all the itemsets at thecurrent frontier for each step, and in general, it is not very eﬃcient for practicalsize of databases.
The current implementation of the original LAMP [15] is not using a breadthﬁrst search due to memory limitation, but just calls the LCM algorithm repeatedly,
as follows.
ALGORITHM Original LAMP (α)
1. σ := maxe∈E (f rq(e))
2. if σ < p then σ := p // p: number of positive transactions.
3. k := κc (σ)// call LCM algorithm to compute κc (σ).
4. if f (σ − 1) ≤ α/k then σ := σ − 1; goto 3
5. output (σ, k)This method requires less memory, but sometimes very time-consuming since
the LCM may be called more than thousand times for practical cases, and it may
take a day or more. The current LAMP has a bottleneck in computation time,and some eﬃcient algorithms are desired.

8

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

Figure 4: The scheme of support increase algorithm

4

Proposed Algorithms

4.1

A Threshold Function for the LAMP condition

Let θ(x, y) : (N × N) → {true, f alse} be a given threshold function such that
θ(x, y) = true implies θ(x , y) = true for any x < x, and that θ(x, y) = true
implies θ(x, y  ) = true for any y  > y. In other words, θ(x, y) is monotonicallydecreasing for x and increasing for y. Now we consider a general scheme of theitemset mining problems, to ﬁnd the largest σ satisfying θ(σ, κ(σ)). Note that
κ(σ) is monotonically decreasing for 1 ≤ σ ≤ m, thus θ(σ, κ(σ)) is monotonicallydecreasing for the same 1 ≤ σ ≤ m. We call the largest σ maximum frequency forthe threshold function, and denote it by σmax .
For examples of such threshold functions, the function for top-k mining can bedeﬁned as θ(x, y) = true iﬀ y ≥ k. We then explore the maximum frequency σmax
for satisfying θ(σ, κ(σ)). It means that the k-th most frequent itemsets have thefrequency σmax .
Here we deﬁne a threshold function for the LAMP condition as follows.
θ(x, y) = true iﬀ f (x − 1) >

α
y

(3)

As discussed in Section 3, we can conﬁrm that this threshold function is decreasing
for x and increasing for y. We then explore the maximum frequency σmax for satisfying θ(σ, κ(σ))1 . Hereafter we assume that θ(x, y) satisﬁes the above condition.

1

Our implementation uses κc (σ) instead of κ(σ) for the LAMP condition in equation (2). The
number of closed itemsets are also monotonically decreasing for the frequency, so we can use κc (σ)
as well. This is discussed in Section 5.2

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 9

4.2

Support Increase Algorithm

For the computation of the maximum frequency for θ(σ, κ(σ)), a natural way is
to compute κ(σ) by frequent itemset mining with the minimum support σ, for all
possible candidates σ, one by one. This computation takes long time when σ issmall since κ(σ) is huge, thus we should compute θ(σ, κ(σ)) in the decreasing orderof σ. This is the basic scheme of the original LAMP [16] shown in the previous
section. However, this needs long computation time since many frequent itemset
mining processes are executed. In this paper, we propose a new algorithm thatbasically executes mining algorithm just once.
Suppose that we are given a function θ(σ, κ(σ)). For a frequency σ, if wefound some k and conﬁrmed both k ≤ κ(σ) and θ(σ, k) = true, then we getθ(σ, κ(σ)) = true, since θ(x, y) is increasing for y. In such a case, we can see
σmax ≥ σ, and in particular, σmax = σ if θ(σ + 1, κ(σ + 1)) = f alse.
Suppose that we execute a backtracking algorithm for minimum support σ tocheck θ(σ, κ(σ)), and during the mining process we found k frequent itemsets satisfying θ(σ, k). From the assumption of the function θ(x, y), we can then conﬁrm
that θ(σ, κ(σ)) = true, thus we next. We are then motivated to re-execute thebacktracking with σ := σ + 1 to check θ(σ + 1, κ(σ + 1)). However, in the current
execution, we already found possibly many itemsets of frequency σ + 1, and in thepast search process, we never missed such itemsets. This implies that the execution
until the current iteration can be skipped. We just need to remove all itemsets offrequency σ from the set of past solutions that have already been found, and canre-start the backtracking algorithm with σ := σ + 1. This implies that even if westart from very small σ having huge κ(σ), we can increase it during the mining
process for reducing the computation time.
A backtracking algorithm with this idea can be written as follows. Figure 4
illustrates the scheme of this algorithm. The algorithm start with σ = 1 and S = ∅where S is a program variable for storing a set of frequent itemsets we alreadyfound. Let S[σ] be the subset of itemsets in S whose frequency is σ.
ALGORITHM SupportIncrease (X)global variable: σ, S (initialized σ = 1, S = ∅)1. S := S ∪ {X}
2. if θ(σ, |S|) = true then S := S \ S[σ], σ := σ + 1; go to 2
3. for each item e > tail(X),if f rq(X ∪ e) ≥ σ then call SupportIncrease (X ∪ e)
Let σ ∗ and S ∗ be the resulted values of σ and S after the execution of thealgorithm.
Theorem 1. There hold σ ∗ = σmax + 1 and |S ∗ | = κ(σmax + 1).

10

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

Proof. Since the algorithm never decreases σ, the itemsets of frequencies no lessthan σ ∗ cannot be missed, and are included in S ∗ . Since no itemset of frequency
less than σ ∗ is in S, we have |S ∗ | = κ(σ ∗ ). We then prove σ ∗ = σmax + 1 bycontradiction.
Suppose that θ(σ ∗ , κ(σ ∗ )) = true holds. Let us consider the iteration in which
the last itemset is inserted to S. Since θ(σ ∗ , κ(σ ∗ )) = true holds, the latterpart of step 2 is not executed in this iteration, otherwise σ is increased so thatθ(σ ∗ , κ(σ ∗ )) = f alse holds. Thus, we have σ = σ ∗ in the iteration. After step 1,
there is no more itemset of frequency no less than σ ∗ that has not been found, thus
we have |S| = κ(σ). This leads that θ(σ ∗ , κ(σ ∗ )) = f alse, and contradicts to theassumption.
We next suppose that θ(σ ∗ − 1, κ(σ ∗ − 1)) = f alse holds. Let us consider theiteration in which σ is increased to σ ∗ . In the iteration, the latter part of step 2
is executed, and thus we have θ(σ ∗ − 1, |S|) = true. Since |S| is always no greaterthan κ(σ), it implies that θ(σ ∗ − 1, k) = true holds for some k ≤ κ(σ ∗ − 1). This
contradicts to the assumption.
The algorithm terminates in short time if |S[σ]| is relatively small compared to|S| on average. Particularly, if |S[σ]| ≤ q always holds, we can bound the numberof iterations by q ·σmax +|S ∗ |, since the algorithm removes at most q ·σmax itemsets
from S. In the real-world data, we can naturally expect that |S[σ]| is much smaller
than |S|. In fact, we could conﬁrm it in our computational experiments.
The computation of |S[σ]| is done eﬃciently by using a heap that extracts theminimum frequency itemset from S. The computation then takes O(|S[σ]| log |S|)
time. This computation time should be short than the computation time of an
iteration, thus the total computation is expected not to increase much. However,
if |S| is large on average, or κ(σ ∗ ) is very large, the algorithm may take very longtime. In the next section, we focus on such cases, and propose an eﬃcient method
for reducing the computation time.

5

Fast Implementation

The bottleneck of the computation of the algorithm in the previous section comesfrom the large size of the heap for S. This eﬀects not only the computation time
but also the memory usage. We here propose to use histogram counters insteadof the heap. The histogram counters c[σ  ] are prepared for each frequency σ  , andkeep the number of itemsets in S whose frequency is σ  . By using the histogram
counters, we can compute |S| by summing up the counters for all σ  ≥ σ. Hence,
we do not have to use the heap for storing the itemsets. The point is that we cancompute |S \ S[σ]| by summing up the counters for all σ  ≥ σ + 1. This implies
that we have to do nothing about the update of S in step 2, thus computation
will be smart. Another important point is the memory usage. The number of thehistogram counters can be bounded by the number of transactions, thus it is only
a linear factor to the input data size.

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 11

The use of histogram counters gives us one more advantage; we can use theequi-support technique. In each iteration with equi-support, we ﬁnd many frequent
itemsets, 2|Eq| itemsets in exact, with the same frequency, at once. We can increase
the counter for these in one step by adding 2|Eq| to the counter. This saves thecomputation time of 2|Eq| −1 iterations, thus the equi-support technique drasticallyshortens the total computation time. The algorithm is then written as follows.
ALGORITHM EquiSupportIncrease (X)global variable: σ, c[] (initialized σ = 1, c[i] = 0 for each i)
1. c[f rq(X)] := c[f rq(X)] + 2|Eq(X)||D|
2. if θ(σ, i=σ c[i]) = true then σ := σ + 1; go to 2
3. for each item e > tail(X),if f rq(X ∪ e) ≥ σ then call EquiSupportIncrease (X ∪ e)
Theorem 2. After the execution of algorithm EquiSupportIncrease, σ ∗ = σmin + 1
holds, and c[σ  ] = κ(σ  ) − κ(σ  + 1) holds for all σ  ≥ σ ∗ .
Proof. We assume that the variable S is simultaneously computed as algorithm
SupportIncrease during the execution of EquiSupportIncrease. Instead of
insertion of itemsets to S, EquiSupportIncrease increases a counter of the frequencyof the itemsets. Thus, in any iteration, c[σ  ] = |{Y ∈ S|f rq(Y ) = σ  }| holds. We
|D|
|D|
then have i=σ c[i] = |S|, thus θ(σ, i=σ c[i]) = true if and only if θ(σ, |S|) = true.
This implies that the computation of σ in EquiSupportIncrease is the same as
SupportIncrease, thus the statement holds.
Theorem 3. Let P be the itemset enumerated by EquiSupportIncrease. The
number of iterations needed to enumerate P by EquiSupportIncrease is equal tothat by backtracking algorithms with equi-support technique.

5.1

Calculating Family Size of the LAMP

Theorem 1 states that |S ∗ | = κ(σmax + 1), namely, the histogram counters holds
κ(σmax + 1) after the execution of the proposed algorithm. However, our ﬁnal
purpose of the LAMP is to know κ(σmax ), which is the hypothesis family size for
the P-value correction. An easy way to know κ(σmax ) is calling LCM algorithm
once again with σmax . This is not so bad since calculating κ(σmax ) is less timeconsuming than ﬁnding σmax , however, we can avoid such two-pass executions if
we maintain not only c[σ] but also c[σ − 1] during the backtracking procedure.
This can be done by a very small modiﬁcation as shown below.

12Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Sese

ALGORITHM EquiSupportIncreaseLAMP (X)
global variable: σ, c[] (initialized σ = 1, c[i] = 0 for each i)
1. c[f rq(X)] := c[f rq(X)] + 2|Eq(X)||D|
2. if θ(σ, i=σ c[i]) = true then σ := σ + 1; go to 2
3. for each item e > tail(X),if f rq(X ∪ e) ≥ σ − 1 then call EquiSupportIncreaseLAMP (X ∪ e)
In this modiﬁcation, the total number of backtracking will be a little increase
because the condition of the recursive call in Step 3 is relaxed to one smallerfrequency. This overhead is relatively small in the total computation time, and it
is a reasonable cost for computing κ(σmax ) correctly.

5.2

Generalization to Other Patterns

Many patterns have been considered in the past researches of pattern mining.
Our algorithm works on many of these patterns. The requirement is that the
backtracking algorithm does work, i.e., the set of frequent patterns satisﬁes somemonotone properties. For example, closed itemset mining accepts our algorithm,
and also maximal frequent itemset mining also does. Closed itemsets have the antimonotone property, and maximal frequent itemsets can be enumerated by backtracking. They can be solved by our implementation. Sequence pattern mining[21], frequent tree mining [4, 5], frequent geograph mining [3], maximal motif mining [2], frequent graph mining [12], and other basic patterns also satisfy monotone
property, so that we can construct a search tree in which parents have frequencies no smaller than their children, thereby backtracking works. They accepts thecounter implementation when the maximum possible frequency is not huge, andalso Equi-support technique when it works. Our basic scheme of the algorithm isquite strong so that we can use it in many kinds of pattern mining problems.

6

Computational Experiments

We implemented our new LAMP algorithm by modifying LCM ver. 5 that isavailable on the author’s website [17]. This is the latest version of LCM algorithm
that won in FIMI04 competition of fast pattern mining implementations [8]. The
fundamental issues of the implementation is described in [18]. We note that themodiﬁcation is quite small such that we added/modiﬁed only up to 30 lines of C
codes. We could not observe any relatively large diﬀerence of computational performance after the modiﬁcation of the LCM. For the comparison, we also evaluatedthe original version of LAMP [15]. The original LAMP repeatedly calls the same
LCM ver. 5, as shown in Section 3 of this paper.
Table 1 presents the speciﬁcations of the database instances used in our experiments. “yeast” and “human cancer” are the real gene databases, which areFast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 13

Table 1: Speciﬁcations of databases
database

n

m

yeast
breast cancer
mushroom(3-119)
T10I4D100K
BMS-WebView-1
BMS-WebView-2
BMS-POS

102
397
117
870
497
3340
1657

6074
12773
8124
10000059602
77512
515597

Bonferroni (family size)
max-arity: 2 max-arity: 3 max-arity: 45253
1769534426528
79003
10428793
1029883108
6903
2670337680738378885109751225 23816205920
12375320460993
2532110133
55794706209953450 5.182 × 1012
1373653758258113 3.137 × 1011

Table 2: Experimental Results of new and original LAMPpσmaxκc (σmax ) new LAMP orig. LAMP
(family size)time(sec)time(sec)
yeast
530
4
303
0.005
0.463
breast cancer
1129
8375033636.53886.315mushroom(3-119)
3916
20
98723
0.740
141.327
T10I4D100K(p-50)
50000
211070803.092
799.738
T10I4D100K(p-10)
10000
74833005.714
820.756
BMS-WebView-1(p-50) 29801
22
17066012.349122.303
BMS-WebView-1(p-10)5960
895943533.351248.055
BMS-WebView-2(p-50) 38756
22
209016
1.813
229.406
BMS-WebView-2(p-10)7751
8665411
5.655
246.278
BMS-POS(p-50)
2577993174373743
580.32178801.858
BMS-POS(p-10)51560
11702878145
4513.052
50883.609
Intel Core i7-3930K 3.2GHz, 64GB Mem, 12MB Cache, OpenSuSE 12.1
databasealso used in the original LAMP paper [16]. The others are well known benchmark datasets of FIMI competition and KDD CUP 2000, available from the FIMI
repository [8]. The columns n and m show the numbers of items and transactions,
respectively. Here we show the hypothesis family sizes of traditional Bonferroni
correction if we limit the maximum arity (the number of items in a combination)
up to 2, 3, and 4. We can see that the family size grows exponentially to the arity,and that it seems too large for meaningful knowledge discovery in practical size of
databases.
Table 2 shows our experimental results of the new and original versions of
LAMP. The columns p, σmax and κc (σmax ) indicate the number of positive transactions, the maximum frequency for the LAMP condition, and the number of frequent
closed itemsets (hypothesis family size by LAMP), respectively. Here we used thesigniﬁcance threshold α = 0.05. Note that the datasets “yeast” and “human cancer” have a positive-negative classiﬁcation for each transaction. “mushroom” does
not have such information but it has the two speciﬁc items which mean poisonous

14

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Seseor edible mushroom, so we deﬁne the poisonous one as positive, and the rest of
117 items are assessed as the combinatorial hypotheses. For the other datasets, we
did not specify a particular classiﬁcation item, but we assumed the two cases thatthe positive transactions share 50% and 10% in the whole data. The experimental results show that the new LAMP is much faster than the original LAMP, asmuch as 10 to 100 times in many cases, and it can work well for practical size of
databases with hundreds of items and thousands of transactions. We can also seethat the family sizes given by LAMP are often smaller than ones by the traditional
Bonferroni with the max-arity up to only 3. This is very powerful in practicalapplications because the LAMP has no arity limit up to n, and this correction still
guarantees the family-wise error rate bounded by α.

7Conclusion

In this paper, we proposed a fast itemset enumeration algorithm to ﬁnd the frequency threshold satisfying the LAMP condition. We developed a general scheme
to explore the maximum frequency satisfying a monotonic threshold function. We
successfully applied this new scheme to the LAMP condition. The procedure is
implemented into the newest LCM program. Our experimental results show thatthe proposed method is much (10 to 100 times) faster than the original LAMP andthat it can work well for practical size of experiment databases. The new enumeration algorithm solved the bottleneck of the LAMP for practical applications, anduseful for various areas of experimental sciences.
We may have several kinds of future work. As well as multiple-testing correction, computing the P-values for a particular hypothesis is also time-consuming
procedure. It will be useful if we can eﬃciently compute the P-values for many
combinatorial hypotheses and can discover the best or top-k signiﬁcant one. In
this paper, we considered Fisher’s exact test, however, there are some other typesof the P-value calculation, such as χ-squared test and Mann-Whitney test, andwe may consider diﬀerent statistical models. In addition, here we assumed only
the binary-valued databases, but extension to non binary-valued databases is alsointeresting problem. As described in Section 5.2, our basic scheme of the algorithm
is quite strong so that we can use it in many kinds of pattern mining problems.
Anyway, our result demonstrated that the state-of-the-art enumeration techniquesof pattern mining can be a useful means to many kinds of statistical problems.

References[1] R. Agrawal, T. Imielinski, and A. N. Swami. Mining association rules between
sets of items in large databases. In P. Buneman and S. Jajodia, editors, Proc.
of the 1993 ACM SIGMOD International Conference on Management of Data,
Vol. 22(2) of SIGMOD Record, pages 207–216, 1993.

Fast Statistical Assessment for Combinatorial Hypotheses Based on Frequent Itemset Mining 15[2] Hiroki Arimura and Takeaki Uno. A polynomial space and polynomial delay
algorithm for enumeration of maximal motifs in a sequence. In Xiaotie Dengand Ding-Zhu Du, editors, Algorithms and Computation, volume 3827 of Lecture Notes in Computer Science, pages 724–737. Springer Berlin Heidelberg,
2005.
[3] Hiroki Arimura, Takeaki Uno, and Shinichi Shimozono. Time and space eﬃcient discovery of maximal geometric graphs. In Vincent Corruble, Masayuki
Takeda, and Einoshin Suzuki, editors, Discovery Science, volume 4755 of Lecture Notes in Computer Science, pages 42–55. Springer Berlin Heidelberg,
2007.
[4] Tatsuya Asai, Kenji Abe, Shinji Kawasoe, Hiroshi Sakamoto, Hiroki Arimura,and Setsuo Arikawa. Eﬃcient substructure discovery from large semistructured data. IEICE Trans. on Information and Systems, E87-D(12):2754–
2763, 2004.
[5] Tatsuya Asai, Hiroki Arimura, Takeaki Uno, and Shin-ichi Nakano. Discovering frequent substructures in large unordered trees. In Gunter Grieser, Yuzuru
Tanaka, and Akihiro Yamamoto, editors, Discovery Science, volume 2843 of
Lecture Notes in Computer Science, pages 47–61. Springer Berlin Heidelberg,
2003.
[6] C. Bonferroni. Teoria statistica delle classi e calcolo delle probabilita. Pubblicazioni del R Istituto Superiore di Scienze Economiche e Commerciali diFirenze (Libreria Internazionale Seeber, Florence, Italy), 8:3–62, 1936.
[7] B. Goethals.
Survey on frequent pattern mining,
http://www.cs.helsinki.ﬁ/u/goethals /publications/survey.ps.

2003.

[8] B. Goethals and M. J. Zaki. Frequent itemset mining dataset repository, 2003.
Frequent Itemset Mining Implementations (FIMI’03),
http://ﬁmi.cs.helsinki.ﬁ/.
[9] Nature Publishing Group. Nature guide to authors: Statistical checklist.
http://www.nature.com/nature/authors/gta/Statistical checklist.doc.
[10] J. Han, J. Pei, and Y. Yin. Mining frequent patterns without candidate
generation. In In Proc of the 2000 ACM SIGMOD international conference
on Management of data, pages 1–12, 2000.
[11] J. Han, J. Pei, Y. Yin, and R. Mao. Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Mining and Knowledge Discovery, 8(1):53–87, 2004.
[12] Akihiro Inokuchi, Takashi Washio, and Hiroshi Motoda. An apriori-basedalgorithm for mining frequent substructures from graph data. In DjamelA.
Zighed, Jan Komorowski, and Jan Zytkow, editors, Principles of Data Mining

16

Shin-ichi Minato, Takeaki Uno, Koji Tsuda, Aika Terada, and Jun Seseand Knowledge Discovery, volume 1910 of Lecture Notes in Computer Science,
pages 13–23. Springer Berlin Heidelberg, 2000.
[13] Keisuke Okita, Tomoko Ichisaka, and Shinya Yamanaka. Generation of
germline-competent induced pluripotent stem cells. Nature, 448:313–317,
2007.
[14] Mark J. van der Laan Sandrine Dudoit. Multiple Testing Procedures with
Applications to Genomics. Springer New York, 2008.
[15] Aika Terada, Mariko Okada-Hatakeyama, Koji
Sese.
LAMP limitless-arity multiple-testing
http://a-terada.github.io/lamp/.

Tsuda, and Junprocedure,
2013.

[16] Aika Terada, Mariko Okada-Hatakeyama, Koji Tsuda, and Jun Sese. Statistical signiﬁcance of combinatorial regulations. Proceedings of National Academyof Sciences of United States of America, 110(32):12996–13001, 2013.
[17] T.
Uno.
Programcodes
http://research.nii.ac.jp/˜uno/codes.htm.

oftakeakiuno.

[18] T. Uno, M. Kiyomi, and H. Arimura. LCM ver.2: eﬃcient mining algorithms
for frequent/closed/maximal itemsets. In Proc. IEEE ICDM’04 Workshop
FIMI’04 (International Conference on Data Mining, Frequent Itemset Mining
Implementations), 2004.
[19] T. Uno, M. Kiyomi, and H. Arimura. LCM ver.3: collaboration of array,
bitmap and preﬁx tree for frequent itemset mining. In Proc. Open Source
Data Mining Workshop on Frequent Pattern Mining Implementations 2005,2005.
[20] T. Uno, Y. Uchida, T. Asai, and H. Arimura. LCM: an eﬃcient algorithm forenumerating frequent closed item sets. In Proc. Workshop on Frequent Itemset
Mining Implementations (FIMI’03), 2003. http://ﬁmi.cs.helsinki.ﬁ/src/.
[21] J. Wang and J. Han. Bide: Eﬃcient mining of frequent closed sequences. In
Proc of 4th IEEE International Conference on Data Mining (ICDM 2004),
pages 79–90, 2007.
[22] M. J. Zaki. Scalable algorithms for association mining. IEEE Trans. Knowl.
Data Eng., 12(2):372–390, 2000.