<?
/*

this module contains all of the functions for creating the id3 dtree, parsing it to create a trace file, and
making classificaions of data based on the tree. the functions are called from the main index page.

tree array data structure:

  the array size is potentially the sum of all elements $max_val^(N-1), where N = 1...$num_attr

  php does not allocate array space for unassigned elements, so it performs reasonably well on
    such a large array space because the space tends to be reasonably sparse

  the index of each node is the string representing the path to that node, with separators
    (e.g. root|ATTR1-value1|ATTR2-value2|ATTR3-value3)
    since php is does not have strongly typed variables, such indices are possible

*/

function information_gain($attribute, $instances) {
  /*
    this function calculates the information gained on a specific attribute over a set of instances
      according to the average entropy formula

    the function behaves correctly when there are more than two classifications of instances

    $attribute holds the name of the attribute for which to calculate the information gain
    $instances holds a query string that describes a specific set of instances from the data set
  */

  $query = "select classification, count(classification) as instances from training $instances ";
  $query = $query."group by classification order by instances desc";
  $inst = mysql_query($query);
  // if there are no instances left or there is only one class of instance left, then no info can be gained
  if (mysql_numrows($inst) < 1) return 0;
  $values = mysql_query("select $attribute from training $instances group by $attribute");
  // if there are less than two different values left for the selected attribute, then no info can be gained
  if (mysql_numrows($values) < 1) return 0;

  // calculate the entropy of the entire set
  $num_inst = mysql_result(mysql_query("select count(instance) from training $instances"),0,0);
  $entropy = 0;
  for ($i=0; $i < mysql_numrows($inst); $i++) {
    $p = mysql_result($inst, $i, 1) / $num_inst;
    $entropy -= ($p * log10($p) / log10(2));
  }

  // subtract off the weighted entropies of the subsets to find information gain
  for ($i=0; $i < mysql_numrows($values); $i++) {
    $value = mysql_result($values, $i, 0);
    $sub_inst = mysql_result(mysql_query("select count(instance) from training $instances and $attribute='$value'"),0,0);
    $query = "select classification, count(classification) as instances from training $instances and $attribute='$value' ";
    $query = $query."group by classification order by instances desc";
    $inst = mysql_query($query);
    for ($j=0; $j < mysql_numrows($inst); $j++) {
      $p = mysql_result($inst, $j, 1) / $sub_inst;
      $entropy += $sub_inst * ($p * log10($p) / log10(2)) / $num_inst; 
    }
  }

  return $entropy;
}

