In this paper, we consider the problem of mining class relevant patterns from a given context, where each object in the context has a label which is either “positive” (i.e., target-class) or “negative” (i.e., non target-class). Garriga et al. studied the notion of relevancy in FCA (Formal Concept Analysis). Based on their work, we propose a CbObased algorithm which, while traversing the search space of closed sets on the positives, performs pruning based on a relevance check; it checks whether or not a pattern (concept) is dominated by another pattern. The pruning method performs two kinds of checks; dominance check between a node and its children nodes, and dominance check between a node and its sibling nodes in a CbO-based search tree. Although extra costs are required for performing the latter check, our experimentally results show that the proposed approach has outperformed the conventional methods in the literature.
Concise representation is essential in a pattern mining task to handle large
amounts of patterns generated during the mining process. Closed patterns and
closed itemsets have been extensively studied in the field of FCA (Formal
Concept Analysis) [
Lavraˇc et al. proposed the theory of relevance [
Several methods have been proposed to generate relevant patterns, using the
notion of closed patterns [
In this paper, we propose a CbO-based algorithm [
The organization of the rest of this paper is as follows. We first summarize some basic notations and definitions of relevant pattern mining in Sect. 2. We then explain our approach to mining relevant patterns from a formal context in Sect. 3, and show some experimental results in Sect. 4. Finally, we give a summary of this work in Sect. 5. 2 2.1
We use some basic notions of FCA in [
By A0 we mean the set of attributes shared by a subset A of objects, and B0 the set of objects sharing a subset B of attributes. A concept (A, B) is a maximal objects-attributes correspondence, satisfying A0 = B and B0 = A. A is called the extent of the concept, and B its intent. Two formal concepts (A1, B1) and (A2, B2) are ordered by
(A1, B1) ≥ (A2, B2) ←→ A1 ⊇ A2, and form a complete lattice.
We assume that each object has a class label in {+, −}. Each label is not in M . The set G of all objects are divided into two subsets: the set G+ of those objects that are labeled by +, the positives (or the positive examples), and the set G− of those objects that are labeled by −, the negatives (or the negative examples).
A pattern in K = (G, M, I) is a subset of the attribute set M . An object g satisfies the pattern P if g contains all attributes in P . The occurrence set of P , denoted by occ(G, P ), is the set of those objects in G which satisfy P . We simply write it by occ(P ), when G is obvious from the context. The negative occurrence set of the pattern P , denoted by occ−(P ), is the set of those objects in G− which satisfy P , i.e., occ−(P ) = occ(G−, P ). The positive occurrence set of the pattern P , denoted by occ+(P ), is defined dually, i.e., occ+(P ) = occ(G+, P ).
The support of P , denoted by supp(G, P ), is the size of occ(G, P ). We simply write it by supp(P ), when G is obvious from the context. The negative support (positive support) of the pattern P , denoted by supp−(P ) (supp+(P )), is the size of occ−(P ) (occ+(P )), respectively.
The notion of a closed pattern is defined as usual: a pattern P is closed when there is no other pattern Q such that P ( Q and supp(G, P ) = supp(G, Q).
Closed patterns can be defined in terms of the following closure operator: ΓG(P ) = {i ∈ M | ∀o ∈ occ(G, P ) contains attribute i.}, i.e., the closure ΓG(P ) of a pattern P includes all attributes that are present in all objects in G which contain all attributes in P . 2.2
A pattern P is more relevant than (or dominates) a pattern Q in G iff – occ+(P ) ⊇ occ+(Q), – occ−(P ) ⊆ occ−(Q). – Γ (P ) 6= Q.1
We call a pattern P relevant if there is no other pattern Q more relevant than (or dominating) P . 2
The following theorem by Garriga et al. [
Γ +(P ) = {i ∈ M | ∀o ∈ occ(G+, P ) contains attribute i.} Γ +(·) is called the closure on the positives , and a pattern P is closed on the positives if Γ +(P ) = P .
Theorem 1 (Garriga et al. [
We note that each concept is also closed on the positives. In particular,
supp−(0) = supp−(01) = ∅, and pattern 0 is more relevant than (or dominates)
pattern 01. 2
1 This condition is due to [
The differences of the function with CbO are threefold: (i) we use the closure function Γ + (line 10), (ii) we employ the pruning methods based on the dominance check (line 14), and (iii) we perform a modified version of the canonicity test (or the prefix-preserving test) using Im (line 13). We call it the Im-canonicity test for short.
For the pruning methods, we perform two kinds of the dominance check; the one is the dominance check between the node hA, Bi and its child node Nj = hC, Di, where D = Γ +(B ∪ {j}) (line 10), and the other is the dominance check between Nj and its sibling nodes Ni = h(Γ +(B ∪ {i}))0, Γ +(B ∪ {i})i for some i > j and i ∈ D \B. We refer to the former check as the supp−-check , while the latter one is referred to as the siblings-check for short. If D is dominated either by B or the intent of Ni, we skip the search tree rooted at Nj , and we record attribute j as “marked” and add it to Im.
We use the set Im of marked attributes in the Im-canonicity test (line 13). Since the search tree rooted at a node constructed with each of attributes in Im is pruned, we ignore those attributes in the canonicity test so that we check whether or not (B j)\Im 6= ∅, where B j = (Γ +(B∪{j})\B)∩{0, 1, . . . , j−1}.2 Algorithm 1: Generate RelSets
Input: a formal context, minsup: a minimun support threshold
Output: RelSet : the set of relevant patterns 1 RelSet := ∅; 2 call RS-GenerateFrom(h(G+)00, (G+)0i, 0, ∅); 3 Remove irrelevant patterns in RelSet 4 return RelSet 5 Function RS-GenerateFrom(hA, Bi, y, Im) is
input: a concept hA, Bi, an attribute y, a set of attributes Im.
Example 2. Figure 2 shows a dataset and the computation of Algorithm 1 for it. We can represent the computation of function RS-GenerateFrom in Algorithm 1 by a tree; each node represents an invocation of RS-GenerateFrom, and each edge in the tree is labeled by the current value of j which is used to compute a (new) concept (line 8). Leaf nodes denoted by black squares represent computed concepts for which the Im-canonicity test in line 13 fails. Leaf nodes denoted by ⊥1 (⊥2) represent computed concepts for which the supp−-check (the siblingscheck) in line 14 fails, respectively. Relevant patterns are ∅, 0 and 03.
As in Figure 2, since the computation of function RS-GenerateFrom in Algorithm 1 can be represented by a tree, we call such a tree a cPos (search) tree. We denote by N0 `T Nj if N0 has a descendant node Nj in a cPos tree T . We also write by N0 `T,I Nj if N0 has a descendant node Nj in a cPos tree T with the I-canonicity test. We denote simply by B0 `T Bj for short, where B0 (Bj ) is the set of attributes of N0 (Nj ), respectively. Similarly for N0 `T,I Nj . Lemma 1. Let N0 = hA, Bi be a node in a cPos search tree T . Suppose that N0 `T Nj = hAj , Bj i, where Nj = h(Γ +(B ∪ {j}))0, Γ +(B ∪ {j})i (j ∈ M ) and
Nj `T Nd = hAd, Bdi for some node Nd in T . Consider a subset Bd1 ⊆ Bd such that {y ∈ Bd1 | y < j + 1} = {y ∈ Bd | y < j + 1}. Then, there exist nodes Ns and Nd1 with its intent Γ +(Bd1 ) in T such that Ns is a sibling node of Nj and Ns `T,Im Nd1 for Im = Bd \ Bd1 .
Proof. Let k = min{i ∈ Bd1 | i > j}. Then, let Ns be the sibling node of Nj with its intent Bs = Γ +(B ∪ {k}). See Fig. 3. We show that Ns is not pruned by the Im-canonicity test. Let Nj1 be the node in the branch from Nj to Nd in T such that attribute k is first introduced in the branch. For the intent Bj1 of Nj1 , we have that Bj1 ⊇ Bs. Since Γ +(·) is monotone, it follows that Γ +(B ∪ {k}) passes the Im-canonicity test.
Next, we show that there exists node Nd1 such that Ns `T,Im Nd1 for Im = Bd \ Bd1 . We prove it by the induction on the size of Bd1 \ Bs. The base case Bd1 = Bs is trivial. For the induction step, let Ns1 be the child node of Ns obtained by adding to Bs k1 = min{i ∈ Bd \ Bs | i > k}. We can show that Ns `T,Im Ns1 similarly to the above. The remaining proof then follows from the induction hypothesis. 2
minimum support minsup, (i) the set of patterns given by function RS-GenerateFrom in Algorithm 1 includes all the relevant patterns, and (ii) it is a subset of the closed on the positives with the support no less than minsup.
Proof. The part (ii) is rather obvious, since the patterns generated by the function are the results of Γ +. For the part (i), since a relevant pattern is closed on the positives from Theorem 1, we show that the pruning methods, line 14 in the algorithm, do not eliminate any relevant pattern. and
Let N0 = hA, Bi be a node in a cPos search tree T . Suppose that N0 has a descendant node Nd = hAd, Bdi in T , i.e., N0 `T Nd = hAd, Bdi, and I ⊆ {y + 1, . . . , |M | − 1} (0 ≤ y < |M |) is the set of attributes added to each node in the branch br from N0 to Nd. Let
I1 = {j ∈ I | supp−(B1) = supp−(Γ +(B1∪{j})) for the intent B1 of a node in br}, I2 = {j ∈ I | Nj in br is dominated by a younger sibling node in T }.
Let Im = I1 ∪ I2. We now consider subset Bd1 = Bd \ Im. From Lemma 1, we then have that there exists a node Nd1 such that N0 `T,Im Nd1 and its intent is Γ +(Bd1 ).
We note that this derivation from N0 to Nd1 is not pruned in Algorithm 1. Moreover, Γ +(Bd1 ) is more relevant than Bd, since supp−(Bd) = supp−(Γ +(Bd1 )). 2
Grosskreutz proposed an output-polynomial time algorithm (Algorithm 2
in [
Algorithm 1 visits irrelevant patterns; its search space is the set of all closed
on the positives in the worst case. The set of all relevant patterns is obtained by
filtering in line 3. For that, we use the filtering method in [
Since the framework using the support/confidence only generates too many rules, we usually use another measure to find “interesting” ones among the generated rules. lift -value is such a measure to find correlated rules; the lift-value of a rule A → c+, where A is a pattern and c+ is a class label, is defined as the ratio P (A∧c+) . of the probability of P (A ∧ c+ | A) to that of P (c+): lift (A, c+) = P (A)·P (c+) Given a contingency table in Table 1, where given m and n are both assumed to be constants, we have that lift (A, c+) = mn · a+ab . We use the following property of lift -values: for patterns A1 and A2,
lift (A1, c+) ≥ lift (A2, c+) ↔ a1b2 ≥ a2b1, where ai (bi) (i = 1, 2) is the number of true positives (false positives), respectively. We thus have that, if A1 is more relevant than A2, then lift (A1, c+) ≥ lift (A2, c+). Algorithm 1 can be therefore utilized to find association rules with high lift -values. We show in Table 2 some datasets used in our experiments. They are from the UCI Machine Learning 3. The table shows some properties of each dataset, including the target classes considered and the number of their positive examples.
We have implemented our proposed method by using Java 8 on a PC with an Intel Core i7 processor running at 2.30GHz, 8GB of main memory, working under Windows 10 (64 bit). We have performed the following experiments with fixed min sup = 1 (i.e., all concepts). To see the effects of our pruning methods, we present some results for the Lenses dataset in Figure 4. In Algorithm 1, we incorporate into the CbO-based miner for closed on the positives (cloPos) two types of pruning methods: the supp−-check and the siblings-check.
The figure shows the number of patterns generated in computing the closed on the positives (cloPos) and that of patterns generated by using the supp−-check only, together with that of patterns generated by using both the supp−-check and siblings-check.
We have tested three cases, varying target classes: hard, soft and non-contact lenses. We have observed that the pruning method by the siblings-check enables us to generate less patterns compared with the cloPos method (i.e., without 3 http://archive.ics.uci.edu/ml/datasets/statlog+(heart). cloPos suppsibsChk 7
5 hard 3 81 81
73 pruning) and supp−-check only. Table 3 shows more detailed results, including the number of closed patterns (#(clo)) and that of relevant patterns after removing irrelevant ones (#(RPs)) (in line 3 in Algorithm 1). 4.2
In Figure 5, we present some results for the other three datasets in Table 2, Mushroom, Lymphography and the Soybean-small. The figure (left) shows the numbers of generated patterns by Algorithm 1. The figure (right) shows the corresponding execution times in milliseconds. We note that these figures use a logarithmic scale.
We have observed that the effects of the pruning method by the siblings-check on these datasets are more prominent than those on the previous Lenses dataset. The numbers of closed patterns (#(clo)) and closed on the positives (#(cloPos)) 105 86547 104 rs n e tta103 p # 102 2643 4692
2710 337 753
26 Mushroom Lymphography Soybean-small in these three datasets are orders of magnitude larger than that of the Lenses dataset. As a result, there are more chances for pruning by the siblings-check to work for reducing the number of irrelevant patterns. The execution times of these datasets are also reduced accordingly. 5
In this paper, we have considered the problem of mining relevant patterns for
labeled data from a formal context, especially focusing on the pruning methods
for reducing irrelevant patterns. Unlike the divide-and-conquer based method [
For future work, sine our algorithm visits a superset of relevant patterns from
a formal context, it will be interesting to introduce another dominance check to
reduce the search space. Another further work is to apply relevant pattern mining
to association rule mining with non-monotone measures such as lift (e.g., [
Acknowledgment The authors would like to thank anonymous reviewers for their useful comments on the previous version of the paper. This work is partially supported by JSPS Grant-in-Aid for Scientific Research (C) 18K11432.