An Efficient Polynomial Delay Algorithm for
Pseudo Frequent Itemset Mining
Takeaki Uno1 , 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 informatics, especially in data mining. Particularly, when
the input database is a collection of subsets of an itemset, the problem
is called the frequent itemset mining problem, and has been extensively
studied. In the real-world use, one of difficulties of frequent itemset mining is that real-world data is often incorrect, or missing some parts. It
causes that some records which should include a pattern do not have it.
To deal with real-world problems, one can use an ambiguous inclusion
relation and find patterns which are mostly included in many records.
However, computational difficulty have prevented such problems frombeing actively used in practice. In this paper, we use an alternative inclusion relation in which we consider an itemset P to be included in an
itemset T if at most k items of P are not included in T , i.e., |P \ T | ≤ k.
We address the problem of enumerating frequent itemsets under thisinclusion relation and propose an efficient polynomial delay polynomial
space algorithm. Moreover, To enable us to skip many small non-valuable
frequent itemsets, we propose an algorithm for directly enumerating frequent itemsets of a certain size.

1

Introduction

The frequent pattern mining problem is to find patterns frequently appearing ina given database. It is one of the central tasks in data mining, and has been afocus of recent informatics studies. Particularly, when the database is a collectionof transactions and the patterns to be found are also subsets of itemsets, theproblem is called the frequent itemset mining problem[1, 4, 10–12]. Precisely, wedefine the frequency of an itemset by the number of transactions including thepattern, and say an itemset is a frequent itemset if its frequency is no less than
the given threshold value σ, called minimum support.
Frequent pattern mining is often used especially for data analysis. For data sohuge that humans can not get any intuition from an overview of it, the frequent
pattern mining is a useful way to capture the features of the data’s features, bothin a global sense and in a local sense. However, in the real world use, we often
encounter difficulties in trying to use the frequent pattern mining on real-world
data. One difficulty is that data are often incorrect or missing parts. Such errors
mean that some records that should include a pattern P do not include P , thus
P may be overlooked because its frequency appears to be too low. A way todeal with this difficulty is to consider 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–8, 14]. In some of these studies, ambiguous inclusion is defined suchthat an itemset P is included in a transaction T if the fraction of items of P
included in T is no less than a given threshold θ, i.e., |P ∩ T |/|P | ≥ θ[14]. 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.
If an item of the itemset is not included in a transaction, then it can beconsidered to be a fault. Some studies, such as Boulicaut et al., Liu et al., andSeppanen et al.[5–8], treat mining pairs of an itemset and a transaction set suchthat there are few faults between their elements. When the size of the transaction
set is large, we can regard the itemset as a frequent pattern with ambiguous
inclusions. Many mining algorithms have been devised for solving both problems,
but enumeration difficulties prevent them from having the completeness that
ensures that they output exactly all frequent patterns.
On the other hand, in sequence pattern mining and text mining, ambiguous matching is used to define the occurrence of a pattern, i.e., if a pattern ishomogeneous to a substring of the input string, then we regard that the pattern appears at the position. Such patterns are called degenerate patterns insome contexts, especially in genome sciences, and several algorithms have been
proposed[9, 13].
There are possibly several models for such ambiguous inclusions. In this paper, we define our ambiguous relation with a constant k that a pattern P isincluded in a transaction (or pattern) T if at most k items are not included in
T . In this paper, we address the problem of enumerating all frequent itemsets
under this inclusion relation, for given a transaction database, minimum support σ, and k. When σ is large, such as 90% of the number of transactions, theproblem can be considered to be one to find combinations of items i1 , . . . , ihsuch that at least h − k items are included in 90% of transactions, thus suchcombinations characterize the database. These combinations can also be usedas rules separating the database from other database, thus has applications tolearning theory and practice.
For the frequent itemset mining with our ambiguous relation, we propose apolynomial delay polynomial space algorithm. To best of our knowledge, thisis the first result of even output polynomial time algorithm for this problem.
Although the algorithm is polynomial time, we still encounter a problem inthe real-world applications, that is, quite many uninteresting small patterns are
frequent in our ambiguous inclusion relation. We can avoid this problem bydirectly enumerating all frequent patterns of given size l, and we propose an
efficient algorithm for this task.
The organization of the paper is as follows. We introduce several notations
and notions concerning to our ambiguous inclusion in Section 2, and propose abasic algorithm for frequent itemset mining under the condition of he ambiguous
inclusion in Section 3. The algorithm is improved in Section 4. Section 5 describes
an algorithm for directly enumerating those of size l, and Section 6 is for theconclusion.

