0 引言

各种组织如政府部门和卫生保健系统等，经常需要与第三方共享所收集的数据，例如人口普查数据、医疗记录或基因数据等，以便进行一些具体的数据分析^[1]。然而，直接发布原始数据可能会导致隐私泄露，具有一定的潜在风险^[2]。特别地，当大量医疗、金融数据等广泛应用于数据挖掘时，这些高维数据中的敏感信息泄露风险同样在逐步加大^[3]。差分隐私是一种严格界定隐私强度和数据效用的隐私保护方法，能够为数据安全和数据可用性提供完整的理论保障^[4]。目前，已经提出了一系列用于差分隐私低维数据发布的技术，然而这些技术并不能有效地处理高维数据的发布，现有的解决方案需要注入噪声，这使得发布的数据几乎不可用^[5]。事实上，所有这些方案都受到维度诅咒的影响，它们既不能实现合理的扩展性，也不能实现理想的实用性^[6]。

为了应对这些挑战，一种方法是通过概率图模型学习一组低维条件概率分布，并通过贝叶斯网络的链式法则来逼近联合分布。Zhang等^[7]提出经典的PrivBayes方法，通过应用带有互信息替代函数的指数机制迭代地学习贝叶斯网络中属性的父集。之后，一些改进算法相继被提出。例如，王良等^[8]提出加权PrivBayes方法，该方法考虑了属性字段属性值的多样性，对贝叶斯网络中的节点增加权重值，优化选择属性字段加入噪声时的顺序并服从拉普拉斯分布，以此来构建更好的贝叶斯网络。Lan等^[9]提出以谱聚类为基础的PrivSCBN算法，通过对属性的分类来达到对数据集的划分，从而得到较低维度的子集，再分别为每个子集快速构建贝叶斯网络，在一定程度上降低了算法的复杂度和计算量。同样基于PrivBayes方法，Cheng等^[10]提出一种无重叠覆盖设计方法DP-SUBN，用于生成给定属性集的所有2-way边缘表，以提高贝叶斯网络的适应度，降低通信成本。此外，Chen等^[11]提出Jtree算法，对属性相关性进行了系统的探索，然后在联合树算法的推理基础上近似得到联合分布，同时最小化所产生的误差。张啸剑等^[12]在Jtree方法的基础上提出PrivHD方法，通过高通滤波技术来加速Markov网络的构建，然后利用最大生成树算法来构建更好的联合树。Tang等^[13]提出DPLT算法，通过构造隐树模型来近似原始数据集的联合概率分布，利用少数隐变量来度量多数显变量之间的关联强度，明显降低了通信开销。

另一类解决方案包括主成分分析、随机线性投影、分组截断等，其背后的思想是建立具有较小尺寸的原始高维数据集的低维概要。通过在差分隐私下发布噪声概要，这些机制可以降低满足数据集差分隐私所需的噪声大小，保持良好的利用率。Li等^[14]在主成分分析优化的基础上，设计属性分级保护策略来满足个性化的差分隐私保护。Xu等^[15]将高维数据集投影到随机选择的低维子空间，以保持成对的L₂距离和相关的用户分割，从而将噪声注入的幅度降至最低。Wang等^[16]将截断与分组技术相结合，对高维数据中列计数进行发布，有效地提高了数据发布的精度。本文针对高维数据发布问题，提出一种基于聚类和压缩感知的差分隐私高维数据发布算法PrivCACS。该算法分开处理属性集，利用差分隐私压缩感知降维技术将高维数据集映射至低维子空间，在以较小的隐私预算提供预期隐私保障的同时减少了噪声的注入。

1 基本概念

定义1   拉普拉斯机制。拉普拉斯机制适用于输出为实数的分析，噪声来自概率密度函数为$p(x \mid \lambda)=\frac{1}{2 \lambda} \mathrm{e}^{-\frac{|x|}{\lambda}}$的拉普拉斯分布，其中λ由全局敏感度GS(f)和期望的隐私级别ε共同决定。在ε-差分隐私的条件下，函数f: D→ R^d在任意域D上，有

