58 #ifndef ROOT_TMVA_MsgLogger
61 #ifndef ROOT_TMVA_MethodBase
64 #ifndef ROOT_TMVA_Tools
67 #ifndef ROOT_TMVA_Event
70 #ifndef ROOT_TMVA_BinarySearchTree
79 TMVA::BinarySearchTree::BinarySearchTree(
void ) :
83 fStatisticsIsValid(
kFALSE ),
85 fCanNormalize( kFALSE )
87 fNEventsW[0]=fNEventsW[1]=0.;
95 fPeriod ( b.fPeriod ),
97 fStatisticsIsValid(
kFALSE ),
98 fSumOfWeights( b.fSumOfWeights ),
102 Log() <<
kFATAL <<
" Copy constructor not implemented yet " <<
Endl;
110 for(std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator pIt = fNormalizeTreeTable.begin();
111 pIt != fNormalizeTreeTable.end(); pIt++) {
120 std::string
type(
"");
123 bt->
ReadXML( node, tmva_Version_Code );
133 fStatisticsIsValid =
kFALSE;
135 if (this->GetRoot() ==
NULL) {
138 this->GetRoot()->SetPos(
's');
139 this->GetRoot()->SetDepth(0);
141 fSumOfWeights =
event->GetWeight();
148 Log() <<
kFATAL <<
"<Insert> event vector length != Periode specified in Binary Tree" <<
Endl
149 <<
"--- event size: " <<
event->GetNVariables() <<
" Periode: " << this->GetPeriode() <<
Endl
150 <<
"--- and all this when trying filling the "<<fNNodes+1<<
"th Node" <<
Endl;
153 this->Insert(event, this->GetRoot());
157 if (fCanNormalize) fNormalizeTreeTable.push_back( std::make_pair(0.0,
new const Event(*event)) );
167 fStatisticsIsValid =
kFALSE;
172 this->Insert(event, node->
GetLeft());
178 fSumOfWeights +=
event->GetWeight();
189 this->Insert(event, node->
GetRight());
195 fSumOfWeights +=
event->GetWeight();
203 else Log() <<
kFATAL <<
"<Insert> neither left nor right :)" <<
Endl;
211 return this->Search( event, this->GetRoot() );
224 return this->Search(event, node->
GetLeft());
226 return this->Search(event, node->
GetRight());
236 if (fSumOfWeights <= 0) {
237 Log() <<
kWARNING <<
"you asked for the SumOfWeights, which is not filled yet"
238 <<
" I call CalcStatistics which hopefully fixes things"
241 if (fSumOfWeights <= 0)
Log() <<
kFATAL <<
" Zero events in your Search Tree" <<
Endl;
243 return fSumOfWeights;
251 if (fSumOfWeights <= 0) {
252 Log() <<
kWARNING <<
"you asked for the SumOfWeights, which is not filled yet"
253 <<
" I call CalcStatistics which hopefully fixes things"
256 if (fSumOfWeights <= 0)
Log() <<
kFATAL <<
" Zero events in your Search Tree" <<
Endl;
268 fPeriod = theVars.size();
269 return Fill(events, theType);
281 if (fSumOfWeights != 0) {
283 <<
"You are filling a search three that is not empty.. "
284 <<
" do you know what you are doing?"
287 for (
UInt_t ievt=0; ievt<
n; ievt++) {
289 if (theType == -1 || (
Int_t(events[ievt]->
GetClass()) == theType) ) {
290 this->Insert( events[ievt] );
292 fSumOfWeights += events[ievt]->GetWeight();
297 return fSumOfWeights;
303 std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator rightBound,
308 if (leftBound == rightBound)
return;
310 if (actDim == fPeriod) actDim = 0;
311 for (std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator i=leftBound; i!=rightBound; i++) {
312 i->first = i->second->GetValue( actDim );
315 std::sort( leftBound, rightBound );
317 std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator leftTemp = leftBound;
318 std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator rightTemp = rightBound;
323 if (rightTemp == leftTemp ) {
327 if (leftTemp == rightTemp) {
332 std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator mid = leftTemp;
333 std::vector< std::pair<Double_t, const TMVA::Event*> >::iterator midTemp = mid;
335 if (mid!=leftBound) midTemp--;
337 while (mid != leftBound && mid->second->GetValue( actDim ) == midTemp->second->GetValue( actDim )) {
342 Insert( mid->second );
347 NormalizeTree( leftBound, mid, actDim+1 );
351 NormalizeTree( mid, rightBound, actDim+1 );
365 NormalizeTree( fNormalizeTreeTable.begin(), fNormalizeTreeTable.end(), 0 );
378 if (n !=
NULL)
delete n;
388 std::vector<const BinarySearchTreeNode*>* events )
390 return SearchVolume( this->GetRoot(), volume, 0, events );
398 std::vector<const BinarySearchTreeNode*>* events )
400 if (t==
NULL)
return 0;
405 if (InVolume( st->
GetEventV(), volume )) {
407 if (
NULL != events) events->push_back( st );
415 Int_t d = depth%this->GetPeriode();
417 Log() <<
kFATAL <<
"<SearchVolume> selector in Searchvolume "
423 if (tl) count += SearchVolume( st->
GetLeft(), volume, (depth+1), events );
424 if (tr) count += SearchVolume( st->
GetRight(), volume, (depth+1), events );
434 for (
UInt_t ivar=0; ivar< fPeriod; ivar++) {
435 result = ( (*(volume->
fLower))[ivar] <
event[ivar] &&
436 (*(volume->
fUpper))[ivar] >=
event[ivar] );
447 if (fStatisticsIsValid)
return;
454 for (
Int_t sb=0; sb<2; sb++) {
456 fMeans[sb] = std::vector<Float_t>(fPeriod);
457 fRMS[sb] = std::vector<Float_t>(fPeriod);
458 fMin[sb] = std::vector<Float_t>(fPeriod);
459 fMax[sb] = std::vector<Float_t>(fPeriod);
460 fSum[sb] = std::vector<Double_t>(fPeriod);
461 fSumSq[sb] = std::vector<Double_t>(fPeriod);
462 for (
UInt_t j=0; j<fPeriod; j++) {
463 fMeans[sb][j] = fRMS[sb][j] = fSum[sb][j] = fSumSq[sb][j] = 0;
464 fMin[sb][j] = FLT_MAX;
465 fMax[sb][j] = -FLT_MAX;
469 if (currentNode ==
NULL)
return;
472 const std::vector<Float_t> & evtVec = currentNode->
GetEventV();
478 fNEventsW[
type] += weight;
479 fSumOfWeights += weight;
481 for (
UInt_t j=0; j<fPeriod; j++) {
483 fSum[
type][j] += val*weight;
484 fSumSq[
type][j] += val*val*weight;
485 if (val < fMin[type][j]) fMin[
type][j] = val;
486 if (val > fMax[type][j]) fMax[
type][j] = val;
493 for (
Int_t sb=0; sb<2; sb++) {
494 for (
UInt_t j=0; j<fPeriod; j++) {
495 if (fNEventsW[sb] == 0) { fMeans[sb][j] = fRMS[sb][j] = 0;
continue; }
496 fMeans[sb][j] = fSum[sb][j]/fNEventsW[sb];
497 fRMS[sb][j] =
TMath::Sqrt(fSumSq[sb][j]/fNEventsW[sb] - fMeans[sb][j]*fMeans[sb][j]);
500 fStatisticsIsValid =
kTRUE;
511 if (this->GetRoot() ==
NULL)
return 0;
513 std::queue< std::pair< const BinarySearchTreeNode*, Int_t > > queue;
514 std::pair< const BinarySearchTreeNode*, Int_t > st = std::make_pair( (
const BinarySearchTreeNode*)this->GetRoot(), 0 );
519 while ( !queue.empty() ) {
520 st = queue.front(); queue.pop();
522 if (count == max_points)
525 if (InVolume( st.first->GetEventV(), volume )) {
527 if (
NULL != events) events->push_back( st.first );
532 if ( d ==
Int_t(this->GetPeriode()) ) d = 0;
534 if (d != st.first->GetSelector()) {
535 Log() <<
kFATAL <<
"<SearchVolume> selector in Searchvolume "
536 << d <<
" != " <<
"node "<< st.first->GetSelector() <<
Endl;
539 tl = (*(volume->
fLower))[d] < st.first->GetEventV()[d] && st.first->GetLeft() !=
NULL;
540 tr = (*(volume->
fUpper))[d] >= st.first->GetEventV()[d] && st.first->GetRight() !=
NULL;
std::vector< Double_t > * fLower
MsgLogger & Endl(MsgLogger &ml)
virtual ~BinarySearchTree(void)
destructor
Bool_t InVolume(const std::vector< Float_t > &, Volume *) const
std::vector< Double_t > * fUpper
Int_t SearchVolumeWithMaxLimit(TMVA::Volume *, std::vector< const TMVA::BinarySearchTreeNode * > *events=0, Int_t=-1)
virtual void SetRight(Node *r)
void NormalizeTree()
Normalisation of tree.
virtual Bool_t GoesLeft(const Event &) const =0
virtual void SetLeft(Node *l)
void SetSelector(Short_t i)
void Clear(TMVA::Node *n=0)
clear nodes
ClassImp(TMVA::BinarySearchTree) TMVA
default constructor
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 ...
Double_t GetSumOfWeights(void) const
return the sum of event (node) weights
void CalcStatistics(TMVA::Node *n=0)
calculate basic statistics (mean, rms for each variable)
UInt_t GetNVariables() const
accessor to the number of variables
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
void Insert(const Event *)
insert a new "event" in the binary tree
virtual void ReadXML(void *node, UInt_t tmva_Version_Code=TMVA_VERSION_CODE)
read attributes from XML
virtual void SetParent(Node *p)
Float_t GetWeight() const
Short_t GetSelector() const
virtual Node * GetRight() const
Abstract ClassifierFactory template that handles arbitrary types.
virtual Bool_t GoesRight(const Event &) const =0
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" ...
const std::vector< Float_t > & GetEventV() const
Double_t Sqrt(Double_t x)
BinarySearchTreeNode * Search(Event *event) const
search the tree to find the node matching "event"
virtual Node * GetLeft() const