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

1次阅读

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

决策树是机器学习中广泛使用的算法，因其直观、易于解释的特性，常被用于分类和回归任务。在众多决策树算法中，CART（Classification and Regression Trees）因其处理连续值和分类问题的优势而备受青睐。与 ID3 和 C4.5 相比，CART 算法不仅支持连续特征，还能处理回归任务，且通过基尼系数进行特征选择，计算效率更高。

基尼系数和信息增益是两种不同的特征选择标准。基尼系数衡量数据的不纯度，值越小表示数据越纯。与信息增益相比，基尼系数的计算不涉及对数运算，因此计算速度更快，尤其适合大规模数据集。

基尼系数公式：
```
Gini(D) = 1 - Σ (p_i)^2
```
其中，p_i是第 i 类样本在数据集 D 中的比例。
信息增益公式：
```
Gain(D, A) = Entropy(D) - Σ (|D_v| / |D|) * Entropy(D_v)
```
其中，Entropy(D)是数据集 D 的信息熵，D_v是特征 A 的第 v 个子集。

CART 算法通过二分法处理连续特征。具体步骤如下：

对连续特征的所有取值进行排序。
计算相邻取值的中间点作为候选分割点。
选择基尼系数最小的分割点作为最优分割点。

递归构建决策树时，需设置终止条件以避免过拟合。常见的终止条件包括：

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

以下是一个使用 Python 实现 CART 分类树的示例代码：

import numpy as np

class Node:
    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 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 _gini(self, y):
        m = len(y)
        return 1.0 - sum((np.sum(y == c) / m) ** 2 for c in range(self.n_classes))

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

        for feature in range(X.shape[1]):
            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):
        if depth == self.max_depth or len(y) < self.min_samples_split or self._gini(y) == 0:
            return Node(value=np.argmax(np.bincount(y)))

        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 Node(feature, threshold, left, right)

    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] <= node.threshold:
            return self._predict_one(x, node.left)
        else:
            return self._predict_one(x, node.right)