C++决策树实现指南：从基础原理到生产环境部署

1次阅读

没有评论

共计 3810 个字符，预计需要花费 10 分钟才能阅读完成。

决策树是一种经典的监督学习算法，通过树状结构对数据进行分类或回归。它模仿人类决策过程，通过一系列 if-then 规则对数据进行划分。决策树的核心优势在于可解释性强，能够直观展示决策逻辑，适合处理数值型和类别型混合数据。

决策树主要由以下组件构成：

根节点：包含所有训练数据的起始节点
内部节点：根据某个特征进行数据划分的节点
叶节点：包含最终预测结果的终端节点
分裂准则：决定如何划分数据的标准（如信息增益、基尼系数等）

性能优势：C++ 的编译执行特性使其在计算密集型任务上具有明显速度优势
内存控制：手动内存管理可以实现更精细的资源利用
系统集成：C++ 代码更容易嵌入到现有生产系统中

内存管理：需要手动处理节点创建和销毁
模板复杂性：泛型编程可能增加代码复杂度
并行实现：多线程优化需要考虑线程安全问题

#include <vector>
#include <memory>
#include <algorithm>
#include <cmath>

// 决策树节点基类
template <typename T>
class TreeNode {
public:
    virtual ~TreeNode() = default;
    virtual T predict(const std::vector<double>& features) = 0;
};

// 内部节点实现
template <typename T>
class InternalNode : public TreeNode<T> {
    int splitFeature;
    double splitValue;
    std::unique_ptr<TreeNode<T>> leftChild;
    std::unique_ptr<TreeNode<T>> rightChild;

public:
    InternalNode(int feature, double value, 
                std::unique_ptr<TreeNode<T>> left,
                std::unique_ptr<TreeNode<T>> right)
        : splitFeature(feature), splitValue(value),
          leftChild(std::move(left)), rightChild(std::move(right)) {}

    T predict(const std::vector<double>& features) override {if (features[splitFeature] <= splitValue) {return leftChild->predict(features);
        }
        return rightChild->predict(features);
    }
};

计算基尼系数（分类任务）

double calculateGini(const std::vector<int>& labels) {
    std::unordered_map<int, int> counts;
    for (int label : labels) {counts[label]++;
    }

    double impurity = 1.0;
    for (const auto& pair : counts) {double prob = static_cast<double>(pair.second) / labels.size();
        impurity -= prob * prob;
    }
    return impurity;
}

寻找最佳分裂点

struct SplitResult {
    int feature;
    double value;
    double score;
};

SplitResult findBestSplit(const std::vector<std::vector<double>>& features,
                         const std::vector<int>& labels) {
    SplitResult bestSplit;
    bestSplit.score = std::numeric_limits<double>::max();

    for (int feature = 0; feature < features[0].size(); ++feature) {
        // 获取当前特征的所有可能分割点
        std::vector<double> values;
        for (const auto& sample : features) {values.push_back(sample[feature]);
        }
        std::sort(values.begin(), values.end());

        // 评估每个可能的分割点
        for (size_t i = 1; i < values.size(); ++i) {double splitValue = (values[i-1] + values[i]) / 2.0;

            // 分割数据集并计算基尼系数
            std::vector<int> leftLabels, rightLabels;
            for (size_t j = 0; j < features.size(); ++j) {if (features[j][feature] <= splitValue) {leftLabels.push_back(labels[j]);
                } else {rightLabels.push_back(labels[j]);
                }
            }

            double score = (leftLabels.size() * calculateGini(leftLabels) +
                           rightLabels.size() * calculateGini(rightLabels)) /
                           features.size();

            if (score < bestSplit.score) {bestSplit = {feature, splitValue, score};
            }
        }
    }
    return bestSplit;
}

使用智能指针管理节点生命周期
预分配内存减少动态分配开销
实现移动语义避免不必要的拷贝

#include <thread>
#include <mutex>

std::mutex mtx;

void parallelFindBestSplit(const std::vector<std::vector<double>>& features,
                          const std::vector<int>& labels,
                          int startFeature, int endFeature,
                          SplitResult& localBest) {for (int feature = startFeature; feature < endFeature; ++feature) {
        // ... 同单线程版本的分裂点评估代码 ...

        std::lock_guard<std::mutex> lock(mtx);
        if (score < localBest.score) {localBest = {feature, splitValue, score};
        }
    }
}

SplitResult parallelBestSplit(const std::vector<std::vector<double>>& features,
                             const std::vector<int>& labels,
                             int numThreads = 4) {
    std::vector<std::thread> threads;
    std::vector<SplitResult> threadResults(numThreads);

    int featuresPerThread = features[0].size() / numThreads;

    for (int i = 0; i < numThreads; ++i) {
        int start = i * featuresPerThread;
        int end = (i == numThreads - 1) ? features[0].size() : start + featuresPerThread;

        threads.emplace_back(parallelFindBestSplit,
                            std::cref(features), std::cref(labels),
                            start, end, std::ref(threadResults[i]));
    }

    for (auto& t : threads) {t.join();
    }

    // 合并各线程结果
    SplitResult globalBest;
    for (const auto& res : threadResults) {if (res.score < globalBest.score) {globalBest = res;}
    }
    return globalBest;
}