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

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

本文将隐私预算分配环节以及决策树的创建环节结合后, 获得差分隐私随机森林模型. 算法框架见图 1 所示. 表 1
所示的是本算法使用的主要符号及其含义.

隐私预算分配环节
随机森林生成环节

ID 数据特征 数据类别
0 {1,2,3,4,5} A
1 {2,2,3,4,5} B 随机森林
2 {6,2,1,4,5} A
3 {4,2,1,4,5} C
4 {2,2,1,4,5} A
5 {6,2,1,4,1} B
…
6 {3,2,1,4,5} B
采样 … …
训练集

pfDPDT 算法

子训练集 决策树创建环节 一组隐私化的决策树
图 1 eDPRF 算法框架示意图

表 1 主要符号及其含义

符号 说明 符号 说明
ε 隐私预算 F D的特征集
treeDepth 决策树的最大深度 (简称深度) L k 第 k 种标签
∆ 全局敏感度 N k D中标签为 L k 的样本数量
T 随机森林的规模 F a 第 a 种特征
D 训练集 v w F a F a 的第 w 种取值情况
L D的标签集 n F a ,w D中 F a 的取值为 v w 且标签为 L k 的样本数量
L,L k
F a

3.1 隐私预算分配环节
如图 2 所示, 隐私预算分配环节分为两个部分: 1) 决策树之间的隐私预算分配, 2) 决策树内部的隐私预算分
配, 具体过程描述如下.
1) 决策树之间的隐私预算分配. 首先, 定义如下 Tree 1 ,Tree 2 ,...,Tree n 表示随机森林的不同决策树, S 1 ,S 2 ,...,
S n 表示每棵决策树的构建算法, ε 1 ,ε 2 ,...,ε n 表示分配给每棵决策树的隐私预算. 本文采用不放回抽样方式将数据
D 1 ,D 2 ,...,D n , 其中每个训练子集被单独分配给每棵决策树, 确保任意两棵决策树的训练集
集划分为 n 个训练子集
无交集.
本文进一步引入差分隐私的并行组合定理将随机森林中每棵决策树构建算法的隐私预算放大至整个随机森
D. 在获得每棵树
林算法的预算水平. 假设训练算法被分配的隐私预算为 ε, 随机森林的规模为 n, 完整的训练集为
(
的训练集 D i i ∈ [1,n]) 时, 采用不放回抽样的方式令 D = D 1 ∪...∪ D i ∪ D n , 则第 i 棵树的构建算法 S i 获得的查询预
算 ε i = ε.
2) 决策树内部的隐私预算分配. S i,1 ,S i,2 ,... 表示第 棵决策树中每层节点的构建算法, ε i,1 ,ε i,2 ,... 表示分配给每
i
层节点的隐私预算. 在为决策树内部节点分配隐私预算时, 初始阶段中同一层节点将会被分配相同的隐私预算. 随
着节点层级增加, 预算呈现递增效果 [8] , 有助于缓解差分隐私扰动少数样本节点导致性能被严重破坏的问题. 同时