1 引言

近年来, 互联网应用的逐步普及, 带来便利的同时, 大量数据信息通过个人用户、企业单位、研究机构等源源不断地产生. 对产生的数据进行数据分析, 挖掘事物潜在的关联, 再反馈给互联网应用商, 可以为大众提供更好的服务. 然而, 这些数据中不乏个人隐私数据, 诸如医疗信息、金融信息、轨迹数据等, 直接向外界发布原始数据存在着巨大的隐私泄露风险. 因此, 对外发布数据时, 需要采取一些隐私保护措施来保障数据安全.

K-匿名^[1]及其相关扩展L-Diversity^[2]、T-closeness^[3]是隐私保护的重要方法, 其主要思想是将待发布数据划分为多个等价类, 等价类内的k个实体无法相互区分, 通过限制数据发布实现数据隐私保护. 然而, 一旦攻击者具有相当的背景知识, K-匿名就无法提供很好的隐私保护效果, 而且无法就其隐私保护程度进行定量分析. 差分隐私^[4-9]作为一种严格可证的新兴隐私保护模型, 其前提是假设数据攻击者具有的背景知识最大化. 通过向输出中添加随机扰动, 尽可能减小单个记录对输出的影响, 保证攻击者无法通过观察不同的输出结果重构真实的数据信息, 实现了单个记录是否参与数据集的不可区分性.

从已有的研究可以看出, 差分隐私在低维数据发布方面做了诸多努力, 但在实际场景中, 更为常见的却是多属性数据集, 即高维数据集. 如果将以往的低维数据发布算法直接应用于多属性数据发布, 存在查询敏感度大、隐私预算消耗过快等问题, 导致数据发布效用低.

针对高维数据发布场景, 常见方法有: 1) 根据树结构划分高维数据集, 通过平衡分区的近似误差和数据的扰动误差来提高数据发布精度; 2) 通过构建数据集的概率图模型计算属性间的条件分布, 通过噪声条件分布近似原始数据集的联合分布, 以此生成新的合成数据集, 避免直接对原始数据扰动产生巨大的扰动误差; 3) 利用数据降维技术, 将高维数据转化成近似的低维数据, 对转化后的低维数据添加噪声扰动, 减少扰动噪声量.

在利用树结构发布高维数据集的研究中, 文献[10]借助细粒度单元划分和kd-树划分两种分区策略, 实现了差分隐私多维直方图发布. 文献[11]利用kd-树和quad-tree设计混合数据结构实现多维数据划分, 从而减少了注入的噪声量. 文献[12]提出了差分隐私泛化数据发布算法DiffGen, 通过构建决策树的过程完成数据的差分隐私保护. 基于概率图模型的研究也有所成果, 文献[13]提出数据发布方案PrivBayes, 该方案通过构建原始数据集的贝叶斯网络模型, 分析原始数据属性之间的依赖关系, 学习提取近似噪声条件分布, 采样生成新的合成数据集. 文献[14]提出联合树算法Jtree, 根据样本数据属性之间的关联构建依赖关系图, 结合联合树的推理基础, 从边缘关系图中学习一组噪声边缘表, 以此近似原始数据集的联合分布. 通过数据降维来近似高维数据发布的研究中, 文献[15, 16] 利用主成分分析技术识别高维数据的近似低维, 实现了高维数据向低维的转化, 并基于低维数据实现差分隐私保护. 文献[17]提出了差分隐私数据发布算法DPPro, 该算法利用随机投影技术, 完成高维数据在低维上的映射, 保证了高维数据发布效用. 文献[18]提出PriView方法, 通过构建一组含噪声扰动的低维View视图, 提取 $ \alpha $ -边际分布, 生成合成数据集.

然而, 前文提到的各种方法对不同属性的隐私保护处理大多隐含地假设同构性, 即不考虑属性数据敏感性的异构, 不同属性的随机干扰程度均相同. 由于不同属性携带的信息量不同, 从而对攻击者推理目标对象隐私信息的贡献不同, 即隐私泄露风险与属性敏感性呈正相关. 例如, 性别属性只有两个属性值, 与年龄属性相比, 携带的信息量更少, 对目标对象的刻画程度较浅, 对攻击者推理敏感信息的贡献较少, 需要的隐私保护强度相对较低, 相应的属性敏感性也就较低. 不考虑属性信息量差异带来的敏感性异构, 会导致没有充分保护高敏感属性数据, 或者过度丢失低敏感属性数据的信息.

文献[19]提出了一种加权贝叶斯网络数据发布方法, 虽然该方法是根据属性的多样性分配权重, 但其目标是借助属性权重构建更好的贝叶斯网络. 文献[20, 21]均在基于贝叶斯网络的数据发布算法中引入属性聚类, 以属性关联强弱分割属性集, 在减少隐私预算分割次数的基础上提高算法计算效率. 然而, 两者在隐私预算的分配上依然采取等分措施, 没有兼顾属性敏感性差异.

针对已有方法的不足之处, 本文提出了一种基于属性分割的差分隐私异构多属性数据发布算法HMPrivBayes (heterogeneous multi-attribute private data publishing via Bayesian networks), 主要贡献包括以下3个方面:

1) 根据属性之间的关联程度, 引入最大信息系数量化属性之间的相关关系, 设计满足差分隐私的谱聚类算法分割属性集, 能在一定程度上缩减贝叶斯网络结构空间, 提高算法计算效率.

2) 针对构建贝叶斯网络随机选取首个属性可能降低数据发布质量的问题, 以属性信息熵为权重选择属性, 尽可能提高数据发布质量, 保留数据实用价值.

3) 考虑到属性携带的信息量的不同, 基于贝叶斯网络提取属性条件分布时, 以属性归一化风险熵为权重分配隐私预算, 实现异构多属性保护.

2 基础知识 2.1 差分隐私

差分隐私(differential privacy, DP)保护模型保证在数据集中对一条记录进行增、删、改操作后, 查询返回的扰动输出没有明显差异, 以至于攻击者不能推断出目标记录是否在发布的数据集中, 即数据集中单个记录对输出的影响有限, 从而实现保护个体隐私.

