tree.h

Go to the documentation of this file.

#ifndef _TREE_H_
#define _TREE_H_
#include "librf/types.h"
#include "librf/tree_node.h"
#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <math.h>
using namespace std;

namespace librf {

class InstanceSet;
class weight_list;
class DiscreteDist;
class Instance;

class Tree {
    public:
        Tree(istream& in);
        Tree(const InstanceSet& set, weight_list* weights,
             int K, uchar max_depth=16, int min_size = 1,
             float min_gain = 0, unsigned int seed =0);
         ~Tree();  // clean up 
        int predict(const Instance& c) const;
        int predict(const InstanceSet& set, int instance_no) const;
        // void write_dot(const string& s) const;
        float training_accuracy() const;
        // predict all the instances in testset and return the accuracy
        float testing_accuracy(const InstanceSet& testset) const;
        float oob_accuracy() const;
        void oob_cases(weight_list* counts, weight_list* correct) const;

        void variable_importance(map<int, float>* scores, unsigned int* seed) const;
        void print() const;
        // do all the work -- separated this from constructor to 
        // facilitate threading
        void grow();
        void write(ostream& o) const;
        void read(istream& i);
    private:
        void copy_instances();
        void move_data(tree_node* n, uint16 split_attr, uint16 split_idx);
        void find_best_split(tree_node* n,
                             const vector<int>& attrs,
                             int* split_attr, int* split_idx,
                             float* split_point, float* split_gain);
        void find_best_split_for_attr(tree_node* n,
                                      int attr,
                                      float prior,
                                      int* split_idx,
                                      float *split_point,
                                      float* best_gain);

        // Node marking
        void mark_build(tree_node* n, uint16 start, uint16 size, uchar depth);
        void mark_terminal(tree_node* n);
        void mark_split(tree_node* n, uint16 split_attr, float split_point);

        void build_tree(int min_size);
        int build_node(uint16 node_num, uint16 min_size);
        void print_node(int n) const;

        // inline convenience functions for
        // traversing nodes
        uint32 parent(uint32 node_num) const {
          return uint32(floor((node_num - 1) / 2.0));
        }
        uint32 left_child(uint32 node_num) const {
          return 2 * node_num + 1;
        }
        uint32 right_child(uint32 node_num) const {
          return 2 * node_num + 2;
        }

        void permuteOOB(int m, double *x);

        vector<tree_node> nodes_;
        vector<uint16> active_nodes_;
        set<uint16> vars_used_;
        uint16 terminal_nodes_;
        uint16 split_nodes_;
        // get sorted indices
        // Const reference to instance set -- we don't get to delete it
        const InstanceSet& set_;
        // array of instance nums sorted by attributes 
        // this is the block array that stores which instances belong to
        // which node
        // ex: sorted_inum_[attr*stride + start]
        // uint16 * sorted_inum_;
        //
        // Turns out there is not much of a gain in batch allocating the
        // 2d array (perhaps because, we only access a single column at a time)
        uint16** sorted_inum_;
        // label population 
        // uchar * sorted_labels_; necessary?
        // A single weight list for all of the instances 
        weight_list* weight_list_;
        // Depth of current tree
        uint16 max_depth_;
        uint16 K_;
        uint16 min_size_;
        float min_gain_;
        // scratch space
        int* temp;
        uchar* move_left;
        uint16 num_instances_;
        uint16 num_attributes_;
        uint16 stride_;
        unsigned int rand_seed_;
        // Constants
        static const int kLeft;
        static const int kRight;
};

} // namespace
#endif

---