decision_tree.h

Go to the documentation of this file.

// Author: AI Werkstatt (TM)
// (C) Copyright 2019, AI Werkstatt (TM) www.aiwerkstatt.com. All rights reserved.

#ifndef KOHO_DECISION_TREE_H
#define KOHO_DECISION_TREE_H

#include <fstream>
#include <stack>
#include <algorithm>

#include <cstring> // memset for C-style data from Cython

#include "random_number_generator.h"

namespace koho {

    typedef double         Features_t; // X provided by Python, needs to be double
    typedef long           Classes_t; // y provided by Python, needs to be long
    typedef double         ClassWeights_t; // class weights provided by Python, needs to be double

    typedef double         Histogram_t; // weighted (number of classes) * number of samples

    typedef unsigned long  SamplesIdx_t; // number of samples
    typedef unsigned long  FeaturesIdx_t; // number of features
    typedef unsigned long  ClassesIdx_t; // number of classes
    typedef unsigned long  NodesIdx_t; // number of nodes
    typedef unsigned long  TreeDepthIdx_t; // maximum tree depth (2 ** 31) - 1

    const double  PRECISION_EQUAL = 1e-7; // float == 0.0 as float <= PRECISION_ZERO

// =============================================================================
// Tree
// =============================================================================

    class Node {
    public:

        NodesIdx_t                left_child;
        NodesIdx_t                right_child;
        FeaturesIdx_t             feature;
        int                       NA; // NA as part of the split criterion, -1:NA, 0:left, 1:right
        Features_t                threshold;
        std::vector<Histogram_t>  histogram; // weighted number of samples per class
        double                    impurity; // for inspection (e.g. graphviz visualization)
        double                    improvement; // for feature importances

        Node(NodesIdx_t                       left_child,
             NodesIdx_t                       right_child,
             FeaturesIdx_t                    feature,
             int                              NA,
             Features_t                       threshold,
             const std::vector<Histogram_t>&  histogram,
             double                           impurity,
             double                           improvement);

        void  serialize(std::ofstream& fout);
        static Node  deserialize(std::ifstream& fin);
    };

    class Tree {
    public:

        ClassesIdx_t       n_classes;
        FeaturesIdx_t      n_features;
        TreeDepthIdx_t     max_depth;
        // Nodes
        NodesIdx_t         node_count;
        std::vector<Node>  nodes;


        Tree(ClassesIdx_t   n_classes,
             FeaturesIdx_t  n_features);


        NodesIdx_t  add_node(TreeDepthIdx_t                   depth,
                             NodesIdx_t                       parent_id,
                             bool                             is_left,
                             FeaturesIdx_t                    feature,
                             int                              NA,
                             Features_t                       threshold,
                             const std::vector<Histogram_t>&  histogram,
                             double                           impurity,
                             double                           improvement);


        // Using 1d array addressing for X and y_prob
        // to support efficient Cython bindings to Python using memory views.
        void  predict(Features_t*   X,
                      SamplesIdx_t  n_samples,
                      double*       y_prob);


        void  calculate_feature_importances(double*  importances);

        void  serialize(std::ofstream& fout);
        void  deserialize(std::ifstream& fin);
    };

// =============================================================================
// Impurity Criterion
// =============================================================================

    class GiniCriterion {

