机器学习经典算法：ID3决策树（Iterative Dichotomiser 3）原理、手动计算与Python/Java双代码实战

                天气?
               /  |  \
            晴    阴   雨
           /      |     \
        湿度?     是     风力?
       /   \             /   \
    高     正常        弱     强
    |       |          |      |
   否       是         是     否

import math
from collections import Counter

def entropy(data):
    labels = [row[-1] for row in data]
    label_counts = Counter(labels)
    total = len(labels)
    ent = 0.0
    for count in label_counts.values():
        p = count / total
        ent -= p * math.log2(p)
    return ent

def split_data(data, feature_idx, value):
    return [row for row in data if row[feature_idx] == value]

def information_gain(data, feature_idx):
    base_entropy = entropy(data)
    feature_values = set(row[feature_idx] for row in data)
    weighted_entropy = 0.0
    for val in feature_values:
        subset = split_data(data, feature_idx, val)
        prob = len(subset) / len(data)
        weighted_entropy += prob * entropy(subset)
    return base_entropy - weighted_entropy

def id3(data, features, feature_names):
    labels = [row[-1] for row in data]
    if len(set(labels)) == 1:
        return labels[0]  # 纯节点
    
    if not features:
        return Counter(labels).most_common(1)[0][0]  # 投票
    
    # 选择信息增益最大的特征
    best_feature_idx = max(features, key=lambda i: information_gain(data, i))
    best_feature_name = feature_names[best_feature_idx]
    
    tree = {best_feature_name: {}}
    feature_values = set(row[best_feature_idx] for row in data)
    
    remaining_features = [i for i in features if i != best_feature_idx]
    
    for val in feature_values:
        subset = split_data(data, best_feature_idx, val)
        if not subset:
            tree[best_feature_name][val] = Counter(labels).most_common(1)[0][0]
        else:
            subtree = id3(subset, remaining_features, feature_names)
            tree[best_feature_name][val] = subtree
    
    return tree

# 数据准备
data = [
    ["晴", "热", "高", "弱", "否"],
    ["晴", "热", "高", "强", "否"],
    ["阴", "热", "高", "弱", "是"],
    ["雨", "凉", "正常", "弱", "是"],
    ["雨", "冷", "正常", "弱", "是"],
    ["雨", "冷", "正常", "强", "否"],
    ["阴", "冷", "正常", "强", "是"],
    ["晴", "凉", "高", "弱", "否"],
    ["晴", "冷", "正常", "弱", "是"],
    ["雨", "凉", "正常", "弱", "是"],
    ["晴", "凉", "正常", "强", "是"],
    ["阴", "凉", "高", "强", "是"],
    ["阴", "热", "正常", "弱", "是"],
    ["雨", "凉", "高", "强", "否"]
]

features = list(range(len(data[0]) - 1))  # [0,1,2,3]
feature_names = ["天气", "温度", "湿度", "风力"]

tree = id3(data, features, feature_names)
print("ID3决策树:", tree)

import java.util.*;

public class ID3 {
    static class TreeNode {
        String feature;
        Map<String, TreeNode> children = new HashMap<>();
        String label; // if leaf

        TreeNode(String feature) { this.feature = feature; }
        TreeNode(String feature, String label) { this.feature = feature; this.label = label; }
    }

    public static double entropy(List<String[]> data) {
        Map<String, Integer> count = new HashMap<>();
        for (String[] row : data) {
            String label = row[row.length - 1];
            count.put(label, count.getOrDefault(label, 0) + 1);
        }
        double ent = 0.0;
        int total = data.size();
        for (int c : count.values()) {
            double p = (double) c / total;
            ent -= p * (Math.log(p) / Math.log(2));
        }
        return ent;
    }

    public static List<String[]> splitData(List<String[]> data, int featureIdx, String value) {
        List<String[]> subset = new ArrayList<>();
        for (String[] row : data) {
            if (row[featureIdx].equals(value)) {
                subset.add(row);
            }
        }
        return subset;
    }

    public static double informationGain(List<String[]> data, int featureIdx) {
        double baseEnt = entropy(data);
        Set<String> values = new HashSet<>();
        for (String[] row : data) values.add(row[featureIdx]);

        double weightedEnt = 0.0;
        for (String val : values) {
            List<String[]> subset = splitData(data, featureIdx, val);
            double prob = (double) subset.size() / data.size();
            weightedEnt += prob * entropy(subset);
        }
        return baseEnt - weightedEnt;
    }

    public static String majorityLabel(List<String[]> data) {
        Map<String, Integer> count = new HashMap<>();
        for (String[] row : data) {
            String label = row[row.length - 1];
            count.put(label, count.getOrDefault(label, 0) + 1);
        }
        return Collections.max(count.entrySet(), Map.Entry.comparingByValue()).getKey();
    }

    public static TreeNode id3(List<String[]> data, List<Integer> features, String[] featureNames) {
        // 检查是否纯节点
        Set<String> labels = new HashSet<>();
        for (String[] row : data) labels.add(row[row.length - 1]);
        if (labels.size() == 1) {
            return new TreeNode("leaf", labels.iterator().next());
        }
        if (features.isEmpty()) {
            return new TreeNode("leaf", majorityLabel(data));
        }

        // 选择最佳特征
        int bestIdx = -1;
        double bestGain = -1;
        for (int idx : features) {
            double gain = informationGain(data, idx);
            if (gain > bestGain) {
                bestGain = gain;
                bestIdx = idx;
            }
        }

        TreeNode node = new TreeNode(featureNames[bestIdx]);
        Set<String> values = new HashSet<>();
        for (String[] row : data) values.add(row[bestIdx]);

        List<Integer> remainingFeatures = new ArrayList<>(features);
        remainingFeatures.remove(Integer.valueOf(bestIdx));

        for (String val : values) {
            List<String[]> subset = splitData(data, bestIdx, val);
            if (subset.isEmpty()) {
                node.children.put(val, new TreeNode("leaf", majorityLabel(data)));
            } else {
                node.children.put(val, id3(subset, remainingFeatures, featureNames));
            }
        }

        return node;
    }

    // 测试
    public static void main(String[] args) {
        List<String[]> data = Arrays.asList(
            new String[]{"晴", "热", "高", "弱", "否"},
            new String[]{"晴", "热", "高", "强", "否"},
            new String[]{"阴", "热", "高", "弱", "是"},
            new String[]{"雨", "凉", "正常", "弱", "是"},
            new String[]{"雨", "冷", "正常", "弱", "是"},
            new String[]{"雨", "冷", "正常", "强", "否"},
            new String[]{"阴", "冷", "正常", "强", "是"},
            new String[]{"晴", "凉", "高", "弱", "否"},
            new String[]{"晴", "冷", "正常", "弱", "是"},
            new String[]{"雨", "凉", "正常", "弱", "是"},
            new String[]{"晴", "凉", "正常", "强", "是"},
            new String[]{"阴", "凉", "高", "强", "是"},
            new String[]{"阴", "热", "正常", "弱", "是"},
            new String[]{"雨", "凉", "高", "强", "否"}
        );

        List<Integer> features = Arrays.asList(0, 1, 2, 3);
        String[] featureNames = {"天气", "温度", "湿度", "风力"};

        TreeNode tree = id3(data, features, featureNames);
        System.out.println("ID3决策树已构建（结构见控制台输出逻辑）");
        // 实际打印需额外遍历函数，此处略
    }
}