一种面向边缘计算的高效差分隐私 分布式数据挖掘方案

摘要

大量数据挖掘应用受益于边缘计算提供的低延迟。然而，边缘计算受限于有限的计算资源，这限制了计算开销大的数据挖掘方法的应用。在边云环境中，参与者通常会协作训练机器学习模型，以获得更准确的预测结果。但是，由于隐私顾虑，数据所有者可能不愿意共享自己的数据。为了应对这些相互冲突的目标，我们专注于具有差分隐私的基于树的分布式数据挖掘方案，该方案在计算上较为友好。我们方法的基本思想基于一种分布式集成策略。每个参与者基于自身的数据构建一个优雅的决策模型，该模型在计算开销与数据分布的准确性之间实现了良好权衡，并在注入精心设计的噪声后与其他参与者共享。随后，其他参与者通过自适应集成策略获取来自这些决策模型的有用知识。理论分析和实验均表明，我们的方案为分布式数据提供了一种高效的挖掘方式，在实现良好预测准确率的同时提供了严格的隐私保障。

关键词 ：分布式数据挖掘，差分隐私，AdaBoost，边缘计算

引言

近年来，随着边缘计算的出现，大量智能设备得到普及，随之产生了海量数据[1]。数据挖掘作为一种革命性技术，能够自动且智能地提取隐藏信息和有价值的知识。因此，已在边缘计算中部署了广泛的数据挖掘应用，以造福我们的日常生活，例如智慧医疗[2], 智能家居[3],和智能交通[4, 5],等。

数据挖掘的广泛应用得益于边缘计算提供的低延迟。然而，边缘计算受限于有限的计算能力资源，这限制了计算成本较高的数据挖掘方法（如人工神经网络）的应用。在边缘计算环境中，参与者通常会联合多个数据所有者共同训练出一个精确的机器学习模型。此外，源数据的收集和预处理在边缘设备端进行，其中涉及一些个人隐私数据。例如，在智慧医疗场景中，大量嵌入式和可穿戴设备用于监测患者的身体状况，这些监测数据不仅可用于医学诊断或治疗，也可能被保险公司等恶意机构所利用 [6]。因此，迫切需要解决隐私问题，以确保在资源受限的边缘计算环境下实现跨多个数据集的数据挖掘。

现有的关于隐私保护的分布式数据挖掘的研究主要集中在密码学 [7–9]。朴素解法是仅共享加密数据，所有操作都直接在密文上进行。例如，全同态加密被用于保护联邦学习中的私有信息[10]。然而，这些密码学解决方案通常会带来巨大的额外计算开销，阻碍了它们在边云环境中的应用。差分隐私是一种新的隐私定义，其实现基于扰动技术[11]。迄今为止，由于差分隐私的高效实现，已经有了许多针对聚类[12],决策树[13]和神经网络等挖掘任务设计的差分隐私算法的研究[14], 。

近年来，我们见证了树状模型在挖掘任务中的广泛应用。当前关于隐私保护决策树的研究主要集中在如何确保单一数据拥有者在发布数据时不泄露任何隐私信息，却忽视了数据由多个拥有者持有的分布式场景[15]。最近的一项工作[16]提出了一种适用于分布式场景的基于树的数据挖掘方案。然而，由于其训练过程缺乏灵活性，无法直接应用于边缘计算。

为了解决资源受限的边云计算中的隐私泄露问题，我们提出了一种高效的、在分布式数据集上实现的隐私保护的基于树的数据挖掘方法。具体而言，基于 AdaBoost框架，我们设计了一种差分隐私方案，在构建优良模型的同时实现了准确性与隐私性之间的权衡。此外，我们在AdaBoost框架下构建基础学习器时，提出一种自适应集成策略，以更准确地学习数据分布。我们的实验证明，该方案在模型构建和隐私保护方面均有效。

总之，我们做出了以下主要贡献：
（1）我们设计了一种面向边云计算的分布式数据挖掘方案，具有隐私保护功能，不仅能够在隐私保护与数据利用之间实现良好权衡所构建模型的准确性与隐私保护，同时也考虑了计算资源的限制。
（2）我们提出了一种自适应集成策略用于构建过程，使得参与者能够在不访问这些私有数据的情况下，通过结合具有相似数据分布的模型来提升基础学习器的预测准确率。
（3）我们对所提方案的隐私性和计算复杂度进行了理论分析。随后进行了一系列仿真实验，在两个真实世界数据集上进行了实验，证明了我们方案的可行性。

