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

《面向隐私保护的数据挖掘和数据发布方法研究(童云海).ppt》由会员分享，可在线阅读，更多相关《面向隐私保护的数据挖掘和数据发布方法研究(童云海).ppt（59页珍藏版）》请在三一文库上搜索。

1、search-ms:displayname=“武”中的搜索结果&crumb=文件名：preview.mp4search-ms:displayname=“武”中的搜索结果&crumb=文件名：preview.mp4%20OR%20System.Generic.String：preview.mp4&crumb=location:C%3A%5CUsers%5Cnana%5CDesktop%5C武%20OR%20System.Generic.String：preview.mp4&crumb=location:C%3A%5CUsers%5Cnana%5CDesktop%5C武,面向隐私保护的数据挖掘和数

2、据发布方法研究,Privacy Preserving Data Mining and Data Publishing,March 2012,Yunhai Tong（童云海）,School of Electronics Engineering and Computer Science,Peking University,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,2,讨论内容 面向隐私保护的数据挖掘方法 研究背景和问题描述 体系架构和评估体系 关联规则挖掘中的隐私保护方法 面向隐私保护的数据发布方法 研究背景和问题描述 面向微数据发布的身份保持的K-匿名,CCF YOCSE

3、F 报告会：数据挖掘及其在网络信息安全中的应用,3,隐私问题的产生 信息技术的飞速发展让各类数据的采集、存储、 使用变得方便快捷, 医院信息管理系统（电子病例） 人口管理系统（市民卡） 金融业务系统（银行卡）, ,病人基本信息、疾病信息、医 疗服务与药品购买记录 市民家庭住址、收入状况、个 人爱好、犯罪记录 客户私有信息及其交易行为,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,4,数据分,密码学,隐私保护方法的研究 通过多用户、多权限、多 层次的资源访问控制策略， 实现对隐私数据的安全存,数据库 安全信 息安全 隐私保护 统计学,利用有效的加密算 法对隐私数据进行 加密，

4、再通过有效 的解密算法实现数 据的访问和使用,析方法 通过数据干扰和查询限制等方法，在不针对 个体信息的条件下得到普遍的规律,储与访问,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,5,数据挖掘中的隐私保护问题 数据挖掘是从大量数据中抽取出新颖的、潜在有用的模 式或者规则 关联规则挖掘、分类、聚类、异常点分析 数据挖掘所关注信息和各类挖掘 结果的隐藏性，使得人们对数据 挖掘中的隐私保护问题异常关注 解决数据挖掘中的隐私保护问题成为研究的热点,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,6, 从大量数据中挖掘出来的,模式或者规则，通常是针 对综合数据而非

5、细节数据 是否可以在不精确访问原始数据详细信息的条件下，挖 掘出准确的模式与规则呢？,隐私保护 数据挖掘,问题的描述 原始数据中包含着数据所有者（或者第三方）的隐私信 息，而挖掘者需要从中获取有用的知识,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,7,相关研究工作 IBM Almaden Research Center (Rakesh Agrawal), ,Privacy Preserving Data Mining, SIGMOD2000 Privacy Preserving OLAP, SIGMOD2005, Stanford University (H. G. Mo

6、lina & R. Motwani),Privacy & Databases, PORTIA project with Yale & Microsoft, Purdue University (Chris Clifton),Privacy Preserving Distributed Data Mining, Syracuse University (Wenliang Du),Randomization approaches, Chinese University of Hong Kong,Personalized Privacy Preservation, SIGMOD2006, CMU、U

7、IUC、Cornell、Texas A&M 等,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,8,架构及其流程,评估指标体系, ,架构及其流程研究基础 有效处理方法关键技术 评估指标体系可靠保障 数据挖掘算法成果体现,数 据 处 理,强 相 关 的 隐 私 属 性 数 值 类 型 隐 私 数 据 枚 举 类 型 隐 私 数 据 布 尔 类 型 隐 私 数 据,特 征 重 构,我们研究的重点内容 隐私保护的数据挖掘算法,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,9,项目支持 国家自然科学基金项目 “面向隐私保护的数据挖掘方法研究” 北京市科学技术委员会

