2
$\begingroup$

A context is a tuple $(O, A, R)$ where $O$ is the set of objects, $A$ the set of attributes and $R \subseteq O\times A$ is a relation. For $o \in O$ and $a \in A$ we read $oRa$ as the object $o$ possesses the attribute $a$.

For $P \subseteq O$ and $B \subseteq A$ we define $P'=\{a \in A | \forall o \in P \, oIa \}$ and $B'=\{o \in O | \forall a \in B \, oIa \}$.

$P'$ is the set of attributes shared by all object of $P$ and $B'$ is the set of objects having all the attributes of $B$.

A concept of the context $(O, A, R)$ is a couple $(P, B)$ where $P \subseteq O$ and $B \subseteq A$ such that $P'=B$ and $P=B'$.

The concepts may be organised according to a partial order in a structure called a concept lattice (or "galois" lattice). For more info check the wikipedia page on Formal Concept Analysis.

The number of concepts in a concept lattice is bounded by :

  • $2^{1+\sqrt{|R|}}$ as told in this paper (which mentions a result from this paper in german). Note that their upper bound is tighter - the one I give here is less precise.
  • $2^{|O|+|A|}$ according to this paper (which is presented as a trivial easy upper bound).

I dont understand why these upper bounds are that large. Intuitively I would say that the number of concepts is bounded by $min(2^{|O|}, 2^{|A|})$. I get this intuition from the observation that since for any pair of concepts $(P_0, B_0)$ and $(P_1, B_1)$ we have $P_0=P_1$ iff $B_0=B_1$, then there can not be more concepts than the number of object sets neither than the number of attribute sets appearing in the lattice.

Could someone explain me if I did a mistake ?

Many thanks, Luz

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ I don’t see what is the problem. Yes, $\min\{2^{|O|},2^{|A|}\}$ is an upper bound. The bound in the second paper is, as you say, “presented as a trivial easy upper bound”, which means there is nothing remarkable on the fact that it is not a good bound, nor is it worth wasting more than a minute to think about. The bound mentioned in the first paper (but coming from a completely different paper [13]) is strictly speaking incomparable with your bound, but usually it is stronger in typical cases where $|O|\sim|A|$. $\endgroup$
    – Emil Jeřábek
    Commented Feb 22, 2017 at 14:40
  • $\begingroup$ Thank you for answering :) I'm sorry if my question was trivial. But the fact is that I did not find this easy upper bound $min\{2^{|O|}, 2^{|A|}\}$ anywhere... Those two bounds are the only one I could find. And this made me hesitate. Especially $2^{1+\sqrt{|R|}}$ for which if $|O|$ is much greater than $|A|^2$ then their upper bound leads to something close to $2^{1+\sqrt{|O|}}$, whereas the best upper bound is simply $2^{|A|}$. Maybe those papers should have written that a simple immediate upper bound is $min\{2^{|O|}, 2^{|A|}\}$ for newbies like me :) $\endgroup$
    – Luz
    Commented Feb 22, 2017 at 15:04
  • $\begingroup$ Do you think that by integrating the $2^{1+\sqrt{|R|}}$ upper bound we can say that one "good" upper bound is $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}} \}$ ? $\endgroup$
    – Luz
    Commented Feb 22, 2017 at 15:08
  • $\begingroup$ Yes, why not, if you have access to all the three parameters. $\endgroup$
    – Emil Jeřábek
    Commented Feb 22, 2017 at 15:34

1 Answer 1

Reset to default
1
$\begingroup$

As told in the previous comments, $min\{2^{|O|}, 2^{|A|}\}$ is a correct upper bound.

When the parameter $R$ is also available, we can improve the upper bound to $min\{2^{|O|}, 2^{|A|}, 2^{1+\sqrt{|R|}}\}$

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.