Unit IV Notes
Unit IV Notes
Unit IV Notes
UNIT-IV
DECISION TREE LEARNING
Decision tree learning is a method for approximating discrete-valued target functions, in which
the learned function is represented by a decision tree.
Decision trees classify instances by sorting them down the tree from the root to some
leaf node, which provides the classification of the instance.
Each node in the tree specifies a test of some attribute of the instance, and each branch
descending from that node corresponds to one of the possible values for this attribute.
An instance is classified by starting at the root node of the tree, testing the attribute
specified by this node, then moving down the tree branch corresponding to the value of
the attribute in the given example. This process is then repeated for the subtree rooted
at the new node.
FIGURE: A decision tree for the concept PlayTennis. An example is classified by sorting it
through the tree to the appropriate leaf node, then returning the classification associated with
this leaf
For example, the decision tree shown in above figure corresponds to the expression
(Outlook = Sunny ∧ Humidity = Normal)
∨ (Outlook = Overcast)
∨ (Outlook = Rain ∧ Wind = Weak)
Decision tree learning is generally best suited to problems with the following characteristics:
2. The target function has discrete output values – The decision tree assigns a Boolean
classification (e.g., yes or no) to each example. Decision tree methods easily extend to
learning functions with more than two possible output values.
4. The training data may contain errors – Decision tree learning methods are robust to
errors, both errors in classifications of the training examples and errors in the attribute
values that describe these examples.
5. The training data may contain missing attribute values – Decision tree methods can
be used even when some training examples have unknown values
The basic algorithm is ID3 which learns decision trees by constructing them top-down
Examples are the training examples. Target_attribute is the attribute whose value is to be
predicted by the tree. Attributes is a list of other attributes that may be tested by the
learned decision tree. Returns a decision tree that correctly classifies the given Examples.
Otherwise Begin
A ← the attribute from Attributes that best* classifies Examples
The decision attribute for Root ← A
For each possible value, vi, of A,
Add a new tree branch below Root, corresponding to the test A = vi
Let Examples vi, be the subset of Examples that have value vi for A
If Examples vi , is empty
Then below this new branch add a leaf node with label = most common
value of Target_attribute in Examples
Else below this new branch add the subtree
ID3(Examples vi, Targe_tattribute, Attributes – {A}))
End
Return Root
TABLE: Summary of the ID3 algorithm specialized to learning Boolean-valued functions. ID3
is a greedy algorithm that grows the tree top-down, at each node selecting the attribute that best
classifies the local training examples. This process continues until the tree perfectly classifies
the training examples, or until all attributes have been used
The central choice in the ID3 algorithm is selecting which attribute to test at each node
in the tree.
A statistical property called information gain that measures how well a given attribute
separates the training examples according to their target classification.
ID3 uses information gain measure to select among the candidate attributes at each
step while growing the tree.
Given a collection S, containing positive and negative examples of some target concept, the
entropy of S relative to this Boolean classification is
Where,
p+ is the proportion of positive examples in S
p- is the proportion of negative examples in S.
Example:
Suppose S is a collection of 14 examples of some boolean concept, including 9 positive and 5
negative examples. Then the entropy of S relative to this boolean classification is
An Illustrative Example
To illustrate the operation of ID3, consider the learning task represented by the training
examples of below table.
Here the target attribute PlayTennis, which can have values yes or no for different days.
Consider the first step through the algorithm, in which the topmost node of the decision
tree is created.
ID3 determines the information gain for each candidate attribute (i.e., Outlook,
Temperature, Humidity, and Wind), then selects the one with highest information gain.
According to the information gain measure, the Outlook attribute provides the best
prediction of the target attribute, PlayTennis, over the training examples. Therefore,
Outlook is selected as the decision attribute for the root node, and branches are created
below the root for each of its possible values i.e., Sunny, Overcast, and Rain.
ID3 can be characterized as searching a space of hypotheses for one that fits the training
examples.
The hypothesis space searched by ID3 is the set of possible decision trees.
ID3 performs a simple-to complex, hill-climbing search through this hypothesis space,
beginning with the empty tree, then considering progressively more elaborate
hypotheses in search of a decision tree that correctly classifies the training data
Figure: Hypothesis space search by ID3. ID3 searches through the space of possible decision
trees from simplest to increasingly complex, guided by the information gain heuristic.
By viewing ID3 in terms of its search space and search strategy, there are some insight into its
capabilities and limitations
1. ID3's hypothesis space of all decision trees is a complete space of finite discrete-valued
functions, relative to the available attributes. Because every finite discrete-valued
function can be represented by some decision tree
ID3 avoids one of the major risks of methods that search incomplete hypothesis spaces:
that the hypothesis space might not contain the target function.
2. ID3 maintains only a single current hypothesis as it searches through the space of
decision trees.
For example, with the earlier version space candidate elimination method, which
maintains the set of all hypotheses consistent with the available training examples.
By determining only a single hypothesis, ID3 loses the capabilities that follow from
explicitly representing all consistent hypotheses.
For example, it does not have the ability to determine how many alternative decision
trees are consistent with the available training data, or to pose new instance queries that
optimally resolve among these competing hypotheses
3. ID3 in its pure form performs no backtracking in its search. Once it selects an attribute
to test at a particular level in the tree, it never backtracks to reconsider this choice.
In the case of ID3, a locally optimal solution corresponds to the decision tree it selects
along the single search path it explores. However, this locally optimal solution may be
less desirable than trees that would have been encountered along a different branch of
the search.
4. ID3 uses all training examples at each step in the search to make statistically based
decisions regarding how to refine its current hypothesis.
One advantage of using statistical properties of all the examples is that the resulting
search is much less sensitive to errors in individual training examples.
ID3 can be easily extended to handle noisy training data by modifying its termination
criterion to accept hypotheses that imperfectly fit the training data.
Inductive bias is the set of assumptions that, together with the training data, deductively justify
the classifications assigned by the learner to future instances
Given a collection of training examples, there are typically many decision trees consistent with
these examples. Which of these decision trees does ID3 choose?
Approximate inductive bias of ID3: Shorter trees are preferred over larger trees
Consider an algorithm that begins with the empty tree and searches breadth first through
progressively more complex trees.
First considering all trees of depth 1, then all trees of depth 2, etc.
Once it finds a decision tree consistent with the training data, it returns the smallest
consistent tree at that search depth (e.g., the tree with the fewest nodes).
Let us call this breadth-first search algorithm BFS-ID3.
BFS-ID3 finds a shortest decision tree and thus exhibits the bias "shorter trees are
preferred over longer trees.
A closer approximation to the inductive bias of ID3: Shorter trees are preferred over longer
trees. Trees that place high information gain attributes close to the root are preferred over
those that do not.
Difference between the types of inductive bias exhibited by ID3 and by the CANDIDATE-
ELIMINATION Algorithm.
ID3:
ID3 searches a complete hypothesis space
It searches incompletely through this space, from simple to complex hypotheses, until
its termination condition is met
Its inductive bias is solely a consequence of the ordering of hypotheses by its search
strategy. Its hypothesis space introduces no additional bias
CANDIDATE-ELIMINATION Algorithm:
The version space CANDIDATE-ELIMINATION Algorithm searches an incomplete
hypothesis space
It searches this space completely, finding every hypothesis consistent with the training
data.
Its inductive bias is solely a consequence of the expressive power of its hypothesis
representation. Its search strategy introduces no additional bias
Preference bias – The inductive bias of ID3 is a preference for certain hypotheses over others
(e.g., preference for shorter hypotheses over larger hypotheses), with no hard restriction on the
hypotheses that can be eventually enumerated. This form of bias is called a preference bias or
a search bias.
Restriction bias – The bias of the CANDIDATE ELIMINATION algorithm is in the form of a
categorical restriction on the set of hypotheses considered. This form of bias is typically called
a restriction bias or a language bias.
Which type of inductive bias is preferred in order to generalize beyond the training data, a
preference bias or restriction bias?
A preference bias is more desirable than a restriction bias, because it allows the learner
to work within a complete hypothesis space that is assured to contain the unknown target
function.
In contrast, a restriction bias that strictly limits the set of potential hypotheses is
generally less desirable, because it introduces the possibility of excluding the unknown
target function altogether.
Occam's razor
Occam's razor: is the problem-solving principle that the simplest solution tends to be
the right one. When presented with competing hypotheses to solve a problem, one
should select the solution with the fewest assumptions.
Occam's razor: “Prefer the simplest hypothesis that fits the data”.
Many complex hypotheses that fit the current training data but fail to generalize
correctly to subsequent data.
Argument opposed:
There are few small trees, and our priori chance of finding one consistent with an
arbitrary set of data is therefore small. The difficulty here is that there are very many
small sets of hypotheses that one can define but understood by fewer learner.
The size of a hypothesis is determined by the representation used internally by the
learner. Occam's razor will produce two different hypotheses from the same training
examples when it is applied by two learners, both justifying their contradictory
conclusions by Occam's razor. On this basis we might be tempted to reject Occam's
razor altogether.
The ID3 algorithm grows each branch of the tree just deeply enough to perfectly classify
the training examples but it can lead to difficulties when there is noise in the data, or
when the number of training examples is too small to produce a representative sample
of the true target function. This algorithm can produce trees that overfit the training
examples.
The below figure illustrates the impact of overfitting in a typical application of decision tree
learning.
The horizontal axis of this plot indicates the total number of nodes in the decision tree,
as the tree is being constructed. The vertical axis indicates the accuracy of predictions
made by the tree.
The solid line shows the accuracy of the decision tree over the training examples. The
broken line shows accuracy measured over an independent set of test example
The accuracy of the tree over the training examples increases monotonically as the tree
is grown. The accuracy measured over the independent test examples first increases,
then decreases.
How can it be possible for tree h to fit the training examples better than h', but for it to perform
more poorly over subsequent examples?
1. Overfitting can occur when the training examples contain random errors or noise
2. When small numbers of examples are associated with leaf nodes.
Reduced-Error Pruning
The impact of reduced-error pruning on the accuracy of the decision tree is illustrated in below
figure
The additional line in figure shows accuracy over the test examples as the tree is pruned.
When pruning begins, the tree is at its maximum size and lowest accuracy over the test
set. As pruning proceeds, the number of nodes is reduced and accuracy over the test set
increases.
The available data has been split into three subsets: the training examples, the validation
examples used for pruning the tree, and a set of test examples used to provide an
unbiased estimate of accuracy over future unseen examples. The plot shows accuracy
over the training and test sets.
Rule Post-Pruning
For example, consider the decision tree. The leftmost path of the tree in below figure is
translated into the rule.
IF (Outlook = Sunny) ^ (Humidity = High)
THEN PlayTennis = No
Given the above rule, rule post-pruning would consider removing the preconditions
(Outlook = Sunny) and (Humidity = High)
It would select whichever of these pruning steps produced the greatest improvement in
estimated rule accuracy, then consider pruning the second precondition as a further
pruning step.
No pruning step is performed if it reduces the estimated rule accuracy.
There are three main advantages by converting the decision tree to rules before pruning
The gain ratio measure penalizes attributes by incorporating a split information, that is sensitive
to how broadly and uniformly the attribute splits the data
The data which is available may contain missing values for some attributes
Example: Medical diagnosis
<Fever = true, Blood-Pressure = normal, …, Blood-Test = ?, …>
Sometimes values truly unknown, sometimes low priority (or cost too high)
In some learning tasks the instance attributes may have associated costs.
For example: In learning to classify medical diseases, the patients described in terms of
attributes such as Temperature, BiopsyResult, Pulse, BloodTestResults, etc.
These attributes vary significantly in their costs, both in terms of monetary cost and cost
to patient comfort
Decision trees use low-cost attributes where possible, depends only on high-cost
attributes only when needed to produce reliable classifications