2

Preliminary

Let an itemset I be a set of items 1, . . . n. A transaction database D is a collectionof transactions where a transaction is a subset of I 3 . We denote the number oftransactions in D by |D|, and the size of D by ||D||. Here the size of
PD is thesum of |D| and the sizes of the transactions in D, i.e., ||D|| = |D| + T ∈D |T |.
Note that ||D|| is not defined in the usual sense. The aim of this definition is toconsider the computation time for empty transactions, which is O(1). Hereafter,
we fix the database D for the input of the algorithm.
A pattern P is a subset of itemset I. The largest item in P is called thetail of P and is denoted by tail(P ). A transaction of D including P is called an
occurrence of P . We denote the set of occurrences of P by Occ(P ). The frequency
f rq(P ) of a pattern P is defined by the number of transactions including P , i.e.,|Occ(P )|. Given a transaction database D and constant number σ, a patternwith frequency no less than σ is called a frequent itemset. The frequency is often
called support, and σ is called the minimum support. The problem of finding
all frequent itemsets for given a transaction database and minimum support iscalled the frequent itemset enumeration problem4 .
For a constant k and two patterns P, T ⊆ I, we write P ⊆k T if |P \ T | ≤k holds. We call the binary relation ⊆k the k-pseudo inclusion relation. Fora pattern P , a transaction T is a k-pseudo occurrence of P if P ⊆k T . We
denote the set of k-pseudo occurrences of P by Occ≤k (P ). Particularly, theset of transactions satisfying |P \ T | = k is denoted by Occ=k (P ). We have
Occ(P ), Occ=k (P ) ⊆ Occ≤k (P ). See the example in Fig. 2. We define the kpseudo frequency of P by |Occ≤k (P )|, and denote it by f rqk (P ). A k-pseudo
frequent itemset is a pattern P such that its k-pseudo frequency is no less thanσ. Here, we define our problem as follows.
3

In the literatures, a transaction is often defined by a pair of an item subset and its
ID. However, we will here omit the ID since ID has no meaning in the arguments inthis paper.
4This problem is also called frequent itemset/pattern mining/discovery. Usually, theterms mining and discovery do not require the output to be complete, thus here
we use the term enumeration which is used in the problem of outputting all thesolutions completely.

A: 1,2,4,5,6
B: 2,3,4
C: 1,2,7
D: 1,5
E: 2,3,7
F: 2,7
G: 4
H: 6

Occ≤0({2,7})
Occ≤1({1,2,4})
Occ=1({1,3,7})= {E,F}= {A,B,C}= {C,E}

Occ≤2({1,2,4,7}) = {A,B,C,E,F}
Occ=2({1,2,4,7}) = {B,C,E,F}
Occ≤2({1,2,4,7} U {3})= Occ≤1({1,2,4,7}) U (Occ=2({1,2,4,7})∩ Occ({3}))= {A,E}

Fig. 1. Examples of pseudo occurrences and update by addition of an item

Pseudo Frequent Itemset Enumeration Problem
Input: transaction database D, minimum support σ, constant k
Output: all k-pseudo frequent itemsets in D
If an algorithm terminates in polynomial time for both the input size and theoutput size, the algorithm is called output polynomial. Output polynomiality is a
popular measure of the theoretical efficiency of the algorithm. If the computation
time between any two consecutive output solutions is bounded by a polynomialof the input size, the algorithm is called polynomial delay. If an algorithm ispolynomial delay, the computation time is linear in the number of outputs, andhence better in practice. If the memory usage of the algorithm is bounded by apolynomial of the input size, the algorithm is called polynomial space. Here ourgoal is to develop an efficient polynomial delay polynomial space algorithm forsolving the pseudo frequent itemset enumeration problem.

3

Basic 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. Although anaive implementation may produce duplicate solutions, we can avoid duplications by using tail extension. For a frequent itemset P , a pattern obtained from
P by adding an item larger than the tail of P is called a tail extension of P . By
generating frequent patterns only via tail extensions, each pattern is generated
only from the pattern obtained by removing its tail, thus we can enumerate
all frequent itemsets without duplicates. A backtrack algorithm generates tailextensions in a depth-first manner, and thus is a polynomial time delay polynomial space algorithm. Precisely, the computation time for each frequent itemset
is linear in the size of the database, i.e., O(||D||). The space complexity is also
optimal, that is, O(||D||).
Regarding the practical use of frequent itemset enumeration, the number of
frequent itemsets is usually not so large compared to the input size, but the
input size is usually large. Thus, linear time in the input size for each solution

