Please

Problem 1: Decision Tree Classification and IF-THEN Rules [60]

1. Decision Trees [25]

You are trying to build a classifier to figure out which restaurant is best suited for a dinner with your friends. You gathered data from about 11 different restaurants and in particular about the kind of restaurant (fast food, ethnic or casual dining), their prices (low, average or high), their locations (Bethpage, Hicksville or Plainview), whether they can comply with dietary restrictions (none, vegetarian or gluten free) and whether you enjoyed them or not. The data is reported in the following table:

Restaurant ID	Type	Price	Neighborhood	Restrictions	Enjoyed?
R1	Fast Food	$	Bethpage	Vegetarian	no
R2	Ethnic	$$	Plainview	Gluten Free	no
R3	Casual	$$	Plainview	None	no
R4	Casual	$$$	Hicksville	Vegetarian	no
R5	Casual	$	Bethpage	Vegetarian	yes
R6	Fast Food	$$	Plainview	None	yes
R7	Ethnic	$	Plainview	None	yes
R8	Casual	$	Hicksville	Gluten Free	no
R9	Fast Food	$$$	Bethpage	None	no
R10	Ethnic	$$	Hicksville	Vegetarian	yes
R11	Casual	$$	Hicksville	Gluten Free	yes

Using this data build a decision tree to decide whether you would enjoy a particular restaurant or not, showing at each level how you decided which attribute to expand next. You can either use Gain ratio or Gini index for attribute selection to build the tree. Show all the calculations of gains/Gini index for every attribute at every node. Just drawing the tree will not be sufficient. In case of tie, prioritize the attributes in left to right order shown in the table above.

2. What is the training set error E_train(h) of your decision tree (i.e. the fraction of points in the training set that it misclassified)? [5]

3. You are now given data from five more restaurants: [10]

Restaurant ID	Type	Price	Neighborhood	Restrictions
R12	Fast Food	$	Plainview	None
R13	Ethnic	$$	Hicksville	None
R14	Ethnic	$	Bethpage	Gluten Free
R15	Casual	$	Hicksville	Vegetarian
R16	Ethnic	$	Plainview	Gluten Free

To which one would you go? Classify this test data using the decision tree created in (a).