Information Technology Reference
In-Depth Information
I X a
(
,
)
=
H X
(
)
−
H X
(
/
a
)
(7.30)
The less the value of expression
7.29
is , the larger the value of expression
7.30
would be. This means the more information provided by test attribute
,
the less uncertainty degree for classification after selecting a. Quinlan's ID3
algorithm selects the attribute which makes
a
I
X
a
maximum to be test attribute,
i.e. selects attribute a which make expression
7.29
minimum.
7.7.3
ID3 algorithm
Except for using information measure as standard, ID3 algorithm introduces
increment learning techniques. In CLS algorithm, since algorithm needs to know
all training examples at beginning, when training example set is too large,
examples cannot be immediately put into memory and have some problems.
Quinlan introduces windows for increment learning to solve the problem. The
following is ID3 algorithm(Quinlan, 1983).
Algorithm 7.5
ID3 Algorithm
1. Select random subset X1 with scale of W from the whole training example set X (W is
window scale, and subset is referred to as window);
2. With the standard that makes the value of expression
7.29
minimum, select each test
attribute to form current decision tree;
3. Scan all training examples sequentially, and find current exception of current decision
tree, if there is not any exception, the algorithm ends.
4. Combine some examples of current window and some exceptions in step 3 to form
new window, go to step 2.
In order to construct new window in step 4, Quinlan tried two different
strategies: one is to retain all examples of window and add appointed exceptions
get from step 3. This strategy will enlarge the window more large. The other
strategy corresponds to retain a training example for each node of current
decision tree, other examples are deleted from the window and replaced by
exceptions. The experiments showed that both approaches work well, but if the
concept is so complicated that windows with fixed scale W cannot be found, the
second approach may be not converged.
7.7.4
Application example of ID3 algorithm
Table 7.2 gives a data set may have noise. There are four attributes: Outlook,
Temperature, Humidity and Windy. It is divided into two classes:
P
and
N,
