SHAP值的计算与近似方法

SHAP值数学定义：基于Shapley Value φ_i = Σ_{S⊆N\{i}} |S|!(|N|-|S|-1)! / |N|! · [f(S∪{i}) - f(S)]

• 计算特征i在所有特征子集中的平均边际贡献
• 满足：局部准确、缺失性、一致性、线性和

计算复杂度：

• 精确计算需遍历所有2^|N|个子集，O(2^n)——NP-hard
• 实际参数量(特征维度)常≥10，必须近似

近似方法：

1. TreeSHAP (Lundberg et al., 2018)：

• 针对树模型(XGBoost/LightGBM/RF)的精确近似
• 利用树的层次结构遍历可能的分支路径
• 单棵树O(TL·2^D) → 优化后O(TLD²)，T为节点数，L为叶子数
• 实际运行快至O(n·log(n))
• 同时计算所有特征，无需采样

2. KernelSHAP (模型无关)：

• LIME + Shapley权重的统一
• 用加权线性回归：min Σ[π_x(z)·(g(z) - f(z))²]
• 采样特征子集z，权重π_x按Shapley核分配
• 采样数≈2^d + 2048（d>10时采样）

3. DeepSHAP (深度学习)：

• 基于DeepLIFT传播，近似SHAP值
• 快但精度低于精确SHAP

实践中：树模型用TreeSHAP（精确且快速），其他用KernelSHAP。