A: 1,2,5
B: 1,4
C: 1,2
D: 1,3
E: 2,3
F: 2
G: 1

1,2,3
1,2

1,4

1,3
1

1,5

2,3

2,4

2,5

2

3

4

5

Fig. 2. An example of backtrack algorithm execution for minimum support σ = 4

is too long. To reduce the practical computation time, several techniques havebeen proposed. One of the most efficient techniques is called database reduction.
Consider the following operation: Remove all items included in less than σtransactions, and unify the same transactions into one transaction. Then, thedatabase shrinks, and its size becomes small. We can further reduce the size byusing trie or prefix tree. This operation is called database reduction. Database
reduction performs well in practice, especially when σ is large, Moreover, if we
apply database reduction to conditional databases to recursively reduce theirsizes, we can further reduce the computation time. Here a conditional databaseis the database restricted to items larger than the tail of the current operating
pattern P and transactions including P , which is the input of an iteration withrespect to P . This technique is called iterated database reduction.
These techniques can be applied to pseudo frequent itemsets in a similar way.
We begin with the following proposition to see the monotonicity.
Proposition 1. For any patterns P and P 0 satisfying P ⊆ P 0 , Occ≤k (P 0 ) ⊆Occ≤k (P ) holds.
The statement holds since any transaction T ∈ Occ≤k (P 0 ) does not include
at most k items in P . From this proposition, we can see that the family of kpseudo frequent itemsets satisfies anti-monotonicity. Hereafter, we assume thatthe minimum support is from 1 to |D| thus the emptyset is always k-pseudo
frequent. For a k-pseudo frequent itemset P , let the children set of P , denotedby CHD(P ), be the set of items i such that i > tail(P ) and P ∪ {i} is k-pseudo
frequent. The monotone property leads to the following backtrack algorithm. By
calling Backtrack(∅), we can enumerate all k-pseudo frequent itemsets.
backtrack(P )1. Output P
2. Compute CHD(P )3. for each i ∈ CHD(P ) call backtrack (P ∪ {i})It is easy to see the correctness of this algorithm. Figure 3 shows an executionof the backtrack algorithm. Each iteration inputs a k-pseudo frequent itemset
P , outputs P , computes the k-pseudo frequency for all tail extensions of P toobtain CHD(P ), and generates recursive calls for each item in CHD(P ). Thus,any iteration outputs a k-pseudo frequent itemset, and the computation timefor each k-pseudo frequent itemset is bounded by the maximum computation
time of an iteration. Computing k-pseudo frequency of each tail extension takes
O(||D||) time thus the computation time of an iteration is O(n||D||). This canbe shortened as follows.
Suppose that we have Occ=0 (P ), ..., Occ=k (P ) for the current processing pattern P . Here we consider the computation of Occ=0 (P ∪ {i}), ..., Occ=k (P ∪ {i})for all i > tail(P ). First, we prove the following proposition.
Proposition 2. 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}).
Proof. Since T ∈ Occ=h (P ), T does not include exactly h items of (P ∪ {i}) if
T includes i, and exactly h items otherwise. Then the statement follows.
ut
Now we have the following lemma.
Lemma 1. The following two equations hold,(a) Occ=0 (P ∪ {i}) = Occ=0 (P ) ∩ Occ({i})(b) Occ=h (P ∪ {i}) = (Occ=h (P ) ∩ Occ({i})) ∪ (Occ=h−1 (P ) \ Occ({i})) for any
h ≥ 1.
Proof. Any transaction T ∈ Occ=h (P ∪ {i}), 0 ≤ h ≤ k, includes at least h − 1
and at most h items of P . This implies that T is included in Occ=h (P ) or
Occ=h−1 (P ) only when h > 0. On the other hand, from Proposition 2, we have
Occ=h (P ∪ {i}) ∩ Occ=h (P ) = Occ=h (P ) ∩ Occ({i}), andOcc=h (P ∪ {i}) ∩ Occ=h−1 (P ) = Occ=h−1 (P ) \ Occ({i}), for h > 0.
Thus, the statement of the lemma holds.
The next proposition is a consequence of the lemma.

