An approximate discovery of closed itemsets is usually based on either setting a frequency threshold or computing a sequence of projections. Both approaches, being incremental, do not provide any estimate of the size of the next output and do not ensure that “more interesting patterns” will be generated first. We propose to generate closed itemsets incrementally, w.r.t. the size of the smallest (cardinality-minimal or minimum) generators and show that this approach (i) exhibits anytime property, and (ii) first generates itemsets of better quality and then those of lower quality.
(ii) a small number of non-optimal itemsets, i.e., |F \ S| should be as small as possible.
There are two main approaches to compute F . The first one is based on
frequency [
An efficient approach to compute F should be not only incremental and
background-knowledge-free but also should (i) have a polynomial delay [
In this paper we propose a minimum closure structure, which is induced by
generators of the smallest size. We show that it (i) allows for exploring closed
itemsets incrementally, (ii) has a polynomial delay, (iii) computes itemsets that
ensure a complete data coverage after at most two iterations. Itemsets providing
a better solution of the set cover problem might be found in subsequent
iterations. We also revise two algorithms, namely Titanic [
The paper has the following structure. In Section 2 we recall the main definitions. In Section 3 we introduce the closure structure and minimum closure structure of closed itemsets and discuss anytime properties of Titanic and CbO w.r.t. the introduced structures. In Section 5 we discuss the empirical properties of closure structures. In Section 6 we conclude and give directions of future work. 2
Concepts and the partial order between them. A formal context [
Sets A ⊆ G, B ⊆ M , such that A = A00 and B = B00, are said to be closed. For A ⊆ G, B ⊆ M , a pair (A, B) such that A00 = B and B00 = A, is called a formal concept, A and B are called extent and intent, respectively. In Data Mining, an intent is also called a closed itemset (or closed pattern).
A partial order ≤ is defined on the set of concepts as follows: (A, B) ≤ (C, D) iff A ⊆ C (D ⊆ B), a pair (A, B) is a subconcept of (C, D), while (C, D) is a superconcept of (A, B). With respect to this partial order, the set of all formal concepts forms a complete lattice L called the concept lattice of the formal context (G, M, I).
Equivalence classes and key sets. Let B be a closed itemset. Then all subsets
D ⊆ B, such that D00 = B are called generators of B and the set of all generators
is called the equivalence class of B, denoted by Equiv(B) = {D | D ⊆ B, D00 =
B}. A subset D ∈ Equiv(B) is a key [
The size of the equivalence class is the nominator of (extentional) stability [
For the sake of simplicity, we denote attribute sets by strings of characters, e.g., abc instead of {a, b, c}.
Example. Let us consider a formal context given in Table 1. Five concepts have nontrivial equivalence classes, namely ({g1}, acf ), ({g3}, ade), ({g5, g6}, bdf ), ({g5}, bdef ) and (∅, abcdef ). Among them, only bdf and abcdef have the minimum key sets that differ from the key sets, i.e., Kmin(bdf ) = {b}, K(bdf ) = {b, df }. Kmin(abcdef ) = {ab}, K(abcdef ) = {ab, adf, aef, cef }.
Stab(bdf ) = |{{g5, g6}, {g6}}|/22 = 1/2 and Stab(ac) = |{{g1, g2}}|/22 = 1/4, thus, if the analyzed dataset contains noise, bdf is more likely to be closed in the original dataset (without noise).
Table 1: Formal context and nontrivial equivalence classes. a b c d e f
C
Kmin(C)
K(C)
Equiv(C) gggggg342651 ××× ×× ××× ××× ×××× ××× bbaaaddbcdfecfedfef bbaaaebfd,, ecff ∗ The equivalence class includes all itemsets that contain a key from K(abcdef ). ad ad, ade af , cf af , cf , acf b, df b, df , bd, bf , bdf be, ef be, ef , bde, bef , def , bdef ab, adf , aef , cef ab, adf , aef , cef , ..., abcdef ∗
Lectic order and lexicographic trees. Let M be a set of linearly ordered attributes m1 < m2 < . . . < mk. Then, an itemset B1 ⊆ M is lectically smaller than the set B2 ⊆ M , if the smallest differing element belongs to B1. A lexicographic tree is a tree that has the following properties: (i) the root corresponds to the null itemset; (ii) a node in the tree corresponds to an itemset, (iii) the parent of a node m1 . . . mi−1mi is a node m1 . . . mi−1.
Example. The lexicographic tree in Fig. 1 is built on closed itemsets with the minimum keys of size 1 and 2, i.e., all closed itemsets except ace from Fig. 1. In the tree we distinguish nodes that correspond to closed itemsets (dark) and intermediate nodes (white), needed to respect property (iii) from the definition of the lexicographic tree. In this section we introduce the closure structure and discuss how Titanic and CbO can be used to discover this structure incrementally. Both algorithms exhibit the anytime property, meaning that they (i) compute the whole set of closed itemsets given enough time and space, (ii) can be interrupted at any time providing an estimated number of closed itemsets at the next (and following) levels. The algorithms differ in (i) key sets they use, (ii) the approaches to derivation of new keys based on previously computed ones, which results in different estimates of the output size for the next iteration and different computational complexity. Let C be the set of all closed itemsets and K(B) be the key set of a closed itemset B ∈ C. Level : C → {1, . . . , |M |} is a function that maps a closed itemset to the set of sizes of its keys, i.e., Level(B) = {|D| | D ∈ K(B)}. The structural level k is given by all the keys of size k, i.e., Kk = {D ∈ K(B) | B ∈ C, |D| = k}. We say that B belongs to the structural level k if there exists a key D ∈ K(B) of size k, i.e., B ∈ Ck if k ∈ Level(B). The set of the corresponding closed itemsets is given by Ck = {B | B ∈ C, k ∈ Level(B)}. The set of all structural levels will be called closure structure. We call structural complexity of C the maximal index of non-empty levels, Nc = max{k | k = 1, . . . , |M |, Kk 6= ∅ }. Example. The levels of dataset from Fig. 1 are given in Fig. 1 (right). The structural complexity Nc = 3. Closed itemset bdf belongs to structural levels C1 and C2, because its equivalence class contains the keys from two structural levels, i.e., b ∈ K1 and df ∈ K2, while acf is included only in C2 since its keys af, cf are in K2.
Proposition 1 I = Sk=1,...,|M| Kk is an order ideal w.r.t. ⊆.
Proof. Consider an itemset B ∈ I. Suppose the contrary, i.e., that an arbitrary subset D ⊂ B of size |B| − 1 is not in I, thus, D is not a key. Then B can not be a key, since we can replace D with key E ⊂ D. Thus, our assumption is wrong and I is an order ideal.
Proposition 2 Nc is the dimension of the maximal Boolean sublattice of the lattice of C.
Proposition 3 Structural complexity Nc of C is the maximal n ∈ {1, . . . , |M |} such that there exists a concept (B0, B) with |B| = n and Stabint(B0, B) = 1/2n. Proof. By Proposition 1, there exists B, |B| = Nc that corresponds to the intent of the bottom element of the Boolean sublattice. Since every subset C ⊂ B0 is an extent of a concept (C, C0) such that C0 6= B, then Stabint(B0, B) = 1/2n. 3.2
Titanic algorithm [
In this paper we state that, in case of limited resources, we can compute just several levels rather than considering only frequent itemsets. The pseudocode is given as Algorithm 1 (this version is a little bit different from the original one, since we put all the steps related to computing keys into one procedure).
To obtain the next set Kk it is sufficient to consider the union of two keys from Kk−1 (line 1) and then check if each obtained key makes an order ideal with the previously computed keys (line 3-6, according to Proposition 1). However, itemsets from S may be just members of an equivalence class. To ensure that an itemset is a key, one needs to compare support supp(D) of candidate D ∈ S with the minimal support ind supp(D) of the keys of size k − 1 contained in D (line 12). If these values are the same, then the support of D is inductively derived from the support of proper subsets, and D is not minimal (not a key).
Anytime property and the estimates of the size of the next output. Given the size of the current output |Kk| (the number of keys), the estimated size of the next output |Kk+1| is given by |Ck+1| ≤ |Kk+1| < |Kk|(|nKk| − 1)/2. More generally, the number of keys at level k + n, n ∈ N is O(|Kk|2 ).
Titanic computes all keys of closed itemsets. A closed itemset can have keys of different size. The latter means that the same closed itemset will be computed at different levels (e.g., an itemset bdf from Fig. 1 has key b ∈ K1 and df ∈ K2). From a PM perspective, computing keys that generate the same closed itemsets is redundant.
Algorithm 1 Titanic-Gen
Require: Kk−1, the key set of level k−1 Reqkueiyrese:tKKk∗km−−i1n1, aofsulebvseeltko−ft1h,e minimum Ensure: Kk, the key set of level k 1: S ← {{m1 < . . . < mk} | {m1, . . . , mk−2, mk−1}, {m1, . . . , mk−2, mk}
Tk−1, the lexicographic tree containing all closed itemsets Si=1,...,k−1 Cimin ∈ Kk−1} Ensure: Kk∗, a subset of the minimum key
set of level k 2: for all D ∈ S do 1: Kk∗ ← ∅ 3: for all (k − 1)-subsets E ⊆ D do 2: Tk ← Tk−1 4: if E ∈/ Kk−1 then 3: for all X ∈ Kk∗−1 do 5: S ← S \ {D} 4: Y ← M \ X00 6: exit forall 5: for all m ∈ Y do 7: end if 6: X∗ = X ∪ {m} 8: ind supp(D) ← 7: S ← (X∗)00
min(ind supp(D), supp(S)) 8: if S ∈/ Tk then 9: end for 9: add(Tk, S) 10: end for 10: Kk∗ ← Kk∗ ∪ {X∗} 11: ComputeSupport(S) 11: end if 12: Kk ← {D ∈ S | ind supp(D) 6= 12: end for
supp(D)} 13: end for 13: return Kk 14: return Kk∗ In the next section we propose an approach where only one minimum key for each closed itemset is considered. 3.3
Similar to the closeness structure induced by key sets, we introduce the minimum closeness structure induced by minimum key sets.
Let C be a set of all closed itemsets and Kmin(B) be the minimum key set of a closed itemset B ∈ C. We denote a function that maps a closed itemset to the size of its minimum key by level, i.e., level : C → {0, . . . , |M |}, such that level(B) = |D|, where D ∈ Kmin(B) is an arbitrary itemset chosen from Kmin(B). The minimal structural level k is given by all minimum keys of size k, i.e., Kkmin = S Kmin(B). We say that B belongs to the minimum structural level k
B∈C, level(B)=k if itemsets in Kmin(B) have size k. We denote the corresponding set of closed itemsets of level k by Ckmin. More formally, Ckmin = {B | B ∈ C, level(B) = k}. We call minimum structural complexity of C the maximal number of not empty levels, Ncmin = max{k | k = 1, . . . , |M |, Kkmin 6= ∅}. Proposition 4 Imin = S
k=1,...,|M| Kkmin is an order ideal.
Example. The structural levels Kk of the dataset from Fig. 1 are given in Fig. 1 (right). The minimum structural levels are the following: K1min = K1, K2min = K \ {df }, and K3min = {ace}. Set df is excluded because the size of b is smaller than df . The same for {adf, aef, cef } ⊆ K3. The minimum structural complexity is Ncmin = 3.
In contrast to Ck (induced by the structural level Kk) Ckmin (induced by the minimum structural level Kkmin) does not intersect with sets of concepts from other levels, e.g., bdf is in C1 = C1min and in C2, but not in C2min. 3.4
A closed itemset may have more than one munimum key. In this section we propose to compute closed itemsets based on a subset Kk∗ of Kkmin.
The algorithm sequentially generates subsets Kk∗ ⊆ Kkmin, k = 1, . . . , |M | such that for each B ∈ Ckmin there exists only one D ∈ Kk∗. The pseudocode is given as Algorithm 2. By construction, I∗ = Sk=1,...,|M| Kk∗ is an order ideal.
An itemset from Kk∗ ⊆ Kkmin is computed as the closure of a union of an itemset X ∈ Kk∗−1 and an attribute m ∈ M \ X00. The minimality of keys can be easily checked by using lexicographic tree Tk−1 that contains the closed itemsets of the minimum keys computed earlier. The tree storage takes O(2|M |) memory. Checking the minimality takes O(|M |) time.
The proposed algorithms is a version of Close-By-One (CbO) [
Example. Let us consider how Algorithm 2 works using the dataset from Fig. 1. The intermediate steps are given in Table 2. At input we get K2∗, a subset of minimum keys of size 2. For each closed itemset C2min it contains only one minimum key. The lexicographic tree for C1min ∪ C2min is given in Fig. 1.
Anytime property and the estimates of the size of the next output. Given the size |Kk∗| of the output at the current iteration, the number of keys |Kk∗+1| that will be generated at the next iteration is given by PX∈Kk∗ |M \ X00|. More generally, the number of minimum keys at level k + n, n ∈ N is O(|Kk∗||M |n). 4
In the previous section we introduced the structural levels Kk (used in Algorithm 1) and the miminum structural levels Kkmin. The corresponding sets of closed itemsets are Ck and Ckmin, respectively. We also consider subsets Kk∗ ⊆ Kkmin used in Algorithm 2.
At level k, both algorithms allow for discovering the same closed itemsets, i.e., Si=1,...,k Ckmin = Si=1,...,k Ck. However, Ck may intersect with another Cn, while all Ckmin are disjoint. The latter means that in the second case closed itemsets will not be discovered twice. Redundant computations may take place not only w.r.t. different levels, but also within a (minimum) structural level, when a closed itemset has several keys of the same size. In Algorithm 2 this problem is solved by reducing Kkmin to Kk∗. Depending on data and the depth k of the closure structure, the performance of algorithms can differ drastically (see experiments in Section 5, Table 4). We illustrate this problem by means of a concrete example.
Example. Let us compare the structures that are used by the algorithms. The closure structure Sk=0,...,3 Kk used by Titanic is given in Fig. 2. Four filled areas highlight the keys of four closed itemset. It means that Titanic discovers the same closed itemset several times (equal to the number of keys in the filled areas). The number of minimum keys (in bold) is much lower, while the number of minimum keys discovered by CbO (in dark bold) is even smaller. For instance, among the minimum keys Kmin(bdef ) = {be, ef } and Kmin(acf ) = {af, cf }, CbO uses only be and af , respectively.
Computational redundancy can affect the estimates of the size of the next output. We will study how precise these estimates are in experiments (Section 5).
In addition to computational benefits, a minimum key is the best descriptor
of an equivalence class according to the information theory [
In our experiments we focus on the following questions: (i) what is the structure induced by the minimum keys, (ii) what concepts does level Ckmin (k = 1, . . . , |M |) contain, (iii) what is the quality of concepts in Ckmin? Considering Algorithms 1 and 2, the structural complexity (Nc and Ncmin) is equal to the number of iterations required to compute the whole lattice. Theoretically, for a dataset over M attributes, Ncmin ≤ Nc ≤ |M |, and the largest level |M2 | has size b||MM2 ||c . In experiments we study how the theoretical bounds differ from the actual values. The results are reported in Table 3. The percentage of closed itemsets at level k w.r.t. the total number |C| is given in column “|Ckmin|/|C|”, the largest level is highlighted in bold. Our experiments show that the theoretical bounds are overestimated 6 times (on average), i.e., Ncmin ≈ |M |/6. The number of closed itemsets in the largest level on average is about 35% of the total number of closed itemsets. Thus, around 30% of closed itemsets can be computed before the largest level has been achieved. As expected, the largest levels are usually in the middle of the closure structure, i.e., Ncmin/2. In the previous section we study the overall closure structure. In this section we consider the composition of each level in more detail.
Coverage ratio. Referring to the set cover problem, we need to reduce the whole set of itemsets to a subset of candidates F (see Section 1). Algorithms 1 and 2 suggest to compute the candidate sets incrementally, which raises the question “when the computation can be stopped?” In our experiments we compute the level-wise coverage ratio of closed itemsets (formal concepts), i.e., the ratio of cells covered by closed itemsets Ckmin to all non-empty entries. The background colors of cells in Table 3 show the coverage ratio for each structural level. The coverage ratio monotonically decreases with levels. For example, for “iris” dataset, closed itemsets from C1min alone covers the whole dataset and C2min alone is able to cover the whole dataset. Each level from C3min to C6min covers more than 80% of dataset. The itemsets from the last level C7min cover more than 60%, but less than 80%. Thus, the coverage ratio does not increase with each consecutive level.
It follows directly from the definitions of the (minimum) structural levels that it is enough to compute at most 2 levels in order to compute the complete covering (if we use for covering itemsets of length at least 2).
Level composition. Along with the coverage ratio, we study the composition of the levels, i.e., the distribution of closed itemsets w.r.t. their frequency. The typical structures are given in Figure 3 (left and middle). For example, for “iris” dataset, frequent closed itemsets (f r. ∈ (0.8, 1.0]) make 20% of C1min, 2.3% of (C02m.,in0.,2a])n,dononthlye 0co.1n%traorfy,Ci3mncinre.aTsehse, er.agt.i,othoefyinmfraekqeu2en0t%colofsCe1dmiint,em46s%etsof(fC3rm.in∈, and 77% of the last level C7min.
The described behavior is typical for all datasets. The only difference is the initial ratio of infrequent closed itemsets. For instance, C1min of “iris” and “heartdisease” contain 20% and 53% of infrequent closed itemsets, respectively. Only closed itemsets of “pima” and “ecoli” have level-wise frequency distribution that differs from the typical one. We show level-wise frequency of “pima” dataset in Figure 3, right. Further we will show that level-wise quality of “pima” and “ecoli” itemsets differs from others.
Fig. 3: Distribution of frequent concepts by levels. A level Ckmin is represented by a horizontal bar. The level number k is given in parentheses, the percentage of closed itemsets |Ckmin|/|Ck| is on the left of the level number. The proportion of closed itemsets of frequency (v1, v2] among Ckmin is highlighted in colors.
In those experiments we showed that the empirical structural complexity is much lower than its theoretical upper bound, i.e., Ncmin ≈ |M |/6 < |M |, and closed itemsets of the first two levels contain a large number of frequent itemsets. This conclusion raises the following questions: (i) how useful are the closed itemsets of the first levels, (ii) do we need to compute the following levels to discover more interesting itemsets (or itemsets of better quality)? Quality of itemsets. In our study we propose to assess itemset quality by average F1 score by levels. All the studied datasets have class labels that are used only for evaluation. F1 score is defined as follows: F1 = 2 · prec · recall/(prec + recall).
For a closed itemset B, objects from B0 are considered as classified. The label of the majority of objects B0 is taken as the label of B. The remaining objects G \ B0 are considered as unclassified by B. Then, the average values of F1 score for concepts Ckmin are considered (see Fig. 4). In general, the quality of closed itemsets decreases with each subsequent level, except for “pima” and “ecoli” datasets. The reason of this unusual behavior needs a more careful study.
Both algorithms provide boundaries on the number of keys that will be generated at the next iteration k + 1. For Algorithms 1 and 2 these values are |Kk|(|Kk| − 1)/2 and PX∈Kk∗ |M \ X00|. We compare these values with the true number of newly generated closed itemsets |Ckmin| = |Ck \ ∪i=1,...,k−1Ci|. The ratio of the predicted size to the actual one is reported in Table 4. The results show that, except for levels 1 and 2, the estimates of Algorithm 2 provide more precise boundaries. Since the boundaries are closely related to the computational strategy, high values indicate the computational redundancy of Algorithm 1. 6
In this paper we have studied the minimum closure structure of closed itemsets. This structure is induced by the smallest (minimum) generators. We have proposed an alternative point of view on the Titanic and Close-By-One algorithms, namely we have shown that they exhibit the anytime property and allow for incremental generation of closed itemsets w.r.t. the (minimum) closure structure. In the experiments we have shown that the algorithms generate first itemsets of the highest quality and then itemsets of decreasing quality. One of the most interesting directions of future work is to study the connection between structural complexity and stability.