There are two types of classification methods using a Galois lattice: as most of them rely on selection, recent research work focus on navigationbased approaches. In navigation-oriented methods, classification is performed by navigating through the complete lattice, similar to the decision tree. When defined from binary attributes obtained after a discretization pre-processing step, and more generally when a non-empty set of complementarity attributes can be associated to each binary attribute, lattices are denoted as ”dichotomic lattices”. The Navigala approach is a navigation-based classification method that relies on the use of a dichotomic lattice. It was initially proposed for symbol recognition in the field of technical document image analysis. In this paper, we define the structural links between decision trees and dichotomic lattices defined from the same table of data described by binary attributes. Under this condition, we prove both that every decision tree is included in the dichotomic lattice and that the dichotomic lattice is the merger of all the decision trees that can be constructed from the same binary data table.
Galois lattice (or concept lattice) has first been introduced in a formal way in graph
and ordered structures theory [
Galois lattice gives a representation of all the possible correspondences (denoted as concepts) between a set of objects (or examples) O and a set of attributes (or features) I . Whereas in decision trees the path from the root to a given leaf is unique, in Galois lattices there are multiple paths from the maximal concept to a given terminal concept. Since a lattice is defined from binary attributes, the continuous-valued primitives have to be discretized (after being normalized) in a pre-processing step.
There are two types of classification methods using a Galois lattice: as most of them rely on selection, recent research work focus on navigation-based approaches. The selection-oriented methods come from the field of data mining and rely on a selection step where the Galois lattice is used to choose concepts which encode relevant information from the huge amount of available data. The classification step is then performed by some usual classifier (k-nearest neighbours, Bayesian classifier. . . ).
On the contrary, in the navigation-oriented methods there is no selection step and classification is performed by navigating through the complete lattice. Similar to the classification tree, we navigate from a node to its successors until a labeled (terminal) concept is reached. Indeed, Galois lattice is a graph whose structure is similar to that of a decision tree. Whereas in decision trees the path from the root to a given leaf is unique, in Galois lattices there are multiple paths from the maximal boundary to a given terminal concept.
This similarity between lattices used by navigation-oriented methods and decision
trees has been mentionned and stated in some works [
As a first consequence of the similarity between lattice and decision tree, the navigation-oriented methods shares the advantages of the decision tree in terms of readability and ability to automatically select discriminatory variables among a large number of variables. And, contrary to decision trees where there is a unique navigation path to a given node, lattices propose several paths. This property provides to lattices enhanced robustness towards noise.
In this paper, we precise and extend the links between these two structures of lattice and decision tree in the particular case of dichtomic lattices, i.e lattices defined from binary features where a non-empty set of complementarity attributes can be associated to each feature: – Every decision tree is included in the dichotomic lattice, when both structures are built from the same binary attributes. – Every dichotomic lattice is the merger of all the decision trees when these structures are built from the same binary attributes.
Galois lattice and the navigation-oriented method Navigala are described in Section 2. Section 3 provides a proper definition for dichotomic lattices and the two main results of this paper concerning structural links between dichotomic lattice and decision tree.
2.1
The concept lattice is built from a relation R between objects O and attributes I . This graph is composed of a set of concepts ordered by inclusion. It verifies the properties of a lattice: the relation between concepts is an order relation (transitive, reflexive and antisymmetric), and there are a lower bound and an upper bound for each pair of concepts in the graph. We associate to a set of objects A ⊆ O the set f (A) of attributes in relation R with the objects of A: Dually, for every set of attributes B ⊆ I , we define the set g(B) of objects in relation with the attributes of B: f (A) = {x ∈ I | pRx ∀ p ∈ A} g(B) = {p ∈ O | pRx ∀ x ∈ B} The relations between the set of objects and the set of attributes are described by a formal context. A formal context C is a triplet C = (O, I , R) represented by a table (see for instance Table 1).
Class Id
Y N N N Y Y Y Y Y N N Y Y Y
The two functions f and g defined between objects and attributes form a Galois connection. The composition ϕ = f ◦ g defined on the attributes set enables to associate to each subset of attributes X ⊆ I the smallest concept containing X : (g(ϕ(X )), ϕ(X )). This composition ϕ verifies the properties of a closure operator: ϕ is idempotent (i.e. ∀X ⊆ S, ϕ2(X ) = ϕ(X )), extensive (i.e. ∀X ⊆ S, X ⊆ ϕ(X )) and isotone (i.e. ∀X, X 0 ⊆ S, X ⊆ X 0 ⇒ ϕ(X ) ⊆ ϕ(X 0)).
The Galois lattice associated to a formal context C is a graph composed of a set of formal concepts equipped with a particular binary relation. Intuitively this graph is a representation of all the possible maximal correspondences between a subset of objects (or instances, examples) O and a subset of attributes (or primitives, features) I . A formal concept is a maximal objects-attributes subset where objects and attributes are in relation. More formally, it is a pair (A, B) with A ⊆ O and B ⊆ I, which verifies f (A) = B and g(B) = A. Let us introduce the binary relation ≤ defined on the set of all the concepts by, for two formal concepts (A1, B1) and (A2, B2): (A1, B1) ≤ (A2, B2) ⇔
A2 ⊆ A1 (equivalent to B1 ⊆ B2)
All the set of formal concepts equipped with the order relation ≤ forms a lattice called a concept lattice or Galois lattice. Thus, for each concepts (A1, B1) and (A2, B2), it exists a greatest lower bound (resp. a least upper bound) called meet (resp. join) denoted as (A1, B1) ∧ (A2, B2) (resp. (A1, B1) ∨ (A2, B2)) defined by: (A1, B1) ∧ (A2, B2) = (g(B1 ∩ B2), (B1 ∩ B2)) (A1, B1) ∨ (A2, B2) = ((A1 ∩ A2), f (A1 ∩ A2)) (1) (2)
Therefore, a lattice contains a minimum (resp. maximum) element according to the
relation ≤ called the bottom (resp. top) of the lattice, and denoted as ⊥ = (O, f (O))
(resp. > = (g(I), I)). For more information on Galois lattice and closure systems, the
reader can refer to [
Figure 1 shows an example of concept lattice built from the formal context in Table 1. This formal context is composed of a set of 14 objects described by 7 attributes (sun, cloudy, rain, hum < 77.5, hum ≥ 77.5, windY and windN ). 2.2
The navigation-base recognition method named Navigala (NAVIgation into GAlois
LAttice) has been introduced in [
Navigala is a supervised classification approach, no matter if the discretization preprocessing relies on a supervised or unsupervised criterion. This method relies on the classical steps of recognition: data preparation that mainly consists in discretizing continuous data, learning where the Galois lattice is built, and classification where the samples to recognize are labeled after navigating through the graph until they reach a labeled concept.
Data preparation Firstly, several signatures are extracted from the symbol images:
statistical signatures (Fourier-Mellin invariants [
Fig. 1. Example of Galois lattice criterion selects both the primitive to divide and the optimal cutting point. Let x ∈ I be a primitive interval composed of values Vx = (v1 . . . vn) sorted by ascending order. The interval will be cut between the values vj and vj+1, where v maximizes a given ”cutting” criterion of the primitive values objects. We can define a lot of cutting criteria, supervised or not. Among these criteria, let us mention maximal distance, entropy and Hotelling’s coefficient. Discretization is processed until a given stopping criterion is met. The stopping criterion used for Navigala is based on class separation, i.e. this criterion is met when each class of objects can be represented by its own set of intervals. More precisely, one class can be separated from the others when the objects characterizing this class share at least one interval which enables to distinguish them from the objects of the other classes. At the end of the process, the continuous-valued primitives are converted into intervals of values, called discretized data. Once intervals are computed, they are extended to a fuzzy number.
Learning The discretized data obtained from the data preparation will then be used as
a training set, in order to compute the Galois lattice. The generation algorithm [
Classification Using the Hasse diagram of the Galois lattice, we can process
recognition of the new symbols belonging to the test set. Classification of a new symbol is
then processed by navigating through the graph, from the minimal concept (the top >)
to a final concept which has been previously labeled by a class. Intuitively, during this
progression, we observe a specification of the objects set and a generalization of the
attributes set, that is to say that the number of objects is reduced while the number of
attributes is increased. Thus, we refine the description of the object to recognize,
until it corresponds to the description of one of the learning objects whose class will be
assigned to the object to recognize. The progression in the graph from a concept to its
successor is done according to a fuzzy distance measure and a choice criterion (for more
details please refer to [
The Galois lattice construction algorithm we use holds several advantages: it is quite easy to implement, and it enables an on-demand concepts generation of the Galois lattice. In other words, it enables to generate from a given concept every successor concept in the lattice. This is interesting because it avoids the construction of the whole graph, which can be of exponential complexity in the worst case. Indeed, recognition is performed by exploring only a small region of the lattice. On-demand concepts generation therefore considerably reduces the complexity of the structure generation.
In Navigala, the classification based on a navigation into the graph is quite similar to the one proposed with a decision tree. In this section, we describe both of these structures, and the handled data. 3.1
Since years 1960-1970, the decision tree built from a data set has been used in several
research works [
When the features are continuous-valued, as it is the case with the signatures we consider, they need a discretization step which can be processed: – during the tree construction. Only the selected features will then be discretized. – before the tree construction, in a pre-processing stage. The data will then be discretized until the classes are separated.
Several heuristics can be used for decision tree construction. For example, a pruning stage can be performed on the decision tree to avoid over-partitioning the data. The pruning principle is to raise into the tree from the leaves by changing nodes in leaves depending on a purity criterion of the nodes. In the structural comparison we describe in the following, the considered decision trees are not pruned. 3.2
As the decision tree construction infers a discretization of the data, it is possible to consider the binary data table issued from this discretization, and consequently the resulting Galois lattice. We thus find in this binary table (see Table 1), and in the Galois lattice (see Figure 1), the same binary attributes as those proposed by the decision tree (see Figure 2). Thus, when a feature V is proposed, with two children, one for yes, and the other for no, we had to consider the two binary attributes V = yes and V = no. In a more general way, the binary attributes issued from the children of a node are present into the table and separate the set of objects.
In Navigala method, features are continuous data which are discretized in a preprocessing stage in order to obtain classes’ separation. The binary attributes in the table are intervals issued from this discretization. A symbol is described by a fixed-size signature before the discretization, and then by a set of binary intervals with the same cardinality after discretization. A symbol is associated to only one interval among the set of intervals issued from a same feature.
Notice that the obtained binary attributes infer an automatic selection of the discriminant features. Indeed, an attribute belonging to all the set of objects will not been proposed in the decision tree, and consequently will not been taken into account in the table. It is the same in Navigala method where a non discretized continuous feature will not appear in the table.
When all objects in a binary table are associated to a same number of binary attributes, the final concepts (i.e. the concepts corresponding to a unique class) contain the same number of attributes. The final concepts of a lattice cannot be related the ones to the others (because two concepts in relation ≤ can not be composed of a same number of attributes). The final concepts thus have as a unique direct successor the concept >. This property can be found in lattice theory with the notion of co-atomisticity . It is the case in our approach Navigala. When discretization is performed (during decision tree construction), the table depends on the proposed attributes in the tree, and two different trees could infer two different binary attributes sets. These two attributes sets can then infer two different lattices. The discretization can also be performed in pre-processing, as in the method Navigala. From this table, several decision trees can be generated but a unique lattice will be associated.
Whatever the case, to each binary attribute x we can associate a non empty set X of binary attributes such as the objects having the attribute x, and those having the attributes in X are all distinct. The binary attributes are deduced from the decision tree: when x is a feature proposed by a node of the tree, then X is a set of all the other features proposed by this same node. Using continuous features discretized in a preprocessing stage, x corresponds to an interval, and X contains all remaining intervals corresponding to this same feature. From this property, lattices issued from a tree belong to particular lattices called dichotomic lattices. More formally, dichotomic lattices are characterized by the fact to be ∨-complementary, that is to say that for each concept (A, B), a complementary concept (A0, B0) always exists such as (A, B) ∨ (A0, B0) = > = (∅, I) (3) Proposition 1 Each dichotomic lattice (i.e. lattice issued from a tree) is ∨-complementary.
Proof. Let (A, B) be any concept of a dichotomic lattice. It consists in showing the existence of a complementary concept to (A, B). We consider x any binary attribute of B, and x a complementary attribute of x belonging to the set X. Thus, the objects having x, and those having x are distinct. This is formalized by g({x}) ∩ g({x}) = ∅. Then we consider the smallest concept containing x which, by definition, will be the concept (g(ϕ({x})), ϕ({x})) where the set of attributes is ϕ({x}). From the definition of functions f and g, we deduce that g(ϕ({x})) = g({x}), and that A ⊆ g({x}). Assuming that g({x}) ∩ g({x}) = ∅, we can then deduce that A ∩ g(ϕ({x})) = ∅. Consequently, (A, B) ∨ (g(ϕ({x})), ϕ({x})) = (∅, I), and the concept (g(ϕ({x})), ϕ({x})) is the complementary concept of (A, B). It proves the ∨-complementarity of the lattice. 3.3
A first structural link between decision tree and dichotomic lattice consists in the fact that both structures can be used in classification, and can be defined from a table of binary attributes.
We can notice that the use of navigation-based lattices for classification is similar to the one of decision trees. This similarity is formalized by a structural link between nodes and concepts: indeed, every node in the decision tree may be associated to a unique concept in the lattice. We consider a node n in the tree, and the set of binary attributes Xn proposed from the root to this node. Assuming that these binary attributes belong to the table corresponding to the lattice construction, we then associate to the node n the smallest concept containing the features of Xn: (g(ϕ(Xn)), ϕ(Xn)) (4)
Proposition 2 Each decision tree is included in the dichotomic lattice, when both structures are built from the same binary attributes.
Fig. 3. Inclusion of the decision tree (in bold) in the Galois lattice Proof. Let us consider a decision tree and a dichotomic lattice issued from the same binary attributes. As mentioned before, these two structures handle the same binary attributes. Moreover, to a node n of the decision tree accessible by validation of the set of attributes Xn we associate the concept (g(ϕ(Xn)), ϕ(Xn)). To prove that the decision tree is included into the lattice, it is necessary to prove the three following points: 1. Two different nodes of a decision tree are associated to different concepts: By contradiction, when two nodes n1 and n2 are associated to a same concept, then ϕ(Xn1 ) = ϕ(Xn2 ). It means that the same objects share the attributes of Xn1 and Xn2 , that is in contradiction with the fact that two nodes n1 and n2 are two different nodes of the decision tree. 2. When two nodes are ancestors in the decision tree, then their associated concepts are related in the lattice: Clearly when a node n1 is ancestor of a node n2 in a decision tree, then Xn1 ⊆ Xn2 . The operator ϕ being isotone, we deduce that ϕ(Xn1 ) ⊆ ϕ(Xn2 ), and consequently that these two concepts (g(ϕ(Xn1 )), ϕ(Xn1 )), (g(ϕ(Xn2 )), ϕ(Xn2 )) are related depending on the relation ≤. 3. Conversely, when two nodes are not ancestor in the decision tree, then their associated concepts are not related in the lattice: When a node n1 is not ancestor of a node n2, then we need to consider all the children of the smallest common ancestor to n1 and n2, and particularly the child n0 1 ancestor of n1 and the child n02 ancestor of n2. These two nodes n01 and n02 exist by construction of the table. Clearly, as n01 and n02 are brothers, their attributes in the associated concepts, being ϕ(Xn01 ) and ϕ(Xn01 ), are not shared by any object. That is formalized by g(ϕ(Xn01 )) ∩ g(ϕ(Xn02 )) = ∅. Then, n01 being ancestor of n1, we can deduce that Xn01 ⊆ Xn1 , where ϕ(Xn01 ) ⊆ ϕ(Xn1 ) by isotony of the operator ϕ, and reversely g(ϕ(Xn01 )) ⊇ g(ϕ(Xn1 )) by definition of g. We also have g(ϕ(Xn02 )) ⊇ g(ϕ(Xn2 )) because n02 is ancestor of n2. Thus we deduce that g(ϕ(Xn2 )) ∩ g(ϕ(Xn1 )) = ∅, and that proves that the concepts associated to the nodes n1 and n2 are not in relation by ≤.
Proposition 3 A dichotomic lattice is the merger of all the decision trees when these structures are built from the same binary attributes.
Proof. We previously proved that each decision tree is included into the dichotomic lattice built from the same binary attributes. To prove that the dichotomic lattice is the merger of all the decision trees, we must prove that each concept potentially belong to a decision tree. This proof is given by construction.
We consider an any concept (A, B). Then we build the subset of concepts C of the lattice containing: the concept (A, B), a complementary concept (A0, B0) to (A, B), the minimal concept ⊥, and all the final successors concepts of (A, B) and (A0, B0). The existence of the complementary concept (A0, B0) is deduced from the ∨-complementarity property of the dichotomic lattice. Moreover, it infers that this subset C in addition to the relation ≤ forms a tree. Then we add in the set C a maximal number of concepts of the dichotomic lattice such as (C, ≤) preserves the property to be a tree. Thus, by construction, we obtain a sub-tree included into the dichotomic lattice, containing (A, B). In this sub-tree, the leaves are final concepts and correspond to subsets of objects which can not be separated by any binary attribute, i.e. the classes when the data have been discretized until the classes are separated. This tree can thus be considered as a decision tree, what finishes this proof. 4
This paper is about Galois lattice which is used as a classifier in the Navigala approach and, more generally, about dichotomic lattices defined from a structural way: to every binary feature, a non-empty set of complementarity features can be associated.
There is some published work about using Galois lattices as a classifier: as most of the proposed approaches consider the lattice as a concept selection tool, Navigala performs classification by navigating through the lattice from one node to its successors, similar to a classification tree.
As a first consequence, the Navigala approach shares the advantages of the decision tree in terms of readability and ability to automatically select discriminatory variables among a large number of variables. As another consequence, contrary to decision trees where there is a unique navigation path to a given node, lattices propose several paths. This property provides to lattices enhanced robustness towards noise.
The inclusion result (Proposition 2) of this paper implies that navigation paths proposed by decision tree are included in the dichotomic lattice issued from the same binary features. Moreover, Proposition 3 states that the every dichotomic lattice is equal to the merge of navigation paths of all the decision trees.
This work opens the way for the definition of a new method that would combine the advantages of both trees and lattices.