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

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

节与同类的 DiffPRF_linear 算法 [7] 、TpDPRF 算法 [8] 以及 DiffPRF 算法 [23] 展开实验比较和分析.

5.1 时间复杂度
表 2 给出了本文方案 eDPRF 与 DiffPRF_linear 算法 [7] 、TpDPRF 算法 [8] 以及 DiffPRF 算法 [23] 的时间复杂度
分析, 以及性能对比. 其中, n 和 m 分别是特征个数与标签种类数, 可以看出, 分支节点构造阶段, 所有方案的时间
复杂度与特征个数 n 成线性相关, 叶子节点构造阶段的时间复杂度与标签种类数 m 呈线性相关, 在此过程中与整
个数据集的大小无关, 因此可以适用于大规模数据集. 针对隐私安全和准确度分析, 安全性分析可以看出本文方案
达到 ε -差分隐私, 与其他方案对比可以达到同等级别, 但是从准确度评估结果可以明显看出本文方案更优.

表 2 时间复杂度和性能对比

方案 分支节点构造阶段 叶子节点构造阶段 隐私安全 准确度 (%)
DiffPRF_linear算法 [7] O(n) 1+ O(m) ε-差分隐私 82.95
TpDPRF算法 [8] O(n) 1+ O(m) ε-差分隐私 81.91
DiffPRF算法 [23] O(n) 1+ O(m) ε-差分隐私 78.89
eDPRF (本文方案) O(3n) O(3m) ε-差分隐私 85.98

5.2 实验平台介绍
本文实验环境是 64 位 Windows 10 操作系统的台式机, 处理器型号是英特尔酷睿 i9-9900K, 内存大小为
32 GB. 本文所有的算法代码基于 Python 语言编写, 使用的代码编辑器是 VSCode, 运行环境是 Python 3.8. 实验数
据集来源于 Kaggle 的 diabetes [26] 以及 UCI 的 wall-following robot 数据集 [27] . 由于原始的 diabetes 数据集不平衡比
例达到 92:8, 为了避免数据不平衡给实验带来的误导性判断, 本文对原始的 diabetes 数据集, 使用 imblearn.
under_sampling 库的 RandomUnderSampler() 函数执行欠采样操作, 生成一个平衡的数据集, 欠采样的参数为
sampling_strategy={0:7000, 1:7000}和 random_state=42. 表 3 给出实验中所使用的数据集信息.

表 3 实验数据集的统计信息

数据集 数据集大小 离散型特征个数 连续型特征个数 标签类别个数
diabetes 14 000 4 4 2
wall-following robot 5 456 0 25 2

5.3 实验指标介绍
本文采用预测准确度对训练集上生成的模型进行性能评估. 通过计算模型在测试集上正确预测的样本数量与
总测试样本数量之比获得预测准确度. 在训练集和测试集的划分中, 本文设置的比例为 8:2. 具体计算过程如下.
N 个样本, 其中第 个样本为 , 对应的真实标签为 , 将第 个样本输入到随机森林模型
i
i
假设测试集中包含 x i y i
后, 输出对应的预测标签为 model(x i ), 则 N 个测试样本的预测准确度可以通过公式 (19) 计算得出.

∑ N
model(x i ) == y i ? 1 : 0
Acc = i=1 (19)
N

5.4 实验结果分析
为说明所提算法的有效性, 接下来将本文方案 eDPRF 与其他方案 [7,8,23] 进行实验比较和分析.

5.4.1 决策树创建方法比较
由于 DiffPRF 算法 [7] 、TpDPRF 算法 [8] 以及 DiffPRF_linear 算法 [23] 在决策树的创建方式上均属于传统方
法 [15] . 为了便于分析, 本文将传统建树算法记为 tradition, 然后与该算法进行 3 组实验对比. 第 1 组实验中, 在
tradition 上对本文提出的分支节点创建方法进行有效性验证. 第 2 组实验中, 在 tradition 上对本文提出的叶子节点
创建方法进行有效性验证. 第 3 组实验中, 与 tradition 进行全面比较, 其中实验的隐私预算以及深度默认为 1 和 6.
为验证分支节点创建方法有效性, 本文将 tradition 算法的分支节点创建方法替换成所提出的方法, 并将替换