使用CART决策树构建高效数据表：原理与实战避坑指南

1次阅读

没有评论

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

在数据分析和机器学习领域，决策表是一种常见的数据表示方法。然而，传统决策表方法存在几个明显的局限性：

过拟合问题：特别是在处理高维数据时，容易生成过于复杂的决策规则
计算效率低下：随着数据量增大，训练时间呈指数级增长
特征选择困难：缺乏系统性的特征重要性评估方法
可解释性差：复杂的决策规则难以向业务方解释

这些痛点使得传统决策表在实际应用中效果大打折扣，而 CART(Classification and Regression Trees)决策树算法为解决这些问题提供了有效方案。

决策树算法有多种，最流行的包括 ID3、C4.5 和 CART。它们的主要区别在于：

ID3 算法
使用信息增益作为特征选择标准
只能处理离散型特征
容易产生过拟合
不支持回归任务
C4.5 算法
改进 ID3，使用信息增益比
可以处理连续型特征
引入了剪枝机制
仍然不支持回归任务
CART 算法
使用基尼系数 (分类) 或最小二乘(回归)
支持连续和离散特征
支持分类和回归任务
二叉树结构，计算效率高
提供特征重要性评估

对于构建数据表的应用场景，CART 算法因其高效的二叉树结构、支持回归任务和内置的特征重要性评估而成为最佳选择。

基尼系数是 CART 用于分类问题的特征选择标准，计算一个特征对数据纯度提升的程度。基尼系数越小，说明数据纯度越高。

基尼系数的计算公式为：

def gini_index(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

下面是一个完整的 CART 决策树实现，包含数据预处理、模型训练和预测：

import numpy as np
from collections import Counter

class DecisionNode:
    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  # 叶节点值

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

    def fit(self, X, y):
        self.n_classes = len(set(y))
        self.n_features = X.shape[1]
        self.root = self._grow_tree(X, y)

    def _gini(self, y):
        counts = np.bincount(y)
        ps = counts / len(y)
        return 1 - np.sum(ps ** 2)

    def _best_split(self, X, y):
        best_gini = float('inf')
        best_feature, best_threshold = None, None

        for feature in range(self.n_features):
            thresholds = np.unique(X[:, feature])
            for threshold in thresholds:
                left_indices = X[:, feature] < threshold
                gini = self._gini(y[left_indices]) * np.sum(left_indices) / len(y) + \
                       self._gini(y[~left_indices]) * np.sum(~left_indices) / len(y)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature
                    best_threshold = threshold

        return best_feature, best_threshold

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

        # 终止条件
        if (self.max_depth is not None and depth >= self.max_depth) or \
           n_labels == 1 or n_samples < self.min_samples_split:
            counter = Counter(y)
            value = counter.most_common(1)[0][0]
            return DecisionNode(value=value)

        # 寻找最佳分裂
        feature, threshold = self._best_split(X, y)
        left_indices = X[:, feature] < threshold

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

        return DecisionNode(feature, threshold, left, right)

    def predict(self, X):
        return np.array([self._traverse_tree(x, self.root) for x in X])

    def _traverse_tree(self, x, node):
        if node.value is not None:
            return node.value

        if x[node.feature] < node.threshold:
            return self._traverse_tree(x, node.left)
        else:
            return self._traverse_tree(x, node.right)

剪枝是防止决策树过拟合的关键技术，主要有两种方法：

预剪枝(Pre-pruning)
在树生长过程中提前停止
通过设置 max_depth、min_samples_split 等参数控制
实现简单，但可能欠拟合
后剪枝(Post-pruning)
先让树完全生长，再剪去不重要的分支
基于验证集错误率进行剪枝
效果更好但计算成本高

决策树的训练可以通过以下方式并行化：

特征并行：不同特征的分裂点计算可以并行进行
数据并行：将数据分片，在不同节点上计算统计量
树并行：构建多棵树时并行训练(如随机森林)

使用类权重参数(class_weight)
过采样少数类或欠采样多数类
使用 F1-score 等不平衡指标评估模型

CART 提供了内置的特征重要性评估方法：

def feature_importance(self):
    importance = np.zeros(self.n_features)
    self._compute_importance(self.root, importance)
    return importance / np.sum(importance)

def _compute_importance(self, node, importance):
    if node.value is not None:
        return

    # 计算该节点的重要性
    importance[node.feature] += node.impurity - \
        (node.left.impurity * node.left.n_samples + \
         node.right.impurity * node.right.n_samples) / node.n_samples

    self._compute_importance(node.left, importance)
    self._compute_importance(node.right, importance)

限制树的最大深度(通常 3 - 5 层)
输出决策路径
使用 SHAP 或 LIME 等解释工具

下面我们用一个信用卡申请审批的案例展示 CART 决策树的应用：

import pandas as pd
from sklearn.model_selection import train_test_split
from sklearn.metrics import accuracy_score

# 加载数据
data = pd.read_csv('credit_approval.csv')

# 数据预处理
X = data.drop('Approval', axis=1).values
y = data['Approval'].values

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

# 训练模型
tree = CARTDecisionTree(max_depth=5)
tree.fit(X_train, y_train)

# 评估
predictions = tree.predict(X_test)
print(f"Accuracy: {accuracy_score(y_test, predictions):.2f}")

# 特征重要性
importance = tree.feature_importance()
for i, imp in enumerate(importance):
    print(f"Feature {i}: {imp:.3f}")

CART 决策树是构建高效数据表的强大工具，它结合了良好的解释性和不错的预测性能。但在实际应用中还需要考虑：