$ A(D)=f(D)+ Laplace (G S(f) / \varepsilon)。$

(1)

定义2  属性敏感度。将原始数据集中的连续属性作离散化处理后，根据所求得的各离散属性的熵值以及对应的最大离散熵，将属性敏感度定义为

$ A S_i=\frac{H_{\max }\left(a_i\right)-H\left(a_i\right)}{H_{\max }\left(a_i\right)} 。$

(2)

定义3  互信息。为选择出与敏感属性具有强依赖关系的非敏感属性，此处属性关联度以属性间的互信息计算，定义为

$ I\left(a_i, a_j\right)=\sum\limits_{b=1}^{\left|\mathit{\Omega} _i\right|} \sum\limits_{c=1}^{\left|\mathit{\Omega} _j\right|} p_{b c} \log \frac{p_{b c}}{p_b p_c} 。$

(3)

定义4  压缩感知。压缩感知的一个重要前提是数据为稀疏的或可压缩的，为了克服这一障碍，压缩感知先通过稀疏表示将原始数据转换为稀疏数据，稀疏表示是一种从字典基上寻找较少向量来表示原始数据全部信息的操作。任意给定数据集D∈ R^d×n的稀疏表示为

$ D=\boldsymbol{\eta} \boldsymbol{\xi}, \text{s. t.} \left\|\boldsymbol{\xi}_i\right\| \leqslant k, i \in[1, n] 。$

(4)

定义5  受限等距性(restricted isometry property，RIP)。在给定受限等距参数μ_k的情况下，对于任何稀疏数据集，感知矩阵和稀疏系数应满足：

$ \begin{aligned} & \left(1-\mu_k\right)\|\boldsymbol{\xi}\|_2^2 \leqslant\|\boldsymbol{\pi} \boldsymbol{\xi}\|_2^2 \leqslant\left(1+\mu_k\right)\|\boldsymbol{\xi}\|_2^2 \\ & \mu_k \in(0, 1)。\end{aligned} $

(5)

2 PrivCACS算法

已有研究中高维数据集的发布方法总是聚焦于整体数据集，但实际上部分数据集并不会造成隐私泄露。因此，在数据发布前对数据集进行预处理，将非敏感数据集从整体中分割出来，并且着眼于敏感数据集进行差分隐私扰动，可以达到对不同类型数据集独立处理的目的，同时降低所需扰动数据集的维度，有利于减少隐私预算的分配次数。基于此，PrivCACS算法流程如图 1所示。

PrivCACS算法的主要思想是：考虑到高维数据属性间的关联性较为普遍，非敏感属性通过推理攻击可造成敏感属性的信息泄露，提出一种基于属性敏感度的聚类算法，在属性敏感度和属性关联度的基础上通过聚类获得不同的数据子集D₁和D₂。因为非敏感数据集D₁不会泄露敏感信息，所以不作隐私保护处理；将敏感数据集D₂从高维空间投影至低维子空间，这样可以最小化地增加噪声量，以此来最大限度地提高数据效用，同时保证发布数据的隐私。

2.1 基于属性敏感度的聚类(ASC)算法

ASC算法是基于属性信息熵量化及聚类分析的属性识别，其中也考虑了属性间的关联关系作为划分依据。通过ASC算法，可将原始属性集划分为两簇，即非敏感属性集C₁和敏感属性集C₂，然后根据这些属性子集将原始数据集分割为两个互不相交的数据子集D₁和D₂。ASC算法的具体步骤描述如下。

算法1   ASC算法

输入：属性集a_i(i=1, 2，…，d)，簇k=2。

输出：非敏感属性NSA构成的簇C₁，敏感属性SA构成的簇C₂。

1.计算属性敏感度$A S_i=\frac{H_{\max }\left(a_i\right)-H\left(a_i\right)}{H_{\max }\left(a_i\right)}$；

2.令C_k=∅，k=1, 2；

3.for each AS_i={AS₁, AS₂, …, AS_d}

4. 随机选定2个聚类中心{AS_u, AS_v}；

5. repeat

