算法之决策树：用自然思维解决复杂问题的白盒模型

class TreeNode {
    int splitFeature; // 分裂特征索引
    double splitValue; // 分裂阈值
    TreeNode left;    // 左子树
    TreeNode right;   // 右子树
    int label;        // 叶节点存储的类别
}

public class DecisionTree {
    // 递归构建决策树
    public TreeNode buildTree(double[][] data, int depth) {
        if (shouldStop(data, depth)) {
            return new TreeNode(mostCommonLabel(data));
        }
        
        SplitInfo bestSplit = findBestSplit(data);
        TreeNode node = new TreeNode();
        node.splitFeature = bestSplit.featureIndex;
        node.splitValue = bestSplit.threshold;
        
        // 递归分裂左右子树
        node.left = buildTree(bestSplit.leftData, depth+1);
        node.right = buildTree(bestSplit.rightData, depth+1);
        return node;
    }

    // 基尼系数计算
    private double giniImpurity(int[] labels) {
        Map<Integer, Integer> counts = new HashMap<>();
        for (int label : labels) counts.put(label, counts.getOrDefault(label, 0) + 1);
        
        double impurity = 1.0;
        for (int count : counts.values()) {
            double prob = (double)count / labels.length;
            impurity -= prob * prob;
        }
        return impurity;
    }

    // 预测方法
    public int predict(TreeNode node, double[] sample) {
        if (node.left == null && node.right == null) {
            return node.label;
        }
        if (sample[node.splitFeature] <= node.splitValue) {
            return predict(node.left, sample);
        } else {
            return predict(node.right, sample);
        }
    }
}

// 简单二分类示例数据
double[][] data = {
    {25, 1, 0},  // 年龄25，有房，拒绝贷款
    {30, 0, 1},  // 年龄30，无房，通过贷款
    {35, 1, 1}
};

// 剪枝优化示例
private boolean shouldPrune(TreeNode node) {
    double errorBefore = calculateError(node);
    double errorAfter = calculateErrorAsLeaf(node);
    return errorAfter <= errorBefore + standardError(errorBefore);
}