Information Technology Reference
In-Depth Information
void, cease to execute the learning algorithm, learning result is
T
;
3. Otherwise, select a leaf node (
X´, Q
´) without the status mentioned in step 2;
4. As for
Q
´, we select test attribute according to certain rules. Assume that
X
'
was divided into m non-intersect subsets
X
i
´, 1
≤
i
≤
m
, by different values of
b
.
sticking m branches from (
X´, Q
´), each branch represents different value of
b
,
then formulate m new leaf nodes (
X
i
´
Q
´-{
b
}), 1
≤
i
≤
m
;
5. Go to step2.
It can be seen from description of CLS algorithm that the construct procedure is
procedure of hypothesis specialization, so CLS algorithm can be seen as a
learning algorithm with only one operator, which can be represented as: through
adding a new discriminative condition (discriminative node), specialize current
hypothesis. CLS algorithm recursively calls the operator, acting at every leaf
node, and constructing a decision tree.
In the steps 2 of algorithm 7.4, if there does not exist contradiction among
training set, which means there does not exist two examples without same
attribute belong to same class, then if the second condition is met (i.e.
Q
´is
empty), the first condition will be met too (i.e. all training examples of
X
'
belong
to same class). This means the cease condition should be chosen from one of
them. However, as for existing contradiction training set, above-mentioned
statement must not hold.
In the step 4, the algorithm should meet
>1 or classification is pointless.
However, because there are contradiction training examples, it is difficult to
assure
m
>1.
In the step4, the algorithm does not give selective standard of test attributes,
so CLS has been improved through many ways.
m
7.7 ID3 Learning Algorithm
Algorithm 7.4 did not give how to select test attribute
, Hunt had proposed
several selective standard. In various decision tree learning algorithms, the most
influential is ID3 algorithm proposed by Quinlan in 1979 (Quinlan, 1979). ID3
algorithm takes the decline velocity of information entropy as selective standard
of test attribute. Decline of information entropy is decline of information
uncertainty.
b
