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

1次阅读

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

决策树就像人类做决策的过程，通过一系列 if-else 规则对数据进行分类。举个例子：判断水果是苹果还是橘子，可能会先问『颜色是红色吗？』，再根据重量、形状等特征逐步细分。

常见的决策树算法有：

ID3：使用信息增益选择特征，只能处理离散值，容易过拟合
C4.5：改进版，用信息增益率选择特征，支持连续值处理
CART（本文主角）：使用基尼系数，能同时处理分类和回归任务

基尼系数衡量数据的不纯度，公式很简单：

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

比如一个袋子有 3 红球 + 7 蓝球：

Gini = 1 - (0.3² + 0.7²) = 0.42

CART 采用二分法：
1. 对每个特征的所有可能分割点计算基尼系数
2. 选择使基尼系数下降最大的特征作为分裂点

数学表达式：

ΔGini = Gini(D) - (|D1|/|D|)*Gini(D1) - (|D2|/|D|)*Gini(D2)

先定义决策树节点结构：

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 build_tree(X, y, depth=0, max_depth=5):
    # 终止条件：纯度达标 / 达到最大深度 / 样本数太少
    if (gini(y) < 0.01) or (depth == max_depth) or (len(y) < 5):
        return Node(value=np.argmax(np.bincount(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 = (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_thresh = thresh

    # 递归构建子树            
    left_idx = X[:, best_feature] <= best_thresh
    left = build_tree(X[left_idx], y[left_idx], depth+1)
    right = build_tree(X[~left_idx], y[~left_idx], depth+1)

    return Node(feature=best_feature, threshold=best_thresh, left=left, right=right)