本文的其余部分组织如下。第2节介绍了相关工作。第3节介绍了相关预备知识。第4节概述了所提方案及设计目标。第5节详细描述了我们的隐私保护分布式数据挖掘方案。第6节通过理论分析证明了方案的可行性。第7节在两个真实世界数据集上评估了性能。最后，第8节对全文进行总结。

相关工作

最近，隐私保护数据挖掘引起了广泛关注，尤其是在边缘计算中，数据挖掘通常涉及多个参与方。为了保护数据隐私，已经提出了多种技术，例如k‐匿名性、随机化和加密工具[17]。差分隐私是首个具有严格且可证明数学定义的隐私保护模型[18]。它已被广泛用于设计数据挖掘中的隐私保护方案，如决策树[19],主成分分析[20],和人工神经网络[21]。

作为一种常见的数据分类模型，决策树已应用于不同的应用场景中。由于其透明性和可解释性，得到了广泛使用。为了解决隐私泄露问题，已提出多种满足差分隐私的决策树构建方案。Blum等人首次提出了 SuLQ框架以实现差分隐私，并结合ID3[22]提出了基于SuLQ的ID3算法。但该方法因保护私有信息所需引入过多噪声，牺牲了模型准确性。文献[13]提出了一种基于指数机制的DiffP‐ID3算法，有效减少了隐私预算的浪费。此外，Friedman和Schuster进一步提出了DiffP‐C4.5算法，以克服DiffP‐ID3只能处理离散属性的局限性[13]。Rana等人[23]和Fletcher[24]提出了构建差分隐私随机森林的方法，通过将多个决策树集成到一个集成模型中，降低了噪声对模型准确性的负面影响。

为了解决分布式环境中的隐私保护问题，Lindell 等人提出使用混淆电路来选择分割属性 [25]。Mohammed 等人提出了一种在非交互式设置下的差分隐私算法，用于实现双方垂直划分的数据挖掘 [26]。该算法被应用于以下场景：医疗数据挖掘 [27]。为了在无信任第三方的情况下实现隐私保护的协同数据挖掘，戈里奇卡等人提出了一种m‐隐私剪枝策略，该策略假设参与者可以利用自己的数据推断其他数据所有者的数据记录贡献[28]。该工作[29]提出在分布式数据上构建ID3决策树，并通过秘密共享方案保护参与者的私有信息。然而，这些方案可能导致较高的通信和计算成本。甘布斯等人提出了Mult‐Boost算法，该算法基于Boosting和差分隐私保护实现隐私保护的协同数据挖掘[30],然而，它需要一个安全第三方来完成信息交互和模型集成，从而带来额外的通信开销。

现有研究主要集中在数据所有者如何使用差分隐私安全地发布基于树的数据 [30]。仅有工作 [16] 提出了一种分布式数据挖掘方案。在该方案中，参与者共享差分私有模型及相应的参数以协同构建模型。然而，该协同训练过程必须遵循特定顺序，因此不适用于边缘计算。

预备知识

差分隐私

定义1. 差分隐私

若一个算法F对于任意数据集D及其相邻数据集D′（对称差为 ∣DΔD′ ∣= 1），满足：
$$
Pr \left( F(D) \in S \right) \leq e^\varepsilon Pr \left( F(D’) \in S \right)
$$
其中，S 表示算法F所有可能输出的子集，ε 是隐私预算。隐私预算越小，算法F提供的隐私保护程度越高。

定义2. 全局敏感度

函数f的全局敏感度如下所示：
$$
\Delta f = \max_{D,D’} | f(D) - f(D’) |_{L1}
$$
通常，对于数值查询函数，可以向查询结果添加满足拉普拉斯分布的随机噪声，以满足 ε‐差分隐私。

定理1. 拉普拉斯机制

对于任意函数 $f : D \rightarrow \mathbb{R}^d$，函数f 在满足以下条件时提供 ε‐差分隐私：
$$
F(D) = f(D) + Lap(\Delta f/\varepsilon)
$$
其中，Lap(Δf/ε) 是从位置参数为 0、尺度参数为 Δf/ε 的拉普拉斯分布中抽取的随机噪声。

然而，当涉及到非数值查询函数时，应使用指数机制。

定理2. 指数机制