定义1. $ \varepsilon $ -差分隐私^[4]. 设 $ {D_1} $ 和 $ {D_2} $ 为任意两个相邻数据集, 即它们彼此相差1条记录, $ Range(M) $ 是随机算法 $ M $ 的取值范围, 若算法 $ M $ 在数据集 $ {D}_{1} $ 和 $ {D_2} $ 上的任意输出 $ S \in Range(M) $ , 满足:

$ \frac{{Pr (M({D_1}) \in S)}}{{Pr (M({D_2}) \in S)}} \leqslant \exp (\varepsilon ) $

(1)

则称算法 $ M $ 满足 $ \varepsilon $ -差分隐私. 其中, 隐私预算 $ \varepsilon $ 与隐私保护程度呈负相关, 与隐私泄露风险呈正相关. $Pr (M({D_1}) \in S)$ 和 $Pr (M({D_2}) \in S)$ 表示算法 $ M $ 在数据集 $ {D_1} $ 和 $ {D_2} $ 上输出为 $ S $ 的概率.

任何满足定义1的噪音机制都可以视为差分隐私机制, 差分隐私中常见噪音机制有Laplace机制^[22]和指数机制^[23], 其噪声扰动大小与随机函数的敏感度以及隐私预算参数密切相关.

定义2. 全局敏感度^[5]. 设查询函数 $ f:D \to {\mathbb{R}^n} $ , $ f $ 的全局敏感度定义如下:

$ \Delta f = \mathop {\max }\limits_{{D_1}, {D_2}} ||f({D_1}) - f({D_2})|| $

(2)

其中, $ {D_1} $ 和 $ {D_2} $ 表示任意两个相邻数据集, 全局敏感度 $ \Delta f $ 由查询函数 $ f $ 决定.

定义3. Laplace机制^[22]. 对任意数据集 $ D $ 和查询函数 $ f:D \to {\mathbb{R}^n} $ , 若算法 $ M $ 的输出结果满足:

$ M\left( D \right) = f\left( D \right) + Lap\left( {\Delta f/\varepsilon } \right) $

(3)

则算法 $ M $ 实现了 $ \varepsilon $ -差分隐私. 其中, $ Lap\left( {\Delta f/\varepsilon } \right) $ 表示添加的噪声量, 噪声量与 $ \Delta f $ 成正比, 与 $ \varepsilon $ 成反比. Laplace机制主要用于处理数值型数据.

定义4. 指数机制^[23]. 对任意数据集 $D$ , 给定评分函数 $ u:\left( {D, r} \right) \to R $ , 若算法 $ M $ 满足:

$ M\left( {D, u} \right) = \left\{ {r|Pr \left[ {r \in O} \right] \propto \exp \left( {\frac{{\varepsilon u\left( {D, r} \right)}}{{2\Delta u}}} \right)} \right\} $

(4)

则算法 $ M $ 实现了 $ \varepsilon $ -差分隐私. 其中, $ \Delta u $ 为 $ u\left( {D, r} \right) $ 的全局敏感度, $Pr \left[ {r \in O} \right]$ 为评分函数 $ u $ 输出 $ r $ 的概率, 评分越高, $ r $ 被输出的概率越高. 指数机制通常用于处理非数值型数据.

对于一组满足差分隐私的随机独立算法, 差分隐私的串行组合性质和并行组合性质^[24]可以用于证明整体算法满足差分隐私保护.

性质1. 串行组合^[24]. 给定数据集 $D$ 和 $D$ 上1组随机独立算法 $ {M_1}\left( D \right), {M_2}\left( D \right), \cdots , {M_m}\left( D \right) $ , 其中每个算法 $ {M_i}\left( D \right) $ 满足 $ {\varepsilon _i} $ -差分隐私, 则 $ M = \left\{ {{M_1}, {M_2}, \cdots , {M_m}} \right\} $ 满足 $ \displaystyle\sum\nolimits_{i = 1}^m {{\varepsilon _i}} $ -差分隐私.

串行组合表明, 当一系列差分隐私机制应用于同一数据集时, 隐私预算和噪声数量呈线性累积.

性质2. 并行组合^[24]. 给定数据集 $D$ , 将 $D$ 分割成 $ m $ 个互不相交的子集 $ D = \left\{ {{D_1}, {D_2}, \cdots , {D_m}} \right\} $ . 每个子集中的随机独立算法 $ {M_1}\left( {{D_1}} \right), \cdots , {M_m}\left( {{D_m}} \right) $ 均满足 $ {\varepsilon _i} $ -差分隐私, 则组合算法 $ M = \left\{ {{M_1}, {M_2}, \cdots , {M_m}} \right\} $ 满足 $ \max \left( {{\varepsilon _i}} \right) $ -差分隐私.

并行组合表明, 当一系列差分隐私机制应用于数据集的不同子集时, 隐私保护的程度取决于 $ {\varepsilon _i} $ 的最大值.

2.2 谱聚类

谱聚类(spectral clustering, SC)^[25]是利用图论中的图分割完成数据聚类的算法. 它的主要思想是先将数据集映射成一张带权无向图, 基于两点之间的距离计算顶点相似度, 通过最优划分准则分割图中结点, 最大化子图内部的相似度, 实现数据聚类. 标准的谱聚类算法实现流程如算法1所示.

算法1. 谱聚类算法

输入: 数据集 $\scriptstyle D = \left\{ {{x_1}, {x_2}, \cdots , {x_n}} \right\} $ , 降维后的维度k₁, 聚类方法, 簇数量k

输出: 簇划分 $\scriptstyle C( {{c_1}, {c_2}, \cdots , {c_k}} )$

1. 计算n×n的相似矩阵S: $\scriptstyle{s_{ij}} = {\| {{x_i} - {x_j}} \|_2}$ ;

2. 根据相似矩阵S构建邻接矩阵W: $\scriptstyle w_{i j}=\exp \left(\frac{-s_{i j}}{2 \sigma^{2}}\right)$

