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

1次阅读

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

决策树是一种模仿人类决策过程的机器学习方法，通过一系列规则对数据进行分类或回归。CART（Classification and Regression Trees）是其中最经典的算法之一，它的特点是：

二叉树结构：每个节点最多有两个分支
可用于分类和回归任务
使用基尼系数作为分类问题的分裂标准
能够处理连续型和离散型特征

基尼系数衡量数据的不纯度，计算公式为：

Gini = 1 - Σ(p_i)^2

其中 p_i 是第 i 类样本在数据集中的比例。基尼系数越小，说明数据集纯度越高。

对每个特征计算所有可能分割点的基尼系数
选择使基尼系数下降最多的特征和分割点
递归地对子集重复上述过程

对于连续特征，通常需要先排序然后尝试相邻值的中点作为候选分割点。

import numpy as np
from sklearn.datasets import load_iris

# 加载鸢尾花数据集
iris = load_iris()
X = iris.data
y = iris.target

# 训练测试集划分
from sklearn.model_selection import train_test_split
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

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

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

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

    def fit(self, X, y):
        self.n_classes = len(np.unique(y))
        self.tree = self._grow_tree(X, y)

    def _grow_tree(self, X, y, depth=0):
        n_samples, n_features = X.shape
        n_classes = len(np.unique(y))

        # 停止条件
        if (self.max_depth is not None and depth >= self.max_depth) or \
           n_samples < self.min_samples_split or n_classes == 1:
            return TreeNode(value=np.argmax(np.bincount(y)))

        # 寻找最佳分裂
        best_gini = float('inf')
        for feature_idx in range(n_features):
            thresholds = np.unique(X[:, feature_idx])
            for threshold in thresholds:
                left_indices = X[:, feature_idx] <= threshold
                gini = self._gini_split(y, left_indices)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature_idx
                    best_threshold = threshold
                    best_left = left_indices

        # 递归构建子树
        left = self._grow_tree(X[best_left], y[best_left], depth+1)
        right = self._grow_tree(X[~best_left], y[~best_left], depth+1)
        return TreeNode(best_feature, best_threshold, left, right)

    def _gini_split(self, y, left_indices):
        p = np.sum(left_indices) / len(y)
        return p * gini(y[left_indices]) + (1 - p) * gini(y[~left_indices])

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

    def _predict(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature_idx] <= node.threshold:
            return self._predict(x, node.left)
        else:
            return self._predict(x, node.right)

决策树容易过拟合，常用解决方案：