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

1次阅读

没有评论

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

决策树是一种模仿人类决策过程的树形结构，而 ID3 算法是最经典的决策树构建算法之一。理解它的核心在于掌握两个关键概念：信息熵和条件熵。

信息熵（Entropy）：度量数据不确定性的指标，公式为：
$$H(D)=-\sum_{k=1}^{K}p_k\log_2 p_k$$
其中 $p_k$ 是第 k 类样本在数据集 D 中的比例
条件熵（Conditional Entropy）：已知特征 X 的条件下，数据集 D 的不确定性：
$$H(D|X)=\sum_{i=1}^{n}\frac{|D_i|}{|D|}H(D_i)$$
信息增益（Information Gain）：选择划分特征的依据：
$$Gain(D,X)=H(D)-H(D|X)$$

ID3 算法就是通过递归选择信息增益最大的特征来构建决策树。

ID3：
仅支持离散特征
使用信息增益作为划分标准
容易偏向取值多的特征
C4.5：
引入信息增益率解决 ID3 的偏向问题
支持连续特征（通过二分法离散化）
支持缺失值处理
CART：
支持分类和回归
使用基尼系数作为划分标准
二叉树结构

对于初学者来说，ID3 算法实现简单，是理解决策树的最佳起点。

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

class DecisionTree {
private:
    std::shared_ptr<TreeNode> root;

    // 计算数据集的信息熵
    double calculateEntropy(const std::vector<std::vector<std::string>>& data, 
                           int labelIndex);

    // 计算特征的信息增益
    double calculateInfoGain(const std::vector<std::vector<std::string>>& data,
                            int featureIndex, int labelIndex);

    // 递归构建决策树
    void buildTree(std::shared_ptr<TreeNode> node, 
                  const std::vector<std::vector<std::string>>& data,
                  const std::vector<std::string>& featureNames,
                  int labelIndex);
public:
    void train(const std::vector<std::vector<std::string>>& data,
              const std::vector<std::string>& featureNames,
              int labelIndex);

    std::string predict(const std::vector<std::string>& sample);
};

计算信息增益是 ID3 中最耗时的部分，我们可以通过以下方式优化：

提前计算类别分布 ：

std::unordered_map<std::string, int> labelCounts;
for (const auto& sample : data) {labelCounts[sample[labelIndex]]++;
}

并行计算各特征的信息增益 ：

std::vector<double> infoGains(featureNames.size());
#pragma omp parallel for
for (int i = 0; i < featureNames.size(); ++i) {if (i != labelIndex) {infoGains[i] = calculateInfoGain(data, i, labelIndex);
    }
}

缓存中间结果 ：对于大型数据集，可以缓存特征值的分布情况。

构建决策树的核心递归函数需要考虑以下终止条件：

所有样本属于同一类别 ：

if (uniqueLabels.size() == 1) {
    node->isLeaf = true;
    node->label = uniqueLabels[0];
    return;
}

没有可用特征 ：

if (remainingFeatures.empty()) {
    node->isLeaf = true;
    node->label = majorityLabel;
    return;
}

样本集为空 （处理边缘情况）：

if (data.empty()) {
    node->isLeaf = true;
    node->label = parentMajorityLabel;
    return;
}

以下是训练方法的完整实现：

void DecisionTree::train(const vector<vector<string>>& data,
                        const vector<string>& featureNames,
                        int labelIndex) {root = make_shared<TreeNode>();
    vector<int> remainingFeatures;

    // 初始化剩余特征（排除标签列）for (int i = 0; i < featureNames.size(); ++i) {if (i != labelIndex) remainingFeatures.push_back(i);
    }

    buildTree(root, data, featureNames, labelIndex, remainingFeatures);
}

void DecisionTree::buildTree(shared_ptr<TreeNode> node,
                           const vector<vector<string>>& data,
                           const vector<string>& featureNames,
                           int labelIndex,
                           vector<int>& remainingFeatures) {
    // 检查终止条件
    auto uniqueLabels = getUniqueValues(data, labelIndex);
    if (uniqueLabels.size() == 1) {
        node->isLeaf = true;
        node->label = uniqueLabels[0];
        return;
    }

    if (remainingFeatures.empty()) {
        node->isLeaf = true;
        node->label = getMajorityLabel(data, labelIndex);
        return;
    }

    // 选择最佳划分特征
    int bestFeatureIndex = -1;
    double maxInfoGain = -1.0;

    for (int featureIndex : remainingFeatures) {double gain = calculateInfoGain(data, featureIndex, labelIndex);
        if (gain > maxInfoGain) {
            maxInfoGain = gain;
            bestFeatureIndex = featureIndex;
        }
    }

    node->featureName = featureNames[bestFeatureIndex];

    // 从剩余特征中移除当前特征
    vector<int> newRemainingFeatures;
    for (int idx : remainingFeatures) {if (idx != bestFeatureIndex) newRemainingFeatures.push_back(idx);
    }

    // 按特征值划分子集
    auto featureValues = getUniqueValues(data, bestFeatureIndex);

    for (const auto& value : featureValues) {auto subset = getSubset(data, bestFeatureIndex, value);

        auto childNode = make_shared<TreeNode>();
        if (subset.empty()) {
            childNode->isLeaf = true;
            childNode->label = getMajorityLabel(data, labelIndex);
        } else {buildTree(childNode, subset, featureNames, labelIndex, newRemainingFeatures);
        }

        node->children[value] = childNode;
    }
}