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

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

录、包含 URL 的点击流等等.对事务数据可以进行各种数据挖掘任务,如关联规则挖掘、用户行为预测、推荐
系统、信息检索等其他基于 WEB 的相关应用.其中应用最广泛、最典型的是频繁项集挖掘.项的集合称为项集,
包含 k 个项的项集称为 k-项集.项集的支持计数是指项集的出现频率,即包含项集的事务数.频繁项集是指支持
计数大于等于设定的最小支持计数的项集.
Table 1 Example of transaction data
表 1 事务数据示例
交易 ID 购买物品
T100 牛奶,面包,火腿
T200 面包,辣椒酱
T300 面包,鸡蛋
T400 牛奶,面包,辣椒酱
T500 牛奶,鸡蛋

2.2 本地差分隐私(local differential privacy,简称LDP)

差分隐私(differential privacy,简称 DP)假设可信的数据收集者不会窃取或泄露用户的隐私信息,然而实际
应用中,这种假设并不成立.特别是当前数据即价值的时代,在利益的驱使下,用户的隐私信息很难得到保证.因
此,本地差分隐私模型(LDP)应运而生,每个用户基于 LDP 对拥有的数据进行随机化,然后将随机化后的数据发
送给数据收集者,即数据收集者无法直接访问用户的真实数据,这就从根源上保证了用户的信息安全.形式上,
*
令 D 代表数据集,ℜ为随机算法,其输入为数据 t,输出为 t ,LDP 形式定义如下.
定义 1(ε-本地差分隐私 [22] ). 一个随机算法ℜ满足ε-本地差分隐私要求,当且仅当对于任意的输入 t 与 t′以及
*
对于任意的输出 t ,下面的不等式成立:
*
*
ε
Pr[ℜ(t)=t ]≤e ×Pr[ℜ(t′)=t ] (1)
*
直观意义上,当得到的结果为 t ,数据收集者无法以很高的置信度(通过ε控制)推断出输入数据是 t 还是 t′,
这点与中心差分隐私有根本的区别,中心差分隐私的输入为只相差一条数据的邻近数据集.
随机响应(randomized response,简称 RR)技术是一种主流的扰动机制,数据收集者在没有得到用户真实值
的情况下,同样能准确地获得相应的统计信息.
2.3 压缩的本地差分隐私(condensed local differential privacy,简称CLDP)

令 U 定义为所有可能的值(或项),定义函数 d:U×U→[0,∞)为距离度量函数,其输入为两个值:v 1 ,v 2 ∈U.函数 d
的结果用来度量这两个值的距离,要求函数 d 满足以下性质:非负性、同一性、对称性、三角不等式等.基于该
函数,CLDP 有如下定义.
定义 2(α-压缩的本地差分隐私 [34] ). 当α>0 时,一个随机算法Φ满足α-CLDP,当仅且当对于任意的输入
v 1 ,v 2 ∈U,
Pr[ ( )vΦ = ] y
∀∈ Range () :Φ 1 ≤ e α⋅ ( dv 12 )v⋅ (2)
y
Pr[ ( )vΦ 2 = ] y
其中,Range(Φ)代表随机算法Φ所有可能的输出.
从定义中可以发现,CLDP 的隐私性由参数α以及项之间的距离进行控制,本质上是对 LDP 引入距离的概
念.特别地,当任意两个项之间的距离为 1 时,即 d(v 1 ,v 2 )=1,令α=ε,则 CLDP 就退化成 LDP.可见,LDP 是 CLDP 的
一种特殊情形.
2.4 隐私攻击模型(threat model)

本地差分隐私机制的主要目的是对用户的隐私数据提供保护.尽管如此,不可信的第三方数据收集者仍然
可以从扰乱的数据集中推断出用户真实的隐私信息.攻击者观察到完整的扰乱数据 y 后,则最坏情况下推断出
用户真实数据的最大后验置信度(maximum posterior confidence,简称 MPC)为