6. 计算其余属性敏感度数据点到质心间的曼哈顿距离d，将{AS₁, AS₂, …, AS_d}划分到相应的簇中；

7. 重新计算新的质心$A S^{\prime}=\frac{1}{\left|C_i\right|} \sum\limits_{A S_i \in C_i} A S_i$，更新两个质心；

8. until质心不再发生变化

9.end for

10.簇C′ ₁={NSA₁, NSA₂, …，NSA_p}，C′ ₂={SA₁, SA₂, …，SA_q}；

11.for each SA in C′ ₁

12. for each NSA in C′ ₂

13.   计算SA和NSA之间的互信息I(SA, NSA)；

14.    将属性关联度从大到小排列，输出最大属性关联度所对应的NSA，并加至C₂中；

15. end for

16.end for

17.输出非敏感属性集构成的簇C₁和敏感属性集构成的簇C₂。

2.2 差分隐私压缩感知(DPCS)算法

压缩感知实现高维数据子集D₂的稀疏表示，通过字典基η将D₂映射到另一个矩阵ξ。如果字典基是正交的，则ξ中的每个项可以看作是D₂中项的线性组合，并且可以通过线性逆运算从ξ中无损地获得D₂。反之，如果字典基是非正交的，那么ξ中的每个项都可以看作是D₂中项的随机仿射组合，而D₂可以通过贪婪算法从ξ中近似地获得。ξ中的项是稀疏系数，通过测量矩阵φ将ξ投影到观测矩阵I中，将I中的项定义为观测系数。DPCS算法的具体步骤描述如下。

算法2  DPCS算法

输入：原始数据集D_2r×n，隐私预算ε，字典基η_r×r，测量矩阵φ_l×r。

输出：合成数据集D_2r×n^*。

1.通过字典基η_r×r计算D₂=ηξ，得到稀疏表示矩阵ξ_r×n;

2.利用测量矩阵φ_l×r，将稀疏表示ξ_r×n映射到观测矩阵I_l×n(l≪r)中；

3.基于隐私预算ε，在I中加入拉普拉斯噪声lap($\sqrt{l}$ /ε)，获得含有噪声版本的I_l×n^*；

4.通过改进正交匹配追踪算法从I_l×n^*中重构出ξ_r×n^*；

5.计算D₂^*=ηξ^*；

6.返回D_2r×n^*。

2.3 改进正交匹配追踪(IMOMP)算法

IMOMP算法将I^*转换为含噪数据集D₂^*，并将其作为输出返回。由于重构步骤仅仅依赖于I^*，从而确保IMOMP算法不会泄露任何关于D₂的信息。IMOMP算法的具体步骤描述如下。

算法3   IMOMP算法

输入：加噪观测矩阵I_l×n^*，感知矩阵π_l×r，残差h=0，索引集合S=∅。

输出：加噪稀疏表示ξ_r×n^*。

1.for each i in n

2.for each j in l

3.   计算内积p=π^T×h；

4.   投影矩阵的索引S[j]=arg max(p)；

5.   计算最小二乘解z=arg min ‖ I^*[: , i]-π[: , S]z ‖ ₂；

6.   更新残差h=I^*[: , i]-π[: , S]z；

7.   w[S]=(π[: , S])^-1×π[: , S]z；

8.end for

9.return ξ^*[: , i]=w

10.end for

3 可用性与隐私性证明 3.1 数据集可用性证明

