基于属性分割的高维二值数据差分隐私发布

洪金鑫1 吴英杰1 蔡剑平2 孙 岚1

1(福州大学数学与计算机科学学院 福州 350108)2(厦门华厦学院信息与智能机电工程学院 福建厦门 361024)

摘 要 通常随着数据集属性维度的增加,高维数据的差分隐私发布方法所需的时间成本和产生的噪声干扰也会随之增大,尤其是对于高维二值数据很容易被过大的噪声所覆盖.因此,针对高维二值数据的隐私发布问题,提出了一种高效且低噪的发布方法PrivSCBN(differentially private spectral clustering Bayesian network).首先,该方法基于Jaccard距离,使用满足差分隐私的谱聚类算法来划分属性集,然后根据划分的结果来进一步分割原始数据集,从而实现数据的降维.其次,该方法基于动态规划思想并结合指数机制,使用满足差分隐私的贝叶斯网络快速构建算法来为每个分割后的子集构建贝叶斯网络.最后,该方法利用条件概率在二值数据上的取值特点,对从贝叶斯网络中提取的条件分布进行加噪,并通过控制贝叶斯网络的最大入度数来减少其产生的噪声大小.通过在3个真实高维二值数据集上的实验,验证了PrivSCBN方法的高效性与可用性.

关键词 差分隐私;高维二值数据发布;贝叶斯网络;属性划分;动态规划;条件分布

随着大数据产业的日趋成熟,在日常生活中有越来越多的数据被采集.通常这些数据蕴含着大量的隐私信息,例如交通数据中的个人移动轨迹、医疗数据中的病人患病记录等.如果直接使用这些数据很有可能会导致隐私的泄露.因此在使用时需要采取一些措施来保证数据的隐私安全.

差分隐私[1-5]是一种严格可证的隐私保护技术,它通过向数据注入满足特定分布的噪声干扰,使攻击者难以对特定的隐私数据进行精确的计算.经过扰动后的数据仍然保留着原始的统计学特征,但攻击者无法重构出真实的原始数据.这样便能够在保证数据安全的前提下,提高数据共享和使用的效率.

高维数据的隐私发布问题一直以来都是差分隐私领域里的一个研究热点与难点问题.如何在有效地保护数据中隐私信息的同时保证数据的可用性是该问题的研究重点.当前已有许多基于差分隐私的高维数据发布方法,这些方法大体上可以分成2类:

1)通过对高维数据进行降维来减小扰动原始数据时产生的噪声大小,主要包括主成分分析[6-9]、随机投影[10-13]、仿射变换[14]、截断分组[15-16]、PriView视图[17]等方法.

2)通过构建数据集的概率图模型来计算数据属性间的概率分布,然后对概率分布进行加噪,并用来生成合成数据发布,以此来避免直接扰动原始数据时产生的巨大噪声干扰.这类方法主要有朴素贝叶斯分类器[18]、贝叶斯网络[19-25]、Markov网络[26-28]等.

第1类方法(降维方法)是一个比较简单有效的方法,但是该类方法无法发布一个完整的高维数据集,这也限制了它的作用范围.一般这类方法主要用于回答一些查询操作或者作为数据挖掘、机器学习等领域的预处理方式.

第2类方法(概率图模型方法)通过生成合成数据的方式,能够发布一个完整的高维数据集,这使得它的适用范围更加广泛.

虽然现有的概率图模型方法在一定程度上能够解决高维数据的隐私发布问题,但当它应用于实际场景时,这些方法仍然存在着一些问题:

第一,这些方法都过于统一地认为属性间是相互独立或是相互关联的.其实对于不同的数据集来说,它们属性间的关联性是不一样的,有的属性间是具有联系的,有的属性间是相互独立的.为了能够让构建的概率图模型更符合真实的分布规律,就不能对这些关联性不同的属性一概而论.而是需要找到一种能够识别属性间不同关联性的方法,并以此来将不相干的属性分开处理.

第二,实现这些方法所需的时间复杂度普遍偏高.尤其是在构建概率图模型的过程中,大部分方法都使用了指数级时间复杂度的算法.虽然理论上这些方法都可适用于任意维度的高维数据,但是在实际使用时由于时间因素的影响,大多数的方法都只能处理到中低维数据,这明显无法满足实际应用的需求.

第三,这些方法中很少有针对高维二值数据的方法,以致于忽视了高维二值数据中存在的可以利用的性质,例如利用条件概率在二值数据上的取值特点.导致在对概率分布加噪时很容易出现概率值大规模失真问题,使得后续由该概率分布生成的合成数据的精度下降.

为解决上述3个问题,本文提出了PrivSCBN(differentially private spectral clustering Bayesian network)方法.本文的主要贡献包括4个方面:

1) 为了解决高维二值数据的差分隐私发布问题,本文提出了一种满足差分隐私的高维二值数据发布方法PrivSCBN.该方法由3个子算法组成,每个子算法都满足差分隐私的定义.然后基于每个子算法的噪声公式,设计了一种策略来分配隐私预算ε.最后,通过实验验证了PrivSCBN方法在时间性能和发布精度上都要优于现有的发布方法.

2) 为了解决不同属性间关联性不一致的问题.本文针对高维二值数据,设计了一种基于Jaccard距离的属性间关联程度衡量指标,并从理论论证了相比于常用的互信息,Jaccard距离在二值数据属性上拥有更低的全局敏感度和更高的准确度.然后基于该衡量指标,本文提出了一种满足差分隐私的谱聚类(differentially private spectral clustering, DPSC)算法来对数据属性进行合理的划分,然后根据划分结果进一步分割原始数据集,以此达到独立属性分开处理和数据降维的双重目的.

3) 为了解决概率图模型方法运行的时间消耗过大的问题.本文针对贝叶斯网络模型方法,设计了一种算法来为当前待选结点求解其最佳父结点集.然后基于该算法结合指数机制,提出了一种满足差分隐私的贝叶斯网络快速构建算法FGB(fast greedy Bayes)来构建贝叶斯网络.相较于传统的GreedyBayes算法所需的时间复杂度,FBN算法只需要O(nm2d2)的时间就能够构建出一个较优的贝叶斯网络,并且所构建的贝叶斯网络是受差分隐私保护的.

4) 为了解决概率分布加噪时容易出现的概率值失真问题.本文利用贝叶斯网络最大入度数的限制和条件概率在二值数据上的取值特点,提出了一种概率分布加噪算法BNC(binary noisy conditionals)来为每个从贝叶斯网络中提取的概率分布进行加噪,在一定程度上减少了出现概率值失真的问题.

1 相关工作

目前,概率图模型方法已取得了一些研究成果.