8、博士论文资助项目 政府、金融、电信行业实际应用项目,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,10,数据挖掘中隐私保护方法的架构与流程 隐私数据处理方法的多样性 数据变换、数据阻塞、数据归并、数据交换、数据抽 样等 数据挖掘算法的多样性 关联规则挖掘、分类、聚类等 系统的简洁性和可操作性 支持海量隐私数据的分析与挖掘,挖掘算法,X,M,挖掘 结果 X 11,发布数据库 D 数 据 处 理,隐私数据,需要保护 原始数据库 D CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,受到保护,特征重构 隐私保 护策略,挖掘,挖掘算法,M 算 法 调 整,结果 X

9、尽量 接近,数据 特征 F,KD3 架构 Knowledge Discovery in Distorted Database 隐私数据,Knowledge Discovery in Database,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,12,KD3 架构的工作流程,1. 分析数据特征 2. 确定保护策略（参数选择） 3. 进行数据处理（参数使用） 4. 调整挖掘算法（参数使用） 5. 实施特征重构（参数使用） 6. 生成挖掘结果（参数使用）,数 据 所 有 者 数 据 挖 掘 者,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,13,方法的评估指

10、标体系 有效的衡量标准和评价指标体系，可以帮助用户 根据不同的数据特征和应用需求，选择出最合适 的隐私保护技术 四个方面的评估指标体系 隐私性 准确性 高效性 适用性,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,14,隐私性 方法对隐私信息的保护程度，可以用被保护的隐 私信息仍然被发现或者预测出来的可能性来衡量 分类属性：隐私破坏系数 Breach Breach = P真实数据所占的比例P真实数据被识别出来的概率 P非真实数据所占的比例P非真实数据被识别出来的概率 P非真实数据被还原的概率,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,15,隐私性(续

11、) 连续值属性： 隐私破坏区间宽度 BreachWidth 如果原始数据 x 落到区间x1, x2上的概率为c%， 则称区间x1, x2是置信度为c%的隐私破坏区间， 而该区间的宽度(x2x1)就定义了置信度为c%的隐 私破坏区间宽度,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,16,准确性 应用隐私保护方法之后的挖掘结果误差，或有效 信息损失和数据功能性损失的程度 原始数据与发布数据的内在特征吻合程度 实际挖掘结果与真实结果之间的差异 重构特征的误差和方差分析,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,17,高效性 方法所需的时间和空间代价，或为

12、了保护隐私信 息而额外花费的时间和使用的空间 算法运行的效率和资源使用情况 方法的整体性能 数据处理的性能 特征重构的性能 针对发布数据进行挖掘的性能 通过时间和空间计算复杂度来进行评估,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,18,适用性 方法适用于不同数据类型、不同数据挖掘算法和不同数 据分布状况的能力 提高数据处理方法对各类数据挖掘算法的适用性水平， 有助于提高数据挖掘中隐私保护方法的一致性和规范性 水平 数据入侵者会试图通过各种数据挖掘算法，来威胁隐私 信息的安全，只有适用性强的通用方法，才能真正实现 有效的隐私保护,CCF YOCSEF 报告会：数据挖掘及其

13、在网络信息安全中的应用,19,关联规则挖掘中的隐私保护方法 在KD3架构与流程的基础上实现 提出了部分隐藏的随机化回答（RRPH）方法 数据干扰和查询限制的隐私保护策略相结合 布尔类型的数据处理和特征重构方法 关联规则挖掘中基于RRPH的隐私保护方法 相同时间和空间开销 更好的隐私保护程度 更高的挖掘结果准确性,算法,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,20,D,频繁项集 生成算法,总体架构,隐私项,需要保护 原始事务集,隐私项 受到保护 发布事务集 D 数 据 处 理,特征重构 RRPH 方法,关联 规则,隐私保护 频繁项集 支持度 生成 计数 算 法 调 整,

