Java案例如何实现决策树？

本文目录导读：

1. 决策树基本结构
2. 决策树实现（ID3算法）
3. C4.5算法改进版本（使用增益率）
4. 使用示例
5. 决策树可视化输出
6. 使用第三方库（Weka）

我来详细介绍Java实现决策树的完整案例,包括ID3算法和C4.5算法的实现。

决策树基本结构

定义决策树的节点和核心数据结构：

import java.util.*;
// 决策树节点
class TreeNode {
    String attribute;           // 分裂属性
    String attributeValue;      // 属性值（分支标识）
    Map<String, TreeNode> children;  // 子节点
    String result;              // 叶子节点的分类结果
    boolean isLeaf;             // 是否为叶子节点
    public TreeNode() {
        this.children = new HashMap<>();
        this.isLeaf = false;
    }
    // 创建叶子节点
    public static TreeNode createLeaf(String result) {
        TreeNode leaf = new TreeNode();
        leaf.isLeaf = true;
        leaf.result = result;
        return leaf;
    }
}
// 数据样本
class DataSample {
    Map<String, String> attributes;  // 属性-值映射
    String label;                    // 类别标签
    public DataSample(String label) {
        this.attributes = new HashMap<>();
        this.label = label;
    }
    public void setAttribute(String key, String value) {
        attributes.put(key, value);
    }
    public String getAttribute(String key) {
        return attributes.get(key);
    }
}

决策树实现（ID3算法）

