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

1次阅读

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

决策树是机器学习中最直观的算法之一，常用于分类和回归任务。它的优点在于模型可解释性强，能够处理数值型和类别型数据。然而，初学者在实际应用中常常遇到以下问题：

算法选择困难：ID3、C4.5、CART 等算法各有特点，不知道如何选择。
参数调优复杂：如何设置树的深度、最小样本分割等参数，直接影响模型性能。
实现细节多：递归构建树、剪枝策略等实现步骤较多，容易出错。

CART（Classification and Regression Trees）算法既可以用于分类也可以用于回归。与 ID3 和 C4.5 算法相比，CART 使用基尼系数（Gini Index）作为特征选择的准则，而不是信息增益或信息增益比。

基尼系数 ：衡量数据的不纯度，值越小表示数据越纯。计算公式为：
```
Gini(D) = 1 - Σ (p_i)^2
```
其中，p_i 是第 i 类样本在数据集 D 中的比例。
与 ID3 和 C4.5 的区别 ：
ID3 使用信息增益，倾向于选择取值较多的特征。
C4.5 使用信息增益比，克服了 ID3 的偏向性。
CART 使用基尼系数，计算更简单，且支持回归任务。

处理缺失值：填充或删除缺失值。
类别型特征编码：如使用独热编码（One-Hot Encoding）。
数据标准化：对于回归任务，可能需要标准化数值型特征。

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

预剪枝 ：在构建树的过程中，通过设置最大深度、最小样本数等参数提前停止树的生长。
后剪枝 ：先构建完整的树，然后自底向上剪枝，通过交叉验证选择最优的子树。

以下是 CART 算法的 Python 实现核心代码：

import numpy as np

class TreeNode:
    def __init__(self, feature=None, threshold=None, left=None, right=None, value=None):
        self.feature = feature  # 分裂特征
        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 = None
    best_threshold = None

    for feature in range(X.shape[1]):
        thresholds = np.unique(X[:, feature])
        for threshold in thresholds:
            left_indices = X[:, feature] <= threshold
            right_indices = X[:, feature] > threshold

            if len(left_indices) == 0 or len(right_indices) == 0:
                continue

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

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

    return best_feature, best_threshold

def build_tree(X, y, max_depth=5, min_samples_split=2):
    if len(np.unique(y)) == 1 or len(y) < min_samples_split or max_depth == 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

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

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

    left = build_tree(X[left_indices], y[left_indices], max_depth-1, min_samples_split)
    right = build_tree(X[right_indices], y[right_indices], max_depth-1, min_samples_split)

    return TreeNode(feature=feature, threshold=threshold, left=left, right=right)