噪声中的每个n[i]都存在着lap($\sqrt{l}$ /ε)的分布且‖ n ‖ ₂≤θ，有‖ ξ－ξ^* ‖ ₂≤c ‖ ξ－ξ_k ‖ ₁/ $\sqrt{k}$ + c′θ。其中，c和c′为常数；ξ_k表示对于n列的稀疏表示矩阵，其每一列中的r-k个绝对值最小的数替换成零值。随机变量Y定义为：$Y=\sum\limits_{i=1}^l n[i]^2$。通过计算Y的均值及方差可知：E[Y]=2l²/ε², Var[Y]=20l³/ε⁴。再由切比雪夫不等式可得：$P\left(|Y| \leqslant 2 l / \varepsilon^2(l+\sqrt{2 l / \delta})\right) \geqslant 1-\delta$。事实上，有$\|n\|_2=\sqrt{Y}$，且在概率至少为1－δ的情况下，有‖ n ‖ ₂=O(l/(εδ^1/4))。对于给定的量级M以及可压缩矩阵$\boldsymbol{\xi} \in \bf{R}^{r \times n}$，对某个常数p∈(0, 1)，存在$\left\|\boldsymbol{\xi}-\boldsymbol{\xi}_k\right\|_1 \leqslant c_p \cdot M \cdot k^{1-\frac{1}{p}}$，即$\left\|D_2-D_2^*\right\|_2=\| \boldsymbol{\xi}-\boldsymbol{\xi}^* \|_2=O\left(k^{\frac{1}{2}-\frac{1}{p}}+\theta\right)$。当概率至少为1－exp(-l)，且感知矩阵π∈ R^l×r满足RIP条件的前提下，在很高的概率下由布尔不等式可得：‖ D₂－D₂^* ‖ ₂=O(log(r)/ε)，经过压缩采样后恢复出的数据集D₂^*具有较高的还原度。

3.2 算法隐私性证明

敏感数据集D₂降维后的差分隐私加噪以及最终的恢复过程满足ε-差分隐私。压缩采样过程可以表征为随机投影过程SP，即对于数据子集D₂，有SP(D₂)=I=φD₂。随机测量矩阵φ∈ R^{$\sqrt{l}$×r}可选自概率分布如高斯分布和伯努利分布等，或矩阵如傅立叶和哈达玛矩阵等。本文选取的概率分布为伯努利分布，其具体表达式为：P(φ(i, j)=±1/ $\sqrt{l}$)=1/2，准确地说，φ中的每一项以1/2的概率等于1/ $\sqrt{l}$，以1/2的概率等于－1/ $\sqrt{l}$，那么SP的全局敏感度为Δ_SP= $\sqrt{l}$。

在压缩感知机制中，将SP的敏感度视为分布参数中所选择的向量个数，压缩感知过程中的拉普拉斯机制符合差分隐私要求。此外，后续的数据重建是确定性的，不涉及任何概率计算。因此，整个压缩感知过程都满足ε-差分隐私。

4 实验评估 4.1 实验配置和数据集

实验环境是Windows10操作系统，Intel(R)Core(TM)i5-1135G7，CPU(2.40 GHz)，16 GB内存。所涉及算法代码用Python和Matlab语言实现。实验数据集NLTCS、Adult、TIC均应用于高维数据的发布场景中。其中，NLTCS源自于美国护理调查中心，包含21 574名残疾人在不同时间段的日常活动；Adult为美国人口普查数据，包括45 222条有效个人信息；TIC为Coil网站数据分析竞赛所用数据集，包括某保险公司客户购买产品信息以及客户社交信息在内的98 220条信息。更多的数据集描述见表 1。

针对上述3种高维数据集，用SVM分类来度量PrivCACS、PrivBayes^[7]、Jtree^[11]算法发布高维数据时的准确性，即SVM分类的准确率可评估生成数据集的可用性大小。在每个生成数据集上分别训练两个SVM分类器，在每个SVM分类器中取一个属性作为分类结果，并用其他属性作为特征来训练SVM分类器，从而对该属性的取值进行预测。对于每个分类任务，用生成数据集中80%的数据作为训练集，剩下20%的数据作为测试集。进一步地，采用错误分类率作为衡量标准。

在NLTCS数据集中，依据某人(a)是否能够管理资金(money)，(b)是否能够旅游(traveling)，作为分类属性进行预测。在Adult数据集中，依据某人(c)是否年薪(salary)大于5万，(d)是否拥有大专学历(education)，作为分类属性进行预测。在TIC数据集中，依据某人(e)是否有车(car)，(f)是否有房(house)，作为分类属性进行预测。由于测试算法具有随机性，将两种分析任务均运行10次，将每次输出数据的平均值作为最终的实验结果。

