drwnDecisionTree.h

/******************************************************************************
** DARWIN: A FRAMEWORK FOR MACHINE LEARNING RESEARCH AND DEVELOPMENT
** Distributed under the terms of the BSD license (see the LICENSE file)
** Copyright (c) 2007-2015, Stephen Gould
** All rights reserved.
**
******************************************************************************
** FILENAME:    drwnDecisionTree.h
** AUTHOR(S):   Stephen Gould <stephen.gould@anu.edu.au>
**
*****************************************************************************/

#pragma once

#include <cstdlib>
#include <vector>

#include "drwnBase.h"
#include "drwnClassifier.h"

using namespace std;

// drwnTreeSplitCriterion ----------------------------------------------------

typedef enum _drwnTreeSplitCriterion {
    DRWN_DT_SPLIT_ENTROPY, DRWN_DT_SPLIT_MISCLASS, DRWN_DT_SPLIT_GINI
} drwnTreeSplitCriterion;

// drwnDecisionTree ---------------------------------------------------------

class drwnDecisionTree : public drwnClassifier {
 public:
    friend class drwnDecisionTreeThread;
    friend class drwnDecisionTreeConfig;
    friend class drwnBoostedClassifier;
    friend class drwnRandomForest;

 public:
    static int MAX_DEPTH;          
    static int MAX_FEATURE_THRESHOLDS; 
    static int MIN_SAMPLES;       
    static double LEAKAGE;        
    static drwnTreeSplitCriterion SPLIT_CRITERION; 
    static bool CACHE_SORTED_INDEXES; 

 protected:
    int _splitIndx;                
    double _splitValue;            
    drwnDecisionTree *_leftChild;  
    drwnDecisionTree *_rightChild; 
    Eigen::VectorXd _scores;       
    int _predictedClass;           
    
    int _maxDepth;                 

 public:
    drwnDecisionTree();
    drwnDecisionTree(unsigned n, unsigned k = 2);
    drwnDecisionTree(const drwnDecisionTree &c);
    ~drwnDecisionTree();

    // access functions
    virtual const char *type() const { return "drwnDecisionTree"; }
    virtual drwnDecisionTree *clone() const { return new drwnDecisionTree(*this); }

    // initialization
    virtual void initialize(unsigned n, unsigned k = 2);

    // i/o
    virtual bool save(drwnXMLNode& node) const;
    virtual bool load(drwnXMLNode& node);

    // training
    using drwnClassifier::train;
    virtual double train(const drwnClassifierDataset& dataset);
    virtual double train(const vector<vector<double> >& features,
        const vector<int>& targets);
    virtual double train(const vector<vector<double> >& features,
        const vector<int>& targets, const vector<double>& weights);

    // evaluation (log-probability)
    using drwnClassifier::getClassScores;
    virtual void getClassScores(const vector<double>& features,
        vector<double>& outputScores) const;

    // evaluation (classification)
    using drwnClassifier::getClassification;
    virtual int getClassification(const vector<double>& features) const;

 protected:
    // evaluation
    const Eigen::VectorXd &evaluate(const Eigen::VectorXd& x) const;

    // training
    static void computeSortedFeatureIndex(const vector<vector<double> >& x,
        const drwnBitArray& sampleIndex, int featureIndx, vector<int>& featureSortIndex);
    static void computeSortedFeatureIndex(const vector<vector<double> >& x,
        vector<vector<int> >& sortIndex);
    void learnDecisionTree(const vector<vector<double> >& x, const vector<int>& y,
        const vector<double>& w, const vector<vector<int> >& sortIndex,
        const drwnBitArray& sampleIndex);    
};