CLS决策树原理剖析与工程实践：从算法原理到生产环境优化

1次阅读

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

在分类任务中，传统决策树算法如 ID3 和 C4.5 存在一些明显的局限性。例如，信息增益（Information Gain）倾向于选择取值较多的特征，这可能导致模型过拟合。此外，基尼系数（Gini Index）在处理类别不平衡数据时表现不佳。

CLS（Conditional Likelihood Score）决策树通过引入条件似然评分来解决这些问题。具体来说，CLS 在特征选择时考虑了类别的条件概率分布，从而避免了信息增益的偏向性问题。

ID3 使用信息增益作为特征选择标准：

$$
IG(S, A) = H(S) – \sum_{v \in Values(A)} \frac{|S_v|}{|S|} H(S_v)
$$

C4.5 引入信息增益比（Gain Ratio）来克服信息增益的偏向性：

$$
GR(S, A) = \frac{IG(S, A)}{SplitInfo(S, A)}
$$

CLS 则直接最大化条件似然评分：

$$
CLS(S, A) = \sum_{v \in Values(A)} P(v) \cdot \log P(y|v)
$$

算法	时间复杂度	适用场景
ID3	O(n \cdot m \cdot d)	小规模数据集，特征取值较少
C4.5	O(n \cdot m \cdot d \cdot \log n)	中等规模数据集，需处理连续特征
CLS	O(n \cdot m \cdot d)	类别不平衡数据，高维特征

计算每个特征取值的条件概率：

$$
P(y|v) = \frac{count(y, v)}{count(v)}
$$

计算 CLS 评分：

$$
CLS = \sum_{v} P(v) \cdot \log P(y|v)
$$

import numpy as np
from collections import defaultdict

class CLSDecisionTree:
    def __init__(self, max_depth=5):
        self.max_depth = max_depth
        self.tree = {}

    def fit(self, X, y):
        self.tree = self._build_tree(X, y, depth=0)

    def _build_tree(self, X, y, depth):
        if depth >= self.max_depth or len(np.unique(y)) == 1:
            return np.argmax(np.bincount(y))

        best_feature = self._select_best_feature(X, y)
        tree = {best_feature: {}}

        for value in np.unique(X[:, best_feature]):
            mask = X[:, best_feature] == value
            X_subset, y_subset = X[mask], y[mask]
            tree[best_feature][value] = self._build_tree(X_subset, y_subset, depth + 1)

        return tree

    def _select_best_feature(self, X, y):
        best_score = -np.inf
        best_feature = -1

        for feature in range(X.shape[1]):
            score = self._calculate_cls(X[:, feature], y)
            if score > best_score:
                best_score = score
                best_feature = feature

        return best_feature

    def _calculate_cls(self, feature_values, y):
        cls_score = 0.0
        for value in np.unique(feature_values):
            mask = feature_values == value
            y_subset = y[mask]
            p_y_given_v = np.mean(y_subset)
            p_v = np.mean(mask)
            cls_score += p_v * np.log(p_y_given_v + 1e-10)

        return cls_score

对于稀疏特征，可以使用稀疏矩阵存储（如 scipy.sparse）来减少内存占用。

在多线程环境下，建议使用线程安全的模型更新策略，例如：