从零开始构建CART决策树分类预测模型：原理详解与Python实战

1次阅读

没有评论

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

在机器学习分类任务中，我们常常需要在不同模型之间做出选择。线性模型（如逻辑回归）和树模型（如 CART 决策树）各有其适用场景：

线性模型 适合特征与目标之间存在近似线性关系的情况，模型简单且计算高效，但对非线性关系的捕捉能力有限。
树模型 则能够自动发现数据中的非线性关系和交互作用，对数据的分布假设较少，更适合处理复杂模式的数据。

对于新手来说，使用决策树时常见的问题包括：

容易产生过拟合，特别是在树深度过大时。
对特征重要性的判断可能存在偏差。
对连续特征的处理不够灵活。

决策树算法主要有 ID3、C4.5 和 CART 三种：

ID3：使用信息增益作为分裂标准，只能处理离散特征，容易偏向取值多的特征。
C4.5：改进 ID3，使用信息增益比，可以处理连续特征，但计算复杂度较高。
CART（本文重点）：使用基尼系数作为分裂标准，可以处理离散和连续特征，并且总是生成二叉树。

基尼系数公式推导：

对于有 K 个类别的分类问题，在节点 t 处的基尼系数定义为：

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

其中 $p(k|t)$ 是节点 t 中类别 k 的样本比例。基尼系数越小，表示节点的纯度越高。

import numpy as np

def gini_index(y: np.ndarray) -> float:
    """
    计算基尼系数
    :param y: 目标值数组
    :return: 基尼系数值
    """
    if len(y) == 0:
        return 0

    # 计算每个类别的比例
    _, counts = np.unique(y, return_counts=True)
    proportions = counts / len(y)

    # 计算基尼系数
    return 1 - np.sum(proportions ** 2)

class TreeNode:
    def __init__(self, feature_idx: int = None, threshold: float = None,
                 left=None, right=None, value=None):
        """
        决策树节点类
        :param feature_idx: 分裂特征索引
        :param threshold: 分裂阈值
        :param left: 左子树
        :param right: 右子树
        :param value: 叶节点的预测值
        """
        self.feature_idx = feature_idx
        self.threshold = threshold
        self.left = left
        self.right = right
        self.value = value

    def is_leaf(self) -> bool:
        """判断是否为叶节点"""
        return self.value is not None

def build_tree(X: np.ndarray, y: np.ndarray, max_depth: int = 5, 
              min_samples_split: int = 2) -> TreeNode:
    """
    递归构建决策树
    :param X: 特征矩阵
    :param y: 目标向量
    :param max_depth: 最大深度
    :param min_samples_split: 最小分裂样本数
    :return: 决策树根节点
    """
    # 终止条件 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.argmax(np.bincount(y)))

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

    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            # 根据阈值分割数据
            left_mask = X[:, feature_idx] <= threshold
            right_mask = ~left_mask

            # 计算分裂后的基尼系数
            gini_left = gini_index(y[left_mask])
            gini_right = gini_index(y[right_mask])

            # 加权平均基尼系数
            total_gini = (len(y[left_mask]) * gini_left + 
                          len(y[right_mask]) * gini_right) / len(y)

            if total_gini < best_gini:
                best_gini = total_gini
                best_feature = feature_idx
                best_threshold = threshold

    # 如果没有找到合适的分裂，返回叶节点
    if best_gini == float('inf'):
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 根据最佳分裂继续构建子树
    left_mask = X[:, best_feature] <= best_threshold
    right_mask = ~left_mask

    left_subtree = build_tree(X[left_mask], y[left_mask], 
                             max_depth-1, min_samples_split)
    right_subtree = build_tree(X[right_mask], y[right_mask], 
                              max_depth-1, min_samples_split)

    return TreeNode(feature_idx=best_feature, 
                   threshold=best_threshold,
                   left=left_subtree, 
                   right=right_subtree)

from sklearn.tree import DecisionTreeClassifier
from sklearn.model_selection import GridSearchCV

# 创建决策树分类器
tree = DecisionTreeClassifier(random_state=42)

# 定义参数网格
param_grid = {'max_depth': [3, 5, 7, None],
    'min_samples_split': [2, 5, 10],
    'min_samples_leaf': [1, 2, 4],
    'criterion': ['gini', 'entropy']
}

# 网格搜索
grid_search = GridSearchCV(tree, param_grid, cv=5, n_jobs=-1)
grid_search.fit(X_train, y_train)

# 输出最佳参数
print("Best parameters:", grid_search.best_params_)
print("Best score:", grid_search.best_score_)

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

plt.figure(figsize=(20, 10))
plot_tree(grid_search.best_estimator_, 
          filled=True, 
          feature_names=feature_names,
          class_names=class_names,
          rounded=True)
plt.show()

类别不平衡处理：
设置 class_weight='balanced' 让模型自动调整类别权重
手动指定类别权重：class_weight={0: 1, 1: 5}

无效特征识别：

import pandas as pd

# 获取特征重要性
feature_importance = pd.DataFrame({
    'feature': feature_names,
    'importance': grid_search.best_estimator_.feature_importances_
}).sort_values('importance', ascending=False)

# 可视化
feature_importance.plot.bar(x='feature', y='importance')
plt.show()

如何处理连续特征中的缺失值？可以考虑哪些填充策略？
除了基尼系数，还可以使用哪些指标作为分裂标准？它们各有什么优缺点？
决策树容易过拟合，除了预剪枝，还可以采用哪些后剪枝策略？

通过本文，我们从理论到实践完整地实现了 CART 决策树分类模型。从基尼系数的数学原理，到 Python 原生实现，再到 sklearn 的生产级应用，希望这篇教程能帮助初学者全面理解决策树的工作原理和实际应用。决策树模型直观易懂，是入门机器学习的不错选择，但也要注意其容易过拟合的特点，合理使用剪枝策略和参数调优。

正文完