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

1次阅读

没有评论

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

传统 ID3 决策树存在几个明显缺陷：

只能处理离散型特征，无法直接处理连续值
采用信息增益作为划分标准，容易偏向取值多的特征
多叉树结构导致模型复杂度难以控制

CART(Classification And Regression Tree)通过两项改进解决了这些问题：

二元分裂：每次只生成两个子节点，天然支持连续特征处理
基尼系数：替代信息增益，避免特征取值数量的影响

基尼系数衡量数据的不纯度，定义如下：

$$Gini(p) = \sum_{k=1}^K p_k(1-p_k) = 1 – \sum_{k=1}^K p_k^2$$

其中 $p_k$ 是第 k 类样本的比例。对于二分类问题，当两类比例相等时基尼系数最大(0.5)。

特征选择时，我们计算分裂后的加权基尼系数：

$$Gini_{split} = \frac{N_{left}}{N}Gini_{left} + \frac{N_{right}}{N}Gini_{right}$$

class TreeNode:
    def __init__(self, feature_idx=None, threshold=None, 
                 left=None, right=None, value=None):
        # 分裂特征索引
        self.feature_idx = feature_idx  
        # 分裂阈值(连续特征)
        self.threshold = threshold
        # 左右子节点
        self.left = left
        self.right = right
        # 叶节点的预测值
        self.value = value

import numpy as np

def gini(y):
    """计算基尼系数"""
    _, counts = np.unique(y, return_counts=True)
    p = counts / len(y)
    return 1 - np.sum(p ** 2)

def build_tree(X, y, max_depth=5, min_samples_split=2):
    # 终止条件 1：所有样本类别相同
    if len(np.unique(y)) == 1:
        return TreeNode(value=y[0])

    # 终止条件 2：达到最大深度或样本不足
    if max_depth <= 0 or len(y) < min_samples_split:
        return TreeNode(value=np.bincount(y).argmax())

    # 寻找最佳分裂特征和阈值
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feature_idx in range(X.shape[1]):
        # 对连续特征尝试不同分裂点
        thresholds = np.unique(X[:, feature_idx])
        for thresh in thresholds:
            left_idx = X[:, feature_idx] <= thresh
            g = (len(y[left_idx]) * gini(y[left_idx]) + 
                 len(y[~left_idx]) * gini(y[~left_idx])) / len(y)
            if g < best_gini:
                best_gini = g
                best_feature = feature_idx
                best_thresh = thresh

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

    return TreeNode(best_feature, best_thresh, left, right)

from joblib import Parallel, delayed

def parallel_predict(tree, X):
    """并行化预测"""
    return Parallel(n_jobs=-1)(delayed(_predict_single)(tree, x) for x in X)

def _predict_single(node, x):
    """单样本预测"""
    while node.value is None:
        if x[node.feature_idx] <= node.threshold:
            node = node.left
        else:
            node = node.right
    return node.value

from sklearn.base import BaseEstimator, ClassifierMixin

class CARTClassifier(BaseEstimator, ClassifierMixin):
    def __init__(self, max_depth=5, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split

    def fit(self, X, y):
        self.tree_ = build_tree(X, y, self.max_depth, self.min_samples_split)
        return self

    def predict(self, X):
        return np.array([_predict_single(self.tree_, x) for x in X])

对浮点特征采用分位数离散化避免数值不稳定
添加微小噪声处理重复值

# 改进后的阈值选择方法
thresholds = np.percentile(X[:, feature_idx], np.linspace(0,100,20))

对高基数类别特征采用目标编码(Target Encoding)
避免使用 one-hot 编码导致树深度过大

# 目标编码示例
def target_encode(df, cat_col, target_col):
    return df[cat_col].map(df.groupby(cat_col)[target_col].mean())

使用 graphviz 时指定字体避免中文乱码：

import graphviz

def plot_tree(tree, feature_names):
    dot = graphviz.Digraph(graph_attr={'fontname': 'Microsoft YaHei'})
    # ... 构建可视化代码
    return dot

在 UCI 乳腺癌数据集上的测试结果：