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

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

在提供个人数据时会感到不安,有时拒绝提供数据或提供假数据.如何在保护好个人数据隐私的同时实施频繁
[2]
模式、关联规则等挖掘任务,是隐私保护数据挖掘(privacy preserving in data mining,简称 PPDM) 要解决的重
要问题,其目标是在不精确访问个体隐私数据的情况下,仍能挖掘到精确的结果.
(1) 相关工作
[3]
随机化回答 RR(randomized response)最先由 Warner 在 1965 年针对二元敏感性问题调查提出 ,称为沃纳
模型.文献[4]提出了分层沃纳模型,但分层沃纳模型解决的仍是单属性敏感问题的调查,且敏感属性是二元变
量.文献[5]使用“风险-效用”映射(risk-utility,简称 R-U)比较了不同的随机化策略,提出了用于单一布尔属性的最
优随机化策略.文献[6]利用多目标优化方法,针对单一多元分类属性,力图寻找接近于最优随机化的变换概率矩
阵.文献[7]提出了针对多个敏感属性的随机化回答技术.文献[8]通过不相关问题随机化回答技术估算多个混合
类型敏感属性的依赖关系,其中,混合类型敏感属性包括你是否抽烟、是否有经济负担等二元分类属性,还包括
睡眠质量、手机对学业的影响度等量化数值属性.Du 等人基于随机化回答技术实现了布尔类型数据的隐私保
[9]
护决策树分类 .不同文献的区别包括属性类型(二元、多元、量化数值)、属性数量(单属性、多属性)、目标(简
单统计、相关性分析、决策树)、随机化问题(正/反问题、正/不相关问题)等.
随机化回答是隐私保护频繁模式和隐私保护关联规则挖掘中的主要方法 [10−14] .文献[10]提出了基于随机
化回答的隐私保护关联规则挖掘方法 mask(mining associations with secrecy konstraints),mask 随机化过程只有
一个参数 p,其基本思想是:对布尔数据中所有的“1”“0”值,以 p 的概率保持不变,以 1−p 的概率取反.文献[11]针
对数据中“1”“0”敏感度不同的问题提出了 emask 算法,该算法对“1”“0”设置两个不同的随机化参数 p 1 和 p 2 ,
emask 随机化时,对所有的“1”值,以 p 1 的概率保持不变,以 1−p 1 的概率取反;而对“0”值,则以 p 2 的概率保持不变,
以 1−p 2 的概率取反.从而使“1”“0”拥有不同的保护级别.文献[12]对 mask 支持度重构进行了性能优化,提出了
mmask 算法.文献[13,14]针对不同属性需要不同保护的场景,提出了“非统一”参数的隐私保护关联规则 RE
(recursive estimation)算法.文献[15]提出了属性分组的随机化方法,实现隐私保护关联规则挖掘.近些年流行的
差分隐私保护 [16−18] 通过在数据分析过程或结果中添加随机噪音,确保在数据库中插入或删除任意一条记录都
不会显著影响数据分析结果,随机化回答是差分隐私的一种变体 [17] .
(2) 本文动机
本文动机来自于两方面:一是文献[13],二是客观存在的不同人群隐私保护需求的差异性.
文献[13]RE 算法认为:“性别”“年龄”和“收入”等不同属性的敏感度是不同的,应设置不同的随机化参数,使
其拥有不同的隐私保护度.既然不同属性都需要不同保护,那不同个体是否需要不同保护呢?
[1]
AT&T 实验室 1999 年调查了 Internet 用户对隐私保护的态度,结果显示 :17%的用户对隐私保护极端重视,
56%的用户对隐私保护中度重视,其余 27%的用户对隐私保护不重视.以上事实说明,不同人群对隐私态度和对
隐私信息的保护需求是有差异的.然而,已有的隐私保护频繁模式挖掘方法没有考虑不同人群的隐私保护需求
差异性,在对个体数据随机化时,运用统一的随机化参数对所有人实施同等的保护,无法满足个体对隐私的偏好
和具体保护需求,造成的结果是对一部分人的隐私保护程度不足,而对另一部分人实施了过度保护.个性化隐私
保护 [18−21] 应运而生.文献[18]提出一种个性化的差分隐私保护系统.文献[19]面向个性化的隐私保护数据发布.
文献[20]提出一种精细化的个性化隐私保护框架.文献[21]提出一种个性化的隐私保护问题调查统计方法,与本
文工作相似,它允许用户抽取自己的概率对答案进行干扰.然而,文献[21]的问题和应用场景与本文不同,文献
[21]针对在线问题调查,而非频繁项集挖掘.
基于以上事实,本文在我们提出的 P N/g 模型 [22] 的基础上,提出一种基于个体分组多参随机化的隐私保护频
繁模式挖掘方法 GR-PPFM(grouping-based randomization for privacy preserving frequent pattern mining).在
GR-PPFM 架构中,当人们参与数据调查提交自己的数据时,可以根据各自偏好进行分组,每一组数据设置不同
的隐私保护级别,进行差异化的隐私保护.本文是我们在文献[22]工作的延续.文献[22]针对 P N/g 模型,总人数为
N,组数为 g,每一分组的人数相同,均为 N/g .文献[22]通过简单的例子,手工计算探索了支持度重构的可行性,但没
有公式推导、算法设计和实验评价.此外,本文的分组随机化是文献[22]P N/g 模型的更一般情况,分组内人数可以