Assignment $4$: Decision Tree Induction $(60$ points Max$)$

Instructions: This is an individual assignment, and the solutions and answers should be your own. This is NOT a group assignment. Your primary task is to build decision tree classifiers to predict the outcome. You can type your answers in Word and submit the document as Word or pdf$.$ Or$,$ you can write your answers by hand on blank sheets, scan them into a pdf document $($the pdf document should show your answers clearly without any smudging or shading issues$).$ Name your document as $"$DT$\_$username", where username is your Ninernet username. Upload the saved document through Canvas assignment.

Credit card companies consider various factors when they decide to approve or decline credit card applications. The following table has data from a sample of customers. The attribute in the last column is the target and columns $2-5$ are the four factors that affect credit card approval.

$\backslash$begin$\{$tabular$\}\{|$l$|$l$|$l$|$l$|$l$|$l$|\}$

$\backslash$hline Customer & Credit Score & $\backslash$begin$\{$tabular$\}\{$l$\}$

College $\backslash \backslash$

Education

$\backslash$end$\{$tabular$\}$ & Income & Home Owner & $\backslash$begin$\{$tabular$\}\{$l$\}$

Approved $\backslash \backslash$

or Not

$\backslash$end$\{$tabular$\}\backslash \backslash$

$\backslash$hline $1$ & Medium & Yes & Medium & No & Yes $\backslash \backslash$

$\backslash$hline $2$ & High & No & Medium & Yes & Yes $\backslash \backslash$

$\backslash$hline $3$ & Low & Yes & High & No & No $\backslash \backslash$

$\backslash$hline $4$ & High & Yes & Low & Yes & Yes $\backslash \backslash$

$\backslash$hline $5$ & High & Yes & High & Yes & Yes $\backslash \backslash$

$\backslash$hline $6$ & Low & No & Low & No & No $\backslash \backslash$

$\backslash$hline $7$ & Medium & No & Medium & No & No $\backslash \backslash$

$\backslash$hline $8$ & Medium & Yes & High & No & Yes $\backslash \backslash$

$\backslash$hline $9$ & Low & Yes & Medium & No & No $\backslash \backslash$

$\backslash$hline $10$ & High & No & High & Yes & Yes $\backslash \backslash$

$\backslash$hline $11$ & High & Yes & Medium & Yes & Yes $\backslash \backslash$

$\backslash$hline $12$ & Medium & No & Medium & Yes & Yes $\backslash \backslash$

$\backslash$hline $13$ & Medium & No & High & No & Yes $\backslash \backslash$

$\backslash$hline $14$ & Low & Yes & Medium & No & No $\backslash \backslash$

$\backslash$hline $15$ & High & Yes & High & Yes & No $\backslash \backslash$

$\backslash$hline

$\backslash$end$\{$tabular$\}$

Based on the training data set above, create two decision tree using the following two measures we learned in class $-$ gain ratio and gini index $-$ as attribute selection measure. You must show all your works, including the formulas, computations, and the decision trees, to get full credit. Do not submit an Excel file with your computations. If solving by pen $\backslash$& paper, scan your solutions clearly and submit them. Unclear or blurry solutions will not be graded.

Overfitting is allowed for this problem. Hence, keep splitting unless the leaf node becomes pure or gain ratio $($or reduction in Gini index$)$ becomes negative. Also, only binary splits are allowed, i$.$e$.,$ if there are more than two unique values for an attribute, use different combinations for each side of the binary split.

$---$ End of Assignment $---$