Ambiguous Frequent Itemset Mining and
Polynomial Delay Enumeration
Takeaki Uno1 and Hiroki Arimura2
1

National Institute of Informatics,
2-1-2, Hitotsubashi, Chiyoda-ku, Tokyo 101-8430, Japan, uno@nii.jp
2
Graduate School of Information Science and Technology, Hokkaido University, Kita
14 Nishi 9, Sapporo 060-0814, Japan, arim@ist.hokudai.ac.jp

Abstract. Mining frequently appearing patterns in a database is a basic
problem in recent informatics, especially in data mining. Particularly,
when the input database is a collection of subsets of an itemset, called
transaction, the problem is called the frequent itemset mining problem,
and it has been extensively studied. The items in a frequent itemset
appear in many records simultaneously, thus they can be considered to
be a cluster with respect to these records. However, in this sense, thecondition that every item appears in each record is quite strong. We
should allow for several missing items in these records. In this paper,
we approach this problem from the algorithm theory, and consider themodel that can be solved efficiently and possibly valuable in practice.
We introduce ambiguous frequent itemsets which allow missing items intheir occurrence records. More precisely, for given thresholds θ and σ, anambiguous frequent itemset P has a transaction set T , |T | ≥ σ, such thaton average, transactions in T include ratio θ of items of P . We formulate
the problem of enumerating ambiguous frequent itemsets, and propose
an efficient polynomial delay polynomial space algorithm. The practical
performance is evaluated by computational experiments. Our algorithm
can be naturally extended to the weighted version of the problem. The
weighted version is a natural extension of the ordinary frequent itemset toweighted transaction databases, and is equivalent to finding submatrices
with large average weights in their cells. An implementation is available
at the author’s homepage3

1

Introduction

The frequent pattern mining problem is to find patterns frequently appearing in agiven database. It is one of the central tasks in data mining, and has been a focusof recent informatics studies. Particularly, when the database D is a collectionof transactions4 where a transaction is a subset of an itemset I = {1, . . . n}, andthe patterns to be found are also subsets of itemsets, the problem is called thefrequent itemset mining problem[1, 4, 11, 12].
34

http://research.nii.ac.jp/˜uno/index.html
In the literature, a transaction is often defined by a pair of an item subset and its
ID. However, we omit the ID since it has no effect on the arguments in this paper.

Precisely, a transaction of D including P is called an occurrence of P , andthe set of occurrences of P is denoted by Occ(P ). we define the frequency of anitemset by |Occ(P )|, and say an itemset is a frequent itemset if its frequency is
no less than the given threshold value σ, called minimum support. The frequency
is often called support, and σ is called the minimum support.
Frequent pattern mining is often used for data analysis. For data so huge thathumans can not get any intuition from an overview of it, the frequent patternmining is a useful way to capture the features of the data’s features, both in a
global sense and in a local sense. However, we often encounter difficulties in trying
to use the frequent pattern mining on real-world data. One difficulty is that data
is often incorrect or has missing parts. Such errors mean that some records thatshould include a pattern P do not include it, thus P may be overlooked because
its frequency appears to be too low. A way to deal with this difficulty is toconsider an ambiguous inclusion relation whereby we consider that a transaction
T includes a pattern P if most items of P are included in T .
There are several studies on the frequent pattern mining with ambiguous
inclusions. In some contexts, these patterns are called fault-tolerant frequent
itemsets[5, 7–9, 16]. In some of these studies[16], ambiguous inclusion is definedsuch that an itemset P is included in a transaction T if |P ∩ T |/|P | ≥ θ. Given
this definition, the family of frequent itemsets is not always anti-monotone, thus
the usual apriori based algorithms are not output sensitive in the sense of timecomplexity. On the other hand, the authors introduced an inclusion allowing
a constant number of missing items, i.e., |P \ T | ≤ θ. This does not violate
the monotonicity, thereby admits both apriori and backtrack with many related
techniques developed for frequent itemset mining. However, it has a disadvantagethat a transaction can miss only few items of large itemsets whereas almost all
small itemsets will be frequent.
In some studies[5, 7–9], they considered that it is a fault if an item of theitemset is not included in a transaction, and treat mining pairs of an itemset
and a transaction set such that there are few faults between their elements.
Their algorithms find pairs with few faults, but they are not always minimum
solutions.
In this paper, we address the problem from the algorithmic point of view, andmodel the problem in a different way. In the other words, the goal of this paper
is to investigate the most simple and useful model of ambiguous frequency whichallows fast computation. In the existing practice-based approach, the designed
model often allows no fast algorithm. Heuristic approaches lose the completeness and exactness of the algorithm. For developing fast algorithms, we consider
another model for ambiguous frequency.
For an itemset P and a transaction T , the inclusion ratio is the ratio of itemsof P included in T , i.e., |T ∩ P |/|P |. For an itemset P and a transaction set T ,the average inclusion ratio of T for P
P is defined by the average of the inclusion ratio of transactions in T , i.e., ( T ∈T |T ∩ P |)/(|T ||P |). By representing
the inclusion between transactions and items by matrix, the average inclusion
ratio corresponds to the density of the submatrix induced by the items andtransaction database D

