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

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

∗
⑤ 将 QS 集合中最大的效用分数记为 u ;
spl
⑥ 对特征集合 F 执行随机排列操作, 获得新的特征集合 B;
⑦ for b in B do /*遍历集合 B 中每一个特征*/
⑧ 设置 ∆u spl = 2
⑨ 根据公式 (12) 计算特征 b 的概率 p spl_b :
⑩ if Bernoulli(p spl_b ) then /*根据 p spl_b 生成一个服从伯努利分布的随机数 */
r
r
⑪ return b /*当随机数 取值为 1 时, 将 b 作为分支节点的分裂特征*/
⑫ end if
⑬ end for

算法 3. 标签的输出过程.

输入: 训练数据 D, 标签集合 L, 隐私预算 ε lea f ;
输出: 节点的标签.
函数: BuildLea f(D,L,ε lea f ).
① QS = { } /*设置一个空集合*/;
② for i in L do /*遍历集合 L 中每一种标签*/
③ 根据公式 (15) 计算标签 i 的效用分数 u i
lea f
④ QS = u i
lea f
⑤ end for

⑥ 将 QS 集合中最大的效用分数记为 u ∗ ;
leaf
L 执行随机排列操作, 获得新的标签集合 ;
U
⑦ 对标签集合
U
⑧ for u in do /*遍历集合 U 中每一种标签*/
⑨ 根据公式 (16) 计算标签 u 的概率 p leaf_u
⑩ if Bernoulli(p leaf_u ) then /*根据 p leaf_u 生成一个服从伯努利分布的随机数 */
r
⑪ return u /*当随机数 取值为 1 时, 将 u 作为叶子节点的标签*/
r
⑫ end if
⑬ end for

3.2.1 创建分支节点
本文将基尼指数作为分支节点的特征选择依据, 使用基尼指数衡量节点纯度, 进而辅助分支节点确定最佳的
划分方式, 提高子节点纯度, 从而获得表现效果好的决策树模型. 然而, 在确定分支节点的分裂特征时, 涉及对训练
数据的查询操作, 存在个人隐私的泄露风险. 尽管传统算法基于指数机制 [15] 防止隐私泄露, 但是指数机制在分裂
点的选择上会引入一些随机扰动, 导致构建出来的树模型精准度低. 相比之下, 本文采用的重排翻转机制, 具有比
指数机制具有更小的预期误差, 从而为分支节点提供更准确的分裂点信息.
在重排翻转过程中, 首先为查询特征的操作设置一个恰当的效用函数, 该效用函数被用于后续的分数概率计
算过程中. 基于基尼指数以及重排翻转机制的实施要求, 该效用函数的定义如下.
假设当前访问的训练集为 D, 则对特征集 F 执行查询的效用函数 u spl (D,F a ) 定义如公式 (11) 所示.

   2 
K ∑ n F a ,i
   
C ∑
 
i     L,L k  
u spl (D,F a ) = − v 1−    (11)
 

F a   i  
 
i=1 k=1 v
F a

其中, F a 表示 F 中任一特征, i F a 取值为 v i 的样本数量, C 表示 F a 的所有取值情况数, K 表示 L 的所有标
v 表示
F a F a