Qardaji等人[17]针对高维二值数据的隐私保护问题提出了PriView方法,该方法假设所有属性都是相互独立,通过构建一组带噪声的View视图来回答用户的α-way查询.Zhang等人[19-20]针对高维数据隐私发布问题提出了PrivBayes方法,该方法认为属性间都是相互关联的,通过贪心算法GreedyBayes来构建贝叶斯网络,然后利用贝叶斯网络和拉普拉斯机制计算出属性间带噪声的条件分布,并通过贝叶斯网络的近似推理来计算出所有属性的联合分布,最后基于这个联合分布来生成合成数据发布.在PrivBayes方法的基础上,加权PrivBayes[21]、平滑PrivBayes[22]、PrivBayes_Hierarchical[23]等一系列方法被相继被提出.王良等人[21]提出了加权Priv-Bayes方法,该方法认为不同属性的敏感程度是不一样的,并不能一概而论,因此该方法通过为每个属性分配一个权值,然后在构建贝叶斯网络的过程中优先选择权值高的属性结点,以此来构建更好的贝叶斯网络.Li等人[22]提出了平滑PrivBayes方法,该法方法引入了差分隐私的平滑敏感度机制,使其能够在牺牲部分隐私保护程度的情况下减少产生的噪声大小,从而提高联合分布的精度.郝志峰等人[23]提出了PrivBayes_Hierarchical方法,该方法利用语义树来对数据属性的语义层次关系进行抽象,然后在构建贝叶斯网络的过程中考虑父结点的语义层级对子结点的影响,从而能够平衡数据的可用性与安全性.

除了基于贝叶斯网络的有向图模型方法,还有基于Markov网络的无向图模型方法.Chen等人[26]提出了Jtree方法,该方法先是使用基于稀疏向量的采样技术来探索属性间的关系,然后基于这些关系来构建Markov网络,接着将该网络分割成若干个完全团,并基于这些完全团通过联合树算法和拉普拉斯机制计算出属性间带噪声的联合分布.张啸剑等人[27]在Jtree方法的基础之上提出了PrivHD方法,该方法通过高通滤波技术来加速Markov网络的构建,然后利用最大生成树算法来构建更好的联合树.

从这些分析中可以看出,现有的概率图模型方法主要集中在研究如何更好更快地构建概率图模型、减少产生的噪声干扰、获得更准确的概率分布值,从而生成更高精度的合成数据.但是这些方法仍然存在着时间复杂度过高、没有考虑属性间不同程度的关联性、注入的噪声过大导致概率值失真等问题.为此本文提出了PrivSCBN方法来进行解决.

2 理论与定义

2.1 差分隐私

定义1. ε-差分隐私[1].设兄弟数据集DD′,它们彼此相差1条记录.给定1个随机算法A,若A满足ε-差分隐私,则有

Pr[A(D)=O]≤exp(εPr[A(D′)=O],

(1)

其中,ε表示隐私预算,预算越小则隐私的保护程度就越高.Pr[A(D)=O],Pr[A(D′)=O]分别表示算法A在数据集DD′上输出为O的概率.

实现差分隐私的机制主要有拉普拉斯机制[2]和指数机制[3].这2种机制产生的噪声大小与查询函数的全局敏感度有关.

定义2. 全局敏感度[2].设查询函数f:Dn,其全局敏感度定义为

(2)

其中,表示p-范数,比较常用1-范数.一般来说全局敏感度越大,f受影响的程度就越强,需要添加的噪声也就越多.

定理1. 拉普拉斯机制[2].设查询函数f:Dn,给定1个随机算法A,若A满足ε-差分隐私,则有

A(D)=f(D)+Lapf/ε),

(3)

其中,Lapf/ε)表示满足拉普拉斯分布的噪声变量.隐私预算ε越大或全局敏感度Δf越小,产生的噪声就越小.

定理2. 指数机制[3].设评分函数u(x)表示输出结果为x的评分,给定一个随机算法A,若A满足ε-差分隐私,则有

A(D)=

(4)

其中,Δu表示评分函数u(x)的全局敏感度.输出Oi的评分越高,则被选中的概率就越大.

此外,在设计和证明满足差分隐私的算法过程中,需要用到2条重要的差分隐私组合性质.

性质1. 串行组合性质[4].给定数据集DD上1组满足差分隐私的算法A1(D),A2(D),…,Am(D),其中算法Ai(D)满足εi-差分隐私,且任意2个算法的随机过程相互独立.那么这些算法的组合算法A满足差分隐私.

性质2. 并行组合性质[4].给定数据集D,将D分割成m个互不相交的子集D={D1,D2,…,Dm}.设算法A1(D1),A2(D2),…,Am(Dm)均各自满足ε-差分隐私,并且任意2个算法的随机过程相互独立.那么这些算法的组合算法A也满足ε-差分隐私.

2.2 谱聚类

谱聚类(spectral clustering)[28]是一种基于图论的分割式聚类方法,通常能够收敛于全局最优解.它的作用机理是先将数据集映射成一张带权无向图,然后通过对图中的结点进行分割,使得子图内部的结点尽量相似,子图外部的结点尽量不同.

标准的谱聚类算法实现过程如算法1所示:

算法1. 谱聚类算法.

输入:数据集D={x1,x2,…,xn}、类簇个数k、尺度参数σ;

输出:分割结果集C={C1,C2,…,Ck}.

① 使用式(5)计算n×n的距离矩阵W:

(5)

② 使用式(6)计算n×n的相似度矩阵A:

(6)

③ 使用式(7)计算n×n的度矩阵B:

(7)

④ 计算拉普拉斯矩阵L=B-1/2(B-A) B-1/2;

⑤ 计算L的特征值,然后从小到大排序,取前k个特征值计算其特征向量u1,u2,…,uk;

⑥ 将k个特征向量(列向量)组成n×k的矩阵U=(u1,u2,…,uk),令yi为矩阵U的第i行向量,并对其进行单位化yi=yi/|yi|;

⑦ 使用k-means聚类算法对新样本点Y={y1,y2,…,ym}进行划分得到划分结果C;

⑧ return C.

算法1中的拉普拉斯矩阵L是对称的半正定矩阵,可以计算出n个非负实数的特征值和n个对应的特征向量.因此,该算法最终一定可以得到k个聚类的结果.

2.3 贝叶斯网络

贝叶斯网络(Bayesian network)是一种概率图模型,主要用来探索一组随机变量之间的关系.贝叶斯网络通常使用1张有向无环图来表示,图中结点代表随机变量、边代表随机变量之间的关系.

例如图1是1张拥有5个结点的贝叶斯网络图,该网络的最大入度数为3.

Fig. 1 Bayesian network of 5 nodes

图1 5个结点的贝叶斯网络

一般给定一组属性S={S1,S2,…,Sm},由条件概率的链式法则可得这组属性的联合分布为

Pr[S]=Pr[S1Pr[S2|S1]×…×Pr[Sm|S1,…,Sm-1],

(8)

通过贝叶斯网络可将该联合分布近似为

(9)

其中,Πi表示结点Si的父结点集.如果所构建的贝叶斯网络能够很好地表示属性间的关系,那么有因此,选择一个好的贝叶斯网络结构至关重要.

表1显示了图1中各个结点的父结点集:

Table 1 Parent Set of Each Node in Bayesian Network

表1 贝叶斯网络各结点的父集

结点父集S1∅S2{S1}S3{S1}S4{S1,S3}S5{S2,S3,S4}

利用式(9),可得该属性集的近似联合分布为

Pr[S2|S1]×…×Pr[S5|S2,S3,S4].

(10)

实际上越复杂的贝叶斯网络所蕴含的信息就越丰富,计算出来的联合分布也会越接近真实的分布规律.但由于时间因素的影响,通常在构建贝叶斯网络时会限制整个网络的最大入度数,以此来降低构建网络所需的时间成本.

2.4 互信息

互信息常用来表示1个变量由于已知另一个变量所能减少的不确定程度.互信息也可以用于衡量2个属性间的相互依赖程度.互信息越大,则属性间的相互依赖程度就越高.

定义3. 互信息.给定2个离散的随机变量X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym},它们间的互信息为

