DecisionTree.cpp

/*
GRT MIT License
Copyright (c) <2012> <Nicholas Gillian, Media Lab, MIT>

Permission is hereby granted, free of charge, to any person obtaining a copy of this software
and associated documentation files (the "Software"), to deal in the Software without restriction,
including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so,
subject to the following conditions:

The above copyright notice and this permission notice shall be included in all copies or substantial
portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT
LIMITED TO THE WARRANTIES OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
*/

#define GRT_DLL_EXPORTS
#include "DecisionTree.h"

GRT_BEGIN_NAMESPACE

//Define the string that will be used to identify the object
const std::string DecisionTree::id = "DecisionTree";
std::string DecisionTree::getId() { return DecisionTree::id; }

//Register the DecisionTree module with the Classifier base class
RegisterClassifierModule< DecisionTree > DecisionTree::registerModule( DecisionTree::getId() );

DecisionTree::DecisionTree(const DecisionTreeNode &decisionTreeNode,const UINT minNumSamplesPerNode,const UINT maxDepth,const bool removeFeaturesAtEachSplit,const Tree::TrainingMode trainingMode,const UINT numSplittingSteps,const bool useScaling) : Classifier( DecisionTree::getId() )
{
 this->tree = NULL;
 this->decisionTreeNode = dynamic_cast< DecisionTreeNode* >( decisionTreeNode.deepCopy() );
 this->minNumSamplesPerNode = minNumSamplesPerNode;
 this->maxDepth = maxDepth;
 this->removeFeaturesAtEachSplit = removeFeaturesAtEachSplit;
 this->trainingMode = trainingMode;
 this->numSplittingSteps = numSplittingSteps;
 this->useScaling = useScaling;
 this->supportsNullRejection = true;
 this->numTrainingIterationsToConverge = 20; //Retrain the model 20 times and pick the best one
 classifierMode = STANDARD_CLASSIFIER_MODE;
}

DecisionTree::DecisionTree(const DecisionTree &rhs) : Classifier( DecisionTree::getId() )
{
 tree = NULL;
 decisionTreeNode = NULL;
 classifierMode = STANDARD_CLASSIFIER_MODE;
 *this = rhs;
}

DecisionTree::~DecisionTree(void)
{
 clear();
 
 if( decisionTreeNode != NULL ){
 delete decisionTreeNode;
 decisionTreeNode = NULL;
 }
}

DecisionTree& DecisionTree::operator=(const DecisionTree &rhs){
 if( this != &rhs ){
 //Clear this tree
 clear();
 
 if( rhs.getTrained() ){
 //Deep copy the tree
 this->tree = (DecisionTreeNode*)rhs.deepCopyTree();
 }
 
 //Deep copy the main node
 if( this->decisionTreeNode != NULL ){
 delete decisionTreeNode;
 decisionTreeNode = NULL;
 }
 this->decisionTreeNode = rhs.deepCopyDecisionTreeNode();
 
 this->minNumSamplesPerNode = rhs.minNumSamplesPerNode;
 this->maxDepth = rhs.maxDepth;
 this->removeFeaturesAtEachSplit = rhs.removeFeaturesAtEachSplit;
 this->trainingMode = rhs.trainingMode;
 this->numSplittingSteps = rhs.numSplittingSteps;
 this->nodeClusters = rhs.nodeClusters;
 
 //Copy the base classifier variables
 copyBaseVariables( (Classifier*)&rhs );
 }
 return *this;
}

bool DecisionTree::deepCopyFrom(const Classifier *classifier){
 
 if( classifier == NULL ) return false;
 
 if( this->getClassifierType() == classifier->getClassifierType() ){
 
 const DecisionTree *ptr = dynamic_cast<const DecisionTree*>( classifier );
 
 //Clear this tree
 this->clear();
 
 if( ptr->getTrained() ){
 //Deep copy the tree
 this->tree = ptr->deepCopyTree();
 }
 
 //Deep copy the main node
 if( this->decisionTreeNode != NULL ){
 delete decisionTreeNode;
 decisionTreeNode = NULL;
 }
 this->decisionTreeNode = ptr->deepCopyDecisionTreeNode();
 
 this->minNumSamplesPerNode = ptr->minNumSamplesPerNode;
 this->maxDepth = ptr->maxDepth;
 this->removeFeaturesAtEachSplit = ptr->removeFeaturesAtEachSplit;
 this->trainingMode = ptr->trainingMode;
 this->numSplittingSteps = ptr->numSplittingSteps;
 this->nodeClusters = ptr->nodeClusters;
 
 //Copy the base classifier variables
 return copyBaseVariables( classifier );
 }
 return false;
}

