Q$6$ Consider the dataset in the Fig. $1.$ We will study tree$-$based methods.

Figure $2$: Decision Tree

Is x$1<mn>5</mn>$x$\_1<mtext></mtext><mn>5</mn>$x

Yes $($x$1<mn>5</mn>$x$\_1<mtext></mtext><mn>5</mn>$x$1<mn>5</mn><mi>)</mi>$:

Outcome: $\backslash$times$($cross mark$)$

No $($x$15$x$\_1\backslash$geq $5$x$15)$:

Is x$1<mn>7</mn>$x$\_1<mtext></mtext><mn>7</mn>$x

Yes $($x$1<mn>7</mn>$x$\_1<mtext></mtext><mn>7</mn>$x$1<mn>7</mn><mi>)</mi>$:

Is x$2<mn>4</mn><mn>.</mn><mn>5</mn>$x$\_2<mtext></mtext><mn>4</mn><mn>.</mn><mn>5</mn>$x

Yes $($x$2<mn>4</mn><mn>.</mn><mn>5</mn>$x$\_2<mtext></mtext><mn>4</mn><mn>.</mn><mn>5</mn>$x$2<mn>4</mn><mn>.</mn><mn>5</mn><mi>)</mi>$:

Is x$2<mn>1</mn><mn>.</mn><mn>5</mn>$x$\_2<mtext></mtext><mn>1</mn><mn>.</mn><mn>5</mn>$x

Yes $($x$2<mn>1</mn><mn>.</mn><mn>5</mn>$x$\_2<mtext></mtext><mn>1</mn><mn>.</mn><mn>5</mn>$x$2<mn>1</mn><mn>.</mn><mn>5</mn><mi>)</mi>$: Outcome: $\backslash$circ$($circle mark$)$ No $($x$21\mathrm{.}5$x$\_2\backslash$geq $1\mathrm{.}5$x$21\mathrm{.}5)$: Outcome: $\backslash$times$($cross mark$)$

No $($x$24\mathrm{.}5$x$\_2\backslash$geq $4\mathrm{.}5$x$24\mathrm{.}5)$: Outcome: $\backslash$times$($cross mark$)$

No $($x$17$x$\_1\backslash$geq $7$x$17)$: Outcome: $\backslash$times$($cross mark$)$

$($a$)$ Construct a classification tree using recursive binary splitting and Gini index as impurity measure. Stop when all leaves contains a single class. Write necessary calculation procedure and you can present the tree similar to the one in Fig. $2.$

$($b$)$ Draw a graph showing the partitioning induced by the decision boundaries of the classification tree in Fig. $2.$ Note: DO NOT draw the partitioning for the tree you got in Q$6($a$).$

$($c$)$ Besides tree$-$based methods, what other classification methods you will use to achieve zero training error $($with some $($hyper$-)$parameter setting$)$ for the above dataset? List three other choices and briefly explain your answers.