I(X,Y)=

(11)

其中,Pr[xi,yj]表示随机变量X,Y取值为xi,yj的联合分布.I(X,Y)→0时,有Pr[xi,yj]→Pr[xi]Pr[yj],即随机变量XY接近于相互独立.

2.5 Jaccard距离

Jaccard距离常用来表示2个集合间的差异程度.距离越小,集合间的差异程度就越小.

定义4. Jaccard距离.给定2个集合X,Y,它们之间的Jaccard距离为

(12)

Jaccard距离也可以用来表示同一数据集中2个二值属性间的差异程度.

假设给定2个二值属性X,Y,它们取值为X=1,Y=1的数据量为n11,取值为X=0,Y=1的数据量为n01,取值为X=1,Y=0的数据量为n10.那么这2个属性之间的Jaccard距离为

(13)

可以看出距离越小,属性间的关联程度就越高.

3 PrivSCBN算法

3.1 概 述

PrivSCBN算法的整体流程如图2所示:

Fig. 2 PrivSCBN algorithm flowchart

图2 PrivSCBN算法流程图

PrivSCBN算法的实现过程如算法2所示:

算法2. PrivSCBN算法.

输入:数据集D={x1,x2,…,xn}、属性集S={S1,S2,…,Sm}、类簇个数k、尺度参数σ、最大入度数d、隐私预算ε;

输出:合成数据集

① 计算a1=(m-1)/(n-1),a2=2m/(nk),a3=2m/(nk),并计算a=a1+a2+a3;

② 计算ε1=(a1/a)εε2=(a2/a)εε3=(a3/a)ε;

③ 求属性划分结果集C={C1,C2,…,Ck}←DPSC(D,S,k,σ,ε1);

④ 依据C分割原始数据集D={D1,D2,…,Dk};

⑤ 初始化

⑥ for i=1 to k do

⑦ 求贝叶斯网络

⑧ 求带噪条件分布

⑨ 使用计算的带噪声的联合分布,然后进行采样得到并将其加入

⑩ end for

PrivSCBN算法可以拆解成4个独立的步骤:

1) 通过DPSC算法将属性集S划分成k个属性子集C1,C2,…,Ck,然后根据这些子集将原始数据集D分割成k个互不相交的数据集子集D1,D2,…,Dk.

2) 通过FGB算法为每个数据集子集Di构建贝叶斯网络

3) 通过BNC算法从每个贝叶斯网络中提取条件分布并注入拉普拉斯噪声干扰,从而得到带噪声的条件分布

4) 通过带噪声的条件分布利用贝叶斯网络的近似推理求得的联合分布,然后基于该联合分布进行采样得到合成数据集最后,将所有合并成数据集进行发布.

在PrivSCBN算法中,子算法DPSC,FGB,BNC均会使用到原始数据集D.由性质1可知,要想使整个PrivSCBN算法满足ε-差分隐私,我们需要为这3个子算法分配隐私预算.根据本文后续的分析可知隐私预算ε1ε2ε3在使用时将分别对应这3个噪声分布.其中第1个和第3个使用了拉普拉斯机制,其优化的目标是使括号里面的值最小,而第2个使用的是指数机制,其优化的目标是使括号里面的值最大.对上述3个式子进行化简有

(14)

(15)

(16)

故可得隐私预算ε1ε2ε3的分配策略为ε1=(((m-1)/(n-1))/a)εε2=((2m/(nk))/a)εε3=((2m/(nk))/a)ε,而a=(m-1)/(n-1)+2m/(nk)+2m/(nk).

最后,说明PrivSCBN算法满足ε-差分隐私.由3.2~3.4节的最后一段满足差分隐私性质的说明可知,步骤③⑦⑧中的DPSC,FGB,BNC算法均各自满足ε1ε2ε3-差分隐私.虽然其中的FGB和BNC算法会被执行k次,但每次执行所使用的数据集Di之间是没有交集的.由性质2可知,它们仍然满足ε2ε3-差分隐私.并且除了上述的3个算法之外,PrivSCBN算法没有其他地方再涉及原始数据集D的使用.因此,由性质1可知,整个PrivSCBN算法满足ε=(ε1+ε2+ε3)-差分隐私.

3.2 差分隐私谱聚类算法

由于高维数据的来源非常广泛,其属性间的关系错综复杂,即有的属性间是具有联系的、有的属性间是相互独立的.一般在构建概率图模型时,是希望模型能够很好地反映出这些属性间的关系.但由于高维数据中可能存在着毫无因果关系的属性对,而如果将这些属性对放到一起来构建概率图模型,那么得到的模型将无法很好地反映真实的分布规律.因为,这时引入了一些全局无关的变量(属性),导致模型为这些无关的变量建立了有关的联系.举个例子,给定一个属性集S,满足下标奇偶性相同的属性间是具有联系的、奇偶性不同的属性间是相互独立的.如图3所示:

Fig. 3 Black and white node network diagram

图3 黑白结点网络图

从图3可以看出通过将黑白结点分开并分别构建网络图,可以消除图中所有错误的依赖关系.当然这是在能够将黑白结点完全区分开来的最理想条件下实现的,但在一般情况下是无法完全将它们区分开的.因此,如何找到一种较好的区分方法是本文研究的重点.为此本文提出了一种满足差分隐私的谱聚类算法DPSC来对数据集属性进行合理的划分.

考虑如何衡量属性间的关联程度,一个比较常用的方法是使用互信息来进行衡量.但是这在处理高维二值数据时可能遇到一个问题,那就是高维二值数据通常是稀疏型数据,其中存在大量同时取值为0的属性对.而在一般的高维二值数据中能够反映出客观规律的是同时取值为1的属性对.因此,如果使用互信息来作为衡量指标,那么会很容易得出所有属性都是具有联系的这种无效结论.而由式(13)可知Jaccard距离是不会考虑这种情况的,并且它也能很好地反映出2个属性间的差异程度.因此,DPSC算法采用Jaccard距离来作为属性间关联程度的衡量指标.

DPSC算法的实现过程如算法3所示:

算法3. DPSC算法.

输入:数据集D={x1,x2,…,xn}、属性集S={S1,S2,…,Sm}、类簇个数k、尺度参数σ、隐私预算ε1;

输出:属性划分结果C={C1,C2,…,Ck}.

① 使用式(17)计算m×m的距离矩阵W:

(17)

② 执行算法1的步骤②~⑥;

③ 使用k-means++聚类算法对新样本点Y={y1,y2,…,ym}进行划分得到划分结果C;

④ return C.

