#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 17 of file Tree.h.

Constructor & Destructor Documentation

Tree::Tree ( )

Definition at line 26 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 34 of file Tree.cc.

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

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

Tree::~Tree ( )

Definition at line 47 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 321 of file Tree.cc.

References Node::getFitValue(), Node::getSplitValue(), 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 107 of file Tree.cc.

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

Referenced by Forest::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 91 of file Tree.cc.

References 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 202 of file Tree.cc.

References filterEventRecursive(), and rootNode.

Referenced by Forest::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 214 of file Tree.cc.

References 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 168 of file Tree.cc.

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

Referenced by Forest::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 184 of file Tree.cc.

References Node::filterEventsToDaughters(), Node::getLeftDaughter(), and 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 82 of file Tree.cc.

References numTerminalNodes.

 {
     return numTerminalNodes;
 }

Node * Tree::getRootNode ( )

Definition at line 63 of file Tree.cc.

References rootNode.

 {
      return rootNode;
 }

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

Definition at line 300 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 270 of file Tree.cc.

References gather_cfg::cout, Node::getLeftDaughter(), Node::getRightDaughter(), Node::getSplitValue(), 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 75 of file Tree.cc.

References terminalNodes.

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

 {
     return terminalNodes;
 }

void Tree::loadFromXML ( const char * filename )

Definition at line 380 of file Tree.cc.

References loadFromXMLRecursive(), rootNode, and ExtractAppInfoFromXML::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 406 of file Tree.cc.

References Node::getLeftDaughter(), Node::getRightDaughter(), i, numTerminalNodes, Node::setFitValue(), Node::setSplitValue(), Node::setSplitVariable(), terminalNodes, and 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 262 of file Tree.cc.

References rankVariablesRecursive(), and rootNode.

 {
     rankVariablesRecursive(rootNode, v);
 }

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

Definition at line 229 of file Tree.cc.

References Node::getErrorReduction(), Node::getLeftDaughter(), Node::getRightDaughter(), and 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 332 of file Tree.cc.

References addXMLAttributes(), Node::getName(), pyrootRender::root, rootNode, saveToXMLRecursive(), and ExtractAppInfoFromXML::xmldoc.

Referenced by Forest::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 358 of file Tree.cc.

References addXMLAttributes(), Node::getLeftDaughter(), Node::getRightDaughter(), cmsLHEtoEOSManager::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);
 }