Logo ROOT   6.30.04
Reference Guide
 All Namespaces Files Pages
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"
49 #include "TMVA/BinarySearchTreeNode.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
71  BinarySearchTree (const BinarySearchTree &b);
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
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  //
145  void DestroyNode ( BinarySearchTreeNode* );
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
152  Double_t SearchVolume( Node*, Volume*, Int_t,
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