Decision Tree$]$ You will build a decision tree to determine whether or not a child goes out to

play.

Day Weather Temperature Humanity Wind Play

$1$ Sunny Hot High Weak No

$2$ Cloudy Hot High Weak Yes

$3$ Sunny Mild Normal Strong Yes

$4$ Cloudy Mild High Strong Yes

$5$ Rainy Mild High Strong No

$6$ Rainy Cool Normal Strong No

$7$ Rainy Mild High Weak Yes

$8$ Sunny Hot High Strong No

$9$ Cloudy Hot Normal Weak Yes

$10$ Rainy Mild High Strong No

$1\mathrm{.}1$ Calculate the information gain for each feature and select the feature with the highest infor$-$

mation gain to serve as the root of the decision tree. Draw a root and split the ten training data

points into two groups based on the value of the selected root feature.

k$=$ arg max

k

I$($Xk; Y $)=$ H$($Y $)$ H$($Y $|$Xk$)$

$1\mathrm{.}2$ Repeat the two procedures: $(1)$ selecting a feature and $(2)$ splitting the data points until the

leaf nodes of the tree achieve complete purity.

$1\mathrm{.}3[$Extra Points: $10$ points$]$ Try pruning your tree. You need to find a subtree $($T $)$ minimizing

the criterion C$($T $)$ below. Based on the criterion computation, do you think we need to prune the

tree found in $4\mathrm{.}2?$

C$($T $)=$

T $$

X

$=1$

Q$($ $)+$ $|$num of leaves in T $|$

Q$($ $)=$ entropy of a leaf in T $($measure of impurity$)$

$1$