root/TMVA/BinarySearchTree.h

0001 // @(#)root/tmva $Id$
0002 // Author: Andreas Hoecker, Joerg Stelzer, Helge Voss, Kai Voss
0003
0004 /**********************************************************************************
0005  * Project: TMVA - a Root-integrated toolkit for multivariate data analysis       *
0006  * Package: TMVA                                                                  *
0007  * Class  : BinarySearchTree                                                      *
0008  *                                             *
0009  *                                                                                *
0010  * Description:                                                                   *
0011  *      BinarySearchTree incl. volume Search method                               *
0012  *                                                                                *
0013  * Authors (alphabetical):                                                        *
0014  *      Andreas Hoecker <Andreas.Hocker@cern.ch> - CERN, Switzerland              *
0015  *      Joerg Stelzer   <Joerg.Stelzer@cern.ch>  - CERN, Switzerland              *
0016  *      Helge Voss      <Helge.Voss@cern.ch>     - MPI-K Heidelberg, Germany      *
0017  *      Kai Voss        <Kai.Voss@cern.ch>       - U. of Victoria, Canada         *
0018  *                                                                                *
0019  * Copyright (c) 2005:                                                            *
0020  *      CERN, Switzerland                                                         *
0021  *      U. of Victoria, Canada                                                    *
0022  *      MPI-K Heidelberg, Germany                                                 *
0023  *      LAPP, Annecy, France                                                      *
0024  *                                                                                *
0025  * Redistribution and use in source and binary forms, with or without             *
0026  * modification, are permitted according to the terms listed in LICENSE           *
0027  * (see tmva/doc/LICENSE)                                          *
0028  **********************************************************************************/
0029
0030 #ifndef ROOT_TMVA_BinarySearchTree
0031 #define ROOT_TMVA_BinarySearchTree
0032
0033 //////////////////////////////////////////////////////////////////////////
0034 //                                                                      //
0035 // BinarySearchTree                                                     //
0036 //                                                                      //
0037 // A simple Binary search tree including volume search method           //
0038 //                                                                      //
0039 //////////////////////////////////////////////////////////////////////////
0040
0041 #include <vector>
0042 #include <queue>
0043 #include <utility>
0044
0045 #ifndef ROOT_time
0046 #include "time.h"
0047 #endif
0048
0049 #include "TMVA/Volume.h"
0050 #include "TMVA/BinaryTree.h"
0051 #include "TMVA/BinarySearchTreeNode.h"
0052 #include "TMVA/VariableInfo.h"
0053
0054 class TString;
0055 class TTree;
0056
0057 // -----------------------------------------------------------------------------
0058 // the binary search tree
0059
0060 namespace TMVA {
0061
0062    class Event;
0063    //   class MethodBase;
0064
0065    class BinarySearchTree : public BinaryTree {
0066
0067    public:
0068
0069       // constructor
0070       BinarySearchTree( void );
0071
0072       // copy constructor
0073       BinarySearchTree (const BinarySearchTree &b);
0074
0075       // destructor
0076       virtual ~BinarySearchTree( void );
0077
0078       Node * CreateNode( UInt_t ) const override { return new BinarySearchTreeNode(); }
0079       BinaryTree* CreateTree() const override { return new BinarySearchTree(); }
0080       static BinarySearchTree* CreateFromXML(void* node, UInt_t tmva_Version_Code = TMVA_VERSION_CODE);
0081       const char* ClassName() const override { return "BinarySearchTree"; }
0082
0083       // Searches for a node with the specified data
0084       // by calling  the private, recursive, function for searching
0085       BinarySearchTreeNode* Search( Event * event ) const;
0086
0087       // Adds an item to the tree,
0088       void Insert( const Event * );
0089
0090       // get sum of weights of the nodes;
0091       Double_t GetSumOfWeights( void ) const;
0092
0093       //get sum of weights of the nodes of given type;
0094       Double_t GetSumOfWeights( Int_t theType ) const;
0095
0096       //set the periode (number of variables)
0097       void SetPeriode( Int_t p )      { fPeriod = p; }
0098
0099       // return periode (number of variables)
0100       UInt_t  GetPeriode( void ) const { return fPeriod; }
0101
0102       // counts events (weights) within a given volume
0103       Double_t SearchVolume( Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = nullptr );
0104
0105       // Create the search tree from the event collection
0106       // using ONLY the variables specified in "theVars"
0107       Double_t Fill( const std::vector<TMVA::Event*>& events, const std::vector<Int_t>& theVars, Int_t theType = -1 );
0108
0109       // create the search tree from the events in a TTree
0110       // using ALL the variables specified included in the Event
0111       Double_t Fill( const std::vector<TMVA::Event*>& events, Int_t theType = -1 );
0112
0113       void NormalizeTree ();
0114
0115       void CalcStatistics( TMVA::Node* n = nullptr );
0116       void Clear         ( TMVA::Node* n = nullptr );
0117
0118       /// access to mean for signal and background for each variable
0119       Float_t Mean(Types::ESBType sb, UInt_t var ) { return fMeans[sb==Types::kSignal?0:1][var]; }
0120
0121       /// access to RMS for signal and background for each variable
0122       Float_t RMS(Types::ESBType sb, UInt_t var ) { return fRMS[sb==Types::kSignal?0:1][var]; }
0123
0124       /// access to Minimum for signal and background for each variable
0125       Float_t Min(Types::ESBType sb, UInt_t var ) { return fMin[sb==Types::kSignal?0:1][var]; }
0126
0127       /// access to Maximum for signal and background for each variable
0128       Float_t Max(Types::ESBType sb, UInt_t var ) { return fMax[sb==Types::kSignal?0:1][var]; }
0129
0130       Int_t SearchVolumeWithMaxLimit( TMVA::Volume*, std::vector<const TMVA::BinarySearchTreeNode*>* events = nullptr, Int_t = -1);
0131
0132       /// access to RMS for each variable
0133       Float_t RMS(UInt_t var ) { return fRMS[0][var]; } // attention! class 0 is taken as signal!
0134
0135       void SetNormalize( Bool_t norm ) { fCanNormalize = norm; }
0136
0137    private:
0138
0139       // add a new  node to the tree (as daughter)
0140       void       Insert( const Event*, Node* );
0141       // recursively search the nodes for Event
0142       BinarySearchTreeNode*      Search( Event*, Node *) const ;
0143
0144       //check of Event variables lie with the volume
0145       Bool_t   InVolume    (const std::vector<Float_t>&, Volume* ) const;
0146       //
0147       void     DestroyNode ( BinarySearchTreeNode* );
0148
0149
0150       void     NormalizeTree( std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator,
0151                               std::vector< std::pair< Double_t, const TMVA::Event* > >::iterator, UInt_t );
0152
0153       // recursive search through daughter nodes in weight counting
0154       Double_t SearchVolume( Node*, Volume*, Int_t,
0155                              std::vector<const TMVA::BinarySearchTreeNode*>* events );
0156       UInt_t fPeriod;            ///< periode (number of event variables)
0157       UInt_t fCurrentDepth;      ///< internal variable, counting the depth of the tree during insertion
0158       Bool_t fStatisticsIsValid; ///< flag if last stat calculation is still valid, set to false if new node is insert
0159
0160       std::vector<Float_t>        fMeans[2];    ///< mean for signal and background for each variable
0161       std::vector<Float_t>        fRMS[2];      ///< RMS for signal and background for each variable
0162       std::vector<Float_t>        fMin[2];      ///< RMS for signal and background for each variable
0163       std::vector<Float_t>        fMax[2];      ///< RMS for signal and background for each variable
0164       std::vector<Double_t>       fSum[2];      ///< Sum for signal and background for each variable
0165       std::vector<Double_t>       fSumSq[2];    ///< Squared Sum for signal and background for each variable
0166       Double_t                    fNEventsW[2]; ///< Number of events per class, taking into account event weights
0167       Double_t                    fSumOfWeights;///< Total number of events (weighted) counted during filling
0168                                                 ///< should be the same as fNEventsW[0]+fNEventsW[1].. used as a check
0169
0170       Bool_t                      fCanNormalize; ///< the tree can be normalised
0171       std::vector< std::pair<Double_t,const TMVA::Event*> > fNormalizeTreeTable;
0172
0173       ClassDefOverride(BinarySearchTree,0); // Binary search tree including volume search method
0174    };
0175
0176 } // namespace TMVA
0177
0178 #endif