#include <Node.h>

Public Member Functions
void	calcOptimumSplit ()

void	filterEventsToDaughters ()

Node *	filterEventToDaughter (emtf::Event *e)

Double_t	getAvgError ()

Double_t	getErrorReduction ()

std::vector< std::vector< emtf::Event * > > &	getEvents ()

Double_t	getFitValue ()

Node *	getLeftDaughter ()

std::string	getName ()

Int_t	getNumEvents ()

Node *	getParent ()

Node *	getRightDaughter ()

Double_t	getSplitValue ()

Int_t	getSplitVariable ()

Double_t	getTotalError ()

void	listEvents ()

	Node ()

	Node (std::string cName)

void	setAvgError (Double_t sAvgError)

void	setErrorReduction (Double_t sErrorReduction)

void	setEvents (std::vector< std::vector< emtf::Event * > > &sEvents)

void	setFitValue (Double_t sFitValue)

void	setLeftDaughter (Node *sLeftDaughter)

void	setName (std::string sName)

void	setNumEvents (Int_t sNumEvents)

void	setParent (Node *sParent)

void	setRightDaughter (Node *sLeftDaughter)

void	setSplitValue (Double_t sSplitValue)

void	setSplitVariable (Int_t sSplitVar)

void	setTotalError (Double_t sTotalError)

void	theMiracleOfChildBirth ()

	~Node ()

Private Attributes
Double_t	avgError

Double_t	errorReduction

std::vector< std::vector< emtf::Event * > >	events

Double_t	fitValue

Node *	leftDaughter

std::string	name

Int_t	numEvents

Node *	parent

Node *	rightDaughter

Double_t	splitValue

Int_t	splitVariable

Double_t	totalError

Detailed Description

Definition at line 11 of file Node.h.

Constructor & Destructor Documentation

Node::Node ( )

Definition at line 31 of file Node.cc.

References avgError, errorReduction, leftDaughter, name, parent, rightDaughter, splitValue, splitVariable, and totalError.

Referenced by theMiracleOfChildBirth().

 {
   name = "";
   leftDaughter = 0;
   rightDaughter = 0;
   parent = 0;
   splitValue = -99;
   splitVariable = -1;
   avgError = -1;
   totalError = -1;
   errorReduction = -1;
 }

Node::Node ( std::string cName )

Definition at line 44 of file Node.cc.

References avgError, errorReduction, leftDaughter, name, parent, rightDaughter, splitValue, splitVariable, and totalError.

 {
   name = cName;
   leftDaughter = 0;
   rightDaughter = 0;
   parent = 0;
   splitValue = -99;
   splitVariable = -1;
   avgError = -1;
   totalError = -1;
   errorReduction = -1;
 }

Node::~Node ( )

Definition at line 61 of file Node.cc.

References leftDaughter, and rightDaughter.

 {
   // Recursively delete all nodes in the tree.
   delete leftDaughter;
   delete rightDaughter;
 }

Member Function Documentation

void Node::calcOptimumSplit ( )

Definition at line 213 of file Node.cc.

References avgError, data, errorReduction, events, fitValue, mps_fire::i, numEvents, splitValue, splitVariable, SUM, edmPickEvents::target, totalError, and findQualityFiles::v.