bool DecisionTree::train_(ClassificationData &trainingData){
 
 //Clear any previous model
 clear();
 
 if( decisionTreeNode == NULL ){
 errorLog << __GRT_LOG__ << " The decision tree node has not been set! You must set this first before training a model." << std::endl;
 return false;
 }
 
 const unsigned int N = trainingData.getNumDimensions();
 const unsigned int K = trainingData.getNumClasses();
 
 if( trainingData.getNumSamples() == 0 ){
 errorLog << __GRT_LOG__ << " Training data has zero samples!" << std::endl;
 return false;
 }
 
 numInputDimensions = N;
 numOutputDimensions = K;
 numClasses = K;
 classLabels = trainingData.getClassLabels();
 ranges = trainingData.getRanges();
 
 //Get the validation set if needed
 ClassificationData validationData;
 if( useValidationSet ){
 validationData = trainingData.split( validationSetSize );
 validationSetAccuracy = 0;
 validationSetPrecision.resize( useNullRejection ? K+1 : K, 0 );
 validationSetRecall.resize( useNullRejection ? K+1 : K, 0 );
 }

 const unsigned int M = trainingData.getNumSamples();
 
 //Scale the training data if needed
 if( useScaling ){
 //Scale the training data between 0 and 1
 trainingData.scale(0, 1);
 }
 
 //If we are using null rejection, then we need a copy of the training dataset for later
 ClassificationData trainingDataCopy;
 if( useNullRejection ){
 trainingDataCopy = trainingData;
 }
 
 //Setup the valid features - at this point all features can be used
 Vector< UINT > features(N);
 for(UINT i=0; i<N; i++){
 features[i] = i;
 }

 numTrainingIterationsToConverge = 1;
 trainingLog << "numTrainingIterationsToConverge " << numTrainingIterationsToConverge << " useValidationSet: " << useValidationSet << std::endl;

 if( useValidationSet ){

 //If we get here, then we are going to train the tree several times and pick the best model
 DecisionTreeNode *bestTree = NULL;
 Float bestValidationSetAccuracy = 0;
 UINT bestTreeIndex = 0;
 for(UINT i=0; i<numTrainingIterationsToConverge; i++){

 trainingLog << "Training tree iteration: " << i+1 << "/" << numTrainingIterationsToConverge << std::endl;

 if( !trainTree( trainingData, trainingDataCopy, validationData, features ) ){
 errorLog << __GRT_LOG__ << " Failed to build tree!" << std::endl;
 //Delete the best tree if it exists
 if( bestTree != NULL ){
 delete bestTree;
 bestTree = NULL;
 }
 return false;
 }

 //Keep track of the best tree
 if( bestTree == NULL ){
 //Grab the tree pointer
 bestTree = tree;
 bestValidationSetAccuracy = validationSetAccuracy;
 bestTreeIndex = i;
 }else{
 if( validationSetAccuracy > bestValidationSetAccuracy ){
 //Grab the tree pointer
 bestTree = tree;
 bestValidationSetAccuracy = validationSetAccuracy;
 bestTreeIndex = i;
 }else{
 //If we get here then the current tree is not the best so far, so free it
 if( tree != NULL ){
 delete tree;
 tree = NULL;
 }
 }
 }
 }

 //Use the best tree
 trainingLog << "Best tree index: " << bestTreeIndex+1 << " validation set accuracy: " << bestValidationSetAccuracy << std::endl;
 
 if( bestTree != tree ){
 //Delete the tree if it exists
 if( tree != NULL ){
 delete tree;
 tree = NULL;
 }

 //Swap the pointers
 tree = bestTree;
 }

 }else{
 //If we get here, then we are going to train the tree once
 if( !trainTree( trainingData, trainingDataCopy, validationData, features ) ){
 return false;
 }
 }

 //If we get this far, then a model has been trained
 converged = true;

 //Setup the data for prediction
 predictedClassLabel = 0;
 maxLikelihood = 0;
 classLikelihoods.resize(numClasses);
 classDistances.resize(numClasses);

 //Compute the final training stats
 trainingSetAccuracy = 0;
 validationSetAccuracy = 0;

 //If scaling was on, then the data will already be scaled, so turn it off temporially
 bool scalingState = useScaling;
 useScaling = false;
 for(UINT i=0; i<M; i++){
 if( !predict_( trainingData[i].getSample() ) ){
 trained = false;
 errorLog << __GRT_LOG__ << " Failed to run prediction for training sample: " << i << "! Failed to fully train model!" << std::endl;
 return false;
 }

 if( predictedClassLabel == trainingData[i].getClassLabel() ){
 trainingSetAccuracy++;
 }
 }

 if( useValidationSet ){
 for(UINT i=0; i<validationData.getNumSamples(); i++){
 if( !predict_( validationData[i].getSample() ) ){
 trained = false;
 errorLog << __GRT_LOG__ << " Failed to run prediction for validation sample: " << i << "! Failed to fully train model!" << std::endl;
 return false;
 }

 if( predictedClassLabel == validationData[i].getClassLabel() ){
 validationSetAccuracy++;
 }
 }
 }

 trainingSetAccuracy = trainingSetAccuracy / M * 100.0;

 trainingLog << "Training set accuracy: " << trainingSetAccuracy << std::endl;

 if( useValidationSet ){
 validationSetAccuracy = validationSetAccuracy / validationData.getNumSamples() * 100.0;
 trainingLog << "Validation set accuracy: " << validationSetAccuracy << std::endl;
 }

 //Reset the scaling state for future prediction
 useScaling = scalingState;

 return true;
}

