Page 16 - 《软件学报》2025年第7期

王树兰 等: eDPRF: 高效的差分隐私随机森林训练算法 2937

签种数.
在分支节点的特征选择过程中, 针对待选的特征集合, 根据公式 (11) 为集合中每个特征计算效用分数. 同时,
为每个特征计算其分数概率, 计算过程如公式 定义
(12) 所示. 对于特征集合中的任一特征
F a , 其分数概率
p spl_F a
如下:

(
 ) 
ε spl u −u ∗ 
F a
 spl spl 
   
p spl_F a = exp    (12)
 
2∆u spl
其中, ε spl 表示分支节点获得的隐私预算, u F a 表示 F a 的效用分数, 通过公式 (11) 计算获得. u ∗ 表示待选特征集
spl spl
合中最大的效用分数. ∆u spl 为公式 (11) 的全局敏感度. 为简化计算, 假设对于任意数据集 D 2 , 数据集 D 1 是通过
D 2 上增加 1 i ′ ∆u spl 的计算过程如公
′
在 条样本后形成的, 新增样本的特征 F a 取值为 v , 标签为 L k . 全局敏感度
F a
式 (13).

∆u spl = maxu spl (D 1 ,F a )−u spl (D 2 ,F a )
D 1 ,D 2
    2      2 
C K ∑ n F a ,i C K ∑ n F a ,i
 
 
 ∑    L,L k    ∑    L,L k  


 
  i        i     
 
= − v 1−  i   − − v 1−    (13)
 i  

 


  F a     F a   

v v
i=1 k=1 F a i=1 k=1 F a
D 1 D 2
其中, ∆u spl 等价于公式 (14).

)
( ) 2 K ∑ ( ) K ∑(
F a ,i ′ 2 F a ,i ′ 2
n F a ,i ′ +1 + n n
L,L k ′ L,L k
L,L k
k=1,k,k ′
k=1
∆u spl = 1− +
i ′ i ′
(v + 1) v
F a F a

 

K ∑( K ∑ (
)
) 
F a ,i ′ 2 ( ) 2 F a ,i ′ 2

i ′ 
i ′
(v + 1) n − v  n F a ,i ′ +1 + n 



L,L k 
F a L,L k F a   L,L k ′ 
k=1 k=1,k,k ′

= 1+
i ′ i ′
(v + 1)v
F a F a

K ∑( )
F a ,i ′ 2 F a ,i ′ i ′
i ′
n −2v n − v
L,L k F a L,L k ′ F a

k=1
= 1+

i ′ i ′
v (v + 1)
F a F a

K ∑( )
F a ,i ′ 2
n
L,L k F a ,i ′
2n
k=1 L,L k ′ +1
(14)
= 1+ −
i ′ i ′ i ′
v (v + 1)
F a F a v + 1
F a

K ∑( )
F a ,i ′
n ( ) 2
L,L k i ′ 2n F a ,i ′ i ′

v +1 2v +1
k=1 F a L,L k ′ F a ∆u spl 的取值范围为
,
根据 ⩽ 1 0 ⩽ ⩽ ⩽ 2. 可以确定
0 ⩽ ⩽ i ′ i ′
i ′ i ′ i ′ i ′ v + 1 v + 1
F a
F a
F a
v (v + 1) v (v + 1) F a F a
F a

0–2 之间, 由于当 ∆u spl 取值过小时, 差分隐私的保护效果将受到影响, 因此本文将 ∆u spl 设定为 2.
此外, 在上述计算过程中, D 1 是通过在 D 2 上增加 1 条样本后形成的数据集, 同理可得, 如果假设 D 2 是通过在
D 1 增加 1 条样本后形成的数据集, ∆u spl 的范围仍然为 0–2 之间.
在创建分支节点过程中, 本文基于算法 2 访问训练数据并输出分裂特征, 并将输出的特征作为分支节点的分
裂点.