utProposition 3. Occ≤k (P ∪ {i}) = Occ≤k−1 (P ) ∪ (Occ=k (P ) ∩ Occ({i})).
From Lemma 1, we can see that all we have to do is take intersection of
occurrences for all i. For this task, the technique so called occurrence deliverdescribed in [10, 12, 11] is efficient.
Let us consider the task of computing Occ=k (P ∪ {i}) for all i > tail(P ).
First, we prepare an empty bucket for each item i. Next, for each transaction T in
Occ=k (P ), we do “insert T into the bucket of i for each item i ∈ T, i > tail(P )”.
After performing this operation for all transactions in Occ=k (P ), the content of
the bucket of i is equal to Occ=k (P ∪ {i}). The pseudo code of occurrence deliveris described as follows. The code inputs a set of transactions S and pattern P ,then sets bucket[i] to S ∩Occ({i}) for all i > tail(P ). We suppose that the bucketof any item i is initialized, and thus is empty at the beginning.
Occurrence deliver(S, P)
1. for each T ∈ S do
2. for each i ∈ T, i > tail(P ) do

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

4: B
5: A, B
6: A
7: A,C,D,E,F
8: C
9: A,C,D,E,F

Fig. 3. Example execution of occurrence deliver3.
insert T into bucket[i]4. end for5. end forFig. 3 shows an example of the execution of occurrence deliver. Let S>h ={T ∩ {h + 1, . . . , |I|} | T ∈ S}). Hereafter, we assume that each transaction T is
stored in memory so that the items in T are sorted in increasing order of items.
Bucket sort or radix sort to all transactions at once can be done in O(||D|| + |I|)
time. The following proposition is proved in [10–12].
Lemma 2. Algorithm Occurrence deliver takes O(||S>tail(P ) ||) time and computes S ∩ Occ({i}) for all i > tail(P ).
Lemma 2 leads in turn to the following proposition.
Proposition 4. For pattern P , we can compute the k-pseudo frequency of all
P ∪{i}, i > tail(P ) having non-zero k-pseudo frequency in O(||Occ=k (P )>tail(P ) ||)time.
From Proposition 4, we can see that computation of CHD(P ) can be donein O(||Occ=k (P )>tail(P ) ||) = O(||D||) time. Next let us consider the cost ofcomputing Occ=0 (P ∪{i}), ..., Occ=k (P ∪{i}) for each i ∈ CHD(P ). From Lemma
1, we can see that it can be computed by taking the intersection of Occ≤k (P )and Occ({i}) in O(|Occ≤k (P )| + |Occ({i})|) time. The following proposition isstated for the memory use[10, 12, 11].
Proposition 5. For any set S ⊆ D of transactions and item i, the size of thebucket of i does not exceed |Occ({i})| after applying occurrence deliver.
We can see from Proposition 5 that the memory used by an iteration isbounded by O(||D||). The depth of the recursion of Backtrack is at most n,
and the accumulated memory usage is O(n||D||).
Theorem 1. For given a database D, minimum support σ and constant k, algorithm Backtrack enumerates k-pseudo frequent itemsets in O(N · ||D||) timewith using O(n||D||) memory, where N is the number of k-pseudo frequent itemsets.
Corollary 1. Algorithm Backtrack is a polynomial delay polynomial space algorithm for enumerating all k-pseudo frequent itemsets.

4

Reducing Computational Cost

