We describe a method for computing closed sets with data-dependent constraints. Especially, we show how the method can be adapted to find frequent closed sets in a given data set. The current preliminary implementation of the method is quite inefficient but more powerful pruning techniques could be used. Also, the method can be easily applied to wide variety of constraints. Regardless of the potential practical usefulness of the method, we hope that the sketched approach can shed some additional light to frequent closed set mining.
Much of the research in data mining has concentrated on finding from some given (finite) set R all subsets that satisfy some condition. (For the rest of the paper we assume, w.l.o.g., that R is a finite subset of N.)
The most prominent example of this task is probably the task of finding all subsets X ⊆ R that are contained at least minsupp times in the sets of a given sequence d = d1 . . . dn of subsets di ⊆ R, i.e., to find the collection F (minsupp, d) = {X ⊆ R : supp (X, d) ≥ minsupp} where
supp (X, d) = |{i : X ⊆ di, 1 ≤ i ≤ n}| .
The collection F (minsupp, d) is known as the collection of frequent sets. (We could have defined the collection of frequent sets by by the frequency of sets which is a normalized version of supports: f r (X, d) = supp (X, d) /n.)
Recently one particular subclass of frequent sets, frequent closed sets, has received quite much attention. A set X is closed in d if supp (X, d) > supp (Y, d) for all proper supersets Y of X. The collection of closed sets (in d) is denoted by
C (d) = {X ⊆ R : Y ⊆ R, Y ⊃ X
⇒ supp (X, d) > supp (Y.d)}
The collection of frequent closed sets consists of the sets that are frequent and closed, i.e.,
F C (minsupp, d) = F (minsupp, d) ∩ C (d) .
Most of the closed set mining algorithms [
The paper is organized as follows. In Section 2 we sketch the method, in Section 3 we adapt the method for finding closed sets with frequency constraints, in Section 4 we describe some implementations details the method, and in Section 5 we experimentally study the properties of the method. Section 6 concludes the work and suggests some improvements to the work. 2
Let us assume that R = Si∈{1,...,n} di as sometimes R is not known explicitly. Furthermore, we shall use shorthand di,j for the subsequence di . . . dj , 1 ≤ i ≤ j ≤ n. The elements of R are sometimes called items and the sets di transactions.
As noted in the previous section, a set X ⊆ R is closed
in d if and only if supp (X, d) > supp (Y, d) for all proper
supersets Y of X. However, the closed sets can be defined
also as intersection of the transactions (see e.g. [
A more efficient solution can be found by the following recursive definition of closed sets:
C (d1,i+1)
C (d1) = = {R, d1}
C (d1,i) ∪ {X ∩ di+1 : X ∈ C (d1,i)}
Thus the closed sets can be computed by initializing C = nR = Si∈{1,...,n} dio (since R is always closed), initializing supp to R 7→ 0, and calling the following algorithm for each di (1 ≤ i ≤ n): INTERSECT(supp : C → N, di) 1 for each X ∈ C 2 do C ← C ∪ {X ∩ di} 3 if supp (X ∩ di) < supp (X) + 1 4 then supp (X ∩ di) ← supp (X) + 1 5 return (supp : C → N)
Using the above algorithm the sequence d does not have to be stored as each di is needed just for updating the current approximation of R and intersecting the current collection C of closed sets.
The closed sets can be very useful way to understand
data sets that consist of only few different transactions and
they have been studied in the field of Formal Concept
Analysis [
Unfortunately the collection of closed sets can be much larger than the collection of frequent closed sets. Thus the 1If supp (X) is not defined then its value is interpreted to be 0. above approach can generate huge number of closed sets that do not have to be generated.
A better approach to find the frequent closed sets is to prune the closed sets that cannot satisfy the constraints – such as the minimum support constraint – as soon as possible. If the sequence is scanned only once and nothing is known about the sequence d in advance then no pruning of infrequent closed sets can be done: the rest of the sequence can always contain each closed set at least minsupp times.
If more than one pass can be afforded or something is known about the data d in advance then the pruning of closed sets that do not satisfy the constraints can be done as follows: INTERSECTOR(d) 1 supp ← INIT-CONSTRAINTS (d) 2 for each di in d 3 do supp ← INTERSECT (supp, di) 4 UPDATE-CONSTRAINTS (supp, di) 5 supp ← PRUNE-BY-CONSTRAINTS (supp, di) 6 return (supp : C → N)
The function INTERSECTOR is based on three subroutines: function INIT-CONSTRAINTS initializes the data structures used in pruning and computes the initial collection of closed sets, e.g. the the collection C = {R}, function UPDATE-CONSTRAINTS updates the data structures by one transaction at a time, and function PRUNE-BYCONSTRAINTS prunes those current closed sets that cannot satisfy the constraints. 3
Adaptation to Frequency Constraints
The actual behaviors of the functions INITCONSTRAINTS, UPDATE-CONSTRAINTS and PRUNE-BYCONSTRAINTS depend on the constraints used to determine the closed sets that are interesting. We shall concentrate on implementing the minimum and the maximum support constraints, i.e., finding the closed sets X ∈ C (d) such that minsupp ≤ supp (X, d) ≤ maxsupp.
The efficiency of pruning depends crucially on how much is known about the data. For example, if only the number of transactions in the sequence is known, then all possible pruning is essentially determined by Observation 1 and Observation 2.
Observation 1 For all 1 ≤ i ≤ n holds: supp (X, d1,i)+n−i < minsupp ⇒ supp (X, d) < minsupp Observation 2 For all 1 ≤ i ≤ n holds: supp (X, d1,i) > maxsupp ⇒ supp (X, d) > maxsupp Checking the constraints induced by Observation 1 and Observation 2 can be computed very efficiently. However, the pruning based on these observations might not be very effective: all closed sets in d1,n−minsupp can have frequency at least minsupp and all closed sets in d1,maxsupp can have frequency at most maxsupp. Thus all closed sets in d1,min{n−minsupp,maxsupp} are generated before the observations can be used to prune anything.
To be able to do more extreme pruning we need more information about the sequence d. If we are able to know the number of transactions in the sequence, it might be possible to count the supports of items. In that case Observation 3 can be exploited.
Observation 3 If there exists A ∈ supp (X, d1,i) + supp ({A} , di+1,n) < supp (X, d) < minsupp.
X such that minsupp then
Also, if we know the frequencies of some sets then we can make the following observation: Observation 4 If there exists Y supp (X, d1,i) + supp (Y, di+1,n) supp (X, d) < minsupp. ⊆ <
X such that minsupp then
Note that these observations do not mean that we could remove the infrequent closed sets from the collection since an intersection of an infrequent closed set with some transaction might still be frequent in the sequence d. However, we can do some pruning based on the observations as shown in Proposition 1.
Proposition 1 Let Z be the largest subset of X ∈ C such that for all A ∈ Z hold supp (X, d1,i) + supp ({A} , di+1,n) ≥ minsupp. Then X ∈ C can be removed from C if there is a W ⊆ Y ∈ C, Z ⊂ W , such that supp (Y, d1,i) ≥ supp (X, d1,i) and for all A ∈ W hold supp (Y, d1,i) + supp ({A} , di+1,n) ≥ minsupp, and replaced by Z otherwise.
Proof. All frequent subsets of X are contained in Z. If there is a proper superset W ⊆ Y ∈ C of Z such that supp (Y, d1,i) + supp ({A} , di+1,n) ≥ minsupp then all frequent subsets of X are contained in W and thus X can be removed. Otherwise Z is the largest subset of X that can be frequent and there is no superset of Z that could be frequent. If Z is not closed, then its support is equal to some of its proper supersets’ supports. If Z is added to C then none of proper supersets is frequent and thus also Z is infrequent.
This idea of replacing infrequent sets based on the supports items can be generalized to the case where we know supports for some collection S of sets.
Proposition 2 Let S be the collection of sets such that supp (Y, d1,i) and supp (Y, d1,i) are known for all Y ∈ S, and let S0 consist of sets Y ∈ S, Y ⊆ X, such that supp (X, d1,i) + supp (Y, di+1,n) < minsupp. Then all frequent subsets of X ∈ C are the collection S00 of subsets Z ⊆ X such that Z 6⊆ Y for all Y ∈ S0, no W ⊂ Z ∈ S00 is contained in S00.
Proof. If Z ⊆ X is frequent then there is a set in S00 containing Z, or Z is contained in some set in S0 but there is another set Y ∈ C such that supp (Y, d1,i) > supp (X, d1,i). Proposition 3 Let S, S0 and S00 be as in Proposition 2. Then X ∈ C can be replaced by the collection S000 consisting of sets in S00 such that supp (Y, d1,i) + supp (W, di+1,n) < minsupp for some W ⊆ Z ⊆ Y with Y ∈ C and W ∈ S.
Proof. If Z ⊆ X is frequent then it is subset of some set in S00 or there is Y ∈ C, Z ⊆ Y , such that supp (Y, d1,i) + supp (W, di+1,n) < minsupp for all W ∈ S, W ⊆ Z.
If Z ∈ S00 is not closed then it is infrequent since none of its supersets is frequent.
The efficiency of pruning depends crucially also on the ordering of the transactions. In Section 5 we experimentally evaluate some orderings with different data sets. 4
The Organization of the Implementation A preliminary adaptation of the algorithm INTERSECTOR of Section 2 to minimum support and maximum support constraints is implemented as a program intersector. The main components of the implementation are classes Itemarray, ItemarrayInput and ItemarrayMap.
The class Itemarray is a straightforward implementation consisting of int n expressing the number of items in the set and int* items that is a length (at least) n array of items (that are assumed to be nonnegative integers) in ascending order. One of the reasons why this very simple representation of a set is used is that Itemarrays are used also in the data sources, and although some more sophisticated data structures would enable to do some operations more efficiently, we believe that Itemarray reflects better what an arbitrary source of transactions could give.
The class ItemarrayInput implements an
interface to the data set d. The class handles the
pruning of infrequent items from the input and
maintaining the numbers of remaining occurrences of each
item occurring in the data set. The data set d is
accessed by a function pair<Itemarray*,int>*
getItemarray() which returns a pointer to next
pair<Itemarray*,int>. The returned pointer is
NULL if the previous pair were the last one in the data set d.
The main difference to the reference implementation given
at the home page of Workshop on Frequent Itemset Mining
Implementations2 is that pair<Itemarray*,int>* is
returned instead of Itemarray*. This change were made
partly to reflect the attempt to have the closure property of
inductive databases [
The class ItemarrayFileInput maintains in the main memory only the item statistics (such as the number of remaining occurrences of each item) thus possibly reading the data set several times. The class ItemarrayMemoryInput reads the whole data set d into main memory. The latter one can be much faster since it can also reorder the data set and replace all transactions di, 1 ≤ i ≤ n, with same frequent items by one pair with appropriate count. The implementations of these classes are currently quite slow which might be seen as imitating the performance of real databases quite faithfully.
The class ItemarrayMap represents a mapping from Itemarrays to supports. The class consists of a mapping map<Itemarray*,int,CardLex> itemarrays that maps the sets to supports, and a set set<Itemarray*,CardLex> forbidden consisting of the sets that are known to be infrequent or too frequent. The set set<Itemarray*,CardLex> forbidden is needed mainly because of the maximum frequency constraint. The class consists two methods: • The method intersect(const pair<Itemarray*,int>*) intersects the current collection sets represented by the mapping map<Itemarray*,int,CardLex> itemarrays by the given set pair<Itemarray*,int>* and updates the supports appropriately. • The method prune(ItemarrayInput&) prunes the sets that are already known to be infrequent or too frequent based on the statistics maintained by the implementation of the interface ItemarrayInput. (The class CardLex defines a total ordering of sets (of integers) by their cardinality and lexicographically within of each group with same sizes.) The pruning rules used in the current implementation of the method prune(ItemarrayInput&) are Observation 1, Observation 2, and Observation 3. 5
name T10I4D100K T40I10D100K chess connect internet kosarak mushroom pumsb pumsb*
We tested the efficiency and behavior of the implementation by the data sets listed in Table 1. All data sets except internet were provided by the Workshop on Frequent Itemset Mining Implementations. The data set internet is the Internet Usage data from UCI KDD Repository3.
If the data sequence is read to main memory then it can
be easily reordered. Also, even if this is not the case, there
exist efficient external memory sorting algorithms that can
be used to reorder the data [
We experimented especially with two orderings: ordering in ascending cardinality and ordering in descending cardinality. The results are shown in Figures 1–9. Each point (|C| , i) in the figures corresponds to the number |C| of closed sets in the sequence d1,i that could be frequent in the whole sequence d. Note that the reason why there is no point for each number i (1 ≤ i ≤ n) of seen transactions is that same set of items can occur several times in the sequence d.
There is no clear winner within the ascending and descending orderings: with data sets T10I4D100K, T40I10D100K, internet, kosarak, and mushroom the ascending order is better whereas the descending order seems to be better with data sets chess, connect, and pumsb. However, it is not clear whether this is due to the chosen minimum support thresholds.
number of seen transactions number of seen transactions 2500 3000 3500 increasing cardinality decreasing cardinality 1000 500 0 0
0 0 800 700 tse600 s d e s lco500 t n e u q fre400 ilt a n e t fpo300 o r e b unm200 100 0 0
4000 5000 number of seen transactions 1000 2000 3000 6000 7000 8000 9000
One interpretation of the results is the following: small set di cannot increase the size of C dramatically since all new closed sets are subsets of di and di has at most 2|di| closed subsets. However, the small sets do not decrease the remaining number of occurrences of items very much either. In the case of large sets dj the situation is the opposite: each large set dj decreases the supports supp ({A} , dj+1,n) of each item A ∈ dj but on the other hand it can generate several new closed sets.
Also, we experimented with two data sets internet and mushroom to see how the behavior of the method changes when changing the minimum support threshold minsupp. The results are shown in Figure 10 and Figure 11.
The pruning seems to work satisfactory if the minimum support threshold minsupp is high enough. However, it is not clear how much this is due to the pruning of infrequent items in the class ItemarrayInput and how much due to the pruning done by the class ItemarrayMap. Unfortunately, the performance rapidly collapses as the minimum support threshold decreases. It is possible that more aggressive pruning could help when the minimum support threshold minsupp is low. 6
In this paper we have sketched an approach for finding closed sets with some constraints from data with only few passes over the data. Also, we described a preliminary implementation of the method for finding frequent but not too frequent closed sets from data. The current version of the implementation is still quite inefficient but it can hopefully shed some light to the interplay of data and closed sets.
As the current implementation of the approach is still
very preliminary, there is plenty of room for improvements,
e.g., the following ones:
• The ordering of input seems to play crucial role in the
efficiency of the method. Thus the favorable
orderings should be detected and strategies for
automatically finding them should be studied.
• The pruning heuristics described in this paper are still
quite simplistic. Thus, more sophisticated pruning
techniques such as inclusion-exclusion [
4400
minimum support threshold
4600
4800
5000
1800
2000
2600
2800
3000
2200 2400
minimum support threshold
40000
35000
4000 5000
number of seen transactions
• After two passes over the data it is easy to do the third
pass, or even more. Thus one could apply the
intersections with several different minimum support
thresholds to get refining collection of frequent closed sets in
the data: the already found frequent closed sets with
high frequencies could be used to prune less frequent
closed sets more efficiently than e.g. the occurrence
counters for frequent items.
• If it is not necessary to find the exact collection of
closed sets with exact supports, then a sampling could
be applied [