bool DecisionTree::trainTree( ClassificationData trainingData, const ClassificationData &trainingDataCopy, const ClassificationData &validationData, Vector< UINT > features ){

 //Note, this function is only called internally by the decision tree, users should call train_ instead.

 const unsigned int M = trainingData.getNumSamples();

 //Build the tree
 UINT nodeID = 0;
 tree = buildTree( trainingData, NULL, features, classLabels, nodeID );
 
 if( tree == NULL ){
 clear();
 errorLog << __GRT_LOG__ << " Failed to build tree!" << std::endl;
 return false;
 }

 //Flag that the algorithm has been trained
 trained = true;
 
 //Compute the null rejection thresholds if null rejection is enabled
 if( useNullRejection ){
 VectorFloat classLikelihoods( numClasses );
 Vector< UINT > predictions(M);
 VectorFloat distances(M);
 VectorFloat classCounter( numClasses, 0 );
 
 //Run over the training dataset and compute the distance between each training sample and the predicted node cluster
 VectorFloat sample;
 for(UINT i=0; i<M; i++){
 //Run the prediction for this sample
 sample = trainingDataCopy[i].getSample();
 if( !tree->predict_( sample, classLikelihoods ) ){
 errorLog << __GRT_LOG__ << " Failed to predict training sample while building null rejection model!" << std::endl;
 return false;
 }
 
 //Store the predicted class index and cluster distance
 predictions[i] = Util::getMaxIndex( classLikelihoods );
 distances[i] = getNodeDistance(sample, tree->getPredictedNodeID() );
 
 classCounter[ predictions[i] ]++;
 }
 
 //Compute the average distance for each class between the training data and the node clusters
 classClusterMean.clear();
 classClusterStdDev.clear();
 classClusterMean.resize( numClasses, 0 );
 classClusterStdDev.resize( numClasses, 0.01 ); //we start the std dev with a small value to ensure it is not zero
 
 for(UINT i=0; i<M; i++){
 classClusterMean[ predictions[i] ] += distances[ i ];
 }
 for(UINT k=0; k<numClasses; k++){
 classClusterMean[k] /= grt_max( classCounter[k], 1 );
 }
 
 //Compute the std deviation
 for(UINT i=0; i<M; i++){
 classClusterStdDev[ predictions[i] ] += MLBase::SQR( distances[ i ] - classClusterMean[ predictions[i] ] );
 }
 for(UINT k=0; k<numClasses; k++){
 classClusterStdDev[k] = sqrt( classClusterStdDev[k] / grt_max( classCounter[k], 1 ) );
 }
 
 //Compute the null rejection thresholds using the class mean and std dev
 recomputeNullRejectionThresholds();
 }
 
 if( useValidationSet ){
 const UINT numTestSamples = validationData.getNumSamples();
 double numCorrect = 0;
 UINT testLabel = 0;
 VectorFloat testSample;
 VectorFloat validationSetPrecisionCounter( validationSetPrecision.size(), 0.0 );
 VectorFloat validationSetRecallCounter( validationSetRecall.size(), 0.0 );
 trainingLog << "Testing model with validation set..." << std::endl;
 for(UINT i=0; i<numTestSamples; i++){
 testLabel = validationData[i].getClassLabel();
 testSample = validationData[i].getSample();
 predict_( testSample );
 if( predictedClassLabel == testLabel ){
 numCorrect++;
 validationSetPrecision[ getClassLabelIndexValue( testLabel ) ]++;
 validationSetRecall[ getClassLabelIndexValue( testLabel ) ]++;
 }
 validationSetPrecisionCounter[ getClassLabelIndexValue( predictedClassLabel ) ]++;
 validationSetRecallCounter[ getClassLabelIndexValue( testLabel ) ]++;
 }
 
 validationSetAccuracy = (numCorrect / numTestSamples) * 100.0;
 for(UINT i=0; i<validationSetPrecision.getSize(); i++){
 validationSetPrecision[i] /= validationSetPrecisionCounter[i] > 0 ? validationSetPrecisionCounter[i] : 1;
 }
 for(UINT i=0; i<validationSetRecall.getSize(); i++){
 validationSetRecall[i] /= validationSetRecallCounter[i] > 0 ? validationSetRecallCounter[i] : 1;
 }
 
 Classifier::trainingLog << "Validation set accuracy: " << validationSetAccuracy << std::endl;
 
 Classifier::trainingLog << "Validation set precision: ";
 for(UINT i=0; i<validationSetPrecision.getSize(); i++){
 Classifier::trainingLog << validationSetPrecision[i] << " ";
 }
 Classifier::trainingLog << std::endl;
 
 Classifier::trainingLog << "Validation set recall: ";
 for(UINT i=0; i<validationSetRecall.getSize(); i++){
 Classifier::trainingLog << validationSetRecall[i] << " ";
 }
 Classifier::trainingLog << std::endl;
 }
 
 return true;
}

bool DecisionTree::predict_(VectorFloat &inputVector){
 
 predictedClassLabel = 0;
 maxLikelihood = 0;
 
 //Validate the input is OK and the model is trained properly
 if( !trained ){
 errorLog << __GRT_LOG__ << " Model Not Trained!" << std::endl;
 return false;
 }
 
 if( tree == NULL ){
 errorLog << __GRT_LOG__ << " DecisionTree pointer is null!" << std::endl;
 return false;
 }
 
 if( inputVector.getSize() != numInputDimensions ){
 errorLog << __GRT_LOG__ << " The size of the input Vector (" << inputVector.getSize() << ") does not match the num features in the model (" << numInputDimensions << std::endl;
 return false;
 }
 
 //Scale the input data if needed
 if( useScaling ){
 for(UINT n=0; n<numInputDimensions; n++){
 inputVector[n] = grt_scale(inputVector[n], ranges[n].minValue, ranges[n].maxValue, 0.0, 1.0);
 }
 }
 
 if( classLikelihoods.size() != numClasses ) classLikelihoods.resize(numClasses,0);
 if( classDistances.size() != numClasses ) classDistances.resize(numClasses,0);
 
 //Run the decision tree prediction
 if( !tree->predict_( inputVector, classLikelihoods ) ){
 errorLog << __GRT_LOG__ << " Failed to predict!" << std::endl;
 return false;
 }
 
 //Find the maximum likelihood
 //The tree automatically returns proper class likelihoods so we don't need to do anything else
 UINT maxIndex = 0;
 maxLikelihood = 0;
 for(UINT k=0; k<numClasses; k++){
 if( classLikelihoods[k] > maxLikelihood ){
 maxLikelihood = classLikelihoods[k];
 maxIndex = k;
 }
 }
 
 //Run the null rejection
 if( useNullRejection ){
 
 //Get the distance between the input and the leaf mean
 Float leafDistance = getNodeDistance( inputVector, tree->getPredictedNodeID() );
 
 if( grt_isnan(leafDistance) ){
 errorLog << __GRT_LOG__ << " Failed to match leaf node ID to compute node distance!" << std::endl;
 return false;
 }
 
 //Set the predicted class distance as the leaf distance, all other classes will have a distance of zero
 classDistances.setAll(0.0);
 classDistances[ maxIndex ] = leafDistance;
 
 //Use the distance to check if the class label should be rejected or not
 if( leafDistance <= nullRejectionThresholds[ maxIndex ] ){
 predictedClassLabel = classLabels[ maxIndex ];
 }else predictedClassLabel = GRT_DEFAULT_NULL_CLASS_LABEL;
 
 }else {
 //Set the predicated class label
 predictedClassLabel = classLabels[ maxIndex ];
 }
 
 return true;
}

