决策树实战：从CART算法原理到分类问题完整实现

1次阅读

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

决策树作为经典的机器学习算法，在分类问题上有着天然的优势：模型结构直观可解释，连非技术人员也能理解其判断逻辑；对数据分布没有严格要求，不需要烦琐的特征缩放处理。下面我们就用 CART 算法手把手实现一个完整的决策树分类器。

决策树的构建过程就是不断寻找最佳分裂特征和分裂点的过程。CART 算法采用基尼系数（Gini Index）作为划分标准，其计算公式为：

def gini_index(groups, classes):
    # groups 是分裂后的左右子集
    # classes 是所有类别标签
    n_instances = 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_instances)
    return gini

对于连续值特征，我们需要遍历所有可能的分割点。假设有一个特征值为 [1.2, 2.4, 3.1, 4.8]，则候选分割点为相邻值的平均值：

排序特征值：[1.2, 2.4, 3.1, 4.8]
计算中点：(1.2+2.4)/2=1.8, (2.4+3.1)/2=2.75, (3.1+4.8)/2=3.95
对每个分割点计算基尼系数
选择使基尼系数最小的分割点

首先定义树节点结构：

class TreeNode:
    def __init__(self, feature_index=None, threshold=None,
                 left=None, right=None, value=None):
        self.feature_index = feature_index  # 分裂特征索引
        self.threshold = threshold          # 分裂阈值
        self.left = left                    # 左子树
        self.right = right                  # 右子树
        self.value = value                  # 叶节点预测值

然后是核心的建树函数（关键代码已添加中文注释）：

def build_tree(X, y, max_depth, min_samples_split):
    # 如果达到最大深度或样本数不足，则创建叶节点
    if max_depth <=0 or len(X) < min_samples_split:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    best_gini = 1.0
    best_feature = None
    best_threshold = None

    for feature_index in range(X.shape[1]):
        # 对当前特征所有可能的分割点进行尝试
        thresholds = np.unique(X[:, feature_index])
        for threshold in thresholds:
            # 按当前分割点划分数据集
            left_indices = X[:, feature_index] < threshold
            right_indices = ~left_indices

            # 计算基尼系数
            current_gini = gini_index([y[left_indices], y[right_indices]],
                np.unique(y)
            )

            # 更新最佳分裂
            if current_gini < best_gini:
                best_gini = current_gini
                best_feature = feature_index
                best_threshold = threshold

    # 递归构建左右子树
    left_indices = X[:, best_feature] < best_threshold
    left = build_tree(X[left_indices], y[left_indices], 
                     max_depth-1, min_samples_split)
    right = build_tree(X[~left_indices], y[~left_indices],
                      max_depth-1, min_samples_split)

    return TreeNode(best_feature, best_threshold, left, right)

加载数据并训练模型：

from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data, iris.target

# 训练决策树
tree = build_tree(X, y, max_depth=3, min_samples_split=5)

# 可视化决策边界（以两个特征为例）plt.figure(figsize=(10, 6))
plot_decision_boundary(tree, X[:, :2], y)
plt.xlabel(iris.feature_names[0])
plt.ylabel(iris.feature_names[1])
plt.show()