决策树实战：从原理到实现，手把手教你用CART算法划分数据集

1次阅读

没有评论

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

在机器学习中，决策树是一种直观且强大的分类和回归工具。但对于初学者来说，如何正确地划分数据集、选择合适的特征往往是一个难题。今天，我们就来深入探讨 CART 算法的实现细节，帮助你快速掌握决策树的核心技术。

决策树的构建过程中，特征选择是关键。不同的划分方式会直接影响模型的性能和泛化能力。手动实现划分逻辑时，常见的问题包括：

如何量化划分的好坏？
如何高效地遍历所有可能的划分点？
如何处理连续型和分类型特征？

决策树算法有很多，常见的包括 ID3、C4.5 和 CART。它们的核心区别在于划分标准：

ID3：使用信息增益，倾向于选择取值多的特征
C4.5：使用信息增益比，解决了 ID3 的偏置问题
CART：使用基尼系数，可以同时处理分类和回归问题

CART 算法的优势在于：

计算效率高，基尼系数比信息熵计算更快
支持连续特征和缺失值处理
可以构建二叉树，模型结构更简单

基尼系数的计算公式很简单：

Gini(D) = 1 - Σ(p_i)^2

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

对于一个二分类问题，假设正样本比例为 p，那么基尼系数就是 2p(1-p)。

对每个特征进行排序
计算所有可能划分点的基尼系数
选择使基尼系数最小的划分点

这里有一个技巧：对于连续特征，我们只需要考察相邻样本的中点作为候选划分点。

下面是一个用 Python 实现的 CART 划分函数：

import numpy as np

def find_best_split(X, y):
    """寻找最优划分特征和划分点"""
    best_gini = float('inf')
    best_feature = None
    best_value = None

    # 遍历所有特征
    for feature in range(X.shape[1]):
        # 获取当前特征的所有值并排序
        values = np.sort(np.unique(X[:, feature]))

        # 遍历所有可能的划分点
        for i in range(1, len(values)):  # 跳过第一个值
            threshold = (values[i-1] + values[i]) / 2

            # 划分数据集
            left_indices = X[:, feature] <= threshold
            right_indices = X[:, feature] > threshold

            # 计算左右子集的基尼系数
            gini_left = calculate_gini(y[left_indices])
            gini_right = calculate_gini(y[right_indices])

            # 加权平均基尼系数
            total_gini = (len(y[left_indices]) * gini_left + 
                          len(y[right_indices]) * gini_right) / len(y)

            # 更新最优划分
            if total_gini < best_gini:
                best_gini = total_gini
                best_feature = feature
                best_value = threshold

    return best_feature, best_value

def calculate_gini(y):
    """计算基尼系数"""
    if len(y) == 0:
        return 0
    p = np.sum(y) / len(y)
    return 2 * p * (1 - p)

对于大数据集，CART 算法可能会遇到性能瓶颈。可以考虑以下优化方法：