Scribd
Upload
4 views5 pages

ID3 Algorithm

The document outlines an algorithm for generating a decision tree from a training dataset, D, using a specified attribute selection method to determine the best splitting criterion. It details the steps to create nodes, handle class labels, and partition data based on outcomes of the splitting criterion. The computational complexity of the algorithm is O(n × |D| × log(|D|)), where n is the number of attributes and |D| is the number of training tuples.

Uploaded by

contactvedantraje
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views5 pages

ID3 Algorithm

The document outlines an algorithm for generating a decision tree from a training dataset, D, using a specified attribute selection method to determine the best splitting criterion. It details the steps to create nodes, handle class labels, and partition data based on outcomes of the splitting criterion. The computational complexity of the algorithm is O(n × |D| × log(|D|)), where n is the number of attributes and |D| is the number of training tuples.

Uploaded by

contactvedantraje
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Algorithm: Generate decision tree.

Generate a decision tree from the training tuples


of
data partition, D.
Input
:
Data partition, D, which is a set of training tuples and their associated class
labels;
attribute list, the set of candidate
attributes;
Attribute selection method, a procedure to determine the splitting criterion that
“best”
partitions the data tuples into individual classes. This criterion consists of a
splitting attribute and, possibly, either a split-point or splitting subset.

Output: A decision
tree.
l Method:
1) (1) create a node N ;
2) (2) if tuples in D are all of the same class, C,
then
3) (3) return N as a leaf node labeled with the class
C;
4) (4) if attribute list is empty then
5) (5) return N as a leaf node labeled with the
majority class in D; // majority voting
6) (6) apply Attribute selection method(D, attribute
list) to find the “best” splitting criterion;
7) (7) label node N with splitting criterion;
(8) if splitting attribute is discrete-valued and
multiway splits allowed then // not restricted to
binary trees
(9) attribute list ← attribute list − splitting attribute; //
remove splitting attribute
(10) for each outcome j of splitting criterion
// partition the tuples and grow subtrees for
each
partition
(11) let Dj be the set of data tuples in D satisfying
outcome j; // a partition
l 12) if Dj is empty then
l 13) attach a leaf labeled with the majority class in
D to node N ;
l 14) else attach the node returned by Generate
decision tree(D j , attribute list) to node N ;
l endfor
l 15) return N ;
l The computational complexity of the algorithm
given training set D is O(n × |D| ×log(|D|)), where
n is the number of attributes describing the tuples
in D and |D| is the number of training tuples in D.
l The computational cost of growing a tree grows
at most n × |D| × log(|D|) with |D| tuples.

You might also like