从零构建CART决策树：原理详解与Python实战指南

1次阅读

没有评论

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

在机器学习项目中，特征工程的质量直接影响模型效果。决策树作为一种直观且强大的特征选择工具，能自动筛选重要特征并处理非线性关系。但对初学者而言，手动实现 CART（分类与回归树）时存在两大困惑点：

混淆划分标准 ：信息增益（ID3）、增益率（C4.5）与基尼系数（CART）的应用场景差异
忽视工程细节 ：连续特征处理、剪枝策略等实际问题的解决方案

基尼系数衡量数据集的纯度，值越小表示纯度越高。对于包含 K 类的数据集 D：

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

其中 |C_k| 表示第 k 类样本数量。对比其他算法：

ID3：使用信息增益，偏向选择取值多的特征
C4.5：改用增益率，克服 ID3 的偏置问题
CART：基尼系数计算更快且无需对数运算

import numpy as np

def gini_impurity(y):
    """计算节点的基尼不纯度"""
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p ** 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
            gini = (len(y[left_idx]) * gini_impurity(y[left_idx]) + 
                    len(y[~left_idx]) * gini_impurity(y[~left_idx])) / len(y)
            if gini < best_gini:
                best_gini = gini
                best_feature, best_thresh = feature, thresh
    return best_feature, best_thresh

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 build_tree(X, y, max_depth=5, min_samples=2):
    """递归构建决策树"""
    # 终止条件：达到最大深度或样本数不足
    if max_depth <= 0 or len(y) < min_samples:
        return TreeNode(value=np.bincount(y).argmax())

    feature, thresh = find_best_split(X, y)
    if feature is None:  # 无法继续分裂
        return TreeNode(value=np.bincount(y).argmax())

    left_idx = X[:, feature] <= thresh
    left = build_tree(X[left_idx], y[left_idx], max_depth-1, min_samples)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1, min_samples)
    return TreeNode(feature, thresh, left, right)

预剪枝 ：在建树过程中通过参数控制（如 max_depth）
优点：训练速度快
缺点：可能欠拟合
后剪枝 ：先构建完整树，再自底向上剪枝
优点：保留更多有效分裂
缺点：计算成本高

连续特征处理 ：
错误：直接按唯一值分割导致计算爆炸
正确：先排序后取相邻值中位数作为候选分割点
类别不平衡 ：
错误：直接使用基尼系数会偏向多数类
正确：采用带类别权重的基尼系数或过采样
缺失值处理 ：
错误：直接丢弃含缺失值的样本
正确：将缺失值作为独立分支或按比例分配

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris

# 加载数据
X, y = load_iris(return_X_y=True)

# 自实现模型
tree = build_tree(X, y)

# sklearn 对比
clf = DecisionTreeClassifier(criterion='gini', max_depth=5)
clf.fit(X, y)

print("自实现模型与 sklearn 的预测一致率:", 
      np.mean(clf.predict(X) == predict(tree, X)))

如何改进当前算法以支持 GPU 加速？可以考虑：