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

1次阅读

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

决策树是机器学习中常用的算法，它通过树状结构对数据进行分类或回归。CART（Classification and Regression Trees）算法是一种广泛使用的决策树算法，相比 ID3 和 C4.5，它在处理连续值和分类问题上具有明显优势。

ID3 算法：只能处理离散特征，使用信息增益作为特征选择标准，容易偏向取值多的特征。
C4.5 算法：改进了 ID3，引入了信息增益比，可以处理连续特征，但仍偏向取值多的特征。
CART 算法：既能处理分类问题（使用基尼系数），也能处理回归问题（使用均方误差），并且可以处理连续特征和缺失值，适用性更广。

基尼系数（Gini Index）是 CART 算法中用于分类问题的特征选择标准。基尼系数越小，数据集的纯度越高。

基尼系数公式：
```
Gini(D) = 1 - Σ(p_i)^2
```
其中，p_i是第 i 类样本在数据集 D 中的比例。
信息增益：ID3 和 C4.5 使用的标准，基于信息熵，计算复杂度较高。

基尼系数计算更简单，且在实际应用中效果与信息增益类似，因此 CART 算法通常选择基尼系数。

CART 算法通过二分法处理连续特征：

对连续特征的所有取值进行排序。
遍历所有可能的分割点，计算基尼系数。
选择基尼系数最小的分割点作为最优分割点。

递归构建决策树时，需要设置终止条件以避免过拟合：

当前节点的样本数小于预设阈值。
当前节点的基尼系数小于预设阈值。
树的深度达到预设最大值。

以下是用 Python 实现 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              # 叶子节点的类别

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

    def fit(self, X, y):
        self.n_classes = len(np.unique(y))
        self.tree = self._grow_tree(X, y)

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

        # 终止条件
        if (depth == self.max_depth or
            n_samples < self.min_samples_split or
            n_classes == 1):
            return TreeNode(value=self._most_common_label(y))

        # 寻找最佳分裂
        best_gini = float('inf')
        best_feature, best_threshold = None, None

        for feature_idx in range(n_features):
            thresholds = np.unique(X[:, feature_idx])
            for threshold in thresholds:
                left_mask = X[:, feature_idx] <= threshold
                gini = self._gini_impurity(y, left_mask)
                if gini < best_gini:
                    best_gini = gini
                    best_feature = feature_idx
                    best_threshold = threshold

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

        return TreeNode(best_feature, best_threshold, left, right)

    def _gini_impurity(self, y, mask):
        n = len(y)
        if n == 0:
            return 0
        p_left = np.sum(mask) / n
        p_right = 1 - p_left
        gini_left = 1 - sum((np.sum(y[mask] == c) / np.sum(mask)) ** 2 for c in np.unique(y))
        gini_right = 1 - sum((np.sum(y[~mask] == c) / np.sum(~mask)) ** 2 for c in np.unique(y))
        return p_left * gini_left + p_right * gini_right

    def _most_common_label(self, y):
        return np.bincount(y).argmax()

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

    def _predict_one(self, x, node):
        if node.value is not None:
            return node.value
        if x[node.feature_idx] <= node.threshold:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)