#include <Node.h>

Public Member Functions
void	calcOptimumSplit ()

void	filterEventsToDaughters ()

Node *	filterEventToDaughter (Event *e)

Double_t	getAvgError ()

Double_t	getErrorReduction ()

std::vector< std::vector < 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< 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 < 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 10 of file Node.h.

Constructor & Destructor Documentation

Node::Node ( )

Definition at line 29 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 42 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 59 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 211 of file Node.cc.

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

Referenced by 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 347 of file Node.cc.

References Event::data, alignCSCRings::e, events, getEvents(), i, j, cmsLHEtoEOSManager::l, leftDaughter, alignCSCRings::r, rightDaughter, setNumEvents(), splitValue, and splitVariable.

Referenced by Tree::buildTree(), and 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 ( Event * e )

Definition at line 392 of file Node.cc.

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

Referenced by 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 177 of file Node.cc.

References avgError.

 {
     return avgError;
 }

Double_t Node::getErrorReduction ( )

Definition at line 87 of file Node.cc.

References errorReduction.

Referenced by Tree::rankVariablesRecursive().

 {
     return errorReduction;
 }

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

Definition at line 196 of file Node.cc.

References events.

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

 {
     return events;
 }

Double_t Node::getFitValue ( )

Definition at line 155 of file Node.cc.

References fitValue.

Referenced by Tree::addXMLAttributes(), and Forest::appendCorrection().

 {
     return fitValue;
 }

Node * Node::getLeftDaughter ( )

Definition at line 99 of file Node.cc.

References leftDaughter.

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

 {
     return leftDaughter;
 }

std::string Node::getName ( void )

Definition at line 75 of file Node.cc.

References name.

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

 {
     return name;
 }

Int_t Node::getNumEvents ( )

Definition at line 189 of file Node.cc.

References numEvents.

Referenced by Tree::calcError().

 {
     return numEvents;
 }

Node * Node::getParent ( )

Definition at line 121 of file Node.cc.

References parent.

 {
     return parent;
 }

Node * Node::getRightDaughter ( )

Definition at line 109 of file Node.cc.

References rightDaughter.

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

 {
     return rightDaughter;
 }

Double_t Node::getSplitValue ( )

Definition at line 133 of file Node.cc.

References splitValue.

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

 {
     return splitValue;
 }

Int_t Node::getSplitVariable ( )

Definition at line 143 of file Node.cc.

References splitVariable.

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

 {
     return splitVariable;
 }

Double_t Node::getTotalError ( )

Definition at line 167 of file Node.cc.

References totalError.

 {
     return totalError;
 }

void Node::listEvents ( )

Definition at line 315 of file Node.cc.

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

 {
     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 172 of file Node.cc.

References avgError.

 {
     avgError = sAvgError;
 }

void Node::setErrorReduction ( Double_t sErrorReduction )

Definition at line 82 of file Node.cc.

References errorReduction.

 {
     errorReduction = sErrorReduction;
 }

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

Definition at line 201 of file Node.cc.

References events, and numEvents.

Referenced by Tree::Tree().

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

void Node::setFitValue ( Double_t sFitValue )

Definition at line 150 of file Node.cc.

References fitValue.

Referenced by Tree::loadFromXMLRecursive().

 {
     fitValue = sFitValue;
 }

void Node::setLeftDaughter ( Node * sLeftDaughter )

Definition at line 94 of file Node.cc.

References leftDaughter.

 {
     leftDaughter = sLeftDaughter;
 }

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

Definition at line 70 of file Node.cc.

References name.

 {
     name = sName;
 }

void Node::setNumEvents ( Int_t sNumEvents )

Definition at line 184 of file Node.cc.

References numEvents.

Referenced by filterEventsToDaughters().

 {
     numEvents = sNumEvents;
 }

void Node::setParent ( Node * sParent )

Definition at line 116 of file Node.cc.

References parent.

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

 {
     parent = sParent;
 }

void Node::setRightDaughter ( Node * sLeftDaughter )

Definition at line 104 of file Node.cc.

References rightDaughter.

 {
     rightDaughter = sRightDaughter;
 }

void Node::setSplitValue ( Double_t sSplitValue )

Definition at line 128 of file Node.cc.

References splitValue.

Referenced by Tree::loadFromXMLRecursive().

 {
     splitValue = sSplitValue;
 }

void Node::setSplitVariable ( Int_t sSplitVar )

Definition at line 138 of file Node.cc.

References splitVariable.

Referenced by Tree::loadFromXMLRecursive().

 {
     splitVariable = sSplitVar;
 }

void Node::setTotalError ( Double_t sTotalError )

Definition at line 162 of file Node.cc.

References totalError.

 {
     totalError = sTotalError;
 }

void Node::theMiracleOfChildBirth ( )

Definition at line 332 of file Node.cc.

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

Referenced by Tree::buildTree(), and 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); 
 }