2. Decision Tree a. One typical decision tree algorithm ID3 is used for binary classification. There is another decision tree algorithm named CART. The difference between CART and ID3 is CART

does binary splits at every node, whereas ID3 exhausts one attribute once it is used. Example of ID3: High No Example of CART: High No Sunny Humidity Normal Yes Yes Humidity High Normal Outlook Yes Overcast Outlook Sunny Yes No Yes No Rain Strong No Wind = Strong Wind No Yes Weak Yes The difference between these two algorithms is obvious by looking at the above tree structure. They use similar ways to calculate how to split a node. At each node of CART,/nthe algorithm will iterate all the features and feature values and evaluate each split according to a cost function to select the feature and feature value with the largest cost reduction. Pright Reduction (Feature;, Value;) = cost (D) - De cost (Dieft) + |DI cost (Dright)]) Consider a data set comprising 400 data points from class C1 and 400 data points from class C2. Suppose that a decision stump model A splits these into two leaves at the root node; one containing (300,100) and the other containing (100,300) where (n,m) denotes n points are from class C1 and m points are from class C2. Similarly a second decision stump model B splits the examples as (200,400) and (200,0). Calculate the reduction in cost using misclassification rate for models A and B. Which is the preferred split (model A or model B) according to the cost calculations? Misclassification rate: Σ Σ 1(y + 9) (x,y)ED ŷ majority label in D cost (D) Hint: Gini Index: |D| b. If using the entropy to measure the cost, what is the answer to the question 2.a ? Hint: Entropy: Let p = fraction of position examples in D cost (D) = -p log₂ p-(1-p)log2 (1-p) c. If using the Gini index to measure the cost, what is the answer to the question 2.a cost (D) = 2p (1-p) d. Go to decisiontree folder and execute the hw_4_dt.ipynb, fill the code cells and answer the questions in notebook.