Notes

import math

depth = 0 # current depth of the decision tree that is being built
attribute_no = 1 # current attribute number that is being checked for
IG_list = [] # list of IGs for all attributes corresponding to the current depth
node_list = [] # list of all attributes for which IGs are calculated
dt_nodes = [] # list of all nodes that form the decision tree
final_IG_list = [] # list of IGs for nodes in the dt_nodes list
current_class = 1 # current class which is being traversed for a node
counter = 0 # keep track of whether the branch has been covered or not

def ID3(training_df, target_attribute_df, attributes_df):
if depth = 0 and attribute_no = 1:
current_node_df = training_df.columns[0:attribute_no]
if all(x == 1 for x in target_attribute_df):
# return +
if all(x == 0 for x in target_attribute_df):
# return -
if attributes_df.empty:
if all(x == 1 for x in target_attribute_df):
count_1 = count_1 + 1 # count no. of '1' value class labels for the current_node_df
if all(x == 0 for x in target_attribute_df):
count_0 = count_0 + 1 # count no. of '0' value class labels for the current_node_df
if count_1 >= count_0:
# return current_node with 1
else:
# return current_node with 0
for x in attributes_df.iteritems():
IG_list.append(IG(current_node_df,target_attribute_df, attributes_df))
if attribute_no < (len(training_df.columns) - 1):
current_node_df = attributes_df[attributes_df.columns[attribute_no:attribute_no + 1]]
attribute_no = attribute_no + 1
# final_IG_list.append(max(IG_list))
index = IG_list.index(max(IG_list)) # 'index' is the index of the best attribute i.e. with maximum IG
dt_nodes.append(training_df.columns[index + 1])
# depth = depth + 1
attribute_no = 1
IG_list = []
new_attributes_df = attributes_df.ix[:, attributes_df.columns != (index + 1)] # updated dataframe excluding the attribute which is already used in the decision tree
column_names = range(1,len(new_attributes_df.columns))
new_attributes_df.columns = column_names
if current_class and not counter:
current_class = 0
counter = 1
new_training_df_1 = training_df.loc[training_df[index + 1] == 1]
new_training_df_0 = training_df.loc[training_df[index + 1] == 0]
ID3(new_training_df_1, target_attribute_df, new_attributes_df)
if not current_class and not counter:
counter = 1
current_class = 1
ID3(new_training_df_0, target_attribute_df, new_attributes_df)
depth = depth + 1
training_df = training_df
ID3(new_training_df_1, target_attribute_df, new_attributes_df)




def IG(current_node_df, target_attribute_df, attributes_df):
if depth = 0:
entropy_parent = 1
# else:
# if x == 1 in attributes_df:
# entropy_parent = final_IG_list[depth - 1]
if all(x == 1 for x in current_node_df and y == 1 for y in target_attribute_df):
m1 = m1 + 1 # m1 corresponds to all examples where value of attribute is 1 and class label is 1
if all(x == 1 for x in current_node_df and y == 0 for y in target_attribute_df):
n1 = n1 + 1 # n1 corresponds to all examples where value of attribute is 1 and class label is 0
if all(x == 0 for x in current_node_df and y == 1 for y in target_attribute_df):
m2 = m2 + 1 # m2 corresponds to all examples where value of attribute is 0 and class label is 1
if all(x == 0 for x in current_node_df and y == 0 for y in target_attribute_df):
n2 = n2 + 1 # n2 corresponds to all examples where value of attribute is 0 and class label is 0

total_count = m1 + n1 + m2 + n2

entropy_1 = entropy_of_1(m1, n1)
entropy_0 = entropy_of_0(m2, n2)

weighted_entropy_children = ((m1+n1/total_count)*entropy_1) + ((m2+n2/total_count)*entropy_0)

return entropy_parent - weighted_entropy_children



def entropy_of_1(m1, n1):
a = m1/(m1+n1)
b = n1/(m1+n1)
return (-(a*math.log(a,2))-(b*math.log(b,2)))

def entropy_of_0(m2, n2):
return entropy_of_1(m2, n2)