In this section, we improve the efficiency of the algorithm proposed in the previous section by reducing both time and space complexities. Our basic idea is to
re-use one bucket in all iterations. This results in a reduction of memory usage.
Here we denote a transaction T in Occ=h (P ∪ {i}) by a pair (T, h). Instead of having all Occ=0 (P ∪ {i}), ..., Occ=k (P ∪ {i}), we maintain Occ0≤k (P ) ={(T, h) | T ∈ Occ=h (P ∪ {i})} keeping that all elements (T, h) in Occ0≤k (P )are sorted in increasing order of h. Then, by applying occurrence deliver to
Occ0≤k (P ), we can obtain Occ0≤k (P ∪ {i}) while keeping the order in
O(||Occ=k (P )>tail(P ) ||) time. By looking at the bottom of each bucket, we caneasily take Occ=k (P ) in O(|Occ=k (P )|) time. This simplifies the operation tomaintain the Occ=h for all h.
A technique called rightmost sweep is useful for the re-use of buckets[10]. The
following propositions and lemmas regard the availability of buckets.
Proposition 6. For an iteration inputting pattern P , no bucket of i ≤ tail(P )is accessed from the beginning of the iteration to the termination of the iteration,
including the execution of the recursive calls.
An iteration adds items i larger than tail(P ), and tail(P ∪ {i}) > tail(P )always holds. Occurrence deliver accesses only the buckets of i satisfying i >tail(P ); thus the statement holds. Proposition 6 indicates that when we generatea recursive call with respect to P ∪ {i}, the bucket of any j < i is preserved until
the end of the recursive call. Thus, we consider the following algorithm PFIM
(Pseudo Frequent Itemset minor) that generates recursive calls in decreasingorder of indices.
PFIM(P , Occ0≤k (P ))1. Output P
2. Apply occurrence deliver to Occ0≤k (P )3. if |Occ≤k−1 (P )| ≥ σ then L := {tail(P ) + 1, . . . , n}
4. else L := {i | |Occ=k (P ∪ {i})| > 0}
remove i 6∈ CHD(P ) from L and initialize the bucket of i
5. end if
6. sort items in L in the decreasing order
7. while L 6= ∅ do
8. extract the head i of L
9. call PFIM (P ∪ {i}, Occ0≤k (P ∪ {i}))10. initialize the bucket of i
11. end while
This algorithm re-uses buckets; thus the buckets to be used seem to be notinitialized at the beginning of an iteration. However, if we can prove that thosebuckets are actually initialized at the beginning, we can be assured of the correctness of the algorithm.

Lemma 3. If all buckets of i > tail(P ) are initialized at the beginning of an
iteration of PFIM inputting pattern P , then the buckets of i > tail(P ) are also
initialized at the termination of the iteration.
Proof. We prove the statement by the induction, starting from the leaves of thecomputation tree of the algorithm. For any iteration, we define its height by 0
if it generates no recursive call, and the maximum height plus one otherwise.
The height is the distance to the farthest leaf among its descendants in thecomputation tree.
First, we consider an iteration that generates no recursive call. In such an
iteration, all buckets inserted some elements in step 2 are initialized in step 4,
thereby L has no element. Thus, the statement holds.
Next, we suppose that for any iteration of height at most h satisfies thestatement, and we consider an iteration I of height h + 1. Let P be the input
pattern of I and suppose that at the beginning of I, the bucket of any i > tail(P )is initialized. Of the buckets holding some elements in step2, the buckets ofi 6∈ CHD(P ) are initialized in step 4. Several recursive calls are generated in theloop from step 7 to step 12. Suppose that i is the head of L. When we generate
the recursive call with P ∪ {i}, the bucket of any j > tail(P ∪ {i1 }) is initialized
since L is sorted in decreasing order. From the assumption of the induction, thebucket of any j > tail(P ∪{i}) is initialized after the termination of the recursive
call. Then, the bucket of i is initialized. Since i is extracted from L, for the newhead i0 of L, the bucket of any j > i0 is again initialized. In this way, recursive
calls are generated with satisfying the assumption of the statement. Thus, aftergenerating recursive calls for all items in L, the bucket of any j > tail(P ) is
initialized.
utForm the lemma, we obtain the following theorem.
Theorem 2. Algorithm PFIM uses
P O(||D||) memory and enumerates all kpseudo frequent itemsets in D in O( P ∈F ||Occ≤k (P )>tail(P ) ||+log n) = O(|F|×||D||) time, where F is the family of k-pseudo frequent itemsets.
Proof. The correctness of the algorithm is obvious from the correctness of Algorithm Backtrack and Lemma 3. The statement for the memory usage is clear
from the re-use of buckets.
Next, we discuss the computation time. Step 2 is done in O(||Occ≤k (P )>tail(P ) ||)time, and step 6 is done in O(|CHD(P )| log n) time. Other steps can be done in
O(|CHD(P )|) time. Thus, by taking the sum overPall k-pseudo frequent itemsets, the total computation time is bounded by O( P ∈F (||Occ≤k (P )>tail(P ) || +log n)) = O(|F| × ||D||).
ut
The structure of the algorithms is almost equal to that of LCM[10–12] forthe frequent itemset enumeration. Our algorithm can be used together withpractical efficient techniques such as database reduction, thus our algorithm
should perform well in practice.

5

