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

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

2 分组随机化与挖掘方法

2.1 分组随机化
GR-PPFM 分组随机化的基本思想是由参与调查的个体自行决定对其数据的隐私保护级别和相应的随机
化参数,隐私保护级别差不多的分为一组,同一组内共用同一个随机化参数,可表示为如下形式:
1 w w 2 w n 1 w w 2 w n
pp
12 ... n p
DD ...D ⎯⎯⎯⎯→ D D′ ′ ...D′ ,
1
n
n
2
1
2
D D′
其中,原始事务集 D 由 N 个事务(个体)的 m 个项构成二维 N×m 布尔矩阵(数值属性可通过离散化变为分类属性,
而分类属性又可变为布尔属性,即一般数据都可变为二维布尔矩阵形式).D 1 ,D 2 ,…,D n 为 D 中的 n 个数据分组,
分组中的个体数占总个体数|D|=N 的比例分别为 w 1 ,w 2 ,…,w n (0<w g <1,g∈{1,...,n}).此 n 个数据分组分别以 p 1 ,
p 2 ,…,p n 的概率进行随机化,生成随机化后的数据分组 DD′ , ′ ,...,D′ ,共同组成频繁模式挖掘所用的事务集 D′.每
1 2 n
个 D g 的随机化都遵循单参数随机化的基本过程,即:对该分组对应的 N×m 矩阵中的所有 0-1 元素,均以 p g 的概
率取原值,以 1−p g 的概率取反.单参数随机化使用随机化参数 p 与 1−p 具有对等效果(隐私保护度和挖掘结果准
确性关于 p=0.5 对称,p=0.5 隐私保护能力最强,但误差无穷大),故以下假定随机化参数均大于 0.5.
表 1 给出了个体分组随机化的例子.表的左边为原始事务集,由 10 个被调查者的 4 个问题项(I 1 /I 2 /I 3 /I 4 )组
成,10 个被调查者分为 5 组,分别包含 3 个、2 个、2 个、2 个、1 个被调查者.同一组内隐私保护需求相同,对应
的随机化参数分别为 1,0.9,0.8,0.7,0.6.表的右边为分组随机化后的数据集,其中,前 3 行为第 1 组数据,这 3 名被
调查者完全不考虑隐私保护,愿意全部贡献原始数据,随机化概率参数 p 1 =1;相反,由被调查者 10 构成的第 5 组
数据非常在乎隐私,选择的随机化参数 p 5 =0.6,其数据随机化时以 0.6 的概率保持不变,以 0.4 的概率取反.得到的
最后一条记录中,有 2 个值保持不变、2 个值取反.被调查者 4-5,6-7,8-9 的隐私保护需求介于第 1 组和第 5 组之
间,随机化参数在 0.6 到 1 之间.
Table 1 Grouping randomization of with GR-PPFM method
表 1 GR-PPFM 方法分组随机化
TID items I 1 I 2 I 3 I 4 items I 1 I 2 I 3 I 4
1 (p 1=1) I 1I 3 1 0 1 0 I 1I 3 1 0 1 0
2 (p 1=1) I 1I 2 1 1 0 0 I 1I 2 1 1 0 0
3 (p 2=1) I 3I 4 0 0 1 1 I 2I 3I 4 0 0 1 1
4 (p 2=0.9) I 2I 4 0 1 0 1 分组 I 2I 4 0 1 0 1
5 (p 3=0.9) I 1I 2I 3I 4 1 1 1 1 随机化 I 1I 2I 3 1 1 1 0
6 (p 3=0.8) I 4 0 0 0 1 ――→ I 3I 4 0 0 1 1
7 (p 4=0.8 I 1I 2 1 1 0 0 I 1I 2I 4 1 1 0 1
8 (p 4=0.7) I 1I 2I 4 1 1 0 1 I 2I 4 0 1 0 1
9 (p 5=0.7) I 2I 4 0 1 0 1 I 1I 4 0 0 0 1
10 (p 5=0.6) I 2I 3I 4 0 1 1 1 I 2I 4 0 1 0 0
GR-PPFM 方法采用分组多参随机化,允许对不同的人群使用不同的随机化参数,问题和挑战在于:
(1) GR-PPFM 对不同个体采取不同的随机化参数后,能像单参数随机化 mask 一样重构出原始事务集中
各项集的支持度吗?如何重构呢?第 2.2 节针该问题给出解决方法;
(2) GR-PPFM 能从个体分组多参随机化模型中,得到真正的益处吗?第 3 节实验评价将针对该问题作答.
2.2 支持度重构
2.2.1 基本原理
设 I={I 1 ,I 2 ,...,I m }是一组项的集合,D={T 1 ,T 2 ,...,T N }为事务数据库,其中,事务 T u (u∈{1,2,…,N})为 I 的子集.项
集 A⊆I 的长度|A|是指 A 中项的个数,如果|A|=k,则称 A 为 k-项集.项集 A 在 D 中的支持计数(简称支持数)是指 D
中包含 A 的事务数,记作 support_count(A)或 S A ,S A =|{T u |A⊆T u ,T u ∈D}|.同时,将 D 中恰等于 A 的事务数,称作项集
A 在 D 中的净计数,记作 C A ,C A =|{T u |A=T u ,T u ∈D}|.
假定 A={I 1 ,I 2 ,…,I k }为 k-项集,根据 mask 方法支持度重构原理,只要给出 k-项集 A 的变换概率矩阵 P k =[p ij ],