Referenced by emtf::Tree::buildTree().

 {
   // Determines the split variable and split point which would most reduce the error for the given node (region).
   // In the process we calculate the fitValue and Error. The general aglorithm is based upon  Luis Torgo's thesis.
   // Check out the reference for a more in depth outline. This part is chapter 3.
   
   // Intialize some variables.
   Double_t bestSplitValue = 0;
   Int_t bestSplitVariable = -1; 
   Double_t bestErrorReduction = -1;
   
   Double_t SUM = 0;
   Double_t SSUM = 0;
   numEvents = events[0].size();
   
   Double_t candidateErrorReduction = -1;
   
   // Calculate the sum of the target variables and the sum of
   // the target variables squared. We use these later.
   for(unsigned int i=0; i<events[0].size(); i++)
     {   
       Double_t target = events[0][i]->data[0];
       SUM += target;
       SSUM += target*target;
     }  
   
   unsigned int numVars = events.size();
   
   // Calculate the best split point for each variable
   for(unsigned int variableToCheck = 1; variableToCheck < numVars; variableToCheck++)
     { 
       
       // The sum of the target variables in the left, right nodes
       Double_t SUMleft = 0;
       Double_t SUMright = SUM;
       
       // The number of events in the left, right nodes
       Int_t nleft = 1;
       Int_t nright = events[variableToCheck].size()-1;
       
       Int_t candidateSplitVariable = variableToCheck;
       
       std::vector<Event*>& v = events[variableToCheck];
       
       // Find the best split point for this variable 
       for(unsigned int i=1; i<v.size(); i++)
         {
       // As the candidate split point interates, the number of events in the 
       // left/right node increases/decreases and SUMleft/right increases/decreases.
       
       SUMleft = SUMleft + v[i-1]->data[0];
       SUMright = SUMright - v[i-1]->data[0];
           
       // No need to check the split point if x on both sides is equal
       if(v[i-1]->data[candidateSplitVariable] < v[i]->data[candidateSplitVariable])
             {
           // Finding the maximum error reduction for Least Squares boils down to maximizing
           // the following statement.
           candidateErrorReduction = SUMleft*SUMleft/nleft + SUMright*SUMright/nright - SUM*SUM/numEvents;
           //                std::cout << "candidateErrorReduction= " << candidateErrorReduction << std::endl << std::endl;
           
           // if the new candidate is better than the current best, then we have a new overall best.
           if(candidateErrorReduction > bestErrorReduction)
                 {
           bestErrorReduction = candidateErrorReduction;
           bestSplitValue = (v[i-1]->data[candidateSplitVariable] + v[i]->data[candidateSplitVariable])/2;
           bestSplitVariable = candidateSplitVariable;
                 }
             }
       
       nright = nright-1;
       nleft = nleft+1;
         }
     }
   
   // Store the information gained from our computations.
   
   // The fit value is the average for least squares.
   fitValue = SUM/numEvents;
   //    std::cout << "fitValue= " << fitValue << std::endl;
   
   // n*[ <y^2>-k^2 ]
   totalError = SSUM - SUM*SUM/numEvents;
   //    std::cout << "totalError= " << totalError << std::endl;
   
   // [ <y^2>-k^2 ]
   avgError = totalError/numEvents;
   //    std::cout << "avgError= " << avgError << std::endl;
   
   
   errorReduction = bestErrorReduction;
   //    std::cout << "errorReduction= " << errorReduction << std::endl;
   
   splitVariable = bestSplitVariable;
   //    std::cout << "splitVariable= " << splitVariable << std::endl;
   
   splitValue = bestSplitValue;
   //    std::cout << "splitValue= " << splitValue << std::endl;
   
   //if(bestSplitVariable == -1) std::cout << "splitVar = -1. numEvents = " << numEvents << ". errRed = " << errorReduction << std::endl;
 }

void Node::filterEventsToDaughters ( )

Definition at line 349 of file Node.cc.

References emtf::Event::data, MillePedeFileConverter_cfg::e, events, getEvents(), mps_fire::i, checklumidiff::l, leftDaughter, alignCSCRings::r, rightDaughter, setNumEvents(), splitValue, and splitVariable.

