67、C++项目实战：决策树算法

决策树，说白了就是一堆 if-else 的集合体。你想想看，我们平时做判断，不也是“如果天气好就去打球，否则待家里”这种逻辑吗？决策树就是把这种人类直觉，用数学和代码给固化下来。

我个人习惯把决策树看作一个“自动问答机”。你给它一条数据，它就开始问问题：这个特征大于某个值吗？那个特征属于哪个类别？一路问下去，最后落到叶子节点上，给出答案。嗯，就这么简单。

从零开始：决策树的核心思想

决策树的核心就三件事：分裂、停止、剪枝。

• 分裂：选哪个特征，在哪个阈值上切一刀，能让数据分得最“纯”。
• 停止：什么时候不再分裂？比如树太深了，或者节点里样本太少。
• 剪枝：树长太茂盛容易过拟合，得适当砍掉一些分支。

我在项目中遇到过最头疼的问题，就是树长到十几层深，训练集准确率 99%，测试集直接崩到 60%。后来才明白，决策树天生就是过拟合的“好手”，必须用剪枝来约束它。

信息增益 = 父节点熵 - 子节点加权平均熵

手写一个简单的决策树

别急着调库。我建议你先手写一个最简单的版本，哪怕只支持二分类、连续特征。这样你才能真正理解它的运作机制。

下面这个例子，我用 C++ 实现了一个极简决策树。它只做一件事：根据一个特征阈值，把数据分成左右两堆。

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

struct Node {
    double threshold;      // 分裂阈值
    int feature_index;     // 特征索引
    double value;          // 叶子节点的预测值
    Node* left;
    Node* right;
    bool is_leaf;

    Node() : left(nullptr), right(nullptr), is_leaf(false) {}
};

// 计算熵
double entropy(const std::vector<double>& labels) {
    double p = 0.0;
    for (double l : labels) p += l;
    p /= labels.size();
    if (p == 0.0 || p == 1.0) return 0.0;
    return -p * log2(p) - (1 - p) * log2(1 - p);
}

// 简单分裂：找最佳阈值
double find_best_threshold(
    const std::vector<std::vector<double>>& data,
    const std::vector<double>& labels,
    int feat_idx) {

    double best_gain = -1.0;
    double best_thresh = 0.0;
    double parent_entropy = entropy(labels);

    // 收集所有可能的阈值
    std::vector<double> values;
    for (auto& row : data) values.push_back(row[feat_idx]);
    std::sort(values.begin(), values.end());

    for (double thresh : values) {
        std::vector<double> left_labels, right_labels;
        for (size_t i = 0; i < data.size(); ++i) {
            if (data[i][feat_idx] <= thresh)
                left_labels.push_back(labels[i]);
            else
                right_labels.push_back(labels[i]);
        }
        if (left_labels.empty() || right_labels.empty()) continue;

        double gain = parent_entropy -
            (left_labels.size() * entropy(left_labels) +
             right_labels.size() * entropy(right_labels)) / labels.size();

        if (gain > best_gain) {
            best_gain = gain;
            best_thresh = thresh;
        }
    }
    return best_thresh;
}

int main() {
    // 示例数据：两个特征，二分类
    std::vector<std::vector<double>> data = {
        {1.0, 2.0}, {2.0, 3.0}, {3.0, 1.0}, {6.0, 5.0}, {7.0, 8.0}
    };
    std::vector<double> labels = {0, 0, 0, 1, 1};

    double thresh = find_best_threshold(data, labels, 0);
    std::cout << "最佳分裂阈值（特征0）: " << thresh << std::endl;

    return 0;
}

这段代码虽然简陋，但骨架已经出来了。你想想看，只要把这个过程递归下去，就能长成一棵树。我在实际项目中，就是从这个版本开始，一步步加上多特征、多分类、剪枝等功能的。

决策树的完整流程图

下面这张图，是我自己总结的决策树训练流程。每次做项目前，我都会先看一眼这张图，确保思路不乱。

避坑指南：我踩过的三个大坑

决策树看起来简单，但真正用起来，坑不少。我把自己踩过的坑列出来，你遇到了能少走弯路。

实战：用决策树做鸢尾花分类

光说不练假把式。下面我用决策树对经典的鸢尾花数据集做分类。虽然 C++ 没有现成的数据集加载库，但我们可以手动构造一个简化版。

#include <iostream>
#include <vector>
#include <string>
#include <map>

// 简化版鸢尾花数据：只取两个特征（花萼长度、花瓣长度），三类
std::vector<std::vector<double>> iris_data = {
    {5.1, 1.4}, {4.9, 1.4}, {4.7, 1.3},  // setosa
    {7.0, 4.7}, {6.4, 4.5}, {6.9, 4.9},  // versicolor
    {6.3, 6.0}, {5.8, 5.1}, {7.1, 5.9}   // virginica
};
std::vector<std::string> iris_labels = {
    "setosa", "setosa", "setosa",
    "versicolor", "versicolor", "versicolor",
    "virginica", "virginica", "virginica"
};

// 这里省略了完整的决策树类实现（篇幅原因）
// 实际使用时，调用 train() 和 predict() 即可

int main() {
    std::cout << "鸢尾花决策树示例" << std::endl;
    std::cout << "数据量: " << iris_data.size() << " 条" << std::endl;
    std::cout << "类别数: 3 (setosa, versicolor, virginica)" << std::endl;
    return 0;
}

嗯，这里要注意。上面的代码只是数据准备部分。完整的决策树类实现，我建议你把它封装成一个模板类，支持不同的特征类型和标签类型。我在项目中就是这么做的，后面换数据集只需要改数据加载部分，树的核心代码完全不用动。

性能对比：决策树 vs 其他算法

决策树不是万能的。我整理了一个简单的对比表，帮你快速判断什么时候该用它。

你看，决策树的优势在于“可解释性”。我做过一个信贷风控项目，银行要求每个拒绝贷款的决定都必须给出理由。这时候决策树就派上用场了——直接输出“因为收入小于 5000 且 信用分小于 600，所以拒绝”。换成神经网络？你根本解释不了。

总结

决策树算法，说白了就是“分而治之”的思想。它不复杂，但很实用。我建议你从手写一个简单版本开始，理解它的分裂、停止、剪枝三个核心机制。然后再去用现成的库，比如 sklearn 或者自己封装 C++ 版本。

记住，算法是死的，人是活的。别被那些数学公式吓到，动手写几行代码，跑几个例子，你就发现它其实挺亲切的。

公众号:蓝海资料掘金营，微信deep3321