决策树(信息增益)

决策树是一种监督学习算法，通过树形结构对样本进行分类或回归。每个内部节点表示一个特征上的测试，每个分支代表一个测试输出，每个叶节点存放一个类别（分类）或数值（回归）。

基础概念

信息熵

熵表示随机变量不确定性的度量，熵越大，随机变量的不确定性就越大，各类别分布均匀。

熵越小，数据越纯净，越倾向于某一类。

对一个包含个类别的离散随机变量，其概率分布为，则信息熵可定义为：

单位为bit。

信息增益

信息增益表示得到一类特征的信息，而使得另一类的信息的不确定性减少的程度。

其中：

• 为划分前数据集的熵
• 为按特征划分后各子集的加权平均熵

信息增益越大，说明使用特征划分后数据集提纯提升越多，因此选择信息增益最大的特征作为当前节点的分裂特征。

应用示例

基于 ID3 算法的决策树分类器：

假设你是一个户外运动俱乐部的组织者，每天需要根据天气情况决定是否适合组织会员进行网球活动。你收集了过去14天的天气数据，包括四个特征和一个标签：

• 特征：
  • outlook（天气状况）：取值为 Sunny（晴天）、Overcast（阴天）、Rainy（雨天）。
  • temperature（温度）：取值为 Hot（热）、Mild（温和）、Cool（凉爽）。
  • humidity（湿度）：取值为 High（高）、Normal（正常）。
  • windy（是否有风）：取值为 True（有风）、False（无风）。
• 标签（play）：是否适合打球，取值为 Yes（适合）或 No（不适合）。

构建一个决策树模型，能够根据当天的天气特征（outlook、temperature、humidity、windy）自动预测是否适合进行网球活动。这样，未来某天只要输入天气状况，模型就能给出建议，帮助组织者快速决策。

数据准备(输入)：

• 训练数据集
• 特征属性集

递归创建决策树：

步骤1：检查终止条件

• 数据集为空，返回空的叶节点
• 所有样本属于同一类别，生成叶节点，且标签为该类别
• 没有可用特征，生成叶节点，类别标签取当前数据集的多数类

步骤2：选择最佳分裂特征

• 计算每个特征的信息增益
  • 计算当前数据集的熵
  • 按特征取值划分子集，计算加权平均熵(条件熵)
  • 信息增益 = 原熵 - 条件熵
• 找出最大增益的特征

步骤3：按最佳特征划分数据

• 获取特征值到子集的映射
• 从可用特征列表中移除已选特征

步骤4：递归构建子树

• 遍历每个特征值->子数据集键值对
  • 以该子数据集和可用哦该特征列表，递归调用构建决策树接口，返回子树节点
  • 将子树节点作为当前节点的子节点，与对应的特征值绑定

步骤5：返回当前节点

• 节点中保存了分裂特征索引和子节点映射

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

using namespace std;

// 数据集类型：每行为一个样本，最后一列为标签，其余为特征值
using Data = vector<vector<string>>;

// 决策树节点
struct TreeNode {
    int feature_idx;                // 分裂使用的特征索引（-1 表示叶节点）
    string label;                   // 叶节点的类别（内部节点为空）
    map<string, shared_ptr<TreeNode>> children; // 特征值 -> 子节点
};

// 计算数据集的熵
double entropy(const Data& data) {
    map<string, int> freq;
    for (const auto& row : data) {
        freq[row.back()]++;          // 最后一列是标签
    }
    double ent = 0.0;
    int total = data.size();
    for (const auto& p : freq) {
        double prob = (double)p.second / total;
        ent -= prob * log2(prob);
    }
    return ent;
}

// 按照特征划分数据集
map<string, Data> split_by_feature(const Data& data, int feature_idx) {
    map<string, Data> subsets;
    for (const auto& row : data) {
        string val = row[feature_idx];
        subsets[val].push_back(row);
    }
    return subsets;
}

// 计算按某个特征划分后的信息增益
double info_gain(const Data& data, int feature_idx) {
    double ent_before = entropy(data);
    auto subsets = split_by_feature(data, feature_idx);
    double ent_after = 0.0;
    int total = data.size();
    for (const auto& pair : subsets) {
        double prob = (double)pair.second.size() / total;
        ent_after += prob * entropy(pair.second);
    }
    return ent_before - ent_after;
}

