Logo ROOT  
Reference Guide
BinarySearchTree.h
Go to the documentation of this file.
1// @(#)root/tmva $Id$
2// Author: Andreas Hoecker, Joerg Stelzer, Helge Voss, Kai Voss
3
4/**********************************************************************************
5 * Project: TMVA - a Root-integrated toolkit for multivariate data analysis *
6 * Package: TMVA *
7 * Class : BinarySearchTree *
8 * Web : http://tmva.sourceforge.net *
9 * *
10 * Description: *
11 * BinarySearchTree incl. volume Search method *
12 * *
13 * Authors (alphabetical): *
14 * Andreas Hoecker <Andreas.Hocker@cern.ch> - CERN, Switzerland *
15 * Joerg Stelzer <Joerg.Stelzer@cern.ch> - CERN, Switzerland *
16 * Helge Voss <Helge.Voss@cern.ch> - MPI-K Heidelberg, Germany *
17 * Kai Voss <Kai.Voss@cern.ch> - U. of Victoria, Canada *
18 * *
19 * Copyright (c) 2005: *
20 * CERN, Switzerland *
21 * U. of Victoria, Canada *
22 * MPI-K Heidelberg, Germany *
23 * LAPP, Annecy, France *
24 * *
25 * Redistribution and use in source and binary forms, with or without *
26 * modification, are permitted according to the terms listed in LICENSE *
27 * (http://tmva.sourceforge.net/LICENSE) *
28 **********************************************************************************/
29
30#ifndef ROOT_TMVA_BinarySearchTree
31#define ROOT_TMVA_BinarySearchTree
32
33//////////////////////////////////////////////////////////////////////////
34// //
35// BinarySearchTree //
36// //
37// A simple Binary search tree including volume search method //
38// //
39//////////////////////////////////////////////////////////////////////////
40
41#include <vector>
42#include <queue>
43#include <utility>
44
45#ifndef ROOT_time
46#include "time.h"
47#endif
48
49#include "TMVA/Volume.h"
50#include "TMVA/BinaryTree.h"
52#include "TMVA/VariableInfo.h"
53
54class TString;
55class TTree;
56
57// -----------------------------------------------------------------------------
58// the binary search tree
59
60namespace TMVA {
61
62 class Event;
63 // class MethodBase;
64
66
67 public:
68
69 // constructor
70 BinarySearchTree( void );
71
72 // copy constructor
74
75 // destructor
76 virtual ~BinarySearchTree( void );
77
78 virtual Node * CreateNode( UInt_t ) const { return new BinarySearchTreeNode(); }
79 virtual BinaryTree* CreateTree() const { return new BinarySearchTree(); }
80 static BinarySearchTree* CreateFromXML(void* node, UInt_t tmva_Version_Code = TMVA_VERSION_CODE);
81 virtual const char* ClassName() const { return "BinarySearchTree"; }
82
83 // Searches for a node with the specified data
84 // by calling the private, recursive, function for searching
86
87 // Adds an item to the tree,
88 void Insert( const Event * );
89
90 // get sum of weights of the nodes;
91 Double_t GetSumOfWeights( void ) const;
92
93 //get sum of weights of the nodes of given type;
94 Double_t GetSumOfWeights( Int_t theType ) const;
95
96 //set the periode (number of variables)
97 void SetPeriode( Int_t p ) { fPeriod = p; }
98
99 // return periode (number of variables)
100 UInt_t GetPeriode( void ) const { return fPeriod; }
101
102 // counts events (weights) within a given volume
103 Double_t SearchVolume( Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = nullptr );
104
105 // Create the search tree from the event collection
106 // using ONLY the variables specified in "theVars"
107 Double_t Fill( const std::vector<TMVA::Event*>& events, const std::vector<Int_t>& theVars, Int_t theType = -1 );
108
109 // create the search tree from the events in a TTree
110 // using ALL the variables specified included in the Event
111 Double_t Fill( const std::vector<TMVA::Event*>& events, Int_t theType = -1 );
112
113 void NormalizeTree ();
114
115 void CalcStatistics( TMVA::Node* n = nullptr );
116 void Clear ( TMVA::Node* n = nullptr );
117
118 /// access to mean for signal and background for each variable
119 Float_t Mean(Types::ESBType sb, UInt_t var ) { return fMeans[sb==Types::kSignal?0:1][var]; }
120
121 /// access to RMS for signal and background for each variable
122 Float_t RMS(Types::ESBType sb, UInt_t var ) { return fRMS[sb==Types::kSignal?0:1][var]; }
123
124 /// access to Minimum for signal and background for each variable
125 Float_t Min(Types::ESBType sb, UInt_t var ) { return fMin[sb==Types::kSignal?0:1][var]; }
126
127 /// access to Maximum for signal and background for each variable
128 Float_t Max(Types::ESBType sb, UInt_t var ) { return fMax[sb==Types::kSignal?0:1][var]; }
129
130 Int_t SearchVolumeWithMaxLimit( TMVA::Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = nullptr, Int_t = -1);
131
132 /// access to RMS for each variable
133 Float_t RMS(UInt_t var ) { return fRMS[0][var]; } // attention! class 0 is taken as signal!
134
135 void SetNormalize( Bool_t norm ) { fCanNormalize = norm; }
136
137 private:
138
139 // add a new node to the tree (as daughter)
140 void Insert( const Event*, Node* );
141 // recursively search the nodes for Event
143
144 //check of Event variables lie with the volume
145 Bool_t InVolume (const std::vector<Float_t>&, Volume* ) const;
146 //
148
149
150 void NormalizeTree( std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator,
151 std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator, UInt_t );
152
153 // recursive search through daughter nodes in weight counting
155 std::vector<const TMVA::BinarySearchTreeNode*>* events );
156 UInt_t fPeriod; ///< periode (number of event variables)
157 UInt_t fCurrentDepth; ///< internal variable, counting the depth of the tree during insertion
158 Bool_t fStatisticsIsValid; ///< flag if last stat calculation is still valid, set to false if new node is insert
159
160 std::vector<Float_t> fMeans[2]; ///< mean for signal and background for each variable
161 std::vector<Float_t> fRMS[2]; ///< RMS for signal and background for each variable
162 std::vector<Float_t> fMin[2]; ///< RMS for signal and background for each variable
163 std::vector<Float_t> fMax[2]; ///< RMS for signal and background for each variable
164 std::vector<Double_t> fSum[2]; ///< Sum for signal and background for each variable
165 std::vector<Double_t> fSumSq[2]; ///< Squared Sum for signal and background for each variable
166 Double_t fNEventsW[2]; ///< Number of events per class, taking into account event weights
167 Double_t fSumOfWeights;///< Total number of events (weighted) counted during filling
168 ///< should be the same as fNEventsW[0]+fNEventsW[1].. used as a check
169
170 Bool_t fCanNormalize; ///< the tree can be normalised
171 std::vector< std::pair<Double_t,const TMVA::Event*> > fNormalizeTreeTable;
172
173 ClassDef(BinarySearchTree,0); // Binary search tree including volume search method
174 };
175
176} // namespace TMVA
177
178#endif
bool Bool_t
Definition: RtypesCore.h:63
unsigned int UInt_t
Definition: RtypesCore.h:46
float Float_t
Definition: RtypesCore.h:57
double Double_t
Definition: RtypesCore.h:59
#define ClassDef(name, id)
Definition: Rtypes.h:335
winID h TVirtualViewer3D TVirtualGLPainter p
Option_t Option_t TPoint TPoint const char GetTextMagnitude GetFillStyle GetLineColor GetLineWidth GetMarkerStyle GetTextAlign GetTextColor GetTextSize void char Point_t Rectangle_t WindowAttributes_t Float_t Float_t Float_t b
#define TMVA_VERSION_CODE
Definition: Version.h:47
Node for the BinarySearch or Decision Trees.
A simple Binary search tree including a volume search method.
Int_t SearchVolumeWithMaxLimit(TMVA::Volume *, std::vector< const TMVA::BinarySearchTreeNode * > *events=nullptr, Int_t=-1)
recursively walk through the daughter nodes and add up all weights of events that lie within the give...
BinarySearchTreeNode * Search(Event *event) const
search the tree to find the node matching "event"
virtual BinaryTree * CreateTree() const
Double_t SearchVolume(Volume *, std::vector< const TMVA::BinarySearchTreeNode * > *events=nullptr)
search the whole tree and add up all weights of events that lie within the given volume
void CalcStatistics(TMVA::Node *n=nullptr)
calculate basic statistics (mean, rms for each variable)
UInt_t fCurrentDepth
internal variable, counting the depth of the tree during insertion
void Clear(TMVA::Node *n=nullptr)
clear nodes
void SetNormalize(Bool_t norm)
Bool_t InVolume(const std::vector< Float_t > &, Volume *) const
test if the data points are in the given volume
std::vector< Float_t > fMax[2]
RMS for signal and background for each variable.
virtual ~BinarySearchTree(void)
destructor
Double_t Fill(const std::vector< TMVA::Event * > &events, const std::vector< Int_t > &theVars, Int_t theType=-1)
create the search tree from the event collection using ONLY the variables specified in "theVars"
Double_t fNEventsW[2]
Number of events per class, taking into account event weights.
void NormalizeTree()
Normalisation of tree.
std::vector< Double_t > fSumSq[2]
Squared Sum for signal and background for each variable.
Float_t RMS(Types::ESBType sb, UInt_t var)
access to RMS for signal and background for each variable
virtual const char * ClassName() const
Double_t GetSumOfWeights(void) const
return the sum of event (node) weights
virtual Node * CreateNode(UInt_t) const
std::vector< Float_t > fMeans[2]
mean for signal and background for each variable
UInt_t fPeriod
periode (number of event variables)
Bool_t fCanNormalize
the tree can be normalised
Double_t fSumOfWeights
Total number of events (weighted) counted during filling should be the same as fNEventsW[0]+fNEventsW...
Float_t Min(Types::ESBType sb, UInt_t var)
access to Minimum for signal and background for each variable
UInt_t GetPeriode(void) const
std::vector< Double_t > fSum[2]
Sum for signal and background for each variable.
BinarySearchTree(void)
default constructor
Bool_t fStatisticsIsValid
flag if last stat calculation is still valid, set to false if new node is insert
Float_t RMS(UInt_t var)
access to RMS for each variable
void Insert(const Event *)
insert a new "event" in the binary tree
std::vector< Float_t > fMin[2]
RMS for signal and background for each variable.
std::vector< std::pair< Double_t, const TMVA::Event * > > fNormalizeTreeTable
void DestroyNode(BinarySearchTreeNode *)
std::vector< Float_t > fRMS[2]
RMS for signal and background for each variable.
Float_t Max(Types::ESBType sb, UInt_t var)
access to Maximum for signal and background for each variable
static BinarySearchTree * CreateFromXML(void *node, UInt_t tmva_Version_Code=262657)
re-create a new tree (decision tree or search tree) from XML
Float_t Mean(Types::ESBType sb, UInt_t var)
access to mean for signal and background for each variable
Base class for BinarySearch and Decision Trees.
Definition: BinaryTree.h:62
Node for the BinarySearch or Decision Trees.
Definition: Node.h:58
@ kSignal
Never change this number - it is elsewhere assumed to be zero !
Definition: Types.h:135
Volume for BinarySearchTree.
Definition: Volume.h:47
Basic string class.
Definition: TString.h:136
A TTree represents a columnar dataset.
Definition: TTree.h:79
const Int_t n
Definition: legend1.C:16
create variable transformations