本文目录导读：
我来详细介绍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));
}
}
这个完整的决策树实现包含了：
- 基础决策树结构：节点定义、数据样本结构
- ID3算法实现：使用信息增益选择分裂属性
- C4.5算法改进：使用增益率减少对多值属性的偏好
- 预测功能：对新样本进行分类
- 可视化输出：树结构和预测结果的展示
- Weka集成示例：使用专业机器学习库
你可以根据实际需求：
- 调整算法参数（如最小叶子节点样本数、最大深度）
- 添加剪枝功能防止过拟合
- 处理连续属性
- 处理缺失值
- 集成到Web应用或Android应用中