DPSC算法先将属性集S映射成一张带权无向图.图中以每个属性Si(1≤im)作为顶点,以属性间的关联程度作为边权,边权使用的是属性间的Jaccard距离进行度量.由于在计算边权时涉及到了原始数据集D的使用,为了保护数据中的隐私信息不被泄露,我们需要对计算结果进行扰动.这里使用拉普拉斯机制来进行扰动,扰动所产生的噪声大小与边权函数的全局敏感度有关.因此,我们需要先考虑Jaccard距离的全局敏感度大小.

定理3. Jaccard距离的全局敏感度为ΔJ=1/(n-1).

证明. 根据式(13),不失一般性地假设n11+n01+n10=n,并且令x=n11.考虑减少一条记录给dJ(X,Y)带来的影响,存在2种情况:

1) 减少的是X=1,Y=1的记录,根据式(2)有

(18)

求一阶导数得可知该函数是单调递减函数,则有ΔJ-=1/n;

2) 减少的是X=0,Y=1或X=1,Y=0的记录,同样由式(2)有

(19)

求一阶导数得可知该函数是单调递增函数,则有ΔJ-=1/(n-1).

同理,当增加一条记录时,有ΔJ+=1/(n-1)成立.

综上所述,Jaccard距离的全局敏感度为ΔJ=max(ΔJ-J+)=1/(n-1).

证毕.

实际上对于互信息,由Zhang等人[19]的论文可知,互信息在二值属性上的全局敏感度ΔI

(20)

很明显相对于Jaccard距离ΔJ=1/(n-1)的全局敏感度,互信息的全局敏感度要来得更大.根据式(3)可知相比于互信息,使用Jaccard距离产生的拉普拉斯噪声大小会更小.

在确定完边权的全局敏感度之后,DPSC算法会对每个边权值进行加噪,这个加噪过程会进行多次.由性质1可知每次加噪都需要分配一部分的隐私预算.因此需要先确定加噪的总次数,即构建距离矩阵W总共需要查询原始数据集D的次数.

W的定义可知,该矩阵是一个实对称矩阵,并且对角线上的数值均为0.因此计算出W实际上只需要计算m(m-1)/2个不同位置上的值即可.又因为每次查询D都可以同时计算出m/2个不同位置上的值.故我们一共只需要查询原始数据集Dm(m-1)/(2m/2)次.由性质1可知,我们需要

将隐私预算ε1分成m(m-1)/(2m/2)份.这里采取平均分配的方式.

综上所述,我们可以得到加入边权函数的拉普拉斯噪声大小为

(21)

此外DPSC算法为了能够进一步提升属性的聚类效果,我们将原本算法1步骤⑦使用的k-means聚类算法换成了k-means++算法.该算法在初始点的选择上更为合理,因此能够产生更好的聚类效果.

在聚类完成后,算法会根据得到的样本点Y的聚类情况,按照样本点y1对应属性S1,样本点y2对应属性S2,…,样本点ym对应属性Sm的对应规则,将每个属性分配到其所对应的样本点所在的类簇中,这样就完成了对数据属性的划分.

最后,说明一下DPSC算法满足ε1-差分隐私.算法在步骤①中向距离矩阵W注入了拉普拉斯噪声LapJ×m(m-1)/(2ε1m/2)).由定理1和性质1可知,该过程满足ε1-差分隐私.而在后续的步骤中,计算的所有矩阵和向量都直接或间接地使用到了W,并且也都没有再次涉及原始数据集D的使用.因此,整个DPSC算法满足ε1-差分隐私.

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

在现有的贝叶斯网络模型方法中,大多都是使用由Zhang等人[19]提出的GreedyBayes算法来构建贝叶斯网络.该算法基于贪心的思想,即通过枚举所有的情况,选择能够使整个贝叶斯网络的互信息量达到最大的网络结构进行构造.

GreedyBayes算法的实现过程如算法4所示:

算法4. GreedyBayes算法.

输入:数据集D={x1,x2,…,xn}、属性集S={S1,S2,…,Sm}、最大入度数d;

输出:贝叶斯网络

① 初始化

② 从属性集S中随机选取一个属性作为S1,将(S1,∅)加入S1加入顶点集V;

③ for i=2 to m do

④ 初始化集合Ω=∅;

⑤ 对每个SiS\V将(Si,Πi)加入Ω;

⑥ 从Ω中选取互信息最大的(Si,Πi)加入并将Si加入V;

⑦ end for

由于Zhang等人[19]在论文中没有给出该算法具体的时间复杂度公式,故本文先对GreedyBayes算法的时间复杂度进行论证.

定理4. GreedyBayes算法的时间复杂度为

证明. GreedyBayes算法的时间消耗主要集中在算法4的步骤③~⑦的for循环.for循环一共执行m-1次,每次都会产生个(Si,Πi)对.因此,这个过程总共产生的(Si,Πi)对数为

(22)

在最坏情况下,即d+2=(m+1)/2时,有

(23)

即时间复杂度上界只需要关注即可,因此枚举(Si,Πi)对所需的时间为

而对于每个(Si,Πi)对都需要计算其互信息大小,每次计算需要O(nd)的时间.故GreedyBayes算法的总时间复杂度为

证毕.

很明显由于时间复杂度的影响,GreedyBayes算法仅能适用于属性维度m较小或者贝叶斯网络最大入度数d很小的情况.

为了能够更直观地说明,我们以含有50个属性的数据集为例.当贝叶斯网络的最大入度数d分别为5,10,15,20,25时,GreedyBayes算法所需要枚举的(Si,Πi)对的个数如表2所示:

Table 2 Enumeration Number of GreedyBayes Algorithm

表2 GreedyBayes算法的枚举次数

dCd+2m+15≈1.16×10810≈1.59×101115≈1.48×101320≈1.56×101425≈2.30×1014

从表2中可以看出,假设计算机每秒可以计算1万个(Si,Πi)对的互信息.当最大入度数d=10时,就已经需要184天每天24 h的不间断处理才能完成.而当d=25时,就变得连计算机也无法解决,因为它一共需要728年零11天每天24 h的不间断处理时间才能完成任务.

为了能够“真正”地处理高维数据、构建更复杂的贝叶斯网络,本文提出了一种简洁高效的贝叶斯网络快速构建算法FGB.该算法只需要O(nm2d2)的时间就能够构建出一个完整的贝叶斯网络.

FGB算法的实现过程如算法5所示:

算法5. FGB算法.

输入:数据集子集Di={x1,x2,…,xn}、属性子集Ci={S1,S2,…,S|Ci|}、最大入度数d、隐私预算ε2;

输出:贝叶斯网络

① 初始化

② 从Ci中随机选择一个属性作为S1,将(S1,∅)加入S1加入顶点集V,令fa=S1;

③ for t=2 to |Ci| do

④ 初始化集合Ω=∅;

⑤ 对每个SjCi\VΠjDPBestParent(Di,Sj,fa,min(t-1,d)),将(Sj,Πj)加入Ω;

⑥ 使用指数机制以概率Pc(St,Πt)从Ω中选(St,Πt)加入并将St加入V,令fa=St;

⑦ end for

