Page 276 - 《软件学报》2021年第12期

3940 Journal of Software 软件学报 Vol.32, No.12 December 2021

据挖掘得到的结果,必须通过支持度重构恢复原数据库中各项集的支持度,以得到跟原数据尽可能相近的挖掘
结果.
图 4(b)、图 4(d)针对真实购物篮数据,可发现当频繁项集长度不大时,不重构的误差远远大于重构误差;但
当频繁项集长度较大时(单参数随机化后 k=4,5,分组随机化 k=5),不重构的误差反而小于重构的误差.说明对于
高阶项集重构的误差大,这跟之前分析的误差随 k 增大而增大的规律一致.综合图 4,针对分组随机化,对于低阶
项集(k<5)使用重构支持度,对于高阶项集(k≥5)使用不重构支持度.
3.3.4 隐私保护对比
下面分析两种方法的隐私保护性能,从隐私保护度(定量)、个体隐私保护差异性和暴露的信息(定性)等方
面进行对比.本文隐私保护性能考虑的场景是敏感问题调查或购物时,对于敏感问题回答为“是”和“购买”敏感
物品的保护,不考虑对于敏感问题回答为“否”和“不购买”敏感物品的保护.并假定被调查者运用随机化装置给
出了真实的回答,购物数据提供者对数据进行了相应的随机化变换.
3.3.4.1 隐私保护度
文献[10]将单参数随机化 mask 的隐私保护度 privacy 定义为 1−R(p),其中,R(p)=aR 1 (p)+(1−a)R 0 (p).其中,
R 1 (p)表示原始数据库中的“1”能从随机化后的数据库中被还原的概率,R 0 (p)表示原始数据库中的“0”能从随机
化后的数据库中被还原的概率,a 为隐私保护权重.本文隐私保护场景只考虑敏感问题回答为“是”和“购买”敏感
物品记录的保护,即对如表 1 所示的 0-1 购物篮数据,只考虑“1”值的保护.设保护权重系数 a=1,则隐私保护度公
式为
privacy=1−R 1 (p) (5)
假定随机化概率为 p,项的平均支持度为 s 0 ,R 1 (p)的计算公式为
2
2
−
)
() =
Rp ps 0 + (1 p s 0 (6)
1
−
−
(1 p )(1 s 0 ) + p s 0 p − (1 s 0 ) (1− + p ) s 0
根据公式(5)、公式(6)的分析,隐私保护度 1−R 1 (p)跟 p(p>0.5)和 s 0 均成反比.说明随机化概率越大,项的平均
支持度越高,隐私保护度越低;反之亦然.极端地,当 p=1 时,数据完全保持不变,R 1 (p)=1,隐私保护度最低,为 0.
• 当 s 0 =1 时,数据是全 1 数据,R 1 (p)=1,隐私保护度也是最低,为 0.此时,无论 p 取多少,“1”均能从随机化后
的数据中被还原,随机化均无法保护数据;
• 当 s 0 =0 时,数据是全 0 数据,R 1 (p)=0,隐私保护度最高,为 1.
对于分组随机化,由于不同分组随机化概率 p 不同,所以不同分组的隐私保护度也不同.假定 w g 为第 g 个分
组个体数占总个体数的比例,p g 为第 g 个分组对应的随机化概率,R 1 (p g )为第 g 个分组中的“1”能从随机化后的数
据库中被还原的概率,privacy(g)=1−R 1 (p g )为第 g 个分组对应的隐私保护度.对于分组随机化,在已知每个分组对
应的随机化概率的条件下,定义如下 4 个隐私保护度:最低隐私保护度、最高隐私保护度、平均隐私保护度、
整体隐私保护度.
定义 1(最低隐私保护度 minPrivacy). 分组随机化中,隐私保护度最小的分组对应的隐私保护度.公式为
minPrivacy=min{privacy(g)|g=1,2,…,n} (7)
定义 2(最高隐私保护度 maxPrivacy). 分组随机化中,隐私保护度最大的分组对应的隐私保护度.公式为
maxPrivacy=max{privacy(g)|g=1,2,…,n} (8)
定义 3(平均隐私保护度 avgPrivacy). 分组随机化中,多个分组隐私保护度的平均值称为平均隐私保护度.
计算公式为
n
avgPrivacy = ∑ w privacy ()g (9)
g
g = 1
定义 4(整体隐私保护度 overallPrivacy). 将分组随机化的平均概率 p 代入公式(5),求得的隐私保护度称为
整体隐私保护度.计算公式为