Information Technology Reference
In-Depth Information
C
i
. Discriminative rules found may overlap in unobserved region of example
space.
In order to find classification rule set which does not overlap, AQ11 takes
examples of class
C
i
as positive examples, and negative examples include all
examples of other classes
) and all examples in positive example region
of various unhandled classes
C
k
(1
≤
k
≤
i
). Then, class
C
2
only covers parts
that class
C
j
(
j
≠
i
C
1
does not cover. Parts that class
C
3
covers are parts that neither class
2
nor
C
1
covers.
Discriminative rules gotten from AQ11 correspond to the most general
description set meet training examples. That is, set
C
of various classes, such as
G
1
,
G
2
, etc. Sometimes the most specific description sets meet training examples
which need to be used. That is, set
G
2
, etc.
Michalski et al. employed AQ11 program in learning diagnosed rules of soy
sick. In program, 630 descriptions of plants with soy sick have been provided.
Each description has 35 feature vectors. At the same time, expert diagnose
conclusions have been pooled. Program of selecting examples selects 290 sample
plants as training examples. Selective principle makes distance between
examples as larger as possible. Other 340 plants take as test set for check the
acquired rules.
S
of various classes, such as
S
1
,
S
7.6 Constructing Decision Trees
A particularly efficient method for exploring the space of concept descriptions
is to generate a decision tree. Hunt,Marin and Stone have developed Concept
Learning System(CLS) (Hunt, Marin and Stone, 1966). CLS uses a lookahead
strategy similar to minimax. At each stage, CLS explores the space of possible
decision trees to a fixed depth, chooses an action to minimize cost in this limited
space, then moves one level down in the tree. It intends to solve single concept
learning tasks and uses the learned concepts to classify new instances.
The main idea of CLS algorithm is as following. First, start from an empty
decision tree, improve original decision tree by adding new discriminative node,
until decision tree could correctly classify the training examples.
Algorithm 7.4
CLS Algorithm
1. Let initial status of decision tree
T
only includes a root (
X, Q
), where
X
is a set
of all training examples,
Q
is a set of all test attributes;
2. If all leaf nodes (
´) , of T have following status: when all training
examples of the first vector
X´, Q
X
´ belong to same class, or the second vector
Q
´ is
