Page 221 - 《软件学报》2021年第11期

欧阳佳 等:面向频繁项集挖掘的本地差分隐私事务数据收集方法 3547

算法 1. TDC_CLDP_Cand 算法.
输入:用户的事务数据 t,所有候选项集 CandI.
输出:扰乱后的事务数据 t′.
1: for s∈CandI do:
2: //计算 t 与每个候选项集 s 的分数
α
−⋅ dist (, )t s
3: score ()s = e 2
4: end for
5: 随机选择一个候选项集 t′,其概率为
score ()s′
6: Pr[ is sampled]s′ =
∑ s CandI∈ score () s
7: return t′
3.2 TDC_CLDP算法
TDC_CLDP_Cand 算法存在的主要问题是候选项集的样品空间随着项集域的大小 d 呈指数级增长,导致时
间复杂度非常高.本文基于 TDC_CLDP_Cand 提出 TDC_CLDP 算法,该算法是对 TDC_CLDP_Cand 的具体实现,
其优点是可以避免直接从候选项集的样品空间中进行抽样.TDC_CLDP 方法见算法 2.
算法 2. TDC_CLDP 算法.
输入:用户的事务数据 t∈D,|t|≤m,项集域 I={a 1 ,…,a d },隐私参数α,输出的事务数据长度 k.
输出:扰乱的事务数据 t′,|t′|=k,且满足α-CLDP.
1: t′=∅,d=|I|
2: Z对 t 作等长处理

3: t = , t I = { ,...,a 1 a d } {a∪ d + 1 ,...,a d m+ } , //已有项集域的项为 a 1 ,…,a d ,补充的项为 a d+1 ,…,a d+m ,属于噪音项.
4: for i=0; i<m−|t|; i=i+1 do:

5: t =∪ a di++ 1
t
6: end for

7: Z对 t 作随机化处理
− α 0 ⋅ k ⎛ − α ⋅ (k − inter ) ⎞
8: Ω = e 2 ⋅ C + k ∑ e ⎜ 2 ⋅ (C inter ⋅ C k − inter )⎟ //*部分表示相似度为 0,**部分表示相似度大于 0
inter= 1 ⎝ ⎜ m d ⎟ ⎠
d
*
**
9: r=uniform_random(0.0,1.0)
10: inter=0
− α ⋅ 0 C k
11: p = e 2 ⋅ d //相似度为 0 的候选项集被选中的概率
Ω
12: while p<r do:
13: inter=inter+1
− α ⋅ (k inter )
−
1 inter
e 2 ⋅ (C inter ⋅ C k −− )
14: p = p + m d − 1 //相似度大于 0 的候选项集被选中的概率
Ω
15: end while

16: t′ t′ =∪ sample (,in rt te ) //以等概率方式从 t 中不放回随机抽取 inter 个项,这部分为保留的真实数据

17: t′ t′ =∪ sample (I − t ,ki− nte ) r //以等概率方式从 I − 中不放回随机抽取 k−inter 个项,这部分为引入
t
的噪音数据
18: return t′