Tree.cc

Go to the documentation of this file.

//                            Tree.cxx                                  //
// =====================================================================//
// This is the object implementation of a decision tree.                //
// References include                                                   //
//    *Elements of Statistical Learning by Hastie,                      //
//     Tibshirani, and Friedman.                                        //
//    *Greedy Function Approximation: A Gradient Boosting Machine.      //
//     Friedman. The Annals of Statistics, Vol. 29, No. 5. Oct 2001.    //
//    *Inductive Learning of Tree-based Regression Models. Luis Torgo.  //    
//                                                                      //

// _______________________Includes_______________________________________//

#include "L1Trigger/L1TMuonEndCap/interface/Tree.h"
#include <iostream>
#include <sstream>

// _______________________Constructor(s)________________________________//

Tree::Tree()
{
  rootNode = new Node("root");
  
  terminalNodes.push_back(rootNode);
  numTerminalNodes = 1;
}

Tree::Tree(std::vector< std::vector<Event*> >& cEvents)
{
  rootNode = new Node("root");
  rootNode->setEvents(cEvents);
  
  terminalNodes.push_back(rootNode);
  numTerminalNodes = 1;
}
// _______________________Destructor____________________________________//

Tree::~Tree()
{
  // When the tree is destroyed it will delete all of the nodes in the tree.
// The deletion begins with the rootnode and continues recursively.
    delete rootNode;
}

// ______________________Get/Set________________________________________//

void Tree::setRootNode(Node *sRootNode)
{
  rootNode = sRootNode;
}

Node * Tree::getRootNode()
{
  return rootNode;
}

// ----------------------------------------------------------------------

void Tree::setTerminalNodes(std::list<Node*>& sTNodes)
{
  terminalNodes = sTNodes;
}

std::list<Node*>& Tree::getTerminalNodes()
{
  return terminalNodes;
}

// ----------------------------------------------------------------------

Int_t Tree::getNumTerminalNodes()
{
  return numTerminalNodes;
}

// ______________________Performace_____________________________________//

void Tree::calcError() 
{ 
  // Loop through the separate predictive regions (terminal nodes) and 
  // add up the errors to get the error of the entire space.  
  
  Double_t totalSquaredError = 0; 
  
  for(std::list<Node*>::iterator it=terminalNodes.begin(); it!=terminalNodes.end(); it++) 
    { 
      totalSquaredError += (*it)->getTotalError();  
    } 
  rmsError = sqrt( totalSquaredError/rootNode->getNumEvents() ); 
} 

// ----------------------------------------------------------------------

void Tree::buildTree(Int_t nodeLimit)
{
  // We greedily pick the best terminal node to split.
  Double_t bestNodeErrorReduction = -1;
  Node* nodeToSplit = 0;
  
  if(numTerminalNodes == 1)
    {   
      rootNode->calcOptimumSplit();
      calcError();
      //        std::cout << std::endl << "  " << numTerminalNodes << " Nodes : " << rmsError << std::endl;
    }
  
  for(std::list<Node*>::iterator it=terminalNodes.begin(); it!=terminalNodes.end(); it++)
    {   
      if( (*it)->getErrorReduction() > bestNodeErrorReduction ) 
    {   
      bestNodeErrorReduction = (*it)->getErrorReduction();
      nodeToSplit = (*it);
    }    
    }   
  
  //std::cout << "nodeToSplit size = " << nodeToSplit->getNumEvents() << std::endl;
  
  // If all of the nodes have one event we can't add any more nodes and reduce the error.
  if(nodeToSplit == 0) return;
  
  // Create daughter nodes, and link the nodes together appropriately.
  nodeToSplit->theMiracleOfChildBirth();
  
  // Get left and right daughters for reference.
  Node* left = nodeToSplit->getLeftDaughter();
  Node* right = nodeToSplit->getRightDaughter();
  
  // Update the list of terminal nodes.
  terminalNodes.remove(nodeToSplit);
  terminalNodes.push_back(left);
  terminalNodes.push_back(right);
  numTerminalNodes++;
  
  // Filter the events from the parent into the daughters.
  nodeToSplit->filterEventsToDaughters();  
  
  // Calculate the best splits for the new nodes.
  left->calcOptimumSplit();
  right->calcOptimumSplit();
  
  // See if the error reduces as we add more nodes.
  calcError();
  
  if(numTerminalNodes % 1 == 0)
    {
      //        std::cout << "  " << numTerminalNodes << " Nodes : " << rmsError << std::endl;
    }
  
  // Repeat until done.
  if(numTerminalNodes <  nodeLimit) buildTree(nodeLimit);
}