Referenced by emtf::Tree::buildTree(), and emtf::Tree::filterEventsRecursive().

 {
   // Keeping sorted copies of the event vectors allows us to save on
   // computation time. That way we don't have to resort the events
   // each time we calculate the splitpoint for a node. We sort them once.
   // Every time we split a node, we simply filter them down correctly
   // preserving the order. This way we have O(n) efficiency instead
   // of O(nlogn) efficiency.
   
   // Anyways, this function takes events from the parent node
   // and filters an event into the left or right daughter
   // node depending on whether it is < or > the split point
   // for the given split variable. 
   
   Int_t sv = splitVariable;
   Double_t sp = splitValue;
   
   Node* left = leftDaughter;
   Node* right = rightDaughter;
   
   std::vector< std::vector<Event*> > l(events.size());
   std::vector< std::vector<Event*> > r(events.size());
   
   for(unsigned int i=0; i<events.size(); i++)
     {
       for(unsigned int j=0; j<events[i].size(); j++)
         {
       Event* e = events[i][j];
       if(e->data[sv] < sp) l[i].push_back(e);
       if(e->data[sv] > sp) r[i].push_back(e);
         }
     }
   
   events = std::vector< std::vector<Event*> >();    
   
   left->getEvents().swap(l);
   right->getEvents().swap(r);    
   
   // Set the number of events in the node.
   left->setNumEvents(left->getEvents()[0].size());
   right->setNumEvents(right->getEvents()[0].size());
 }

Node * Node::filterEventToDaughter ( emtf::Event * e )

Definition at line 394 of file Node.cc.

References emtf::Event::data, leftDaughter, rightDaughter, splitValue, and splitVariable.

Referenced by emtf::Tree::filterEventRecursive().

 {
   // Anyways, this function takes an event from the parent node
   // and filters an event into the left or right daughter
   // node depending on whether it is < or > the split point
   // for the given split variable. 
   
   Int_t sv = splitVariable;
   Double_t sp = splitValue;
   
   Node* left = leftDaughter;
   Node* right = rightDaughter;
   Node* nextNode = 0;
   
   if(left ==0 || right ==0) return 0;
   
   if(e->data[sv] < sp) nextNode = left;
   if(e->data[sv] > sp) nextNode = right;
   
   return nextNode;
 }

Double_t Node::getAvgError ( )

Definition at line 179 of file Node.cc.

References avgError.

 {
   return avgError;
 }

Double_t Node::getErrorReduction ( )

Definition at line 89 of file Node.cc.

References errorReduction.

Referenced by emtf::Tree::rankVariablesRecursive().

 {
   return errorReduction;
 }

std::vector< std::vector< Event * > > & Node::getEvents ( )

Definition at line 198 of file Node.cc.

References events.

Referenced by emtf::Tree::filterEvents(), and filterEventsToDaughters().

 {
   return events;
 }

Double_t Node::getFitValue ( )

Definition at line 157 of file Node.cc.

References fitValue.

Referenced by emtf::Tree::addXMLAttributes(), and L1TForest::appendCorrection().

 {
   return fitValue;
 }

Node * Node::getLeftDaughter ( )

Definition at line 101 of file Node.cc.

References leftDaughter.

Referenced by emtf::Tree::buildTree(), emtf::Tree::filterEventsRecursive(), emtf::Tree::getSplitValuesRecursive(), emtf::Tree::loadFromXMLRecursive(), emtf::Tree::rankVariablesRecursive(), and emtf::Tree::saveToXMLRecursive().

 {
   return leftDaughter;
 }

std::string Node::getName ( void )

Definition at line 77 of file Node.cc.

References name.

Referenced by plotting.Plot::draw(), and emtf::Tree::saveToXML().

 {
   return name;
 }

Int_t Node::getNumEvents ( )

Definition at line 191 of file Node.cc.

References numEvents.

Referenced by emtf::Tree::calcError().

 {
   return numEvents;
 }

Node * Node::getParent ( )

Definition at line 123 of file Node.cc.

References parent.

 {
   return parent;
 }

Node * Node::getRightDaughter ( )

Definition at line 111 of file Node.cc.

References rightDaughter.

Referenced by emtf::Tree::buildTree(), emtf::Tree::filterEventsRecursive(), emtf::Tree::getSplitValuesRecursive(), emtf::Tree::loadFromXMLRecursive(), emtf::Tree::rankVariablesRecursive(), and emtf::Tree::saveToXMLRecursive().

 {
   return rightDaughter;
 }

Double_t Node::getSplitValue ( )

Definition at line 135 of file Node.cc.

References splitValue.

Referenced by emtf::Tree::addXMLAttributes(), and emtf::Tree::getSplitValuesRecursive().

 {
   return splitValue;
 }