4.2 聚类结果分析

图 2展示了不同数据集的属性聚类结果。在数据集NLTCS中，敏感属性集为Y13、Y11、Y10、Y9、Y7、Y6、Y5、Y3、Y2、Y1，非敏感属性集为Y16、Y15、Y14、Y12、Y8、Y4。计算出敏感属性和非敏感属性间对应的属性关联度后，将Y14、Y12、Y4加入敏感属性集中，更新后得到新的属性集合。在数据集Adult中，敏感属性集为age，fnlwgt，occupation，relationship，sex，hour-per-week，income，非敏感属性集为workclass，education，education-num，marital-status，race，capital-gain，capital-loss，native country。只考虑与敏感属性关联度较高的非敏感属性，将workclass，education，education-num，marital-status加至敏感属性集中。在数据集TIC中，计算出各属性的敏感度后经过聚类，敏感属性有MOSTYPE、MOSHOOFD、MGODPR、MRELGE、MFWEKIND、MOPLLAAG、MBERMIDD、MSKC、MHHUUR、MHKOOP等；非敏感属性有MAANTHUI、MINK123M、PWABEDR、PWALAND、PBESAUT、PMOTSCO、PVRAAUT、PAANHANG、PTRACTOR、PWERKT等。根据敏感属性和非敏感属性间的关联度大小，将非敏感属性MAANTHUI、MINK123M添加到敏感属性集中。可以看出，相较于图 2(a)，图 2(b)中敏感属性个数有明显增多，这是由于在未考虑属性间的关联度前，与敏感属性产生高关联度的某些非敏感属性同样会造成额外的信息泄露，所以应用互信息作为属性关联度，挑选出与每个敏感属性具有强依赖度的非敏感属性，并将其等价地当作敏感属性。聚类完成后，原始数据集被划分为两类，形成初次降维，但是敏感属性值构成的数据子集依然属于高维度范畴。因此，采用特定的降维方法将其压缩成低维矩阵形式。

4.3 SVM分类结果分析

图 3展示了不同数据集在隐私预算逐渐变化下的SVM分类结果。可以看出，PrivCACS算法的总体表现要好于PrivBayes和Jtree算法，尤其在隐私预算较低的条件下，PrivCACS方法的错误分类率明显较低。这是由于使用贝叶斯网络和联合树算法都不可避免地受制于概率图模型缺陷的影响，即概率图结构的学习会随着属性节点的提高而使得噪声量急剧增加，从而降低数据效用。而PrivCACS算法采用压缩感知的降维方法，将高维数据映射至低维子空间，通过在子空间对数据加噪，明显降低了噪声量和空间成本，从而能够当隐私预算较低时，在SVM分类上体现出较大的优势。

PrivCACS算法在绝大多数情况下优于PrivBayes和Jtree算法。这是因为本文从属性划分的角度出发，同时考虑属性之间的关联性，敏感属性和部分能够推理出敏感属性的非敏感属性共同构成泄露隐私信息的敏感属性集，有针对性地对敏感属性对应的数据子集进行拉普拉斯扰动处理，而非敏感属性对应的数据子集并未受到任何噪声干扰，所以最终所得合成数据集在SVM分类中的准确率较高。这也表明PrivCACS方法在有效保证数据隐私信息的同时，其SVM分类精确性有显著提高，增强了数据发布的效用性。

5 小结

在高维数据发布过程中，由于数据维度和值域的增加，数据发布空间以指数级别增长，导致数据可用性差，为此提出一种满足差分隐私保护的高维数据发布算法PrivCACS，通过对属性集加以聚类，达到对原始数据集的划分。高维数据子集D₂采用压缩感知降维，在低维空间中引入拉普拉斯机制，对敏感信息进行加扰，在减少噪声量的同时降低空间成本，改进正交匹配追踪算法还原后的合成数据集D₂^*与D₂大概率接近。实验结果表明，相比于PrivBayes和Jtree算法，PrivCACS算法使最终数据在满足隐私保护要求的同时，数据的可用性与准确性有较大的提升。