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

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

的计数信息同样泄露个人隐私, 并没有真正意义上实现差分隐私保护. 此外, 现有的大多数随机森林对不同层节点
的预算分配策略采用均分的方式, 文献 [7,8,23] 指出, 这种方式会导致深层结点的信噪比不均衡. 为确保随机森林
模型效用性, 上述文献建议在按层分配的基础上为深层节点分配更多的隐私预算. 然而却忽略了模型结构对隐私
预算分配的影响, 导致部分预算被闲置. 与此同时, 上述方案在决策树间采用的等分预算方式在森林规模较大时容
易引入过多随机性影响模型性能.
综上所述, 上述研究并不能很好地平衡隐私保护性与模型可用性之间的关系. 为此, 本文提出一种高效且满足
差分隐私的随机森林训练算法, 设计新的决策树创建方法以及隐私预算分配策略, 在提升节点的查询预算时进一
步改善其在扰动下对数据信息的学习能力, 并通过隐私性分析证明本算法可以提供 ε-差分隐私保护, 实现了隐私
保护与模型可用性之间的有效平衡.

2 基础知识

2.1 差分隐私
定义 1 (相邻数据集) [13] . 如果两个数据集 D 1 和 D 2 之间只相差一条数据, 则这两个数据集被称为相邻数据集.
定义 2 ( (ε,δ) -差分隐私) [13] . 假设 D 1 和 D 2 是任意相邻数据集, S 是数据集上的一个随机函数. 如果函数 S 满
足公式 (ε,δ) -差分隐私.
(1), 则称函数 S 满足
ε
Pr[S (D 1 ) = O] ⩽ e ×Pr[S (D 2 ) = O]+δ (1)
其中, O 是 S 在数据集上的任意可能的输出结果, ε 是用来量化隐私损失的隐私预算, 隐私预算 ε 越小则对隐私的
δ
保护程度越高. 隐私参数 δ 是一个松弛控制概率, 即存在大小为 的概率, 数据会在没有任何保护措施的情况下被
δ = 0 时, 被称为纯差分隐私, 纯差分隐私
释放. 通常 δ 会设置成一个很小的数, 当 δ > 0 时被称为松弛差分隐私, 当
的保护强度要高于松弛差分隐私的保护强度. 如果函数 S 满足公式 (2), 则称函数 S 满足 ε -差分隐私.

ε
Pr[S (D 1 ) = O] ⩽ e ×Pr[S (D 2 ) = O] (2)
定义 3 (全局敏感度) [13] f : D → R , f 的全局敏感度如公式 (3) 所示.
d
. 给定函数
∆ f = max∥ f(D 1 )− f(D 2 )∥ (3)
1
D 1 ,D 2
其中, D 1 和 D 2 为任意的相邻数据集.
定义 4 (隐私保护机制). 拉普拉斯机制、指数机制以及重排翻转机制是实现差分隐私的 3 种机制, 下面给出
相关概念.
(1) 拉普拉斯机制 [24] : 拉普拉斯机制通过向原始数据的查询结果添加一些噪声以保护数据隐私.
f
对于任意数据集 D 以及查询算法 , 若算法 S 的输出结果满足公式 (4), 则认为算法 S 满足 ε -差分隐私.

( )
∆ f
S (D) = f(D)+ Lap (4)
ε
其中, Lap(∆f/ε) 表示服从拉普拉斯分布的随机噪声, ∆f 是算法 f 的全局敏感度, ε 是隐私预算.
拉普拉斯噪声的概率密度函数定义见公式 (5).

 ( )
 1 x

( )  exp − , x ⩾ 0

1 |x|  2b b


Lap(b) = exp − =  (5)
2b b  1 ( )
x



 exp , x < 0

2b b
(2) 指数机制 [25] : 给定数据集 D, 对于范围 R 的任意对象 r, 效用函数 u(D,r) : D×R → R 都会输出对象 的效用
r
分数. 若随机算法 M 以公式 (6) 的概率从 R 中选择并输出 r, 则算法 M 满足 ε -差分隐私.

( )
εu(D,r)
exp
2∆u
Pr[M = r] = (6)
Ω