决策树实战：从零构建CART算法并解决分类问题

1次阅读

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

决策树是一种模仿人类决策过程的机器学习模型，通过一系列的判断规则对数据进行分类或回归。它的结构就像一棵倒置的树，从根节点开始，根据特征的不同取值不断分支，直到到达叶节点给出预测结果。

CART（Classification and Regression Trees）算法是决策树家族中的经典成员，由 Breiman 等人在 1984 年提出。它的特点是：

二叉树结构：每个节点最多分裂成两个子节点
可用于分类和回归任务
使用基尼系数（分类）或均方误差（回归）作为分裂标准
支持连续特征和类别特征的处理

基尼系数衡量数据的不纯度，值越小表示数据越纯。对于包含 K 个类别的数据集 D，基尼系数计算公式为：

Gini(D) = 1 - Σ(p_i)^2 (i=1 to K)

其中 p_i 是第 i 类样本在 D 中的比例。

选择最佳分裂特征的步骤：

对每个特征的所有可能分割点计算基尼指数
选择使基尼指数最小的特征和分割点
基尼指数的计算公式：

Gini_index(D, A) = |D1|/|D| * Gini(D1) + |D2|/|D| * Gini(D2)

其中 A 是特征，D1 和 D2 是分割后的两个子集。

我们使用 sklearn 中的鸢尾花数据集：

from sklearn.datasets import load_iris
import numpy as np

iris = load_iris()
X = iris.data
y = iris.target

def gini(y):
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / counts.sum()
    return 1 - np.sum(probabilities ** 2)

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              # 叶节点的预测值

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

    # 终止条件 2：样本数小于最小分裂数量
    if len(y) < min_samples_split:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 终止条件 3：达到最大深度
    if max_depth is not None and max_depth <= 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    best_gini = float('inf')
    best_feature = None
    best_threshold = 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(y[left_mask])
            gini_right = gini(y[right_mask])

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

            if weighted_gini < best_gini:
                best_gini = weighted_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 if max_depth is not None else None,
                             min_samples_split)
    right_subtree = build_tree(X[right_mask], y[right_mask],
                              max_depth-1 if max_depth is not None else None,
                              min_samples_split)

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

def predict(tree, x):
    if tree.value is not None:
        return tree.value

    if x[tree.feature_idx] <= tree.threshold:
        return predict(tree.left, x)
    else:
        return predict(tree.right, x)

决策树容易过拟合训练数据，常见解决方法：