(a) Compute the Entropy for the overall collection of training examples.
Answer: Entropy(t)= -∑ p( j | t)log p( j | t) =-[1020log21020+1020log21020]

=1

(b) Compute the Entropy for the Movie ID attribute.
Answer: The movie id is unique to each movie. The Entropy for each Movie ID value is 0, hence the entropy for the Movie ID attribute is 0.
(c) Compute the Entropy for the Format attribute.
Answer: It has two types: DVD and Online. Entropy can be calculated in the following manner:
Entropy(t)= -∑ p( j | t)log p( j | t)
Entropy for DVD= -68log268+28log228=0.811
In similar way,
Entropy for Online= 0.915
Weighted average = 820x0.811+1220x0.915=0.8734
(d) Compute the Entropy for the Movie Category attribute using multiway split.
Answer: Entropy(t)= -∑ p( j | t)log p( j | t)
Entropy for Entertainment= -14log214+34log234=0.8112
Similarly,
Entropy for comedy= 0.5435
Entropy for Documentaries= 0.8112
Weighted Average=420x0.8112+820x0.5435+820x0.8112=0.70412
(e) Which of the three attributes has the lowest Entropy?
Answer: Movie ID has the lowest Entropy.
(f) Which of the three attributes will you use for splitting at the root node? Brief explain your choice.
Answer: We will use Movie Category to split the root nodes even though the entropy for Movie ID is lowest it is just an identification attribute and a decision tree using this attribute would not generalize at all. Movie ID value is unique for each record. The number of records for each partition are too small to make any predictions. Thus movie id is not a good choice.

2. Consider the decision tree shown in Figure 1, and the corresponding training and test sets in Tables 2 and 3 respectively.
(a) Estimate the generalization error rate of the tree using both the optimistic approach and the pessimistic approach. While computing the error with pessimistic approach, to account for model complexity, use a penalty value of 2 to each leaf node.
Answer:
Optimistic approach for calculating generalization error is provided using training error or resubstituting error. eT=0+0+0+0+0+015=0 Error(optimistic) =0

Pessimistic approach for calculating generalization error is given by:

eT=et+Ω(t)N e(t) is the overall training error of the decision tree.
N is the number of training records.
Ωtis the penalty term associated with each node t.

eT=0+6x215= 0.8

(b) Compute the error rate of the tree on the test set shown in Table 3.
Answer:

Error rate= Number of wrong predictionTotal number of wrong prediciton

Error rate=4+3+0+0+0+015=0.467

(c) Comment on the behavior of training and test set errors with respect to model complexity. Comment on the utility of incorporating model complexity in building a predictive model.
Answer:

Optimistic approach is where model complexity is ideal when it produces the lowest generalization error.
The training error and test error of the model are large if the model is very simple. As the model gets to complicated, the training error and test error decreases. When the model complexity becomes very large, there are very few training errors but the test errors rate begins to increase. This is known as model overfitting.
Model that contains smaller complexity has higher training error rate but a lower error rate compared to the more complex model. It seems that the smaller models are less likely to have overfitting problem. We can try to incorporate model complexity, when the model is too large, by evaluating the errors in the process through the pessimistic error rate. This also means that we can even add training data when the model is too complex. In this way, we can build simple and accurate tree.

3. [20 points: 10 for each part] Given the data sets shown in Figure 2, explain how the decision tree and k-nearest neighbor (k-NN) classiers would perform on these data sets.

Answer: a) The Choice for the data set will be the Decision Tree. Decision tree is a structure that includes a root node, branches, and leaf nodes. Each internal node denotes a test on an attribute, each branch denotes the outcome of a test, and each leaf node holds a class label. The topmost node in the tree is the root node. Decision tree is used to learn a model. It does it by mapping of input attributes to the class label as soon as the training data is available. It is easy to distinguish the attributes and determine the noisy attributes. Thus we can compute the impurity of a node then decide whether to split it or not. If the impurity is reduced after splitting then we do it or else we don’t split it. Hence the aim is to get higher gain after splitting.

K nearest neighbor is not a good option as the data given in the data set contains lot of noisy attributes. K nearest neighbor approach is by calculating the proximity to rest of the data points in the training set by using the proximity measure of the test sample. Hence the distance metric which computes distance between records to identify the K nearest neighbors will be adversely affected by the noisy attributes and give wrong results.

b) K nearest neighbor approach is by calculating the proximity to rest of the data points in the training set by using the proximity measure of the test sample. It uses distance metric which computes distance between records to identify the K nearest neighbors. Using this we can easily classify the attributes. Thus for data set 2 k nearest neighbor is the best choice.

Decision tree will not work well because a simple tree cannot classify the attributes accurately. If we make the model complex by extending the boundaries and capturing all attributes then the model will suffer from the overfitting problem.
4.
(a) Are the rules mutually exclusive?
Answer: No. The instance {Home Owner = Yes, Marital Status = Single} will trigger the first two rules.
(b) Is the rule set exhaustive?
Answer: No, the rule set doesn’t account for all possible combination of attributes values. For example, Marital Status = Divorced, Annual Income = High, Currently Employed = Yes is not covered by any of the rules.
(c) Is ordering needed for this set of rules?
Answer: Yes, because the rule set is not mutually exclusive, there will be some conflicting classes predicted by multiple classification rules. For example, Marital Status = Single, Annual Income = Medium, Currently Employed = Yes, this set of rules creating conflicting classes by predicting both Yes and No for the default Borrower. This problem can be resolved by setting an order in the rule set.
(d) Do you need a default class for the rule set?
Answer: Yes, since the rules are not exhaustive.

5. [15 points] Consider the problem of predicting whether a movie is popular given the following attributes: Format (DVD/Online), Movie Category (Comedy/Documentaries), Release Year, Number of world-class stars, Director, Language, Expense of Production and Length. If you had to choose between RIPPER and a k-nearest neighbor classier, which would you prefer and why? Briefly explain why the other one may not work so well?
Answer: RIPPER is favored for this issue. Given data sets with various properties with different estimation scales or mix of numerical and hard and fast qualities, the structure must affirm each trademark similarly as distinction so that the system can anticipate whether a film is standard or not. For this circumstance, as one of the rule based classifiers giving comparative execution to the decision tree, RIPPER is fitting for dealing with data sets for matched portrayal task. On the other hand, k-NN is not appropriate for this circumstance since k-NN predicts in perspective of a larger part vote of its neighbors measured by a detachment limit and utilize specific planning cases to make desires without keeping up a model got from data. As for Commotion dealing with, RIPPER works better since it uses an endorsement set to hinder model overfitting while k-NN is powerless against uproar credits in view of the secretly decided game plan decisions. All around, RIPPER is more fit the bill for the case.