David Natingga [David Natingga] - Data Science Algorithms in a Week - Second Edition

House ownership and annual income

We implement an ID3 algorithm that constructs a decision tree for the data given in a CSV file. All sources are in the chapter directory. The most important parts of the source code are given here:

# source_code/3/construct_decision_tree.py
# Constructs a decision tree from data specified in a CSV file.# Format of a CSV file:# Each data item is written on one line, with its variables separated# by a comma. The last variable is used as a decision variable to# branch a node and construct the decision tree.import math# anytree module is used to visualize the decision tree constructed by
# this ID3 algorithm.from anytree import Node, RenderTreeimport syssys.path.append('../common')import commonimport decision_tree# Program startcsv_file_name = sys.argv[1]verbose = int(sys.argv[2]) # verbosity level, 0 - only decision tree
# Define the enquired column to be the last one.
# I.e. a column defining the decision variable.(heading, complete_data, incomplete_data, enquired_column) = common.csv_file_to_ordered_data(csv_file_name)tree = decision_tree.constuct_decision_tree( verbose, heading, complete_data, enquired_column)decision_tree.display_tree(tree)# source_code/common/decision_tree.py
# ***Decision Tree library ***# Used to construct a decision tree and a random forest.import mathimport randomimport commonfrom anytree import Node, RenderTreefrom common import printfv# Node for the construction of a decision tree.class TreeNode: def __init__(self, var=None, val=None): self.children = [] self.var = var self.val = val def add_child(self, child): self.children.append(child) def get_children(self): return self.children def get_var(self): return self.var def get_val(self): return self.val def is_root(self): return self.var is None and self.val is None def is_leaf(self): return len(self.children) == 0 def name(self): if self.is_root(): return "[root]" return "[" + self.var + "=" + self.val + "]"# Constructs a decision tree where heading is the heading of the table# with the data, i.e. the names of the attributes.# complete_data are data samples with a known value for every attribute.# enquired_column is the index of the column (starting from zero) which# holds the classifying attribute.def construct_decision_tree(verbose, heading, complete_data, enquired_column): return construct_general_tree(verbose, heading, complete_data, enquired_column, len(heading))# m is the number of the classifying variables that should be at most# considered at each node. m needed only for a random forest.def construct_general_tree(verbose, heading, complete_data, enquired_column, m): available_columns = [] for col in range(0, len(heading)): if col != enquired_column: available_columns.append(col) tree = TreeNode() printfv(2, verbose, "We start the construction with the root node" + " to create the first node of the tree.\n") add_children_to_node(verbose, tree, heading, complete_data, available_columns, enquired_column, m) return tree# Splits the data samples into the groups with each having a different# value for the attribute at the column col.def split_data_by_col(data, col): data_groups = {} for data_item in data: if data_groups.get(data_item[col]) is None: data_groups[data_item[col]] = [] data_groups[data_item[col]].append(data_item) return data_groups# Adds a leaf node to node.def add_leaf(verbose, node, heading, complete_data, enquired_column): leaf_node = TreeNode(heading[enquired_column], complete_data[0][enquired_column]) printfv(2, verbose, "We add the leaf node " + leaf_node.name() + ".\n") node.add_child(leaf_node)# Adds all the descendants to the node.def add_children_to_node(verbose, node, heading, complete_data, available_columns, enquired_column, m): if len(available_columns) == 0: printfv(2, verbose, "We do not have any available variables " + "on which we could split the node further, therefore " + "we add a leaf node to the current branch of the tree. ") add_leaf(verbose, node, heading, complete_data, enquired_column) return -1 printfv(2, verbose, "We would like to add children to the node " + node.name() + ".\n") selected_col = select_col( verbose, heading, complete_data, available_columns, enquired_column, m) for i in range(0, len(available_columns)): if available_columns[i] == selected_col: available_columns.pop(i) break data_groups = split_data_by_col(complete_data, selected_col) if (len(data_groups.items()) == 1): printfv(2, verbose, "For the chosen variable " + heading[selected_col] + " all the remaining features have the same value " + complete_data[0][selected_col] + ". " + "Thus we close the branch with a leaf node. ") add_leaf(verbose, node, heading, complete_data, enquired_column) return -1 if verbose >= 2: printfv(2, verbose, "Using the variable " + heading[selected_col] + " we partition the data in the current node, where" + " each partition of the data will be for one of the " + "new branches from the current node " + node.name() + ". " + "We have the following partitions:\n") for child_group, child_data in data_groups.items(): printfv(2, verbose, "Partition for " + str(heading[selected_col]) + "=" + str(child_data[0][selected_col]) + ": " + str(child_data) + "\n") printfv( 2, verbose, "Now, given the partitions, let us form the " + "branches and the child nodes.\n") for child_group, child_data in data_groups.items(): child = TreeNode(heading[selected_col], child_group) printfv(2, verbose, "\nWe add a child node " + child.name() + " to the node " + node.name() + ". " + "This branch classifies %d feature(s): " + str(child_data) + "\n", len(child_data)) add_children_to_node(verbose, child, heading, child_data, list( available_columns), enquired_column, m) node.add_child(child) printfv(2, verbose, "\nNow, we have added all the children nodes for the " + "node " + node.name() + ".\n")# Selects an available column/attribute with the highest
# information gain.def select_col(verbose, heading, complete_data, available_columns, enquired_column, m): # Consider only a subset of the available columns of size m. printfv(2, verbose, "The available variables that we have still left are " + str(numbers_to_strings(available_columns, heading)) + ". ") if len(available_columns) < m: printfv( 2, verbose, "As there are fewer of them than the " + "parameter m=%d, we consider all of them. ", m) sample_columns = available_columns else: sample_columns = random.sample(available_columns, m) printfv(2, verbose, "We choose a subset of them of size m to be " + str(numbers_to_strings(available_columns, heading)) + ".") selected_col = -1 selected_col_information_gain = -1 for col in sample_columns: current_information_gain = col_information_gain( complete_data, col, enquired_column) # print len(complete_data),col,current_information_gain if current_information_gain > selected_col_information_gain: selected_col = col selected_col_information_gain = current_information_gain printfv(2, verbose, "Out of these variables, the variable with " + "the highest information gain is the variable " + heading[selected_col] + ". Thus we will branch the node further on this " + "variable. " + "We also remove this variable from the list of the " + "available variables for the children of the current node. ") return selected_col# Calculates the information gain when partitioning complete_data# according to the attribute at the column col and classifying by the# attribute at enquired_column.