深入解析CART决策树算法实现：从数学原理到Python实战

1次阅读

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

决策树通过递归分割数据空间，能自动识别最具区分度的特征组合。其产生的 if-else 规则天然可解释，特别适合需要特征重要性分析的场景。相比神经网络等黑盒模型，决策树在特征交互关系的可视化呈现上具有独特优势。

熵衡量样本集合的混乱程度，计算公式：
```
H(D) = -Σ(p_k * log2(p_k))
```
信息增益 = 父节点熵 – 加权子节点熵

解决 ID3 对多值特征的偏好问题：

Gain_ratio(D,A) = Gain(D,A) / IV(A)
IV(A) = -Σ(|D_v|/|D| * log2(|D_v|/|D|))

衡量数据不纯度的替代指标：
```
Gini(D) = 1 - Σ(p_k^2)
```
计算效率比熵更高（省去对数运算）

class TreeNode:
    def __init__(self, feat_idx=None, threshold=None,
                 left=None, right=None, value=None):
        self.feat_idx = feat_idx   # 分裂特征索引
        self.threshold = threshold # 分裂阈值
        self.left = left           # 左子树
        self.right = right         # 右子树
        self.value = value         # 叶节点预测值

def gini_impurity(y):
    m = y.shape[0]
    return 1.0 - sum((np.sum(y == c) / m) ** 2 for c in np.unique(y))

寻找最佳分裂特征和阈值：

def find_best_split(X, y):
    best_gini = float('inf')
    best_idx, best_thresh = None, None

    for feat_idx in range(X.shape[1]):
        thresholds = np.unique(X[:, feat_idx])
        for thresh in thresholds:
            left_idx = X[:, feat_idx] <= thresh
            gini = (len(y[left_idx]) * gini_impurity(y[left_idx]) + 
                    len(y[~left_idx]) * gini_impurity(y[~left_idx])) / len(y)
            if gini < best_gini:
                best_gini = gini
                best_idx = feat_idx
                best_thresh = thresh
    return best_idx, best_thresh

递归构建树：

def build_tree(X, y, max_depth=5, min_samples_split=2):
    if len(y) < min_samples_split or max_depth <= 0:
        return TreeNode(value=np.argmax(np.bincount(y)))

    feat_idx, thresh = find_best_split(X, y)
    left_idx = X[:, feat_idx] <= thresh

    left = build_tree(X[left_idx], y[left_idx], max_depth-1, min_samples_split)
    right = build_tree(X[~left_idx], y[~left_idx], max_depth-1, min_samples_split)
    return TreeNode(feat_idx, thresh, left, right)