14、统计学,究成果, 部分隐藏的随机化回答（RRPH）方法 1 X,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,21,原始数 关,处理后的数据均与 相结合据直接相 引入 中的研 提供的所有数据都是真实数据,RRPH方法 现有的数据处理方法, 数据干扰策略 查询限制策略,0,0 0 1 1,0 0 1 0,1 1 0 0 1,0 0,1 0 1 1 1 0 0 X 支持布尔类型的数据处理和特征重构 0 0 1 0 X 用于实现关联规则挖掘中的隐私保护 X 1 1 1 0,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,22,RRPH的数据处理方法 随机化参数，

15、0p1, p2, p31，且 p1+p2+p3=1 对 x0,1，令 r1=x, r2=1, r3=0，随机函数 r(x) 以概率 pj,返回 rj 用向量 X=(x1, x2, ., xn),表示数据库 D 中的一条记录，其中 xi0,1 用 Y=R(X) 生成随机向量 Y=(y1, y2, ., yn)，其中 yi=r(xi)，分 别以概率 p1, p2, p3 返回 xi, 1, 0 随机向量 Y 在形式上与原始向量相同，作为处理后的数 据记录被加入到数据库 D 中,p1 x,p2 1,p3 0,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用, p2 p1, ,序号,X

16、A,YA,映射概率,1 2 3 4,0 0 1 1,0 1 0 1,p1+p3 p2 p3 p1+p2,隐私保护的频繁项集生成算法 1-项集的支持度计算 表示项 A 在 D 中的支持度 表示项 A 在 D 中的支持度 (p1 p2)(1)p2 p1 p2,2323,mij tmax(0,i jk)C j(p1 p2)t p3,Ck j p2,C,C=MC，C 1,Ck ,C ,，C 1,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,24,k-项集的支持度计算 A=i1, i2, , ik 是一个 k-项集 恰好包含 A 中 j 项的 D 中事务 T（共 Cj个）经过 RRP

17、H 方法处理，变 成为恰好包含 A 中 i 项的 D 中事务 T（共 Ci 个）的概率 mij都相等,，M=mij是(k+1)(k+1)矩阵,C0 ,C0 Ck, 当 M 可逆时，令 M-1=aij，则项集 A 的支持度计数为 Ck ak,0C0 ak,1C1 ak,kCk ,it,it,jt,min(i, j) t,(p1 p3)ki jt,Breach1= p p+(1-p)(1-p)1= p (1 p),CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,25,RRPH方法的隐私性分析 在真实数据所占的比例相同，都为 p 的情况下 MASK方法VLDB2002，随机化参数为