3. 计算n×n的度矩阵B: $\scriptstyle{b_{ij}} =\scriptstyle \left\{ \begin{array}{l} \scriptstyle \sum\nolimits_{k = 1}^d {{w_{ik}}, \; i = j} \\\scriptstyle 0, \; i \ne j\end{array} \right.$ ;

4. 计算并标准化拉普拉斯矩阵 $\scriptstyle L = {B^{ - 1/2}}(B - W){B^{ - 1/2}}$ ;

5. 计算L最小的k₁个特征值以及各自对应的特征向量 $\scriptstyle {u_1}, \; {u_2}, \; \cdots , \; {u_{{k_1}}}$ ;

6. 将特征向量组成矩阵并按行进行标准化, 最终组成n×k₁维的特征矩阵U;

7. 将U中的每一行作为一个k₁维的样本, 按照输入的聚类方式进行聚类, 聚类维数为k;

8. 返回簇划分 $\scriptstyle C\left( {{c_1}, \; {c_2}, \; \cdots , \; {c_k}} \right)$ .

在本文中, 谱聚类主要用于属性聚类, 即根据属性之间的关联程度分割属性集. 本文选用最大信息系数(maximal information coefficient, MIC)^[26]度量属性之间关联程度. 在此之前, 互信息是常用的属性关联度量手段, 然而, 互信息需要考虑连续属性的离散化, 而且不同数据集上的互信息计算结果无法相互比较. MIC利用网格划分属性值域, 结合属性互信息, 可以更准确地识别出大数据集中属性间的线性或非线性关系, 以及非函数依赖关系.

定义5. 最大信息系数^[26]. 给定属性 $ X, \; Y $ 和有序对 $ < a, b > $ , 样本数量为 $ N $ , 将当前二维空间在 $ x, \; y $ 方向上划分为 $ a \times b $ 的网格 $ G $ , 将属性数据点离散落入网格 $ G $ 中, 属性 $ X $ 和 $ Y $ 的最大信息系数计算如下:

$ MIC\left( {X, Y} \right) = \mathop {\max }\limits_{a \times b < B} \frac{{I\left( {X, Y} \right)}}{{{{\log }_2}\min \left( {a, b} \right)}} $

(5)

其中, $ B $ 为网格划分 $ a \times b $ 的上限值, 通常取值 ${N^{0.6}}$ 或 ${N^{0.55}}$ , $I\left( {X, \; Y} \right)$ 为属性X和Y的互信息值, 具体计算如下:

$ I\left( {X, Y} \right) = \sum\nolimits_{i = 1}^n {\sum\nolimits_{j = 1}^m {Pr ( {{x_i}, {y_j}} )} } \log \frac{{Pr ( {{x_i}, {y_j}} )}}{{Pr ( {{x_i}} )Pr ( {{y_j}} )}} $

(6)

其中, $Pr ( {{x_i}, {y_j}} )$ 表示属性 $X, \; Y$ 取值 ${x_i}, \; {y_j}$ 的联合分布.

2.3 贝叶斯网络

贝叶斯网络(Bayesian network)是常用的概率图模型之一, 用来表示一组随机变量(属性)之间的依赖关系. 形式上, 贝叶斯网络 $ N $ 可以表示为 $N = \left( {G, \; \theta } \right)$ . 其中, $ G $ 表示有向无环图, 图中节点代表随机变量, 节点之间的有向边代表随机变量之间的依赖关系. 在 $ G $ 中, 若存在一条从 $ {X_j} $ 到 $ {X_i} $ 的有向边, 则称 $ {X_j} $ 为 $ {X_i} $ 的父节点. $ {X_i} $ 的所有父节点构成 $ {X_i} $ 的父节点集合, 表示为 $ {\prod _i} $ . $ \theta $ 表示 $ N $ 的参数集合, $ \theta $ 包含每个节点 $ {X_i} $ 的条件分布, 表示为 $Pr \left[ {{X_i}|{\prod _i}} \right]$ . 对于一个包含属性集 $ X = \left\{ {{X_1}, {X_2}, \cdots , {X_d}} \right\} $ 的贝叶斯网络 $ N $ , $ N $ 可以近似表示 $ X $ 的联合概率分布, 具体为 ${Pr _N}\left[ X \right] = \prod\nolimits_{i = 1}^d {Pr \left[ {{X_i}|{\prod _i}} \right]}$ . 图1表示包含属性节点 $ \left\{ {{X_1}, {X_2}, \cdots , {X_5}} \right\} $ 的贝叶斯网络, 图中所有属性节点的联合概率分布为 $Pr \left( {{X_1}, {X_2}, {X_3}, {X_4}, {X_5}} \right) =$ $Pr \left( {{X_1}} \right) Pr \left( {{X_2}|{X_1}} \right) Pr \left( {{X_3}|{X_2}} \right) Pr \left( {{X_4}|{X_1}, {X_2}} \right) Pr \left( {{X_5}|{X_3}, {X_4}} \right)$ .

3 基于属性分割的差分隐私异构多属性数据发布 3.1 HMPrivBayes算法概述

HMPrivBayes算法的整体流程如图2所示, 包括4个阶段: 属性聚类划分、构建差分隐私贝叶斯网络、生成属性加噪条件分布、生成待发布数据集. 为了方便描述, 本文假设所有属性均是二进制属性. 对于非二进制属性, 利用文献[13]提出的等宽法将非二进制属性转化成一组二进制属性. 由于等宽法的转化过程只依赖非二进制属性的值域, 且属性的值域是公开信息, 不涉及隐私数据. 因此, 属性转化过程不存在隐私泄露问题.

HMPrivBayes算法的实现过程如算法2所示.

算法2. HMPrivBayes算法

输入: 数据集 $\scriptstyle D = \left\{ {{x_1}, {x_2}, \cdots , {x_n}} \right\}$ , 属性集 $\scriptstyle X = \left\{ {{X_1}, {X_2}, \cdots , {X_d}} \right\}$ , 属性簇个数k, 隐私预算ε

输出: 数据集D满足差分隐私的合成数据集D′

1. 初始化D′= $\scriptstyle\varnothing $ ;

2. 分配隐私预算ε₁+ε₂+ε₃=ε;

3. 执行算法3, 返回聚类结果 $\scriptstyle C = \left\{ {{C_1}, {C_2}, \cdots , {C_k}} \right\}$ ;

4. 依据C划分原始数据集 $\scriptstyle D = \left\{ {{D_1}, \cdots , {D_k}} \right\}$ ;

5. for i=1 to k do

　　执行算法4, 求贝叶斯网络N_i;

　　基于 $\scriptstyle P_i^*$ 计算N_i的带噪联合分布, 采样得到合成数据集 $\scriptstyle D_i'$ , 并加入 $\scriptstyle D'$ ;

　　执行算法5, 求带噪条件分布 $\scriptstyle P_i^*$ ;

　end for

6. 返回 $\scriptstyle D'$ .

3.2 差分隐私谱聚类算法

谱聚类算法是根据数据点之间相似性程度进行数据集聚类, 对于关联程度不高的属性对, 其相似值相应较小, 从而分割至不同的子集. 本文采用最大信息系数作为属性之间关联程度衡量指标, MIC不仅能高效检测大数据集中不同类型属性之间关联关系, 而且不需要进行归一化处理. 选用K-means++聚类算法实现特征矩阵 $ U $ 的聚类划分, K-means++算法选择初始的聚类中心时, 要求各聚类中心之间的相互距离要尽可能的远. 初始点选择的优化, 使得K-means++算法在聚类结果准确性上有较大提升. 差分隐私谱聚类算法DPSC如算法3所示.

算法3. DPSC算法

输入: 数据集 $\scriptstyle D=\left\{x_{1}, x_{2},\cdots{,} x_{n}\right\}$ , 属性集 $\scriptstyle X = \left\{ {{X_1}, {X_2}, \cdots , {X_d}} \right\}$ , 尺度参数 $\scriptstyle \sigma$ , 降维后的维度 $\scriptstyle k_{1}$ , 聚类后的维度 $\scriptstyle k$ , 隐私预算 $\scriptstyle \varepsilon_{1}$

输出: 属性集 $\scriptstyle X$ 聚类划分结果 $\scriptstyle C^{\prime}=\{C_{1}, C_{2}, \cdots, C_{k}\}$

1. 计算 $\scriptstyle d \times d$ 的相似矩阵 $\scriptstyle S$ : $\scriptstyle s_{i j}=\left\{ \begin{array}{l}\scriptstyle{{{MIC}}}\left(X_{i}, X_{j}\right)+{Lap}\left(\frac{\Delta m \cdot d(d-1)}{\varepsilon_{1} \cdot(2\lfloor d / 2\rfloor)}\right), \; i \neq j \\\scriptstyle 0, \; i=j\end{array}\right.\text{; }$

2. 执行算法1的步骤2–步骤6;

3. 使用K-means++算法对新样本点 $\scriptstyle U=\{u_{1}, u_{2}, \cdots, u_{k_{1}}\}$ 进行聚类划分得到划分结果 $\scriptstyle C$ ;

4. 返回属性聚类结果 $\scriptstyle C^{\prime}=\left\{C_{1}, C_{2}, \cdots, C_{k}\right\}$ .

由于在计算属性关联程度时涉及到了原始数据集 $D$ 的使用, 为了保护数据集中的数据隐私不被泄露, 采用Laplace机制对计算结果添加噪声.

首先计算属性间的最大信息系数的全局敏感度 $ \Delta m $ , 由式(5)可知, MIC的计算取决于属性间的互信息, 故计算相似矩阵 $ S $ 的全局敏感度 $ \Delta m = \Delta I $ . 由文献[13]可知, $\Delta I = \dfrac{1}{n} \cdot \log n + \dfrac{{n - 1}}{n} \cdot \log \dfrac{n}{{n - 1}}$ .

从算法3可以看出, Laplace机制是通过多次扰动加噪过程实现的, 每次加噪都需要消耗部分隐私预算 $ {\varepsilon _1} $ . 由定义可知, 相似矩阵 $ S $ 是一个对称矩阵, 且对角线元素不需要计算, 所以计算 $ {{d\left( {d - 1} \right)} \mathord{\left/ {\vphantom {{d\left( {d - 1} \right)} 2}} \right. } 2} $ 个不同元素的值就可以得到矩阵 $ S $ . 每次访问数据集 $ D $ 可以计算 $ \left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor $ 对属性对之间的MIC, 因此, 对数据集 $ D $ 的访问次数, 即扰动总次数为 $ {{d\left( {d - 1} \right)} \mathord{\left/ {\vphantom {{d\left( {d - 1} \right)} {\left( {2\left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor } \right)}}} \right. } {\left( {2\left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor } \right)}} $ , 每次扰动添加的噪声量为 $ Lap\left( {{{\left( {\Delta m \cdot d(d - 1)} \right)} \mathord{\left/ {\vphantom {{\left( {\Delta m \cdot d(d - 1)} \right)} {\left( {{\varepsilon _1} \cdot (2\left\lfloor {d/2} \right\rfloor )} \right)}}} \right. } {\left( {{\varepsilon _1} \cdot (2\left\lfloor {d/2} \right\rfloor )} \right)}}} \right) $ . 由定义3和性质1可知, 算法3满足 $ {\varepsilon _1} $ -差分隐私.

3.3 差分隐私贝叶斯网络算法

在基于贝叶斯网络构建数据发布模型的现有研究中, 大多以文献[13]中的PrivBayes为参照进一步改进贝叶斯网络的构建设计发布算法^[19-21]. 由于PrivBayes在构建贝叶斯网络时, 随机选取首个属性加入父节点集合, 这样构建的贝叶斯网络不一定能真实反映原始数据集. 与此同时, 通过枚举的方式选取互信息最大的 $ \left( {{X_i}, {\prod _i}} \right) $ 对会造成大量无意义的计算, 影响贝叶斯网络的构建速度. 基于此, 本文提出改进的贝叶斯网络构建算法IBayes, IBayes引入信息熵作为选取首个属性的依据, 同时缩减候选属性的 $ \left( {{X_i}, {\prod _i}} \right) $ 对, 以此达到快速构建“最合适”的贝叶斯网络的目的. IBayes的实现过程如算法4所示.

算法4. IBayes算法

输入: 数据子集 $\scriptstyle D_{i}=\left\{x_{1}, x_{2}, \cdots, x_{n}\right\}$ , 属性子集 $\scriptstyle {C_i} = \{ {{X_1}, {X_2}, \cdots , {X_{\left| {{C_i}} \right|}}} \}$ , 最大父节点数 $\scriptstyle l$ , 隐私预算 $\scriptstyle {\varepsilon}_{2}$

输出: 数据子集 $\scriptstyle { D_i}$ 的贝叶斯网络 $\scriptstyle {N_i}$

1. 初始化 $\scriptstyle N_{i}=\varnothing$ , $\scriptstyle V=\varnothing$ ;

2. 使用指数机制从 $\scriptstyle C_i$ 中选取信息熵最大的属性 $\scriptstyle {X_j}$ , 将 $\scriptstyle \left( {{X_j}, \varnothing } \right)$ 加入 $\scriptstyle {N_i}$ , 将 $\scriptstyle {X_j}$ 加入 $\scriptstyle V$ ;

3. for $\scriptstyle t=2$ to $\scriptstyle |C_{\imath}|$ do

初始化 $\scriptstyle \Omega=\varnothing $ ;

for $\scriptstyle {X_s} \in {C_i}\backslash V$

令 $\scriptstyle V^{\prime}=V$ ;

If $\scriptstyle {S_i}\left( {{X_s}, {X_c}} \right) = 0$ 且 $\scriptstyle {X_c} \in V'$

将 $\scriptstyle {X_c}$ 从 $\scriptstyle V'$ 中移除, 且 $\scriptstyle \Pi_{s} \in\left(\begin{array}{c} \scriptstyle{V'}\\ \scriptstyle l\end{array} \right)$ ;

