CART决策树分类结构实战指南：从原理到Python实现

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

为什么需要决策树？

当开始学习机器学习分类问题时，我们通常会先接触线性模型（如逻辑回归）。虽然简单易用，但线性模型有明显的局限性：

• 无法自动捕捉特征间的交互作用（比如 ” 年龄 <30 且收入 >50k” 的组合条件）
• 对非线性决策边界表现不佳（比如环形分布的数据）
• 缺乏可解释性（难以理解权重系数的实际含义）

决策树的优势在于：

1. 天然支持特征组合，自动发现重要决策规则
2. 可视化后能直观展示决策逻辑（像流程图一样清晰）
3. 对数据分布不做强假设，适用于各种类型数据

CART 决策树的数学原理

CART（Classification and Regression Trees）使用基尼系数作为分裂标准。假设数据集 $D$ 有 $K$ 个类别，基尼系数计算公式为：

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

其中 $|C_k|$ 是类别 $k$ 的样本数。基尼系数越小表示纯度越高。比较分裂前后的基尼指数变化：

$$ \Delta Gini = Gini(D) – \sum_{v=1}^{V} \frac{|D_v|}{|D|} Gini(D_v) $$

与 ID3/C4.5 的主要区别：

• ID3 使用信息增益，对多值特征有偏好
• C4.5 使用信息增益比，但计算更复杂
• CART 生成二叉树，计算效率更高

Python 实现步骤

1. 定义树节点结构

from dataclasses import dataclass
from typing import Any, Optional

@dataclass
class TreeNode:
    feature: Optional[str] = None  # 分裂特征名
    threshold: Optional[float] = None  # 分裂阈值
    left: Optional['TreeNode'] = None  # 左子树
    right: Optional['TreeNode'] = None  # 右子树
    value: Optional[Any] = None  # 叶节点的预测值 

2. 核心递归分裂逻辑

def _best_split(self, X, y, features) -> tuple:
    """寻找最佳分裂特征和阈值"""
    best_gini = float('inf')
    best_feature, best_thresh = None, None

    for feat in features:
        # 对连续特征排序后取相邻点中点作为候选阈值
        values = np.unique(X[:, feat])
        thresholds = (values[:-1] + values[1:]) / 2

        for thresh in thresholds:
            left_idx = X[:, feat] <= thresh
            gini = self._weighted_gini(y[left_idx], y[~left_idx])

            if gini < best_gini:
                best_gini = gini
                best_feature = feat
                best_thresh = thresh

    return best_feature, best_thresh

def _weighted_gini(self, left_y, right_y) -> float:
    """计算加权基尼系数"""
    n_left, n_right = len(left_y), len(right_y)
    total = n_left + n_right

    gini_left = 1 - sum((np.sum(left_y == k) / n_left)**2 
                       for k in np.unique(left_y))
    gini_right = 1 - sum((np.sum(right_y == k) / n_right)**2 
                        for k in np.unique(right_y))

    return (n_left/total)*gini_left + (n_right/total)*gini_right

3. 后剪枝实现（伪代码）

def prune(self, node, X_val, y_val):
    if node is None or node.value is not None:
        return

    # 1. 先剪枝左右子树
    self.prune(node.left, X_val, y_val)
    self.prune(node.right, X_val, y_val)

    # 2. 计算当前节点作为叶节点时的错误率
    pred_leaf = self._predict_node(X_val, node.value)
    error_leaf = np.mean(pred_leaf != y_val)

    # 3. 计算不剪枝的错误率
    pred_tree = self._predict_node(X_val, node)
    error_tree = np.mean(pred_tree != y_val)

    # 4. 判断是否剪枝
    if error_leaf <= error_tree:
        node.left = node.right = None
        node.value = np.argmax(np.bincount(y_val))

常见问题与解决方案

类别不平衡处理

当某些类别样本极少时：

• 在基尼计算中引入类别权重

  class_weight = {'A':0.8, 'B':0.2}  # 手动指定权重
  gini = 1 - sum(weight * (count/total)**2 
               for cls, weight in class_weight.items())

连续值分箱陷阱

• 避免等宽分箱导致某些区间样本过少
• 推荐使用分位数分箱（pd.qcut）

可视化技巧

使用 graphviz 绘制决策路径：

import graphviz
def plot_tree(clf, feature_names):
    dot_data = export_graphviz(
        clf, feature_names=feature_names,
        filled=True, rounded=True
    )
    return graphviz.Source(dot_data)

性能优化方向

实际项目中建议直接使用 scikit-learn 的实现，它通过以下方式优化：

1. 使用 Cython 加速核心计算
2. 支持并行化（n_jobs 参数）
3. 内存映射处理超大数据集
4. 增量训练（warm_start=True）

实战挑战：泰坦尼克数据集

尝试对以下特征进行工程化处理：

1. 姓名中的称谓（Mr/Mrs/Miss）是否影响生存率？
2. 如何合理分箱年龄和票价？
3. 舱位（Pclass）和登船港口（Embarked）是否需要 One-Hot 编码？

# 数据下载
from sklearn.datasets import fetch_openml
titanic = fetch_openml('titanic', version=1, as_frame=True)
df = titanic.frame

总结心得

通过这次实现，我深刻体会到：

1. 决策树的优势在于直观易懂，适合作为基线模型
2. 实际应用中剪枝比预想的更重要
3. 特征工程的质量直接影响树模型的性能

建议初学者先用 sklearn 的 DecisionTreeClassifier 熟悉接口，再尝试自己实现底层逻辑，这样学习效果最佳。