// ----------------------------------------------------------------------

void Tree::filterEvents(std::vector<Event*>& tEvents)
{
  // Use trees which have already been built to fit a bunch of events
  // given by the tEvents vector.
  
  // Set the events to be filtered.
  rootNode->getEvents() = std::vector< std::vector<Event*> >(1);
  rootNode->getEvents()[0] = tEvents;
  
  // The tree now knows about the events it needs to fit.
  // Filter them into a predictive region (terminal node).
  filterEventsRecursive(rootNode);
}

// ----------------------------------------------------------------------

void Tree::filterEventsRecursive(Node* node)
{
  // Filter the events repeatedly into the daughter nodes until they
  // fall into a terminal node.
  
  Node* left = node->getLeftDaughter();
  Node* right = node->getRightDaughter();
  
  if(left == 0 || right == 0) return;
  
  node->filterEventsToDaughters();
  
  filterEventsRecursive(left);
  filterEventsRecursive(right);
}

// ----------------------------------------------------------------------

Node* Tree::filterEvent(Event* e)
{
  // Use trees which have already been built to fit a bunch of events
  // given by the tEvents vector.
  
  // Filter the event into a predictive region (terminal node).
  Node* node = filterEventRecursive(rootNode, e);
  return node;
}

// ----------------------------------------------------------------------

Node* Tree::filterEventRecursive(Node* node, Event* e)
{
  // Filter the event repeatedly into the daughter nodes until it
  // falls into a terminal node.
  
  
  Node* nextNode = node->filterEventToDaughter(e);
  if(nextNode == 0) return node;
  
  return filterEventRecursive(nextNode, e);
}

// ----------------------------------------------------------------------


void Tree::rankVariablesRecursive(Node* node, std::vector<Double_t>& v)
{
  // We recursively go through all of the nodes in the tree and find the
  // total error reduction for each variable. The one with the most
  // error reduction should be the most important.
  
  Node* left = node->getLeftDaughter();
  Node* right = node->getRightDaughter();
  
  // Terminal nodes don't contribute to error reduction.
  if(left==0 || right==0) return;
  
  Int_t sv =  node->getSplitVariable();
  Double_t er = node->getErrorReduction();
  
  //if(sv == -1)
  //{
  //std::cout << "ERROR: negative split variable for nonterminal node." << std::endl;
  //std::cout << "rankVarRecursive Split Variable = " << sv << std::endl;
  //std::cout << "rankVarRecursive Error Reduction = " << er << std::endl;
  //}
  
  // Add error reduction to the current total for the appropriate
  // variable.
  v[sv] += er;
  
  rankVariablesRecursive(left, v);
  rankVariablesRecursive(right, v); 
  
}

// ----------------------------------------------------------------------

void Tree::rankVariables(std::vector<Double_t>& v)
{
  rankVariablesRecursive(rootNode, v);
}

// ----------------------------------------------------------------------


void Tree::getSplitValuesRecursive(Node* node, std::vector<std::vector<Double_t>>& v)
{
  // We recursively go through all of the nodes in the tree and find the
  // split points used for each split variable.
  
  Node* left = node->getLeftDaughter();
  Node* right = node->getRightDaughter();
  
  // Terminal nodes don't contribute.
  if(left==0 || right==0) return;
  
  Int_t sv =  node->getSplitVariable();
  Double_t sp = node->getSplitValue();
  
  if(sv == -1)
    {
      std::cout << "ERROR: negative split variable for nonterminal node." << std::endl;
      std::cout << "rankVarRecursive Split Variable = " << sv << std::endl;
    }
  
  // Add the split point to the list for the correct split variable.
  v[sv].push_back(sp);
  
  getSplitValuesRecursive(left, v);
  getSplitValuesRecursive(right, v); 
  
}

// ----------------------------------------------------------------------

void Tree::getSplitValues(std::vector<std::vector<Double_t>>& v)
{
  getSplitValuesRecursive(rootNode, v);
}

// ______________________Storage/Retrieval______________________________//

template <typename T>
std::string numToStr( T num )
{
  // Convert a number to a string.
  std::stringstream ss;
  ss << num;
  std::string s = ss.str();
  return  s;
}

// ----------------------------------------------------------------------