Efficient Computation in PracticeIn this paper, we use the k-pseudo inclusion relation as a model of ambiguous
inclusion. Although this is a natural modeling, it has a weak point in practice;that is, many small patterns are k-pseudo frequent. For example, any pattern
whose size is no greater than k is a k-pseudo frequent itemset, and an additionof any item to a (k − 1)-pseudo frequent itemset also yields a k-pseudo frequent
itemset. In the real-world problems, we may not have much interest in thesesmall patterns.
To cope with this difficulty, we often enumerate only the maximal patterns
in the sense of set inclusion. However, possibly so many small itemsets have kpseudo frequencies close to the minimum support, many of these small patterns
become maximal. Moreover, we lose non-maximal but large k-pseudo frequent
itemsets. Thus, we here address the method for enumerating k-pseudo frequent
itemsets of given size l directly. For a pattern P and its item i, let Occ∗=k (P, i)be the set of k-pseudo occurrences T of P such that T does not include i, i.e.,
Occ∗=k (P, i) = {T | T ∈ Occ=k (P ), i 6∈ T }.
Lemma 4. For any pattern P , there exists a sequence of its items (i1 , i2 , . . . , i|P | )such that for any y, |Occ≤k−1 ({i1 , . . . , iy })| ≥ |Occ≤k (P )| |P|P|−y| holds.
Proof. Let (i1 , i2 , . . . , i|P | ) be the items of P sorted in increasing order of|Occ∗=k (P, ij )|, i.e., for any 1 ≤ y < |P |, |Occ∗=k (P, iy )| ≤ |Occ∗=k (P, iy+1 )| holds.
Consider the (k−1)-pseudo frequency of pattern {1, . . . , y} for some 1 ≤ y < |P |.
For any j > y, {1, . . . , y} is included in any transaction of Occ∗=k (P, ij ) in thesense of (k − 1)-pseudo inclusion. Observe that the average of |Occ∗=k (P, ij )|, 1 ≤j ≤ |P | is at most |Occ=k (P )| |Pk | , and one transaction is included in Occ∗=k (P, ij )S|P |at most k j’s. Thus, we see that the cardinality of j=y+1 Occ∗=k (P, ij ) is at least(|P | − y) × |Occ=k (P )| |Pk | /k = |Occ=k (P )| |P|P|−y| . Since |Occ≤k−1 ({i1 , . . . , iy })| =S|P |∗|Occ≤k−1 (P )| + | j=y+1 Occ=k (P, ij )|, the sequence (i1 , . . . , i|P | ) satisfies thestatement.
ut
For given a constant l and a pattern P such that |P | < l, we call the condition||Occ≤k−1 (P )| ≥ σ l−|Pthe partial frequency condition, and we denote by K thelset of all k-pseudo frequent itemsets of size less than l satisfying the partial
frequency condition. From the lemma, we can see that any k-pseudo frequent
itemset of size l can be generated by adding items by passing through only
patterns in K, thus we can use the condition for pruning the iterations. The sizeof K is expected to be smaller than that of k-pseudo frequent itemsets of sizesof at most l, thus the computation time will be short.
For such a generation, we can not use the usual tail extension, since for someP ∈ K, P \ {tail(P )} may not be in K. On the other hand, if we add items
smaller than the tail, we may produce a pattern P = {i1 , . . . , ih } ∈ K twicefrom P \ {ij }, and P \ {ig } for some j 6= g, Thus, we consider the following
generation rule to avoid duplicates.

