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

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

⑤ Result = Result ∪ predict_value;
⑥ end for
⑦ end for
⑧ return max{Result}

4 隐私性分析

本节对 pfDPDT 算法、eDPRF 算法以及基于随机森林实现预测过程 (算法 6) 的隐私性进行分析.
定理 3. 假设分配给 pfDPDT 算法的隐私预算为 ε tree , 则 pfDPDT 算法满足 ε tree -差分隐私.
treeDepth. 使用 pfDPDT i 层的任意节点时将分为两类: 如果该节
证明: 假设决策树的最大深度为 算法构建第
点是分支节点, pfDPDT 算法消耗的隐私预算如公式 (17) 所示. 由于 pfDPDT 算法对于分支节点的创建过程严格
遵从重排翻转机制 [12] , 因此该分支节点的构建过程满足 ε i,spl -差分隐私.

1
ε tree
ε i,spl = × (17)
s t treeDepth−i+1
如果该节点是叶子节点, pfDPDT 算法消耗的隐私预算如公式 (18) 所示. 由于算法 5 对于叶子节点的创建过
程严格遵从重排翻转机制, 因此该叶子节点的构建过程满足 ε i,leaf -差分隐私.

i−1
∑
ε i,lea f = ε tree − ε j,spl (18)
j=1
ε split 是
根据并行组合定理, 构建决策树所消耗的隐私预算 ε spend 取决于最长支路消耗的总隐私预算 ε max . 假设
ε leaf 是最长支路上叶子节点的预算消耗, 则总隐私预算 ε max 的计算过程如下:
最长支路上所有分支节点的预算消耗,
treeDepth−1
∑
ε max = ε split +ε leaf = ε i,spl +ε treeDepth,lea f = ε tree
i=1
ε spend = ε max = ε tree . 由于在使用 pfDPDT 算法构建决策树的过程中, 所消耗的隐私预算没有超过
所以可以得出
ε tree , 因此 pfDPDT 算法满足 ε tree -差分隐私.
综上所述, 定理 3 证明完毕.
定理 4. 假设分配给 eDPRF 算法的隐私预算为 ε, 则 eDPRF 算法满足 ε -差分隐私.
证明: 假设随机森林规模为 T, 随机森林的最大深度为 treeDepth. 在构建每棵决策树时, eDPRF 算法为
pfDPDT 算法分配的隐私预算均为 ε. 根据定理 3 可得, 对于每棵决策树, pfDPDT 算法满足 ε -差分隐私.
由于 eDPRF 算法中每棵决策树被分配的训练数据互不相交, 即存在 D i ∩ D j = ∅,i , j且i, j ∈ [1,T].
根据差分隐私的并行组合定理可得, eDPRF 算法构建随机森林所消耗的隐私预算为 ε, 该过程消耗的隐私预
ε, 因此 eDPRF
算没有超过 算法满足 ε -差分隐私.
综上所述, 定理 4 证明完毕.
定理 5. 假设 eDPRF 算法满足 ε -差分隐私, 则使用 eDPRF 算法构建而成的随机森林模型满足 ε -差分隐私, 并
且基于随机森林实现预测过程 (算法 6) 同样满足 ε -差分隐私.
证明: 由于 eDPRF 算法满足 ε -差分隐私, 根据差分隐私的后处理性质, 使用 eDPRF 算法构建而成的随机森林
模型满足 ε -差分隐私.
由于随机森林模型满足 ε -差分隐私, 根据差分隐私的后处理性质, 基于随机森林实现预测过程 (算法 6) 满足
ε -差分隐私.
综上所述, 定理 5 证明完毕.

5 实验结果与分析

本节首先给出算法的时间复杂度分析, 在第 2、3 节对所使用的实验环境以及实验指标进行介绍, 最后在第 4