function train_id3_dtree($tree, $root, $num_attr, $attr_left, $inst_left, $max_val) {
  /*
    this function generates a decision tree based on the id3 algorithm and returns the tree as an array

    $tree holds the current decision tree
    $root holds the current node being considered (an array index)
    $num_attr holds the number of attributes
    $attr_left holds a whitepace-separated list of attributes that have not yet been used
    $inst_left holds a query string that describes only the remaining instances from the data set
    $max_val holds the maximum number of possible values for any of attributes
  */
  
  if ($inst_left == '') $inst_left = "where instance like '%'";

  $query = "select classification, count(classification) as instances from training $inst_left ";
  $query = $query."group by classification order by instances desc";
  $classes = mysql_query($query);
  if (mysql_numrows($classes) == 1) // if all examples have the same target value, give the root that label
    $tree[$root] = mysql_result($classes, 0, 0);
  else if ($attr_left == '') { // else if attributes is the empty set, label the root according to the most common value 
    if (mysql_numrows($classes) == 0) { // if there are no examples left use the most common value from the entire set
      $query = "select classification, count(classification) as instances from training ";
      $query = $query."group by classification order by instances desc";
      $classes = mysql_query($query);
    } else { // if there are two or more classes with the most frequent occurences choose the most frequent
             // of these classes from the entire data set
      $i = 0;
      while (($i < mysql_numrows($classes)-1) && (mysql_result($classes, $i + 1, 1) == mysql_result($classes, 0, 1))) $i++;
      $query = "select classification, count(classification) as instances from training where ";
      for ($j=1; $j < $i; $j++) $query = $query." classification='".mysql_result($classes, $j, 0)."' or ";
      if ($i > 0) {
        $query = $query."classification='".mysql_result($classes, $i, 0)."' group by classification order by instances desc";
        $classes = mysql_query($query);
      }
    }
    $tree[$root] = mysql_result($classes, 0, 0);
  } else if (mysql_numrows($classes) == 0) { // else if there are no instances in the data set, no class can be determined
    $tree[$root] = "*NO DATA*";
  } else {
    // calculate the information gain for each attribute A, according to the average entropy formula
    $attr = explode(" ",$attr_left);
    for ($i=0; $i < sizeof($attr); $i++) $gain[$i] = information_gain($attr[$i], $inst_left);

    // select the attribute with the lowest average entropy (highest information gain) and make this the
    // attribute tested at the root
    $tested = 0;
    for ($i=1; $i < sizeof($attr); $i++) if ($gain[$i] > $gain[$tested]) $tested = $i;

    // this code was used for question 4 to choose an attribute randomly:
    // $tested = rand(0,sizeof($attr)-1);

    $attr = $attr[$tested];
    $tree[$root] = $attr;

    $values = mysql_query("select $attr from training $inst_left group by $attr order by $attr");

    for ($i=0; $i < mysql_numrows($values); $i++) { // for each possible value V of this attribute
      // add a new branch below the root, corresponding to A = V
      $value = mysql_result($values, $i, 0);
      $branch = $root."|".$attr."-".$value;

      // let examples(V) be those examples with A = V
      $query = "select classification, count(classification) as instances from training $inst_left and $attr='$value' ";
      $query = $query."group by classification order by instances desc";
      $examples = mysql_query($query);

      if (mysql_numrows($examples) == 0) // if examples(V) is empty, make the new branch a leaf node labelled with the most
                                         // common value among examples
        $tree[$branch] = mysql_result($classes, 0, 0);
      else { // else let the new branch be the tree created by recursively calling the id3 function
        $new_attr_left = trim(ereg_replace("( )+($attr)( )+"," "," ".$attr_left." "));
        $new_inst_left = $inst_left." and $attr='$value'";
        $tree = train_id3_dtree($tree, $branch, $num_attr, $new_attr_left, $new_inst_left, $max_val);
      }
    }
  }
  return $tree;
}

function id3_dtree_trace($tree, $root, $level) {
  /*
    this function returns a trace of a dtree generated by the id3 algorithm starting from the node $root

    it parses the tree in a depth-first, inorder fashion, and labels the first node as level $level
  */

  $attr = $tree[$root];
  $trace = $trace."LEVEL$level: $attr";
  if (mysql_numrows(mysql_query("select id from attributes where id='$attr'")) > 0) { // if root node is an attribute
    $trace = $trace."\n";
    $values = mysql_query("select $attr from training group by $attr order by $attr");
    for ($i=0; $i < mysql_numrows($values); $i++) { // parse subtrees
      $value = mysql_result($values, $i, 0);
      if (isset($tree[$root."|".$attr."-".$value]))
        $trace = $trace."BRANCH: $value\n".id3_dtree_trace($tree,$root."|".$attr."-".$value, $level+1);
    }
  } else {
    $query = "select count(instance) from training where classification='$attr'";
    $root = explode("|", $root);
    for ($i=1; $i < sizeof($root); $i++) {
      $attr = explode("-",$root[$i]);
      $query = $query." and ".$attr[0]."='".$attr[1]."'";
    }
    $trace = $trace." (".mysql_result(mysql_query($query), 0, 0).")\n";
  }
  return $trace;
}

function id3_dtree_classify($tree, $root, $set, $instance) {
  /*
    this function returns the classification made by the dtree $tree for the element
    of the data set $set labeled by $instance
  */

  $attr = $tree[$root];
  $value = mysql_query("select $attr from $set where instance='$instance'");
  if (mysql_error()) // if the attr is not a valid attribute, it must be a classification
    return $attr;
  $value = mysql_result($value, 0, 0);
  if (isset($tree[$root."|".$attr."-".$value])) // if the tree knows how to classify the attribute, continue parsing
    return id3_dtree_classify($tree, $root."|".$attr."-".$value, $set, $instance);
  // if the tree doesn't branch on the attribute value, return the most common classification at that node
  $root = explode("|", $root);
  $query = "select classification, count(classification) as instances from training where instance like '%'";
  for ($i=1; $i < sizeof($root); $i++) {
    $attr = explode("-",$root[$i]);
    $query = $query." and ".$attr[0]."='".$attr[1]."' ";
  }
  $query = $query."group by classification order by instances desc";
  return mysql_result(mysql_query($query), 0, 0);
}

?>