A: 1,2,4
B: 1,2
C: 1,3
D: 2,3

Inclusion ratio of A for itemset {1,3,4,5} = 1/2
inclusion ratio of B for itemset {1} = 1
average inclusion ratio of {A,B,C} for itemset {1} = 1
for density threshold θ= 0.65,
AmbiOcc({1,3}) = {A,B,C}
for density threshold θ= 0.65,
a maximum co-occurrence set of {1,2,3} = {A,B,C,D}

Fig. 1. Examples of average inclusion ratio and maximum occurrence setstransactions. When the average inclusion ratio is high, the items co-occur in thetransactions, or the transactions co-occur in the items. For a density threshold
θ, a transaction set of the largest size having average inclusion ratio no less than
θ is called the maximum co-occurrence set for P . Note that any maximum cooccurrence set can be obtained by choosing transactions in decreasing order of
their inclusion ratio. The size of the maximum co-occurrence set is called the
maximum co-occurrence size of P , and is denoted by cov(P ). We denote thelexicographical minimum maximum co-occurrence set by AmbiOcc(P ). Some
examples are shown in Figure 1.
For the minimum support threshold σ, an itemset is called an ambiguous
frequent itemset if its maximum co-occurrence size is no less than σ. The problem
in this paper is formulated as follows.
Ambiguous Frequent Itemset Enumeration Problem
Input: transaction database D, minimum support σ, density threshold θ
Output: all ambiguous frequent itemsets in D
We propose a polynomial delay polynomial space algorithm, and show thepractical performance by computational experiments. Note that an algorithm ispolynomial delay if the computation time between any two consecutive solutions
is polynomial in the input size.
If we represent the inclusion relation by a bipartite graph, an ambiguous frequent itemset and its corresponding transaction set corresponds to a vertex set
inducing a dense bipartite subgraph, which is a quasi bipartite clique. Enumerating dense subgraphs whose edge density is no less than a threshold value canbe done in polynomial delay polynomial space[14]. However, since an ambiguous
frequent itemset has a lower bound for transaction sets, and identifies the same
itemsets with different transaction sets, a direct application of the algorithm toour problem is not polynomial delay.
The existence of a polynomial delay algorithm for the enumeration problemof ambiguous frequent itemset is not trivial, since as we will show, simple algorithms involve an NP-complete problem in each iteration. The framework of thealgorithm in this paper is motivated from the enumeration algorithm for pseudocliques[14]. We introduce an adjacency relation with respect to a removal ofan item between ambiguous frequent itemsets, and implicitly construct a treeshaped traversal route on the relation. Our algorithm searches traverses the tree

in a depth-first search manner, so that the computation time is polynomial delay.
To best of our knowledge, this is the first result of even an output polynomial
time algorithm for this problem. The ambiguous frequency and our algorithm
can be naturally extended to a weighted version, in a straightforward manner.

2

Polynomial Delay Algorithm