public class DecisionTreeID3 {
    private TreeNode root;
    private List<String> attributeNames;
    public DecisionTreeID3() {
        this.attributeNames = new ArrayList<>();
    }
    // 训练决策树
    public void train(List<DataSample> samples, List<String> attributes) {
        this.attributeNames = new ArrayList<>(attributes);
        this.root = buildTree(samples, attributes);
    }
    // 构建决策树
    private TreeNode buildTree(List<DataSample> samples, List<String> attributes) {
        // 如果所有样本属于同一类别，返回叶子节点
        String sameLabel = getSameLabel(samples);
        if (sameLabel != null) {
            return TreeNode.createLeaf(sameLabel);
        }
        // 如果没有可用属性，返回样本中出现最多的类别
        if (attributes.isEmpty()) {
            return TreeNode.createLeaf(getMajorityLabel(samples));
        }
        // 选择最佳分裂属性
        String bestAttribute = selectBestAttribute(samples, attributes);
        TreeNode node = new TreeNode();
        node.attribute = bestAttribute;
        node.isLeaf = false;
        // 根据最佳属性的取值分裂
        Set<String> attributeValues = getAttributeValues(samples, bestAttribute);
        List<String> remainingAttributes = new ArrayList<>(attributes);
        remainingAttributes.remove(bestAttribute);
        for (String value : attributeValues) {
            List<DataSample> subSamples = getSubSamples(samples, bestAttribute, value);
            if (subSamples.isEmpty()) {
                // 如果子集为空，创建多数类别的叶子节点
                node.children.put(value, TreeNode.createLeaf(getMajorityLabel(samples)));
            } else {
                // 递归构建子树
                node.children.put(value, buildTree(subSamples, remainingAttributes));
            }
        }
        return node;
    }
    // 选择最佳属性（基于信息增益）
    private String selectBestAttribute(List<DataSample> samples, List<String> attributes) {
        double baseEntropy = calculateEntropy(samples);
        String bestAttribute = null;
        double maxInfoGain = 0;
        for (String attribute : attributes) {
            double infoGain = baseEntropy - calculateConditionalEntropy(samples, attribute);
            if (infoGain > maxInfoGain) {
                maxInfoGain = infoGain;
                bestAttribute = attribute;
            }
        }
        return bestAttribute;
    }
    // 计算熵
    private double calculateEntropy(List<DataSample> samples) {
        Map<String, Integer> labelCounts = new HashMap<>();
        for (DataSample sample : samples) {
            labelCounts.merge(sample.label, 1, Integer::sum);
        }
        double entropy = 0.0;
        int total = samples.size();
        for (int count : labelCounts.values()) {
            double probability = (double) count / total;
            if (probability > 0) {
                entropy -= probability * (Math.log(probability) / Math.log(2));
            }
        }
        return entropy;
    }
    // 计算条件熵
    private double calculateConditionalEntropy(List<DataSample> samples, String attribute) {
        Map<String, List<DataSample>> splitData = splitByAttribute(samples, attribute);
        double conditionalEntropy = 0.0;
        int total = samples.size();
        for (Map.Entry<String, List<DataSample>> entry : splitData.entrySet()) {
            double weight = (double) entry.getValue().size() / total;
            double entropy = calculateEntropy(entry.getValue());
            conditionalEntropy += weight * entropy;
        }
        return conditionalEntropy;
    }
    // 按属性值分割数据
    private Map<String, List<DataSample>> splitByAttribute(List<DataSample> samples, String attribute) {
        Map<String, List<DataSample>> splitData = new HashMap<>();
        for (DataSample sample : samples) {
            String value = sample.getAttribute(attribute);
            splitData.computeIfAbsent(value, k -> new ArrayList<>()).add(sample);
        }
        return splitData;
    }
    // 辅助方法
    private String getSameLabel(List<DataSample> samples) {
        if (samples.isEmpty()) return null;
        String firstLabel = samples.get(0).label;
        for (DataSample sample : samples) {
            if (!sample.label.equals(firstLabel)) {
                return null;
            }
        }
        return firstLabel;
    }
    private String getMajorityLabel(List<DataSample> samples) {
        Map<String, Integer> labelCount = new HashMap<>();
        for (DataSample sample : samples) {
            labelCount.merge(sample.label, 1, Integer::sum);
        }
        return labelCount.entrySet().stream()
                .max(Map.Entry.comparingByValue())
                .get().getKey();
    }
    private Set<String> getAttributeValues(List<DataSample> samples, String attribute) {
        Set<String> values = new HashSet<>();
        for (DataSample sample : samples) {
            values.add(sample.getAttribute(attribute));
        }
        return values;
    }
    private List<DataSample> getSubSamples(List<DataSample> samples, String attribute, String value) {
        List<DataSample> subSamples = new ArrayList<>();
        for (DataSample sample : samples) {
            if (sample.getAttribute(attribute).equals(value)) {
                subSamples.add(sample);
            }
        }
        return subSamples;
    }
    // 预测
    public String predict(DataSample sample) {
        return predict(sample, root);
    }
    private String predict(DataSample sample, TreeNode node) {
        if (node.isLeaf) {
            return node.result;
        }
        String attributeValue = sample.getAttribute(node.attribute);
        TreeNode child = node.children.get(attributeValue);
        if (child == null) {
            // 如果找不到对应的分支，返回null或者默认值
            return null;
        }
        return predict(sample, child);
    }
    // 打印决策树
    public void printTree() {
        printTree(root, 0);
    }
    private void printTree(TreeNode node, int depth) {
        StringBuilder indent = new StringBuilder();
        for (int i = 0; i < depth; i++) {
            indent.append("  ");
        }
        if (node.isLeaf) {
            System.out.println(indent + "-> 结果: " + node.result);
        } else {
            System.out.println(indent + "属性: " + node.attribute);
            for (Map.Entry<String, TreeNode> entry : node.children.entrySet()) {
                System.out.println(indent + "  └── " + entry.getKey() + ":");
                printTree(entry.getValue(), depth + 2);
            }
        }
    }
}

C4.5算法改进版本（使用增益率）

public class DecisionTreeC45 extends DecisionTreeID3 {
    @Override
    protected String selectBestAttribute(List<DataSample> samples, List<String> attributes) {
        double baseEntropy = calculateEntropy(samples);
        String bestAttribute = null;
        double maxGainRatio = 0;
        for (String attribute : attributes) {
            double infoGain = baseEntropy - calculateConditionalEntropy(samples, attribute);
            double splitInfo = calculateSplitInfo(samples, attribute);
            if (splitInfo == 0) continue;
            double gainRatio = infoGain / splitInfo;
            if (gainRatio > maxGainRatio) {
                maxGainRatio = gainRatio;
                bestAttribute = attribute;
            }
        }
        return bestAttribute;
    }
    // 计算分裂信息
    private double calculateSplitInfo(List<DataSample> samples, String attribute) {
        Map<String, Integer> valueCounts = new HashMap<>();
        for (DataSample sample : samples) {
            String value = sample.getAttribute(attribute);
            valueCounts.merge(value, 1, Integer::sum);
        }
        double splitInfo = 0.0;
        int total = samples.size();
        for (int count : valueCounts.values()) {
            double probability = (double) count / total;
            if (probability > 0) {
                splitInfo -= probability * (Math.log(probability) / Math.log(2));
            }
        }
        return splitInfo;
    }
}

