The ID3 algorithm constructs a decision tree based on an estimate of the "best" attribute for the current set of data at that level in the tree.
(a) Outline the ID3 algorithm for constructing a decision tree. Assume that the initial set of examples is represented as the set S and that you have a supplied function that determines the next "best" attribute for splitting.
(b) The change in entropy is one approach to selecting the "best" attribute when deciding how to split the current node for a decision tree. Define a measure of entropy for the classification problem shown in part (c), and explain how it is used to select the "best" attribute for splitting.
(c) The ID3 algorithm is now applied to the following table of data, where the examples el ..e8 are based on three attributes (atl ..at3) and classified as either positive (+) or negative (-) examples.
|
Example
|
at1
|
at2
|
at3
|
Classification
|
|
el
|
a
|
x
|
n
|
+
|
|
e2
|
b
|
x
|
n
|
+
|
|
e3
|
b
|
y
|
n
|
-
|
|
e4
|
a
|
y
|
m
|
-
|
|
e5
|
a
|
y
|
n
|
+
|
|
e6
|
a
|
x
|
p
|
+
|
|
e7
|
c
|
z
|
p
|
-
|
|
e8
|
c
|
z
|
n
|
+
|
Assume that you are starting the construction of the decision tree, and that the "best" attribute for the first split in the tree has been determined to be at2.
Draw the decision tree after this initial split, and include at each node of the tree the new subset of examples that need to be split, or if the node is homogeneous then include the final classification for this node.