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

2932 软件学报 2025 年第 36 卷第 7 期

其中, Ω 为指数机制的归一化因子, ∆u 是函数 u(D,r) 的全局敏感度.
(3) 重排翻转机制 [12] : 假设数据集为 D, 由一组选项构成的集合为 , Q 的效用函数为 u : D× Q → Q. 对
Q D 与
Q 的任意选项 u 都会输出选项 q 的效用分数. 若算法 F 以算法 1 所示的形式获得集合 Q 中的选项
于集合 q, 函数
q, 则算法 F 满足 ε -差分隐私.
算法 1. 重排翻转算法.

输入: 数据集 D, 隐私预算 ε, 效用函数 u, 选项集合 Q;
输出: 选项.
函数: PermuteAndFlip(D,ε,u,Q).
① s ∗ = max q∈Q u(D,q);
② for q in RandomPermutation(Q) do
ε
( )
③ p q ← exp (u(D,q)− s ∗ ) // ∆u 是 u 的全局敏感度;
2∆u
④ if Bernoulli(p q ) then
⑤ return q;
⑥ end if
⑦ end for
定理 1 (串行组合定理) [13] . 给定一个数据集 D, 如果 n 个随机函数 S i 对于数据集 D 的访问都满足 ε i -差分隐私,
∑
其中 1 ⩽ i ⩽ n, 则 n 个函数 S i 构成的组合函数对于数据集 D 的访问满足 ε i -差分隐私.
定理 2 (并行组合定理) [13] . 假如 n 个两两互不相交的数据集 D i 共同构成数据集 D. 如果存在随机函数 S i 对于
D 的访问满足
数据集 D i 的访问满足 ε i -差分隐私, 其中 1 ⩽ i ⩽ n, 则 n 个函数 S i 构成的组合函数对于数据集
max(ε i ) -差分隐私.
性质 1 (后处理性) [13] . 假设作用在数据集 D 上的随机机制 G : D → M 满足 (ε,δ) -差分隐私, 则对于随机机制
′ ′
f : M → M , 有 A(◦) = f(G(◦)) : D → M 满足 (ε,δ) -差分隐私.

2.2 随机森林
随机森林采用 Bagging 集成策略以及自助采样方法 (Bootstrap) 对多棵决策树进行组合. 在差分隐私化的随机
森林 [7,8] 中, 基尼指数是最常用的划分标准, 对应的数学定义如下所示.
定义 D 的基尼指数定义如公式 (7) 所示.
5 (数据集的基尼指数). 假设数据集 D 存在 c 个类别特征值, 则数据集
∑ c ∑ ∑ c
Gini(D) = p i p i = 1− p 2 i (7)
′
′
i=1 i ,i i=1
其中 p i 代表每个类别特征值的概率. 基尼指数越小, 表明数据集的纯度越高.
定义 6 (特征划分子集的基尼指数). 对于特征 F i , 当 F i 有 v 种取值时, 经过 F i 划分后的基尼指数定义如公式 (8)
所示.

∑
v |D k |
Gini − index(D) = Gini(D k ) (8)
k=1 |D|

3 高效的差分隐私随机森林训练算法 eDPRF
本文提出一种高效的差分隐私随机森林训练算法 eDPRF, 其中包括: 隐私预算分配环节、决策树创建环节以
及随机森林生成环节. 在设计过程中, 主要考虑以下原则: 1) 需要对训练数据隐私提供保护; 2) 尽可能提高随机森
林模型的可用性. 因此, 在隐私预算分配环节中, 本文引入并行组合定理进行预算对齐操作, 提高每个树节点获得
的查询预算. 在决策树的创建环节中, 本文提出 pfDPDT (differential privacy decision tree with permute and flip) 算
法, 通过重排翻转机制优化节点查询过程, 增强每个树节点获取数据信息的能力. 在随机森林模型的生成环节中,