从零开始实现决策树——手撕 CART 算法（C++）

本文的 C++ 代码基于 C++ 20 标准（不包含 C++ modules），对于之前的标准，可能需要做一些适配。

CART 分类树和回归树的内容各自在一个类中，分类树为 CartClassifier 类，回归树为 CartRegression 类。

数据结构设计

二叉树设计

// 二叉树结点
struct BinTreeNode {
    std::string threshold_str_;
    double threshold_ = -1;
    std::string feature_name_;
    std::shared_ptr<BinTreeNode> left_ = nullptr;
    std::shared_ptr<BinTreeNode> right_ = nullptr;
    [[nodiscard]] std::shared_ptr<BinTreeNode> copy() const {
        auto node = std::make_shared<BinTreeNode>();
        node->threshold_ = threshold_;
        node->threshold_str_ = threshold_str_;
        node->feature_name_ = feature_name_;
        if(left_) node->left_ = left_->copy();
        if(right_) node->right_ = right_->copy();
        return node;
    }
};

copy 模块用于二叉树结点的深复制，包括复制本身及其所有的子结点。

结点信息设计

struct Info {
    std::shared_ptr<BinTreeNode> tree_;
    size_t num_leaf_ = 0;
    double a = 0;
    std::pair<bool, std::string> key_str_{};
    std::pair<bool, double> key_{};
};

实际上结点信息可以直接存储到二叉树结点 BinTreeNode 中。分开是为了保证代码的语义清晰，易于理解。

分类树

训练

/**
 * @brief
 * 训练决策树
 * @param X 训练集属性值
 * @param y 训练集目标变量
 * @param feature_names 属性名
 * @return 生成的决策树
 */
shared_ptr<BinTreeNode> CartClassifier::train {
    feature_names_ = feature_names;
    
    tree_ = (X, y);
     tree_;
}