由算法4和算法5可知,FGB与GreedyBayes算法的一个主要区别在于步骤⑤求解每个待选结点的最佳父结点集的过程.FGB使用了一个时间复杂度为O(nd2)的算法DPBestParent来进行求解.而GreedyBayes算法是通过枚举所有的情况,然后从中选择最优的.实际上在枚举的过程中是存在着大量的重复计算和无意义计算的.而FGB算法利用了动态规划的记忆化手段和最优子结构特性,在保证解是当前最优解的前提下极大地减少了大量的重复计算和无意义计算.这在很大程度上提升了贝叶斯网络的构建速度.

DPBestParent算法的实现过程如算法6所示:

算法6. DPBestParent算法.

输入:数据集Di={x1,x2,…,xn}、属性Sj、新增父属性fa、当前最大入度数d′;

输出:最佳父属性集Πj.

dp[Sj,0]=∅;

② for l=d′ to 1 do

Π′=dp[Sj,l-1]∪fa;

Π″=dp[Sj,l];

⑥ end for

Πj=dp[Sj,d′];

⑧ return Πj.

算法6中dp[Sj,l]表示结点集合,含义是结点Sj选择l个结点作为父结点的最佳选择情况.从步骤②~⑥的for循环中可以看出,实际上在新一轮的DPBestParent算法执行时,dp[Sj,l]就已经记录了上一轮中在该状态下的最佳父结点集的选择情况.因此对于本轮来说,只需要关心上一轮新加入网络的结点fa对当前最佳父结点集的选择情况的影响即可.这里for循环采用的是倒序遍历的方式,即从d′到1.其原因是为了保证当前更新的状态不会影响到下一次的状态更新,这个操作避免了结点fa被加入到同一个父结点集多次.

接下来证明FGB算法的时间复杂度.

定理5. FGB算法的时间复杂度为O(nm2d2).

证明. FGB算法的时间消耗主要集中在步骤③~⑦的for循环.该for循环一共会执行|Ci|-1次.

对于步骤⑤,循环每次执行时都会调用|Ci|-t(t∈[1,|Ci|-1])次 DPBestParentSet子算法,而每次调用子算法所需的时间为O(nd2).因此,执行完|Ci|-1次步骤⑤所需的总时间复杂度为O(n|Ci|2d2).

对于步骤⑥,循环每次都会为|Ci|-t个待选组合(St,Πt) 计算其被选择的概率Pc(St,Πt),而每次计算所需的时间为O(nd).因此,执行完|Ci|-1次步骤⑥所需的总时间复杂度为O(n|Ci|2d).

又因为每个属性子集的大小|Ci|∝m.因此,整个FGB算法的时间复杂度为O(nm2d2).

证毕.

除了解决GreedyBayes算法在执行效率上的问题之外,FGB算法还引入了差分隐私指数机制来扰动贝叶斯网络的构建过程(步骤⑥),从而解决了构建的贝叶斯网络存在隐私泄露风险的问题.

差分隐私指数机制的思想是依据评分函数以一定的概率来选择当前加入贝叶斯网络的(Si,Πi)对.我们使用互信息I来作为指数机制的评分函数u(S,Π)=I(S,Π).当(S,Π)对的互信息越大时,评分函数u(S,Π)的值就越高,则被选择的概率也就越大.由式(20)可知,该评分函数的全局敏感度为

(24)

虽然Zhang等人[19]在PrivBayes方法中提出了一种全局敏感度更低的评分函数F,其全局敏感度仅为ΔF=1/n.但计算该评分函数所需的时间为O(n2d),仅能适用于构建d较小的贝叶斯网络.因此本文不采用该方法,仍然使用互信息作为评分函数.

在执行FGB算法之前,PriveSCBN算法(算法2)的步骤④会将原始数据集D分割成k个相互独立的数据集子集Di.由性质2可知,处理这些子集的过程可以共享同一个隐私预算.

FGB算法会执行步骤⑥共|Ci|-1次,每次都需要使用指数机制从Ω中选择一个(St,Πt)对加入贝叶斯网络.由性质1可知,每次选择都会消耗一部分的隐私预算.这里采用平均分配的方式,即将隐私预算ε2平均分成|Ci|份.结合指数机制,可得概率值Pc(St,Πt)的表达式为

(25)

其中,u表示评分函数,Δu表示评分函数的全局敏感度,Ω表示当前所有可选的组合情况.

最后,说明FGB算法满足ε2-差分隐私.算法最终输出的是一个贝叶斯网络而在构建的过程中在步骤⑥选择当前加入的(St,Πt)组合时使用了指数机制exp(ε2u(St,Πt)/(2|Ciu))来进行选择,这个操作扰动了贝叶斯网络的构建过程.由定理2可知,该操作满足ε2-差分隐私.而后续没有其他的步骤再次涉及原始数据集D的使用.因此,整个FGB算法满足ε2-差分隐私.

3.4 差分隐私条件分布计算

通过贝叶斯网络可以在很大程度上简化联合分布的计算过程,并且越好的贝叶斯网络计算出来的联合分布越接近真实值.但是如果直接使用贝叶斯网络来进行计算,很有可能会导致隐私的泄露.因此,我们需要对计算出来的联合分布做进一步的扰动,以此来达到保护隐私的目的.

Zhang等人[19]在论文中使用NoisyConditionals算法来实现贝叶斯网络的安全计算.该算法通过向每个结点与其父结点集的联合分布Pr[Sj,Πj]注入拉普拉斯噪声来得到带噪声的联合分布Pr*[Sj,Πj].虽然这样做能够保证联合分布是受差分隐私保护的,但当属性维度m较大或者属性的取值情况较多时,计算得到的联合分布的概率值会普遍偏小.而如果直接对这些较小的概率值注入噪声干扰的话,那么很有可能会导致这些概率值被完全覆盖,造成大规模的概率值失真问题,这将严重影响后续生成的合成数据的精度.因此,本文不直接采用NoisyConditionals方法,而是针对二值数据的取值特点提出了一种概率分布加噪算法BNC来实现贝叶斯网络的安全计算.

由于BNC算法每次处理的是一个数据集子集Di,由性质2可知,处理这些子集的过程可以共享同一个隐私预算. 因此,BNC算法的实现过程如算法7所示:

算法7. BNC算法.

输入:数据集子集Di={x1, x2,…, xn}、贝叶斯网络最大入度数d、隐私预算ε3;

输出:带噪声的条件分布集

① 初始化

② fo

③ 求联合分布Pr[Sj,Πj]和边缘分布

Pr[Πj];

④ 求条件分布Pr[Sj|Πj]=Pr[Sj,Πj]/

Pr[Πj];

⑤ 对Pr[Sj|Πj]加入噪声得到

Pr*[Sj|Πj];

⑥ 将Pr*[Sj|Πj]中的负值归0,对每一对条件相同、取值相对的条件概率归一化,然后加入

⑦ end for

⑧ for j=1 to d′ do

⑨ 基于联合分布Pr*[Sd′+1,Πd′+1]计算条件分布Pr*[Sj|Πj],并加入

⑩ end for

