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 = 0 );
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 = 0 );
116 void Clear ( TMVA::Node* n = 0 );
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 = 0, 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 volumde
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 (weigthed) 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
#define b(i)
Definition: RSha256.hxx:100
int Int_t
Definition: RtypesCore.h:45
unsigned int UInt_t
Definition: RtypesCore.h:46
bool Bool_t
Definition: RtypesCore.h:63
double Double_t
Definition: RtypesCore.h:59
float Float_t
Definition: RtypesCore.h:57
#define ClassDef(name, id)
Definition: Rtypes.h:325
#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.
BinarySearchTreeNode * Search(Event *event) const
search the tree to find the node matching "event"
virtual BinaryTree * CreateTree() const
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]
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"
void NormalizeTree()
Normalisation of tree.
std::vector< Double_t > fSumSq[2]
Float_t RMS(Types::ESBType sb, UInt_t var)
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]
static BinarySearchTree * CreateFromXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
re-create a new tree (decision tree or search tree) from XML
Float_t Min(Types::ESBType sb, UInt_t var)
UInt_t GetPeriode(void) const
std::vector< Double_t > fSum[2]
void Clear(TMVA::Node *n=0)
clear nodes
BinarySearchTree(void)
default constructor
void CalcStatistics(TMVA::Node *n=0)
calculate basic statistics (mean, rms for each variable)
Float_t RMS(UInt_t var)
Double_t SearchVolume(Volume *, std::vector< const TMVA::BinarySearchTreeNode * > *events=0)
search the whole tree and add up all weights of events that lie within the given volume
void Insert(const Event *)
insert a new "event" in the binary tree
std::vector< Float_t > fMin[2]
Int_t SearchVolumeWithMaxLimit(TMVA::Volume *, std::vector< const TMVA::BinarySearchTreeNode * > *events=0, Int_t=-1)
recursively walk through the daughter nodes and add up all weights of events that lie within the give...
std::vector< std::pair< Double_t, const TMVA::Event * > > fNormalizeTreeTable
void DestroyNode(BinarySearchTreeNode *)
std::vector< Float_t > fRMS[2]
Float_t Max(Types::ESBType sb, UInt_t var)
Float_t Mean(Types::ESBType sb, UInt_t var)
Base class for BinarySearch and Decision Trees.
Definition: BinaryTree.h:62
Node for the BinarySearch or Decision Trees.
Definition: Node.h:58
@ kSignal
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