The enumeration of pseudo-intents is a long-standing problem in which the order plays a major role. In this paper, we present new algorithms that enumerate pseudo-intents in orders that do not necessarily respect the inclusion relation. We show that, confirming established results, this enumeration is equivalent to computing minimal transversals in hypergraphs a bounded number of times.
Our algorithms enumerate pseudo-intents incrementally, i.e. given a formal context and a set of previously found implications, they return a new pseudointent. In order to do this, we define new conditions under which a pseudo-intent P can be recognized using the lower covers of P in the lattice of attribute sets closed under the implications already found. This allows us to build algorithms that, instead of starting from ∅ and adding attributes to construct sets, start from > and remove attributes, resulting in a depth-first search in the lattice.
We show that both constructing and recognizing a pseudo-intent can be done
c 2015 for the individual papers by the papers' authors. Copying permitted for private
and academic purposes. This volume is published and copyrighted by its editors.
Local Proceedings also appeared in ISBN 978-84-606-7410-8, Universidad de Malaga
(Dept. Matematica Aplicada), Spain.
by computing a bounded number of times the minimal transversals of some
hypergraph, which makes it easy to bound the delay and isolate special, easier
cases. This result establishes a link with the proof in [
We start by recalling in Section 2 the basic definitions of FCA and results on the enumeration of pseudo-intents and minimal transversals. In Section 3, we present the definition of a recognizable pseudo-intent that we use along with the properties needed for our algorithms. Finally, Sections 4 and 5 are dedicated to the two algorithms, an example and a brief study of their delay. 2 2.1
In formal concept analysis, data takes the form of a formal context. A formal context is a triple C = (O, A, R) in which O is a set of objects, A is a set of attributes and R ⊆ O × A a relation that maps attributes to objects. An object o ∈ O is said to be described by an attribute a ∈ A if (o, a) ∈ R. Together with the context, there are two ·0 operators defined as ·0 : 2O 7→ 2A ·0 : 2A 7→ 2O O0 = {a ∈ A | ∀o ∈ O, (o, a) ∈ R}
A0 = {o ∈ O | ∀a ∈ A, (o, a) ∈ R}
Their composition ·00 is a closure operator. A set of attributes A = A00 closed under ·00 is called an intent. 2.2
An implication is a relation between two attribute sets A and B, noted A → B. It is said to hold in the context if and only if A0 ⊆ B0 or, in other words, if and only if every object described by A is also described by B. A set I of implications is a basis if and only if every implication that holds in the context can be derived from I using Armstrong’s rules :
B ⊆ A , A → B
A → B A ∪ C → B ∪ C , A → B, B → C
A → C
A pseudo-intent (or pseudo-closed set ) P is a set of attributes that contains
the closure of all its subsets and is not an intent. The set B = {P → P 00 | P
is a pseudo-intent} is the implication basis with the minimum cardinality and
is called the Duquenne-Guigues basis [
I(A) = A++...+ (up to saturation) A◦ = A ∪ {C | B → C ∈ I and B ⊂ A}
I−(A) = A◦◦...◦ (up to saturation)
It is known that intents are closed under both B−(·) and B(·), whereas a pseudo-intent P is closed under B−(·) and I(·) for I ⊆ B \ {P → P 00}.
An attribute set Y is said to be a generator of an attribute set X under
I(·) (resp. I−(·)) if I(Y ) = X (resp. I−(Y ) = X). It is a minimal generator
if there is no generator Z of X such that Z ⊂ Y . We will use GenI (X) to
denote the set of all minimal generators of a set X under I(·). The complexity
of computing the minimal generators of a set has been studied in [
We shall use ΦI to denote the lattice of attribute sets closed under I(·) ordered by the inclusion relation. For an attribute set A, the set of pseudointents P in I such that P ⊆ A and P 00 6⊆ A will be denoted by PI (A). 2.4
The problem of computing minimal transversals in hypergraphs or, equivalently,
the prime conjunctive normal form of the dual of a Boolean function (otherwise
called monotone dualization), have been largely studied in the literature [
Given a hypergraph H = (E, V) where E is a set of edges and V ⊆ 2E is a set of vertices, a transversal T ⊆ E is a set of edges such that ∀V ∈ V, T ∩ V 6= ∅. A transversal is minimal if none of its subsets is a transversal. We shall use T r(V ) to denote the set of minimal transversals of a set of vertices V . For example, T r({ace, bce, cde}) = {c, e, abd}.
The problem of computing all the minimal transversals of a hypergraph can
be solved in quasi-polynomial total time [
In this work, we cannot presuppose the nature of the hypergraph and so we
are interested in the general case. The problem still being actively studied, we
will suppose that we have a blackbox algorithm nextTrans that enumerates
the minimal transversals of a set of vertices X. We suppose, for ease of writing,
that the transversals Ti this algorithm enumerates in some arbitrary order T1 <
T2 < ... < Tn with nextTrans(Ti, X) = Ti+1 and nextTrans(Tn, X) = ∅.
For example, Berge Multiplication [
We know that an attribute set is a pseudo-intent if and only if it contains the
closure of all its subsets that are pseudo-intents. As for the problem of recognizing
pseudo-intents, two cases have been studied. When only a context and a set A
are provided, checking whether A is a pseudo-intent is coNP-complete [
In this paper, we are interested in enumerating pseudo-intents in orders that do not extend the inclusion and, as such, we cannot suppose that we know the closure of all the subsets of a set before attempting to recognize its pseudoclosedness. Hence, we propose to consider the problem of recognizing a pseudointent A given a context and a set of subsets of A that is not necessarily complete. Proposition 1. An attribute set A ∈ ΦI is a pseudo-intent if A 6= A00 and all its lower covers in ΦI are closed.
Proof. Let us suppose that A is not closed and that all its lower covers are closed. Let B be a lower cover of A and X be a subset of A. If B ⊂ X, then I(X) = A and X00 = A00. If X ⊆ B and X00 6⊆ B, then B cannot be closed and we have a contradiction. Therefore, X00 ⊆ B. Since the closure of every subset of A is either A00 or contained in A, the set A is a pseudo-intent.
This proposition states that some pseudo-intents can be recognized in ΦI only by looking at their lower covers. As such, when I is a subset of the DuquenneGuigues basis, a new pseudo-intent can be found by looking in ΦI for sets that only have intents as lower covers. Definition 1. A pseudo-intent that can be recognized using Proposition 1 with a set of implication I is said to be recognizable. The set of all the implications that are recognizable with I is denoted by Rec(I).
Proposition 2. ∀I ⊂ B, Rec(I) 6= ∅ Proof. Let P be minimal among pseudo-intents that are not premises of implications in I. If there is a lower cover X of P in ΦI that is not closed, then there is a set A ⊂ X in ΦI such that A → A00 holds in the context. If A00 ⊆ P , then P is not minimal. If A00 6⊆ P , then P is not a pseudo-intent. Both cases lead to contradictions so all the lower covers of P are closed and P is recognizable from I. Since we have I ⊂ B, the set of pseudo-intents that are not a premise of I is not empty, so it has minimal elements. Hence, the set of pseudo-intents that are recognizable from I is not empty if I ⊂ B.
We have that, even though some unknown pseudo-intents may not be recognizable, there are always additional recognizable pseudo-intents for any subset of the Duquenne-Guigues basis. This ensures that we are able to enumerate all the pseudo-intents with an algorithm that finds recognizable ones. Proposition 3. Let A and B be two elements of ΦI . The set B is a lower cover of A if and only if B = A \ C with C a minimal transversal of GenI (A). Proof. Let C be minimal such that ∀G ∈ GenI (A), G∩C 6= ∅. For any attribute i ∈ A \ C, the set (A \ C) ∪ {i} = A \ (C \ {i}) contains a minimal generator of A because of the minimality of C. Therefore, any B between A \ C and A is such that I(B) = A and cannot be in ΦI . Hence, A \ C is a lower cover of A.
Let B be a lower cover of A in ΦI . By definition, I(B ∪ {i}) = A for any attribute i ∈ A \ B so there is a subset C of A such that i ∈ C and (C \ {i}) ⊆ B that is a minimal generator of A.
This proposition states that the lower covers of a set can be computed from
and depend on its minimal generators. As such, the number of lower covers can be
exponential in the number of minimal generators which can itself be exponential
in the size of the attribute set [
Definition 2. For any two attribute sets A and B, we say that B is reachable from A if and only if B ⊂ A and there is an ordering x1 < x2 < ... < xn of the elements of A \ B such that, for every m < n, A \ {x1, x2, ..., xm} is not closed under I.
In other words, B is reachable from A if you can obtain B by removing attributes from A and only go through sets that are not closed under I. Evidently, minimal reachable sets are elements of ΦI .
Proposition 4. An attribute set A ∈ ΦI is a minimal recognizable pseudointent if and only if A is not an intent and all the minimal attributes sets reachable from A are intents. Algorithm 1 reachableSets(A) Proof. If A is a minimal recognizable pseudo-intent, then every subset of A in ΦI is an intent. Thus every minimal reachable set is an intent.
Let us suppose that every minimal reachable subset of A is an intent and A 6= A00. For any set X reachable from A and any attribute set P ⊆ X, if P 00 6⊂ A, then X cannot be an intent. Every minimal reachable subset of A being an intent, A contains the closure of all its subsets so it is a pseudo-intent. If P is a pseudo-intent that is not in I, subsets of A \ {i} with i ∈ P 00 \ P cannot be intents so either P or a superset of P in ΦI that is not an intent is reachable from A. Hence, A is a minimal recognizable pseudo-intent.
A minimal recognizable pseudo-intent can therefore be recognized by computing the sets of its minimal reachable subsets. These minimal reachable sets can be computed using Algorithm 1. By definition, reachable sets can be computed by removing from A attributes that play a role in the logical closure, i.e. attributes in minimal generators of pseudo-intents P ⊂ A such that P 00 6⊆ A \ X for some A \ X reachable from A. The minimal transversals T make up all the possible ways to remove minimal generators of pseudo-intents and, thus, all the sets T such that for every Y ⊂ T , A \ Y cannot be logically closed. As such, removing minimal transversals of the generators of pseudo-intents used in the logical closure of a set produces a reachable set. The set A \ T is not always logically closed so the algorithm is recursively applied until an element of ΦI is reached.
The algorithm is not optimal as some reachable sets can be computed multiple times and the sets reachable from a set A that is not an element of ΦI could be computed directly from PI (A) instead of its direct subsets. However, it is sufficient to give us an upper bound of the runtime. For each recursive call, the algorithm computes PI (A \ {i}) for every attribute i ∈ A. For each of these attributes, it then computes the minimal transversals of S There is another recursive call for each pseudo-intent founPd∈mPIis(Asi\n{gi}s)oGtehneIr(uPn)-. time is bounded by O(|A| × |I| × T ) where T is the complexity of computing the transversals.
In the rest of this paper, we will suppose that we have an algorithm nextReach that enumerates minimal reachable sets in the same fashion as nextTrans. 4
4.1
We want to incrementally compute the pseudo-intents in a formal context. In
the beginning, we only have the formal context (O, A, R) and an empty set of
implications I. The corresponding ΦI is the boolean lattice of subsets of A. In
order to find a first pseudo-intent, we can look for a recognizable set (Proposition
1) in ΦI . We know that a non-closed set contains a pseudo-intent. Thus, we can
start with A and recursively remove attributes as long as we obtain non-closed
sets. When we cannot remove attributes without obtaining an intent, the set is
a recognizable pseudo-intent and we have a first implication. This corresponds
to the algorithm presented in [
Proposition 5. nextP I(A, I) returns either A or a pseudo-intent that is not in I.
Proof. Let X be a set in ΦI . If X00 6= X, then there is a pseudo-intent P ⊆ X. If a lower cover of X is not closed, then there is a pseudo-intent X ⊂ S. The algorithm returns the first set it finds that has all its lower covers closed. If this set is not A, then it is not closed and is thus a pseudo-intent.
Algorithm 3 uses Algorithm 2 to enumerate pseudo-intents iteratively until it returns A. It is sound but not complete, as exemplified below. Algorithm 2 nextP I(A, I) Let us consider an arbitrary context for which the Duquenne-Guigues basis is {de → bde, bc → bcd, ac → abcd, be → bde, bcde → abcde}. We want to find its pseudo-intents using Algorithm 3 :
The set of implications is initially empty. We start with abcde.
It has a single minimal generator, itself. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has a single minimal generator, itself. The first minimal transversal of Gen(bcde) is b. The set bcde \ b = cde is not an intent so we continue recursively with it.
The set cde has a single minimal generator, itself. The first minimal transversal of Gen(cde) is c. The set cde\c = de is not an intent so we continue recursively with it.
The set de has a single minimal generator, itself. The first minimal transversal of Gen(de) is d. The set de \ d = e is an intent. The second and last minimal transversal is e. The set de \ e = d is an intent. The algorithm returns de as the first pseudo-intent which gives us I = {de → bde}.
We start again with abcde. It has a single minimal generator, acde. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has a single minimal generator, cde. The first minimal transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal transversal is d. The set bcde \ d = bce is not an intent so we continue recursively with it.
The set bce has a single minimal generator, itself. The first minimal transversal of Gen(bce) is b. The set bce \ b = ce is an intent. The second minimal transversal is c. The set bce \ c = be is not an intent so we continue recursively with it.
The set be has a single minimal generator, itself. The first minimal transversal of Gen(be) is b. The set be \ b = e is an intent. The second and last minimal transversal is e. The set be \ e = b is an intent. The algorithm returns be as the second pseudo-intent which gives us I = {de → bde, be → bde}.
We start again with abcde. It has two minimal generators, acde and abce. The first minimal transversal of Gen(abcde) is a. The set abcde \ a = bcde is not an intent so we continue recursively with it.
The set bcde has two minimal generators, bce and cde. The first minimal transversal of Gen(cde) is c. The set bcde \ c = bde is an intent. The second minimal transversal is bd. The set bcde \ bd = ce is an intent. The third and last minimal transversal is e. The set bcde \ e = bcd is an intent. The algorithm returns bcde as the third pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde}.
We start again with abcde. It has two minimal generators, cde and bce. The first minimal transversal of Gen(abcde) is bd. The set abcde \ bd = ace is not an intent so we continue recursively with it.
The set ace has a single minimal generator, itself. The first minimal transversal of Gen(ace) is a. The set ace \ a = ce is an intent. The second minimal transversal is c. The set ace \ c = ae is an intent. The third minimal transversal is e. The set ace \ e = ac is not an intent so we continue recursively with it.
The set ac has a single minimal generator, itself. The first minimal transversal of Gen(ace) is a. The set ac \ a = c is an intent. The second and last minimal transversal is c. The set ac\c = a is intent. The algorithm returns ac as the fourth pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac → abcd}.
We start again with abcde. It has three minimal generators, ace, cde and bce. The first minimal transversal of Gen(abcde) is c. The set abcde \ c = abde is an intent. The second minimal transversal is e. The set abcde \ e = abcd is an intent. The third and last minimal transversal is abd. The set abcde \ abd = ce is an intent. The algorithm ends.
The algorithm has found four pseudo-intents but is unable to find the set bc when considering the minimal transversals, and thus the sets, in that particular order. Indeed, knowing be → bde and de → bde makes bcde recognizable and blocks every path from abcde to bc in ΦI . Finding bc before either de or be solves the problem. 4.3
The nature of Algorithm 2 makes it easy to bound the delay between finding
two pseudo-intents. As the algorithm starts from A and removes attributes until
it ends, it performs a maximum of |A| recursive calls before finding a
pseudointent. In a call, three different tasks are performed : computing the closure
of a set, computing the set of minimal generators and computing the set of all
lower covers. The closure of a set is known to be computable in polynomial time.
Computing GenI (A) is done in time polynomial in the size of the output. The
computation of all the lower covers of A, as we have seen in Section 2.4, can be
performed in quasi-polynomial total time, i.e. in time quasi-polynomial in the
size of n = |GenI (A)| and m = |T r(GenI (A))| (note that the size of m itself is
n
bounded by n [
An interesting point of detail is that the algorithm does not necessarily enumerate all the intents. When all the upper covers of an intent A in ΦI are intents themselves, A cannot be reached by the algorithm anymore. In particular, if A ∪ {i} = (A ∪ {i})00 for every i ∈ A \ A, we are sure that A will never be considered. In the previous example (see Figure 3), we see that the intents abd, ab, ad, bd, de and ∅ are never considered because they do not appear as lower covers of sets. We suppose that this property helps reduce the runtime on dense contexts with a high number of intents.
The problem with Algorithm 3 is that there are some pseudo-intents it cannot compute. Among those leftover pseudo-intents, there is necessarily at least one that is minimal. We have shown in Proposition 4 that a minimal recognizable pseudo-intent P can be recognized through the minimal sets reachable from P . Those reachable sets can themselves be obtained by computing the transversals of the sets of minimal generators of the pseudo-intents involved in the logical closure of the different P \ {i} (Algorithm 1). Algorithm 4 uses these properties to compute a minimal recognizable pseudo-intent. In a manner similar to that of Algorithm 2, the algorithm starts with A and enumerates the minimal reachable sets. Once one that is not an intent is found, the algorithm is recursively applied. The algorithm ends when it finds a set with only intents as minimal reachable sets. The main difference between Algorithm 2 and Algorithm 4 is that the former performs a depth-first search in the lattice ΦI while the latter performs it in the directed graph in which the nodes are the elements of ΦI and the edges are the pairs in the “reachable” relation.
Proposition 6. Algorithm 4 returns either A or a minimal pseudo-intent that is not in I. Algorithm 5 allP I2 1: I = ∅ 2: A = nextminP I(A, I) 3: while A 6= A do 4: I = I ∪ {A → A00} 5: A = nextM inP I(A, I) 6: end while 7: Return I Proof. From Proposition 4 we know that if every minimal set T ∈ ΦI reachable from A ∈ ΦI is closed and A is not, then A is a minimal recognizable pseudointent. If T ∈ ΦI is not closed, then T contains a minimal recognizable pseudointent so the algorithm can be recursively called on T . The algorithm stops when it encounters a set A with only intents as minimal reachable sets. The set A being the only intent on which the algorithm is called, it returns either A or a minimal recognizable pseudo-intent.
We can enumerate all the pseudo-intents with Algorithm 5 using Algorithm 4 in the same fashion as Algorithm 3.
Proposition 7. Algorithm 5 is sound and complete.
Proof. Soundness follows from Proposition 6. For any implication set I ⊂ B, pseudo-intent P not used in I and attribute set A ∈ ΦI such that P ⊂ A, no set X such that P ⊂ X and P 00 6⊆ X can be an intent so either P or one of its non-closed supersets is reachable from A. Hence, the algorithm does not stop until every pseudo-intent has been found. 5.2
Contrary to Algorithm 3, Algorithm 5 is complete. We can either use it to compute all the pseudo-intents or combine it with Algorithm 3. Let us suppose we have used Algorithm 3, as exemplified in Section 4, and that we know the set of implications I = {de → bde, be → bde, bcde → abcde, ac → abcd}. Using Algorithm 5 from there gives us the following :
We start with abcde. The first minimal reachable set abcde\(a∪bd) = ce is an intent. The second minimal reachable set abcde \ (a ∪ bc) = de is an intent. The third minimal reachable set abcde \ (a ∪ e) = bcd is an intent. The fourth minimal reachable set abcde \ (b ∪ cd) = ae is an intent. The fifth minimal reachable set abcde \ (b ∪ e) = cd is an intent. The sixth minimal reachable set abcde \ (b ∪ ce) = ad is an intent. The seventh minimal reachable set abcde \ c = abde is an intent. The eighth minimal reachable set abcde \ (d ∪ ab) = ce is an intent. The ninth minimal reachable set abcde \ (d ∪ ae) = bc is not an intent so we continue recursively with it.
The set bc contains no pseudo-intents so its minimal reachable sets are bc\b = c and bc \ c = b. They are both intents so the algorithm returns bc as a new pseudo-intent which gives us I = {de → bde, be → bde, bcde → abcde, ac → abcd, bc → bcd}.
We start again with abcde. The eight first minimal reachable sets computed are the same as in the previous step. The ninth reachable set abcde \ cde = ab is an intent. The tenth and last reachable set abcde \ e = abcd is an intent. The algorithm ends.
In this example, the pseudo-intent bc has been found after bcde. Using both Algorithm 3 and Algorithm 5, it is thus possible to enumerate pseudo-intents in orders that do not extend the inclusion. Once again, the delay between two pseudo-intents with Algorithm 5 is easy to bound. Algorithm 4 performs at most |A| recursive calls before returning a pseudo-intent or A. Each call requires the computation of, at most, all the reachable sets in ΦI . We have shown that this can be done in O(|A| × |I| × T ) with T the complexity of computing minimal transversals of minimal generators of pseudo-intents. Thus, the worst case delay of Algorithm 5 is |I| times that of Algorithm 3.
A first minimal transversal can be computed in polynomial time. As such,
for any attribute set A, we can compute its first reachable set in ΦI in time
polynomial in |A| and |I|. Hence, if, for every A ∈ ΦI that is not a pseudo-intent,
the reachable sets in ΦI are ordered in such a way that the first one is not closed,
Algorithm 5 can compute (but not necessarily recognize) a pseudo-intent in time
polynomial in the size of the implication set. A minimal pseudo-intent P , by
definition, does not contain any other pseudo-intent so the set of its reachable
set is {P \ {p} | p ∈ P } which can be computed in polynomial time. Thus,
there are always orderings of reachable sets such that Algorithm 5 can compute
minimal pseudo-intents with an incremental polynomial time between two of
them. However, as shown in [
We have proposed two algorithms for computing pseudo-intents using the computation of minimal transversals as their main operation. The first can find pseudo-intents before some of their subsets that are themselves pseudo-intents but it is not complete for some enumeration orders. The second is complete but can only enumerate in orders that respect the inclusion relation. They can be combined to obtain the enumeration order of the first with the completeness of the second. We expressed their delay as a function of the complexity of computing minimal transversals. We showed that, for some orderings of attribute sets, pseudo-intents can be reached, but not recognized, in incremental polynomial time. As both reaching and recognizing pseudo-intents, in our context, are related to the problem of computing minimal transversals in hypergraphs for which many special cases are known, we believe that this work may be useful in isolating more cases for which the enumeration of pseudo-intents is easier.
On the practical side, the fact that the algorithms do not necessarily enumerate the entirety of the set of intents should significantly reduce the runtime on dense contexts. Furthermore, the depth-first strategy used in the algorithms allows for some computations to be saved and reused. Further algorithmic optimizations and empirical comparisons with other algorithms for the same problem will be the subject of future investigations.