Fuzzy Decision Trees

Introduction

The inductive learning methodology known as decision trees, concerns the ability to classify objects based on their attributes values, using a tree like structure from which decision rules can be accrued. In this article, a description of decision trees is given, with the main emphasis on their operation in a fuzzy environment.

A first reference to decision trees is made in Hunt et al. (1966), who proposed the Concept learning system to construct a decision tree that attempts to minimize the score of classifying chess endgames. The example problem concerning chess offers early evidence supporting the view that decision trees are closely associated with artificial intelligence (AI). It is over ten years later that Quinlan (1979) developed the early work on decision trees, to introduced the Interactive Dichotomizer 3 (ID3). The important feature with their development was the use of an entropy measure to aid the decision tree construction process (using again the chess game as the considered problem).

It is ID3, and techniques like it, that defines the hierarchical structure commonly associated with decision trees, see for example the recent theoretical and application studies of Pal and Chakraborty (2001), Bhatt and Gopal (2005) and Armand et al. (2007). Moreover, starting from an identified root node, paths are constructed down to leaf nodes, where the attributes associated with the intermediate nodes are identified through the use of an entropy measure to preferentially gauge the classification certainty down that path. Each path down to a leaf node forms an ‘if .. then ..’ decision rule used to classify the objects.

The introduction of fuzzy set theory in Zadeh (1965), offered a general methodology that allows notions of vagueness and imprecision to be considered. Moreover, Zadeh’s work allowed the possibility for previously defined techniques to be considered with a fuzzy environment. It was over ten years later that the area of decision trees benefited from this fuzzy environment opportunity (see Chang and Pavlidis, 1977). Since then there has been a steady stream of research studies that have developed or applied fuzzy decision trees (FDTs) (see recently for example Li et al., 2006 and Wang et al., 2007).

The expectations that come with the utilisation of FDTs are succinctly stated by Li et al. (2006, p. 655);

Chiang and Hsu (2002) highlight that decision trees has been successfully applied to problems in artificial intelligence, pattern recognition and statistics. They go onto outline a positive development the FDTs offer, namely that it is better placed to have an estimate of the degree that an object is associated with each class, often desirable in areas like medical diagnosis (see Quinlan (1987) for the alternative view with respect to crisp decision trees).

The remains of this article look in more details at FDTs, including a tutorial example showing the rudiments of how an FDT can be constructed.

Background

The background section of this article concentrates on a brief description of fuzzy set theory pertinent to FDTs, followed by a presentation of one FDT technique.

In fuzzy set theory (Zadeh, 1965), the grade of membership of a value x to a set S is defined through a membership function μ_S(x) that can take a value in the range [0, 1]. The accompanying numerical attribute domain can be described by a finite series of MFs that each offers a grade of membership to describe x, which collectively form its concomitant fuzzy number. In this article, MFs are used to formulate linguistic variables for the considered attributes. These linguistic variables are made up of sets of linguistic terms which are defined by the MFs (see later).

Surrounding the notion of MFs is the issue of their structure (Dombi and Gera, 2005). Here, piecewise linear MFs are used to define the linguistic terms presented, see Figure 1.