决策树实战：基于基尼系数的CART算法实现与调优指南

1次阅读

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

在机器学习领域，分类任务一直是最基础也是最重要的任务之一。在众多分类算法中，决策树因其出色的可解释性和接近人类的决策过程而广受欢迎。其中，CART(Classification and Regression Trees) 算法因其高效和灵活性，成为工业界最常用的决策树算法之一。

然而，在实际应用中，特别是处理高维数据时，基尼系数的计算往往会成为性能瓶颈。今天我们就来深入探讨这个问题，并给出完整的解决方案。

基尼系数是 CART 算法用于特征选择的重要指标，它衡量的是一个数据集的纯度。其数学定义如下：

$$Gini(p) = 1-\sum_{k=1}^K p_k^2$$

其中，$p_k$ 表示数据集中第 k 类样本所占的比例。

与信息增益相比，基尼系数有两个显著优势：

计算更加高效，不需要计算对数
对类别不平衡的数据集更加鲁棒

下面我们来看如何用 Python 实现基于基尼系数的 CART 算法。首先，我们需要实现基尼系数的计算函数：

import numpy as np
from typing import List, Tuple

def calculate_gini(y: np.ndarray) -> float:
    """
    计算基尼系数
    :param y: 目标值数组
    :return: 基尼系数
    """
    if len(y) == 0:
        return 0

    # 计算每个类别的比例
    _, counts = np.unique(y, return_counts=True)
    proportions = counts / len(y)

    # 计算基尼系数
    gini = 1 - np.sum(proportions ** 2)
    return gini

接下来是递归建树的核心逻辑：

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 build_tree(X: np.ndarray, y: np.ndarray, max_depth: int = None, min_samples_split: int = 2) -> TreeNode:
    """
    递归构建决策树
    :param X: 特征矩阵
    :param y: 目标值
    :param max_depth: 最大深度
    :param min_samples_split: 分裂所需最小样本数
    :return: 决策树根节点
    """
    # 终止条件 1：所有样本属于同一类别
    if len(np.unique(y)) == 1:
        return TreeNode(value=y[0])

    # 终止条件 2：样本数小于最小分裂样本数
    if len(y) < min_samples_split:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 终止条件 3：达到最大深度
    if max_depth is not None and max_depth <= 0:
        return TreeNode(value=np.argmax(np.bincount(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 = ~left_indices

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

            # 计算加权基尼系数
            left_gini = calculate_gini(y[left_indices])
            right_gini = calculate_gini(y[right_indices])
            weighted_gini = (sum(left_indices) * left_gini + sum(right_indices) * right_gini) / len(y)

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

    # 如果没有找到合适的特征分裂，则返回叶子节点
    if best_gini == float('inf'):
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 递归构建左右子树
    left_indices = X[:, best_feature] <= best_threshold
    right_indices = ~left_indices

    left_subtree = build_tree(X[left_indices], y[left_indices], 
                             max_depth=max_depth-1 if max_depth is not None else None,
                             min_samples_split=min_samples_split)

    right_subtree = build_tree(X[right_indices], y[right_indices],
                              max_depth=max_depth-1 if max_depth is not None else None,
                              min_samples_split=min_samples_split)

    return TreeNode(feature_idx=best_feature, threshold=best_threshold, 
                   left=left_subtree, right=right_subtree)

虽然我们从零实现了 CART 算法，但在实际项目中，我们通常会使用成熟的库如 scikit-learn：

from sklearn.tree import DecisionTreeClassifier
from sklearn.datasets import load_iris
from sklearn.model_selection import train_test_split

# 加载数据
iris = load_iris()
X, y = iris.data, iris.target

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

# 创建决策树模型，使用基尼系数
clf = DecisionTreeClassifier(criterion='gini', 
                            max_depth=3,
                            min_samples_split=2,
                            random_state=42)

# 训练模型
clf.fit(X_train, y_train)

# 评估模型
print(f"Test accuracy: {clf.score(X_test, y_test):.2f}")

在处理高维数据时，决策树的训练可能会很慢。以下是几个优化建议：

并行化特征选择 ：使用 joblib 并行计算每个特征的基尼系数

from joblib import Parallel, delayed

def find_best_split_parallel(X, y, n_jobs=-1):
    """并行寻找最佳分裂"""
    def _eval_feature(feature_idx):
        # 评估单个特征的实现代码
        pass

    results = Parallel(n_jobs=n_jobs)(delayed(_eval_feature)(i) for i in range(X.shape[1])
    )

    # 找出最佳分裂
    best_result = min(results, key=lambda x: x[1])
    return best_result