Design Issues of Decision Tree Induction

Design Issues of Decision Tree Induction

A learning algorithm for inducing decision trees must address the following two issues.

a) How should the training records be split? Each recursive step of the tree-growingprocessmustselectan attributetestconditionto dividetherecordsintosmallersubsets.To implementthisstep,the algorithmmust providea methodfor specifyingthe testcondition fordifferentattribute types as wellas an objectivemeasure forevaluating the goodness of each test condition.

b) How should the splitting procedure stop?

A stopping condition is needed to terminate thetree-growing process.A possible strategy is to continue expanding a node until either all therecords belong to the same class or all the records have identical attribute values.Althoughboth conditions are sufficientto stopanydecisiontreeinductionalgorithm, othercriteriacanbe imposedto allowthe tree-growingprocedureto terminate earlier.

5.3.3 Methods for Expressing Attribute Test Conditions

Decisiontreeinductionalgorithmsmustprovide amethodforexpressingan attributetestconditionanditscorresponding outcomes for different attribute types. BinaryAttributes generates two potential outcomes, as shown in Figure 3.8.The test condition for a binary attribute

Cold blooded Warm blooded

Figure 5.7Test conditions for nominal attributes.

Nominal Attributes:

Since a nominal attribute can have many values, its test condition can be expressed intwoways, as shownin Figure5.7.For amultiwaysplit(Figure5.7(a)),thenumber ofoutcomesdependson the number ofdistinctvalues for thecorrespondingattribute.Forexample, if an attribute such as marital status has three distinct values—single, married, or divorcedits test condition will produce a three-way split.On the other hand, some decision tree algorithms,such as CART, produce only binary splits by considering all 2k−1− 1 waysof creating a binarypartition of k attribute values. Figure 5.8(b) illustrates three different ways of grouping the attributevalues for marital status into two subsets.

Ordinal Attributes:

Ordinal attributes can also produce binary or multiway splits.Ordinal attribute values canbe grouped aslong asthegroupingdoesnotviolatetheorderproperty oftheattributevalues.Figure 5.9 illustrates various ways of splitting training records based on the Shirt Size attribute.Thegroupingsshownin Figures5.9(a)and(b)preservetheorderamong the attributevalues,whereasthe groupingshown inFigure 5.9(c)violates this property because it combinesthe attribute valuesSmall andLarge into the same partition while Medium and ExtraLarge are combined into another partition.

Figure 5.9Different ways of grouping ordinal attribute values.