CLS决策树从入门到实战：原理详解与Python实现

1次阅读

没有评论

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

背景痛点：为什么需要 CLS 决策树？
原理解析：信息增益与算法对比
代码实现：从零搭建 CLS 决策树
避坑指南：三个常见问题解决方案
性能优化：效率与效果的平衡
动手挑战：鸢尾花分类实战

传统决策树（如 ID3）在处理分类任务时存在明显缺陷：

信息增益偏向多值特征：倾向于选择取值较多的特征，可能导致无意义分裂（如按 ID 编号划分）
缺失连续值处理：ID3 算法原生不支持连续特征，需要人工离散化
过拟合风险高：没有剪枝机制时容易生成复杂树结构

CLS 决策树通过以下改进解决这些问题：

引入增益率（C4.5）或基尼系数（CART）替代原始信息增益
内置连续值处理机制
支持预剪枝和后剪枝策略

信息熵计算（ID3 算法基础）：

H(D) = -Σ(p_k * log₂p_k)

其中 p_k 是数据集中第 k 类样本的比例

信息增益改进（C4.5 算法核心）：

Gain_ratio = Gain(D,a) / IV(a)
IV(a) = -Σ(|D_v|/|D| * log₂(|D_v|/|D|))

IV(a)称为特征 a 的固有值，用于消除多值特征偏差

基尼系数（CART 算法采用）：

Gini(D) = 1 - Σ(p_k²)

算法	分裂标准	支持连续值	树结构	剪枝方式
ID3	信息增益	否	多叉树	无
C4.5	增益率	是	多叉树	PEP 剪枝
CART	基尼系数	是	二叉树	CCP 剪枝

from typing import List, Dict, Union
import numpy as np

class TreeNode:
    def __init__(self, 
                 feature_idx: int = None, 
                 threshold: float = None,
                 value: int = None,
                 left: 'TreeNode' = None,
                 right: 'TreeNode' = None):
        # 分裂特征索引（非叶子节点）self.feature_idx = feature_idx  
        # 分裂阈值（连续特征）self.threshold = threshold  
        # 节点类别（叶子节点）self.value = value  
        # 左右子树
        self.left, self.right = left, right  

class CLSDecisionTree:
    def __init__(self, 
                 max_depth: int = 5,
                 min_samples_split: int = 2,
                 criterion: str = 'gini'):
        # 控制树深防止过拟合
        self.max_depth = max_depth  
        # 节点最小分裂样本数
        self.min_samples_split = min_samples_split  
        # 分裂标准（gini/entropy）self.criterion = criterion  
        self.root = None

1. 计算基尼不纯度

def _gini(self, y: np.ndarray) -> float:
    """计算基尼系数"""
    _, counts = np.unique(y, return_counts=True)
    probabilities = counts / counts.sum()
    return 1 - np.sum(probabilities ** 2)

2. 寻找最佳分裂点

def _find_best_split(self, X: np.ndarray, y: np.ndarray) -> Dict:
    """遍历所有特征和阈值寻找最佳分裂方案"""
    best_gini = 1.0
    best_feature = None
    best_threshold = None

    for feature_idx in range(X.shape[1]):
        # 对连续特征进行排序
        thresholds = np.unique(X[:, feature_idx])
        for threshold in thresholds:
            # 按当前阈值划分数据集
            left_mask = X[:, feature_idx] <= threshold
            right_mask = ~left_mask

            # 计算分裂后的加权基尼系数
            n_left, n_right = np.sum(left_mask), np.sum(right_mask)
            gini_left = self._gini(y[left_mask])
            gini_right = self._gini(y[right_mask])
            weighted_gini = (n_left * gini_left + n_right * gini_right) / len(y)

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

    return {'feature_idx': best_feature, 
            'threshold': best_threshold,
            'gini': best_gini}

3. 递归构建决策树

def _build_tree(self, 
               X: np.ndarray, 
               y: np.ndarray, 
               depth: int = 0) -> TreeNode:
    """核心建树逻辑"""
    # 终止条件 1：达到最大深度
    if depth >= self.max_depth:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 终止条件 2：样本数不足或纯度足够
    if len(y) < self.min_samples_split or len(np.unique(y)) == 1:
        return TreeNode(value=np.argmax(np.bincount(y)))

    # 寻找最佳分裂
    split_info = self._find_best_split(X, y)

    # 分裂数据集
    left_mask = X[:, split_info['feature_idx']] <= split_info['threshold']
    right_mask = ~left_mask

    # 递归构建子树
    left_subtree = self._build_tree(X[left_mask], y[left_mask], depth+1)
    right_subtree = self._build_tree(X[right_mask], y[right_mask], depth+1)

    return TreeNode(feature_idx=split_info['feature_idx'],
                   threshold=split_info['threshold'],
                   left=left_subtree,
                   right=right_subtree)

解决方案：

设置 max_depth 和min_samples_split参数限制树生长
实现后剪枝（Post-Pruning）：
预留验证集
自底向上考察非叶子节点
比较剪枝前后在验证集上的准确率

改进方法：

在计算信息增益 / 基尼系数时引入类别权重：

class_weights = len(y) / (len(np.unique(y)) * np.bincount(y))
weighted_gini = np.sum([(count/len(y))**2 * w 
                       for count, w in zip(counts, class_weights)])

最佳实践：

使用等频分箱（pd.qcut）替代等宽分箱

对缺失值单独处理：

# 在_find_best_split 方法中添加缺失值处理
missing_mask = np.isnan(X[:, feature_idx])
if np.any(missing_mask):
    # 将缺失值单独划分到一侧
    left_mask = (~missing_mask) & (X[:, feature_idx] <= threshold)

特征预排序：对连续特征预先排序，加速阈值搜索
并行化处理：对不同特征的分裂评估使用多进程
采样策略：当数据量大时，对每个节点分裂只使用部分样本

对于类别型特征，存储 category 类型而非字符串

实现 predict 方法时避免递归调用：

def predict(self, X: np.ndarray) -> np.ndarray:
    """非递归预测方法"""
    preds = []
    for sample in X:
        node = self.root
        while node.value is None:  # 非叶子节点
            if sample[node.feature_idx] <= node.threshold:
                node = node.left
            else:
                node = node.right
        preds.append(node.value)
    return np.array(preds)

使用 sklearn 的鸢尾花数据集（load_iris）
实现完整的 CLS 决策树（支持基尼系数和熵两种标准）
添加后剪枝功能
达到测试集准确率≥90%

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

# 数据准备
iris = load_iris()
X_train, X_test, y_train, y_test = train_test_split(iris.data, iris.target, test_size=0.3, random_state=42)

# 模型训练
tree = CLSDecisionTree(max_depth=4, criterion='gini')
tree.fit(X_train, y_train)

# 后剪枝实现（伪代码）def post_pruning(tree, X_val, y_val):
    """后剪枝核心逻辑"""
    # 1. 遍历所有非叶子节点
    # 2. 临时将节点转为叶子节点（value= 多数类）# 3. 比较剪枝前后验证集准确率
    # 4. 保留效果更好的结构
    pass

# 性能评估
print(f"Test Accuracy: {np.mean(tree.predict(X_test) == y_test):.2f}")

通过这个完整的实现流程，你应该已经掌握了 CLS 决策树的核心原理和实现技巧。建议进一步尝试：
1. 添加对缺失值的鲁棒处理
2. 实现可视化树结构的功能
3. 对比与 sklearn 的 DecisionTreeClassifier 性能差异

正文完