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

3550 Journal of Software 软件学报 Vol.32, No.11, November 2021

由于本文采用了不同的隐私模型 CLDP 与距离函数,因此 TPR 与 FPR 与文献[2]是完全不同的,推导过程的
原理也不同,是两种不同的方法,是对 PrivSet 方法的改进.接下来分析如何对项的支持度计数进行估计.
考虑项 a i ∈I 以及含有 n 个用户的事务数据集 D={t 1 ,t 2 ,t 3 ,…,t n },数据收集者得到的事务数据集为
′′
D′ = { , , ,..., }.t t t′ 3 t′
1
n
2
假设其真实的项分布为 P = {P P P ,...,P } ,则 a i 在隐私事务数据 t′的期望频率为
,
,
a 1 a 2 a 3 a d a
⋅
=
[ EF ] = E [#{ | t a ∈ ′ t′ }] n P TPR n ⋅ ⋅ + (1 P ⋅ − ) FPR (21)
i a i i i i a i a
其中,前半段 nP TPR⋅ ⋅ 表示保留下来真实的 a i ,而后半段 n ⋅ (1 P− ) FPR⋅ 代表噪音.因此, P 可以估计为
i a i a i a
1 F −⋅
n FPR
P = ⋅ i a (22)
−
i a n TPR FPR

P 是对 P a 的无偏估计,证明过程如公式(23)所示.
a
n FPR ⎤
[] =
⋅
EP a E ⎡ ⎢ 1 F −⋅ ⎥ = n ⋅ 1 − ⋅ [ E F − a ] FPR
a
−
n TPR FPR ⎦ − ⎣ (TPR FPR ) TPR FPR (23)
⋅
= 1 ⋅ {nP TPR n ⋅ + (1 P ⋅ ) FPR − } FPR = P
⋅
−
−
n ⋅ (TPR FPR ) a a TPR FPR a
−

其中, F 为数据收集者得到 D′统计得到.本文采用文献[2]提出的频数估计算法统计 F 并进一步得到 P ,见算
i a i a i a
法 3.注意:其中,FPR 与 TPR 不同于文献[2].
算法 3. 频数估计算法.
输入:数据收集者得到的 D′ { , , ,..., }.t t t ′ = ′ ′ t′
1 2 3 n
输出:项的频率分布估计 P = {P P P ,...,P }.
,
,
i a 1 a 2 a 3 a d a
1: P = {0} ,F = ||I {0} ,
||I
a a
2: for t′∈D′ do:
3: for a i ∈t′ do:
4: F = F + 1 //从 D′中统计每个项的频率
i a i a
5: end for
6: end for
7: for i=1 to |I| do:
1 F −⋅
n FPR
i a
8: P = i a n TPR FPR
⋅
−
9: end for

10: return P
a
4 理论分析与隐私参数设置
本节首先分析项的频数估计的错误边界,该边界是 TDC_CLDP 中设置 k 的重要依据,过程与文献[2]类似,
但本文对整个推导过程做了更详细的说明;其次,考虑到最大后验置信度的攻击模型,本文通过约束 MPC 的上
界为ρ,找到了 CLDP 的隐私参数α与ρ的关系,由于参数ρ的设置具有启发式意义,即限定攻击者的攻击能力的上
界,因此提出一种基于ρ的隐私参数启发式设置策略.
4.1 项的频数分布估计的错误边界
基于项的 TPR 与 FPR,接下来分析项分布估计的均方差(mean squared error,简称 MSE).考虑一个项 a i ,公式

(22)中的随机变量 P 是 F a 的线性变换,而 F a 又是 n 个伯努利随机变量之和,其中,n⋅P a 是伯努利实验中以概率
a
TPR 成功的数目,而 n−n⋅P a 是伯努利实验中以概率 FPR 成功的数目.又因为重复 n 次独立的伯努利实验的方差
2
2
为 Var(X)=E(X )−E(X) =n⋅p⋅(1−p),其中,p 为实验成功的概率,则 F a 的方差为
Var(F a )=n⋅P a ⋅TPR⋅(1−TPR)+(n−n⋅P a )⋅FPR⋅(1−FPR) (24)