Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Advances in Data Analysis and Classification
Published in: Advances in Data Analysis and Classification 1/2017

08-12-2015 | Regular Article

Dichotomic lattices and local discretization for Galois lattices

Authors: Nathalie Girard, Karell Bertet, Muriel Visani

Published in: Advances in Data Analysis and Classification | Issue 1/2017

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

The present paper deals with supervised classification methods based on Galois lattices and decision trees. Such ordered structures require attributes discretization and it is known that, for decision trees, local discretization improves the classification performance compared with global discretization. While most literature on discretization for Galois lattices relies on global discretization, the presented work introduces a new local discretization algorithm for Galois lattices which hinges on a property of some specific lattices that we introduce as dichotomic lattices. Their properties, co-atomicity and \(\vee \)-complementarity are proved along with their links with decision trees. Finally, some quantitative and qualitative evaluations of the local discretization are proposed.
previous article NMF versus ICA for blind source separation
next article Minimum Class Variance SVM+ for data classification

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
Footnotes
1
Galois lattices defined from a closed/finite data set.
 
2
The convergence property relies on the complete definition of objects, i.e. if knowledge on objects increases the concepts just become more precise and are not modified.
 
3
Considering that the number of concepts in a lattice can be exponential in the number of objects and attributes, note that concepts can be generated on demand during the navigation process, see Visani et al. (2011).
 
4
Noisy data contain useless and cumbersome information, as an example the image artefact representation in signatures extracted from images forms a noise.
 
5
Since we perform supervised classification, we focus on supervised discretization, for more details on other discretization methods the reader may refer to (Dougherty et al. 1995; Fayyad and Irani 1993; Muhlenbach and Rakotomalala 2002).
 
6
Binary table reduction deletes the attributes satisfied by all objects, and the objects satisfying all attributes.
 
7
An inseparable problem occurs when objects belonging to different classes have the same description.
 
8
For comparison with other decision trees refer to Visani et al. (2011), where experiments have shown that Galois lattice obtains better recognition rates than decision trees in a context of noisy data.
 