void Tree::addXMLAttributes(TXMLEngine* xml, Node* node, XMLNodePointer_t np)
{
  // Convert Node members into XML attributes    
  // and add them to the XMLEngine.
  xml->NewAttr(np, 0, "splitVar", numToStr(node->getSplitVariable()).c_str());
  xml->NewAttr(np, 0, "splitVal", numToStr(node->getSplitValue()).c_str());
  xml->NewAttr(np, 0, "fitVal", numToStr(node->getFitValue()).c_str());
}

// ----------------------------------------------------------------------

void Tree::saveToXML(const char* c)
{
  
  TXMLEngine* xml = new TXMLEngine();
  
  // Add the root node.
  XMLNodePointer_t root = xml->NewChild(0, 0, rootNode->getName().c_str());
  addXMLAttributes(xml, rootNode, root);
  
  // Recursively write the tree to XML.
  saveToXMLRecursive(xml, rootNode, root);
  
  // Make the XML Document.
  XMLDocPointer_t xmldoc = xml->NewDoc();
  xml->DocSetRootElement(xmldoc, root);
  
  // Save to file.
  xml->SaveDoc(xmldoc, c);
  
  // Clean up.
  xml->FreeDoc(xmldoc);
  delete xml;
}

// ----------------------------------------------------------------------

void Tree::saveToXMLRecursive(TXMLEngine* xml, Node* node, XMLNodePointer_t np)
{
  Node* l = node->getLeftDaughter();
  Node* r = node->getRightDaughter();
  
  if(l==0 || r==0) return;
  
  // Add children to the XMLEngine. 
  XMLNodePointer_t left = xml->NewChild(np, 0, "left");
  XMLNodePointer_t right = xml->NewChild(np, 0, "right");
  
  // Add attributes to the children.
  addXMLAttributes(xml, l, left);
  addXMLAttributes(xml, r, right);
  
  // Recurse.
  saveToXMLRecursive(xml, l, left);
  saveToXMLRecursive(xml, r, right);
}

// ----------------------------------------------------------------------

void Tree::loadFromXML(const char* filename)
{   
  // First create the engine.
  TXMLEngine* xml = new TXMLEngine;
  
  // Now try to parse xml file.
  XMLDocPointer_t xmldoc = xml->ParseFile(filename);
  if (xmldoc==0)
    {
      delete xml;
      return;  
    }
  
  // Get access to main node of the xml file.
  XMLNodePointer_t mainnode = xml->DocGetRootElement(xmldoc);
  
  // Recursively connect nodes together.
  loadFromXMLRecursive(xml, mainnode, rootNode);
  
  // Release memory before exit
  xml->FreeDoc(xmldoc);
  delete xml;
}

// ----------------------------------------------------------------------

void Tree::loadFromXMLRecursive(TXMLEngine* xml, XMLNodePointer_t xnode, Node* tnode) 
{
  
  // Get the split information from xml.
  XMLAttrPointer_t attr = xml->GetFirstAttr(xnode);
  std::vector<std::string> splitInfo(3);
  for(unsigned int i=0; i<3; i++)
    {
      splitInfo[i] = xml->GetAttrValue(attr); 
      attr = xml->GetNextAttr(attr);  
    }
  
  // Convert strings into numbers.
  std::stringstream converter;
  Int_t splitVar;
  Double_t splitVal;
  Double_t fitVal;  
  
  converter << splitInfo[0];
  converter >> splitVar;
  converter.str("");
  converter.clear();
  
  converter << splitInfo[1];
  converter >> splitVal;
  converter.str("");
  converter.clear();
  
  converter << splitInfo[2];
  converter >> fitVal;
  converter.str("");
  converter.clear();
  
  // Store gathered splitInfo into the node object.
  tnode->setSplitVariable(splitVar);
  tnode->setSplitValue(splitVal);
  tnode->setFitValue(fitVal);
  
  // Get the xml daughters of the current xml node. 
  XMLNodePointer_t xleft = xml->GetChild(xnode);
  XMLNodePointer_t xright = xml->GetNext(xleft);
  
  // If there are no daughters we are done.
  if(xleft == 0 || xright == 0) return;
  
  // If there are daughters link the node objects appropriately.
  tnode->theMiracleOfChildBirth();
  Node* tleft = tnode->getLeftDaughter();
  Node* tright = tnode->getRightDaughter();
  
  // Update the list of terminal nodes.
  terminalNodes.remove(tnode);
  terminalNodes.push_back(tleft);
  terminalNodes.push_back(tright);
  numTerminalNodes++;
  
  loadFromXMLRecursive(xml, xleft, tleft);
  loadFromXMLRecursive(xml, xright, tright);
}