将 $\scriptstyle \left( {{X_s}, {\prod _s}} \right)$ 加入 $\scriptstyle \Omega$ ;

end for

使用指数机制从 $\scriptstyle \Omega$ 中选择互信息最大的 $\scriptstyle \left(X_{t}, \Pi_{t}\right)$ 加入 $\scriptstyle {N_i}$ , 同时 $\scriptstyle X_{t}$ 加入 $\scriptstyle V$ ;

end for

4. 返回 $\scriptstyle {N_i}$ .

信息熵是对信息不确定性的度量, 与信息的不确定性呈正相关. 信息熵越大, 携带的信息量越多, 能更多地反映出数据的多样性, 增加数据的实用价值, 反之亦然. 因此, 引入信息熵作为选取首个属性的依据是合理的.

对于数据集 $ {D_i} $ 中的每个属性 $ {X_j} $ , 其信息熵 $ H({X_j}) $ 计算如下:

$ H({X_j}) = - \sum\nolimits_{j = 1}^n {{p_j}\log } {p_j} $

(7)

根据式(7)可知, 当取不同值的概率相等时信息熵最大, 即 $ {X_j} $ 中有 $n$ 个不同的取值时 $ H({X_j}) $ 取得最大值, 为 $H({X_j}) = - \displaystyle\sum\nolimits_{s = 1}^n {{1 \mathord{\left/ {\vphantom {1 n}} \right. } n} \cdot \log } {1 \mathord{\left/ {\vphantom {1 n}} \right. } n} = \log n$ .

