Inducing decision trees via concept lattices1

^1. The paper is an extended version of a conference paper presented at CLA 2007, Montpellier, France, 24–26 October 2007.

Abstract

We present a novel method for the construction of decision trees. The method utilises concept lattices in that certain formal concepts of the concept lattice associated to input data are used as nodes of the decision tree constructed from the data. The concept lattice provides global information about natural clusters in the input data, which we use for selection of splitting attributes. The usage of such global information is the main novelty of our approach. Experimental evaluation indicates good performance of our method. We describe the method, experimental results, and a comparison with standard methods on benchmark datasets.

Keywords:

• decision trees
• classification
• machine learning
• concept lattice
• formal concept analysis

Acknowledgements

Supported by grant No. 1ET101370417 of GA AV C˘R, by institutional support, research plan MSM 6198959214, and by the Bilateral Scientific Cooperation Flanders–Czech Republic, Special Research Fund of Ghent University (Project No. 011S01106).

Notes

^1. The paper is an extended version of a conference paper presented at CLA 2007, Montpellier, France, 24–26 October 2007.

^2. Weka is a free software available at http://www.cs.waikato.ac.nz/ml/weka/