Dichotomic Lattices and Decision Tree. Treillis Dichotomiques et Arbres de Décision

Dichotomic Lattices and Decision Tree

Treillis Dichotomiques et Arbres de Décision

K. Bertet M. Visani  N. Girard 

Laboratory L3I - University of La Rochelle - France

Page: 
409-418
|
Received: 
15 December 2009
| |
Accepted: 
N/A
| | Citation

OPEN ACCESS

Abstract: 

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.

Résumé

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.

Keywords: 

Symbol recognition,supervised classification,lattice,decision tree.

mots clés 

Reconnaissance de symboles,classification supervisée,treillis,arbre de décision.

1.Introduction
2.Descriptions
3.Treillis Dichotomiques
4.Expérimentation
5.Conclusion et Perspectives
  References

[1] Base d’images GREC (Graphics RECognition), www.cvc.uab.es/grec2003/SymRecContest/ index.htm. 

[2] M. BARBUT and B. MONJARDET. Ordre et classification, Algèbre et combinatoire. Paris, 1970. 2 tomes. 

[3] R. BELOHLAVEK,B. DE BAETS,J. OUTRATA,and V. VYCHODIL. Inducing decision trees via concept lattices. In Fifth International Conference on Concept Lattices and their Applications (CLA’2007), pages 38-49, Montpellier, France, October 24-26, 2007. 

[4] L. BREIMAN, J.H. FRIEDMAN, R.A. OLSHEN, and C.J. STONE. Classification and regression trees. Wadsworth Inc., Belmont, California, 1984.

[5] N. CASPARD, B. LECLERC, and B. MONJARDET. Ensembles ordonnés finis: concepts, résultats, usages. Mathématiques et Applications. SPRINGER, 09 2007. 

[6] M. COUSTATY, S. GUILLAS, M. VISANI, K. BERTET, and J-M. OGIER. Flexible structural signature for symbol recognition using a concept lattice classifier. In Seventh IAPR International Workshop on Graphics Recognition (GREC’07), Curitiba, Brazil, September 20-21 2007. 

[7] S. DERRODE, M. DAOUDI, and F. GHORBEL. Invariant contentbased image retrieval using a complete set of Fourier-Mellin descriptors. Int. Conf. on Multimedia Computing and Systems (ICMCS’99), pages 877-881, june 1999. 

[8] B. GANTER and R. WILLE. Formal concept analysis, Mathematical foundations. Springer Verlag, Berlin, 1999. 

[9] S. GUILLAS. Reconnaissance d’objets graphiques détériorés: approche fondée sur un treillis de Galois. PhD thesis, Université de La Rochelle, 2007. 

[10] H. HOTELLING. Relations between two sets of variates. Biometrika, 28(2): 321-377, 1936. 

[11] S. KUZNETSOV. Machine learning on the basis of formal concept analysis. Automation and Remote Control archive, 62(10): 15431564, 2001. 

[12] S. KUZNETSOV. Machine learning and formal concept analysis. Lecture notes in computer science : Innovations in applied artificial intelligence ; From International conference on industrial and engineering applications of artificial intelligence and expert systems No17, 3029 :287–312, 2004. 

[13] E. MEPHU NGUIFO. Une nouvelle approche basée sur le treillis de Galois, pour l’apprentissage de concepts. Mathématiques et Sciences Humaines, 124: 19-38, 1993.

[14] E. MEPHU-NGUIFO and P. NJIWOUA. Treillis des concepts et classification supervisée. Technique et Science Informatiques, RSTI, 24(4): 449-488, 2005. Hermés – Lavoisier, Paris, France. 

[15] G. OOSTHUIZEN. The use of a Lattice in Knowledge Processing. PhD thesis, University of Strathclyde, Glasgow, 1988. 

[16] J. R. QUINLAN. C4.5: programs for machine learning. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1993. 

[17] J. R. QUINLAN. Induction of decision trees. Machine Learning, 1, 1986. 

[18] R. RAKOTOMALALA. Graphes d’induction. PhD thesis, Université Claude Bernard, Lyon I, Décembre 1997. 

[19] R. RAKOTOMALALA. Arbres de décision. Revue MODULAD, 33, 2005. 

[20] M. SAMUELIDES and E. ZENOU. Learning-based visual localization using formal concept lattices. In 2004 IEEE Workshop on Machine Learning for Signal Processing, page 10, 2004. 

[21] S. TABBONE and L. WENDLING. Recherche d’images par le contenu à l’aide de la transformée de Radon. Technique et Science Informatiques, 2003. 

[22] M. TEAGUE. Image analysis via the general theory of moments. Journal of Optical Society of America (JOSA), 70: 920-930, 2003. 

[23] F.J. VENTER, G.D. OOSTHUIZEN, and J.D. ROOS. Knowledge discovery in databases using lattices. Expert Systems With Applications, 13(4): 259-264, 1997. 

[24] E. ZENOU and M. SAMUELIDES. Utilisation des treillis de Galois pour la caractérisation d’ensembles d’images. In 14ème Congrès Francophone AFRIF-AFIA de Reconnaissance des Formes et Intelligence Artificielle (RFIA’2004), volume 1, pages 395-404, 2004.