In this paper we present a method (linear in the size of the formal context) to solve the seriation problem for formal contexts. We show that any maximal solution can be represented by a PQ-Tree. Moreover, the set of PQ-Trees can be seen as a distributive lattice. This lattice yields a consensus method which deals with the multiple solutions.
The classical problem of seriation in Archeology [9] is the following: we are given a set of objects (di erent kinds of necklace, bracelet, dishes. . . ) and a set of sites (tombs, houses,. . . ). Each object has been used during an interval of time, and each site contains objects. The problem is to order the sites along time. More generally, the seriation problem consists in nding a linear order which underlies a data set, and this problem arises in genetics [2, 6], hypertext browsing [3], philology [4], data visualization [7, 10], musicology [8], . . . ; the order can be time, altitude, dispersion along a river, in uence of an author, or even an unknown reason.
Formally speaking, a seriation problem instance can be represented by a formal context (G; M; I) where, for the classical problem in archeology, G is the set of sites, M the set of objects and I the relation which states if an object m has been found in site g.
In exact seriation, there exists a linear order (said compatible) such that A is an interval for any formal concept (A; B). The problem is to nd one (or all the) compatible orders. Since the intersection of two intervals is also an interval, it is su cient to check the inf-irreducible elements of the associated concept lattice, i.e. the columns of the formal context matrix. In this case, the formal context matrix M is said to have the Consecutive One's Property (C1P); that is the lines of M can be reordered in such a way that on every column of M, the 1s appear in consecutive order. Note tat the C1P is not a symmetrical property. Indeed, e.g. for the classical problem in archeology, the objects organize the sites into a linear order (the time), but the converse is false.
An optimal algorithm to nd all the compatible orders was introduced in 1976 [5], based on a special data structure: PQ-Trees.
In approximate seriation, the data is not accurate (e.g. a site may not contain an object that was used when it was built); and the formal context matrix M does not have the C1P. We suppose (for extra reasons) that there exists a linear order which underlies the data set and the problem is to nd one (or several) such order. There are two basic approaches for approximate seriation: (i) Minimally modify M so that it has the C1P (this yields to an NP-Hard problem); (ii) Find a maximal submatrix which has the C1P. In the formal concept framework, this approach consists in nding a sub-lattice of the formal concept lattice.
The aim of this paper is, following approach (ii), to present an e cient algorithm for approximate seriation, also based on PQ-Trees. This paper is organized as follows: in Section 2, we present the PQ-Tree structure and a rst algorithm which follows approach (ii). In Section 3, we show that the set of PQ-Trees can be organized as a lattice, which generalizes the semilattice of hierarchies; and we give a second algorithm which constructs a consensus between the possibly multiple solutions of the algorithm given in Section 2. In Section 4, we present a possible work ow of our method on an archeological data set. Actually, this work ow makes several runs of the algorithm of Section 3. The inputs of these runs strongly depends on the data and thus has to be decided by the user. 2
Given a nite set X, a PQ-tree T on X is a tree that represents a set of permutations on X denoted by ST . The leaves of T are the elements of X, and the nodes of T are of two types : the P-nodes and the Q-nodes. We represent P-nodes by ellipses, and Q-nodes by rectangles.
On a P-node, one can apply any permutation of its children (equivalently, its
children are not ordered). The children of a Q-node are ordered, and the only
permutation we can apply on them is to reverse the order. For instance, the
PQTree of Figure 1 represents the set of permutations f(
Let M be a formal context matrix. An order on the lines of M is compatible if, when the lines of M are sorted along , on each column of M, the 1's are consecutive. If M has the Consecutive One's Property (i.e. if there exist compatible orders), the set of all compatible orders can be represented by a (unique) PQ-Tree. For instance, the cross-table of Figure 2 has the C1P and its compatible orders are represented by the PQ-Tree of Figure 1. Fig. 3. Extension of the Cross Table 2 (left) and its associated lattice (right).
Given a Formal Context M satisfying the C1P, the associated PQ-Tree is a condensed representation of the associated concept lattice: if we add to M columns which are nonempty intersections or non-disjoint unions of already existing columns, the associated PQ-Tree remains unchanged. This is why we will use PQ-Trees as a representative of concept lattices to solve seriation problems.
Generally, a formal context does not have the C1P, as that associated with the cross table of Figure 3. We can remark that, although this example was built by adding columns to the example of Figure 2, it is not easy to construct the concept lattice of Figure 2 directly from the one of Figure 3.
A rst way to solve the approximate seriation problem consists in nding a maximal set of columns M 0 such that MjM0 has the C1P and exhibit the compatible orders. There exist several maximal sets of attributes having C1P; for instance, the cross-table of Figure 3 admits f0; 1; 2; 4g (see Figure 4) or f1; 3; 4g (see Figure 6). Remark that the concept lattices of Figures 4 and 6 are sublattices of the one of Figure 3. In addition, for each concept (A; B), A is an interval for any compatible order.
This is made possible by the incremental nature of the Booth and Lueker algorithm, which considers one column of the matrix at each step. In addition, starting with this maximal set M 0, it is easy to nd the associated concepts: their extensions are the columns and the 2-intersections of columns (the intersection of three intervals is the intersection of two of them).
The Booth and Lueker algorithm [5] relies on a function Update Tree(T; A), where T is a PQ-Tree on X and A a subset of X. Update Tree returns a PQTree T 0 where ST 0 is the set of all permutations of ST such that, when X is sorted along , A is an interval of X (if there is no such permutations, T 0 is None); for instance, with the PQ-Tree of Figure 1 and the set f1; 3; 4g (column 4 of Figure 3), Update Tree returns the PQ-Tree of Figure 4. Update Tree runs in O(n), where n is the size of the column (i.e. the number of lines of the matrix). Given an n m f0; 1g-matrix M, the algorithm of Booth and Lueker starts with the PQ-Tree Un which represents all permutations on f1; : : : ng (Un has n leaves and one internal node (its root) which is a P-node) and apply Update Tree for all columns of M. By this way, it determines if M has the C1P in O(nm). Fo instance, applying this algorithm on the cross table of Figure 2, the algorithm runs as on Figure 5.
More generally, given a subset S of 2X , we can apply the algorithm of Booth and Lueker on S and obtain a PQ-Tree T = BL(S) such that, for any permutation represented by T (and only for them), when X is sorted along , all the elements of S are intervals.
So, given a column order , Algorithm Maximal-C1P-Construction gives a solution to the approximate seriation problem in linear time. For the formal context of Figure 3, if we consider the columns in increasing order, this algorithm returns the PQ-Tree of Figure 4 and rejects the column 3, which is not compatible with the 3 rst columns.
Algorithm Maximal-C1P-Construction(M; ) Input A n m f0; 1g-matrix M .
A permutation on the columns of M .
Output A Maximal set C of columns of M such that MjC has C1P;
A PQ-Tree T representing the compatible permutations. begin
T Un ; C ; ; ForAll columns c of M taken along
T 0 Update Tree(T; c) ; If T 0 6= None Then
T T 0 ;
C C [ fcg ; return T; C ; end Do
If the matrix has not the C1P, there are many solutions depending on the order . For instance, if we consider the columns of the formal context of Figure 3 in reverse order, we keep the columns 4, 3, 1 and obtain the PQ-Tree of Figure 6.
We can see that the maximal sets of compatible columns do not have all the same number of elements. Since Maximal-C1P-Construction is very e cient, it is possible to try many orders on the columns and then take the greatest obtained set. The problem is that there may exist many such sets. We will see in next Section that it is possible to go over that by using the lattice structure of PQ-Trees. 3
We will show here that the PQ-Trees on a set X can be organized as a distributive lattice. This will allow us to build a consensus (by taking the join) of several PQ-Trees given by Algorithm Maximal C1P Construction. For instance, the PQ-Tree of Figure 7 is the join of the PQ-Trees of Figures 4 and 6.
We denote by TX the set of all PQ-Trees on a nite set X. Given two elements T1 and T2 of TX , we say that T1 T2 if ST1 ST2 . We will show that (TX ; ) is a distributive lattice, which generalizes the semilattice of hierarchies (a hierarchy can be seen as a PQ-Tree with only P-Nodes). This will allow us to de ne a consensus between the di erent solutions of Maximal-C1P-Construction. fSjk=i X( k); 1
Given a PQ-Tree T on X, the Interval Set of T (denoted by Int(T )) is the set of all nonempty subsets S of X such that, for every permutation compatible with T , when X is sorted along , S is an interval, i.e. Int(T ) is the greatest subset P of 2X n f;g such that BL(P ) = T . Equivalently, S 2 Int(T ) () Update Tree(T; S) = T .
Let be a node, we denote by X( ) the set of the leaves under . If is a Q-node with sons (in this order) 1; : : : p, we denote by Xd() the set i < j
pg (remark that Xd() is a set of sets). We have: Property 1 Int (T ) = fX( ); node of T g [
S
Q-node of T
Xd().
Proof. Let I(T ) = fX( ); node of T g [
Q-node of T permutation represented by T , all subsets of X in I(T ) are intervals. So I(T ) Int(T ).
Conversely, let S be a subset of X not in I(T ). We are in one of the following cases: S
Xd(). Clearly, for every 1. 9 node
s.t. X( ) \ S 6= ;, X( ) 6 S, S 6 X( ).
Suppose that there exists an ordering = (x1; x2; : : : xn) of X, compatible with
T , such that S is a proper interval xi; : : : xj of X. In Case 1, we can suppose that
X( ) = fxk; : : : xlg, with i < k j < l. By reversing X( ), we get a compatible
ordering of X for which S is not an interval. In Case 2, we can suppose that
X(
In Case 3, let x 2 X( i), y 2 X( j) n S and x 2 X( k). For any compatible ordering of X, x < y < z, and thus X is not an interval.
S, S, tu Clearly: Property 2 T1
T2 () Int(T2)
Int(T1).
Theorem 1 (TX ; ) is a distributive lattice.
Proof. By Property 2: T1^T2 = BL(Int(T1)[Int(T2)) and T1_T2 = BL(Int(T1)\ Int(T2)).
In addition, if T1, T2 and T3 are PQ-Trees, Int(T1) [ (Int(T2) \ Int(T3)) = (Int(T1)\Int(T2))[(Int(T1)\Int(T3)), i.e. T1 ^(T2 _T3) = (T1 ^T2)_(T1 ^T3); so (TX ; ) is a distributive lattice. tu
In addition, by Property 1, T1 _ T2 and T1 ^ T2 can be computed in O(n3). Remark that, to compute T1 ^ T2, we can use the sets fX( i) [ X( i+1); 1 i < pg instead of Xd() for all Q-nodes with sons 1; : : : p. Thus T1 ^ T2 can be computed in O(n2).
The largest element of (TX ; ) is the universal tree UjXj which represents all the permutations on X and the smallest one is None which represents no permutation.
The join of the PQ-Trees of Figure 4 and 6 is represented on Figure 7. The PQ-Trees of Figure 4 and 6 represent respectively 4 and 8 permutations. Their join represents 16 permutations, which is very close to the theoretical minimum of 12, especially when compared to the 720 possible permutations on f0; : : : ; 5g. In addition, we can see that, for all the permutations represented by this PQTree, the set f1; 2; 3; 4g is ordered in (2; 1; 3; 4); (2; 3; 1; 4); (4; 1; 3; 2) or (4; 3; 1; 2), as for the two PQ-Trees of Figure 4 and 6.
Conversely, the meet of the two PQ-Trees of Figure 4 and 6 is None, since these two PQ-Trees are compatible with maximal sets of columns. This situation will occur with any two PQ-Trees obtained with Maximal-C1P-Construction: they are built from maximal sets of columns of M and thus the permutation sets that they represent are already minimal.
We can now improve our algorithm by taking, from the best solutions obtained by Maximal-C1P-Construction a consensus made of the join of these solutions. More precisely:
Algorithm Approximate Seriation(M; ) Input A n m f0; 1g-matrix M .
A positive integer < m
A positive integer N b T rials Output A PQ-Tree T representing the compatible permutations.
The set C of columns which have been taken into account. begin
E
; ; C ; ;
For i end 1 To N b T rials Do random permutation on f1; : : : ; m ; (T; C) Maximal-C1P-Construction(M; ) ; If Card(C) Then
E E [ fT g ;
C C [ C ; ==E = fTi1 ; Ti2 ; : : : ; Tip g return Ti1 _ Ti2 _ : : : _ Tip , C;
This algorithm runs in O(N b T rials n m + p n3), where p is the number of column sets of size having the C1P. The result is a consensus of all \good" PQ-Trees, where \good" means that the PQ-Tree is built on at least columns of the matrix. The value of must be determined by the user and depends on the data. In next Section, we will apply our algorithm on a real data set and we will see how to choose . Moreover, we will see that the use of the algorithm may need other actions of the user.
We have experimented our method on a recent archeological data set which is shown in Table 1. This example shows an application where the seriation problem consists in nding trends in the data. In the original paper, the author uses principal component analysis to do that. Our method allows to achieve similar results for binary data, with PQ-Trees replacing principal axes.
The rst step is to nd maximal sets M 0 of columns such that the table induced by M 0 has the C1P. To do that, we have made 200 millions trials of Maximal-C1P-Construction with random order of the columns.1 We found 1563 maximal sets, of size going from 5 to 11. Their distribution is shown in Table 2.
At this step, we made a consensus between all the solutions with maximum number of columns, i.e. we make Approximate Seriation run with = 11. We obtained the PQ-Tree of Figure 8. 1 200 millions is very small when compared to the 31! possible orders of the column set, but actually, we made 20 series of 10 millions of trials. For each of these 20 series, no maximal set M 0 has been found after trial 50,000. In addition, the maximal sets were the same for the 20 series. It is thus reasonable to suppose that we have found all the maximal sets M 0.
This PQ-Tree takes into account 22 columns, but it represents too many permutations (informally speaking, the corresponding consensus is too \soft"). In addition, since it corresponds to a consensus, we cannot build the associated lattice, but all the possible concepts are intervals of the PQ-Tree.
We can remark that all the lines/huts are grouped together except lines 12, 14 and 16. So we put these lines appart from the others (technically, we lled them with 0) and we determine the maximal sets of columns of the transformed table which have the C1P (in exactly the same way that for the complete table). We get the results of Table 3.
The PQ-Tree built on the greatest maximal set of columns (the columns 2, 3, 4, 8, 10, 11, 14, 21, 22, 27, 28 and 30), and all lines except the lines 12, 14 and 16, is shown on Figure 9. Since it is unique, it corresponds to a maximal sub-context (having C1P) of Table 1, whose concept lattice is shown on Figure 10.
This PQ-Tree takes into account only 12 columns, but it is possible to go further that solution. Since their is only one maximal column set of size 12 having C1P, we take the join of all PQ-Trees built on column sets of size 11 and we get the PQ-Tree of Figure 11. This PQ-Tree represents a lot of permutations, but we can see that lines 15 and 17 are appart from the others. So we put them appart and we get the results of Table 4. The consensus of the PQ-Trees corresponding with sets of size 13 is the one of Figure 12. This PQ-Tree takes into account 22 columns (the columns 0, 1, 2, 3, 6, 7, 8, 9, 11, 12, 13, 15, 16, 17, 18, 19, 21, 25, 26, 27, 28 and 29) and represents 2,985,984,000 permutations, which is 167,000 times less that the PQ-Tree of Figure 8.
We have seen that one can associate, with each formal context, maximal (in lines and columns) sub-contexts satisfying the C1P, that we could name Seriation Formal Concepts. The intersection of two seriation formal concepts C1 and C2 is a seriation formal concept (its PQ-Tree is the meet of the two PQ-Trees associated with C1 and C2). So, with any formal context, we can associate the semi-lattice of its seriation formal concepts. At the present time, we are able to determine all the seriation formal concepts containing a given set of lines. We are working on an algorithm which computes all the seriation formal concepts and generates the seriation formal lattice. 5
We have presented in this paper an interactive framework to solve the approximate seriation problem for formal contexts. More precisely, this framework uses some runs (3 for our example) of Approximate Seriation, which is in O(N b T rials n m + p n3). We have used a very high value for N b T rials (up to 200 Millions, but 50,000 trials would have yield the same result). Moreover, since only the large column sets having the C1P are interesting for us, a small number of trials would have been su cient ( 1000 in our case).
As usual in approximation problems, we are dealing with several criteria which are important to determine the quality of the resulting PQ-Tree: { The number of columns taken into account (the largest possible). { The number of removed lines (the smallest possible). { The number of represented permutations (the smallest possible) { The possibility to build a concept lattice from the solution.
If a formal context admits an exact solution to the seriation problem, then its underlying structure can be represented by a PQ-Tree. If it is not the case, we can build a consensus PQ-Tree which is a solution to the approximate seriation problem but at the present time, we are not able to build an associated concept lattice. Moreover, from this work appears the new notion of seriation formal concepts and semilattices.