// 选择最佳分裂特征（信息增益最大）
int best_feature(const Data& data, const vector<int>& feature_indices) {
    int best_idx = -1;
    double best_gain = -1.0;
    for (int idx : feature_indices) {
        double gain = info_gain(data, idx);
        if (gain > best_gain) {
            best_gain = gain;
            best_idx = idx;
        }
    }
    return best_idx;
}

// 检查数据集中所有样本是否属于同一类别
bool all_same_class(const Data& data) {
    if (data.empty()) return true;
    const string& first = data[0].back();
    for (size_t i = 1; i < data.size(); ++i) {
        if (data[i].back() != first) return false;
    }
    return true;
}

// 递归构建决策树
shared_ptr<TreeNode> build_tree(const Data& data, const vector<int>& feature_indices) {
    // 创建新节点
    auto node = make_shared<TreeNode>();

    // 情况1：数据集为空（不应发生，仅作保护）
    if (data.empty()) {
        node->feature_idx = -1;
        node->label = "Unknown";
        return node;
    }

    // 情况2：所有样本同一类别 → 叶节点
    if (all_same_class(data)) {
        node->feature_idx = -1;
        node->label = data[0].back();
        return node;
    }

    // 情况3：没有可用特征 → 叶节点，取多数类别
    if (feature_indices.empty()) {
        node->feature_idx = -1;
        map<string, int> freq;
        for (const auto& row : data) freq[row.back()]++;
        node->label = max_element(freq.begin(), freq.end(),
            [](const auto& a, const auto& b) { return a.second < b.second; })->first;
        return node;
    }

    // 正常情况：选择最佳特征
    int best = best_feature(data, feature_indices);
    node->feature_idx = best;

    // 按最佳特征划分
    auto subsets = split_by_feature(data, best);

    // 剔除已用特征
    vector<int> remaining_features;
    for (int idx : feature_indices) {
        if (idx != best) remaining_features.push_back(idx);
    }

    // 对每个特征值子集递归建树
    for (const auto& pair : subsets) {
        const string& value = pair.first;
        const Data& subset_data = pair.second;
        node->children[value] = build_tree(subset_data, remaining_features);
    }

    return node;
}

// 预测单个样本
string predict(const shared_ptr<TreeNode>& tree, const vector<string>& sample) {
    if (tree->feature_idx == -1) {
        return tree->label;  // 叶节点
    }
    string feat_val = sample[tree->feature_idx];
    auto it = tree->children.find(feat_val);
    if (it == tree->children.end()) {
        // 遇到未见过的特征值，返回多数类（此处简单返回“Unknown”）
        return "Unknown";
    }
    return predict(it->second, sample);
}

// 简单测试
int main() {
    // 构造示例数据（天气数据集）
    Data data = {
        // outlook, temperature, humidity, windy, play
        {"Sunny", "Hot", "High", "False", "No"},
        {"Sunny", "Hot", "High", "True", "No"},
        {"Overcast", "Hot", "High", "False", "Yes"},
        {"Rainy", "Mild", "High", "False", "Yes"},
        {"Rainy", "Cool", "Normal", "False", "Yes"},
        {"Rainy", "Cool", "Normal", "True", "No"},
        {"Overcast", "Cool", "Normal", "True", "Yes"},
        {"Sunny", "Mild", "High", "False", "No"},
        {"Sunny", "Cool", "Normal", "False", "Yes"},
        {"Rainy", "Mild", "Normal", "False", "Yes"},
        {"Sunny", "Mild", "Normal", "True", "Yes"},
        {"Overcast", "Mild", "High", "True", "Yes"},
        {"Overcast", "Hot", "Normal", "False", "Yes"},
        {"Rainy", "Mild", "High", "True", "No"}
    };

    vector<int> feature_indices = {0, 1, 2, 3}; // 特征列索引

    // 训练
    auto tree = build_tree(data, feature_indices);

    // 测试预测
    vector<string> sample = {"Sunny", "Cool", "High", "False"};
    string result = predict(tree, sample);
    cout << "预测结果: " << result << endl; // 应为 "No"

    return 0;
}