Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Decision tree pseudocode
ID3 Pseudocode
id3(examples, attributes)
'''
examples are the training examples. attributes is a list of
attributes that may be tested by the learned decison tree. Returns
a tree that correctly classifies the given examples. Assume that
the targetAttribute, which is the attribute whose value is to be
predicted by the tree, is a class variable.
'''
node = DecisionTreeNode(examples)
# handle target attributes with arbitrary labels
dictionary = summarizeExamples(examples, targetAttribute)
for key in dictionary:
if dictionary[key] == total number of examples
node.label = key
return node
# test for number of examples to avoid overfitting
if attributes is empty or number of examples < minimum allowed per branch:
node.label = most common value in examples
return node
bestA = the attribute with the most information gain
node.decision = bestA
for each possible value v of bestA:
subset = the subset of examples that have value v for bestA
if subset is not empty:
node.addBranch(id3(subset, targetAttribute, attributes-bestA))
return node
Information Gain Pseudocode
infoGain(examples, attribute, entropyOfSet)
gain = entropyOfSet
for value in attributeValues(examples, attribute):
sub = subset(examples, attribute, value)
gain -= (number in sub)/(total number of examples) * entropy(sub)
return gain
Entropy Pseudocode
entropy(examples)
'''
log2(x) = log(x)/log(2)
'''
result = 0
# handle target attributes with arbitrary labels
dictionary = summarizeExamples(examples, targetAttribute)
for key in dictionary:
proportion = dictionary[key]/total number of examples
result -= proportion * log2(proportion)
return result
@adityamhatre

This comment has been minimized.

Copy link

@adityamhatre adityamhatre commented Feb 14, 2018

what is target attribute ?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment