#include <Tree.h>

Public Member Functions
void	addXMLAttributes (TXMLEngine xml, Node node, XMLNodePointer_t np)

void	buildTree (Int_t nodeLimit)

void	calcError ()

Node *	filterEvent (Event *e)

Node *	filterEventRecursive (Node node, Event e)

void	filterEvents (std::vector< Event * > &tEvents)

void	filterEventsRecursive (Node *node)

Int_t	getNumTerminalNodes ()

Node *	getRootNode ()

void	getSplitValues (std::vector< std::vector< Double_t >> &v)

void	getSplitValuesRecursive (Node *node, std::vector< std::vector< Double_t >> &v)

std::list< Node * > &	getTerminalNodes ()

void	loadFromXML (const char *filename)

void	loadFromXMLRecursive (TXMLEngine xml, XMLNodePointer_t node, Node tnode)

void	rankVariables (std::vector< Double_t > &v)

void	rankVariablesRecursive (Node *node, std::vector< Double_t > &v)

void	saveToXML (const char *filename)

void	saveToXMLRecursive (TXMLEngine xml, Node node, XMLNodePointer_t np)

void	setRootNode (Node *sRootNode)

void	setTerminalNodes (std::list< Node * > &sTNodes)

	Tree ()

	Tree (std::vector< std::vector< Event * > > &cEvents)

	~Tree ()

Private Attributes
Int_t	numTerminalNodes

Double_t	rmsError

Node *	rootNode

std::list< Node * >	terminalNodes

Detailed Description

Definition at line 18 of file Tree.h.

Constructor & Destructor Documentation

Tree::Tree ( )

Definition at line 28 of file Tree.cc.

References numTerminalNodes, rootNode, and terminalNodes.

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

Tree::Tree ( std::vector< std::vector< Event * > > & cEvents )

Definition at line 36 of file Tree.cc.

References numTerminalNodes, rootNode, emtf::Node::setEvents(), and terminalNodes.

 {
   rootNode = new Node("root");
   rootNode->setEvents(cEvents);
   
   terminalNodes.push_back(rootNode);
   numTerminalNodes = 1;
 }

Tree::~Tree ( )

Definition at line 48 of file Tree.cc.

References rootNode.

 {
   // 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;
 }

Member Function Documentation

void Tree::addXMLAttributes	(	TXMLEngine *	xml,
		Node *	node,
		XMLNodePointer_t	np
	)

Definition at line 322 of file Tree.cc.

References emtf::Node::getFitValue(), emtf::Node::getSplitValue(), emtf::Node::getSplitVariable(), and numToStr().

Referenced by saveToXML(), and saveToXMLRecursive().

 {
   // 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::buildTree ( Int_t nodeLimit )

Definition at line 108 of file Tree.cc.

References calcError(), emtf::Node::calcOptimumSplit(), emtf::Node::filterEventsToDaughters(), emtf::Node::getLeftDaughter(), emtf::Node::getRightDaughter(), numTerminalNodes, rootNode, terminalNodes, and emtf::Node::theMiracleOfChildBirth().

Referenced by L1TForest::doRegression().

 {
   // 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::calcError ( )

Definition at line 92 of file Tree.cc.

References emtf::Node::getNumEvents(), rmsError, rootNode, mathSSE::sqrt(), and terminalNodes.

Referenced by buildTree().

 { 
   // 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() ); 
 } 

Node * Tree::filterEvent ( Event * e )

Definition at line 203 of file Tree.cc.

References filterEventRecursive(), and rootNode.

Referenced by L1TForest::appendCorrection().

 {
   // 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
	)

Definition at line 215 of file Tree.cc.

References emtf::Node::filterEventToDaughter().

Referenced by filterEvent().

 {
   // 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::filterEvents ( std::vector< Event * > & tEvents )

Definition at line 169 of file Tree.cc.

References filterEventsRecursive(), emtf::Node::getEvents(), and rootNode.

Referenced by L1TForest::appendCorrection().

 {
   // 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 )

Definition at line 185 of file Tree.cc.

References emtf::Node::filterEventsToDaughters(), emtf::Node::getLeftDaughter(), and emtf::Node::getRightDaughter().

Referenced by filterEvents().

 {
   // 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);
 }

Int_t Tree::getNumTerminalNodes ( )

Definition at line 83 of file Tree.cc.

References numTerminalNodes.

 {
   return numTerminalNodes;
 }

Node * Tree::getRootNode ( )

Definition at line 64 of file Tree.cc.

References rootNode.

 {
   return rootNode;
 }

void Tree::getSplitValues ( std::vector< std::vector< Double_t >> & v )

Definition at line 301 of file Tree.cc.

References getSplitValuesRecursive(), rootNode, and findQualityFiles::v.

 {
   getSplitValuesRecursive(rootNode, v);
 }

void Tree::getSplitValuesRecursive	(	Node *	node,
		std::vector< std::vector< Double_t >> &	v
	)

Definition at line 271 of file Tree.cc.

References gather_cfg::cout, emtf::Node::getLeftDaughter(), emtf::Node::getRightDaughter(), emtf::Node::getSplitValue(), emtf::Node::getSplitVariable(), and findQualityFiles::v.

Referenced by getSplitValues().

 {
   // 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); 
   
 }

std::list< Node * > & Tree::getTerminalNodes ( )

Definition at line 76 of file Tree.cc.

References terminalNodes.

Referenced by L1TForest::updateEvents(), and L1TForest::updateRegTargets().

 {
   return terminalNodes;
 }

void Tree::loadFromXML ( const char * filename )

Definition at line 381 of file Tree.cc.

References loadFromXMLRecursive(), rootNode, and cmsPerfSuiteHarvest::xmldoc.

 {   
   // 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	node,
		Node *	tnode
	)

Definition at line 407 of file Tree.cc.

References emtf::Node::getLeftDaughter(), emtf::Node::getRightDaughter(), mps_fire::i, numTerminalNodes, emtf::Node::setFitValue(), emtf::Node::setSplitValue(), emtf::Node::setSplitVariable(), terminalNodes, and emtf::Node::theMiracleOfChildBirth().

Referenced by loadFromXML().

 {
   
   // 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);
 }

void Tree::rankVariables ( std::vector< Double_t > & v )

Definition at line 263 of file Tree.cc.

References rankVariablesRecursive(), and rootNode.

 {
   rankVariablesRecursive(rootNode, v);
 }

void Tree::rankVariablesRecursive	(	Node *	node,
		std::vector< Double_t > &	v
	)

Definition at line 230 of file Tree.cc.

References emtf::Node::getErrorReduction(), emtf::Node::getLeftDaughter(), emtf::Node::getRightDaughter(), and emtf::Node::getSplitVariable().

Referenced by rankVariables().

 {
   // 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::saveToXML ( const char * filename )

Definition at line 333 of file Tree.cc.

References addXMLAttributes(), emtf::Node::getName(), rootNode, saveToXMLRecursive(), and cmsPerfSuiteHarvest::xmldoc.

Referenced by L1TForest::doRegression().

 {
   
   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
	)

Definition at line 359 of file Tree.cc.

References addXMLAttributes(), emtf::Node::getLeftDaughter(), emtf::Node::getRightDaughter(), checklumidiff::l, and alignCSCRings::r.

Referenced by saveToXML().

 {
   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);
 }