bool DecisionTree::clear(){
 
 //Clear the Classifier variables
 Classifier::clear();
 
 //Clear the node clusters
 nodeClusters.clear();
 
 //Delete the tree if it exists
 if( tree != NULL ){
 tree->clear();
 delete tree;
 tree = NULL;
 }
 
 //NOTE: We do not want to clean up the decisionTreeNode here as we need to keep track of this, this is only delete in the destructor
 
 return true;
}

bool DecisionTree::recomputeNullRejectionThresholds(){
 
 if( !trained ){
 Classifier::warningLog << __GRT_LOG__ << " Failed to recompute null rejection thresholds, the model has not been trained!" << std::endl;
 return false;
 }
 
 if( !useNullRejection ){
 Classifier::warningLog << __GRT_LOG__ << " Failed to recompute null rejection thresholds, null rejection is not enabled!" << std::endl;
 return false;
 }
 
 nullRejectionThresholds.resize( numClasses );
 
 //Compute the rejection threshold for each class using the mean and std dev
 for(UINT k=0; k<numClasses; k++){
 nullRejectionThresholds[k] = classClusterMean[k] + (classClusterStdDev[k]*nullRejectionCoeff);
 }
 
 return true;
}

bool DecisionTree::save( std::fstream &file ) const{
 
 if(!file.is_open())
 {
 errorLog << __GRT_LOG__ << " The file is not open!" << std::endl;
 return false;
 }
 
 //Write the header info
 file << "GRT_DECISION_TREE_MODEL_FILE_V4.0\n";
 
 //Write the classifier settings to the file
 if( !Classifier::saveBaseSettingsToFile(file) ){
 errorLog << __GRT_LOG__ << " Failed to save classifier base settings to file!" << std::endl;
 return false;
 }
 
 if( decisionTreeNode != NULL ){
 file << "DecisionTreeNodeType: " << decisionTreeNode->getNodeType() << std::endl;
 if( !decisionTreeNode->save( file ) ){
 errorLog << __GRT_LOG__ << " Failed to save decisionTreeNode settings to file!" << std::endl;
 return false;
 }
 }else{
 file << "DecisionTreeNodeType: " << "NULL" << std::endl;
 }
 
 file << "MinNumSamplesPerNode: " << minNumSamplesPerNode << std::endl;
 file << "MaxDepth: " << maxDepth << std::endl;
 file << "RemoveFeaturesAtEachSpilt: " << removeFeaturesAtEachSplit << std::endl;
 file << "TrainingMode: " << trainingMode << std::endl;
 file << "NumSplittingSteps: " << numSplittingSteps << std::endl;
 file << "TreeBuilt: " << (tree != NULL ? 1 : 0) << std::endl;
 
 if( tree != NULL ){
 file << "Tree:\n";
 if( !tree->save( file ) ){
 errorLog << __GRT_LOG__ << " Failed to save tree to file!" << std::endl;
 return false;
 }
 
 //Save the null rejection data if needed
 if( useNullRejection ){
 
 file << "ClassClusterMean:";
 for(UINT k=0; k<numClasses; k++){
 file << " " << classClusterMean[k];
 }
 file << std::endl;
 
 file << "ClassClusterStdDev:";
 for(UINT k=0; k<numClasses; k++){
 file << " " << classClusterStdDev[k];
 }
 file << std::endl;
 
 file << "NumNodes: " << nodeClusters.size() << std::endl;
 file << "NodeClusters:\n";
 
 std::map< UINT, VectorFloat >::const_iterator iter = nodeClusters.begin();
 
 while( iter != nodeClusters.end() ){
 
 //Write the nodeID
 file << iter->first;
 
 //Write the node cluster
 for(UINT j=0; j<numInputDimensions; j++){
 file << " " << iter->second[j];
 }
 file << std::endl;
 
 iter++;
 }
 }
 
 }
 
 return true;
}