使用示例

public class DecisionTreeExample {
    public static void main(String[] args) {
        // 准备训练数据（天气预报示例）
        List<DataSample> trainingData = createTrainingData();
        List<String> attributes = Arrays.asList("天气", "温度", "湿度", "风力");
        // 使用ID3算法
        System.out.println("=== ID3决策树 ===");
        DecisionTreeID3 id3Tree = new DecisionTreeID3();
        id3Tree.train(trainingData, attributes);
        id3Tree.printTree();
        // 使用C4.5算法
        System.out.println("\n=== C4.5决策树 ===");
        DecisionTreeC45 c45Tree = new DecisionTreeC45();
        c45Tree.train(trainingData, attributes);
        c45Tree.printTree();
        // 预测示例
        DataSample testSample = new DataSample("");
        testSample.setAttribute("天气", "晴");
        testSample.setAttribute("温度", "适中");
        testSample.setAttribute("湿度", "正常");
        testSample.setAttribute("风力", "强");
        System.out.println("\n=== 预测结果 ===");
        String result = id3Tree.predict(testSample);
        System.out.println("是否适合外出: " + result);
        // 测试多个样本
        testMultipleSamples(id3Tree);
    }
    private static List<DataSample> createTrainingData() {
        List<DataSample> data = new ArrayList<>();
        // 样本1
        DataSample sample1 = new DataSample("适合");
        sample1.setAttribute("天气", "晴");
        sample1.setAttribute("温度", "热");
        sample1.setAttribute("湿度", "高");
        sample1.setAttribute("风力", "弱");
        data.add(sample1);
        // 样本2
        DataSample sample2 = new DataSample("适合");
        sample2.setAttribute("天气", "晴");
        sample2.setAttribute("温度", "适中");
        sample2.setAttribute("湿度", "正常");
        sample2.setAttribute("风力", "弱");
        data.add(sample2);
        // 样本3
        DataSample sample3 = new DataSample("不适合");
        sample3.setAttribute("天气", "阴");
        sample3.setAttribute("温度", "热");
        sample3.setAttribute("湿度", "高");
        sample3.setAttribute("风力", "强");
        data.add(sample3);
        // 样本4
        DataSample sample4 = new DataSample("适合");
        sample4.setAttribute("天气", "雨");
        sample4.setAttribute("温度", "凉爽");
        sample4.setAttribute("湿度", "正常");
        sample4.setAttribute("风力", "弱");
        data.add(sample4);
        // 样本5
        DataSample sample5 = new DataSample("不适合");
        sample5.setAttribute("天气", "晴");
        sample5.setAttribute("温度", "热");
        sample5.setAttribute("湿度", "高");
        sample5.setAttribute("风力", "强");
        data.add(sample5);
        // 样本6
        DataSample sample6 = new DataSample("适合");
        sample6.setAttribute("天气", "雨");
        sample6.setAttribute("温度", "适中");
        sample6.setAttribute("湿度", "正常");
        sample6.setAttribute("风力", "弱");
        data.add(sample6);
        return data;
    }
    private static void testMultipleSamples(DecisionTreeID3 tree) {
        System.out.println("\n=== 批量测试 ===");
        // 测试数据
        String[][] testCases = {
            {"晴", "热", "高", "弱", "适合"},
            {"阴", "凉爽", "正常", "强", "不适合"},
            {"雨", "热", "高", "强", "不适合"},
            {"晴", "凉爽", "正常", "弱", "适合"}
        };
        for (String[] testCase : testCases) {
            DataSample sample = new DataSample(testCase[4]);
            sample.setAttribute("天气", testCase[0]);
            sample.setAttribute("温度", testCase[1]);
            sample.setAttribute("湿度", testCase[2]);
            sample.setAttribute("风力", testCase[3]);
            String prediction = tree.predict(sample);
            System.out.printf("天气:%s, 温度:%s, 湿度:%s, 风力:%s → 预测:%s (实际:%s)%n",
                testCase[0], testCase[1], testCase[2], testCase[3], 
                prediction, testCase[4]);
        }
    }
}

