Python实战：从零构建CART决策树模型及避坑指南

1次阅读

没有评论

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

决策树作为机器学习中的经典算法，因其直观的可解释性和对非线性关系的处理能力，常被用于分类和回归任务。然而，对于初学者来说，手动实现 CART 决策树时常常会遇到一些常见问题：

忽略连续值处理：很多新手在实现时只考虑了离散特征，而忽略了连续特征的处理方法。
缺失剪枝逻辑：决策树容易过拟合，剪枝是防止过拟合的关键步骤，但初学者往往忽略这一点。
递归终止条件设置不当：比如没有考虑最小样本数或最大深度等超参数，导致模型性能不稳定。

这些问题在实际应用中可能会严重影响模型的泛化能力。因此，本文将逐步讲解如何从零实现一个完整的 CART 决策树模型，并分享一些避坑技巧。

在决策树算法中，ID3、C4.5 和 CART 是三种常见的实现方式，它们的核心区别在于分裂准则和树的结构：

ID3：使用信息增益作为分裂准则，但无法处理连续特征，且容易偏向取值较多的特征。
C4.5：改进了 ID3，使用信息增益比，能够处理连续特征，但仍生成多叉树。
CART：采用基尼系数（分类任务）或均方误差（回归任务）作为分裂准则，生成二叉树，更适合实际生产环境。

CART 的优势在于：

二叉树结构：简化了树的构建逻辑，计算效率更高。
基尼系数：计算简单，且对噪声数据更加鲁棒。
支持连续特征和缺失值处理：更适合实际数据集。

基尼系数用于衡量数据集的不纯度，定义为：

Gini(D) = 1 - \sum_{k=1}^K (p_k)^2

其中，$p_k$ 是第 $k$ 类样本在数据集 $D$ 中的比例。基尼系数越小，数据集的纯度越高。

Python 实现如下：

import numpy as np

def gini(y):
    classes = np.unique(y)
    gini_val = 1.0
    for c in classes:
        p = np.sum(y == c) / len(y)
        gini_val -= p ** 2
    return gini_val

CART 采用贪心算法，遍历所有特征和可能的分裂点，选择基尼系数最小的分裂方式。

def find_best_split(X, y):
    best_gini = float('inf')
    best_feature = None
    best_value = None

    for feature in range(X.shape[1]):
        values = np.unique(X[:, feature])
        for value in values:
            left_mask = X[:, feature] <= value
            right_mask = ~left_mask

            if np.sum(left_mask) == 0 or np.sum(right_mask) == 0:
                continue

            gini_left = gini(y[left_mask])
            gini_right = gini(y[right_mask])

            total_gini = (np.sum(left_mask) * gini_left + np.sum(right_mask) * gini_right) / len(y)

            if total_gini < best_gini:
                best_gini = total_gini
                best_feature = feature
                best_value = value

    return best_feature, best_value

决策树的构建是一个递归过程，终止条件包括：

当前节点的样本全部属于同一类别。
没有更多特征可用于分裂。
达到预设的最大深度或最小样本数。

class Node:
    def __init__(self, feature=None, value=None, left=None, right=None, label=None):
        self.feature = feature  # 分裂特征
        self.value = value      # 分裂值
        self.left = left        # 左子树
        self.right = right      # 右子树
        self.label = label      # 叶子节点的类别

class DecisionTree:
    def __init__(self, max_depth=None, min_samples_split=2):
        self.max_depth = max_depth
        self.min_samples_split = min_samples_split
        self.tree = None

    def fit(self, X, y, depth=0):
        if len(np.unique(y)) == 1:
            return Node(label=y[0])

        if self.max_depth is not None and depth >= self.max_depth:
            return Node(label=np.argmax(np.bincount(y)))

        if len(y) < self.min_samples_split:
            return Node(label=np.argmax(np.bincount(y)))

        feature, value = find_best_split(X, y)

        if feature is None:
            return Node(label=np.argmax(np.bincount(y)))

        left_mask = X[:, feature] <= value
        right_mask = ~left_mask

        left = self.fit(X[left_mask], y[left_mask], depth + 1)
        right = self.fit(X[right_mask], y[right_mask], depth + 1)

        return Node(feature=feature, value=value, left=left, right=right)

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

    def _predict_one(self, x, node):
        if node.label is not None:
            return node.label

        if x[node.feature] <= node.value:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)

在实际应用中，CART 决策树可能会遇到以下问题，以下是三条避坑建议：