对于以数据集D为输入的任意质量函数M，其输出为r ∈ M的取值范围。其敏感度为 Δu。当该函数M以与 exp(εu(D′,r)/2Δu)成正比的概率从M的取值范围内输出r时，可提供 ε‐差分隐私。

定理3. 序列组合

假设A1,A2, ⋯, An是随机算法，且Ai满足 εi‐差分隐私。对于任意数据集D，这n个算法的序列组合
$$
A(D) = { t_1 = A_1(D); \cdots; t_n = A_n(D, t_1, \cdots, t_{n-1}) }
$$
满足 ε‐差分隐私，且 $\varepsilon = \sum_{i=1}^{n}\varepsilon_i$。

定理2. 并行组合

假设随机算法A满足 ε‐差分隐私，且数据集D被划分为 m个互不相交的子集{D1, D2, ⋯,Dm}。则在这些互不相交的子集上对A进行并行组合
$$
A(D) = { t_1 = A(D_1); t_2 = A(D_2); \cdots; t_m = A(D_m) }
$$
满足 ε‐差分隐私。

AdaBoost算法

根据个体学习器之间的关系，集成学习可分为两类。一类是基学习器相互独立，例如随机森林（RF），其中基学习器的性能和训练过程不受其他学习器的影响；另一类是基学习器之间存在强依赖关系，例如 AdaBoost[31]。

设 $D = {(x_1, y_1), (x_2, y_2), \cdots, (x_N, y_N)}$ 表示训练数据集。$y_i \in {-1,+1}$ 是与 $x_i$ 相关联的类别标签。分布 $W = (w_{1,1}, w_{1,2}, \cdots, w_{1,N})$ 表示 D 中每个实例的权重，w 的初始值为 $w_{1,i} = 1/N$。在训练过程中，$W_{t+1}$ 根据每次迭代中基学习器的错误率从 $W_t$ 重新调整。每个基学习器 $H_t(x) : x \rightarrow {1, v_{15}}$ 是通过在具有权重分布 $W_t$ 的训练数据集上运行学习算法获得的。最终分类器是通过对基学习器进行线性组合得到的。
$$
g(x) = \sum_{t=1}^{T} \alpha_t H_t(x)
$$

模型与目标

系统模型

图 1给出了我们系统模型的概览。假设在边云环境中存在 M个参与者，每个参与者可以通过网络交换信息，并且各自拥有一个私有数据集。请注意，数据挖掘者可以是这些参与者之一。在挖掘过程中，每个参与者基于AdaBoost算法构建学习模型，基础学习器由本地模型和共享模型组成。具体而言，在训练完本地模型后，每个参与者会共享该模型及其对应参数，而不是原始数据，以实现隐私保护。此外，提出了Diff PRS算法来保护模型及其对应参数所泄露的隐私信息。当接收到共享模型时，每个参与者根据该共享模型在其各自的私有数据集上的表现，选择合适的模型并以自适应的方式进行集成。

当一个新参与者加入系统时，无需重新训练整个模型，新参与者只需执行所提出的学习算法来训练本地模型并进行自适应模型集成。对于现有参与者而言，他们仅需决定新的共享模型是否值得集成。

模型目标

为了解决边缘计算中分布式数据挖掘的隐私问题，我们提出方案的设计目标可以概括为：
1) 隐私保护：共享模型及其相应参数不会泄露私有信息。换句话说，系统中的参与者无需担心其他参与者中可能存在恶意参与者。
2) 准确性与效率：在考虑边缘计算中计算资源限制的同时，实现所构建模型的准确性与隐私保护之间的良好权衡。

所提方案描述

问题定义

假设有M个参与者，每个参与者都有一个私有数据集 $D = {D_1^{N_1}; D_2^{N_2}; \cdots; D_M^{N_M}}$。其中，第m个参与者的私有数据集为 $D_m^{N_m} = {(X_{m,1}; y_{1,m}); (X_{m,2}; y_{2,m}); \cdots; (X_{m,N_m}; y_{m,N_m})}$，包含Nm个元组，每个元组 $X_{m,n} = (x_{m,n,1}; \cdots; x_{m,n,K_m})$ 具有Km个属性。在所提方案中，考虑二分类问题的每个标签 $y_i \in {-1,+1}$。

所提方案