    protected:
        ClassesIdx_t              n_classes;
        SamplesIdx_t              n_samples;
        ClassWeights_t*           class_weight;
        // Histograms
        // vectors are created in initialization list
        // - all samples
        std::vector<Histogram_t>  node_weighted_histogram;
        Histogram_t               node_weighted_n_samples;
        double                    node_impurity;
        // - samples with missing values
        std::vector<Histogram_t>  node_weighted_histogram_NA;
        Histogram_t               node_weighted_n_samples_NA;
        double                    node_impurity_NA;
        // - samples with values
        std::vector<Histogram_t>  node_weighted_histogram_values;
        Histogram_t               node_weighted_n_samples_values;
        double                    node_impurity_values;
        SamplesIdx_t              node_pos_NA;
        // - samples with values smaller than threshold (assigned to left child)
        std::vector<Histogram_t>  node_weighted_histogram_threshold_left;
        Histogram_t               node_weighted_n_samples_threshold_left;
        double                    node_impurity_threshold_left;
        // -- plus missing values (assigned to left child)
        Histogram_t               node_weighted_n_samples_threshold_left_NA;
        double                    node_impurity_threshold_left_NA;
        // - samples with values greater than threshold (assigned to right child)
        std::vector<Histogram_t>  node_weighted_histogram_threshold_right;
        Histogram_t               node_weighted_n_samples_threshold_right;
        double                    node_impurity_threshold_right;
        // -- plus missing values (assigned to right child)
        Histogram_t               node_weighted_n_samples_threshold_right_NA;
        double                    node_impurity_threshold_right_NA;
        SamplesIdx_t              node_pos_threshold;

    public:

        GiniCriterion(ClassesIdx_t     n_classes, // required: 2 <= n_classes
                      SamplesIdx_t     n_samples, // required: 2 <= n_samples
                      ClassWeights_t*  class_weight);

        void calculate_node_histogram(Classes_t*                  y,
                                      std::vector<SamplesIdx_t>&  samples,
                                      SamplesIdx_t                start,
                                      SamplesIdx_t                end);


        double  calculate_impurity(std::vector<Histogram_t>&  histogram);


        void calculate_node_impurity();


        void calculate_NA_histogram(Classes_t*                  y,
                                    std::vector<SamplesIdx_t>&  samples,
                                    SamplesIdx_t                pos);


        void calculate_NA_impurity();


        double calculate_NA_impurity_improvement();


        void init_threshold_histograms();


        void init_threshold_values_histograms();


        void update_threshold_histograms(Classes_t*                  y,
                                         std::vector<SamplesIdx_t>&  samples,
                                         SamplesIdx_t                new_pos);


        void calculate_threshold_impurity();


        void calculate_threshold_NA_impurity();


        double calculate_threshold_impurity_improvement();


        double calculate_threshold_values_impurity_improvement();


        double calculate_threshold_NA_left_impurity_improvement();


        double calculate_threshold_NA_right_impurity_improvement();

        std::vector<Histogram_t> get_node_weighted_histogram() {
                                 return GiniCriterion::node_weighted_histogram; }
        double                   get_node_impurity() {
                                 return GiniCriterion::node_impurity; }
        double                   get_node_impurity_NA() {
                                 return GiniCriterion::node_impurity_NA; }
        double                   get_node_impurity_values() {
                                 return GiniCriterion::node_impurity_values; }
        double                   get_node_impurity_threshold_left() {
                                 return GiniCriterion::node_impurity_threshold_left; }
        double                   get_node_impurity_threshold_right() {
                                 return GiniCriterion::node_impurity_threshold_right; }
    };

// =============================================================================
// Node Splitter
// =============================================================================

    class BestSplitter {

    protected:
        FeaturesIdx_t              n_features;
        SamplesIdx_t               n_samples;
        FeaturesIdx_t              max_features;
        unsigned long              max_thresholds;
        RandomState                random_state;
        // Samples
        // samples[start, end] is a LUT to the training data X, y
        // to handle the recursive partitioning and
        // the sorting of the data efficiently.
        std::vector<SamplesIdx_t>  samples; // vector created in initialization list
        SamplesIdx_t               start;
        SamplesIdx_t               end;
    public:
        // Gini Criterion
        GiniCriterion              criterion; // nested object created in initialization list

    public:
        BestSplitter(ClassesIdx_t     n_classes, // required: 2 <= n_classes
                     FeaturesIdx_t    n_features, // required: 1 <= n_features
                     SamplesIdx_t     n_samples, // required: 2 <= n_samples
                     ClassWeights_t*  class_weight,
                     FeaturesIdx_t    max_features, // required: 0 < max_features <= n_features
                     unsigned long    max_thresholds, // required: 0, 1
                     RandomState const& random_state);