The frequent itemset enumeration problem is, from the viewpoint of complexity theory, an easy problem. The reason is that the frequency has a monotone property, thus obviously any frequent itemset can be obtained by iteratively adding items to the emptyset by passing through only frequent itemsets.
The repeated addition admits any ordering of items, hence we can efficiently
avoid the duplications by adding items only in increasing order of their indices.
Thus, we can construct a backtrack algorithm of a polynomial delay polynomial
space. Precisely, the computation time for each frequent itemset is linear in thesize of the database,i.e., O(||D||), where ||D|| is the size of database D, i.e.,
P||D|| = |D| + T ∈D |T |. The space complexity is optimal, that is, O(||D||).
However, the family of ambiguous frequent itemsets does not have this monotone property. For the database D in Figure 1, θ = 65% and σ = 4, we cansee that cov({1, 2, 3}) = 4, as obtained by transaction set {A, B, C, D}, thereby{1, 2, 3} is an ambiguous frequent itemset. However, the maximum co-occurrence
size of its subset {1, 3} is 3, obtained by transaction set {A, B, C}, thereby {1, 3}
is not an ambiguous frequent itemset. Since the monotonicity is not held, a
straightforward backtrack algorithm is not applicable to the enumeration.
We approach the problem in another way. For itemset P 6= ∅, we define e∗ (P )by the item e ∈ P that minimizes |AmbiOcc(P ) ∩ Occ({e})|. Ties are broken bychoosing the minimum index one. Using e∗ , we introduce an adjacency relation
among ambiguous frequent itemsets, and construct an implicit traversal route.
Lemma 1. For any itemset P 6= ∅, there exists an item e ∈ P satisfying cov(P \{e}) ≥ cov(P ).
Proof. First we observe that the average inclusion ratio of AmbiOcc(P ) for P
is given by the average of |AmbiOcc(P ) ∩ Occ({e})|/|AmbiOcc(P)|, since theP|AmbiOcc(P )∩Occ({e})|average inclusion ratio of AmbiOcc(P ) for P is e∈P. From(|P |−1)×|AmbiOcc(P )|the observation, the average inclusion ratio of AmbiOcc(P ) for P \ {e∗ (P )} is
the average of |AmbiOcc(P ) ∩ Occ({e})|/|AmbiOcc(P )| among P \ {e∗ (P )}, thus
it is no less than the average inclusion ratio of AmbiOcc(P ) for P . It means thatcov(P \ {e∗ (P )} is no less than cov(P ), thus e∗ (P ) satisfies the condition to be
the item e in the statement.
ut
For an itemset P 6= ∅, we define the parent P rt(P ) of P by P \ {e∗ (P )}.
From Lemma 1, P \ {e∗ (P )} is an ambiguous frequent itemset. Particularly,
cov(P rt(P )) ≤ cov(P ). The cardinality of P rt(P ) is exactly one smaller than P ,thus the parent child relation induced by P rt is acyclic. Since every ambiguous
frequent itemset other than the emptyset has a parent, the relation inducesθ＝ 66%, σ= 4
A: 1,3,4,7
B: 2,4,5,
C: 1,2,7
D: 1,4,5,7
E: 2,3,6
F: 3,4,6

φ
1
1,4

2

3

4

3,4 4,5

7
4,7

1,7

1,4,5 1,3,4 1,4,7 3,4,7 4,5,7 1,2,7 1,3,7 1,5,7
1,2,4,7 1,3,4,7 1,4,5,7Fig. 2. Example of an enumeration tree

a rooted tree spanning all ambiguous frequent itemsets. We call this tree theenumeration tree of ambiguous frequent itemsets. An example of the enumeration
tree is shown in Figure 2. By traversing the tree, we can find all ambiguous
frequent itemsets without duplication.
To perform a depth-first search on the enumeration tree, we need to find all
children of the current visiting ambiguous frequent itemset. By recursively finding the children, we can perform a depth-first search without using additional
memory on visited vertices. This ensures the polynomiality of the memory complexity. The algorithm can be written as follows.
ReverseSearch(P )1. Output P
2. for each e 6∈ P
2-1. if P ∪ {e} is an ambiguous frequent itemset then
2-2. if P rt(P ∪ {e}) = P then2-3.
call ReverseSearch (P ∪ {e})The computation of the average inclusion ratio and the parent of P ∪ {e} in
2-1 and 2-2 can be done in O(||D||) time. They are executed at most n times
in an iteration, thus the computation in an iteration except for those in therecursive calls is bounded by O(||D|| × n). This algorithm outputs an ambiguous
frequent itemset in each iteration, thus the computation time per ambiguous
frequent itemset is O(||D|| × n). The depth of the enumeration tree is boundedby n, thus we obtain the following theorem.
Theorem 1. For given a transaction database D, minimum support thresholdσ, and density threshold θ, ambiguous frequent itemsets in D can be enumerated
in polynomial delay with polynomial space in terms of ||D||. In particular, thecomputation time for one ambiguous frequent itemset is O(n||D||) where n is thenumber of items included in some transactions in D.

3

Improvements for Efficient Practical Computation

For practical huge databases, the computation time O(||D|| × n) is quite long. It
is not easy to reduce the time complexity, but possible to improve the practical
efficiency by using at typical structures of actual datasets. The heavy tasks ineach iteration with respect to itemset P is the computation of cov(P ∪ {e}) ande∗ (P ∪ {e}) for each e. Both need O(n||D|) time, and we will describe techniques
to reduce the computation time for each. Note that the computation of cov(P )is maybe heavier since we have to compute e∗ (P ∪ {e}) only when P ∪ {e} is an
ambiguous frequent itemset.
We define Occ=h (P ) by the set of transactions not including exactly h items
in P , i.e., Occ=h (P ) = {T | T ∈ D, |P \ T | = h}. Similarly, Occ≤h (P ) ={T | T ∈ D, |P \ T | ≤ h}. For the computation of cov(P ∪ {e}), we have toobtain Occ=h (P ∪ {e}) for each e and h, in increasing order of h. We can use
the following property and lemma for efficient computation.
Property 1. [13] For a transaction T included in Occ=h (P ) for some h, 0 ≤ h ≤ k,
T ∈ Occ=h (P ∪ {i}) holds if T includes i. Otherwise, T ∈ Occ=h+1 (P ∪ {i}).
Lemma 2. [13] (a) Occ=0 (P ∪ {i}) = Occ=0 (P ) ∩ Occ({i}), and (b) Occ=h (P ∪{i}) = (Occ=h (P ) ∩ Occ({i})) ∪ (Occ=h−1 (P ) \ Occ({i})) for any h ≥ 1.
From these, we can see that Occ=h (P ∪ {e}) for all h are obtained by moving
transactions of Occ=h (P ) ∩ Occ({e}) to Occ=h+1 (P ). This takes O(|Occ({e})|)time, which is expected to be small when the input database is sparse. To compute Occ=h (P ) ∩ Occ({e}), a method called delivery is efficient[11–13].
We briefly explain the framework of Delivery. An example is shown in Fig.
3. First, we prepare an empty bucket for each item e. Next, for each transaction
T in Occ=h (P ), we “insert T into the bucket of e for each item e ∈ T ”. After
performing this operation for all transactions in Occ=h (P ), the content of thebucket of e is equal to Occ=h (P ∪ {e}). The pseudo code of occurrence deliver is
described as follows. The code inputs a transaction set S, then sets bucket[e] toS ∩ Occ({e}) for all e. We suppose that the bucket of any item e is initialized,
and thus is empty at the beginning.
Delivery(S)
1. for each T ∈ S do
2. for each i ∈ T , insert T into bucket[i]Lemma 3. [12, 11] Delivery computes S ∩ Occ({e}) for all e in O(||S||) time.
Let k ∗ (P ) be the smallest h satisfying AmbiOcc(P ) ⊆ Occ≤h (P ).
Lemma 4. If P ∪ {e} is a child of P , k ∗ (P ∪ {e}) ≤ k ∗ (P ) + 1 holds andOcc≤k∗ (P ) (P ) includes a maximum co-occurrence set of P ∪ {e}.

Proof. From Lemma 2, we have Occ≤k∗ (P ) (P ∪ {e}) ⊆ Occ≤k∗ (P ) (P ) ⊆Occ≤k∗ (P )+1 (P ∪ {e}). This means that Occ≤k∗ (P ) (P ) is constructed by taking|Occ≤k∗ (P ) (P )| transactions from Occ≤k∗ (P )+1 (P ∪ {e}) in decreasing order ofthe inclusion ratio for P ∪ {e}. If P ∪ {e} is a child of P , we have cov(P ∪{e}) ≤ cov(P ) ≤ |Occ≤k∗ (P ) (P )|. Thus, Occ≤k∗ (P ) (P ) includes a maximum cooccurrence set of P ∪ {e}, and k ∗ (P ∪ {e}) ≤ k ∗ (P ) + 1.
utThis lemma implies that for the computation of cov(P ∪{e}), we have to lookonly at the transactions included in Occ≤k∗ (P )+1 (P ). This reduces the computation time to O(||Occ≤k∗ (P )+1 (P )||), where ||Occ≤k∗ (P )+1 (P )|| is the sum of thesizes of transactions in Occ≤k∗ (P )+1 (P ).
We next state a lemma to P
determine k ∗ (P ∪ {e}) efficiently. Let T h(P, k) =θ × (|P | + 1) × |Occ≤k (P )| − T ∈Occ≤k (P ) |T ∩ P |. If and only if |Occ≤k (P ) ∩Occ({e})| ≥ T h(P, k), the average inclusion ratio of Occ≤k (P ) for P ∪ {e} isno less than θ. For any transactions T ∈ Occ=h (P ) and T 0 ∈ Occ=h+1 (P ), theinclusion ratio of T for P ∪ {e} is always no less than that of T 0 for P ∪ {e}.
Thus, we have the following property.
Lemma 5. Suppose that P ∪{e} is a child of P . Then, both |Occ({e})∩Occ≤k−1 (P )|≥ T h(P, k − 1) and |Occ({e}) ∩ Occ≤k (P )| < T h(P, k) hold if and only if|Occ≤k−1 (P )| < cov(P ∪ {e}) ≤ |Occ≤k (P )|.
Note that the statement holds for a unique k since T h(P, k) is monotone
decreasing for the increase of k. From the above lemma, we compute |Occ({e}) ∩Occ≤k−1 (P )| in increasing order of k from k = 1, then find each item e satisfying
the condition of Property 5 with k, and check whether P ∪ {e} is a child of P
or not by computing AmbiOcc(P ∪ {e}). The algorithm based on this method is
as follows.
ALGORITHM FindAllChildren(P )1. compute T h(P, k) for each k = 0, ..., k ∗ (P ) + 1
2. for k = 0 to k ∗ (P )3. compute Occ=k (P ) ∩ Occ({e}) for each e
4. for each e s.t. |Occ({e}) ∩ Occ≤k−1 (P )| ≥ T h(P, k − 1) do (for each e if k = 0)5.
if |Occ({e}) ∩ Occ≤k (P )| < T h(P, k) then6.
if σ ≤ |AmbiOcc(P ∪ {e})| ≤ |AmbiOcc(P )| then7.
if P rt(P ∪ {e}) = P then P ∪ {e} is a child
8. end for9. end for
Step 6 computes AmbiOcc(P ∪ {e}), then obtain P rt(P ∪ {e}) by computing
AmbiOcc(P ∪{e})∩Occ{e0 } for each e0 ∈ P ∪{e}. At the time of computing thesevalues, we already have computed Occ≤k∗ (P ∪{e})−1 (P )∩Occ≤k∗ (P ∪{e}) (P ∪{e}),thus we have to compute only Occ=k∗ (P ∪{e}) (P ) ∩ Occ({e}).
Now the computation time in each iteration with respect to P is(a) O(||Occ≤k∗ (P )+1 (P )||) for computing cov(P ∪ {e}) for all e, and (b)O(||Occ=k∗ (P ∪{e}) (P )||) for each e such that P ∪ {e} is an ambiguous frequent
itemset. In practical datasets, it is expected that P ∪{e} is an ambiguous frequentA: 1,2,5,6,7,9
B: 2,3,4,5
C: 1,2,7,8,9
D: 1,7,9
E: 2,3,7,9
F: 2,7,9

1: A,C,D
2: A,B,C,E,F
3: B,E
4: B
5: A, B
6: A
7: A,C,D,E,F
8: C
9: A,C,D,E,F
Fig. 3. Example of delivery

itemset only for few e’s. Otherwise the number of ambiguous frequent itemsets
is huge so that we can not enumerate them in a practically short time, andwe can not deal with huge output itemsets. Therefore, we can expect that (b)is not larger so much than (a), thus the computation time for an iteration isO(||Occ≤k∗ (P )+1 (P )||), which is relatively shorter than O(n||D||).

4

Weighted Ambiguous Frequent Itemset

In practical transaction databases, items of each transaction often has several
different weights. For example, POS data includes the number or the price ofeach item purchased by a customer. In experiments in industry or natural science,each cell or item may have a kind of intensity. Such a database can be regarded
as a matrix of item columns and transaction rows such that each cell has a value.
One may be naturally motivated to find submatrices with a large average weightof cells. These locally heavy submatrices correspond to important objects suchas clusters, and have applications in knowledge discovery and data engineering.
We define the problem as follows. We suppose that each item e of a transaction T has a weight w(T, e). For an itemset P and a transaction
T , we defineP
the average weight w(T, P ) of T with respect to P by ( e∈P ∩T w(T, e))/|P |.
For
P a set T of weighted transactions, we define the average weight w(T , P ) by
( T ∈T w(T, P ))/|T |. When we are given a weight threshold θ, we define theweighted maximum co-occurrence size of P by the maximum size of a transaction set having average weight no less than θ. For a given support threshold σ,
an itemset is called a weighted ambiguous frequent itemset if its weighted maximum co-occurrence size is no less than σ. The weighted version of the ambiguous
frequent itemset enumeration problem is to output all weighted ambiguous frequent itemsets. Given these definitions, we obtain a similar neighboring relation
between weighted ambiguous frequent itemsets.
Theorem 2. For given a weighted transaction database D, weight threshold θ,and minimum support threshold σ, all weighted ambiguous frequent itemsets canbe enumerated in polynomial delay and polynomial space. In particular, the computation time is O(||D||n) for each, and the space complexity is linear in the
input size, where n is the number of items in D.
The method described in the above sections is not directly applicable toimprove the practical efficiency of the weighted version of our algorithm. The

reason is that Properties 1 and 2 are not valid for the weighted version. To
compute the weighted maximum co-occurrence size of P ∪{e}, we need to get thetransactions T in the order of w(T, P ∪ {e}). If w(T, P ∪ {e}) is large, then either
w(T, P ) or w(T, {e}) has to have a large value. Thus, by getting transactions
having large average weights with respect to either P or {e}, we can efficiently
compute the weighted maximum co-occurrence size.

5

Hardness Result for Branch-and-Bound Approaches

We show that a hardness result for simple approaches to answer the questionthat why we need a sophisticated enumeration scheme. In a typical branchand-bound algorithm, we may choose an item e and divide the enumeration
problem into two subproblems; the enumeration problem of ambiguous frequent
itemsets including e, and the problem for itemsets not including e. The divisionof the problem is done recursively until the problem includes a unique solution(ambiguous frequent itemset). In this approach we have to know the existenceof solutions to the restricted problem, otherwise we will divide problems having
no solution recursively, thereby exponentially many times.
The following theorem states that this problem is NP-complete. Therefore,
we observe that it is hard to get a polynomial delay algorithm by typical branchand-bound since we have to solve an NP-complete problem in each iteration.
Theorem 3. For given a transaction database D, itemset S, density threshold
θ, and minimum support threshold σ, the problem of answering whether an ambiguous frequent itemset including S exists or not, is NP-complete.
Proof. Suppose that we are given a transaction database D, a minimum support
threshold σ, and a constant number k, and going to check for the existence ofan itemset of size at least k that is included in at least σ transactions. This is
known to be NP-complete[17]. Let I be the set of items included in transactions
in D, and I 0 be a set of items of size |D| × |I| satisfying I ∩ I 0 = ∅. We choose
an item e∗ from I 0 .
We now construct a transaction database D0 = {T ∪ (I 0 \ {e∗ })|T ∈ D}. Let
X be a subset of I, T be a transaction set of D, and T 0 be the transaction setof D0 corresponding to T . Then, X is a frequent itemset of D and T = Occ(X)
if and only if the average inclusion ratio of T 0 for X ∪ I 0 is strictly larger than(|D|×|I|−1)/(|D|×|I|). In particular, when |X| = k, the average inclusion ratiois (|D|×|I|+k−1)/(|D|×|I|+k). Here we set θ = (|D|×|I|+k−1)/(|D|×|I|+k).
Then, X is a frequent itemset of D of size at least k if and only if X ∪ I 0 is an
ambiguous frequent itemset of D0 . Therefore we have the theorem.
ut6Computational Experiments

In general, the practical computation time of an algorithm often differs from thetheoretical upper bound. The reason is that the computation time is dominatedBMS-WebView2

1000000

LCM time
1.0 number
1.0 time
1.0 time/M
0.9 number
0.9 time
0.9 time/M
0.8 number
0.8 time
0.8 time/M

100000
10000

time(sec)/number

1000
100
10
1
0.1
1%

0.50%

0.30%

0.15%

0.05%

support10000000

Mushroom

1000000

LCM time
1.0 number
1.0 time
1.0 time/M
0.9 number
0.9 time
0.9 time/M
0.8 number
0.8 time
0.8 time/M

100000
10000
1000

time(sec)/number

10000000

100
10
1
0.1
0.01
80%

70%

60%

50%

40%

30%

support20%

Fig. 4. Computation time and #solutions on BMS-WebView and Mushroom

0.9 max
0.9 prt
0.9 occ
0.8 max
0.8 prt
0.8 occ

10

ratio

1

0.1
1%

0.70% 0.50% 0.40% 0.30% 0.20% 0.15%

support100

Mushroom

10

0.9 max
0.9 prt
0.9 occ
0.8 max
0.8 prt
0.8 occ

ratio

BMS-WebView2

100

1
80%

70%

60%

50%

40%

30%

supportFig. 5. Comparison of accessed items on BMS-WebView and Mushroom

by the “average”, but the theoretical upper bound looks only at the worst case.
To see the gap and to be a help for the practical use, we show the results ofsome computational experiments.
The C code is used for the implementation. The computer used in the experiments was a notebook PC with a Pentium M 1.1GHz processor with 768MB
memory. The experiments were done on cygwin which is an emulator of Linux
environments on Windows. The implementation is a simpler version of our algorithm, which compute the parent in a straightforward way. The reason is tochoose a simpler version is to see the performance of a simple implementation,
which would help for coding. The implementation is available at the author’s
homepage; http://research.nii.ac.jp/˜uno/index.html.
We examined two practical datasets taken from FIMI repository[6]. The firstis BMS-WebView2 with about 3,300 items and 77,000 transactions. The average size of transactions is 4.6, thus the dataset is quite sparse. The second isMushroom with about 120 items and 8,000 transactions. The average size oftransactions is 23, thus the dataset is not sparse.
We run the implementations with the thresholds θ = 0.8, 0.9 and 1.0. Since
we could not find any implementation for the ambiguous frequent itemset enumeration, we have no comparison to other implementations. Instead of this, we
compare the performance to that of an ordinary frequent itemset enumeration
algorithm LCM[12, 11]. Since the frequent itemset enumeration is a special caseof our problem, it can be considered as a kind of upper bound of the performanceof the ambiguous frequent itemset enumeration.

The results are shown in Fig. 4. The left is BMS-WebView2, and the rightis Mushroom. The horizontal axis is for minimum support threshold, and thevertical axis is for computation time, computation time for 1 million (ambiguous)frequent itemsets, and the number of output itemsets, written in log scales.
The computation time of our algorithm increases as the decrease of minimum
support, but the computation time per one million itemsets does not change drastically. It seems to change as the change of average size of Occ({e}). Comparing
to the ordinary frequent itemset mining algorithm, the performance of our algorithm is not so good. One of the reason is that the cost for computing parentsof the candidate children. A simple duplication check by storing the discovered
itemsets in memory will accelerate the computation when the output itemsets
are few. The other reason is that in the ordinary frequent itemset mining, we canuse the conditional database for the current operating itemset, which includes
only items larger than the maximum item in the current operating itemset andare frequent in the database induced by the occurrence of the current operating itemset. Usually the number of items in the conditional database is muchsmaller than the number of items in the original database, thus the computation
is faster. To reduce the difference on the computation time, further techniques
for the efficient computation are still needed. The number of ambiguous frequent
itemsets increases drastically by the decrease of density threshold. In practice,
we should use a threshold slightly smaller than 1.0.
We also looked at several statistics on the experiments in Figure 5. “max”
means the ratio of ambiguous frequent itemsets and the number of maximal
ambiguous frequent itemsets to which no item addition yields an ambiguous frequent itemset. “prt” shows the ratio of the number of accessed items between
a straightforward algorithm and the sophisticated algorithm proposed in thispaper, and “occ” indicates that between delivery for computing the frequencies
of all additions of items, and delivery for computing the parent. As we can see,these ratio increase as the increase the number of solutions. Thus, we can expect
the decrease of the number of solutions by outputting only maximal ones. The
speedup is also expected by introducing our sophisticated parent computation,
but the effect will be limited. The big ratio of “occ” implies that the big gap between computation time of our algorithm and ordinary frequent itemset mining.
It also implies that more practical improvements are needed.

7

Conclusion and Future Work

We formulated the enumeration problem of ambiguous frequent itemsets, andproposed a polynomial delay polynomial space algorithm. The algorithm is naturally extended to a weighted version. The experimental performance for practical
datasets is acceptable, but improvements on practical performance is a crucial
future work. Another interesting research topic is extending the technique toother frequent pattern mining problems.

Acknowledgments
This research was supported by Grant-in-Aid for Scientific Research of Japan,“Developing efficient and accurate algorithms for large-scale data processing in
genome science”, and a joint-research fund of National Institute of Informatics.

References
1. R. Agrawal, H. Mannila, R. Srikant, H. Toivonen, A. I. Verkamo, Fast Discovery
of Association Rules, In Advances in Knowledge Discovery and Data Mining, pp.
307–328, 1996.
2. T. Asai, K. Abe, S. Kawasoe, H. Arimura, H. Sakamoto, S. Arikawa, Efficient
Substructure Discovery from Large Semi-structured Data, SDM 2002, 2002.
3. D. Avis and K. Fukuda, Reverse Search for Enumeration, Disc. App. Math. 65,
pp. 21–46, 1996.
4. R. J. Bayardo Jr., Efficiently Mining Long Patterns from Databases, SIGMOD98,
pp. 85–93, 1998.
5. J. Besson, C. Robardet, and J. F. Boulicaut, Mining Formal Concepts with aBounded Number of Exceptions from Transactional Data, KDID 2004, LNCS 3377,
pp. 33–45, 2005.
6. B. Goethals, the FIMI repository, http://fimi.cs.helsinki.fi/, 2003.
7. J. Liu, S. Paulsen, W. Wang, A. Nobel, J. Prins, Mining Approximate Frequent
Itemsets from Noisy Data,” ICDM05, pp. 721-724, 2005
8. J. K. Seppanen and H. Mannila, Dense Itemsets, SIGKDD 2004, 2004.
9. W. Shen-Shung and L. Suh-Yin, Mining Fault-Tolerant Frequent Patterns in Large
Databases, ICS2002, 2002.
10. M. Takeda, S. Inenaga, H. Bannai, A. Shinohara, and S. Arikawa, Discovering
Most Classificatory Patterns for Very Expressive Pattern Classes, LNCS 2843, pp.
486–493, 2003.
11. T. Uno, T. Asai, Y. Uchida, H. Arimura, An Efficient Algorithm for Enumerating
Closed Patterns in Transaction Databases, LNAI 3245, pp. 16–31, 2004.
12. T. Uno, M. Kiyomi, H. Arimura, LCM ver. 2: Efficient Mining Algorithms forFrequent/Closed/Maximal Itemsets, IEEE ICDM’04 Workshop FIMI’04, 2004.
13. T. Uno, H. Arimura, An Efficient Polynomial Delay Algorithm for Pseudo Frequent
Itemset Mining, LNAI 4755, pp. 219–230, 2007
14. T. Uno, An Efficient Algorithm for Enumerating Pseudo Cliques, ISAAC 2007,
LNCS 4835, pp. 402–414, 2007.
15. J. T. L. Wang, G. W. Chirn, T. G. Marr, B. Shapiro, D. Shasha and K. Zhang,
Combinatorial pattern discovery for scientific data: some preliminary results, SIGMOD 94, pp. 115–125, 1994
16. C. Yang, U. Fayyad, P. S. Bradley, Efficient Discovery of Error-Tolerant Frequent
Itemsets in High Dimensions, SIGKDD 2001, 2001.
17. M. J. Zaki and M. Ogihara, Theoretical foundations of association rules, In 3rd
ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery, 1998.