Please solve Problem $3$:

Decision Trees

Problem $2.[30$ points$]$ In this problem, you will investigate building a decision tree for a binary clas$-$

sification problem. The training data is given in Table $1$ with $16$ instances that will be used to learn a

decision tree for predicting whether a mushroom is edible or not based on its attributes $($Color$,$ Size, and

Shape$).$ Please note the label set is a binary set $\{$Yes$,$ No$\}.$

$1.$ Which attribute would the algorithm choose to use for the root of the tree. Show the details of your

calculations. Recall from lectures that if we let S denote the data set at current node, A denote

the feature with values v in V$,$ H denote the entropy function, and Sv denote the subset of S for

which the feature A has the value v$,$ the gain of a split along the feature A$,$ denoted InfoGain$($S$,$ A$)$

is computed as:

InfoGain$($S$,$ A$)=$ H$($S$)$ X

v in V

$|$Sv$|$

$|$S$|$

H$($Sv$)$

That is$,$ we are taking the difference of the entropy before the split, and subtracting off the entropies

of each new node after splitting, with an appropriate weight depending on the size of each node.

$2.$ Draw the full decision tree that would be learned for this data $($assume no pruning and you stop split$-$

ting a leaf node when all samples in the node belong to the same class, i$.$e$.,$ there is no information

gain in splitting the node$).$

$1$

Instance Color Size Shape Edible

D$1$ Yellow Small Round Yes

D$2$ Yellow Small Round No

D$3$ Green Small Irregular Yes

D$4$ Green Large Irregular No

D$5$ Yellow Large Round Yes

D$6$ Yellow Small Round Yes

D$7$ Yellow Small Round Yes

D$8$ Yellow Small Round Yes

D$9$ Green Small Round No

D$10$ Yellow Large Round No

D$11$ Yellow Large Round Yes

D$12$ Yellow Large Round No

D$13$ Yellow Large Round No

D$14$ Yellow Large Round No

D$15$ Yellow Small Irregular Yes

D$16$ Yellow Large Irregular Yes

Table $1$: Mushroom data with $16$ instances, three categorical features, and binary labels.

Problem $3.[10$ points$]$ Handling real valued $($numerical$)$ features is totally different from categorical

features in splitting nodes. This problem intends to discuss a simple way to decide good thresholds for

splitting based on numerical features. Specifically, when there is a numerical feature in data, an option

would be treating all numeric values of feature as discrete, i$.$e$.,$ proceeding exactly as we do with categorical

data. What problems may arise when we use a tree derived this way to classify an unseen example?