从零实现CART决策树代码：机器学习入门实战指南

1次阅读

没有评论

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

很多机器学习初学者在第一次手写 CART 决策树时，往往会遇到一些共性问题。我自己刚开始实现时也踩过不少坑，这里总结几个典型的误区：

连续特征处理不当：直接把连续值当作类别特征处理，导致决策树效果很差
缺失值忽略：没有考虑数据中可能存在的缺失值情况
递归终止条件太简单：仅用 ” 所有样本属于同一类 ” 作为停止条件，容易过拟合
代码结构混乱：把建树、预测、剪枝等逻辑全部写在一起，难以维护

相比直接调用 sklearn 的 DecisionTreeClassifier，自己实现决策树有几个优势：

更深入理解算法原理
可以定制特殊需求（如特定的剪枝策略）
对代码性能优化有完全控制权

当然现成库也有优势，比如优化更好、功能更全。但对于学习来说，从零实现是不可替代的。

CART 决策树使用基尼系数 (Gini Index) 来衡量节点的不纯度。对于一个包含 K 类的数据集 D，基尼系数计算公式为：

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

其中 $C_k$ 是第 k 类样本的集合。基尼系数越小，说明数据越纯。

在 Python 中实现如下：

def gini_index(groups, classes):
    """计算基尼系数"""
    n_samples = sum(len(group) for group in groups)
    gini = 0.0
    for group in groups:
        size = len(group)
        if size == 0:
            continue
        score = 0.0
        for class_val in classes:
            p = [row[-1] for row in group].count(class_val) / size
            score += p * p
        gini += (1.0 - score) * (size / n_samples)
    return gini

特征选择的目标是找到使子节点基尼系数最小的分裂方式。对于每个特征，我们需要：

计算所有可能的分裂点
计算分裂后的加权基尼系数
选择使基尼系数最小的分裂方案

这里以连续特征为例：

def get_split(dataset):
    """找到最佳分裂特征和值"""
    class_values = list(set(row[-1] for row in dataset))
    b_index, b_value, b_score, b_groups = 999, 999, 999, None

    for index in range(len(dataset[0])-1):
        for row in dataset:
            groups = test_split(index, row[index], dataset)
            gini = gini_index(groups, class_values)
            if gini < b_score:
                b_index, b_value, b_score, b_groups = index, row[index], gini, groups
    return {
        'index': b_index, 
        'value': b_value,
        'groups': b_groups
    }

有了上面的基础，建树过程就是一个递归分割的过程：

创建根节点
寻找最佳分裂
如果满足停止条件则创建叶节点
否则递归处理左右子树

停止条件通常包括：

节点样本数小于阈值
基尼系数低于阈值
达到最大深度

def build_tree(node, max_depth, min_size, depth):
    """递归构建决策树"""
    left, right = node['groups']
    del(node['groups'])

    # 检查是否需要终止
    if not left or not right:
        node['left'] = node['right'] = to_terminal(left + right)
        return
    if depth >= max_depth:
        node['left'], node['right'] = to_terminal(left), to_terminal(right)
        return

    # 处理左子树
    if len(left) <= min_size:
        node['left'] = to_terminal(left)
    else:
        node['left'] = get_split(left)
        build_tree(node['left'], max_depth, min_size, depth+1)

    # 处理右子树
    if len(right) <= min_size:
        node['right'] = to_terminal(right)
    else:
        node['right'] = get_split(right)
        build_tree(node['right'], max_depth, min_size, depth+1)

完整实现需要注意几个关键点：

类型注解：Python 3.5+ 支持类型注解，可以提高代码可读性
PEP8 规范：保持一致的代码风格
模块化设计：将不同功能拆分为独立函数
详细注释：特别是算法关键步骤

完整代码结构建议如下：

from typing import List, Dict, Union

class DecisionTree:
    """CART 决策树实现"""

    def __init__(self, max_depth: int = 5, min_size: int = 10):
        self.max_depth = max_depth
        self.min_size = min_size
        self.tree = None

    def fit(self, X: List[List[float]], y: List[int]) -> None:
        """训练模型"""
        dataset = [x + [label] for x, label in zip(X, y)]
        self.tree = self._build_tree(dataset)

    def _build_tree(self, dataset: List[list], depth: int = 0) -> Dict:
        """内部建树方法"""
        # 实现细节同上
        pass

    def predict(self, X: List[List[float]]) -> List[int]:
        """预测方法"""
        return [self._predict(self.tree, x) for x in X]

    def _predict(self, node: Dict, row: List[float]) -> int:
        """单样本预测"""
        if row[node['index']] < node['value']:
            if isinstance(node['left'], dict):
                return self._predict(node['left'], row)
            return node['left']
        else:
            if isinstance(node['right'], dict):
                return self._predict(node['right'], row)
            return node['right']

当特征维度很高时，可以采取以下优化措施：

对连续特征只考虑分位数点作为候选分裂点
使用稀疏矩阵存储数据
实现增量学习（partial_fit）

决策树可视化是很好的调试工具：

import matplotlib.pyplot as plt
from sklearn.tree import plot_tree

# 将自实现的树转换为 sklearn 格式（需要适配）plot_tree(sklearn_tree)
plt.show()

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

特性	CART	ID3	C4.5
分裂标准	基尼系数	信息增益	信息增益比
处理连续特征	是	否	是
生成树类型	二叉树	多叉树	多叉树
剪枝方式	代价复杂度	无	悲观剪枝

错误现象	可能原因	解决方案
基尼系数为负数	样本计数错误	检查类别计数逻辑
所有样本都分到同一侧	分裂值选择不当	检查特征值范围
树深度过大	停止条件不合理	调整 max_depth/min_size
预测结果全相同	树没有正确分裂	检查建树过程