=========================preview======================
(comp328)[2009](s)midterm~PPSpider^_10198.pdf
Back to COMP328 Login to download
======================================================
THE HONG KONG UNIVERSITY OF SCIENCE & TECHNOLOGY
COMP 328: Machine Learning
Spring 2009
Midterm Examination
Room 2302, 19:00pm C 21:00pm, Tuesday, 24 March 2009

Name: Student No.:
Department: Year of Study:
This is a closed book exam although you might bring the midterm review materials prepared by the instructor. You should put everything o. your desk except for stationeries and your student ID.
There are 8 questions. You need to answer all questions in 120 minutes. You should use the back of the pages for rough work and, if necessary, for your .nal answers. There are 2 blank pages at the end should you need more space. Scrap papers will be handed out separately.
Question Grade
1
2
3
4
5
6
7
8
Total

1. (15 points) Consider building a decision tree to separate the two classes of geometric shapes in the following .gure:

The attributes to use are: shape (square or triangle), size (large or small), and line.thickness (.ne or thick). Draw the tree that ID3 builds. Show the process of tree construction. For each step, write down the information gain (in expression) for each attribute examined. You should be able to decide which attribute to pick without exactly evaluating information gain expressions. Break ties arbitrarily.
Answer:
The .gure gives us the following information:
Instances shape size line-thickness class
1 square large thick 1
2 square small thick 2
3 square small thick 2
4 square small .ne 2
5 square small .ne 2
6 triangle large .ne 2
7 triangle small .ne 1
8 triangle small .ne 1
9 triangle small thick 1

Let S denotes a set of instances, Sv denotes a set of instances with attributes value equals to v.
Let |S| denotes the number of instances,|Sv| denotes number of instances with attributes value equals
to v.

Entropy(S)= .p(class = 1) log p(class = 1) . p(class = 2) log p(class = 2) = 0.99
We can compute the information gain as follows:
|Ssquare||Striangle|
Gain(S, shape)= Entropy(S) . Entropy(Ssquare) . Entropy(Striangle)=0.23
|S||S||Slarge|
Gain(S, size)= Entropy(S) . |Ssmall| Entropy(Ssmall) . Entropy(Slarge)=0.002
|S||S||Sfine||Sthick|
Gain(S, line . thickness)= Entropy(S) . Entropy(Sfine) . Entropy(Sthick)=0.007
|S||S|
So, we can choose shape as the root attribute.
Then, for each branch, we compute the information gain as follows:
Gain(Ssquare, size) |Ssquare,small||Ssquare,large|
=Entropy(Ssquare) . |Ssquare| Entropy(Ssquare,small) . |Ssquare| Entropy(Ssquare,large)=0.72
Similarly,
Gain(Ssquare, line . thickness)=0.17,
Gain(Striangle, size)=0.72

Gain(Striangle, line . thickness)=0.17
So, for both branches, we choose attribute size. And all the instances are classi.ed correctly.
The decision tree is as follow:
shape = square | size = large: class 1 | size = small: class 2 shape = triangle | size = large: class 2 | size = small: class 1
2. (15 points) Consider the f