Int_t Node::getSplitVariable ( )

Definition at line 145 of file Node.cc.

References splitVariable.

Referenced by emtf::Tree::addXMLAttributes(), emtf::Tree::getSplitValuesRecursive(), and emtf::Tree::rankVariablesRecursive().

 {
   return splitVariable;
 }

Double_t Node::getTotalError ( )

Definition at line 169 of file Node.cc.

References totalError.

 {
   return totalError;
 }

void Node::listEvents ( )

Definition at line 317 of file Node.cc.

References gather_cfg::cout, events, and mps_fire::i.

 {
   std::cout << std::endl << "Listing Events... " << std::endl;
   
   for(unsigned int i=0; i < events.size(); i++)
     {   
       std::cout << std::endl << "Variable " << i << " vector contents: " << std::endl;
       for(unsigned int j=0; j < events[i].size(); j++)
         {   
       events[i][j]->outputEvent();
         }   
       std::cout << std::endl;
     }   
 }

void Node::setAvgError ( Double_t sAvgError )

Definition at line 174 of file Node.cc.

References avgError.

 {
   avgError = sAvgError;
 }

void Node::setErrorReduction ( Double_t sErrorReduction )

Definition at line 84 of file Node.cc.

References errorReduction.

 {
   errorReduction = sErrorReduction;
 }

void Node::setEvents ( std::vector< std::vector< emtf::Event * > > & sEvents )

Definition at line 203 of file Node.cc.

References events, and numEvents.

Referenced by emtf::Tree::Tree().

 {
   events = sEvents;
   numEvents = events[0].size();
 }

void Node::setFitValue ( Double_t sFitValue )

Definition at line 152 of file Node.cc.

References fitValue.

Referenced by emtf::Tree::loadFromXMLRecursive().

 {
   fitValue = sFitValue;
 }

void Node::setLeftDaughter ( Node * sLeftDaughter )

Definition at line 96 of file Node.cc.

References leftDaughter.

 {
   leftDaughter = sLeftDaughter;
 }

void Node::setName ( std::string sName )

Definition at line 72 of file Node.cc.

References name.

 {
   name = sName;
 }

void Node::setNumEvents ( Int_t sNumEvents )

Definition at line 186 of file Node.cc.

References numEvents.

Referenced by filterEventsToDaughters().

 {
   numEvents = sNumEvents;
 }

void Node::setParent ( Node * sParent )

Definition at line 118 of file Node.cc.

References parent.

Referenced by lumiQTWidget.LumiCanvas::__init__(), and theMiracleOfChildBirth().

 {
   parent = sParent;
 }

void Node::setRightDaughter ( Node * sLeftDaughter )

Definition at line 106 of file Node.cc.

References rightDaughter.

 {
   rightDaughter = sRightDaughter;
 }

void Node::setSplitValue ( Double_t sSplitValue )

Definition at line 130 of file Node.cc.

References splitValue.

Referenced by emtf::Tree::loadFromXMLRecursive().

 {
   splitValue = sSplitValue;
 }

void Node::setSplitVariable ( Int_t sSplitVar )

Definition at line 140 of file Node.cc.

References splitVariable.

Referenced by emtf::Tree::loadFromXMLRecursive().

 {
   splitVariable = sSplitVar;
 }

void Node::setTotalError ( Double_t sTotalError )

Definition at line 164 of file Node.cc.

References totalError.

 {
   totalError = sTotalError;
 }

void Node::theMiracleOfChildBirth ( )

Definition at line 334 of file Node.cc.

References leftDaughter, name, Node(), rightDaughter, and setParent().

Referenced by emtf::Tree::buildTree(), and emtf::Tree::loadFromXMLRecursive().

 { 
   // Create Daughter Nodes 
   Node* left = new Node(name + " left");
   Node* right = new Node(name + " right");
   
   // Link the Nodes Appropriately
   leftDaughter = left;
   rightDaughter = right;
   left->setParent(this);
   right->setParent(this); 
 }