bool DecisionTree::load( std::fstream &file ){
 
 clear();

 UINT tempTrainingMode = 0;
 
 if( decisionTreeNode != NULL ){
 delete decisionTreeNode;
 decisionTreeNode = NULL;
 }
 
 if( !file.is_open() )
 {
 errorLog << __GRT_LOG__ << " Could not open file to load model" << std::endl;
 return false;
 }
 
 std::string word;
 file >> word;
 
 //Check to see if we should load a legacy file
 if( word == "GRT_DECISION_TREE_MODEL_FILE_V1.0" ){
 return loadLegacyModelFromFile_v1( file );
 }
 
 if( word == "GRT_DECISION_TREE_MODEL_FILE_V2.0" ){
 return loadLegacyModelFromFile_v2( file );
 }
 
 if( word == "GRT_DECISION_TREE_MODEL_FILE_V3.0" ){
 return loadLegacyModelFromFile_v3( file );
 }
 
 //Find the file type header
 if( word != "GRT_DECISION_TREE_MODEL_FILE_V4.0" ){
 errorLog << __GRT_LOG__ << " Could not find Model File Header" << std::endl;
 return false;
 }
 
 //Load the base settings from the file
 if( !Classifier::loadBaseSettingsFromFile(file) ){
 errorLog << __GRT_LOG__ << " Failed to load base settings from file!" << std::endl;
 return false;
 }
 
 file >> word;
 if(word != "DecisionTreeNodeType:"){
 errorLog << __GRT_LOG__ << " Could not find the DecisionTreeNodeType!" << std::endl;
 return false;
 }
 file >> word;
 
 if( word != "NULL" ){
 
 decisionTreeNode = dynamic_cast< DecisionTreeNode* >( DecisionTreeNode::createInstanceFromString( word ) );
 
 if( decisionTreeNode == NULL ){
 errorLog << __GRT_LOG__ << " Could not create new DecisionTreeNode from type: " << word << std::endl;
 return false;
 }
 
 if( !decisionTreeNode->load( file ) ){
 errorLog << __GRT_LOG__ << " Failed to load decisionTreeNode settings from file!" << std::endl;
 return false;
 }
 }else{
 errorLog << __GRT_LOG__ << " Failed to load decisionTreeNode! DecisionTreeNodeType is NULL!" << std::endl;
 return false;
 }
 
 file >> word;
 if(word != "MinNumSamplesPerNode:"){
 errorLog << __GRT_LOG__ << " Could not find the MinNumSamplesPerNode!" << std::endl;
 return false;
 }
 file >> minNumSamplesPerNode;
 
 file >> word;
 if(word != "MaxDepth:"){
 errorLog << __GRT_LOG__ << " Could not find the MaxDepth!" << std::endl;
 return false;
 }
 file >> maxDepth;
 
 file >> word;
 if(word != "RemoveFeaturesAtEachSpilt:"){
 errorLog << __GRT_LOG__ << " Could not find the RemoveFeaturesAtEachSpilt!" << std::endl;
 return false;
 }
 file >> removeFeaturesAtEachSplit;
 
 file >> word;
 if(word != "TrainingMode:"){
 errorLog << __GRT_LOG__ << " Could not find the TrainingMode!" << std::endl;
 return false;
 }
 file >> tempTrainingMode;
 trainingMode = static_cast<Tree::TrainingMode>(tempTrainingMode);
 
 file >> word;
 if(word != "NumSplittingSteps:"){
 errorLog << __GRT_LOG__ << " Could not find the NumSplittingSteps!" << std::endl;
 return false;
 }
 file >> numSplittingSteps;
 
 file >> word;
 if(word != "TreeBuilt:"){
 errorLog << __GRT_LOG__ << " Could not find the TreeBuilt!" << std::endl;
 return false;
 }
 file >> trained;
 
 if( trained ){
 file >> word;
 if(word != "Tree:"){
 errorLog << __GRT_LOG__ << " Could not find the Tree!" << std::endl;
 return false;
 }
 
 //Create a new DTree
 tree = dynamic_cast< DecisionTreeNode* >( decisionTreeNode->createNewInstance() );
 
 if( tree == NULL ){
 clear();
 errorLog << __GRT_LOG__ << " Failed to create new DecisionTreeNode!" << std::endl;
 return false;
 }
 
 tree->setParent( NULL );
 if( !tree->load( file ) ){
 clear();
 errorLog << __GRT_LOG__ << " Failed to load tree from file!" << std::endl;
 return false;
 }
 
 //Load the null rejection data if needed
 if( useNullRejection ){
 
 UINT numNodes = 0;
 classClusterMean.resize( numClasses );
 classClusterStdDev.resize( numClasses );
 
 file >> word;
 if(word != "ClassClusterMean:"){
 errorLog << __GRT_LOG__ << " Could not find the ClassClusterMean header!" << std::endl;
 return false;
 }
 for(UINT k=0; k<numClasses; k++){
 file >> classClusterMean[k];
 }
 
 file >> word;
 if(word != "ClassClusterStdDev:"){
 errorLog << __GRT_LOG__ << " Could not find the ClassClusterStdDev header!" << std::endl;
 return false;
 }
 for(UINT k=0; k<numClasses; k++){
 file >> classClusterStdDev[k];
 }
 
 file >> word;
 if(word != "NumNodes:"){
 errorLog << __GRT_LOG__ << " Could not find the NumNodes header!" << std::endl;
 return false;
 }
 file >> numNodes;
 
 file >> word;
 if(word != "NodeClusters:"){
 errorLog << __GRT_LOG__ << " Could not find the NodeClusters header!" << std::endl;
 return false;
 }
 
 UINT nodeID = 0;
 VectorFloat cluster( numInputDimensions );
 for(UINT i=0; i<numNodes; i++){
 
 //load the nodeID
 file >> nodeID;
 
 for(UINT j=0; j<numInputDimensions; j++){
 file >> cluster[j];
 }
 
 //Add the cluster to the cluster nodes map
 nodeClusters[ nodeID ] = cluster;
 }
 
 //Recompute the null rejection thresholds
 recomputeNullRejectionThresholds();
 }
 
 //Resize the prediction results to make sure it is setup for realtime prediction
 maxLikelihood = DEFAULT_NULL_LIKELIHOOD_VALUE;
 bestDistance = DEFAULT_NULL_DISTANCE_VALUE;
 classLikelihoods.resize(numClasses,DEFAULT_NULL_LIKELIHOOD_VALUE);
 classDistances.resize(numClasses,DEFAULT_NULL_DISTANCE_VALUE);
 }
 
 return true;
}

bool DecisionTree::getModel( std::ostream &stream ) const{
 
 if( tree != NULL )
 return tree->getModel( stream );
 return false;
 
}

DecisionTreeNode* DecisionTree::deepCopyTree() const{
 
 if( tree == NULL ){
 return NULL;
 }

 return dynamic_cast< DecisionTreeNode* >( tree->deepCopy() );
}

DecisionTreeNode* DecisionTree::deepCopyDecisionTreeNode() const{
 
 if( decisionTreeNode == NULL ){
 return NULL;
 }
 
 return dynamic_cast< DecisionTreeNode* >(decisionTreeNode->deepCopy());
}

const DecisionTreeNode* DecisionTree::getTree() const{
 return tree;
}

bool DecisionTree::setDecisionTreeNode( const DecisionTreeNode &node ){
 
 if( decisionTreeNode != NULL ){
 decisionTreeNode->clear();
 delete decisionTreeNode;
 decisionTreeNode = NULL;
 }
 this->decisionTreeNode = dynamic_cast< DecisionTreeNode* >(node.deepCopy());
 
 return true;
}

