26-07-2012, 03:26 PM
An Implementation of ID3 Decision Tree Learning Algorithm
DecisionTree2.pdf (Size: 138.84 KB / Downloads: 165)
Abstract
Decision tree learning algorithm has been successfully used in expert
systems in capturing knowledge. The main task performed in these systems is
using inductive methods to the given values of attributes of an unknown object
to determine appropriate classification according to decision tree rules. We
examine the decision tree learning algorithm ID3 and implement this algorithm
using Java programming. We first implement basic ID3 in which we dealt with
the target function that has discrete output values. We also extend the domain
of ID3 to real-valued output, such as numeric data and discrete outcome
rather than simply Boolean value. The Java applet provided at last section
offers a simulation of decision-tree learning algorithm in various situations.
Some shortcomings are discussed in this project as well.
Introduction
What is Decision Tree?
What is decision tree: A decision tree is a tree in which each branch node
represents a choice between a number of alternatives, and each leaf node
represents a decision.
Decision tree are commonly used for gaining information for the purpose of
decision -making. Decision tree starts with a root node on which it is for users
to take actions. From this node, users split each node recursively according to
decision tree learning algorithm. The final result is a decision tree in which
each branch represents a possible scenario of decision and its outcome.
What is decision tree learning algorithm?
'Decision tree learning is a method for approximating discrete-valued target
functions, in which the learned function is represented by a decision tree.
Decision tree learning is one of the most widely used and practical methods
for inductive inference'. (Tom M. Mitchell,1997,p52)
Decision tree learning algorithm has been successfully used in expert
systems in capturing knowledge. The main task performed in these systems is
using inductive methods to the given values of attributes of an unknown object
to determine appropriate classification according to decision tree rules.
Decision trees classify instances by traverse from root node to leaf node. We
start from root node of decision tree, testing the attribute specified by this
node, then moving down the tree branch according to the attribute value in the
given set. This process is the repeated at the sub-tree level.
What is decision tree learning algorithm suited for:
1. Instance is represented as attribute-value pairs. For example, attribute
'Temperature' and its value 'hot', 'mild', 'cool'. We are also concerning to
extend attribute -value to continuous-valued data (numeric attribute value) in
our project.
2.The target function has discrete output values. It can easily deal with
instance which is assigned to a boolean decision, such as 'true' and 'false',
'p(positive)' and 'n(negative)'. Although it is possible to extend target to realvalued
outputs, we will cover the issue in the later part of this report.
3.The training data may contain errors. This can be dealt with pruning
techniques that we will not cover here.
The 3 widely used decision tree learning algorithms are: ID3, ASSISTANT
and C4.5. We will cover ID3 in this report.