Logo ROOT   6.08/07
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 #ifndef ROOT_time
44 #include "time.h"
45 #endif
46 
47 #ifndef ROOT_TMVA_Volume
48 #include "TMVA/Volume.h"
49 #endif
50 #ifndef ROOT_TMVA_BinaryTree
51 #include "TMVA/BinaryTree.h"
52 #endif
53 #ifndef ROOT_TMVA_BinarySearchTreeNode
55 #endif
56 #ifndef ROOT_TMVA_VariableInfo
57 #include "TMVA/VariableInfo.h"
58 #endif
59 
60 class TString;
61 class TTree;
62 
63 // -----------------------------------------------------------------------------
64 // the binary search tree
65 
66 namespace TMVA {
67 
68  class Event;
69  // class MethodBase;
70 
71  class BinarySearchTree : public BinaryTree {
72 
73  public:
74 
75  // constructor
76  BinarySearchTree( void );
77 
78  // copy constructor
80 
81  // destructor
82  virtual ~BinarySearchTree( void );
83 
84  virtual Node * CreateNode( UInt_t ) const { return new BinarySearchTreeNode(); }
85  virtual BinaryTree* CreateTree() const { return new BinarySearchTree(); }
86  static BinarySearchTree* CreateFromXML(void* node, UInt_t tmva_Version_Code = TMVA_VERSION_CODE);
87  virtual const char* ClassName() const { return "BinarySearchTree"; }
88 
89  // Searches for a node with the specified data
90  // by calling the private, recursive, function for searching
91  BinarySearchTreeNode* Search( Event * event ) const;
92 
93  // Adds an item to the tree,
94  void Insert( const Event * );
95 
96  // get sum of weights of the nodes;
97  Double_t GetSumOfWeights( void ) const;
98 
99  //get sum of weights of the nodes of given type;
100  Double_t GetSumOfWeights( Int_t theType ) const;
101 
102  //set the periode (number of variables)
103  void SetPeriode( Int_t p ) { fPeriod = p; }
104 
105  // return periode (number of variables)
106  UInt_t GetPeriode( void ) const { return fPeriod; }
107 
108  // counts events (weights) within a given volume
109  Double_t SearchVolume( Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = 0 );
110 
111  // Create the search tree from the event collection
112  // using ONLY the variables specified in "theVars"
113  Double_t Fill( const std::vector<TMVA::Event*>& events, const std::vector<Int_t>& theVars, Int_t theType = -1 );
114 
115  // create the search tree from the events in a TTree
116  // using ALL the variables specified included in the Event
117  Double_t Fill( const std::vector<TMVA::Event*>& events, Int_t theType = -1 );
118 
119  void NormalizeTree ();
120 
121  void CalcStatistics( TMVA::Node* n = 0 );
122  void Clear ( TMVA::Node* n = 0 );
123 
124  // access to mean for signal and background for each variable
125  Float_t Mean(Types::ESBType sb, UInt_t var ) { return fMeans[sb==Types::kSignal?0:1][var]; }
126 
127  // access to RMS for signal and background for each variable
128  Float_t RMS(Types::ESBType sb, UInt_t var ) { return fRMS[sb==Types::kSignal?0:1][var]; }
129 
130  // access to Minimum for signal and background for each variable
131  Float_t Min(Types::ESBType sb, UInt_t var ) { return fMin[sb==Types::kSignal?0:1][var]; }
132 
133  // access to Maximum for signal and background for each variable
134  Float_t Max(Types::ESBType sb, UInt_t var ) { return fMax[sb==Types::kSignal?0:1][var]; }
135 
136  Int_t SearchVolumeWithMaxLimit( TMVA::Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = 0, Int_t = -1);
137 
138  // access to RMS for each variable
139  Float_t RMS(UInt_t var ) { return fRMS[0][var]; } // attention! class 0 is taken as signal!
140 
142 
143  private:
144 
145  // add a new node to the tree (as daughter)
146  void Insert( const Event*, Node* );
147  // recursively search the nodes for Event
148  BinarySearchTreeNode* Search( Event*, Node *) const ;
149 
150  //check of Event variables lie with the volumde
151  Bool_t InVolume (const std::vector<Float_t>&, Volume* ) const;
152  //
154 
155 
156  void NormalizeTree( std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator,
157  std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator, UInt_t );
158 
159  // recursive search through daughter nodes in weight counting
161  std::vector<const TMVA::BinarySearchTreeNode*>* events );
162  UInt_t fPeriod; // periode (number of event variables)
163  UInt_t fCurrentDepth; // internal variable, counting the depth of the tree during insertion
164  Bool_t fStatisticsIsValid; // flag if last stat calculation is still valid, set to false if new node is insert
165 
166  std::vector<Float_t> fMeans[2]; // mean for signal and background for each variable
167  std::vector<Float_t> fRMS[2]; // RMS for signal and background for each variable
168  std::vector<Float_t> fMin[2]; // RMS for signal and background for each variable
169  std::vector<Float_t> fMax[2]; // RMS for signal and background for each variable
170  std::vector<Double_t> fSum[2]; // Sum for signal and background for each variable
171  std::vector<Double_t> fSumSq[2]; // Squared Sum for signal and background for each variable
172  Double_t fNEventsW[2]; // Number of events per class, taking into account event weights
173  Double_t fSumOfWeights;// Total number of events (weigthed) counted during filling
174  // should be the same as fNEventsW[0]+fNEventsW[1].. used as a check
175 
176  Bool_t fCanNormalize; // the tree can be normalised
177  std::vector< std::pair<Double_t,const TMVA::Event*> > fNormalizeTreeTable;
178 
179  ClassDef(BinarySearchTree,0); // Binary search tree including volume search method
180  };
181 
182 } // namespace TMVA
183 
184 #endif
Int_t SearchVolumeWithMaxLimit(TMVA::Volume *, std::vector< const TMVA::BinarySearchTreeNode *> *events=0, Int_t=-1)
std::vector< Double_t > fSum[2]
BinarySearchTreeNode * Search(Event *event) const
search the tree to find the node matching "event"
virtual Node * CreateNode(UInt_t) const
std::vector< Float_t > fMax[2]
std::vector< Double_t > fSumSq[2]
#define TMVA_VERSION_CODE
Definition: Version.h:47
virtual ~BinarySearchTree(void)
destructor
Bool_t InVolume(const std::vector< Float_t > &, Volume *) const
virtual BinaryTree * CreateTree() const
float Float_t
Definition: RtypesCore.h:53
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" ...
Basic string class.
Definition: TString.h:137
int Int_t
Definition: RtypesCore.h:41
bool Bool_t
Definition: RtypesCore.h:59
Double_t GetSumOfWeights(void) const
return the sum of event (node) weights
UInt_t GetPeriode(void) const
void NormalizeTree()
Normalisation of tree.
std::vector< std::pair< Double_t, const TMVA::Event * > > fNormalizeTreeTable
#define ClassDef(name, id)
Definition: Rtypes.h:254
void Clear(TMVA::Node *n=0)
clear nodes
void CalcStatistics(TMVA::Node *n=0)
calculate basic statistics (mean, rms for each variable)
Float_t RMS(UInt_t var)
BinarySearchTree(void)
default constructor
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 Max(Types::ESBType sb, UInt_t var)
Float_t Min(Types::ESBType sb, UInt_t var)
unsigned int UInt_t
Definition: RtypesCore.h:42
void SetNormalize(Bool_t norm)
void Insert(const Event *)
insert a new "event" in the binary tree
double Double_t
Definition: RtypesCore.h:55
Float_t RMS(Types::ESBType sb, UInt_t var)
std::vector< Float_t > fMeans[2]
Float_t Mean(Types::ESBType sb, UInt_t var)
Abstract ClassifierFactory template that handles arbitrary types.
void DestroyNode(BinarySearchTreeNode *)
virtual const char * ClassName() const
you should not use this method at all Int_t Int_t Double_t Double_t Double_t Int_t Double_t Double_t Double_t Double_t b
Definition: TRolke.cxx:630
A TTree object has a header with a name and a title.
Definition: TTree.h:98
std::vector< Float_t > fMin[2]
Double_t SearchVolume(Volume *, std::vector< const TMVA::BinarySearchTreeNode *> *events=0)
search the whole tree and add up all weigths of events that lie within the given voluem ...
std::vector< Float_t > fRMS[2]
double norm(double *x, double *p)
Definition: unuranDistr.cxx:40
const Int_t n
Definition: legend1.C:16