title: Implementing Pseudocode For ID3 Algorithm
body: <p>I'm trying to implement the pseudo code for the id3 algorithm that is given below</p>
  
  <pre><code>function ID3 (I, 0, T) {   
  /* I is the set of input attributes 
   * O is  the output attribute 
   * T is a set of training data 
   * 
   * function ID3 returns a decision tree */
  
   if (T is empty) { return a single node with the value "Failure"; } 
  
   if (all records in T have the same value for O) {return a single node with that value;} 
  
   if (I is empty) { 
       return a single node with the value of the most frequent value of O in T; 
      /* Note: some elements in this node will be incorrectly classified */ 
   }
  
  /* now handle the case where we can’t return a single node */ 
  
  compute the  information gain for each attribute in I relative to T;
  
  let X be the attribute with largest Gain(X, T) of the attributes in I; 
  
  let {x_j| j=1,2, .., m} be the values of X; 
  
  let {T_j| j=1,2, .., m} be the subsets of T when T is 
      partitioned according the value of X; 
  
      return a tree with the root node labelled X and 
      arcs labelled x_1, x_2, .., x_m, where the arcs go to the 
      trees ID3(I-{X}, O, T_1), ID3(I-{X}, O, T_2), .., ID3(I-{X}, O, T_m);
  }
  </code></pre>
  
  <p>Here is what I have so far</p>
  
  <pre><code>def ID3(attributes, class_set, training_data):
      if not training_data:
          tree = Tree("Empty")
      elif np.sum(class_set) == len(class_set):
          #there are only two possible values for a class_set
          #0 or 1 so if the class set is all 1 return 1 else return 0
          tree = Tree("1")
      elif np.sum(class_set) == 0:
          tree = Tree("0")
      elif not attributes:
          if np.count_nonzero(class_set) &gt; (len(class_set) - np.count_nonzero(class_set)):
              #if there are more ones than zeroes in the class set return 1
              #else return 0
              tree = Tree("1")
          else:
              tree = Tree("0")
      else:
          max_value = 0
          node_name = ""
          for value in range (len(training_data[0]) -1):
              ig = IG(training_data, value) #calculating the gain for each attribute and keeping track of it
                                            #largest ig is node_name
              if ig &gt; max_value:
                  max_value = ig
                  node_name = attributes[value][0]
                  col_n = value
          tree = Tree(node_name)
      true_values = []
      false_values = []
  
  
      #the code here is splitting the partition according to the values of x which are
      #always 0 and 1
      for binary_values in range(len(training_data) -1):
          if training_data [binary_values + 1][col_n] == '1':
              true_values.append(training_data[binary_values + 1])
          else:
              false_values.append(training_data[binary_values + 1])
      true_values = np.array(true_values)
      false_values = np.array(false_values)
      #since the data_table actually contains the names of the column I'm  deleting them here
      true_values = np.delete(true_values, col_n, 1)
      false_values = np.delete(false_values, col_n, 1)
      #T is now partiontioned according to the values of X
  </code></pre>
  
  <p>I'm having trouble implementing the last few lines of the psuedocode which are</p>
  
  <pre><code>    return a tree with the root node labelled X and 
      arcs labelled x_1, x_2, .., x_m, where the arcs go to the 
      trees ID3(I-{X}, O, T_1), ID3(I-{X}, O, T_2), .., ID3(I-{X}, O, T_m);
  </code></pre>
  
  <p>I don't get what the pseudo code means when its referring to arcs. I'm assuming it's referring to the branches but I don't know how to return an arc or how to make the actual recursive call on it.</p>