DecisionTreeNode* DecisionTree::buildTree(ClassificationData &trainingData,DecisionTreeNode *parent,Vector< UINT > features,const Vector< UINT > &classLabels, UINT nodeID){
 
 const UINT M = trainingData.getNumSamples();
 const UINT N = trainingData.getNumDimensions();
 
 //Update the nodeID
 nodeID++;
 
 //Get the depth
 UINT depth = 0;
 
 if( parent != NULL )
 depth = parent->getDepth() + 1;
 
 //If there are no training data then return NULL
 if( trainingData.getNumSamples() == 0 )
 return NULL;
 
 //Create the new node
 DecisionTreeNode *node = dynamic_cast< DecisionTreeNode* >( decisionTreeNode->createNewInstance() );
 
 if( node == NULL )
 return NULL;
 
 //Get the class probabilities
 VectorFloat classProbs = trainingData.getClassProbabilities( classLabels );
 
 //Set the parent
 node->initNode( parent, depth, nodeID );
 
 //If all the training data belongs to the same class or there are no features left then create a leaf node and return
 if( trainingData.getNumClasses() == 1 || features.size() == 0 || M < minNumSamplesPerNode || depth >= maxDepth ){
 
 //Set the node
 node->setLeafNode( trainingData.getNumSamples(), classProbs );
 
 //Build the null cluster if null rejection is enabled
 if( useNullRejection ){
 nodeClusters[ nodeID ] = trainingData.getMean();
 }
 
 std::string info = "Reached leaf node.";
 if( trainingData.getNumClasses() == 1 ) info = "Reached pure leaf node.";
 else if( features.size() == 0 ) info = "Reached leaf node, no remaining features.";
 else if( M < minNumSamplesPerNode ) info = "Reached leaf node, hit min-samples-per-node limit.";
 else if( depth >= maxDepth ) info = "Reached leaf node, max depth reached.";
 
 trainingLog << info << " Depth: " << depth << " NumSamples: " << trainingData.getNumSamples();
 
 trainingLog << " Class Probabilities: ";
 for(UINT k=0; k<classProbs.getSize(); k++){
 trainingLog << classProbs[k] << " ";
 }
 trainingLog << std::endl;
 
 return node;
 }
 
 //Compute the best spilt point
 UINT featureIndex = 0;
 Float minError = 0;
 
 if( !node->computeBestSplit( trainingMode, numSplittingSteps, trainingData, features, classLabels, featureIndex, minError ) ){
 delete node;
 return NULL;
 }
 
 trainingLog << "Depth: " << depth << " FeatureIndex: " << featureIndex << " MinError: " << minError;
 trainingLog << " Class Probabilities: ";
 for(UINT k=0; k<classProbs.getSize(); k++){
 trainingLog << classProbs[k] << " ";
 }
 trainingLog << std::endl;
 
 //Remove the selected feature so we will not use it again
 if( removeFeaturesAtEachSplit ){
 for(UINT i=0; i<features.getSize(); i++){
 if( features[i] == featureIndex ){
 features.erase( features.begin()+i );
 break;
 }
 }
 }
 
 //Split the data into a left and right dataset
 ClassificationData lhs(N);
 ClassificationData rhs(N);
 
 //Reserve the memory to speed up the allocation of large datasets
 lhs.reserve( M );
 rhs.reserve( M );
 
 for(UINT i=0; i<M; i++){
 if( node->predict_( trainingData[i].getSample() ) ){
 rhs.addSample(trainingData[i].getClassLabel(), trainingData[i].getSample());
 }else lhs.addSample(trainingData[i].getClassLabel(), trainingData[i].getSample());
 }
 
 //Clear the parent dataset so we do not run out of memory with very large datasets (with very deep trees)
 trainingData.clear();
 
 //Get the new node IDs for the children
 UINT leftNodeID = ++nodeID;
 UINT rightNodeID = ++nodeID;
 
 //Run the recursive tree building on the children
 node->setLeftChild( buildTree( lhs, node, features, classLabels, leftNodeID ) );
 node->setRightChild( buildTree( rhs, node, features, classLabels, rightNodeID ) );
 
 //Build the null clusters for the rhs and lhs nodes if null rejection is enabled
 if( useNullRejection ){
 nodeClusters[ leftNodeID ] = lhs.getMean();
 nodeClusters[ rightNodeID ] = rhs.getMean();
 }
 
 return node;
}

Float DecisionTree::getNodeDistance( const VectorFloat &x, const UINT nodeID ){
 
 //Use the node ID to find the node cluster
 std::map< UINT,VectorFloat >::iterator iter = nodeClusters.find( nodeID );
 
 //If we failed to find a match, return NAN
 if( iter == nodeClusters.end() ) return NAN;
 
 //Compute the distance between the input and the node cluster
 return getNodeDistance( x, iter->second );
}

Float DecisionTree::getNodeDistance( const VectorFloat &x, const VectorFloat &y ){
 
 Float distance = 0;
 const UINT N = x.getSize();
 
 for(UINT i=0; i<N; i++){
 distance += MLBase::SQR( x[i] - y[i] );
 }
 
 //Return the squared Euclidean distance instead of actual Euclidean distance as this is faster and just as useful
 return distance;
}

Tree::TrainingMode DecisionTree::getTrainingMode() const{
 return trainingMode;
}

UINT DecisionTree::getNumSplittingSteps()const{
 return numSplittingSteps;
}

UINT DecisionTree::getMinNumSamplesPerNode()const{
 return minNumSamplesPerNode;
}

UINT DecisionTree::getMaxDepth()const{
 return maxDepth;
}

UINT DecisionTree::getPredictedNodeID()const{
 
 if( tree == NULL ){
 return 0;
 }
 
 return tree->getPredictedNodeID();
}

bool DecisionTree::getRemoveFeaturesAtEachSplit() const{
 return removeFeaturesAtEachSplit;
}

bool DecisionTree::setTrainingMode(const Tree::TrainingMode trainingMode){ 
 if( trainingMode >= Tree::BEST_ITERATIVE_SPILT && trainingMode < Tree::NUM_TRAINING_MODES ){
 this->trainingMode = trainingMode;
 return true;
 }
 warningLog << __GRT_LOG__ << " Unknown trainingMode: " << trainingMode << std::endl;
 return false;
}

bool DecisionTree::setNumSplittingSteps(const UINT numSplittingSteps){
 if( numSplittingSteps > 0 ){
 this->numSplittingSteps = numSplittingSteps;
 return true;
 }
 warningLog << __GRT_LOG__ << " The number of splitting steps must be greater than zero!" << std::endl;
 return false;
}

