Logo ROOT   6.18/05
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
52class TString;
53class TTree;
54
55// -----------------------------------------------------------------------------
56// the binary search tree
57
58namespace TMVA {
59
60 class Event;
61 // class MethodBase;
62
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
133 void SetNormalize( Bool_t norm ) { fCanNormalize = norm; }
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
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
#define b(i)
Definition: RSha256.hxx:100
int Int_t
Definition: RtypesCore.h:41
unsigned int UInt_t
Definition: RtypesCore.h:42
bool Bool_t
Definition: RtypesCore.h:59
double Double_t
Definition: RtypesCore.h:55
float Float_t
Definition: RtypesCore.h:53
#define ClassDef(name, id)
Definition: Rtypes.h:326
#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:56
@ kSignal
Definition: Types.h:136
Volume for BinarySearchTree.
Definition: Volume.h:48
Basic string class.
Definition: TString.h:131
A TTree represents a columnar dataset.
Definition: TTree.h:71
const Int_t n
Definition: legend1.C:16
create variable transformations