从算法7中可以看出,BNC算法不会直接对联合分布进行加噪,而是改为对由联合分布和边缘分布计算得来的条件分布进行加噪.这里利用了条件概率在二值数据上的取值特点,即当分布为条件分布时,有以下式子成立:

PrSj=0|Πj=Oj+PrSj=1|Πj=Oj=1,

(26)

其中,Sj表示当前结点所对应的属性,Πj表示Sj的最佳父结点集所对应的属性集,Oj表示Πj的某个取值情况.

由式(26)可知,在条件概率Pr[Sj=0|Πj=Oj]和Pr[Sj=1|Πj=Oj]中至少会存在一个条件概率的概率值比较大或者2个条件概率的概率值相差不大即都在0.5上下.这样即使直接对条件概率注入噪声干扰,也至少存在一个较大的条件概率的概率值不会被完全覆盖.所以就不会出现2个概率值同时被覆盖的情况,除非是注入的噪声干扰原本就是非常大的,那在这种情况下即使采取任何措施也都无法避免概率值失真的情况发生.因此,利用条件概率在二值数据上的这个特点能够在很大程度上减少概率失真发生的次数.

接下来考虑BNC算法在步骤⑤中加入的拉普拉斯噪声大小.在步骤⑤中计算时会注入次拉普拉斯噪声.由性质1可知,每次注入噪声都需要分配一部分的隐私预算.这里采用平均分配的方式,即将隐私预算ε3平均分成.同时由Zhang等人[19]的论文可知条件分布的全局敏感度为2/n.因此,每次对条件分布Pr[Sj|Πj]加入的拉普拉斯噪声大小为

(27)

注意到BNC算法在步骤⑨中计算Pr*[Sj,Πj](j∈[1,d′])是直接基于Pr*[Sd′+1,Πd′+1]计算的,不会涉及原始数据集Di的使用.因此不需要对其加入拉普拉斯噪声干扰,这样可以节省下d′个隐私预算的分配.

除了利用条件概率在二值数据属性上的取值特点来减少概率失真发生的次数之外.根据式(27)可知,当贝叶斯网络的最大入度数d′在不断增加时,其所产生的拉普拉斯噪声大小也在逐渐减小.因此,BNC算法还允许使用者通过控制d′来减小产生的噪声大小,以此来进一步减少概率值失真发生的次数.

考虑到在对条件分布注入拉普拉斯噪声后,条件分布的概率值可能出现取值为负和每一对条件相同、取值相对的条件概率之和不为1的问题.BNC算法还会对加噪后的概率值进行“一致性处理”,即算法7中的步骤⑥,从而保障求出来的条件分布的概率值满足概率的基本性质.

最后,说明BNC算法满足ε3-差分隐私.算法在步骤⑤中对每个条件分布Pr[Sj,Πj]注入拉普拉斯噪声得到带噪声的条件分布Pr*[Sj,Πj].由定理1和性质1可知,该步骤满足ε3-差分隐私.而在后续的步骤中,没有其他操作有涉及到原始数据集Di的使用.因此,整个BNC算法满足ε3-差分隐私.

4 实 验

4.1 实验环境

本次实验使用C++编程语言来实现所有的方法,其中贝叶斯网络部分的实现参考了Zhang等人[20]论文的实验相关代码.

实验平台的具体配置信息如表3所示:

Table 3 Experimental Platform Configuration Information

表3 实验平台配置信息

软硬件信息具体配置处理器Intel CoreTM i5-6300HQ CPU(2.3GHz)内存8GB操作系统Windows10 64位操作系统集成开发环境Dev-C++ v5.11编程语言C++ 11

4.2 实验数据集

实验采用3个真实的数据集NLTCS,ACS,Retail.其中NLTCS是一项美国长期护理调查记录,其中包括21 574名老年残疾人的日常生活、医疗情况;ACS是由IPUMS-USA所发布的全球人口普查和调查数据,记录了47 461条个人信息;Retail是美国零售市场的88 162条购物记录,每条记录包含其所购买的商品条目,总共有16 469种商品类别,我们从中选取了前50个销量最多的商品,并将它们处理成含有50个属性的高维二值数据集.这3个数据集的具体信息如表4所示:

Table 4 Description of Datasets

表4 数据集信息描述

数据集数据类型行数列数取值个数NLTCS二值数据21 57416216ACS二值数据47 46123223Retail二值数据88 16250250

4.3 评价指标

定义5. L2误差.假设原始数据集D通过第i次查询产生的α-way边缘表为Ti(D),合成数据集产生的α-way边缘表为则它们之间的L2误差为

(28)

其中,表示第i次查询产生的α-way边缘表第j行的值,N表示查询的次数,M表示边缘表的行数.

4.4 实验和结果

我们将通过3个不同的实验来验证PrivSCBN算法的高效性和可用性.

第1个实验是为了验证PrivSCBN算法中的FGB子算法与传统的GreedyBayes算法在构建贝叶斯网络的时间性能上的表现.实验将在NLTCS和ACS这2个数据集上进行100次随机的重复实验,贝叶斯网络的最大入度数d分别设置为2,3,4.对于FGB算法所需的隐私预算ε,由于不是本次实验关心的变量,因此我们将其恒定为1.实验结果将通过对比这2个算法构建贝叶斯网络的平均时间消耗来进行验证.实验结果如表5所示:

Table 5 Average Time Consumption Record

表5 平均时间消耗记录 s

最大入度数dNLTCS数据集ACS数据集FGB算法GreedyBayes算法FGB算法GreedyBayes算法22.90526.88214.881265.02834.03072.86120.4281103.61045.103154.07027.3473742.950

从表5中可以看出,FGB算法在时间性能上的表现要明显优于GreedyBayes算法,这是符合我们预期的.当d=2时,GreedyBayes算法的时间消耗是FGB的9倍(NLTCS)和18倍(ACS),并且随着d的增加这个倍数也在逐渐扩大.d=3时是18倍和54倍,当d=4时是30倍和137倍.这个实验结果表明相较于传统的GreedyBayes算法,使用FGB算法来构建贝叶斯网络更为高效.

从另一个角度来看,不管是随着数据属性维度m的增加还是随着贝叶斯网络最大入度数d的增大,FGB算法的时间消耗增长幅度都要比Greedy-Bayes小很多.例如当d=2,m从16增加到23时,FGB的运行时间只扩大了5倍左右,而GreedyBayes的运行时间扩大了10倍左右.并且随着d的增加FGB的运行时间的增幅一直维持在5倍左右,而GreedyBayes的增幅是明显变大的,d=3时是15倍,d=4时是24倍.这个结果表明FGB算法在执行效率上具有一定的稳定性.

因此,以FGB算法作为核心子算法的PrivSCBN算法本身也具有高效性和一定的稳定性.

第2个实验是为了分析PrivSCBN算法的可用性.为了能够知道在无噪声环境下,PrivSCBN算法本身可能会产生的噪声大小.我们通过设置无差分隐私保护的NoPrivSCBN算法来与之进行对比.实验将在NLTCS,ACS这2个数据集上进行100次随机的重复实验,隐私预算ε分别设置为0.05,0.1,0.2,0.4,0.8,1.0.实验结果将通过200次随机的α-way查询进行验证,其中α的取值为3,8,12.实验结果如图4所示.

