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

1次阅读

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

决策树是一种模仿人类决策过程的树形结构模型。就像我们根据天气决定是否出门（” 下雨吗？→是→带伞 ”），它通过一系列判断条件对数据进行分类或回归。常见算法家族有：

ID3：使用信息增益选择特征，但只能处理离散值且倾向多值属性
C4.5：改进 ID3，引入信息增益率并支持连续值，但计算成本较高
CART（本文主角）：使用基尼系数或平方误差，同时支持分类和回归任务

基尼系数衡量数据的不纯度，值越小表示纯度越高。计算公式为：

Gini(D) = 1 - \sum_{k=1}^{K}(\frac{|C_k|}{|D|})^2

其中 K 是类别数，|C_k|是第 k 类样本数。以二分类为例：

当两类样本各占 50% 时：Gini=1-(0.5²+0.5²)=0.5
当全部属于同一类时：Gini=1-(1²+0²)=0

对于每个特征，计算按该特征分裂后的加权基尼系数：

Gini_{split}(D,A) = \sum_{v=1}^{V}\frac{|D_v|}{|D|}Gini(D_v)

选择使 Gini_split 最小的特征作为分裂节点。

class TreeNode:
    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 build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件判断
    if len(y) < min_samples_split or max_depth == 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    best_gini = float('inf')
    best_feature, best_threshold = None, None

    # 遍历所有特征和可能的分裂点
    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_idx = X[:, feature] <= threshold
            g = (len(y[left_idx])/len(y))*gini(y[left_idx]) + \
                (len(y[~left_idx])/len(y))*gini(y[~left_idx])

            if g < best_gini:
                best_gini = g
                best_feature = feature
                best_threshold = threshold

    # 递归构建子树
    left_idx = X[:, best_feature] <= best_threshold
    left = build_tree(X[left_idx], y[left_idx], max_depth-1, min_samples_split)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1, min_samples_split)

    return TreeNode(feature=best_feature, threshold=best_threshold, 
                   left=left, right=right)