bool DecisionTree::setMinNumSamplesPerNode(const UINT minNumSamplesPerNode){
 if( minNumSamplesPerNode > 0 ){
 this->minNumSamplesPerNode = minNumSamplesPerNode;
 return true;
 }
 warningLog << __GRT_LOG__ << " The minimum number of samples per node must be greater than zero!" << std::endl;
 return false;
}

bool DecisionTree::setMaxDepth(const UINT maxDepth){
 if( maxDepth > 0 ){
 this->maxDepth = maxDepth;
 return true;
 }
 warningLog << __GRT_LOG__ << " The maximum depth must be greater than zero!" << std::endl;
 return false;
}

bool DecisionTree::setRemoveFeaturesAtEachSplit(const bool removeFeaturesAtEachSplit){
 this->removeFeaturesAtEachSplit = removeFeaturesAtEachSplit;
 return true;
}

bool DecisionTree::setRemoveFeaturesAtEachSpilt(const bool removeFeaturesAtEachSpilt){
 return setRemoveFeaturesAtEachSplit(removeFeaturesAtEachSpilt);
}

bool DecisionTree::loadLegacyModelFromFile_v1( std::fstream &file ){
 
 std::string word;
 UINT tempTrainingMode = 0;
 
 file >> word;
 if(word != "NumFeatures:"){
 errorLog << __GRT_LOG__ << " Could not find NumFeatures!" << std::endl;
 return false;
 }
 file >> numInputDimensions;
 
 file >> word;
 if(word != "NumClasses:"){
 errorLog << __GRT_LOG__ << " Could not find NumClasses!" << std::endl;
 return false;
 }
 file >> numClasses;
 
 file >> word;
 if(word != "UseScaling:"){
 errorLog << __GRT_LOG__ << " Could not find UseScaling!" << std::endl;
 return false;
 }
 file >> useScaling;
 
 file >> word;
 if(word != "UseNullRejection:"){
 errorLog << __GRT_LOG__ << " Could not find UseNullRejection!" << std::endl;
 return false;
 }
 file >> useNullRejection;
 
 if( useScaling ){
 //Resize the ranges buffer
 ranges.resize( numInputDimensions );
 
 file >> word;
 if(word != "Ranges:"){
 errorLog << __GRT_LOG__ << " Could not find the Ranges!" << std::endl;
 return false;
 }
 for(UINT n=0; n<ranges.size(); n++){
 file >> ranges[n].minValue;
 file >> ranges[n].maxValue;
 }
 }
 
 file >> word;
 if(word != "NumSplittingSteps:"){
 errorLog << __GRT_LOG__ << " Could not find the NumSplittingSteps!" << std::endl;
 return false;
 }
 file >> numSplittingSteps;
 
 file >> word;
 if(word != "MinNumSamplesPerNode:"){
 errorLog << __GRT_LOG__ << " Could not find the MinNumSamplesPerNode!" << std::endl;
 return false;
 }
 file >> minNumSamplesPerNode;
 
 file >> word;
 if(word != "MaxDepth:"){
 errorLog << __GRT_LOG__ << " Could not find the MaxDepth!" << std::endl;
 return false;
 }
 file >> maxDepth;
 
 file >> word;
 if(word != "RemoveFeaturesAtEachSpilt:"){
 errorLog << __GRT_LOG__ << " Could not find the RemoveFeaturesAtEachSpilt!" << std::endl;
 return false;
 }
 file >> removeFeaturesAtEachSplit;
 
 file >> word;
 if(word != "TrainingMode:"){
 errorLog << __GRT_LOG__ << " Could not find the TrainingMode!" << std::endl;
 return false;
 }
 file >> tempTrainingMode;
 trainingMode = static_cast<Tree::TrainingMode>(tempTrainingMode);
 
 file >> word;
 if(word != "TreeBuilt:"){
 errorLog << __GRT_LOG__ << " Could not find the TreeBuilt!" << std::endl;
 return false;
 }
 file >> trained;
 
 if( trained ){
 file >> word;
 if(word != "Tree:"){
 errorLog << __GRT_LOG__ << " Could not find the Tree!" << std::endl;
 return false;
 }
 
 //Create a new DTree
 tree = new DecisionTreeNode;
 
 if( tree == NULL ){
 clear();
 errorLog << __GRT_LOG__ << " Failed to create new DecisionTreeNode!" << std::endl;
 return false;
 }
 
 tree->setParent( NULL );
 if( !tree->load( file ) ){
 clear();
 errorLog << __GRT_LOG__ << " Failed to load tree from file!" << std::endl;
 return false;
 }
 }
 
 return true;
}

