For the longest time I have simply been showing outputs from my decision tree generator and telling you all the things it is capable of doing, but I haven’t given you access to it or shown you the code itself. For the most part this is because the code is ugly and some may say hacked, but since I am not a professionally trained software engineer, I don’t care too much. I am a roboticist who is interested in writing software and designing systems to allow people (especially those with little experience) to enjoy robots and machine learning, more so than making optimally efficient software. My code is fully commented (maybe even overly so) in the hopes that someone looking at it in the future won’t have trouble understanding what it does (or how to make it better). The code is being hosted on my Bitbucket account and there is a link to the code on my software page.

A brief explanation of how to use the generator should start with explaining that the decision tree generator is essentially a single Java Class object and the only function the user is required to interact with is the constructor for the class. The constructor for a Class is the function/method in the object oriented programming Class which initializes an object (an instance) of that Class. Meaning the constructor builds you one of the things you want. All you have to do is pass the constructor some inputs. The decision tree generator constructor is relatively large and looks like this:

// CONSTRUCTOR //
  Decision_Tree(String tree_name, int[] outputs, String[] output_labels, int[][] attributes, String[] attribute_labels, String[][] attribute_level_labels, int leave_out, int[] initial_node, float screen_width)

Yes, there are a lot of inputs to this single function, but since it is the only one you need to use to generate the decision tree and Arduino code, it really isn’t all that bad. Plus, I’ll explain what each input is and how to make it.

(String tree_name) should be the name of the decision tree you are making, such as “play_tennis”. Make sure this name contains no spaces or punctuation except underscore, “_”, characters.

(int[] outputs) should be be an integer array representing the output label/class for each input/output pair. This integer array should have an element for each input/output pair, it should contain only numbers ranging from 0 to the number of possible output classes. If your data is something like “no”/”yes” or “left”/”right”/”center” simply replace each label with an integer so that no = 0, yes = 1 or left = 0, right = 1 and center = 2. This array may look something like int[] outputs = {0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0};

(String[] output_labels) should be an array of String objects, where each element represents the actual label for the corresponding output level/class. For example we just learned that the outputs should be integers from 0 to the number of output classes so the number of labels should be equal to the number of classes as well. For example: String[] output_labels = {“no”, “yes”} or String[] output_labels = {“left”, “right”, “center”};

(int[][] attributes) might be little more confusing because it is an array of integer arrays, but if you think about it as a matrix or a spreadsheet it shouldn’t be too difficult to understand. Each column of the matrix/spreadsheet of attributes represents a different attribute, for example: int[][] attributes = {outlook, humidity, temperature, wind}. Each one of these columns is just like the outputs array we already learned about. The column arrays for all the attributes must be the same length (have the same number of elements) and each one must only contain numbers from 0 to the number of levels that specific attribute can take on. The length of all the columns must be the same as the outputs array because the decision tree algorithm expects to see input/output pairs, where the entry for all the attributes is the input and the output entry is obviously the output.

(String[][] attribute_level_labels) is very similar to the attributes matrix, except that the length of the columns are simply equal to the number of different levels for that given attribute. For example: we could have String[] attribute1_labels = {“hot”, “mild”, “cold”} and String[][] attribute2_labels = {“cloudy”, “sunny”}. Then String[][] attribute_level_labels = {attribute1_labels, attribuite2_labels}. We need to have a label for each possible value of a given attribute and an array of labels for each of the attributes.

(int leave_out) is simply the number of input/output pairs that we have passed to the constructor that we do not want to use to generate the decision tree. In general it is always a good idea to partition your data into test and validation sets randomly and then use the percent accuracy of the validation set to determine how well the tree generated from the training set will generalize to new instances. If the number leave_out is greater than 0 then this is the number of pairs at the end of the output and attribute columns which will be ignored during tree generation. The validation data will be output in the command line in a format for use on the Arduino for validation.

(int[] initial_node) is used to help generate the graphical tree and the auto-generated code. This should always be passed int[] initial_node = {1, 1}.

(float screen_width) is used to determine the size of the graphical output. Processing has a global constant called width which should be passed for this value.

I’ll go into more detail explaining exactly how to generate some of this data without having to manually enter it all by hand in my next post.

This is going to have to be a short post because I’m simply out of time for the day.

I’ve been doing some reading about information theory as the basis for using entropy and information gain as measures to choose the branches and leaves of a decision tree. I’ve also been reading other people’s implementations of decision tree algorithms, so I won’t be totally reinventing the wheel with this project. First off, a very good general explanation of decision trees can be found at Rudjer Boskovic Institute’s Data Mining Server tutorial titled Decision Trees. In the tutorial is J. Ross Quinlan’s classic decision tree algorithm ID3.

function ID3
Input:   (R: a set of non-target attributes,
          C: the target attribute,
          S: a training set) returns a decision tree;
begin    If S is empty, return a single node with
      value Failure;
   If S consists of records all with the same
      value for the target attribute,
      return a single leaf node with that value;
   If R is empty, then return a single node
      with the value of the most frequent of the
      values of the target attribute that are
      found in records of S; [in that case
      there may be be errors, examples
      that will be improperly classified];
   Let A be the attribute with largest
      Gain(A,S) among attributes in R;
   Let {aj| j=1,2, .., m} be the values of
      attribute A;
   Let {Sj| j=1,2, .., m} be the subsets of
      S consisting respectively of records
      with value aj for A;
   Return a tree with root labeled A and arcs
      labeled a1, a2, .., am going respectively
      to the trees (ID3(R-{A}, C, S1), ID3(R-{A}, C, S2),
      .....,ID3(R-{A}, C, Sm);
   Recursively apply ID3 to subsets {Sj| j=1,2, .., m}
      until they are empty
end

I’m doing my best to implement something similar to this in Processing, we’ll see how it goes. So far I am able to calculate the entropy and gain of a collection and all it’s attributes, but have not yet written the code to branch the attributes and outputs in order to recursively traverse the tree. If this doesn’t prove too difficult I’d also like to make graphical output to demonstrate the structure of the tree and possibly post-prune the tree as recommended by experts to remove over-fitted branches that reduce the decision tree’s ability to generalize to data outside the training set.