通过图3的实例可以说明属性信息熵的最大差异.

根据图3(a)取值概率分布计算 $ H({X_j}) $ 的值为0, 通过图3(b)计算 $ H({X_j}) $ 的值为 $\dfrac{1}{n} \cdot \log n + \dfrac{{n - 1}}{n} \cdot \log \dfrac{n}{{n - 1}}$ . 在此基础上, 可以得出属性信息熵的全局敏感度 $ \Delta H $ 为:

$ \Delta H = \frac{1}{n} \cdot \log n + \frac{{n - 1}}{n} \cdot \log \frac{n}{{n - 1}} $

(8)

PrivBayes通过枚举选择互信息最大的属性对时, 候选 $ \left( {{X_t}, {\prod _t}} \right) $ 对越多, 对算法的时间复杂的影响越大. 因此, 本文在求解候选属性的父节点集时, 筛选关联程度弱的属性对, 减少 $ \left( {{X_t}, {\prod _t}} \right) $ 对互信息的计算量. 筛选操作通过关联矩阵 $ {S_i} $ 实现. 从相似矩阵 $ S $ 中提取出相关属性子集的最大信息系数, 根据式(9)得到 $ {S_i} $ :

$ {S_i}\left( {{X_s}, {X_c}} \right) = \left\{ \begin{array}{l} 1, {\text{ }}{\rm{else}} \\ 0, {\text{ }}\left\{ \begin{gathered} S\left( {{X_s}, {X_c}} \right) \leqslant \eta \times \max S\left( {{X_s}} \right){\text{ }} \\ S\left( {{X_c}, {X_s}} \right) \leqslant \eta \times \max S\left( {{X_c}} \right) \\ \end{gathered} \right.{\text{or}} \end{array} \right. $

(9)

IBayes算法使用指数机制选取加入 $ {N_i} $ 中的首个属性节点, 同时从 $ \Omega $ 中选择 $ \left( {{X_t}, {\prod _t}} \right) $ 对加入 $ {N_i} $ , 评分函数分别采用属性信息熵和互信息. 由于 $ \Delta u = \Delta I = \Delta H $ , 除选取加入 $ {N_i} $ 中的首个属性节点外, 选择 $ \left( {{X_t}, {\prod _t}} \right) $ 需要执行 $ \left| {{C_i}} \right| - 1 $ 次, 故将 $ {\varepsilon _2} $ 平均分为 $ \left| {{C_i}} \right| $ 份. 因此, 结合差分隐私指数机制, 选择 $ \left( {{X_t}, {\prod _t}} \right) $ 的概率表达式如式(10):

$ P\left( {{X_t}, {\prod _t}} \right) = \dfrac{{\exp \left( {\dfrac{{{\varepsilon _2}u\left( {{X_t}, {\prod _t}} \right)}}{{2\left| {{C_i}} \right|\Delta u}}} \right)}}{{\displaystyle\sum\limits_{\left( {{X_t}, {\prod _t}} \right) \in \Omega } {\exp \left( {\dfrac{{{\varepsilon _2}u\left( {{X_j}, {\prod _j}} \right)}}{{2\left| {{C_i}} \right|\Delta u}}} \right)} }} $

(10)

IBayes算法最终输出一个贝叶斯网络 $ {N_i} $ , 除了使用指数机制选取首个属性节点和 $ \left( {{X_t}, {\prod _t}} \right) $ 对之外, 其他步骤均无需访问原始数据集 $D$ . 在构建贝叶斯网络之前, HMPrivBayes算法已经通过算法3将原始数据集 $D$ 划分为 $ k $ 个独立数据子集 $ {D_1}, \cdots , {D_k} $ . 根据定义4和性质1, 指数机制 $ \exp \left( {{{{\varepsilon _2}u\left( {{D_i}, r} \right)} \mathord{\left/ {\vphantom {{{\varepsilon _2}u\left( {{D_i}, r} \right)} {\left( {2\left| {{C_i}} \right|\Delta u} \right)}}} \right. } {\left( {2\left| {{C_i}} \right|\Delta u} \right)}}} \right) $ 满足 $ {\varepsilon _2} $ -差分隐私, 因此IBayes算法满足 $ {\varepsilon _2} $ -差分隐私.

3.4 差分隐私异构条件分布计算

通过贝叶斯网络计算属性的联合分布, 生成合成数据集, 可以近似原始数据集. 尽管贝叶斯网络的构建过程满足差分隐私保护, 但仍存在隐私泄露的可能. 因此, 需要对计算出来的属性联合分布添加噪声扰动, 以进一步保护隐私数据. 之前的研究均通过均分隐私预算实现联合分布噪声扰动, 这种方式没有考虑到属性敏感性差异. 属性携带的信息量越多, 帮助攻击者推出目标信息的贡献越大, 也就意味着它对外发布的敏感性越高. 基于此, 本文提出差分隐私异构条件分布计算算法HnoisyConditionals, 具体实现过程如算法5所示.

算法5. HnoisyConditionals算法

输入: 数据集 $\scriptstyle D_{i}=\left\{x_{1}, \; x_{2}, \; \cdots, \; x_{n}\right\}$ , 贝叶斯网络 $\scriptstyle N_{i}$ , 隐私预算 $\scriptstyle \varepsilon _{3}$

输出: 根据 $\scriptstyle N_{i}$ 生成的带噪声的条件分布集 $\scriptstyle P_{i}^{*}$

1. 初始化 $\scriptstyle P_{i}^{*}=\varnothing$ , 令 $\scriptstyle l^{\prime}=\min \left(\left|C_{i}\right|-1, d\right)$ ;

2. for $\scriptstyle j=l'+1$ to $\scriptstyle \left|C_{i}\right|$ do

　构建 $\scriptstyle {X_j}$ 的联合分布 $\scriptstyle Pr \left( {{X_j}, {\prod _j}} \right)$ ;

　加入拉普拉斯噪声 $\scriptstyle {Lap}\left(\frac{2}{n \varepsilon _{3}} \times \frac{\sum_{j=l'+1}^{|C_i|}{\rm{exp}}(-OE_j)}{{\rm{exp}}(-OE_j)}\right)$ , 实现差分隐私 $\scriptstyle {Pr ^*}\left( {{X_j}, {\prod _j}} \right)$ ;

设 $\scriptstyle {Pr ^*}( {{X_j}, {\prod _j}} )$ 中的负值归0并正常化;

从 $\scriptstyle {Pr ^*}( {{X_j}, {\prod _j}} )$ 中提取 $\scriptstyle {\Pr ^*}( {{X_j}|{\prod _j}} )$ 并加入 $\scriptstyle P_{i}^{*}$ ;

end for

3. for $\scriptstyle j=1$ to $\scriptstyle l'$ do

从 $\scriptstyle {Pr ^*}( {{X_{l' + 1}}, {\prod _{l' + 1}}} )$ 中提取 $\scriptstyle {Pr ^*}( {{X_j}|{\prod _j}} )$ 加入 $\scriptstyle P_{i}^{*}$ ;

end for

4. 返回 $\scriptstyle P_{i}^{*}$ .

根据式(7), 归一化风险熵计算公式如下:

$ O{E_j} = - \frac{1}{{\log n}}\sum\nolimits_{i = 1}^n {{p_i}\log } {p_i} $

(11)

在算法5中, 向联合分布注入噪声不再采取均分策略, 而是以归一化风险熵为权重分配隐私预算. 由文献[13]可知, 联合分布全局敏感度为 $ {2 \mathord{\left/ {\vphantom {2 n}} \right. } n} $ . 因此, 每次对联合分布 $Pr ( {{X_j}, {\prod _j}} )$ 添加的拉普拉斯噪声大小为:

$ Lap\left( {\frac{2}{{n{\varepsilon _3}}} \times \frac{{\displaystyle\sum\nolimits_{j = l' + 1}^{\left| {{C_i}} \right|} {\exp \left( { - O{E_j}} \right)} }}{{\exp \left( { - O{E_j}} \right)}}} \right) $

(12)

其中, 属性归一化风险熵 $ O{E_j} $ 越大, 属性敏感性越高, 需要的隐私保护强度越大, 分配的隐私预算也就越小. 由定义3和性质1可知, 算法5满足 $ {\varepsilon _3} $ -差分隐私.

3.5 隐私分析

定理1. HMPrivBayes算法满足 $ \varepsilon $ -差分隐私.

证明: 在HMPrivBayes的整个执行过程中, 其中有3步涉及原始数据集的访问, 分别是属性分割、构建差分隐私贝叶斯网络和提取属性噪声条件分布, 下面分别讨论这3步的隐私保护强度.

对于属性分割, 需要重复访问数据集 $D$ 计算属性对的MIC, 每次访问数据集 $D$ 可以计算 $ \left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor $ 对属性对的MIC, 相似矩阵 $ S $ 中有 $ {{d\left( {d - 1} \right)} \mathord{\left/ {\vphantom {{d\left( {d - 1} \right)} 2}} \right. } 2} $ 个不同的MIC值需要计算, 因此, 需访问 $ {{d\left( {d - 1} \right)} \mathord{\left/ {\vphantom {{d\left( {d - 1} \right)} {\left( {2\left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor } \right)}}} \right. } {\left( {2\left\lfloor {{d \mathord{\left/ {\vphantom {d 2}} \right. } 2}} \right\rfloor } \right)}} $ 次数据集 $D$ . MIC计算的敏感度为 $ \Delta m $ , 故每次扰动添加的噪声量为 $ Lap\left( {{{\left( {\Delta m \cdot d(d - 1)} \right)} \mathord{\left/ {\vphantom {{\left( {\Delta m \cdot d(d - 1)} \right)} {\left( {{\varepsilon _1} \cdot (2\left\lfloor {d/2} \right\rfloor )} \right)}}} \right. } {\left( {{\varepsilon _1} \cdot (2\left\lfloor {d/2} \right\rfloor )} \right)}}} \right) $ , 进而属性分割满足 $ {\varepsilon _1} $ -差分隐私.

在贝叶斯网络构建阶段, 需要借助指数机制 $ \exp \left( {{{{\varepsilon _2}H({X_j})} \mathord{\left/ {\vphantom {{{\varepsilon _2}H({X_j})} {\left( {2\left| {{C_i}} \right|\Delta H} \right)}}} \right. } {\left( {2\left| {{C_i}} \right|\Delta H} \right)}}} \right) $ 从数据子集 $ {D_i} $ 中选取加入 $ {N_i} $ 的首个属性节点. 指数机制 $ \exp \left( {{{{\varepsilon _2}u\left( {{X_t}, {\prod _t}} \right)} \mathord{\left/ {\vphantom {{{\varepsilon _2}u\left( {{X_t}, {\prod _t}} \right)} {\left( {2\left| {{C_i}} \right|\Delta u} \right)}}} \right. } {\left( {2\left| {{C_i}} \right|\Delta u} \right)}}} \right) $ 用于选择互信息最大的 $ \left( {{X_i}, {\prod _i}} \right) $ 对加入 $ {N_i} $ , 执行 $ \left| {{C_i}} \right| - 1 $ 次, 因此贝叶斯网络构建满足 $ {\varepsilon _2} $ -差分隐私.

从贝叶斯网络 $ {N_i} $ 中提取属性条件分布时, 需要往 $ \left| {{C_i}} \right| - l' $ 个属性联合分布中添加噪声扰动, 进一步保护数据隐私. 为了兼顾属性敏感性的差异, 隐私预算根据属性 $ {X_j} $ 的归一化风险熵 $ O{E_j} $ 异构分配, 添加的噪声量为 $Lap\left( {{{\left( {2 \times \displaystyle\sum\nolimits_{j = l' + 1}^{\left| {{C_i}} \right|} {\exp ( { - O{E_j}} )} } \right)} \mathord{\left/ {\vphantom {{\left( {2 \times \displaystyle\sum\nolimits_{j = l' + 1}^{\left| {{C_i}} \right|} {\exp ( { - O{E_j}} )} } \right)} {\left( {n{\varepsilon _3}\exp ( { - O{E_j}} )} \right)}}} \right. } {\left( {n{\varepsilon _3}\exp ( { - O{E_j}} )} \right)}}} \right)$ , 其中联合分布计算的敏感度为 $ {2 \mathord{\left/ {\vphantom {2 n}} \right. } n} $ . 因此, 属性条件分布计算满足 $ {\varepsilon _3} $ -差分隐私.

综上, HMPrivBayes算法满足 $ \varepsilon $ -差分隐私, 其中 $ {\varepsilon _1} + {\varepsilon _2} + {\varepsilon _3} = \varepsilon $ .

4 实验评估 4.1 实验设置

本次实验使用Python编程语言来实现所有的方法, 其中贝叶斯网络模型部分的实现参考了Zhang等人^[13]论文的实验相关代码. 实验的硬件环境为AMD Ryzen7 4800H (2.90 GHz), 操作系统为Windows 10 (64位), 内存为16 GB.

实验采用两个公开可用的数据集Adult^[27]和Big5^[28]. 其中, Adult为美国人口普查数据集, 包含45222条个体信息记录, 每条记录包含15个属性. Big5是包含19719条人口普查记录的信息集合, 每条记录包含57个属性. 利用等宽法完成属性转化后, 二进制属性的数量分别为52和175. 两个数据集的详细信息如表1所示.

对于这两个数据集, 隐私预算分配策略为 $ {\varepsilon _1} = {{{a_1}} \mathord{\left/ {\vphantom {{{a_1}} a}} \right. } a}\varepsilon , {\text{ }}{\varepsilon _2} = {{{a_2}} \mathord{\left/ {\vphantom {{{a_2}} a}} \right. } a}\varepsilon , {\text{ }}{\varepsilon _3} = {{{a_3}} \mathord{\left/ {\vphantom {{{a_3}} a}} \right. } a}\varepsilon $ , 其中 $ a = {a_1} + {a_2} + {a_3}, $ ${a_1} = \dfrac{{d - 1}}{n}, {a_2} = \dfrac{{2d}}{{nk}}, {a_3} = \dfrac{{2d}}{{nk}}$ . 属性分类簇个数 $ k $ 默认值为3, 贝叶斯网络的最大入度数 $ l $ 默认值为3.

4.2 评价指标

本文通过 $ \alpha $ -边际分布^[29]和SVM (support vector machine)分类^[30]来评估算法的性能. 实验选取2-边际分布和3-边际分布作为 $ \alpha $ -边际分布评估的实例, 通过计算生成的噪声边际分布和原始边际分布的平均变量距离(average variation distance, AVD)^[31]确性. $ {L_1} $ 距离的一半:

$ Dis{t_{{\rm{AVD}}}}\left( {P, Q} \right) = \frac{1}{2}\sum\nolimits_{\omega \in \mho } {\left| {P\left( \omega \right) - Q\left( \omega \right)} \right|} $

(13)

其中, $ P\left( \omega \right) $ 和 $ Q\left( \omega \right) $ 分别表示加噪前后的边际分布, $ \mho $ 表示边际分布集合.

实验通过度量SVM分类的准确性, 分析生成的噪声数据集的有效性. 本组实验在噪声数据集上同时训练2个分类器, 通过分析合成数据集的其他属性预测目标属性的分类结果. 对于Adult数据集, 选取salary作为分类实例, 预测个体每年收入是否超过50k. 对于Big5数据集, 选取age作为分类实例, 预测个体年龄是否在50岁以下. 每个分类任务, 将合成数据集按照8:2分为训练数据集和测试数据集, 重复运行50次, 并记录实验结果的平均值.

4.3 实验结果

本文将通过3个不同的实验来分析HMPrivBayes算法的可用性和高效性. 为了更好地评估HMPrivBayes方案的性能, 本节采用的对比算法包括: PrivSCBN、PrivBayes、Jtree、NoPrivacy. 其中, PrivSCBN算法^[20]、PrivBayes算法^[13]均是基于贝叶斯网络的数据发布算法, Jtree^[14]是基于联合树的数据发布算法, NoPrivacy是HMPrivBayes不添加噪声扰动的数据发布情况.

第1个实验是为了验证HMPrivBayes算法的安全性, 比较在不同记录数量下, 敏感属性隐私泄露的可能性. 在Adult数据集原有的45222条记录的基础上, 随机产生54778条记录, 生成包含100000条记录的数据集, 并将salary作为敏感属性. 由于隐私预算 $ \varepsilon $ 不是该实验关心的变量, 故将 $ \varepsilon $ 固定为0.2. 实验结果如图4所示, 从图中可以看出, 随着记录数的增加隐私泄露概率逐渐下降, 即攻击者根据其他属性信息推断出salary属性值的概率逐渐下降, 而且HMPrivBayes算法安全性高于PrivBayes算法和PrivSCBN算法. 这是因为, HMPrivBayes算法根据属性敏感性决定隐私预算分配大小, 能对多属性数据发布提供更安全的隐私保护.

第2个实验是对HMPrivBayes算法数据性能的分析, 图5(a)–图5(d)分别对比了在不同 $ \varepsilon $ 取值下, 算法HMPrivBayes、PrivSCBN、PrivBayes、Jtree的合成数据集的边际分布与原始数据集边际分布之间AVD的变化. 图5(e)–图5(f)显示了算法HMPrivBayes、PrivSCBN、PrivBayes、Jtree的合成数据集训练2个分类器的误分类率在不同 $ \varepsilon $ 取值下的变化趋势.

可以看出, 对于NoPrivacy, 边际分布之间的AVD和分类器的误分类率均与隐私预算 $ \varepsilon $ 的取值无关, 且NoPrivacy的性能均优于其他方法的性能. 随着隐私预算 $ \varepsilon $ 取值的增大, 隐私保护强度下降, 合成数据的两项指标越来越接近NoPrivacy的情况, 这符合差分隐私的规律. 在多数情况下, HMPrivBayes的性能均优于PrivSCBN、PrivBayes、Jtree的性能, 仅当隐私预算 $ \varepsilon $ 足够大时, HMPrivBayes与PrivSCBN性能趋于接近. 这说明本文提出的各种贝叶斯网络改进策略以及异构属性发布策略是有效的.

第3个实验是对HMPrivBayes算法计算效率的分析, 比较在贝叶斯网络不同最大入度数 $ l $ 下, 算法的整体运行时间. 由于隐私预算 $ \varepsilon $ 不是该实验关心的变量, 故将 $ \varepsilon $ 固定为0.2. 实验结果如图6所示, 随着最大入度数 $ l $ 的增加, 整体运行时间大幅上升. 比较图6(a)–图6(b)可以看出, 随着属性数目的增加, 算法整体运行时间也大幅增加. 不过, HMPrivBayes的运行时间远低于PrivBayes算法, 而且属性越多, 两者运行时间的差距越大, 这说明HMPrivBayes的效率得到了较好的提升. 效率的提升一方面在于, HMPrivBayes利用聚类算法分割属性集, 缩减了单个贝叶斯网络的节点空间; 另一方面在于, 借助属性关联强度, 缩减了候选属性对集合.

5 结束语

针对差分隐私异构多属性数据发布问题, 本文提出了一种基于属性分割的异构多属性数据差分隐私发布方法HMPrivBayes. 与已有多属性数据发布算法不同的是, HMPrivBayes基于属性敏感性差异给予属性数据相对应的隐私保护强度, 避免了多属性数据隐私保护不均匀的问题, 进而提高数据可用性. 与此同时, 该方法通过引入属性分割、改进贝叶斯构建过程等都实现了算法整体计算效率的提升. 在不破坏属性关联的前提下, 以属性归一化风险熵为权重分配隐私预算, 实现异构多属性数据发布. 理论证明, HMPrivBayes满足 $ \varepsilon $ -差分隐私. 实验结果表明, HMPrivBayes方法在提升算法整体计算效率的基础上, 保证了数据发布的可用性在未来的研究中, 我们将考虑基于差分隐私的分布式异构多属性数据发布, 即如何在多方设置中实现异构多属性数据发布.