bool DecisionTree::loadLegacyModelFromFile_v2( std::fstream &file ){
 
 std::string word;
 UINT tempTrainingMode = 0;
 
 //Load the base settings from the file
 if( !Classifier::loadBaseSettingsFromFile(file) ){
 errorLog << "load(string filename) - Failed to load base settings from file!" << std::endl;
 return false;
 }
 
 file >> word;
 if(word != "NumSplittingSteps:"){
 errorLog << "load(string filename) - Could not find the NumSplittingSteps!" << std::endl;
 return false;
 }
 file >> numSplittingSteps;
 
 file >> word;
 if(word != "MinNumSamplesPerNode:"){
 errorLog << "load(string filename) - Could not find the MinNumSamplesPerNode!" << std::endl;
 return false;
 }
 file >> minNumSamplesPerNode;
 
 file >> word;
 if(word != "MaxDepth:"){
 errorLog << "load(string filename) - Could not find the MaxDepth!" << std::endl;
 return false;
 }
 file >> maxDepth;
 
 file >> word;
 if(word != "RemoveFeaturesAtEachSpilt:"){
 errorLog << "load(string filename) - Could not find the RemoveFeaturesAtEachSpilt!" << std::endl;
 return false;
 }
 file >> removeFeaturesAtEachSplit;
 
 file >> word;
 if(word != "TrainingMode:"){
 errorLog << "load(string filename) - Could not find the TrainingMode!" << std::endl;
 return false;
 }
 file >> tempTrainingMode;
 trainingMode = static_cast<Tree::TrainingMode>(tempTrainingMode);
 
 file >> word;
 if(word != "TreeBuilt:"){
 errorLog << "load(string filename) - Could not find the TreeBuilt!" << std::endl;
 return false;
 }
 file >> trained;
 
 if( trained ){
 file >> word;
 if(word != "Tree:"){
 errorLog << "load(string filename) - Could not find the Tree!" << std::endl;
 return false;
 }
 
 //Create a new DTree
 tree = dynamic_cast<DecisionTreeNode*>( new DecisionTreeNode );
 
 if( tree == NULL ){
 clear();
 errorLog << "load(fstream &file) - Failed to create new DecisionTreeNode!" << std::endl;
 return false;
 }
 
 tree->setParent( NULL );
 if( !tree->load( file ) ){
 clear();
 errorLog << "load(fstream &file) - Failed to load tree from file!" << std::endl;
 return false;
 }
 
 //Recompute the null rejection thresholds
 recomputeNullRejectionThresholds();
 
 //Resize the prediction results to make sure it is setup for realtime prediction
 maxLikelihood = DEFAULT_NULL_LIKELIHOOD_VALUE;
 bestDistance = DEFAULT_NULL_DISTANCE_VALUE;
 classLikelihoods.resize(numClasses,DEFAULT_NULL_LIKELIHOOD_VALUE);
 classDistances.resize(numClasses,DEFAULT_NULL_DISTANCE_VALUE);
 }
 
 return true;
}

bool DecisionTree::loadLegacyModelFromFile_v3( std::fstream &file ){
 
 std::string word;
 UINT tempTrainingMode = 0;
 
 //Load the base settings from the file
 if( !Classifier::loadBaseSettingsFromFile(file) ){
 errorLog << "load(string filename) - Failed to load base settings from file!" << std::endl;
 return false;
 }
 
 file >> word;
 if(word != "NumSplittingSteps:"){
 errorLog << "load(string filename) - Could not find the NumSplittingSteps!" << std::endl;
 return false;
 }
 file >> numSplittingSteps;
 
 file >> word;
 if(word != "MinNumSamplesPerNode:"){
 errorLog << "load(string filename) - Could not find the MinNumSamplesPerNode!" << std::endl;
 return false;
 }
 file >> minNumSamplesPerNode;
 
 file >> word;
 if(word != "MaxDepth:"){
 errorLog << "load(string filename) - Could not find the MaxDepth!" << std::endl;
 return false;
 }
 file >> maxDepth;
 
 file >> word;
 if(word != "RemoveFeaturesAtEachSpilt:"){
 errorLog << "load(string filename) - Could not find the RemoveFeaturesAtEachSpilt!" << std::endl;
 return false;
 }
 file >> removeFeaturesAtEachSplit;
 
 file >> word;
 if(word != "TrainingMode:"){
 errorLog << "load(string filename) - Could not find the TrainingMode!" << std::endl;
 return false;
 }
 file >> tempTrainingMode;
 trainingMode = static_cast<Tree::TrainingMode>(tempTrainingMode);
 
 file >> word;
 if(word != "TreeBuilt:"){
 errorLog << "load(string filename) - Could not find the TreeBuilt!" << std::endl;
 return false;
 }
 file >> trained;
 
 if( trained ){
 file >> word;
 if(word != "Tree:"){
 errorLog << "load(string filename) - Could not find the Tree!" << std::endl;
 return false;
 }
 
 //Create a new DTree
 tree = new DecisionTreeNode;
 
 if( tree == NULL ){
 clear();
 errorLog << "load(fstream &file) - Failed to create new DecisionTreeNode!" << std::endl;
 return false;
 }
 
 tree->setParent( NULL );
 if( !tree->load( file ) ){
 clear();
 errorLog << "load(fstream &file) - Failed to load tree from file!" << std::endl;
 return false;
 }
 
 //Load the null rejection data if needed
 if( useNullRejection ){
 
 UINT numNodes = 0;
 classClusterMean.resize( numClasses );
 classClusterStdDev.resize( numClasses );
 
 file >> word;
 if(word != "ClassClusterMean:"){
 errorLog << "load(string filename) - Could not find the ClassClusterMean header!" << std::endl;
 return false;
 }
 for(UINT k=0; k<numClasses; k++){
 file >> classClusterMean[k];
 }
 
 file >> word;
 if(word != "ClassClusterStdDev:"){
 errorLog << "load(string filename) - Could not find the ClassClusterStdDev header!" << std::endl;
 return false;
 }
 for(UINT k=0; k<numClasses; k++){
 file >> classClusterStdDev[k];
 }
 
 file >> word;
 if(word != "NumNodes:"){
 errorLog << "load(string filename) - Could not find the NumNodes header!" << std::endl;
 return false;
 }
 file >> numNodes;
 
 file >> word;
 if(word != "NodeClusters:"){
 errorLog << "load(string filename) - Could not find the NodeClusters header!" << std::endl;
 return false;
 }
 
 UINT nodeID = 0;
 VectorFloat cluster( numInputDimensions );
 for(UINT i=0; i<numNodes; i++){
 
 //load the nodeID
 file >> nodeID;
 
 for(UINT j=0; j<numInputDimensions; j++){
 file >> cluster[j];
 }
 
 //Add the cluster to the cluster nodes map
 nodeClusters[ nodeID ] = cluster;
 }
 
 //Recompute the null rejection thresholds
 recomputeNullRejectionThresholds();
 }
 
 //Resize the prediction results to make sure it is setup for realtime prediction
 maxLikelihood = DEFAULT_NULL_LIKELIHOOD_VALUE;
 bestDistance = DEFAULT_NULL_DISTANCE_VALUE;
 classLikelihoods.resize(numClasses,DEFAULT_NULL_LIKELIHOOD_VALUE);
 classDistances.resize(numClasses,DEFAULT_NULL_DISTANCE_VALUE);
 }
 
 return true;
}

GRT_END_NAMESPACE