        void init_node(Classes_t*    y,
                       SamplesIdx_t  start,
                       SamplesIdx_t  end);

        void split_feature(Features_t*                 X,
                           Classes_t*                  y,
                           std::vector<SamplesIdx_t>&  s,
                           FeaturesIdx_t               feature,
                           int&                        NA,
                           Features_t&                 threshold,
                           SamplesIdx_t&               pos,
                           double&                     improvement);

        void split_feature_extreme_random(Features_t*                 X,
                                          Classes_t*                  y,
                                          std::vector<SamplesIdx_t>&  s,
                                          FeaturesIdx_t               feature,
                                          int&                        NA,
                                          Features_t&                 threshold,
                                          SamplesIdx_t&               pos,
                                          double&                     improvement);


        void split_node(Features_t*     X,
                        Classes_t*      y,
                        FeaturesIdx_t&  feature,
                        int&            NA,
                        Features_t&     threshold,
                        SamplesIdx_t&   pos,
                        double&         improvement);
    };

// =============================================================================
// Tree Builder
// =============================================================================

    class DepthFirstTreeBuilder {

    protected:
        TreeDepthIdx_t  max_depth;
        std::string     missing_values;
        // Best Splitter (and Gini Criterion)
        BestSplitter    splitter; // nested object created in initialization list

    public:

        DepthFirstTreeBuilder(ClassesIdx_t          n_classes,
                              FeaturesIdx_t         n_features,
                              SamplesIdx_t          n_samples,
                              ClassWeights_t*       class_weight,
                              TreeDepthIdx_t        max_depth,
                              FeaturesIdx_t         max_features,
                              unsigned long         max_thresholds,
                              std::string           missing_values,
                              RandomState const&    random_state);


        // Using 1d array addressing for X and y to support efficient Cython bindings to Python using memory views.
        void build(Tree&         tree,
                   Features_t*   X,
                   Classes_t*    y,
                   SamplesIdx_t  n_samples);
    };

// =============================================================================
// Decision Tree Classifier
// =============================================================================

    class DecisionTreeClassifier {

    protected:
        std::vector<std::string>  classes;
        ClassesIdx_t              n_classes;
        std::vector<std::string>  features;
        FeaturesIdx_t             n_features;

        // Hyperparameters
        std::string               class_balance;
        TreeDepthIdx_t            max_depth;
        FeaturesIdx_t             max_features;
        unsigned long             max_thresholds;
        std::string               missing_values;

        // Random Number Generator
        RandomState               random_state;

        // Model
        Tree                      tree_; // underlying estimator

    public:

        DecisionTreeClassifier(std::vector<std::string>  classes,
                               ClassesIdx_t              n_classes,
                               std::vector<std::string>  features,
                               FeaturesIdx_t             n_features,
                               std::string const&        class_balance = "balanced",
                               TreeDepthIdx_t            max_depth = 0,
                               FeaturesIdx_t             max_features = 0,
                               unsigned long             max_thresholds = 0,
                               std::string const&        missing_values = "None",
                               long                      random_state_seed = 0);


        void fit(Features_t*   X,
                 Classes_t*    y,
                 SamplesIdx_t  n_samples);


        void  predict_proba(Features_t*   X,
                            SamplesIdx_t  n_samples,
                            double*       y_prob);


        void  predict(Features_t*   X,
                      SamplesIdx_t  n_samples,
                      Classes_t*    y);


        double score(Features_t*   X,
                     Classes_t*    y,
                     SamplesIdx_t  n_samples);


        void  calculate_feature_importances(double*  importances);


        void  export_graphviz(std::string const& filename, bool rotate=false);

        std::string  export_text();


        void  export_serialize(std::string const& filename);


        static  DecisionTreeClassifier  import_deserialize(std::string const& filename);

        void  serialize(std::ofstream& fout);
        static  DecisionTreeClassifier  deserialize(std::ifstream& fin);
    };

} // namespace koho

#endif