从图4中可以看出,即使是没有差分隐私保护的PrivSCBN算法也会产生一定的误差.其原因是PrivSCBN是一种贝叶斯网络模型方法,在构建贝叶斯网络的过程中,以及通过贝叶斯网络的近似推理求得的联合分布本身,还有使用联合分布生成的合成数据集,在这些过程中本身就会产生一定的误差.因此随着隐私预算ε的增加,PrivSCBN的误差逐渐逼近NoPrivSCBN的误差,这是符合差分隐私规律的.

注意到当隐私预算ε=0.05时,所有实验的查询误差都达到了很高的量级.而当ε增大时,这些查询误差开始呈明显的下降趋势.这是符合我们的预期的.因为当ε=0.05时,注入的噪声干扰是非常大的,这会使得大部分的概率值都出现失真问题,导致最后生成的合成数据的精度变得非常差.

通过进一步的观察我们发现随着隐私预算ε的增加,PrivSCBN算法的查询误差在快速地下降.最后会达到NoPrivSCBN的误差界限,并且大多都只需要较少的隐私预算就能达到.这个实验结果表明PrivSCBN具有较高的可用性.

Fig. 4 Analysis of α-way query error with or without differentially private on NLTCS and ACS datasets

图4 NLTCS和ACS数据集上有无隐私保护的α-way查询误差分析

第3个实验是为了分析PrivSCBN算法在真正的高维数据集Retail上的表现.为了能够做更好的说明,本次实验从现有的高维数据差分隐私发布方法中挑选了3个最具有代表性的方法来作为实验对比.这3个方法为降维系列方法中的PriView[17]方法、贝叶斯网络模型方法中的PrivBayes[19]方法、Markov网络模型方法中的Jtree[26]方法,它们都是目前比较最经典且权威的发布方法.以这3个方法作为实验对比,能够增加实验结果的可信程度.

我们将在Retail数据集上进行100次随机的重复实验,隐私预算ε分别设置为0.1和1.0.实验结果将通过200次随机的α-way查询进行验证,其中α的取值为4,6,8.实验结果如图5所示.

Fig. 5 Error analysis of α-way query in different methods on Retail dataset

图5 Retail数据集上不同方法的α-way查询误差分析

从图5中可以看出,当隐私预算ε较小时(ε=0.1),PrivSCBN方法的表现要明显优于其他3种方法.而当隐私预算ε较大时(ε=1.0),PrivSCBN虽然仍优于其他3种方法,但与Jtree方法的结果相差不大.这是符合差分隐私规律的.因为随着隐私预算的不断增加,算法的隐私保护程度将会不断地下降,直至与无差分隐私保护算法的执行结果一致.因此,可以看出通过PrivSCBN方法构建的概率图模型本身的精度与用Jtree方法构建的模型精度相比,要来得更好一些.而与用PrivBayes方法构建的模型精度相比,要来得更好许多.这也进一步验证了本文提出的各种改进策略是有效的,并且取得了不错的效果.本次实验结果表明了PrivSCBN相较于其他3种方法具有更高的可用性.

5 结束语

高维数据的差分隐私发布问题一直以来都是差分隐私领域中的研究重点与难点问题.本文针对高维二值数据差分隐私发布问题,提出了一种高效且低噪的差分隐私发布方法PrivSCBN.该方法先是通过DPSC算法将属性集S划分成多个相互独立的属性子集Ci,然后根据这些子集将原始数据集D分割成多个互不相交的数据集子集Di.接着使用FGB算法为每个Di快速地构建满足差分隐私的贝叶斯网络,然后使用BNC算法从每个贝叶斯网络中提取带噪声的条件分布最后利用这些来生成合成数据集进行发布.通过在3个真实高维二值数据集上的3组实验,并与3个同类型的方法进行对比,验证了PrivSCBN方法的高效性与可用性.

在未来的研究中,我们将进一步关注高维非二值数据的差分隐私发布问题,以及研究如何解决流式数据环境下的发布问题.

作者贡献声明:洪金鑫负责分析问题,设计算法,验证实验和撰写论文;吴英杰负责提出问题,参与算法讨论,指导论文写作;蔡剑平负责协助分析,参与算法讨论,指导论文写作;孙岚负责协助分析,参与算法讨论,指导论文写作.

参考文献

[1]Dwork C. Differential privacy[C] //Proc of the 33rd Int Colloquium on Automata, Languages and Programming(ICALP 2006). Berlin: Springer, 2006: 1-12

[2]Dwork C, McSherry F, Nissim K, et al. Calibrating noise to sensitivity in private data analysis[C] //Proc of the 3rd Theory of Cryptography Conf (TCC 2006). Berlin: Springer, 2006: 363-385

[3]McSherry F, Talwar K. Mechanism design via differential privacy[C] //Proc of the 48th Annual IEEE Symp on Foundations of Computer Science. Piscataway, NJ: IEEE, 2007: 94-103

[4]McSherry F. Privacy integrated queries:An extensible platform for privacy-preserving data analysis[C] //Proc of the 2009 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2009: 19-30

[5]Zhang Xiaojian, Meng Xiaofeng. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949 (in Chinese)(张啸剑, 孟小峰. 面向数据发布和分析的差分隐私保护[J]. 计算机学报, 2014, 37(4): 927-949)

[6]Chen Shixi, Zhou Shuigeng, Bhowmick S S. Integrating historical noisy answers for improving data utility under differential privacy[C] //Proc of the 15th Int Conf on Extending Database Technology. New York: ACM, 2012: 62-73

[7]Chaudhuri K, Sarwate A D, Sinha K. A near-optimal algorithm for differentially-private principal components[J]. The Journal of Machine Learning Research, 2013, 14(1): 2905-2943

[8]Wang Sen, Chang J M. Differentially private principal component analysis over horizontally partitioned data[C] //Proc of the 2018 IEEE Conf on Dependable and Secure Computing(DSC). Piscataway, NJ: IEEE, 2018: 1-8

[9]Ge J, Wang Zhaoran, Wang Mengdi, et al. Minimax-optimal privacy-preserving sparse PCA in distributed systems[C] //Proc of the 21st Int Conf on Artificial Intelligence and Statistics. Brookline, MA: JMLR, 2018: 1589-1598

[10]Choromanska A, Choromanski K, Jagannathan G, et al. Differentially-private learning of low dimensional manifolds[C] //Proc of the 24th Int Conf on Algorithmic Learning Theory. Berlin: Springer, 2013: 249-263

[11]Kasiviswanathan S P, Jin Hongxia. Efficient private empirical risk minimization for high-dimensional learning[C] //Proc of the 15th IEEE Int Conf on Machine Learning and Applications. Piscataway, NJ: IEEE, 2016: 488-497

[12]Xu Chugui, Ren Ju, Zhang Yaoxue, et al. DPPro: Differentially private high-dimensional data release via random projection[J]. IEEE Transactions on Information Forensics and Security, 2017, 12(12): 3081-3093

