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