Literature
Barbut M, Monjardet B (1970) Ordres et classifications : algèbre et combinatoire, 2 tomes. Hachette, Paris
Bertet K, Visani M, Girard N (2009) Treillis dichotomiques et arbres de décision. Traitement Signal 26(5):407–416
Birkhoff G (1940) Lattice theory, 1st edn. American Mathematical Society, New York
Birkhoff G (1967) Lattice theory, vol 25, 3rd edn. American Mathematical Society, New York
Bordat JP (1986) Calcul pratique du treillis de Galois d’une correspondance. Math Sci Hum 96:31–47MathSciNetMATH
Breiman L, Friedman J, Olshen R, Stone C (1984) Classification and regression trees. Wadsworth Inc., Belmont
Caspard N, Leclerc B, Monjardet B (2012) Finite ordered sets: concepts, results and uses. In: Collection encyclopedia of mathematics and its applications, vol 144, Cambridge University Press, Cambridge
Coustaty M, Bertet K, Visani M, Ogier JM (2011) A new adaptive structural signature for symbol recognition by using a Galois lattice as a classifier. IEEE Trans Syst Man Cybern Part B Cybern 41(4):1136–1148CrossRef
Davey B, Priestley H (1991) Introduction to lattices and orders, 2nd edn. Cambridge University Press, Cambridge
Diday E, Emilion R (2003) Maximal and stochastic Galois lattices. Discrete Appl Math 127(2):271–284 (ordinal and symbolic data analysis (OSDA ’98), University of Massachusetts, Amherst, 28–30 September 1998)
Dougherty J, Kohavi R, Sahami M (1995) Supervised and unsupervised discretization of continuous features. In: Machine learning. Proceedings of the 12th international conference, Morgan Kaufmann, pp 194–202
Esposito F, Malerba D, Semeraro G (1997) A comparative analysis of methods for pruning decision trees. IEEE Trans Pattern Anal Mach Intell 19:476–491CrossRef
Fayyad U, Irani K (1993) Multi-interval discretization of continuous-valued attributes for classification learning. In: Proceedings of the international joint conference on uncertainty in AI, Morgan Kaufman, pp 1022–1027
Frank E, Witten I (1999) Making better use of global discretization. In: Proceedings of 16th international conference on machine learning, Bled, pp 115–123
Fu H, Fu H, Njiwoua P, Mephu-Nguifo EM (2004) A comparative study of FCA-based supervised classification algorithms. In: Concept lattices. LNCS, vol 2961. Springer, Berlin, pp 219–220
Ganter B (1984) Two basic algorithms in concept analysis. In: Technische Hochschule Darmstadt (preprint 831)
Ganter B, Kuznetsov S (2001) Pattern structures and their projections. In: Delugach H, Stumme G (eds) Conceptual structures: broadening the base. LNCS, vol 2120. Springer, Berlin, pp 129–142CrossRef
Ganter B, Wille R (1989) Conceptual scaling. In: Roberts F (ed) Applications of combinatorics and graph theory to biological and social sciences. LNCS. Springer, Berlin, pp 139–167CrossRef
Ganter B, Wille R (1999) Formal concept analysis. In: Mathematical foundations. Springer, Berlin
Godin R, Missaoui R, April A (1998) Experimental comparison of navigation in a Galois lattice with conventional information retrieval methods. Int J Man Mach Stud 38:747–767CrossRef
Guillas S, Bertet K, Visani M, Ogier JM, Girard N (2008) Some links between decision tree and dichotomic lattice. In: Proceedings CW (ed) Proceedings of the sixth international conference on concept lattices and their applications, CLA 2008, pp 193–205
Hotelling H (1936) Relations between two sets of variates. Biometrika XXVII I (2):321–377CrossRefMATH
Hwang G, Li F (2002) A dynamic method for discretization of continuous attributes. In: Yin H, Allinson N, Freeman R, Keane J, Hubbard S (eds) Intelligent data engineering and automated learning. LNCS, vol 2412. Springer, Berlin, pp 181–193
Kass GV (1980) An exploratory technique for investigating large quantities of categorical data. J R Stat Soc Ser C (Appl Stat) 29(2):119–127
Kaytoue M, Kuznetsov SO, Napoli A, Duplessis S (2011) Mining gene expression data with pattern structures in formal concept analysis. Inf Sci 181(10):1989–2001MathSciNetCrossRef
Klimushkin M, Obiedkov S, Roth C (2010) Approaches to the selection of relevant concepts in the case of noisy data. In: Kwuida L, Sertkaya B (eds) Proceedings of the 8th international conference formal concept analysis. LNCS/LNAI, vol 5986. Springer, New York, pp 255–266
Kuznetsov S, Obiedkov S (2001) Algorithms for the construction of concept lattices and their diagram graphs. In: De Raedt L, Siebes A (eds) Principles of data mining and knowledge discovery. LNCS, vol 2168. Springer, Berlin, pp 289–300CrossRef
Kuznetsov S, Obiedkov S, Roth C (2007) Reducing the representation complexity of lattice-based taxonomies. In: Priss U, Polovina S, Hill R (eds) Proceedings of the ICCS 15th international conference on conceptual structures. LNCS/LNAI, vol 4604. Springer, New York, pp 241–254
Liquière M, Mephu-Nguifo E (1990) LEGAL: LEarning with GAlois Lattice. Actes des Journées Françaises sur l’Apprentissage (JFA). Lannion, France, pp 93–113
Mingers J (1989) An empirical comparison of pruning methods for decision tree induction. Mach Learn 4:227–243CrossRef
Morgan JN, Sonquist JA (1963) Problems in the analysis of survey data, and a proposal. J Am Stat Assoc 58(302):415–434
Muhlenbach F, Rakotomalala R (2002) Multivariate supervised discretization, a neighborhood graph approach. In: Proceedings of 2002 IEEE International conference on data mining, 2002. ICDM 2003, pp 314–321. doi:10.​1109/​ICDM.​2002.​1183918
Muhlenbach F, Rakotomalala R (2005) Discretization of continuous attributes. In: Idea Group Reference (ed) Encyclopedia of data warehousing and mining, John Wang, pp 397–402
Oosthuizen GD (1988) The use of a lattice in knowledge processing. PhD thesis, University of Strathclyde, Glasgow
Quinlan JR (1979) Discovering rules by induction from large collections of examples. In: Michie D (ed) Expert systems in the micro-electronic age. Edinburgh University Press, Edinburgh, pp 168–201
Quinlan JR (1987) Generating production rules from decision trees. Proceedings of the 10th international joint conference on artificial intelligence -, vol 1. Morgan Kaufmann, San Francisco, pp 304–307
Quinlan JR (1993) C4.5: programs for machine learning. Morgan Kaufman, Los Altos
Quinlan JR (1996) Improved use of continuous attributes in C4.5. J Artif Intell Res 4:77–90MATH
Rokach L, Maimon O (2005) Decision trees. Data mining and knowledge discovery handbook. Springer, New York, pp 165–192CrossRef
Roth C, Obiedkov SA, Kourie DG (2006) Towards concise representation for taxonomies of epistemic communities. In: CLA, pp 240–255
Sahami M (1995) Learning classification rules using lattices. In: Lavrac N, Wrobel S (eds) Proceedings of the European conference on machine learning, ECML’95, Heraclion, Crete, pp 343–346
Stumme G (1996) Local scaling in conceptual data systems. In: ICCS’96, pp 308–320
van der Merwe D, Obiedkov S, Kourie D (2004) Addintent: a new incremental algorithm for constructing concept lattices. In: Eklund P (ed) Concept lattices. LNCS, vol 2961. Springer, Berlin, pp 372–385CrossRef
Visani M, Bertet K, Ogier JM (2011) Navigala: an original symbol classifier based on navigation through a Galois lattice. Int J Pattern Recognit Artif Intell 25(4):449–473MathSciNetCrossRef
Wille R (1982) Restructuring lattice theory: an approach based on hierarchies of concepts. In: Ordered sets, pp 445–470
Zhang XH, Wu J, Lu TJ, Jiang Y (2007) A discretization algorithm based on Gini criterion. In: International conference on machine learning and cybernetics, vol 5, pp 2557–2561
Zighed D, Rakotomalala R, Feschet F (1997) Optimal multiple intervals discretization of continuous attributes for supervised learning. In: Heckerman D, Mannila H, Pregibon D, Uthurusamy R (eds) Proceedings of the third international conference on knowledge discovery and data mining. AAAI Press, pp 295–298
Metadata
Title
Dichotomic lattices and local discretization for Galois lattices
Authors
Nathalie Girard
Karell Bertet
Muriel Visani
Publication date
08-12-2015
Publisher
Springer Berlin Heidelberg
Published in
Advances in Data Analysis and Classification / Issue 1/2017
Print ISSN: 1862-5347
Electronic ISSN: 1862-5355
DOI
https://doi.org/10.1007/s11634-015-0225-7

Other articles of this Issue 1/2017

Advances in Data Analysis and Classification 1/2017 Go to the issue

Editorial

Editorial for issue 1/2017

Regular Article

A generalized maximum entropy estimator to simple linear measurement error model with a composite indicator

Regular Article

NMF versus ICA for blind source separation

Regular Article

Multiple straight-line fitting using a Bayes factor

Regular Article

Minimum Class Variance SVM+ for data classification

Regular Article

Supervised box clustering

Premium Partner

    Image Credits