18、 p，, Breach1 Breach2=, 当,时，Breach1 Breach2,p1 2p2 1 2,( 2p1)( 2p1)(p 1) p 1,2p3 2p2 p1 p1,1 2,0 p ,2,2,(p ),(p ),p (1 p2)2p1p2,n (2p 1), ,4p ,4np (2p 1),26, MASK 方法, RRPH 方法, 取 p1=p，p2=p3，则, 当,RRPH方法的准确性分析,1 2,1 (1 p) 2p1, 1 ,1 2,p(1 p) n(2p1)2,Var( 1) ,2 p2 p1, 2,np1 2, 2,p1(1 p1) np1 2,Var( 2) ,(1

19、 p)(1 p) 4np2,p2(1 p2) np1 2,Var( 2) , 1 和 2 都是 的无偏估计量，而,),1 2,2,(p ,(1 p)( 3p 1) 2 2,1 p 2,1 p p ,Var( 1)Var( 2) ,1 3, p 1时，Var( 1) Var( 2) CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,平均项集度误差（）,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,25 20 15 10 5 0,实验结果 30,0.1,0.2,0.3 0.35 0.4 0.45 0.49 0.51 0.55 0.6 0.65 0.7,0.8,0

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

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

22、 体系架构和评估体系 关联规则挖掘中的隐私保护方法 面向隐私保护的数据发布方法 研究背景和问题描述 面向微数据发布的身份保持的K-匿名,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,31,数据发布中的隐私保护 核心问题：在保护隐私的前提下，发布较为准 确的数据 统计数据库把数据发布分为三种类型 微数据：指包含个体信息的数据； 聚集数据：指汇总之后的各项分类的统计数据； 其他统计数据：包括其他各种类型的总体描述，比如 回归因子、相对指数等。,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,32,我们研究的重点 微数据发布场景 分析单一个体对应多个记录的情况，

23、提出了身份保 持的匿名模型 分析动态数据发布的场景和隐私推理途径，提出了t- rotation模型处理动态数据 联机分析处理(OLAP)中的数据保护 基于度量的OLAP数据隐私保护方法 基于维度的OLAP数据隐私保护方法,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,33,问题提出 很多部门和单位（例如：医院）需要发布一些数据表。包 含个体信息的表称为微数据（microdata） 微数据是记录个人信息的数据 身份标识属性（Individually Identifying Attribute ，简称ID ）：记 录了可以唯一识别个人的取值，比如身份证号、电话号码、姓名 等信息

24、 准标识属性（Quasi-identifiers，简称QI）：记录了对个人的一些 类型属性的取值，比如性别、所在的邮政编码、出生日期等 敏感属性（Sensitive Attribute，简称ST）：记录了个人不愿为人所 知的取值信息，比如个人收入、所患病症等,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,34,问题提出：微数据发布场景 为了提供研究，医院发布了一个病人情况表 简单的方法：去掉“身份标识属性” publish,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,35,连接推理,发布表 Quasi-identifier (QI) attribute

25、s,选民登记表 An adversary,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,36,连接推理 Swe00的研究表明，87的美国人口信息可以通过性 别、出生日期、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)：准标识

26、属性 STk (k=1，2，t)：敏感属性 为了保护个人隐私，发布数据集需要设定一个隐私保护 需求 为了达到隐私保护需求，需要对数据集T中的元组t进 行转化得到t，设转化函数为f,CCF 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，

27、qs) 取值相同的那些元组形成一个QI分组。 为了尽量准确地评价发布数据，需要建立评价指 标，设为,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,39,问题定义(3) 隐私保护的数据发布问题可以表示为一个四元组PPDP=（ T，f，） T是需要发布的数据集，发布的数据集为PTf(t)|tT 是隐私保护需求,f 是转化函数, 是对发布数据集的评价结果 隐私保护的数据发布问题就是在满足隐私保护需求的 前提下，最大化数据有效性指标 实现隐私信息的合理保护和获得数据信息的最大效用,抑制 隐私保护需求,评价指标 CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,记录处

28、理 k-匿名 l-多样化 (,k)-匿名,背景知识 隐私攻击,待发布表,中间表 属 性 处 理,发布表,外部表 40,处理的基本框架 概化 有损分解,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,41,相关研究工作 隐私保护需求, ,k-anonymity (TKDE01) l-diversity (ICDE06) (,k)-anonymity (KDD06) t-closeness (ICDE07) 个性化隐私 (SIGMOD06), 转化方法, ,单维概化 (TKDE01) 多维概化 (ICDE06) 有损连接 (VLDB06) 空间索引 (VLDB07,VLDB07)

29、,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,42,相关研究工作 评价指标 概化比例DR (KDD02) 可识别性DM (ICDE05) 确定性代价NCP (KDD06) 隐私攻击 Minimality Attack (VLDB07) Privacy Skyline (VLDB07),CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,43,隐私保护需求 研究者提出了多种隐私保护需求 k-anonymity：每个QI分组中至少包含k个元组 l-diversity：每个QI分组中的敏感属性至少有l个不同 的取值 (,k)-anonymity：每个QI分组中的每

30、个敏感属性取值 的概率不超过,并且每个QI分组中至少包含k个元组 t-closeness ,4 QI 分组,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,44,anonymous）,QI 属性,ST属性,隐私保护需求：k-anonymity 具有相同的准标识属性组(QI)的元组至少有k个（2-,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,45,数据转化方法：概化 概化关系D ：设两个域Di，Dj，|Dj| |Di|，Dj称为 Di的一个概化，如果对任何一个diDi，都存在djDj， dj是di的概化。,CCF YOCSEF 报告会：数据挖掘及其在网络信