本文提出的方案旨在解决边云环境中分布式数据挖掘的数据隐私保护问题。考虑到参与方的计算资源可能有限，使用人工神经网络(ANN)等需要高计算资源的学习算法来训练模型较为困难。因此，基于 AdaBoost框架，我们提出了一种针对分布式数据的挖掘方法，以降低对计算资源和数据收集的依赖性。

在AdaBoost框架中，首先通过平均方法初始化权重 $W_1 = (w_{1,1}, w_{1,2}, \cdots, w_{1,N})$，其中 $w_{1,i}$ 等于1/N。其次，基于具有 $W_i$ 权重分布的数据集训练基本学习器 $h(x)$。然后，计算其错误率
$$
e_t = \sum_{i=1}^{N} w_{t,i} I(H_t(X_i) \neq y_i)
$$
以及 $\alpha_t = \log((1 - e_t)/e_t)/2$，其中 $\alpha_t$ 用于衡量弱学习器 $h(\cdot)$ 在最终分类器中的重要性。经过多次迭代后，弱模型被提升为一个强集成模型。

所提方案的基本思想是每个参与者使用所提出的 DiffPRS算法来训练满足差分隐私的本地模型，并与他人共享，然后参与者根据本地模型选择合适的共享模型，并将本地模型作为基础模型集成到集成模型中进行每次迭代。考虑到参与者数据集中包含的私有信息，我们共享模型及其相应的参数。

在每次迭代中，通过在计算叶节点的支持度时添加噪声来实现隐私保护，其中支持度指的是节点中的记录数量。我们所提方案的详细信息在算法1中进行了概述。

构建差分隐私随机决策树桩

在选择合适的模型作为基础学习器时，必须考虑边缘计算有限的计算能力。这意味着基础学习器必须对计算友好。随机决策树桩是类树分类模型的典型代表。

通常，其性能不如传统的决策树，但其构建过程在计算上更高效，因为它不完全依赖于特定的数据库。因此，在AdaBoost框架中，随机决策树桩被用作基础学习器，以提升为“强”分类器。

从以往的研究可知，直接发布决策树模型及其参数存在隐私泄露的风险[32,33]。与传统的决策树构建方法相比，在随机桩构造过程中，每个分裂属性是通过随机选择确定的，并且仅在确定叶节点的分类时执行查询。然而，直接发布随机桩及其相应参数并不满足数据隐私保护的要求。假设基于数据集A的随机桩结构如图2b所示，并且攻击者有能力构建一个相邻数据集B，该数据集与数据集A相比仅有一条记录不同（如图2a所示），则可以通过基于数据集B构建多个随机桩后，比较随机桩中叶节点的支持度或每个叶节点的标签来分析数据集A的私有信息。

在构建随机决策树桩的结构时，可能会出现某些叶节点的支持度为零的情况。通常情况下，在发布随机决策树桩时会省略这类节点。然而，为了防止攻击者通过观察特定的随机决策树桩结构来获取数据集的私有信息，在发布模型时不能省略零支持的节点。因此，在发布随机决策树桩时，必须向叶节点引入适当的噪声以实现隐私保护。在选择分裂属性时，无需引入额外的随机性，因为分裂节点的属性是通过随机选择确定的，这不依赖于数据集查询，同时已具备随机性。构建差分隐私随机决策树桩的详细过程如算法2所示。

注意到所有差分隐私决策树桩具有相同的结构，为简化起见，在多个参与者之间交换信息时，可将模型及其相应参数统一为向量V。通常，向量V包含三个主要元素：根节点、叶节点的分类及其对应的支持度。

选择合适模型

每个参与者在每次迭代中将接收到来自其他方共享的M−1模型。考虑到这一点，随机决策树桩的性能有限，对于每个特定参与者而言，将其自身的本地模型与共享模型集成到一个集成模型中，可以降低每次迭代中基础模型的错误率，并减少训练过程的迭代时间。换句话说，模型集成能够减少为隐私保护所引入的噪声量，从而增强共享模型的可用性。因此，在所提方案中，如何以适当的方式将模型集成为集成模型，使得集成模型的预测准确率高于本地模型，具有重要意义。此外，简单且无差别地集成各种共享模型可能会降低本地模型的预测准确率。为防止这种情况发生，我们需要确定哪些共享模型适合进行集成。

