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 
54 class TString;
55 class TTree;
56 
57 // -----------------------------------------------------------------------------
58 // the binary search tree
59 
60 namespace TMVA {
61 
62  class Event;
63  // class MethodBase;
64 
65  class BinarySearchTree : public BinaryTree {
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
85  BinarySearchTreeNode* Search( Event * event ) const;
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
142  BinarySearchTreeNode* Search( Event*, Node *) const ;
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
BinarySearchTreeNode.h
n
const Int_t n
Definition: legend1.C:16
TMVA::BinarySearchTree::Clear
void Clear(TMVA::Node *n=0)
clear nodes
Definition: BinarySearchTree.cxx:356
TMVA::BinarySearchTree::fNormalizeTreeTable
std::vector< std::pair< Double_t, const TMVA::Event * > > fNormalizeTreeTable
Definition: BinarySearchTree.h:171
TMVA::BinarySearchTree::SearchVolumeWithMaxLimit
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...
Definition: BinarySearchTree.cxx:497
TMVA::BinarySearchTree::fCanNormalize
Bool_t fCanNormalize
Definition: BinarySearchTree.h:170
TMVA::BinarySearchTree::fMin
std::vector< Float_t > fMin[2]
Definition: BinarySearchTree.h:162
TMVA::BinarySearchTree::fPeriod
UInt_t fPeriod
Definition: BinarySearchTree.h:156
TMVA::BinarySearchTree::Max
Float_t Max(Types::ESBType sb, UInt_t var)
Definition: BinarySearchTree.h:128
TMVA::BinarySearchTree::Search
BinarySearchTreeNode * Search(Event *event) const
search the tree to find the node matching "event"
Definition: BinarySearchTree.cxx:193
TMVA::BinarySearchTree::fMax
std::vector< Float_t > fMax[2]
Definition: BinarySearchTree.h:163
TMVA::BinarySearchTree::NormalizeTree
void NormalizeTree()
Normalisation of tree.
Definition: BinarySearchTree.cxx:345
TMVA::Volume
Definition: Volume.h:69
TMVA::BinarySearchTree::RMS
Float_t RMS(Types::ESBType sb, UInt_t var)
Definition: BinarySearchTree.h:122
TTree
Definition: TTree.h:79
TMVA::BinarySearchTree::CreateTree
virtual BinaryTree * CreateTree() const
Definition: BinarySearchTree.h:79
TMVA::BinarySearchTree::SetPeriode
void SetPeriode(Int_t p)
Definition: BinarySearchTree.h:97
Float_t
float Float_t
Definition: RtypesCore.h:57
VariableInfo.h
TString
Definition: TString.h:136
TMVA::Types::kSignal
@ kSignal
Definition: Types.h:159
Bool_t
bool Bool_t
Definition: RtypesCore.h:63
TMVA::BinarySearchTree::~BinarySearchTree
virtual ~BinarySearchTree(void)
destructor
Definition: BinarySearchTree.cxx:92
b
#define b(i)
Definition: RSha256.hxx:118
TMVA::Node
Definition: Node.h:80
TMVA::BinarySearchTree::CalcStatistics
void CalcStatistics(TMVA::Node *n=0)
calculate basic statistics (mean, rms for each variable)
Definition: BinarySearchTree.cxx:432
bool
TMVA::BinarySearchTree::GetPeriode
UInt_t GetPeriode(void) const
Definition: BinarySearchTree.h:100
Volume.h
TMVA::Types::ESBType
ESBType
Definition: Types.h:158
TMVA::BinarySearchTree::fRMS
std::vector< Float_t > fRMS[2]
Definition: BinarySearchTree.h:161
TMVA::BinarySearchTree::fMeans
std::vector< Float_t > fMeans[2]
Definition: BinarySearchTree.h:160
TMVA::BinarySearchTree::Mean
Float_t Mean(Types::ESBType sb, UInt_t var)
Definition: BinarySearchTree.h:119
TMVA::BinarySearchTree
Definition: BinarySearchTree.h:65
TMVA::BinarySearchTree::RMS
Float_t RMS(UInt_t var)
Definition: BinarySearchTree.h:133
TMVA::BinarySearchTree::fSumSq
std::vector< Double_t > fSumSq[2]
Definition: BinarySearchTree.h:165
TMVA::BinarySearchTree::DestroyNode
void DestroyNode(BinarySearchTreeNode *)
TMVA::BinarySearchTree::BinarySearchTree
BinarySearchTree(void)
default constructor
Definition: BinarySearchTree.cxx:63
TMVA::BinarySearchTree::SetNormalize
void SetNormalize(Bool_t norm)
Definition: BinarySearchTree.h:135
TMVA::BinaryTree
Definition: BinaryTree.h:86
TMVA::BinarySearchTree::GetSumOfWeights
Double_t GetSumOfWeights(void) const
return the sum of event (node) weights
Definition: BinarySearchTree.cxx:218
TMVA::BinarySearchTree::fCurrentDepth
UInt_t fCurrentDepth
Definition: BinarySearchTree.h:157
UInt_t
unsigned int UInt_t
Definition: RtypesCore.h:46
TMVA::BinarySearchTree::Insert
void Insert(const Event *)
insert a new "event" in the binary tree
Definition: BinarySearchTree.cxx:114
TMVA::BinarySearchTree::fSum
std::vector< Double_t > fSum[2]
Definition: BinarySearchTree.h:164
TMVA::BinarySearchTree::fStatisticsIsValid
Bool_t fStatisticsIsValid
Definition: BinarySearchTree.h:158
unsigned int
TMVA::BinarySearchTree::SearchVolume
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
Definition: BinarySearchTree.cxx:372
BinaryTree.h
Double_t
double Double_t
Definition: RtypesCore.h:59
TMVA::BinarySearchTree::fSumOfWeights
Double_t fSumOfWeights
Definition: BinarySearchTree.h:167
TMVA_VERSION_CODE
#define TMVA_VERSION_CODE
Definition: Version.h:47
TMVA::BinarySearchTree::CreateNode
virtual Node * CreateNode(UInt_t) const
Definition: BinarySearchTree.h:78
TMVA::Event
Definition: Event.h:51
ClassDef
#define ClassDef(name, id)
Definition: Rtypes.h:325
TMVA::BinarySearchTreeNode
Definition: BinarySearchTreeNode.h:78
TMVA::BinarySearchTree::fNEventsW
Double_t fNEventsW[2]
Definition: BinarySearchTree.h:166
TMVA::BinarySearchTree::ClassName
virtual const char * ClassName() const
Definition: BinarySearchTree.h:81
TMVA::BinarySearchTree::InVolume
Bool_t InVolume(const std::vector< Float_t > &, Volume *) const
test if the data points are in the given volume
Definition: BinarySearchTree.cxx:417
TMVA::BinarySearchTree::Fill
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"
Definition: BinarySearchTree.cxx:249
TMVA::BinarySearchTree::Min
Float_t Min(Types::ESBType sb, UInt_t var)
Definition: BinarySearchTree.h:125
TMVA
create variable transformations
Definition: GeneticMinimizer.h:22
int
TMVA::BinarySearchTree::CreateFromXML
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
Definition: BinarySearchTree.cxx:103