Given a relation R ⊆ O × A on a set O of objects and a set A of attributes, the Galois sub-hierarchy (also called AOC-poset) is the partial order on the introducers of objects and attributes in the corresponding concept lattice. We present a new efficient algorithm for building a Galois sub-hierarchy which runs in O(min{nm, nα}), where n is the number of objects or attributes, m is the size of the relation, and nα is the time required to perform matrix multiplication (currently α = 2.376).
Galois lattices (also called concept lattices) are a powerful tool for data modeling. Such a lattice is built on a relation between a set of objects and a set of attributes. The main drawback of this structure is that it may have an exponential size in the number n of objects or attributes. A canonical sub-order of the lattice, its Galois sub-hierarchy (GSH, also called AOC-Poset), of much smaller size, is recommended whenever possible. This GSH preserves only the key elements of the lattice: object-concepts and attribute-concepts (also called introducers); the number of these key elements is at most equal to the total number n of objects and attributes.
Galois sub-hierarchies were introduced in software engineering by Godin et al.
[
what complicated. Their comparative experimental running times were
investigated in [
In this paper, we present a new algorithm for building Galois sub-hierarchies, which we call Hermes, with a better complexity. Hermes runs in O(nm) time, where m is the size of the relation, and is very easy to understand and implement. With more effort invested in the implementation, Hermes can be made to run in O(nα) (i.e. O(n2.376)) time, which is the time for performing matrix multiplication. Hermes works by simplifying and then extending the input relation into a relation which contains in a compact fashion all the necessary information on the elements of the GSH.
The paper is organized as follows: after this introduction, we give some notations and definitions. Section 3 briefly outlines how previous algorithms work. Section 4 proves some preliminary results and presents the algorithmic tools necessary to ensure our good complexity. Section 5 describes and analyzes in detail the successive steps of our algorithmic process. Section 6 gives the algorithm. Section 7 describes the special case for chordal bipartite relations, where the final relation can easily be obtained in O(n2) time. We conclude in Section 8. 2
The different communities handling Galois lattices and Galois sub-hierarchies use various notations. Here, we will use algebraic notations detailed below.
Given two finite sets O (of ’objects’) and A (of ’attributes’), a binary relation
R ⊆ O × A indicates which objects of O are associated with which attributes
of A. O is called the starting set of the relation. We will denote n = |O| + |A|
and m = |R|. For (x, y) ∈ R, we will say that x is an antecedent of y, and y is
an image of x. For x ∈ O, R(x) = {y ∈ A | (x, y) ∈ R} is the image set (row)
of x, and for y ∈ A, R−1(y) = {x ∈ O | (x, y) ∈ R} is the antecedent set
(column) of y. Note that notation x′ is used in FCA [
A maximal rectangle of R, also called a concept, is a maximal Cartesian sub-product of R, i.e. X × Y such that ∀x ∈ X, ∀y ∈ Y , (x, y) ∈ R and ∀w ∈ O − X, ∃y ∈ Y | (w, y) 6∈ R and ∀z ∈ A − Y , ∃x ∈ X | (x, z) 6∈ R. X is called the extent and Y the intent of concept X × Y , which is denoted (X, Y ). In our examples, we may omit set brackets when the meaning is clear. The extent and intent of concept C will be denoted Extent(C) and Intent(C). The concepts, ordered by inclusion on their extents (or dually by inclusion on their intents) form a lattice L(R) called a Galois lattice or a concept lattice.
lattice is represented by its Hasse diagram, where reflexivity and transitivity edges are omitted.
An object-concept is a concept Cx which introduces some object x: x is in
the extent of Cx but is not in the extent of any smaller concept C′ <L(R) Cx.
Dually, an attribute-concept is a concept Cy which introduces some attribute
y: y is in the intent of Cy but is not in the intent of any greater concept C′ >L(R)
Cy. Thus, the intent of object-concept Cx is R(x), and the extent of
attributeconcept Cy is R−1(y). Object-concepts and attribute-concepts are also called
introducer concepts or simply introducers. Objects are introduced from
bottom to top and attributes from top to bottom in L(R). A given concept may
introduce several objects and/or attributes. Note that [
A relation is said to be clarified when it has no identical lines. A relation is said to be reduced when it is clarified and has no line which is the intersection of several other lines. When a relation is reduced, the irreducible elements of the lattice are exactly the introducers, whereas in a non-reduced relation there will be extra introducers.
H(R) denotes the Galois sub-hierarchy (GSH) of relation R, defined by the set of introducer concepts ordered as in L(R). H(R) is then a sub-order of L(R). The elements of H(R) are generally labeled by the objects and/or attributes they introduce, defining the simplified labeling. The same simplified labeling applies to L(R), in which some concepts may have an empty label. <H(R) will be used to compare two elements of H(R), as <L(R) is used for L(R).
A linear extension of a partially ordered set P is a total order in which P is included.
Running example. Figure 1 shows the Galois
lattice L(R) (as drawn by Context Explorer [
R a b c d e f g
1 × × × × ×
2 × × × ×
3 × × × × × ×
4 × ×
5 ×
6 × ×
7 × × ×
8 × × × ×
We present a brief description of the existing algorithms for building Galois
subhierarchies; all run in O(n3) time, where n stands for the number of objects
and attributes in the input relation. The reader is referred to the corresponding
publications for detailed descriptions and to [
Pruned lattice. [
Preliminary results and algorithmic tools
The following theorem will help order the introducers:
Let Cx be the introducer of x ∈ O and Cy be the introducer of y ∈ A. – Cx ≤H(R) Cy iff (x, y) ∈ R. – Cx ≥H(R) Cy iff Intent(Cx)⊆Intent(Cy) iff Extent(Cx)⊇Extent(Cy).
In this case, (x, y) 6∈ R except if Cx = Cy.
– Otherwise, Cx and Cy are not comparable.
[
An attribute y ∈ A is said to dominate an attribute z ∈ A in R if the antecedent set of y is included in the antecedent set of z: R−1(y) ⊆ R−1(z); the corresponding relation is denoted DomA. When the inclusion is strict, the domination is said to be strict. For y ∈ A, DomA(y) = {z ∈ A | R−1(y) ⊆ R−1(z)}. This preorder defines the way attributes label the concepts of H(R) from top (the dominating attributes) to bottom (the dominated attributes).
A domination relation, DomO, can also be defined between objects by
inclusion of their image sets: ∀w ∈ O, DomO(w) = {x ∈ O | R(w) ⊆ R(x)}. The label
of H(R) will be set from bottom (the dominating objects) to top (the dominated
objects), according to the dual behavior of objects and attributes in concepts.
Theorem 2. [
Endowed with domination relation DomO, the set of object-concepts of R forms a sub-order of H(R) and L(R): for w, x ∈ O, the introducer of w is greater than or equal to the introducer of x iff (w, x) ∈ DomO.
Example. In our running example, R−1(b) = {3} ⊂ R−1(a) = {1, 2, 3, 7, 8}; attribute b dominates attribute a and the introducer of b is smaller than the introducer of a, as shown in Figure 1. DomA(b) = {a, b, c, d, f, g}. R(6) = {c, d} ⊂ R(1) = {a, c, d, e, g}; object 6 dominates object 1 and the introducer of 6 is greater than the introducer of 1. DomO(6) = {1, 3}.
We will need two processes for our complexity results.
The first process is to rapidly recognize lines of a relation which are equal,
which corresponds to the clarification of context (O, A, R). This can be done
in linear time O(|R|) by a process of partition refinement, as proved by [
The second tool we use extensively enables us to decide which lines (rows
or columns) are properly included in another, or in other words determines a
domination order. This can be done using the tripartite directed graph
introduced by Bordat [
The last step of our algorithm requires a transitive reduction which consists in removing all the transitivity edges of a partial order. This problem has the same time complexity as the equivalent problem of transitivity closure and can also be performed in the same time as matrix multiplication. 5
Our algorithm works in five simple steps: 1. Clarify the input relation R ⊆ O × A into a relation Rc where no two lines (rows or columns) are identical in order to avoid redundancy. 2. Compute the domination relation DomA between attributes (i.e. decide which columns of Rc are included into which other columns). 3. Compute a new relation Rce, obtained by appending DomA to Rc, and simplify Rce into Rces where no two rows are identical. (This simplification merges an attribute and an object whenever they are introduced by the same concept.) 4. Extract from Rces the elements of H(R), whose intents are in fact the rows of Rces and whose simplified labels are the labels of these rows in Rces. 5. Construct the Hasse diagram of H(R) from these intents.
Note that as objects and attributes play symmetric roles, the algorithm can dually use domination on objects instead of attributes. The choice may result from an unbalanced number of objects with respect to the number of attributes.
+ DomA a,g b c d e f a,g × b × × × × × c × d × e × × f × computation of DomA will require; a better average time complexity is thus obtained by separating these steps.
Example. Rc(3) = DomA(b), so 3 and b are merged in Rces, as 5 with d, and 7 with e.
Rc a,g b c d e f 1 × × × × 2,8 × × × 3 × × × × × 4 × × 5 × 6 × × 7 × × →
Rce → Rces Rces a,g b c d e f 1 × × × × 2,8 × × × 4 × × 6 × × a,g × 3,b × × × × × c × 5,d × 7,e × × f × Rc + DomA = Rce Rce a,g b c d e f 1 × × × × 2,8 × × × 3 × × × × × 4 × × 5 × 6 × × 7 × × a,g × b × × × × × c × d × e × × f × We will now prove that the starting set of Rces yields exactly the elements of H(R), because of our two-step merging process. Step 1 grouped together separately equivalent objects or equivalent attributes which trivially correspond to objects or attributes having the same introducer. Step 3 grouped together an object and an attribute whenever they have the same introducer, as proved in Theorem 3. Thus the labels of the rows of Rces are the simplified labels of H(R), and for each row, its elements yield the intent of the corresponding concept, as proved in Theorem 4. No extra computation is thus needed for this step. Example. The starting set of Rces is: { {1}, {2,8}, {4}, {6}, {a,g}, {3,b}, {c}, {5,d}, {7,e}, {f } }. Its elements correspond exactly to the simplified label of the elements of H(R) presented in Figure 1. The rows represent the intents of these elements: for example, the complete labeling of the introducer of 2 would be ({2,8},{a,g,e,f }).
Theorem 3. Given a relation R ⊆ O × A, the introducer of x ∈ O and the introducer of y ∈ A are the same if and only if Rce(x) = Rce(y). Proof. – Suppose concept Cxy is the introducer of both x ∈ O and y ∈ A. The intent of Cxy is by definition R(x), which includes y. Let z be an attribute of R(x) = Rce(x) and Cz its introducer; as (x, z) ∈ R, Cxy ≤ Cz and then Extent(Cxy)⊆Extent(Cz) (Theorem 1); therefore, (y, z) ∈ DomA and so z ∈ Rce(y); thus Rce(x) ⊆ Rce(y). Let t be an attribute in Rce(y) and Ct its introducer; (y, t) ∈ DomA, which implies Ct ≥ Cxy, and so the extent of Ct contains x, which implies (x, t) ∈ R, i.e. t ∈ Rce(x); thus Rce(y) ⊆ Rce(x). – Suppose Rce(x) = Rce(y), i.e. R(x) = DomA(y). For z ∈ DomA(y), (x, z) ∈ R, so the introducers of z and x are comparable: Cz ≥ Cx (Theorem 1); in particular, Cy ≥ Cx. By definition of the domination relation, R−1(y) ⊆ R−1(z) for all z ∈ DomA(y) = R(x) and then, by definition of the ordering of L(R), Cz ≥ Cy; the extent of Cy is included in the intersection of the extents of these Cz. As we are dealing with elements of a lattice, the extent of Cx is the intersection of the extents of all Cz, z ∈ R(x), which means Cx is the infimum (greatest lower bound) of these Cz. Finally, Cy is the minimum concept of a set of concepts of which Cx is the infimum, clearly Cx = Cy. ⋄ Consequently, the final relation Rces yields the elements of H(R): Theorem 4. The rows of Rces are in a one-to-one correspondence with the elements of H(R). More precisely, each element of the starting set is the simplified label of the corresponding element of H(R) and its image set is the intent of this concept.
Proof.
Each object or attribute has an associated introducer. Two objects (resp.
attributes) have the same introducer if and only if their image sets (resp.
antecedent sets) are equal; the corresponding lines of R have been merged in Rc.
In the other hand, by Theorem 3, an object and an attribute have the same
introducer if and only if Rce(x) = Rce(y); the corresponding lines of Rce have
been merged in Rces. As a consequence, the starting sets of Rces are the
simplified labels of the elements of H(R). Their image sets are the corresponding
intents: for x ∈ O, Rces(x) = R(x) is the intent of the introducer of x; for
y ∈ A, Rces(y) = {z ∈ A | (y, z) ∈ DomA} which corresponds to the intent of
the introducer of y.
⋄
Note that the use of DomA gives the intent sets of the elements of H(R). The
use of DomO instead would have given the extent sets. The use of both DomA
and DomO, as proposed in [
Constructing the Hasse diagram of H(R) Now all we have left to do is construct the Hasse diagram of H(R) by constructing the ordering by inclusion on the intents. This can be done in O(|O| + |A|)α) time by removing all transitivity edges, as discussed in Subsection 4.2.
Algorithm Hermes Input: binary relation R ⊆ O × A.
Output: H(R)
Compute clarified relation Rc; //merge all identical lines Compute relation DomA; //determine column inclusions in Rc Rce=Rc+DomA; //simple juxtaposition Simplify Rce into Rces; //merge all identical rows Extract the elements of H(R); //select the starting set of Rces Order the elements of H(R); //by inclusion on their image sets.
The complexity of the algorithm is bounded by Steps 2 and 5 with a time in O((|O| + |A|).|R|) or O((|O| + |A|)α), depending on the chosen implementation. 7
Specialized input: chordal-bipartite relations
A special class of relations should be mentioned in this context: relations which
correspond to ’chordal-bipartite graphs’, which are bipartite graphs containing
no chordless cycle of length six or more. This is a superclass of the relations
which have a planar lattice, but the lattice of chordal-bipartite relations remains
of polynomial size [
Relations whose corresponding bipartite graph is chordal-bipartite can be reordered so that their matrix becomes ’Γ -free’. A Γ in a matrix is a sub-matrix on 4 elements, with a unique zero in the right-hand lower corner (i.e. in matrix M, there is a pair h,i of rows, h < i, and a pair j,k of columns, j < k, such that M(h,j)=M(h,k)=M(i,j)=1 and M(i,k)=0).
This Γ -free form is obtained by computing a ’Double Lexical Ordering’
(DLO) [
Any matrix can be re-ordered to be DLO, and this is re-ordering can be done
in time O(min{m logn, n2}) [
When a relation is in such a DLO and Γ -free form, it is easy to compute DomA: take each attribute from left to right; for each attribute y, let x be the first object (from top to bottom) in the column of y (i.e. the first x such that (x, y) ∈ R); then y dominates exactly the attributes z which are to its right and that are on row x (i.e. (x, z) ∈ R).
This a consequence of the DLO and Γ -free form: in a DLO matrix, a given column can not be included in any column to its left; and in a Γ -free matrix, if w is the first row with a one in column y, for any column z at the right of y which has a one in the row of w, if column y is not included in column z, as the rows of y above w all have zeros, this might only be because of a row x after w with a one in column y and a zero in column z, i.e. because of a Γ in the matrix formed by rows w and x, and columns y and z.
Example. The following matrix is ordered in a double lexical fashion and is Γ -free. Attribute a is processed first; its first one is on row 1, so a dominates all the attributes to its right which has a one on row 1: a dominates d. Attribute b is processed next; its first one is on row 5, which has ones at the right of b for c, d and e, b dominates c, d and e. Attribute c: highest one in row 3, c dominates e. Attribute d: highest one in row 1, no one at the right, no domination. Attribute e is last and therefore can dominate no other attribute.
We conjecture that the Hasse diagram can be extracted at no extra cost. 8
building the Galois sub-hierarchy of a relation. It would be interesting to compare its running time in practice to that of the other known algorithms; we conjecture that Hermes will run faster in most cases.
may prove interesting for on-line applications such as updating hierarchies in object-oriented languages.
The authors thank Lhouari Nourine for fruitful discussions on the construction of Galois sub-hierarchies.