1. General Learning
Consider the following modification to the restaurant example described in class, which includes missing and partially specified attributes:
⇒ The outcomes for X1 and X7 are reversed.
⇒ X3 has the missing attribute value for "Pat".
⇒ X5 has the missing attribute value for "Hun".
⇒ X10 has the attribute for “TYPE” which could be either ITALIAN or FRENCH.
Define an algorithm for dealing with missing attributes and partially specified attributes,which includes the modified calculation for information gain use to make splitting decisions.
Generate a decision tree for this example using your new algorithm.
Answer
There are a lot of ways of answering this question. One algorithm is as follows:
For a training instance with multivalued attributes, I will duplicate that instance by the number of values of that attribute. But each duplicated instance will be weighted down by the number of times I have seen each value in other training examples.
For example, in the restaurant example, X10 will now become X10’ and X10’’. X10’ will have a value of French, with a weight of 2/3 (note this is 2/3 because there are only 3 examples with either French or Italian of which 2 are French). X10’’ will have a weight of 1/3 when learning in my decision tree.
For a missing attribute, I will treat it like a multivalued attribute, using all possible values of the missing attribute. For example, X3 will become X3’, X3’’ and X3’’’. X3’ will have the value None with a weight of 2/11. X3’’ will have the value Some for Pat, with a weight of 3/11. X3’’’ will have the value Full for Pat, with a weight of 6/11.
Note, that these weights are independent of each other. So, if X10 also had the value of Pat missing, I would have to generate 6 new training instances. X10’ would be French for Type and None for Pat, with a weight of 2/3 *
2/11.
We can now use this modification of the algorithm given in class to compute our decision tree by calculating the information gain. I will show the formulas for some of the important ones here
FRI = 5/12 * I(2/5,3/5) + 7/12 * I(4/7,3/7)
HUN = (7 + 7/11)/12 * I[4/(7+7/11),(3 + 7/11)/(7+7/11)] + (4 + 4/11)/12 * I[2/(4+4/11),(2+4/11)/(4+4/11)]
TYPE = 4/12 * I(2/4,2/4) + 4/12 * I(3/4,1/4) + (2+2/3)/12 * I(1,0) + (1+1/3)/12 * I[1/(1+1/3),1/3/(1+1/3)]
And so on. The final decision tree will look something like this