基本思想是选择那些数据分布与第p个参与者相似的共享模型。同时，这可以有效减少基于恶意数据集构建的共享模型所带来的负面影响。由于隐私保护的限制，直接检查其他参与者的私有数据集是不可行的。因此，通过比较所有共享模型在第p个参与者的训练数据集上的错误率与其本地模型的训练误差，我们可以大致判断哪些对应的数据集与第p个参与者相似。需要注意的是，共享模型可能包含针对某些独特属性的决策树桩。因此，有必要根据属性选择一个合适的共享模型子集。对于第p个参与者，第q个参与者的错误率表示为：
$$
\gamma_q^p = \frac{1}{n_p} \sum_{i=1}^{n_p} I\left( \text{sign} \left( \tilde{H}_q(X_p^i) \right) \neq y_p^i \right)
$$
其中，$I(\cdot)$ 是指示函数，$\tilde{H}_q(\cdot)$ 是由随机决策树桩训练得到的子集。

第q个参与者。第p个参与者的错误率为：
$$
\gamma_p = \frac{1}{n_p} \sum_{i=1}^{n_p} I\left( \text{sign} \left( H_p(X_p^i) \right) \neq y_p^i \right)
$$

对于每个参与者，我们计算 $\left| \gamma_p - \gamma_q^p \right|$ 的绝对值。如果 $\left| \gamma_p - \gamma_q^p \right|$ 小于某个阈值 $\rho$，则可以认为第q个参与者的数据分布与第p个参与者的数据分布相同。通过这种方式，每个参与者以最大程度提升预测性能，并间接增强数据分布。

自适应集成方法

在选择了合适的共享模型子集后，我们采用聚合方法以实现更优的性能，其中聚合方法起着至关重要的作用。在分类情况下，多数投票是最常用的聚合方法，用于得出最终分类。也就是说，最终分类由得票最多的标签决定：
$$
L(x) = \arg\max_c \sum_{i=1}^{T} h_i(x)
$$
尽管这种聚合方法确实提高了树桩间的稳定性，但由于每个决策树桩本身的性能较差[34]，因此仍可能导致较低的预测准确率。因此，在确定上述方法所选模型的权重时，我们不仅应利用其他参与者私有数据的统计信息，还应考虑个体情况。

为了实现这些目标，在为每个模型分配权重时，应遵循以下原则：
（1）分配给共享模型的权重应与相应数据集的数量呈正相关。这是因为较大的数据集数量可以降低由于采样不足导致的决策树桩的错误率。
（2）与共享模型相比，应为本地模型分配更多的权重，但该权重应有一个上界。这是因为我们假设参与者可以通过集成其他模型来增强其数据分布，但来自其他参与者的模型在数据分布上可能存在一定差异。设置上界的目的是为了避免由于本地模型权重过大而导致最终集成模型与本地模型完全相同的情况。

根据这些原则，对于p个参与者，设 $\partial_q^{(p)} (p = q)$ 表示分配给本地模型的权重，$\partial_q^{(p)} (p \neq q)$ 表示分配给共享模型的权重。当我们确定相应模型的权重时，首先计算所有参与者所拥有的数据集比例
$$
\eta_p = \frac{n_p}{\sum_{z \in Z} n_z};\quad p \in Z_p
$$
然后权重按如下方式更新：
$$
\partial_q^{(p)} =
\begin{cases}
\eta_q & p \neq q \
\left\lceil \frac{\eta_q}{\eta_{\max}^2} \cdot \left\lceil \frac{\eta_{\max}^2}{\eta_{\min}} \right\rceil \right\rceil & p = q
\end{cases}
$$
其中，$\lceil \cdot \rceil$ 是向上取整函数，$\eta_{\max}$ 是所有参与者中的最大比例，$\eta_{\min}$ 是最小比例。

在更新模型权重时，对于第p个参与者，如果 $p \neq q$，则 $\partial_q^{(p)} = \eta_q$，这意味着分配给其他参与者共享模型的权重与其对应数据集的数量成正比；当 $p = q$ 时，第p个参与者的权重为 $\partial_q^{(p)} = \left( \eta_q / \eta_{\max}^2 \right) \left\lceil \eta_{\max}^2 / \eta_{\min} \right\rceil$。$\eta_p$ 的取值属于 $[\eta_{\min}, \eta_{\max}]$。因此，当 $\eta_q = \eta_{\min}$ 时，$\partial_q^{(p)}$ 取得最小值。并且
$$
\frac{\eta_{\max}^2}{\eta_{\min}} \geq \eta_{\max} \Rightarrow \partial_q^{(p)} \geq \eta_q
$$
我们观察到，当 $\partial_q^{(p)} (p \neq q)$ 取得最大值时，得到的结果为
$$
\eta_q = \eta_{\max},\quad \partial_q^{(p)} {\max} = \frac{1}{\eta {\max}} \left\lceil \frac{\eta_{\max}^2}{\eta_{\min}} \right\rceil
$$
基于上述分析，所提出的更新规则遵守了上述原则。

