决策树实战：从原理到实现CART算法构建决策树例题解析

1次阅读

没有评论

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

决策树是机器学习中最直观且易于解释的算法之一，广泛应用于分类和回归问题。然而，初学者在实践过程中常遇到以下几个问题：

算法选择困难：ID3、C4.5、CART 等算法各有特点，初学者容易混淆其适用场景。
参数调优复杂：如何选择分裂标准、剪枝策略等参数对模型性能影响显著，但缺乏系统指导。
实现细节模糊：递归构建树的过程、基尼系数的计算等关键步骤常被忽略，导致模型效果不佳。

本文将重点介绍 CART（Classification and Regression Trees）算法，它既能处理分类问题，也能处理回归问题，且采用基尼系数作为分裂标准，更适合实际应用。

CART 算法的核心在于通过基尼系数（Gini Index）衡量数据的不纯度，并选择最优特征进行分裂。基尼系数的计算公式如下：

[Gini(D) = 1 – \sum_{i=1}^{k} p_i^2 ]

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

与 ID3 和 C4.5 算法相比，CART 有以下区别：

分裂标准：ID3 使用信息增益，C4.5 使用信息增益率，而 CART 使用基尼系数。
树结构：CART 生成二叉树，而 ID3 和 C4.5 生成多叉树。
适用性：CART 能同时处理分类和回归问题，而 ID3 和 C4.5 仅适用于分类问题。

处理缺失值：填充或删除缺失值。
特征编码：将类别型特征转换为数值型。

计算当前节点的基尼系数。
遍历所有特征及其可能的分裂点，选择基尼系数最小的特征和分裂点。
根据选定的特征和分裂点将数据集分为左右子集。
对左右子集递归调用上述步骤，直到满足停止条件（如节点样本数小于阈值或基尼系数为 0）。

为避免过拟合，可采用代价复杂度剪枝（Cost-Complexity Pruning），通过交叉验证选择最优子树。

以下是一个简化的 CART 算法实现，包含基尼系数计算和树构建的关键代码：

import numpy as np

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):
    classes = np.unique(y)
    gini = 1.0
    for c in classes:
        p = np.sum(y == c) / len(y)
        gini -= p ** 2
    return gini

def find_best_split(X, 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_indices = X[:, feature_idx] <= threshold
            right_indices = X[:, feature_idx] > threshold

            gini_left = gini(y[left_indices])
            gini_right = gini(y[right_indices])
            weighted_gini = (len(y[left_indices]) * gini_left + len(y[right_indices]) * gini_right) / len(y)

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

    return best_feature, best_threshold

def build_tree(X, y, max_depth=None, min_samples_split=2, depth=0):
    if len(y) == 0:
        return None

    if len(np.unique(y)) == 1:
        return TreeNode(value=y[0])

    if max_depth is not None and depth >= max_depth:
        return TreeNode(value=np.argmax(np.bincount(y)))

    if len(y) < min_samples_split:
        return TreeNode(value=np.argmax(np.bincount(y)))

    feature_idx, threshold = find_best_split(X, y)
    if feature_idx is None:
        return TreeNode(value=np.argmax(np.bincount(y)))

    left_indices = X[:, feature_idx] <= threshold
    right_indices = X[:, feature_idx] > threshold

    left_subtree = build_tree(X[left_indices], y[left_indices], max_depth, min_samples_split, depth + 1)
    right_subtree = build_tree(X[right_indices], y[right_indices], max_depth, min_samples_split, depth + 1)

    return TreeNode(feature_idx, threshold, left_subtree, right_subtree)

CART 算法的时间复杂度主要取决于树的深度和特征数量。假设有 (n) 个样本和 (m) 个特征，最坏情况下时间复杂度为(O(n \cdot m \cdot \log n) )。

优化技巧：