面向隐私保护的数据挖掘和数据发布方法研究童云海

1、search-ms:displayname=“武”中的搜索结果&crumb=文件名：preview.mp4search-ms:displayname=“武”中的搜索结果&crumb=文件名： breach2p1 2p21 2( 2p1)( 2p1)(p 1)p 12p3 2p2 p1p1120 p 22,(p ),(p )p (1 p2)2p1p2n (2p 1) 4p 4np (2p 1)26 mask 方法 rrph 方法 取 p1=p，p2=p3，则 当rrph方法的准确性分析121 (1 p)2p1 1 12p(1 p)n(2p1)2var( 1) 2 p2p1 2np1 2 2p1(

2、1 p1)np1 2var( 2) (1 p)(1 p)4np2p2(1 p2)np1 2var( 2) 1 和 2 都是 的无偏估计量，而)122,(p (1 p)( 3p 1)2 21 p21 p pvar( 1)var( 2) 13 p 1时，var( 1) var( 2)ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用平均项集度误差（）ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用2520151050实验结果300.10.20.3 0.35 0.4 0.45 0.49 0.51 0.55 0.6 0.65 0.70.80.9maskrrph随机化参数

3、p mask方法的误差变化比较大当 p 接近 0 或 1 时，挖掘结果比较准确在 p 从 0 或 1 接近 0.5 的过程中，挖掘结果准确性显著下降 rrph方法的误差变化相对比较平稳随着 p 值从 0 增加到 1，挖掘结果的准确性不断提高2727ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用28rrph方法的优势 当时，rrph 方法比 mask 方法同时具有更好的隐私性和更高的准确性 权衡数据的隐私性和挖掘结果的准确性，我们建议在区间0.35, 0.6上选取随机化参数 p 的值，来使用rrph方法进行隐私保护的关联规则挖掘1213 p ccf yocsef 报告会：数据挖

4、掘及其在网络信息安全中的应用29朴素贝叶斯分类中的隐私保护方法 在kd3架构与流程的基础上实现 扩展的部分隐藏随机化回答（errph）方法 rrph方法在数据类型上的扩展 枚举类型的数据处理和特征重构方法 转换的随机化回答（trr）方法 数值类型的数据处理和特征重构方法 分类挖掘中基于errph和trr的隐私保护方法 实现了完整的朴素贝叶斯分类算法 同时支持分类属性和连续值属性的数据ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用30讨论内容 面向隐私保护的数据挖掘方法 研究背景和问题描述 体系架构和评估体系 关联规则挖掘中的隐私保护方法 面向隐私保护的数据发布方法 研究背景和

5、问题描述 面向微数据发布的身份保持的k-匿名ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用31数据发布中的隐私保护 核心问题：在保护隐私的前提下，发布较为准确的数据 统计数据库把数据发布分为三种类型 微数据：指包含个体信息的数据； 聚集数据：指汇总之后的各项分类的统计数据； 其他统计数据：包括其他各种类型的总体描述，比如回归因子、相对指数等。ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用32我们研究的重点 微数据发布场景 分析单一个体对应多个记录的情况，提出了身份保持的匿名模型 分析动态数据发布的场景和隐私推理途径，提出了t-rotation模型处理动态数据

6、 联机分析处理(olap)中的数据保护 基于度量的olap数据隐私保护方法 基于维度的olap数据隐私保护方法ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用33问题提出 很多部门和单位（例如：医院）需要发布一些数据表。包含个体信息的表称为微数据（microdata） 微数据是记录个人信息的数据 身份标识属性（individually identifying attribute ，简称id ）：记录了可以唯一识别个人的取值，比如身份证号、电话号码、姓名等信息 准标识属性（quasi-identifiers，简称qi）：记录了对个人的一些类型属性的取值，比如性别、所在的邮政编码、

7、出生日期等 敏感属性（sensitive attribute，简称st）：记录了个人不愿为人所知的取值信息，比如个人收入、所患病症等ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用34问题提出：微数据发布场景 为了提供研究，医院发布了一个病人情况表 简单的方法：去掉“身份标识属性”publishccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用35连接推理发布表quasi-identifier (qi) attributes选民登记表an adversaryccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用36连接推理 swe00的研究表明，87的美

8、国人口信息可以通过性别、出生日期、5位邮政编码进行个人重建 我们研究了宁波城区中的居民数据，得到了类似的结论 78的人口可以通过出生日期和6位邮政编码唯一确定 58的人口可以通过出生日期和5位邮政编码唯一确定ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用37问题定义(1) 设数据集的模式：t=id1，idr，qi1，qis，st1，stt idi (i=1，2，r)：身份标识属性 qij (j=1，2，s)：准标识属性 stk (k=1，2，t)：敏感属性 为了保护个人隐私，发布数据集需要设定一个隐私保护需求 为了达到隐私保护需求，需要对数据集t中的元组t进行转化得到t，设转

9、化函数为fccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用38问题定义(2) 对转化函数f 设t=( d1，dr，q1，qs，s1，st)，f把t转化为t( d1，dr，q1，qs，s1，st)，即t=f(t)。 通常在微数据发布处理方法中，f并不修改敏感属性的取值，即sk=sk，(k=1，2，t) 对于需要处理的数据集t，转化函数f把t转化为发布数据集pt，其中pt=f(t)|tt。转化后( q1，qs)取值相同的那些元组形成一个qi分组。 为了尽量准确地评价发布数据，需要建立评价指标，设为ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用39问题定义(3) 隐

10、私保护的数据发布问题可以表示为一个四元组ppdp=（t，f，） t是需要发布的数据集，发布的数据集为ptf(t)|tt 是隐私保护需求f 是转化函数 是对发布数据集的评价结果 隐私保护的数据发布问题就是在满足隐私保护需求的前提下，最大化数据有效性指标 实现隐私信息的合理保护和获得数据信息的最大效用抑制隐私保护需求评价指标ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用记录处理k-匿名l-多样化(,k)-匿名背景知识隐私攻击待发布表中间表属性处理发布表外部表40处理的基本框架概化有损分解ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用41相关研究工作 隐私保护需求

11、k-anonymity (tkde01)l-diversity (icde06)(,k)-anonymity (kdd06)t-closeness (icde07)个性化隐私 (sigmod06) 转化方法单维概化 (tkde01)多维概化 (icde06)有损连接 (vldb06)空间索引 (vldb07,vldb07)ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用42相关研究工作 评价指标 概化比例dr (kdd02) 可识别性dm (icde05) 确定性代价ncp (kdd06) 隐私攻击 minimality attack (vldb07) privacy skyl

12、ine (vldb07)ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用43隐私保护需求 研究者提出了多种隐私保护需求 k-anonymity：每个qi分组中至少包含k个元组 l-diversity：每个qi分组中的敏感属性至少有l个不同的取值 (,k)-anonymity：每个qi分组中的每个敏感属性取值的概率不超过,并且每个qi分组中至少包含k个元组 t-closeness 4 qi 分组ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用44anonymous）qi 属性st属性隐私保护需求：k-anonymity 具有相同的准标识属性组(qi)的元组至少有k

13、个（2-ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用45数据转化方法：概化 概化关系d ：设两个域di，dj，|dj| |di|，dj称为di的一个概化，如果对任何一个didi，都存在djdj，dj是di的概化。ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用46数据转化方法：有损分解 有损分解 设数据表t，属性集agid qi st，其中gid属性用于记录每个元组分组之后的分组标号，qi是准标识属性集合，st是敏感属性集合。 将表t分解为两个表stt和qit进行发布 qitgid qi sttgid st23m 1pneumonia35591dyspeps

14、ia6565qit表47有损分解方法 发布表变成两张表，类标识属性表(qit)和敏感属性表（stt）count2221221age sex23 m27355961mmmf13000590001200054000656570fff250002500030000gastritisstt表agezipcode11000diseasegroup-id diseasesex zipcodegroup-id1100027m 1m 11m 21300059000120001dyspepsia dyspepsiapneumonia2 bronchitispneumonia flu61f 2f 2f 25400

15、02500025000flugastritisflu70f30000bronchitismicrodataccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用47ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用48身份保持的匿名 现有的匿名方法只考虑每个个体只出现一次的情况不考虑身份标识属性，直接删除大量信息损失,只保留qi与st的关系，没有保留st之间的关系可能带来部分元组敏感属性的隐私保护度降低ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用49身份保持的匿名 四元组ppdp=（t，f，）中，设t=( d1，dr，q1，qs，s1，st) 现有方

16、法中，f把t转化为t(q1，qs，s1，st) 身份保持的匿名中，t( d，q1，qs，s1，st)，其中d是重编码后的身份属性取值，多个身份属性只保留一个即可。 身份保持的匿名 考虑了单一个体出现多次的情况 提高信息有效性，保留qi与st的关系以及st之间的关系 是现有方法的一般形式ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用50隐私保护需求 身份保持的隐私保护需求 identity-reserved k-anonymity：每个准标识属性分组中至少有k个不同的个体 identity-reserved (k,l)-anonymity：每个准标识属性分组中至少有k个不同的个

17、体，并且敏感属性取值不少于l个 identity-reserved (,)-anonymity：每个准标识属性分组中任何个体所占频率不超过，每个敏感属性取值频率不超过ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用51数据转化方法 属性处理方法 原有的方法就是简单删除身份属性 对身份属性进行处理 选择一个身份属性进行随机化重编码 删除其他身份属性 匿名实现方法 概化 有损分解ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用52数据转化方法：概化 单维全子树重编码不要求同一属性的取值概化到相同层次 提出一种自底向上的全子树重编码算法检查所有元组，将满足匿名要求的元

18、组添加上分组标号选择一个准标识属性进行概化，检查还没有分组的元组，将满足匿名要求的元组添加上组标号这一过程重复下去，直到所有元组都被添加了组标号或者剩余元组的数目达不到匿名要求（比如当k=7时，剩余5个元组）对于这些剩余的元组，进行迁移和合并的方法进行处理ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用53要求身份保持的2-匿名要求身份保持的（0.5,0.5）-匿名ccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用54数据转化方法：有损分解 有损分解方法发布两张表，一张是准标识属性表qit，另一张是敏感属性表stt qit包含了准标识属性的原始取值和分组标号 st

19、t包含3个属性：身份属性id，敏感属性st和分组标号 有损分解的实现基于概化算法 对身份标识属性重编码 采用概化算法，得到满足身份保持的匿名表t 将t 的准标识属性投影到qit中，同时把每个元组对应的分组号填入到分组标号属性中，然后删除重复的记录 将t的id和敏感属性取值投影到stt中，同时把每个元组对应的分组号填入到分组号属性中55qit要求身份保持的2-匿名sttccf yocsef 报告会：数据挖掘及其在网络信息安全中的应用55vulnerable group ratioccf yocsef 报告会：数 k value其在网络信息安全中的应用据挖掘及56实验与分析(1) 实验数据来自于uci的美国人口数据样例库 定义单一个体的平均元组数作为衡量个体的重复程度，记为rpi元组总数/个体总数。 普通k-匿名方法在rpi1时，隐私保护度降低