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

1次阅读

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

决策树作为经典的机器学习算法，在分类问题上展现出了独特的优势：模型结构直观可解释，不需要复杂的特征缩放处理，且能自动处理特征间的非线性关系。今天我们就用 Python 从零实现 CART 算法，并用鸢尾花数据集验证效果。

基尼系数与分裂选择
CART 采用基尼系数衡量节点纯度，定义为：
```
Gini = 1 - Σ(p_i^2)  # p_i 是当前节点第 i 类样本占比
```
分裂时遍历所有特征和切分点，选择使基尼系数下降最大的划分方式。
连续值特征处理
对于连续值特征（如花瓣长度）：
将特征值排序后取相邻值中点作为候选切分点
示例：样本值 [1.1, 1.3, 1.7, 1.8] 的候选点为[1.2, 1.5, 1.75]
计算每个切分点的基尼系数，选择最优解
递归停止条件
需要设置以下条件防止过拟合：
最大树深度(max_depth)
节点最小样本数(min_samples_leaf)
节点基尼系数小于阈值

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 gini(y):
    _, counts = np.unique(y, return_counts=True)
    return 1 - np.sum((counts/len(y))**2)

def build_tree(X, y, max_depth=5, min_samples_leaf=5):
    # 终止条件判断
    if (max_depth <= 0 or len(y) < min_samples_leaf 
        or gini(y) < 0.05):
        return TreeNode(value=np.argmax(np.bincount(y)))

    best_gini = float('inf')
    best_feature, best_thresh = None, None

    # 遍历所有特征和切分点
    for feature_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feature_idx])
        for thresh in thresholds:
            left_idx = X[:, feature_idx] <= thresh
            g = (gini(y[left_idx]) * len(y[left_idx]) + 
                 gini(y[~left_idx]) * len(y[~left_idx])) / len(y)
            if g < best_gini:
                best_gini = g
                best_feature = feature_idx
                best_thresh = thresh

    # 递归构建子树
    left_idx = X[:, best_feature] <= best_thresh
    left = build_tree(X[left_idx], y[left_idx], max_depth-1)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1)
    return TreeNode(best_feature, best_thresh, left, right)

数据准备

from sklearn.datasets import load_iris
iris = load_iris()
X, y = iris.data[:, :2], iris.target  # 只用前两个特征

可视化决策边界

def plot_boundary(tree, X, y):
    x_min, x_max = X[:, 0].min()-1, X[:, 0].max()+1
    y_min, y_max = X[:, 1].min()-1, X[:, 1].max()+1
    xx, yy = np.meshgrid(np.arange(x_min, x_max, 0.02),
                         np.arange(y_min, y_max, 0.02))
    Z = predict(np.c_[xx.ravel(), yy.ravel()], tree)
    plt.contourf(xx, yy, Z.reshape(xx.shape), alpha=0.4)
    plt.scatter(X[:,0], X[:,1], c=y, s=20, edgecolor='k')