所提方案的理论分析

隐私分析

通常，一个复杂的差分隐私方案需要多次使用满足差分隐私的算法。在我们的方案中，对于特定参与者，总隐私预算是 $P$，$T$ 表示协同构建过程中迭代的次数。因此，每个单独的随机决策树桩可获得的隐私预算为 $\varepsilon’ = P/T$。此外，在构建过程中，由于每个参与者的多个随机决策树桩是在相同的数据集上进行训练的，根据差分隐私的序列组合性质，特定参与者消耗的总隐私预算是每次迭代所用隐私预算的总和。对于所提出的分布式数据挖掘方案，只要每个参与者的构造过程满足 $\varepsilon$‐差分隐私，则该方案满足 $\varepsilon$‐差分隐私。

关键在于证明所提出的 DiffPRS 算法满足 $\varepsilon’$‐差分隐私。

引理1
DiffPRS算法满足 $\varepsilon’$‐差分隐私。

证明 令 $R$ 表示 DiffPRS 算法，$S$ 表示通过随机决策树桩方法构建的决策树桩，$\lambda(S)$ 表示根据 DiffPRS 算法向叶节点添加噪声后的决策树桩 $S$。$D$ 和 $D’$ 是两个最多相差一条数据的相邻数据集。假设 $V_1$ 和 $V_2$ 分别是基于数据集 $D$ 和 $D’$ 得到的两个叶向量，可知 $V_1$ 和 $V_2$ 最多有一个元素不同。因此，叶向量的全局敏感度为1。

如果等式 3 对任意决策树桩 $S$ 成立，
$$
\frac{P(R(D) = S)}{P(R(D’) = S)} \leq e^{\varepsilon’}
$$
那么 DiffPRS 算法满足 $\varepsilon’$‐差分隐私。

在发布模型及相应参数时，可以分为两个部分：决策树桩的结构和叶向量。从前文讨论中我们可以得出结论：随机决策树桩的结构在构建过程中引入了随机性，且不依赖于数据库查询，因此不会导致隐私泄露。对于叶向量，其全局敏感度为1，因此在添加满足 Lap(1/$\varepsilon$) 分布的噪声后，公式成立。
$$
\frac{P(\lambda(R(D)) = V)}{P(\lambda(R(D’)) = V)} \leq e^{\varepsilon’}
$$
总之，DiffPRS算法满足 $\varepsilon’$‐差分隐私。

复杂度分析

基于AdaBoost框架，本文提出了一种差分隐私分布式数据挖掘方案。其计算复杂度取决于AdaBoost算法。当弱学习器为决策树桩时，AdaBoost在T次迭代中的总体代价是 $\Theta(K(T + \log n_p) + MT + M n_p)$，其中 $n_p$ 是第p个参与者的样本数量，$K$ 表示训练数据集中的属性数量。模型的错误率可通过 $\Theta(n_p)$ 计算。在集成过程中，计算开销主要消耗在选择步骤的测试上，因此计算代价为 $\Theta(M n_p)$，其中 $M$ 表示参与方数量。在最坏情况下，所有 $M$ 个模型都被选中时，选择步骤中，确定权重的计算代价为 $\Theta(M)$。因此，对于第p个参与者而言，总计算代价为 $\Theta(K(T + \log n_p) + MT(1 + n_p))$。在所提方案中，训练过程和集成过程由每个参与者独立执行。此外，参与者在其本地模型完成后才开始集成过程。因此，所提方案的计算复杂度取决于样本数量最多的参与者，即所提方案的总计算复杂度为 $\Theta(K(T + \log n_{\max}) + MT + M n_{\max})$。

性能评估

