$2.$ Decision Trees $(15$ marks$)$

$($a$)$ Explain how decision trees can be used to address regression and classification problems. $[3$ marks$]$

$($b$)$ Decision trees are trained by maximising the purity of the corresponding partition of the training data. Does the purity of a set depend on the attributes,

on the labels, or on both? Briefly describe how you evaluate the purity of the

partition associated with a given tree. $[3$ marks$]$

$($c$)$ Consider the following data set

D $=\{($xn$,$ yn$)$ in R

$2\backslash$times $\{$one$,$ two, three, four, five$\}\}4$

n$=1$

$=\{($x$1,$ y$1),($x$2,$ y$2),($x$3,$ y$3),($x$4,$ y$4)\}$

Choose y$1,...$ y$4$ in $\{$one$,$ two, three, four, five$\}$ to maximize the purity of D$.$

$[2$ marks$]$

$($d$)$ Suppose you have trained a classification tree to predict Y $=\{$yes$,$ no$\}.$

Explain how you can use a Bayes classifier and the estimated conditional

probability, Prob$($Y $|$X$),$ to predict the label of a test object.

Hint: In this case, a Bayes classifier based on Prob$($Y $|$X$)$ is

y$=$ arg max

y in $\{$yes$,$no$\}$

Prob$($Y $=$ y$|$X$)$

$[3$ marks$]$

$($e$)$ A standard approach to building a decision tree is to perform iterative binary

splits of the input space. How do you find the optimal split at each iteration?

Give the formula of the information gain and explain how it depends on a

real$-$valued threshold.

Hint: The information gain is a function of the size and the entropy of

$$ a bin before the split, B$,$ and

$$ the two bins, B$1$ and B$2,$ you obtain after splitting B$.$

Let $|$D$|$ be the cardinality of D$.$ Then the entropy of D is

H$($D$)=$

X

y in Y

py log py$,$ py $=|$D$|1$ X

$($x$0$

$,$y$0)$ in D

$1($y

$0=$ y$)$

$[4$ marks$]$