Generation Rule: Generate each pattern P ∈ K only from the pattern
P \ {i}, i ∈ P maximizing |Occk−1 (P \ {i})| among all patterns obtained byremoving an item from P . Ties are broken by lexicographical order.
Lemma 5. Adding items under the generation rule, any P ∈ K is generated
exactly once.
An enumeration algorithm using such a generation rule is called reverse
search[3]. The algorithm is as follows.
ReverseSearch (P )1. if |P | = l then output P ; return
2. for each i 6∈ P do
3. if |Occ≤k (P ∪ {i})| ≥ σ then // k-pseudo frequency check4.
if |Occ≤k−1 (P ∪ {i})| ≥ σl (l − |P |) then // partial frequency check5.
if P and P ∪ {i} satisfy the generation rule thencall ReverseSearch (P ∪ {i})6. end forLemma 6. The computation time of an iteration of the algorithm ReverseSearch is O(|P | × ||D||).
Proof. The key to the computation time is steps 3, 4 and 5. For steps 3 and 4,
we explained that they can be done in O(||D||) time, thus we have to consider
only step 5. It checks the generation rule, by computing |Occ≤k−1 (P ∪ {i} \ {j})|for all j ∈ P . This takes O(||D|| × |P |) in a straightforward way, we thereby
explain how to decrease it.
Observe that |Occ≤k−1 (P ∪ {i} \ {j})| = |Occ≤k−1 (P ∪ {i})| + |Occ= k(P ∪{i}) \ Occ({j})|. Since Occ≤k−1 (P ∪ {i}) can be obtained in O(||D||) time, all wehave to do is to compute |Occ=k (P ∪ {i}) \ Occ({j})| quickly. For the task, we
maintain the set Occ=k (P ) ∩ Occ({j}) for j ∈ P in memory, and update themin each iteration. This takes O(||D||) time by occurrence deliver. Using these,
we can compute |Occ=k (P ∪ {i}) \ Occ({j})| for all j ∈ P in O(||Occ=k (P ∪{i})|| × |P |) time. Since the sum of ||Occ=k (P ∪ {i})|| over all i 6∈ P never exceed||D||, the time to compute |Occ=k (P ∪ {i}) \ Occ({j})| for all pairs of i and j isO(|P | × ||D||).
ut

6

Conclusion and future work

In this paper, we introduced an ambiguous inclusion relation to the frequent
itemset mining as a meaning of dealing with errors and ambiguities. We chose amodel for ambiguous inclusion by relaxing the inclusion relation so that several
items can be excluded, and formulated the pseudo frequent itemset enumeration
problem by the inclusion relation. To solve the problem, we proposed an efficientpolynomial delay polynomial space algorithm. The algorithm inherits the structure from the existing efficient frequent itemset mining algorithms, thus we expect that it will have high performance in practical use. To skip many small andnon-valuable frequent itemsets, we propose an algorithm for directly enumerating frequent itemsets of a certain size. As future works, to evaluate the efficiency
in the real-world problems implementation of the algorithm and computational
experiments are crucial. Another interesting research topic is extensions of thetechnique in this paper to other frequent pattern mining problems.

Acknowledgments
Part of this research was supported by Grant-in-Aid for Scientific Research ofJapan “Developing efficient and accurate algorithms for large-scale data processing in genome science”, and and joint-research funds of the National Institute ofInformatics.

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, Discrete App. Math., 65,
pp. 21–46, 1996.
4. R. J. Bayardo Jr., Efficiently Mining Long Patterns from Databases, In Proc. SIGMOD’98, 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, Lecture
Notes in Computer Science 3377, pp. 33–45, 2005.
6. J. Liu, S. Paulsen, W. Wang, A. Nobel, J. Prins, “Mining Approximate Frequent
Itemsets from Noisy Data,” 5th IEEE International Conference on Data Mining(ICDM’05), pp. 721-724, 2005
7. J. K. Seppanen and H. Mannila, “Dense Itemsets”, In SIGKDD 2004.
8. W. Shen-Shung and L. Suh-Yin, “Mining Fault-Tolerant Frequent Patterns in
Large Databases”, ICS2002, 2002.
9. M. Takeda, S. Inenaga, H. Bannai, A. Shinohara, and S. Arikawa, Discovering Most
Classificatory Patterns for Very Expressive Pattern Classes, In Proc. of Discovery
Science 2003, Lecture Notes in Computer Science 2843, pp. 486–493, 2003.
10. T. Uno, T. Asai, Y. Uchida, H. Arimura, LCM: An Efficient Algorithm for Enumerating Frequent Closed Item Sets, In Proc. IEEE ICDM’03 Workshop FIMI’03,
2003.
11. T. Uno, T. Asai, Y. Uchida, H. Arimura, An Efficient Algorithm for Enumerating
Closed Patterns in Transaction Databases, Lecture Notes in Artificial Intelligence3245, pp. 16–31, 2004.
12. T. Uno, M. Kiyomi, H. Arimura, LCM ver. 2: Efficient Mining Algorithms forFrequent/Closed/Maximal Itemsets, In Proc. IEEE ICDM’04 Workshop FIMI’04,
2004.
13. 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, Proceedings of the 1994 ACM SIGMOD international conference on Management of
data, pp. 115–125, 1994
14. C. Yang, U. Fayyad, P. S. Bradley, “Efficient Discovery of Error-Tolerant Frequent
Itemsets in High Dimensions,” In SIGKDD 2001.