Implicational bases are objects of interest in formal concept analysis and its applications. Unfortunately, even the smallest base, the Duquenne-Guigues base, has an exponential size in the worst case. In this paper, we use results on the average number of minimal transversals in random hypergraphs to show that the base of proper premises is, on average, of quasi-polynomial size.
Computing implication bases is a task that has been shown to be costly [
In this paper, we adapt the results presented in [
The paper is organized as follows: in section 2 we introduce the definitions
and notations that we use in the remainder of the paper. Section 3 contains the
main results of this work. In section 4, we discuss randomly generated contexts
and the models that are used in this paper. We then conclude and discuss future
works.
In this section, we provide the definitions and results that will be used in this
paper. Most of the FCA definitions can be found in [
A formal context is a triple C = (O, A, R) in which O and A are finite sets of objects and attributes and R ⊆ O × A is a binary relation between them. A pair (o, a) ∈ R is read “object o has attribute a”. Formal contexts can naturally be represented by cross tables, where a cross in the cell (o, a) means that (o, a) ∈ R.
Let O be a set of objects and A a set of attributes, we denote by O0 the set of all attributes that are shared by all objects of O and A0 the set of all objects that have all the attributes of A. More formally, O0 = {a ∈ A | ∀o ∈ O, (o, a) ∈ R} and A0 = {o ∈ O | ∀a ∈ A, (o, a) ∈ R}.
The composition of those two operators, denoted ·00, forms a closure operator. A set X = X00 is said to be closed. A pair (O, A) with O ⊆ O, A ⊆ A, A0 = O and O0 = A is called a (formal) concept of the (formal) context C. In this case, we also have that A00 = A and O00 = O.
The set of all the concepts of a context, ordered by inclusion on either their sets of attributes or objects forms a complete lattice. Additionally, every complete lattice is isomorphic to the one formed by the concepts of a particular context.
Definition 1. An implication (between attributes) is a pair of sets X, Y ⊆ A. It is noted X → Y .
Definition 2. An implication X → Y is said to hold in a context C if and only if X0 ⊆ Y 0.
In an implication X → Y , X is called the premise and Y the conclusion.
Many implications are redundant, that is if an implication a → c holds, then
ab → c holds and is redundant. The number of implications that hold can be
quite large [
Definition 3. An implication set that allows for the derivation of all implications that hold in a context, and only them, through the application of Armstrong’s axioms is called an implication base of the context.
intent if and only if P 6= P 00 and Q00 ⊂ P for every pseudo-intent Q ⊂ P . The set of all the implications P → P 00 in which P is a pseudo-intent is called the Duquenne-Guigues Base.
The Duquenne-Guigues Base, also called canonical base, or stem base has
first been introduced in [
Base of Proper Premises While the Duquenne-Guigues Base is the smallest
base, the base of proper premises, or Canonical Direct Base, noted here ΣP roper,
is the smallest base for which the logical closure can be computed with a single
pass. The Canonical Direct Base was initially known under five independent
definitions, shown to be equivalent by Bertet and Montjardet in [
For a set X of attributes, let X• be the set of attributes that are contained in X00 but not in the closure of any proper subset of X, that is
X• = X00 \
! X ∪ [ S00 .
S⊂X
X is called a proper premise for attribute a if X• is not empty and a ∈ X•. 2.2
Let V be a set of vertices. A hypergraph H is a subset of the powerset 2V . Each E ∈ H is called an (hyper)edge of the hypergraph. A set S ⊆ V is called a hypergraph transversal of H if it intersects every edge of H, that is S ∩ E 6= ∅, ∀E ∈ H. A set S ⊆ V is called a minimal hypergraph transversal of H if S is a transversal of H and S is minimal with respect to the subset inclusion among all the hypergraph transversals of H. The set of all minimal hypergraph transversals of H forms a hypergraph, that we denote T r(H) and that is called the transversal hypergraph. 2.3
In this section, we introduce a definition of the base of proper premises based on hypergraph transversals.
Proposition 1 (from [
Proposition 23 from [
The set of proper premises of an attribute is equivalent to the minimal
transversals of a hypergraph induced from the context with the following
proposition:
Proposition 2 (From [
Ha = {A \ o0|o ∈ O, (o, a) 6∈ R} The set of all proper premises of a is exactly the transversal hypergraph T r(Ha).
To illustrate this link, we show the computation of the proper premises for some attributes of Context 1. We compute the hypergraph Ha for a1, a2 and a5. Let’s begin with attribute a1. We have to compute Ha1 = {A\o0 |o ∈ O, (o, a1) 6∈ R} and T r(Ha1 ). In C, there is no cross for a1 in the rows o2, o3, o4 and o5. We have :
Ha1 = {{a1, a3}, {a1, a5}, {a1, a2, a3}, {a1, a2, a4}} and
T r(Ha1 ) = {{a1}, {a2, a3, a5}, {a3, a4, a5}
We have the premises for a1, which give implications a2a3a5 → a1 and a3a4a5 → a1. {a1} is also a transversal of Ha1 but can be omitted here, since a → a is always true.
In the same way, we compute the hypergraph and its transversal hypergraph for the other attributes. For example,
Ha2 = {{a1, a2, a3}, {a1, a2, a4}} and T r(Ha2 ) = {{a1}, {a2}, {a3, a4}} Ha5 = {{a1, a5}, {a3, a4, a5}} and T r(Ha5 ) = {{a5}, {a1, a3}, {a1, a4}} The set of all proper premises of ai is exactly the transversal hypergraph T r(Hai ), ∀i ∈ {1, . . . , 5}, to which we remove the trivial transversals (ai is always a transversal for Hai ). The base of proper premises for context C is the union of the proper premises for each attributes: ΣP roper(C) = [ T r(Ha) \ {a} a∈A 3
In [
In the following, we assume all sets to be finite, and that |O| is polynomial in |A|. We call p the probability that an object o has an attribute a. An object having an attribute is independent from other attributes and objects. We denote by q = 1 − p the probability that (o, a) 6∈ R. The probability of an attribute that is not a appearing in a hyperedge of Ha is also q.
The hypergraphs that we consider in the following are sub-hypergraphs constructed from Ha by removing a and removing all the hyperedges that contained only a. The transversal hypergraph of a hypergraph constructed in this way is exactly T r(Ha) \ { }
a . This allows us to consider the transversal hypergraph without adding a as a premise for a. The average number of hyperedges of this hypergraph is m = |O| × q × (1 − p|A|−1). Indeed, there is one hyperedge for each object o for which (o, a) 6∈ R and there exists an attribute a2 such that (o, a2) 6∈ R (otherwise the edge would be empty and, as such, removed). We note n the number of vertices of Ha \ {a}. At most all attributes appear in Ha \ {a}, except a, so n ≤ |A| − 1.
edges and n vertices, with m = βnα, β > 0 and α > 0 and a probability p that a vertex appears in an edge, there exists a positive constant c such that the average number of minimal transversals is
O n d(α)log 1 m+c ln ln m
q with q = 1 − p, d(α) = 1 if α ≤ 1 and d(α) = (α+1)2 otherwise. 4α
Proposition 3 bounds the average number of minimal transversals in a
hypergraph where the number of edges is polynomial in the number of vertices.
In [
From Prop. 3 we can deduce the following property for the number of proper premises for an attribute.
Proposition 4. In a random context with |A| attributes, |O| objects and probability p that (o, a) ∈ R , the number of proper premises for an attribute is on average:
O
d(α)log p1 (|O|×(q×(1−p|A|−1)))+c ln ln(|O|×(q×(1−p|A|−1))) ! and is quasi-polynomial in the number of objects.
Proposition 4 states that the number of proper premises of an attribute is on average quasi-polynomial in the number of objects in a context where the number of objects is polynomial in the number of attributes. |A| × O As attributes can share proper premises, |ΣP roper| is on average less than d(α)log p1 (|O|×q×(1−p|A|−1)))+c ln ln(|O|×q×(1−p|A|−1))) !
Since |Σstem| ≤ |ΣP roper|, Prop. 4 immediately yields the following corollary: Corollary 1. The average number of pseudo-intents in a context where the number of objects is polynomial in the number of attributes is less than or equal to: |A| × O
d(α)log p1 (|O|×q×(1−p|A|−1))+c ln ln(|O|×q×(1−p|A|−1)) !
Corollary 1 states that in a context where the number of object is polynomial in the number of attributes, the number of pseudo-intents is on average at most quasi-polynomial. 3.2
An almost sure lower bound is a bound that is true with probability close to 1.
In [
edges and n vertices, and a probability p that a vertex appears in an edge, the number of minimal transversals is almost surely greater than
LMT = n log 1 m+O(ln ln m)
q
Proposition 5 states that in a random context with probability p that a given object has a given attribute, one can expect at least LMT proper premises for each attribute.
Proposition 6. In a random context with |A| attributes, |O| objects and probability q that a couple (o, a) 6∈ R, the size of ΣP roper is almost surely greater than |A| × (|A| − 1)
log p1 (|O|×q×(1−p|A|−1))+O(ln ln(|O|×q×(1−p|A|−1)))
As Prop 6 states a lower bound on the number of proper premises, no bound on the number of pseudo-intents can be obtained this way.
In this section we consider a multi-parametric model that fits real life data better. In this model, each attribute j has a probability pj of appearing in the description of a given object. All the attributes are not equiprobable.
We consider a context with m objects and n attributes. The set of attributes is partitioned into 3 subsets: – The set U contains the attributes that appear in a lot of objects’ descriptions (ubiquitous attributes). For all attributes u ∈ U we have qu = 1 − pu < mx with x a fixed constant. – The set R represents rare events, i.e. attributes that rarely appear. For all 1 attributes r ∈ R, we have that pr = 1 − ln n tends to 0.
– The set F = A \ (U ∪ R) of other attributes.
Proposition 7 (Reformulated from theorem 3 [
Proposition 7 states that when most of the attributes are common (that is, are in the set U ), |ΣP roper| is on average at most polynomial. When there is a logarithmic quantity of rare attributes (attributes in R), |ΣP roper| is on average at most quasi-polynomial (in the number of objects). When most of the attributes are rare events, |ΣP roper| is on average at most exponential.
As in the single parameter model, Prop. 7 also yields the same bounds on the number of pseudo-intents. 4
The topic of randomly generated contexts is important in FCA, most notably
when used to compare performances of algorithms. Since [
As an answer to the Stegosaurus phenomenon raised by experiments on
random contexts, in [
In [
The partition of attributes induced by the multi-parametric model allows
for a structure that is close to the structure of real life datasets [
In this paper, we used results on average-case combinatorics on hypergraphs to bound the average size of the base of proper premises. Those results concerns only the proper premises, and can’t be applied on the average number of pseudointents. However, as the Duquenne-Guigues base is, by definition, smaller than the base of proper premises, the average size of the base of proper premises can serve as an average bound for the number of pseudo-intents.
This approach does not give indications on the number of concepts. However,
there exists some works on this subject [
As the average number of concepts is known [
This research was partially supported by the European Union’s “Fonds Europ´een de D´eveloppement R´egional (FEDER)” program.