C45Tree.hh

Go to the documentation of this file.

#ifndef _C45TREE_HH_
#define _C45TREE_HH_

#include <rl_common/Random.h>
#include <rl_common/core.hh>
#include <vector>
#include <set>
#include <map>

#define N_C45_EXP 200000
#define N_C45_NODES 2500

#define BUILD_EVERY 0
#define BUILD_ON_ERROR 1
#define BUILD_EVERY_N 2
#define BUILD_ON_TERMINAL 3
#define BUILD_ON_TERMINAL_AND_ERROR 4


class C45Tree: public Classifier {

public:

  C45Tree(int id, int trainMode, int trainFreq, int m, 
          float featPct, Random rng);

  C45Tree(const C45Tree&);

  ~C45Tree();

  // structs to be defined
  struct tree_node;
  struct tree_experience;
  
  void copyTree(tree_node* newNode, tree_node* origNode);

  virtual C45Tree* getCopy();

  struct tree_node {
    int id;

    // split criterion
    int dim;
    float val;
    bool type;

    // set of all outputs seen at this leaf/node
    std::map<float,int> outputs;
    int nInstances;

    // next nodes in tree
    tree_node *l;
    tree_node *r;

    bool leaf;
  };

  struct tree_experience {
    std::vector<float> input;
    float output;
  };
  
  enum splitTypes{
    ONLY,
    CUT
  };

  virtual bool trainInstance(classPair &instance);
  virtual bool trainInstances(std::vector<classPair> &instances);
  virtual void testInstance(const std::vector<float> &input, std::map<float, float>* retval);
  virtual float getConf(const std::vector<float> &input);

  bool buildTree(tree_node* node, const std::vector<tree_experience*> &instances,  bool changed);

  // helper functions
  void initTree();

  bool rebuildTree();

  void initTreeNode(tree_node* node);

  tree_node* traverseTree(tree_node* node, const std::vector<float> &input);

  tree_node* getCorrectChild(tree_node* node, const std::vector<float> &input);

  bool passTest(int dim, float val, bool type, const std::vector<float> &input);

  float calcGainRatio(int dim, float val, bool type,
                       const std::vector<tree_experience*> &instances, float I,
                       std::vector<tree_experience*> &left,
                       std::vector<tree_experience*> &right);

  float* sortOnDim(int dim, const std::vector<tree_experience*> &instances);

  std::set<float> getUniques(int dim, const std::vector<tree_experience*> &instances, float & minVal, float& maxVal);

  void deleteTree(tree_node* node);

  float calcIofP(float* P, int size);

  float calcIforSet(const std::vector<tree_experience*> &instances);

  void printTree(tree_node *t, int level);

  void testPossibleSplits(const std::vector<tree_experience*> &instances, float *bestGainRatio, int *bestDim, 
                          float *bestVal, bool *bestType,
                          std::vector<tree_experience*> *bestLeft, std::vector<tree_experience*> *bestRight);

  bool implementSplit(tree_node* node, float bestGainRatio, int bestDim,
                      float bestVal, bool bestType, 
                      const std::vector<tree_experience*> &left, 
                      const std::vector<tree_experience*> &right, bool changed);

  void compareSplits(float gainRatio, int dim, float val, bool type, 
                     const std::vector<tree_experience*> &left, 
                     const std::vector<tree_experience*> &right,
                     int *nties, float *bestGainRatio, int *bestDim, 
                     float *bestVal, bool *bestType,
                     std::vector<tree_experience*> *bestLeft, 
                     std::vector<tree_experience*> *bestRight);

  void outputProbabilities(tree_node *t, std::map<float, float>* retval);

  bool makeLeaf(tree_node* node);

  tree_node* allocateNode();

  void deallocateNode(tree_node* node);

  void initNodes();


  bool INCDEBUG;
  bool DTDEBUG;
  bool SPLITDEBUG;
  bool STOCH_DEBUG;
  int nExperiences;
  bool NODEDEBUG;
  bool COPYDEBUG;

  float SPLIT_MARGIN;
  float MIN_GAIN_RATIO; 

private:

  const int id;
  
  const int mode;
  const int freq;
  const int M;
  const float featPct; 
  const bool ALLOW_ONLY_SPLITS;

  Random rng;

  int nOutput;
  int nnodes;
  bool hadError;
  int maxnodes;
  int totalnodes;

  std::vector<tree_experience*> experiences;

  tree_experience allExp[N_C45_EXP];

  tree_node allNodes[N_C45_NODES];
  std::vector<int> freeNodes;

  // TREE
  tree_node* root;
  tree_node* lastNode;

};


#endif