面向高维数据发布的个性化差分隐私算法①
马苏杭1,2, 龙士工1,2, 刘 海1,2, 彭长根1,2, 李思雨1
1(贵州大学 计算机科学与技术学院, 贵阳 550025)2
(贵州大学 贵州省公共大数重点实验室, 贵阳 550025)通讯作者: 龙士工q 摘 要: 在高维数据隐私发布过程中, 差分隐私预算大小直接影响噪音的添加. 针对不能合理地为多个相对独立的低维属性集合合理分配隐私预算, 进而影响合成发布数据集的安全性和可用性, 提出一种个性化隐私预算分配算法(PPBA).
引入最大支撑树和属性节点权重值降低差分隐私指数机制挑选属性关系对的候选空间, 提高贝叶斯网络精确度, 提出使用贝叶斯网络中节点动态权重值衡量低维属性集合的敏感性排序. 根据发布数据集安全性和可用性的个性化需求, 个性化设置差分隐私预算分配比值常数值, 实现对按敏感性排序的低维属性集合个性化分配拉普拉斯噪音. 理论分析和实验结果表明, PPBA 算法相比较于同类算法能够满足高维数据发布安全性和可用性的个性化需求, 同时具有更低的时间复杂度.
关键词: 贝叶斯网络; 差分隐私; 最大支撑树; 动态权重值; 个性化比例分配
引用格式: 马苏杭，龙士工，刘海，彭长根，李思雨.面向高维数据发布的个性化差分隐私算法.计算机系统应用,2021,30(4):131–138. www.c-s-a/1003-3254/7870.html
Personalized Differential Privacy Algorithm for High-Dimensional Data Publishing
MA Su-Hang 1,2, LONG Shi-Gong 1,2, LIU Hai 1,2, PENG Chang-Gen 1,2, LI Si-Yu 1
1(College of Computer Science and Technology, Guizhou University, Guiyang 550025, China)
2
(Guizhou Provincial Key Laboratory of Public Big Data, Guizhou University, Guiyang 550025, China)
Abstract : In the process of privacy prerving high-dimensional data publishing, the size of the differential privacy budget directly affects the addition of noi. The privacy budget cannot be allocated reasonably for independent low-dimensional attribute ts, compromising the curity and restricting availability of composite data ts. Then a Personalized Privacy Budget Allocation (PPBA) algorithm is propod. The maximum support tree and weight values of attribute nodes are introduced to reduce the candidate space of attribute relationship pairs lected by the differential privacy index mechanism and enhance the accuracy of the Bayesian network. The dynamic weight values of nodes in the Bayesian network are t to rank the nsitivity of low-dimensional attribute ts. According to the personalized requirements for curity and availability of published data ts, the constant allocation ratio q of differential privacy budgets is customized for the personalized allocation of Laplace noi to the low-dimensional attribute ts sorted by nsitivity. Theoretical analysis and experimental results reveal that the PPBA algorithm can meet the personalized requirements for curity and availability of high-dimensional data publishing, with lower time complexity.
Key words : Bayesian network; differential privacy; maximum support tree; dynamic weight value; personalized proportional distribution
计算机系统应用 ISSN 1003-3254, CODEN CSAOBN
E-mail: Computer Systems & Applications,2021,30(4):131−138 [doi: 10.15888/jki.csa.007870]www.c-s-a ©中国科学院软件研究所版权所有.
Tel: +86-10-62661041搞笑英文
① 基金项目: 国家自然科学基金(62062020, 62002081, U1836205); 贵州省科技计划(黔科合重大专项字[2018]3001)
Foundation item: National Natural Science Foundation of China (62062020, 62002081, U1836205); Science and Technology Plan of Guizhou Province ([2018]3001)
收稿时间: 2020-08-18; 修改时间: 2020-09-10; 采用时间: 2020-09-18; csa 在线出版时间: 2021-03-30
131
1 引 言
随着移动互联网的发展, 数据规模也以前所未有的速度不断增长, 数据属性之间的相互关系变得复杂多
样, 高维数据已是一种常见的数据发布类型. 随着数据挖掘和分析技术的发展, 高维数据的发布具有更高的信息价值, 但高维数据中通常包含大量隐私信息, 如果使用不当将造成隐私泄露[1,2]. 为了保证高维数据发布过程中不会泄露隐私信息, 在发布之前使用差分隐私[3,4]保护技术进行处理. 如果直接对高维数据进行差分隐私处理, 存在添加噪音过多, 数据可用性差等问题.其中差分隐私预算的分配方式直接影响数据的可用性与安全性关系, 而不同数据机构对于发布数据集安全性和可用性之间的关系需求各不相同, 数据保护级别更高的数据机构更注重数据的安全性; 而主要提供数据进行应用的数据机构则更倾向于数据的可用性.
目前已有的面向高维数据发布的差分隐私算法有概率图模型[5–7]、阈值过滤技术[8]以及投影技术[9], 这些技术通过维度转换达到降维效果, 减少噪音添加对数据可用性的影响. 降维效果的好坏直接影响数据的可用性, 而阈值过滤技术和投影技术忽略了高维属性之间普遍存在依赖关系, 采用直接截断的降维方法, 大大降低了数据的可用性. 文献[5–7]利用指数机制[3,10]挑选属性关系对, 受候选空间大小和隐私预算分配方式的影响, 空间越大挑选的属性关系对越不准确. 同时，单一的隐私预算分配方式为敏感性不同的属性数据分配相同的隐私预算, 导致隐私预算无法根据数据可用性与安全性的个性化需求合理分配, 存在隐私浪费的问题.
基于在高维数据发布过程中, 数据安全性与可用性受降维算法效果和隐私预算分配方式的影响, 为满足发布数据集安全性与可用性的个性化需求, 本文提出个性化隐私预算分配(Personnalized Privacy Budg
et Allocation, PPBA)算法, 主要内容如下.
(1)对基于概率图模型的贝叶斯网络算法进行优化, 引入最大支撑树和最大权重值, 减少指数机制挑选属性关系对的搜索空间, 避免敌手进行多次查询对比分析, 泄露隐私信息. 提高数据可用性和安全性.
q (2)依据动态权重值确定贝叶斯网络中低维属性集合敏感性由大到小的排序. 受文献[11–13]启发, 根据不同用户数据可用性与安全性需要, 个性化设置隐私预算分配比值常数，为不同敏感性的属性集合合理
分配差分隐私(Laplace [10])噪声.
ε(3)理论证明所提出的PPBA 算法满足-差分隐私, 并在真实数据集上进行性能评估. 实验结果表明能够满足数据可用性与安全性个性化需求, 同时降低了时间复杂度.
2 相关工作
数据独立发布算法和数据相关发布算法是主要的2类面向高维数据发布的差分隐私算法. 独立发布算法的典型代表是PriVew [14]，该算法假设所有属性都是相互独立的，这在真实数据集中是不存在的, 且缺少正式的推理机制. 而PrivBayes 算法[5]、加权贝叶斯网络算法[6]、联合树算法[7]是典型的数据相关发布算法.
PrivBayes 算法利用指数机制挑选属性关系对形成贝叶斯网络, 对联合分布概率进行推理, 存在候选空间较大, 数据可用性和安全性得不到保障的问题. 文献[6]对贝叶斯网络进行优化, 利用最大权重值提高贝叶斯网络推理的准确性, 但仍然存在挑选属性关系对候选空间较大的问题. 文献[7]通过指数机制构造Markov 网, 引入高通滤波技术缩减指数机制搜索空间. 并结合相应的后置技术对Markov 网分割来获得完全团图, 生成满足差分隐私的联合树, 利用联合树中各个团后置处理之后的联合分布表合成最终的高维数据. 文献[5–7]在高维数据相关发布得到广泛的应用, 但在面对不同数据机构对于数据安全性与可用性的个性化需求, 缺少个性化的隐私预算分配策略.
针对不同数据类型关于隐私预算分配问题, 为了兼顾数据安全性与可用性的效率, 文献[11]以差分隐私保护结合主流决策树分类方法, 提出等差分配隐私预算的方式, 改善决策树的分类准确率. 文献[12]针对树索引结构提出等差数列分配和等比数列分配两种方式. 避免对树的某一层分配过小, 数据可用性过低; 分配过大, 不能对这层数据提供足够安全保障的问题.
3 基础知识
本节内容主要对面向高维数据发布的个性化差分隐私算法所使用的贝叶斯网络、差分隐私概念进行说明.
3.1 贝叶斯网络
文章在论述过程中涉及较多数学符号, 为了更好地对下文相关内容进行解释, 给出相关符号定义, 如表1所示.
计算机系统应用
www.c-s-a
2021 年 第 30 卷 第 4 期
132
表1 符号定义表
符号
描述D 原始高维数据集D n 数据集D 的元组个数Ar 数据集D 中的属性集合d Ar 属性集合中的属性个数星期一英语怎么说
N 贝叶斯网络Pr[Ar ]高维数据集D 的原始分布
Pr N [Ar ]根据贝叶斯网络推理原始数据集的近似分布K 贝叶斯网络的最大父节点数, 即贝叶斯网络的度值
WV 属性节点的权重值DWV 属性节点的动态权重值
CM 属性值的多样性P (X ,M )属性节点与父节点集合的联合概率
M 父节点集合
dom (X )
属性变量的域
N N N N 定义1. 贝叶斯网络. 贝叶斯网络为一个有向无环图, 中每一个节点代表高维数据集D 中一个字段属性, 如果中两个属性节点之间存在着直接依赖关系, 则两个属性字段节点之间用一条弧(或有向边)直接相连. 贝叶斯网络使用(属性字段节点, 属性字段节点的父节点集合)对来表示.
Ar 1通过挑选属性间的依赖关系, 实现高维数据的维度转换, 构建贝叶斯网络进行联合分布的推理. 通过例子解释说明, 高维数据集属性集合为, 有A 、B 、C 、D 共4个属性, 未进行维度转换形成贝叶斯网络时, 其联合分布的计算如下式所示:
若在属性依赖关系的挑选中使用最大父节点个数值即度值为2的贝叶斯网络算法对该数据集进行处理，形成如图1所示4个属性字段节点构成的2度贝叶斯网络图.
图1 2度贝叶斯网络
(A ,∅)(B ,{A })(C ,{A ,B })(D ,{A ,C })Pr N [Ar 1]则该贝叶斯网络用4个相对独立的低维属性集合
,, ,, 来表示, 其中联合分
布的计算如式(2)所示
.
走月Pr N [Ar 1]Pr[Ar 1]未进行维度转化处理之前该数据集属性之间存在6种属性关系, 当使用2度贝叶斯网
络算法之后降低到5种属性关系. 相比在数据量较多的情况下具有更低的计算复杂度, 为多个相对独立的低维属性集合加入更少的噪声.
3.2 差分隐私
差分隐私保护技术通过向原始数据集添加满足差分隐私的噪音生成邻近数据集, 使得原始数据集与邻近数据集在查询输出中具有概率不可区分性.
εD 1D 2εRange (A )A S ⊆Range (A )定义2. -差分隐私[10]. 对于任意两个相邻数据集
和, 它们之间相差最多为一条记录, 若一个随机函
数A 满足-
差分隐私保护, 表示随机函数的取值范围, 则对于所有的有:
Pr[E ]ε其中, 表示事件E 的披露风险, 为隐私预算参数，代表了差分隐私保护水平, 其值越小, 不可区分性越大，隐私保护级别越高.
定义3. 敏感度[10]. 敏感度是由函数本身决定的, 不同函数具有不同的敏感度, 敏感度过低会使发布数据集的安全性得不到保障, 敏感度过高则使发布数据集
金陵十三钗观后感
的发布结果实用性降低.
给定F 是将一个数据集映射到一个固定大小实数向量的函数, 那么函数F 的敏感度为:
D 1D 2其中, 和为任意两个邻近数据集, 二者仅相差一个数据元组.
为了在给定的隐私预算内, 将全部隐私预算合理分配到多个相对独立的低维属性集合中, 使整个数据发布过程中满足差分隐私, 可以利用差分隐私的序列组合性质.
D A 1,A 2,···,A i εi 1≤i ≤d {A 1,A 2,···,A i }εε=
d ∑i =1
εi 性质1. 差分隐私序列组合性[11]. 给定数据集，相互独立的差分隐私随机算法分别满足-
差分隐私, 其中, 则序列组合满足
-差分隐私, 其中.定义4. 互信息函数. 1948年香农提出信息熵[14]的概念, 属性之间互信息I 的大小代表属性之间的关联程度. 高维数据集D 属性节点X 与Y 之间的互信息
2021 年 第 30 卷 第 4 期
www.c-s-a
计算机系统应用
133
I 如式(5)所示.
其中, 满足差分隐私的噪音机制主要有指数机制、Laplace 机制.
∆I (X :Y )exp (εI (X :Y )
2∆I (X :Y )
)εε命题1. 基于互信息函数的指数机制. 指数机制[10]
主要用于处理输出结果为非数值型结果. 在维度转换过程中, 属性节点的关联程度作为指数机制挑选属性关系对的依据, 打分函数为属性间的互信息函数I , 其中为互信息函数I 的敏感度, 以正比于的概率挑选出具有最大依赖关系的维度属
性, 组成多个满足差分隐私的相对独立的低维属性集合.
其中文献[5]中给出了维度转换过程中互信息敏感度的计算方法, 见式(6); 由于在指数机制挑选过程中，除挑选属性关系对外无其它隐私消耗, 由差分隐私组合性质[11], 该过程满足对应-差分隐私.
P P ∗=P +Z Z ∆f Z ∼Lap (∆f /ε)∆f /ε2∆f 2/ε2ε命题2. 基于联合分布的拉普拉斯机制. 拉普拉斯机制
[11]
通过Laplace 分布产生噪声扰动真实值达到差
分隐私保护. 在贝叶斯网络中对多个相对独立的低维属性集合, 计算其联合分布. 为向其联合分布概率中添加拉普拉斯噪音, 其中为联合分布函数敏感度, 为服从尺度参数, 方差为
的Laplace 分布. 由于在该过程中除为联合分
布添加拉普拉斯噪音外无其它隐私消耗, 由差分隐私组合性质
[11]
满足对应值的差分隐私.
4 PPBA 算法
4.1 最大支撑树
本节对最大支撑树的定义和构建过程进行解释说明, 通过最大支撑树限制指数机制挑选属性关系对的候选空间.
K 命题3. 最大支撑树. 利用高维数据属性之间的互信息得到的一种树状网络结构, 通过依次计算两两属性间的互信息, 只保留与该属性具有最大互信息的属性之间的无向边, 完成最大支撑树的建立. 根据最大支撑树减少挑选属性关系对的候选空间, 确定贝叶斯网络度值.
算法1. 最大支撑树
输入: Data D VT
输出: T =∅VT =∅1. Initialize: , ;i d 2. ①for =1 to j d j i
for = 1 to and I (X i ,X j )I (X i ,X j )T Compute , add to I (X i ,X j )(X i ,X j )VT ②Select Max , add to ;
VT 3. Return ;
V T VT (X i ,X j )根据算法1输出的集合, 其中集合用于存储最大支撑树的无向边, 以图1为例将图中有向边转化为无向边, 由连接关系可知A 、B 、C 、D 四个属性节点无向边个数分别为3、3、2、2其中最大值为3, 则选取K 值为3.
4.2 个性化比例分配
本节内容主要对个性化比例分配方法所涉及的敏感性排序和比例分配的计算过程进行解释.
(1)依据动态权重值对低维属性集合进行敏感性排序
CM WV DWV 在文献[6]中分别给出了、、值的计算方法, 根据文献[6]中对属性节点动态权重值的定义,
动态权重值可以很好地代表属性节点在贝叶斯网络中的重要性, 重要性越高, 对于贝叶斯网络精确度和数据集的可用性影响越大, 该属性值隐私泄露对数据集的安全性影响越大. 故选取动态权重值作为敏感性的衡量依据.
CM 假设图1中各属性值如表2中所示, 则由文献[6]的计算方法, 对图1中4个属性权重值计算结果如表2所示.
表2 属性权重值计算结果表
i
X i M i CM WV DWV
1A ∅
150.33330.55552B A {}100.22220.15563C A B {、}120.26670.16684
D
B C {、}
8
0.1778
−0.1222
根据动态权重值大小进行排序, 则属性节点的敏感性排序为A 、C 、B 、D .
(2) 个性化比例分配计算
d 高维数据集经贝叶斯网络处理之后, 将数据集划分为个相对独立的低维属性集合, 依据属性节点的动态权重值对低维属性集合进行敏感性由大到小排序, 根据隐私预算分配策略将总的隐私预算合理分配
计算机系统应用
www.c-s-a
2021 年 第 30 卷 第 4 期
134
q (q >1)q (q >1)εε1,ε2,···,εd d 到每个低维属性集合. 通过个性化设置分配比值常数
, 从敏感性最高的低维属性集合起, 使该节点拉米夫定片
低维属性集合与前一个敏感性更高的低维属性集合分配的隐私预算大小比值为常数 , 从而将隐私预算划分为分别分配至个低维属性集合.
εq (q ≥1)由图1中属性节点的低维属性集合敏感性由大到小的排序为A 、C 、B 、D . 总隐私预算大小, 根据需要设置的比值常数为.
由等比数列性质式(7)、式(8):
得:
εq ε取=0.5时, 分别设值为1、1.1、1.3, 则A 、B 、C 、D 各属性节点分配的值由式(9), 式(10)计算结果如表3所示.
ε表3 分配表
q
A C
B D 10.16670.16670.16670.16671.10.10770.11850.13030.14331.3
0.0808
0.1050
0.1366
0.1775
q q =1q >1q q q 由以上分析和表3可知, 当给定总的隐私预算和低维属性集合按敏感性由高到低的排序, 用户只需调整值, 就可以改变隐私预算的分配方式. 当时, 每个低维属性集合分配的隐私预算相同, 即均匀分配隐私预算. 当时, 按低维属性集合排序, 每个集合分配的隐私预算以倍增加, 随着值的增加, 越重要的低维属性集合分配的隐私预算越小, 对应的保护强度越高, 数据的可用性则相应降低. 不难理解只要稍微改变
值, 就可以改变隐私预算分配方式.
4.3 PPBA 算法实现
本节描述PPBA 算法的具体实现细节如算法2.
算法2. PPBA 算法D K q ε输入: 、、、N D ∗
输出: 、N ∅V ∅1. Initialize: =,=;
X 1X 1V X 1∅N 2. Select ; add to ;add (,) to ;i d 3. ① for =2 to Ω∅② Initialize =;
X ∈A r /V ③ for 每一个属性字段, 并且(X ,M )Ω④ add to ⑤ end for
Ωexp(εi I (X i ,M i )
2∆I (X i ,M i
)
)(X i ,M i )(X i ,M i )N X i V ⑥ 从中选择使最大的; add to ;add to ;⑦ end for N 4. Return ;
N DWV 5. 依据, 计算低维属性集合属性节点的值;生抽老抽酱油的区别
DWV εi 6. 根据值, 将低维属性集合敏感性由大到小排序, 计算为每个集合分配的值i d 7. ① for =1 to do
λi =∆f
εi
P (X i |M i )② Add to ;
P ∗(X i ,M i )③ return ;④ end for D ∗
8. Return ε/2K ε/2N V V K
V min(K ,|V |)N PPBA 算法主要分为两个部分, 1–4步为算法第一部分, 实现满足-差分隐私的贝叶斯网络. 由最大支撑树确定贝叶斯网络的度值, 第2步选择具有最大权重值的属性节点作为贝叶斯网络的首节点. 第3步以互信息函数为满足-差分隐私指数机制的打分函数，从属性字段集合中选择d–1个低维属性集合对加入贝
叶斯网络, 其中用于存储属性节点, 表示的所有子集元素个数为. 第4步返回满足差分隐私的贝叶斯网络.
εq ε/2X i P (X i |M i )P ∗(X i |M i )P ∗(X i |M i )εD ∗算法第2部分, 合成满足-差分隐私的发布数据集. 5–7步根据数据可用性和安全性需求设置值, 为每个属性集合分配满足-差分隐私Laplace 机制的隐私预算. 为属性节点的条件分布加入服从Laplace 分布的噪音, 得到. 第8步根据
形成原始数据集的近似联合分布, 抽样合成
满足-差分隐私的合成发布数据集.
4.4 满足差分隐私证明
ε/2ε证明. 在PPBA 算法中, 根据命题1和命题2在指
数机制挑选属性关系对和对条件分布添加拉普拉斯噪音的过程中由差分隐私序列组合性质[11]分别满
足-差分隐私保护, 其它行为不会产生额外的隐私预算. 根据差分隐私组合性质中的序列组合性[11], 证得PPBA 算法满足-差分隐私.
黄山梦笔生花
2021 年 第 30 卷 第 4 期
台式电脑亮度www.c-s-a
计算机系统应用
135
