Treillis dichotomiques et arbres de décision

Show full item record

Files in this item

PDF 07•Bertet (2009009).pdf 319.6Kb

Pour citer ce document :
URI: http://hdl.handle.net/2042/32612
Title: Treillis dichotomiques et arbres de décision
Author: BERTET, K.; VISANI, M.; GIRARD, N.
Abstract: Dans ce papier, nous nous intéressons aux treillis dits treillis dichotomiques, définis à partir d'attributs binaires possédant une propriété de complémentarité par la borne supérieure. Il s'agit de la structure de treillis utilisée dans la méthode Navigala, méthode de reconnaissance de symboles basée sur un parcours (de type arbre de décision) dans le treillis. Nous mettons en évidence les liens structurels unissant les arbres de décision et les treillis dichotomiques en montrant tout d'abord que tout arbre de décision est inclus dans le treillis, mais également que le treillis est en fait la fusion de tous les arbres de décision. De ce lien de fusion nous déduisons un algorithme d'extraction d'un arbre de décision à partir d'un treillis dichotomique. Nous finissons par des expérimentations visant à comparer, pour de la reconnaissance de symboles, les performances des arbres de classification et des treillis construits avec la méthode Navigala.
Description: In this paper, we introduce a family of Galois lattice denoted as "dichotomic lattices". Such lattices are defined from binary attributes, where each binary attribute may be associated to a non-empty set of complementary attributes. In particular, lattices defined by binary attributes obtained after e discretisation pre-processing step are dichotomic. 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. In navigation-oriented methods, classification is performed by navigating through the complete lattice, similar to the decision tree. 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.
Subject: Reconnaissance de symboles, classification supervisée, treillis, arbre de décision; Symbol recognition, supervised classification, lattice, decision tree
Publisher: GRETSI, Saint Martin d'Hères, France
Date: 2009

This item appears in the following Collection(s)

Show full item record





Advanced Search