CART算法实战：从原理到代码实现决策树构建

1次阅读

共计 2093 个字符，预计需要花费 6 分钟才能阅读完成。

决策树是机器学习中最直观的算法之一，而 CART（Classification and Regression Trees）则是其中应用最广泛的构建方法。与 ID3 和 C4.5 不同，CART 既能处理分类问题也能解决回归任务，其核心是通过递归二分（binary splitting）构建二叉树。

分裂准则 ：分类任务使用基尼系数（Gini Index），回归任务使用最小平方误差
终止条件 ：节点纯度达到阈值 / 样本数小于阈值 / 达到最大深度
输出结果 ：分类树返回类别标签，回归树返回叶节点样本均值

数学上，基尼系数计算公式为：

Gini(D) = 1 - Σ(p_i)^2  # p_i 是第 i 类样本占比

特性	CART	ID3	C4.5
树结构	二叉树	多叉树	多叉树
特征选择	基尼系数 /MSE	信息增益	信息增益率
任务类型	分类 + 回归	仅分类	仅分类
缺失值处理	需预处理	不支持	自动处理

CART 的优势在于：
– 计算效率更高（二叉树结构）
– 输出结果可解释性强
– 对异常值鲁棒性更好

class Node:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature   # 分裂特征
        self.threshold = threshold  # 分裂阈值
        self.left = left        # 左子树
        self.right = right      # 右子树
        self.value = value      # 叶节点值

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / len(y)
    return 1 - np.sum(probabilities**2)

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for thresh in thresholds:
            left_idx = X[:, feature] <= thresh
            g = gini(y[left_idx]) * left_idx.sum() / len(y) + \
                gini(y[~left_idx]) * (~left_idx).sum() / len(y)
            if g < best_gini:
                best_gini = g
                best_feature = feature
                best_thresh = thresh
    return best_feature, best_thresh

def build_tree(X, y, depth=0, max_depth=5):
    if len(np.unique(y)) == 1 or depth >= max_depth:
        return Node(value=np.mean(y))  # 回归任务

    feature, thresh = find_best_split(X, y)
    left_idx = X[:, feature] <= thresh

    left = build_tree(X[left_idx], y[left_idx], depth+1, max_depth)
    right = build_tree(X[~left_idx], y[~left_idx], depth+1, max_depth)
    return Node(feature, thresh, left, right)