在本节中，我们通过两个真实世界的数据集进行一系列实验，以评估所提出的分布式数据挖掘方案在分类任务中的预测准确率。我们在一台配备英特尔酷睿 i5‐8265U CPU 1.6GHz、8GB内存并运行 Windows 10的机器上实现了该方案。所提方案使用 Python 3.7开发。

实验设置

实验在两个真实数据集上进行。第一个是来自UCI机器学习库的成人数据集，包含来自1994年普查数据库的 48,442条人口普查记录。去除含有缺失值的记录后，剩余45,222条记录。每条记录包含14个属性。该二分类任务的目标是预测一个人的收入是否超过50K。另一个数据集是综合社会调查（GSS），包含与幸福感相关的11项个人信息，共51,020条记录。最终分类任务是推断对问题“去年你看过限制级电影吗？”的回答。

此外，为了模拟多个参与者的场景，我们随机地将成人数据集和GSS数据集水平划分为10个不同大小的子数据集。

为了评估所提方案的有效性，我们在不同条件下比较了隐私保护方法与其对应方法的预测准确率。具体而言，我们比较了所提分布式数据挖掘方案在隐私预算从0.1到4的不同取值下的性能表现。同时，我们测试了不同迭代次数以确定合适的 $T$ 值。此外，我们将所提方案与文献[16]中提出的InPriv方案进行对比。为不失一般性，我们将不采用隐私保护的所提方案设为基线。在本方案中，我们设定阈值 $\rho = 2$，因为 AdaBoost的错误率相对较小，而随机决策树桩的情况则相反。此外，所有实验结果均为5次运行的平均值。

实验结果与分析

图 3和图 4显示了所提方案在Adult数据集和GSS数据集上，不同隐私预算 $\varepsilon$ 以及迭代次数 $T$ 下的分类模型的预测准确率。从图3可以看出，分类准确率随着隐私预算和迭代次数的增加呈上升趋势。一旦迭代次数确定，预测准确率会随着隐私预算的增大而逐渐提高。这是因为为保护隐私而在叶节点添加的噪声量减少，从而提高了数据的可用性，使得共享模型能更准确地描述相应参与者的数据分布。通常，增加 $T$ 的值以进行更多迭代有助于获得更精确的模型。然而，当隐私预算较小时，更多的迭代可能对分类性能产生负面影响。迭代次数越多，随机决策树桩所能获得的隐私预算就越少。由于每个组件本身在隐私保护方面表现较差，最终的集成模型性能仍然较低。根据图 4，所提方案在 GSS数据集上的表现符合预期。

我们还将我们的方案与基于梯度提升决策树（GBDT）的 Inpriv在不同隐私预算（0.1、0.3、0.5、1.0、2.0和4.0）下进行了比较。此外，我们为成人数据集设置了 $T = 30$ 和基于上述观察的GSS数据集 $T = 20$。结果如图5和图6所示。

通过对比可以发现，为了保护分布式数据的隐私，需要牺牲一定的分类精度。总体而言，尤其是在隐私预算较小时，我们所提方案的表现优于Inpriv。原因有两点：（1）所提出的差分隐私决策树桩仅需少量噪声即可满足差分隐私的要求；（2）在构建过程中，通过自适应地融合共享模型，提高了每次迭代中基础学习器的准确性，减少了迭代次数，避免了因多次迭代而引入的额外噪声。但在某些情况下，InPriv的表现略优于我们所提方案。原因是GBDT分类器在某些数据集上的表现优于AdaBoost模型，且当隐私预算较大时，隐私保护不再成为限制模型准确率的重要因素。

结论与未来工作

本文中，我们提出了一种高效且保护隐私的分布式协同数据挖掘方案，适用于边云环境。针对自适应提升法，我们分析了提升过程，并精心设计噪声以实现所有参与者的差分隐私。在提升过程中，选择随机决策树桩作为基础学习器，因为边缘计算受限于有限的计算资源。然后，我们提出了一种自适应集成方法，该方法可以增强参与者的数据分布，并避免不良模型带来的负面影响。理论分析和实验结果验证了我们的方案能够在提供严格隐私保障的同时，高效地构建高性能的挖掘模型。

这项工作也提出了若干未来挑战。值得探索一种更合理的方法来度量多个数据所有者之间数据分布的差异，同时不损害数据所有者的隐私。一个有前景的解决方案是放宽隐私要求，允许参与者在隐私约束下更精确地估计数据分布。另一个有趣的方向是在准确性和通信成本之间实现更好的权衡。