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

欧阳佳  等:面向频繁项集挖掘的本地差分隐私事务数据收集方法                                                  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)为
   214   215   216   217   218   219   220   221   222   223   224