[13]Chanyaswad T, Liu Changchang, Mittal P. RON-Gauss: Enhancing utility in non-interactive private data release[C] //Proc of the 19th Privacy Enhancing Technologies Symp. Berlin: De Gruyter, 2019: 26-46

[14]Zhou Shuheng, Ligett K, Wasserman L. Differential privacy with compression[C] //Proc of the 2009 IEEE Int Symp on Information Theory. Piscataway, NJ: IEEE, 2009: 2718-2722

[15]Kellaris G, Papadopoulos S. Practical differential privacy via grouping and smoothing[J]. Proceedings of the VLDB Endowment, 2013, 6(5): 301-312

[16]Wang Ning, Gu Yu, Xu Jia, et al. Differentially private high-dimensional data publication via grouping and truncating techniques[J]. Frontiers of Computer Science, 2019, 13(2): 382-395

[17]Qardaji W H, Yang Weining, Li Ninghui. PriView: Practical differentially private release of marginal contingency tables[C] //Proc of the 2014 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 1435-1446

[18]Chen Xuan, Liu Jian, Feng Xinqi, et al. Differential private synthesis dataset releasing algorithm based on Navie Bayes[J]. Computer Science, 2015, 42(1): 236-238 (in Chinese)(陈旋, 刘健, 冯新淇, 等. 基于朴素贝叶斯的差分隐私合成数据集发布算法[J]. 计算机科学, 2015, 42(1): 236-238)

[19]Zhang Jun, Cormode G, Procopiuc C M, et al. PrivBayes: Private data release via Bayesian networks[C] //Proc of the 2014 ACM SIGMOD Int Conf on Management of Data. New York: ACM, 2014: 1423-1434

[20]Zhang Jun, Cormode G, Procopiuc C M, et al. PrivBayes: Private data release via Bayesian networks[J]. ACM Transactions on Database Systems, 2017, 42(4): 1-41

[21]Wang Liang, Wang Weiping, Meng Dan. Privacy preserving data publishing via weighted Bayesian networks[J]. Journal of Computer Research and Development, 2016, 53(10): 2343-2353 (in Chinese)(王良, 王伟平, 孟丹. 基于加权贝叶斯网络的隐私数据发布方法[J]. 计算机研究与发展, 2016, 53(10): 2343-2353)

[22]Li Mingzhu, Ma Xuebin. Bayesian networks-based data publishing method using smooth sensitivity[C] //Proc of the 2018 IEEE Int Conf on Parallel & Distributed Processing with Applications, Ubiquitous Computing & Communications, Big Data & Cloud Computing, Social Computing & Networking, Sustainable Computing & Communications. Piscataway, NJ: IEEE, 2018: 795-800

[23]Hao Zhifeng, Wang Riyu, Cai Ruichu, et al. Privacy data publishing method based on Bayesian network and semantic tree[J]. Computer Engineering, 2019, 45(4): 130-135 (in Chinese)(郝志峰, 王日宇, 蔡瑞初, 等. 基于贝叶斯网络与语义树的隐私数据发布方法[J]. 计算机工程, 2019, 45(4): 130-135)

[24]Su Sen, Tang Peng, Cheng Xiang, et al. Differentially private multi-party high-dimensional data publishing[C] //Proc of the 32nd IEEE Int Conf on Data Engineering(ICDE). Piscataway, NJ: IEEE, 2016: 205-216

[25]Li Xianxian, Zhao Huaxing, Yu Dongran, et al. Multi-dimensional correlation hierarchical differential privacy formedical data with multiple privacy requirements[C] //Proc of the 2nd Int Conf on Healthcare Science and Engineering. Berlin: Springer, 2018: 153-173

[26]Chen Rui, Xiao Qian, Zhang Yu, et al. Differentially private high-dimensional data publication via sampling-based inference[C] //Proc of the 21st ACM SIGKDD Int Conf on Knowledge Discovery and Data Mining. New York: ACM, 2015: 129-138

[27]Zhang Xiaojian, Chen Li, Jin Kaizhong, et al. Private high-dimensional data publication with junction tree[J]. Journal of Computer Research and Development, 2018, 55(12): 2794-2809 (in Chinese)(张啸剑, 陈莉, 金凯忠, 等. 基于联合树的隐私高维数据发布方法[J]. 计算机研究与发展, 2018, 55(12): 2794-2809)

[28]Ng A Y, Jordan M I, Weiss Y. On spectral clustering: Analysis and an algorithm[C] //Proc of the 14th Int Conf on Neural Information Processing Systems: Natural and Synthetic. New York: ACM, 2001: 849-856

Differentially Private High-Dimensional Binary Data Publication via Attribute Segmentation

Hong Jinxin1, Wu Yingjie1, Cai Jianping2, and Sun Lan1

1(College of Mathematics and Computer Science, Fuzhou University, Fuzhou 350108) 2(College of Information and Smart Electromechanical Engineering, Xiamen Huaxia University, Xiamen, Fujian 361024)

Abstract Generally, as the attribute dimension of the data set increases, the time cost and noise interference generated by the differential privacy publishing method of high-dimensional data will also increase. Especially for high-dimensional binary data, it is easy to be covered by excessive noise. Therefore, an efficient and low-noise publishing method PrivSCBN(differentially private spectral clustering Bayesian network) is proposed for the issue of privacy publishing of high-dimensional binary data. Firstly, based on Jaccard distance, this method uses a spectral clustering algorithm which satisfies differential privacy to divide the attributes set, and further segments the original data set, so as to achieve dimension reduction. Secondly, based on the idea of dynamic programming and combined with the exponential mechanism, this method uses a fast building Bayesian network algorithm which satisfies differential privacy to construct Bayesian network for each subset after segmentation. Finally, this method uses the value characteristic of conditional probability on binary data to add noise to conditional distribution extracted from Bayesian network, and reduces the noise by controlling the maximum in-degrees of Bayesian network. The efficiency and availability of the PrivSCBN method are verified by experiments on three real high-dimensional binary data sets.

Key words differential privacy; high-dimensional binary data publication; Bayesian network; attribute division; dynamic programming; conditional distribution

(fzu_hjx@163.com)

中图法分类号 TP391

收稿日期20200908;修回日期:20210127

基金项目福建省自然科学基金项目(2017J01754,2018J01797)

This work was supported by the Natural Science Foundation of Fujian Province of China (2017J01754, 2018J01797).

通信作者吴英杰(yjwu@fzu.edu.cn)

Hong Jinxin, born in 1996. Master. His main research interests include data security and privacy preserving.

洪金鑫,1996年生.硕士.主要研究方向为数据安全与隐私保护.

Wu Yingjie, born in 1979. PhD, professor. His main research interests include data mining, data security and privacy preserving.

吴英杰,1979年生.博士,教授.主要研究方向为数据挖掘、数据安全与隐私保护.

Cai Jianping, born in 1990. Master, teaching assistant. His main research interests include recommender system, optimization theory and big data.

蔡剑平,1990年生.硕士,助教.主要研究方向为推荐系统、优化理论和大数据.

Sun Lan, born in 1978. Master, lecturer. Her main research interests include data security and privacy preserving.

孙 岚,1978年生.硕士,讲师.主要研究方向为数据安全与隐私保护.