31、息安全中的应用,46,数据转化方法：有损分解 有损分解 设数据表T，属性集AGID QI ST，其 中GID属性用于记录每个元组分组之后的分组 标号，QI是准标识属性集合，ST是敏感属性 集合。 将表T分解为两个表STT和QIT进行发布 QITGID QI STTGID ST,23,M 1,pneumonia,35,59,1dyspepsia,65,65,QIT表,47,有损分解方法 发布表变成两张表，类标识属性表(QIT)和敏感属性表（ STT）,Count,2,2 2 1 2,2,1,Age Sex 23 M,27 35 59 61,M M M F,13000 59000 12000 54

32、000,65 65 70,F F F,25000 25000 30000,gastritis STT表,Age Zipcode 11000,Disease Group-ID Disease,Sex Zipcode Group-ID 11000,27,M 1 M 1 1 M 2,13000 59000 12000,1dyspepsia dyspepsia pneumonia 2 bronchitis pneumonia flu,61,F 2 F 2 F 2,54000 25000 25000,flu gastritis flu,70,F,30000,bronchitis,Microdata,CC

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

34、s，s1，st)，其中d 是重编码后的身份属性取值，多个身份属性只保留一个即可。 身份保持的匿名 考虑了单一个体出现多次的情况 提高信息有效性，保留QI与ST的关系以及ST之间的关系 是现有方法的一般形式,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,50,隐私保护需求 身份保持的隐私保护需求 Identity-reserved k-anonymity：每个准标识属 性分组中至少有k个不同的个体 Identity-reserved (k,l)-anonymity：每个准标识 属性分组中至少有k个不同的个体，并且敏感 属性取值不少于l个 Identity-reserved (

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

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

37、属性ID，敏感属性ST和分组标号 有损分解的实现基于概化算法 对身份标识属性重编码 采用概化算法，得到满足身份保持的匿名表T 将T 的准标识属性投影到QIT中，同时把每个元组对应的分组 号填入到分组标号属性中，然后删除重复的记录 将T的ID和敏感属性取值投影到STT中，同时把每个元组对应 的分组号填入到分组号属性中,55,QIT 要求身份保持的2-匿名 STT,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用55,vulnerable group ratio,CCF YOCSEF 报告会：数 k value其在网络信息安全中的应用,据挖掘及,56,实验与分析(1) 实验数据来自

38、于UCI的美国人口数据样例库 定义单一个体的平均元组数作为衡量个体的重复程度，记为rpi元 组总数/个体总数。 普通k-匿名方法在rpi1时，隐私保护度降低的分组称为脆弱分组 脆弱分组比例与rpi、k的关系,0.5 0.45 0.4 0.35 0.3 0.25 0.2 0.15 0.1 0.05 0,2 3 4 5 6 7,rpi=1.2 rpi=1.4 rpi=1.6 rpi=1.8,distortion ratio,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,57,实验与分析(2) 用概化度描述信息损失的指标，概化层次越低，概化度越小，信息 损失越少 比较普通k-匿名

39、与身份保持的k-匿名的概化度,0.12 0.1 0.08 0.06 0.04 0.02 0,2,3,4,5,6,7,k value (rpi=1.2),common k-anonymity identity-reserved k-anonymity,relative correctness,CCF YOCSEF 报告会：数据挖掘及其在网络信息安全中的应用,58,0.2 0,1,2,3,4,5,6,7,8,9,10 11 12 13,k values(rpi=1.2),实验与分析(3) 用查询有效性来比较概化与有损分解两种实现方 法在信息有效性上的差别。 实现身份保持的匿名时，两种方法的相对查询正 确率比较 1 0.8 0.6 0.4 lossy join,generalization,谢谢！,Contact Information：,E-mail: Telephone: 62756920 (Office),13701205200(Mobil),Office：Room 2312, No.2 Science Building ,Peking University,