决策树可视化输出

可以添加一个简单的ASCII可视化功能：

public class DecisionTreeVisualizer {
    public static void visualizeTree(TreeNode node) {
        StringBuilder sb = new StringBuilder();
        visualizeNode(node, 0, sb);
        System.out.println(sb.toString());
    }
    private static void visualizeNode(TreeNode node, int depth, StringBuilder sb) {
        if (node.isLeaf) {
            for (int i = 0; i < depth; i++) {
                sb.append("│   ");
            }
            sb.append("└── 预测: ").append(node.result).append("\n");
            return;
        }
        for (int i = 0; i < depth; i++) {
            sb.append("│   ");
        }
        sb.append("├── ").append(node.attribute).append("\n");
        int childIndex = 0;
        for (Map.Entry<String, TreeNode> entry : node.children.entrySet()) {
            for (int i = 0; i <= depth; i++) {
                sb.append("│   ");
            }
            sb.append("├── ").append(entry.getKey()).append(":\n");
            childIndex++;
            visualizeNode(entry.getValue(), depth + 2, sb);
        }
    }
}

使用第三方库（Weka）

如果需要更强大的功能,可以使用Weka库：

import weka.classifiers.trees.J48;
import weka.core.*;
public class WekaDecisionTreeExample {
    public static void main(String[] args) throws Exception {
        // 创建数据集
        ArrayList<Attribute> attributes = new ArrayList<>();
        // 定义属性
        attributes.add(new Attribute("天气", Arrays.asList("晴", "阴", "雨")));
        attributes.add(new Attribute("温度", Arrays.asList("热", "适中", "凉爽")));
        attributes.add(new Attribute("湿度", Arrays.asList("高", "正常")));
        attributes.add(new Attribute("风力", Arrays.asList("弱", "强")));
        // 类别属性
        ArrayList<String> classValues = new ArrayList<>();
        classValues.add("适合");
        classValues.add("不适合");
        attributes.add(new Attribute("结果", classValues));
        // 创建实例数据
        Instances data = new Instances("天气数据", attributes, 0);
        data.setClassIndex(data.numAttributes() - 1);
        // 添加数据实例
        double[] values1 = {0, 0, 0, 0, 0}; // 晴,热,高,弱,适合
        data.add(new DenseInstance(1.0, values1));
        double[] values2 = {0, 1, 1, 0, 0}; // 晴,适中,正常,弱,适合
        data.add(new DenseInstance(1.0, values2));
        // 创建J48决策树（C4.5实现）
        J48 tree = new J48();
        tree.buildClassifier(data);
        // 输出决策树
        System.out.println(tree);
        // 预测新样本
        Instance newSample = new DenseInstance(5);
        newSample.setDataset(data);
        newSample.setValue(0, "晴");
        newSample.setValue(1, "热");
        newSample.setValue(2, "高");
        newSample.setValue(3, "弱");
        double prediction = tree.classifyInstance(newSample);
        System.out.println("预测结果: " + data.classAttribute().value((int) prediction));
    }
}

这个完整的决策树实现包含了：

1. 基础决策树结构：节点定义、数据样本结构
2. ID3算法实现：使用信息增益选择分裂属性
3. C4.5算法改进：使用增益率减少对多值属性的偏好
4. 预测功能：对新样本进行分类
5. 可视化输出：树结构和预测结果的展示
6. Weka集成示例：使用专业机器学习库

你可以根据实际需求：

• 调整算法参数（如最小叶子节点样本数、最大深度）
• 添加剪枝功能防止过拟合
• 处理连续属性
• 处理缺失值
• 集成到Web应用或Android应用中