分组随机化隐私保护频繁模式挖掘-郭宇红，童云海，苏燕青.pdf

上善若水

279

16页

0次

2022-05-26

免费下载

软件学报 ISSN 1000-9825, CODEN RUXUEW E-mail: jos@iscas.ac.cn

Journal of Software,2021,32(12):3929−3944 [doi: 10.13328/j.cnki.jos.006101] http://www.jos.org.cn

分组随机化隐私保护频繁模式挖掘

∗

郭宇红

童云海

苏燕青

(国际关系学院网络空间安全学院,北京 100091)

(北京大学智能科学系,北京 100871)

通讯作者: 郭宇红, E-mail: yhguo@uir.cn

摘要: 已有的隐私保护频繁模式挖掘随机化方法不考虑隐私保护需求差异性,对所有个体运用统一的随机化参

数,实施同等的保护,无法满足个体对隐私的偏好.提出基于分组随机化的隐私保护频繁模式挖掘方法 (grouping-

based randomization for privacy preserving frequent pattern mining,简称 GR-PPFM).该方法根据不同个体的隐私保护

要求进行分组,为每一组数据设置不同的隐私保护级别和与之相适应的随机化参数.在合成数据和真实数据中的实

验结果表明:相对于统一单参数随机化 mask,分组多参数随机化 GR-PPFM 不仅能够满足不同群体多样化的隐私保

护需求,还能在整体隐私保护度相同情况下提高挖掘结果的准确性.

关键词: 分组;随机化;个性化;隐私保护;频繁模式挖掘

中图法分类号: TP309

中文引用格式: 郭宇红,童云海,苏燕青.分组随机化隐私保护频繁模式挖掘.软件学报,2021,32(12):3929−3944. http://www.

jos.org.cn/1000-9825/6101.htm

英文引用格式: Guo YH, Tong YH, Su YQ. Privacy preserving frequent pattern mining based on grouping randomization. Ruan

Jian Xue Bao/Journal of Software, 2021,32(12):3929−3944 (in Chinese). http://www.jos.org.cn/1000-9825/6101.htm

Privacy Preserving Frequent Patter n Mi ning Ba sed o n Grouping Ra ndomi zatio n

GUO Yu-Hong

, TONG Yun-Hai

, SU Yan-Qing

(School of Cyber Science and Engineering, University of International Relations, Beijing 100091, China)

(Department of Machine Intelligence, Peking University, Beijing 100871, China)

Abstra ct : Existing randomization methods of privacy preserving frequent pattern mining use a uniform randomization parameter for all

individuals, without considering the differences of privacy requirements. This equal protection cannot satisfy individual preferences for

privacy. This study proposes a method of privacy preserving frequent pattern mining based on grouping randomization (referred to as

GR-PPFM). In this method, individuals are grouped according to their different privacy protection requirements. Different group of data is

assigned to different privacy protection level and corresponding random parameter. The experimental results of both synthetic and real-

world data show that compared with the uniform single parameter randomization of mask, grouping randomization with multi parameters

of GR-PPFM can not only meet the needs of different groups of diverse privacy protection, but also improve the accuracy of mining

results with the same overall privacy protection.

Key words: grouping; randomization; personalization; privacy preserving; frequent pattern mining

频繁模式挖掘应用广泛,比如:医学研究人员希望通过分析医学普查数据,发现疾病间的关联,获取并发症

等病学知识

[1]

——例如患糖尿病的人通常伴随着冠心病和高血压.然而在数据普查时,出于隐私的考虑,许多人

∗ 基金项目: 国家自然科学基金(60403041); 中央高校基本科研业务费专项资金(3262017T48, 3262018T02)

Foundation item: National Natural Science Foundation of China (60403041); Fundamental Research Funds for the Central

Universities (3262017T48, 3262018T02)

收稿时间: 2019-08-28; 修改时间: 2019-12-24, 2020-04-04; 采用时间: 2020-06-16

3930

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

在提供个人数据时会感到不安,有时拒绝提供数据或提供假数据.如何在保护好个人数据隐私的同时实施频繁

模式、关联规则等挖掘任务,是隐私保护数据挖掘(privacy preserving in data mining,简称 PPDM)

[2]

要解决的重

要问题,其目标是在不精确访问个体隐私数据的情况下,仍能挖掘到精确的结果.

(1) 相关工作

随机化回答 RR(randomized response)最先由 Warner 在 1965 年针对二元敏感性问题调查提出

[3]

,称为沃纳

模型.文献[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

和 p

emask 随机化时,对所有的“1”值,以 p

的概率保持不变,以 1−p

的概率取反;而对“0”值,则以 p

的概率保持不变,

以 1−p

的概率取反.从而使“1”“0”拥有不同的保护级别.文献[12]对 mask 支持度重构进行了性能优化,提出了

mmask 算法.文献[13,14]针对不同属性需要不同保护的场景,提出了“非统一”参数的隐私保护关联规则 RE

(recursive estimation)算法.文献[15]提出了属性分组的随机化方法,实现隐私保护关联规则挖掘.近些年流行的

差分隐私保护

[16−18]

通过在数据分析过程或结果中添加随机噪音,确保在数据库中插入或删除任意一条记录都

不会显著影响数据分析结果,随机化回答是差分隐私的一种变体

[17]

(2) 本文动机

本文动机来自于两方面:一是文献[13],二是客观存在的不同人群隐私保护需求的差异性.

文献[13]RE 算法认为:“性别”“年龄”和“收入”等不同属性的敏感度是不同的,应设置不同的随机化参数,使

其拥有不同的隐私保护度.既然不同属性都需要不同保护,那不同个体是否需要不同保护呢?

AT & T 实验室 1999 年调查了 Internet 用户对隐私保护的态度,结果显示

[1]

: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

模型的更一般情况,分组内人数可以

of 16

免费下载

软件学报计算机技术

关注

评论