C++实现决策树ID3算法：从数学原理到工程实践

1次阅读

没有评论

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

决策树是机器学习中经典的分类与回归方法，其核心思想是通过对特征值的不断划分来构建树形结构。ID3 算法作为最早的决策树算法之一，主要特点包括：

仅适用于离散特征
采用信息增益作为划分标准
通过递归方式构建树结构

决策树 ID3 算法的理论基础来自信息论中的熵概念。我们先理解几个关键指标：

信息熵 (Entropy)：度量样本集合纯度的指标，定义为：
```
H(D) = -Σ(p_k * log₂p_k)
```
其中 p_k 表示第 k 类样本在总样本中的比例
条件熵 (Conditional Entropy)：在已知特征 A 的条件下，数据集 D 的熵：
```
H(D|A) = Σ(|D_v|/|D| * H(D_v))
```
信息增益 (Information Gain)：特征 A 对训练集 D 的信息增益：
```
Gain(D,A) = H(D) - H(D|A)
```

ID3：仅处理离散特征，使用信息增益，易产生过拟合
C4.5：改进 ID3，可处理连续特征，使用信息增益比
CART：可分类可回归，使用基尼系数，二叉树结构

我们首先定义决策树节点的数据结构：

class TreeNode {
public:
    std::string feature; // 划分特征
    std::unordered_map<std::string, std::shared_ptr<TreeNode>> children; // 子节点
    std::string label; // 叶节点的类别标签
    bool isLeaf = false;

    // 现代 C ++ 特性：使用智能指针管理内存
    using TreeNodePtr = std::shared_ptr<TreeNode>;
};

计算信息增益是 ID3 算法的核心，优化实现如下：

double calculateInformationGain(const Dataset& data, 
                               const std::string& feature) {double entropyBefore = calculateEntropy(data);
    double entropyAfter = 0.0;

    // 获取该特征所有可能取值
    auto featureValues = getUniqueValues(data, feature);

    for (const auto& value : featureValues) {auto subset = getSubsetByFeature(data, feature, value);
        double weight = static_cast<double>(subset.size()) / data.size();
        entropyAfter += weight * calculateEntropy(subset);
    }

    return entropyBefore - entropyAfter;
}

决策树的构建采用递归方式，注意终止条件：

TreeNodePtr buildTree(const Dataset& data, 
                     const FeatureList& features) {
    // 终止条件 1：所有样本属于同一类别
    if (allSameClass(data)) {auto node = std::make_shared<TreeNode>();
        node->isLeaf = true;
        node->label = getMajorityClass(data);
        return node;
    }

    // 终止条件 2：没有更多特征可用于划分
    if (features.empty()) {auto node = std::make_shared<TreeNode>();
        node->isLeaf = true;
        node->label = getMajorityClass(data);
        return node;
    }

    // 选择最佳划分特征
    string bestFeature = selectBestFeature(data, features);

    // 创建节点
    auto node = std::make_shared<TreeNode>();
    node->feature = bestFeature;

    // 递归构建子树
    auto featureValues = getUniqueValues(data, bestFeature);
    for (const auto& value : featureValues) {auto subset = getSubsetByFeature(data, bestFeature, value);
        if (subset.empty()) {auto leaf = std::make_shared<TreeNode>();
            leaf->isLeaf = true;
            leaf->label = getMajorityClass(data);
            node->children[value] = leaf;
        } else {
            auto newFeatures = features;
            newFeatures.erase(bestFeature);
            node->children[value] = buildTree(subset, newFeatures);
        }
    }

    return node;
}

以下是完整的 C ++ 实现框架（部分代码省略）：

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>
#include <memory>
#include <algorithm>
#include <cmath>

// 数据结构定义
struct DataSample {
    std::unordered_map<std::string, std::string> features;
    std::string label;
};

using Dataset = std::vector<DataSample>;
using FeatureList = std::vector<std::string>;

// 决策树节点类
class TreeNode {// 如前文定义};

// 核心算法实现
class ID3DecisionTree {
public:
    void train(const Dataset& data, const FeatureList& features) {root_ = buildTree(data, features);
    }

    std::string predict(const DataSample& sample) {// 预测实现}

private:
    TreeNode::TreeNodePtr root_;

    // 各种辅助方法
    double calculateEntropy(const Dataset& data) {// 熵计算实现}

    // 其他方法...
};

int main() {
    // 示例数据集
    Dataset trainingData = {{{"Outlook":"Sunny", "Temperature":"Hot", "Humidity":"High"}, "No"},
        // 更多数据...
    };

    FeatureList features = {"Outlook", "Temperature", "Humidity"};

    ID3DecisionTree tree;
    tree.train(trainingData, features);

    // 测试预测
    DataSample testSample{{"Outlook":"Rain", "Temperature":"Mild", "Humidity":"High"}, ""};
    std::cout << "Prediction:" << tree.predict(testSample) << std::endl;

    return 0;
}

虽然 ID3 原生不支持连续特征，但可以通过离散化处理：