In this paper we study distributive lattices in the framework of Formal Concept Analysis (FCA). The main motivation comes from phylogeny where biological derivations and parsimonious trees can be represented as median graphs. There exists a close connection between distributive lattices and median graphs. Moreover, FCA provides efficient algorithms to build concept lattices. However, a concept lattice is not necessarily distributive and thus it is not necessarily a median graph. In this paper we investigate possible ways of transforming a concept lattice into a distributive one, by making use Birkhoff's representation of distributive lattices. We detail the operation that transforms a reduced context into a context of a distributive lattice. This allows us to reuse the FCA algorithmic machinery to build and to visualize distributive concept lattices, and then to study the associated median graphs.
Formal Concept Analysis (FCA) has proved to be an effective tool in data
analysis and knowledge discovery in several application domains [
Bandelt [
Uta Priss [
In this article, we propose an algorithm supporting such a transformation
that minimizes the changes introduced to the original lattice. Using the context
of an initial concept lattice as input, the algorithm outputs the context of a
distributive lattice, without necessarily building the lattice. Our approach relies
on Birkhoff’s representation of distributive lattices [
The paper is organized as follows. In Sections 2 and 3 we recall the basic background and notation as well as some key results on distributive lattices. The transformation algorithm is presented in Section 4 and we discuss the strengths and limitations of our approach in Section 5. 2
Definitions and Notations
In this section we recall basic notions and notation needed throughout the paper.
We will mainly adopt the formalism of [
A partially ordered set (or poset for short) is a pair pP, ďq where P is a set and ď is a partial order on P , that is, a reflexive, antisymmetric and transitive binary relation on P . A poset pP 1, ď1q is a subposet of pP, ďq if P 1 Ď P and ď Ďď. For a subset X Ď P , let Ó X “ ty P P : y ď x for some x P Xu and 1 Ò X “ ty P P : x ď y for some x P Xu. If X :“ txu, we use the notation Ó x and Ò x instead of Ó txu and Ò txu, respectively. In this paper, we will only consider finite posets pP, ďq and, when there is no danger of ambiguity, we will refer to them by their underlying universes P .
A set X Ď P is a (poset ) ideal (resp. filter ) if X “Ó X (resp. X “Ò Xq. If X “Ó x (resp. X “Ò x) for some x P P , then X is said to be a principal ideal (resp. filter) of P . For x, y P P , the greatest element of Ó x X Ó y (resp. least element Ò x X Ò y) if it exists, is called the infimum (resp. supremum) of x and y. A lattice is a poset pL, ďq such that the infimum and the supremum of any pair x, y P L exist, and they are denoted respectively by x ^ y and x _ y. A subset X Ď L is a sublattice of L if for every x, y P X we have that x ^ y, x _ y P X. As for posets, we will only consider finite lattices pL, ďq and we will refer to them by their underlying universes L.
In this finite setting, posets and lattices can be represented and clearly
visualized by their Hasse-diagrams [
We now recall the notions of poset and lattice homomorphisms. Let pP, ďq and pP 1, ď1q be two posets. A mapping f : P Ñ P 1 is said to be a (poset ) homomorphism if x ď y implies f pxq ď1 f pyq. In addition, if f : P Ñ P 1 is injective (one-to-one), then it is called a (poset ) embedding. If it is a bijection and an embedding such that, for every x1, y1 P P 1, x1 ď1 y1 implies f ´1px1q ď f ´1py1q, then it is called a (poset ) isomorphism.
In the case of lattices, the notions of homomorphism, embedding and isomorphism become more stringent. Let pL, ^, _q and pL1, ^1, _1q be two lattices. A mapping f : L Ñ L1 is said to be a (lattice) homomorphism if f px ^ yq “ f pxq ^1 f pyq and f px _ yq “ f pxq _1 f pyq. In addition, if f : L Ñ L1 is injective, then it is called a (lattice) embedding. If it is a bijection and it is an embedding such that f ´1 is also an embedding, then it is called a (lattice) isomorphism. When it is clear from the context, we will drop “(poset)” and “(lattice)” and simply refer to homomorphism, embedding and isomorphism.
It is noteworthy that the image f pLq of a homomorphism f : L Ñ L1 is a
sublattice of L1, and that two isomorphic lattices have the same Hasse diagram.
In particular, two lattices L and L1 are isomorphic if and only if both (1) J pLq
and J pL1q, and (2) M pLq and M pL1q are isomorphic. In the case of distributive
lattices, Birkhoff [
pO, A, Iq a formal context where O is a set of objects, A a set of attributes and I an incidence relation between objects and attributes. In phylogenetic data, objects are usually species, attributes are mutations, and po, aq P I –or oIa– when mutation a is spotted in species o.
X1 “ ty P A | xIy for all x P Xu
Y 1 “ tx P O | xIy for all y P Y u
Then a formal concept is a pair pX, Y q, where X Ď O, Y Ď A and X1 “ Y and Y 1 “ X. X is the extent and Y is the intent of the concept. The set of all formal concepts ordered by inclusion of the extents –dually the intents– denoted by ď generates the concept lattice of the context C “ pO, A, Iq.
For o P O, γo “ po2, o1q denotes the concept introducing object o. For a P A, μa “ pa1, a2q denotes the concept introducing attribute a.
A clarified context is a context such that x1 “ y1 implies x “ y for any element of O and any element of A. Moreover, a clarified context is reduced iff it contains: – no vertex x P O such that x1 “ X1 with X Ď O, x R X – no vertex x P A such that x1 “ X1 with X Ď A, x R X
The reduced context is also called a standard context. Note that the standard context of lattice L is such that O “ J pLq and A “ M pLq.
Definition 2. Let us consider a context pO, A, Iq, an object o P O and an attribute a P A, then: – oÒ a iff po, aq R I and if a1 Ď x1, a1 “ x1 then po, xq P I – oÓ a iff po, aq R I and if o1 Ď x1, o1 “ x1 then px, aq P I – o a iff oÒ a and oÓ a
Ø
Stated differently, oÓ a iff o1 is maximal among all object intents which do not contain a. It can be shown that: oÓ a oÒ a ô ô γo P J pLq and γo ^ μa “ pγoq˚pwith x˚ “ ŽpÓ xztxuqq μa P M pLq and γo _ μa “ pμaq˚pwith x˚ “ ŹpÒ xztxuqq Arrow relations are related to irreducible elements in J pLq and M pLq. In the following, we only consider arrow relations in reduced contexts.
An alternative equivalent definition of arrow relations is the following: Definition 3. Let L be a lattice, j P J pLq and m P M pLq, then: – jÒ m iff μm P maxpLz Ò γjq where maxp.q denotes the maximal elements. – jÓ m iff γj P minpLz Ó μmq where minp.q denotes the minimal elements. – j Øm iff jÒ m and jÓ m.
C “ pJ, M, I,Ó ,Ò q is the reduced context with arrow relations. It can be represented by a table with (irreducible) objects in lines, (irreducible) attributes in columns, and in cell pj, mq (intersection of row j and column m):
M3 a b c 1 ˆ 2 3 Ø Ø
Ø Øˆ Ø Øˆ
N5 a b c 1 ˆ Ó 2 3 Ò Øˆ ˆ ؈ Ø
Distributive lattice
a b c d 1 ˆ 2 3 ˆ 4
؈ ˆ ؈ ˆ ˆ
ˆ ˆ ؈ Ø
Distributive Lattices and Their Representation A lattice is distributive if ^ and _ are distributive one with respect to the over. Formally, a lattice L is distributive if for every x, y, z P L, we have that one (or, equivalently, both) of the following identities holds: piq x _ py ^ zq “ px _ yq ^ px _ zq,
piiq x ^ py _ zq “ px ^ yq _ px ^ zq.
Distributive lattices appear naturally in any classification task or as
computation and semantic models; see, e.g., [
The distributive property of lattices has been equivalently described in several ways. We recall a few useful characterizations that we will use in the following sections of the paper. Theorem 1. A lattice L is distributive if and only if one (or, equivalently, all) of the following conditions hold: 1. px ^ yq _ py ^ zq _ pz ^ xq “ px _ yq ^ py _ zq ^ pz _ xq; 2. L does not contain neither N5 nor M3 as sublattice; 3. the reduced context of L with arrow relations contains exactly one doublearrow Øin each row and in each column, and no other arrows.
The first characterization establishes a correspondence between distributive
lattices and median algebras. Indeed, a median algebra is a structure pM, mq
where M is a nonempty set and m : M 3 Ñ M is an operation, called median
operation, that satisfies the following conditions mpa, a, bq “ a and mpmpa, b, cq, d, eq
“ mpa, mpb, c, dq, mpb, c, eqq, for every a, b, c, d, e P M . It is not difficult to see
that if L is distributive, then mpa, b, cq “ pa ^ bq _ pb ^ cq _ pc ^ aq is a
median operation. The connection to median graphs was established by Avann [
The second characterization describes distributive lattices in terms of two forbbiden structures, namely, M3 and N5 (see Fig. 1) that are, up to isomorphism, the smallest non distributive lattices. The third characterization is given in terms of formal contexts and it is also illustrated in Fig. 1: neither M3 nor N5 are distributive since – for M3, there are two double arrows by row and column; – for N5, there is one double arrow by row and column, but additional simple arrows. 3.2
Let pP, ďq be a poset and consider the set OpP q of ideals of P , i.e., OpP q “ t ď Ó x | X Ď P u.
xPX It is well-known that for every poset P , the set OpP q ordered by inclusion is a distributive lattice, called ideal lattice of P , and that two posets P and P 1 are isomorphic if and only if OpP q and OpP 1q are isomorphic as lattices. Furthermore, the poset of _-irreducible elements of OpP q is
J pOpP qq “ tÓ x | x P P u and it is (order) isomorphic to P .
Dually, we saw in Subsection 2.1 that for any lattice L the set J pLq of
_irreducible elements of L is a poset ordered by inclusion, and that if two lattices
L and L1 are isomorphic, then J pLq and J pL1q are also isomorphic (as posets).
Moreover, for any lattice L the set OpJ pLqq of ordered ideals of J pLq is a
distributive lattice that contains an isomorphic copy of L as a subposet. In particular,
if L is isomorphic to OpJ pLqq, then L must be distributive. The representation
theorem of Birkhoff [
tice and J pLq. Then the mapping x ÑÓ x X J pLq is a (lattice) isomorphism from L to OpJ pLqq.
As immediate consequences we have that every (finite) distributive lattice can
be thought of as a sublattice of a powerset lattice or, equivalently, as a lattice
of ideals of a poset. Figure 2 illustrates the latter assertion: on the left is a
poset P , and on the right is the lattice of ideals of P . For an arbitrary lattice L,
not necessarily distributive, there may be several lattices such that their poset
of _-irreducible elements are isomorphic but only one of them is a distributive
lattice [
Proposal for Building a Distributive Lattice From any lattice L, we want to obtain a distributive one Ld. Moreover, we want Ld to be “similar” to L. In this work, Ld is considered as similar to L if the posets of _-irreducible elements of Ld and of L are isomorphic. In this case, L can be embedded in Ld (Ld is a _-completion of L).
With this definition of “similar” (which can dually be applied to ^-irreducible elements), we can use Birkhoff Representation Theorem to compute Ld or its reduced context.
The main idea of algorithm 1 is to compute the context of Ld from the reduced context of L as input. Our approach relies on the underlying poset pJ, ďq which is used to compute Md.
Property 1. Algorithm 1 outputs the reduced context of the ideal lattice of J pLq. Proof. By construction, there is only one double-arrow by row and by column, and no other arrows. It follows that Cd is the context of a distributive lattice As discussed in section 2.1, this lattice is the ideal poset of pJ pLq, ďq. It follows that pJ pLq, ďq and pJ pLdq, ďdq are isomorphic. \[ Algorithm 1: Construction of context of distributive lattice.
Data: Reduced context CpJ, M, Iq Result: Reduced context CdpJ, Md, Idq of pOpJ q, Ď, X, Yq Md Ð H Id Ð H foreach j P J do Ò j Ð H foreach i P J do
if j1 Ď i1 then Ò j ÐÒ j Y i Md Ð Md Y mj // add a ^-irreducible element mj such that j X Ð J z Ò j // elements of poset J which are not greater than j foreach x P X do
Id Ð Id Y px, mj q Ømj
To illustrate the algorithm, we use N5 context as input. At the beginning of the algorithm, the context Cd has |J | rows but zero columns. Each step of the external loop computes mj , a new ^-irreducible element of Cd such that j mj .
Step 1. Computation of m1 using J z Ò 1. The algorithm computes the _representation of m1, the ^-irreducible element such that 1 Øm1. At the end of this step of the loop, Cd has a unique column which correspond to m1.
Step 3. Computation of m3 using J z Ò 3. The algorithm computes the _representation of m3, the ^-irreducible element such that 3 Øm3. At the end of this step of the loop, Cd has three columns which correspond to m1, m2 and
Step 2. Computation of m2 using J z Ò 2. The algorithm computes the _representation of m2, the ^-irreducible element such that 2 Øm2. At the end of this step of the loop, Cd has two columns which correspond to m1 and to a newly computed element m2.
m1 1 2 ˆ 3 ˆ to a newly computed element m3.
The whole context Cd for Ld is now computed. By construction, the only
arrow relations are double arrows between j and mj Below, Ld is drawn with
black circles for concepts which were present in L and white circles for new
concepts.
Motivated by the work of Priss [
First, we discuss an interpretation of the behavior of the algorithm for phylogenetic data. The algorithm computes ^-irreducible elements of Ld without any consideration for ^-irreducible elements of L but, as discussed in Subsection 3.2, this is not a problem. Now, for real data, two cases may appear: 1. μmj P L: in this case, we can use the initial label m of the object (this label may represent a particular gene mutation); 2. μmj R L: this case suggests a gene mutation that is not spotted in the data, but that is necessary to provide a parsimonious tree.
Similarly, it is possible that m P M pLq but m R M pLdq but in any case, μm exists in L and Ld. This is the case when a mutation m is regarded as the infimum of other mutations.
Second, we propose an algorithm to build the context of a distributive lattice
from any context. However, it is only a partial solution to the problem considered
in [
In the following, we discuss the whole process presented in [
a b c d e
Indeed, if we were to follow the steps suggested by Priss [
Algorithm 1 then returns the context Cd1 of a distributive lattice; similarly, Algorithm 1 returns context Cd2 of L2 “Ò 2.
Moreover, in the whole lattice, every m P M 1 is greater than 1 and every m P M 2 is greater than 2. Hence we obtain the left context for the whole lattice and the reduced context on the right:
a b d 1 ˆ ˆ ˆ 2 ˆ 3 ˆ ˆ 4 5 ˆ 6 Cd1 m2 m3 m5 ˆ ˆ
The resulting lattice is presented in Figure 4.a; not every principal filter is distributive. The problem comes from the fact that the modified parts of the lattice belong to intersection of Ò 1 and Ò 2. The new added elements in a filter may belong to other filters, and this may “break” the consistency achieved in the other filters.
Now we applied this procedure in parallel for Ò 1 and Ò 2, and someone could
argue that it should be iterated filter by filter until a fixed point is reached.
Nevertheless, an optimal solution cannot be found through the general procedure
suggested by Priss [
The difficulty of simultaneously considering all the filters should be studied and solved to deal with phylogenetic data. This entails to the two following open problems.
Problem 1 (Lattice version). Given a lattice L, propose an efficient algorithm to output a lattice Ld such that: – for each atom x of Ld, Ò x is a distributive lattice, – there is an order embedding from L to Ld, and – |Ld| ´ |L| is minimal.
Problem 2 (Context version). Given the reduced context of a lattice L, propose an efficient algorithm to output the reduced context of a lattice Ld such that: – for each atom x of Ld, Ò x is a distributive lattice, – there is an order embedding from L to Ld, and – |Ld| ´ |L| is minimal.
We are currently working on these two variations of the problem. The objective is to establish an operational bridge between FCA (concept lattices) and distributive lattices to allow the use of FCA algorithms in phylogeny.