Decision tree construction.

(a) Draw a decision tree that would perfectly classify the dataset shown below. The dataset has 2 predictor attributes, denoted as x1 and x2, which were partitioned into 3 classes (denoted as A, B, and C). You can draw the tree using any software you want (e.g., powerpoint), save it as a jpeg/bmp/png image, and attach it to the notebook.

Solution: Attach your decision tree figure here.

(b) Consider the following training data for predicting whether there will be traffic congestion on a given segment of an interstate highway. Each data point corresponds to a particular time of day and is classified either as positive (if the highway segment was congested) or negative (if it was not congested) class. Suppose you are interested in building a decision tree classifier on the training data. Compute the overall Gini index for each predictor attribute (construction and weather condition) and select the best attribute to partition the training data.

Solution:

X2 1.0 0.8A 0.6 0.4 0.2 A B X1 0.2 0.4 0.6 0.8 1.0 # Positive examples # Negative examples 10 Construction Weather Yes Yes No Good Bad Good Bad 10 25 20 20