（计算机软件与理论专业论文）基于敏感性语义关系的数据发布隐私保护研究.pdf

独创性声明 | | i i ii ii ii ii iii iii iiiii 18 9 5 3 91 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已注明引用的内容以外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：翮、毒劬陟 lf 年月心日 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 | 本学位论文属于不保密刮。 学位论文作者签名：列华b 面 劢f j 年占月肜日 指制雠：m 够 v “年6 只f 8b 江苏大学硕士研究生毕业论文 摘要 现实中，出于统计和研究等目的，一些机构和组织往往需要发布一些包含敏 感信息的个人数据，如医疗信息、人口普查信息等。怎样在发布个人数据的同时 又能防止个人敏感信息泄露成为数据发布隐私保护中的一个重要问题。 肛匿名模型常用来解决数据发布中的隐私保护问题，但它并没有考虑敏感属 性值的分布，容易受到同质攻击和知识背景攻击。- d i v e r s i t y 模型考虑了敏感属 性字面上的差异，但忽略了敏感属性值之间的语义相似关系，同样容易受到相似 性攻击。相似性攻击是指在同一个等价类中的敏感属性值虽然不同，但它们语义 上相似，攻击者仍然能获取目标个体大致的敏感信息。相似性攻击作为属性泄露 的一种方式是普遍存在的，并会对个人隐私保护构成严重威胁。 针对以上存在的问题，本文提出以下解决方法： ( 1 ) 为了有效地解决属性泄露问题，防止相似性攻击的发生，本文提出了 基于敏感属性语义关系的q s i m i l a r i t yk - a n o n y m i t y 隐私保护模型。该模型在b 匿 名有效解决身份泄露的基础上，增加对敏感属性语义关系的限制，要求等价类中 敏感属性值的语义关系不大于预先给定的参数o t ；并根据敏感属性值的相似度对 等价类进行反聚类处理，避免语义关系相似的敏感属性值密集发布所带来的相似 性攻击问题。 ( 2 ) 敏感属性按照其属性域的不同可以分为数值属性和分类属性两种。对 于数值属性，属性值之问的数值差异自然的描述了它们之问的不相似程度。对于 分类属性，由于属性值并不是严格意义上有序的，目前缺少一种有效的方法对分 类敏感属性值的语义相似性进行计算。在此，本文从语义学角度构建分类树模型， 并使用该模型来衡量分类敏感属性值之问的语义相似程度。 ( 3 ) 关于算法方面，本文首先提出改进的i n c o g n i t o 算法来获取符合o t s i m i l a r i t yk - a n o n y m i t y 要求的匿名数据集。由于i n c o g n i t o 算法采用的是自底向上 全域泛化方式，在匿名过程中会造成严重的信息丢失。为此，本文又提出了基于 局部重编码的多维空间分割算法来解决匿名过程中的信息丢失问题。 与现有的缸匿名模型和- d i v e r s i t y 模型相比，a s i m i l a r i t yk - a n o n y m i t y 模型 不仅考虑了身份泄露问题，同时还考虑了针对敏感属性的属性泄露问题，从而降 江苏大学硕士研究生毕业论文 低个人敏感信息泄露的风险。理论分析和实验结果表明新的隐私保护模型能够很 好的防止相似性攻击的发生，提供更好的隐私保护效果，并且，匿名数据的信息 丢失量并没有显著的增加。 关键词：隐私保护，数据发布，驴匿名，属性泄露，相似性攻击，语义相似性 江苏大学硕士研究生毕业论文 a b s tr a c t f o rt h er e s e a r c ha n do t h e rp u r p o s e s ，a g e n c i e sa n do t h e ro r g a n i z a t i o n so f t e nn e e d t op u b l i s hm i c r o d a t a , e g ，m e d i c a ld a t ao rc e n s u sd a t a s u c hd a t ao f t e nc o n t a i n ss o m e p r i v a c yi n f o r m a t i o na b o u ti n d i v i d u a l s s o ，p u b l i s h i n gd a t aa b o u ti n d i v i d u a l sw i t h o u t r e v e a l i n gs e n s i t i v ei n f o r m a t i o nh a sb e c o m ea ni m p o r t a n tp r o b l e mi np r i v a c y p r e s e r v a t i o no fm i c r o d a t ap u b l i s h i n g t h ek - a n o n y m i t ym o d e lw a sp r o p o s e df o rp r i v a c y p r e s e r v i n gm i c r o d a t a p u b l i s h i n g b u ti tf a i l st oc o n s i d e ra t t r i b u t ed i s c l o s u r e t h en o t i o no f - d i v e r s i t yh a s b e e ni n t r o d u c e dt oa d d r e s st h i sp r o b l e m b u ti ts t i l lc a nn o tp r e v e n ts i m i l a r i t ya t t a c k b e c a u s ei tt a k e so n l yt h ed i v e r s i t yo fs e n s i t i v ea t t r i b u t ev a l u e si n t oc o n s i d e r a t i o n e x c e p tt h es e m a n t i cs i m i l a r i t yo ft h ev a l u e s w h e nt h es e n s i t i v ea t t r i b u t ev a l u e si na n e q u i v a l e n c ec l a s sa r ed i s t i n c tl i t e r a l l yb u ts e m a n t i c a l l ys i m i l a r , a ni n t r u d e rc a na l s o i n f e rs o m ei n d i v i d u a lp r i v a c yi n f o r m a t i o ne a s i l y t h i si ss oc a l l e dt h es i m i l a r i t y a t t a c k d u et ot h el i m i t a t i o n so ft h e s ee x i s t e dp r i v a c yp r e s e r v i n ga p p r o a c h e s ，w es u g g e s t t h ef o l l o w i n gm e t h o dt or e s o l v et h e s ep r o b l e m s ( 1 ) i no r d e rt or e s o l v et h ep r o b l e mo fs i m i l a r i t ya t t a c k ，w ep r o p o s ean o v e l m o d e ln a m e da sq s i m i l a r i t yk - a n o n y m i t yw h i c hi m p o s e st h ea d d i t i o n a ls i m i l a r i t y r e q u i r e m e n to ns e n s i t i v ea t t r i b u t e st h a nk - a n o n y m i t yd o e s o u ra p p r o a c hr e q u i r e st h a t t h es i m i l a r i t yd e g r e eo fs e n s i t i v ea t t r i b u t ev a l u e si ne a c he q u i v a l e n c ec l a s ss h o u l db e n om o r et h a nt h ep r e d e f i n e dp a r a m e t e r0 1 ：s oo u ra p p r o a c hc a nn o to n l yp r e v e n t i d e n t i t yd i s c l o s u r eb u ta l s oc a np r e v e n ta t t r i b u t ed i s c l o s u r ew e l l i te f f e c t i v e l yl i m i t s t h ea m o u n to fi n d i v i d u a ls p e c i f i ci n f o r m a t i o nt h a ta no b s e r v e rc a nl e a mf r o mt h e 口 - s i m i l a r i t yk - a n o n y m i t yt a b l e ( 2 ) i no r d e rt oc a l c u l a t es e m a n t i cs i m i l a r i t yd e g r e ea c c u r a t e l y , w ef i r s t l yd i v i d e t h es e n s i t i v ea t t r i b u t e si n t ot w op a r t s ：t h en u m e r i ca t t r i b u t e sa n dt h ec a t e g o r i c a l a t t r i b u t e sa n da d o p td i f f e r e n tm e t h o d st om e a s u r et h e i rs e m a n t i cs i m i l a r i t y f o ra n u m e r i ca t t r i b u t e ，t h ed i f f e r e n c eb e t w e e nt w ov a l u e s ( e g ，l x - y 1 ) n a t u r a l l yd e s c r i b e s 江苏大学硕士研究生毕业论文 t h ed i s s i m i l a r i t y ( i e s e m a n t i cd i s t a n c e ) o ft h ev a l u e s h o w e v e r , f o rt h ec a t e g o r i c a l a t t r i b u t e ，t h en u m e r i cd i f f e r e n c ei s n ol o n g e ra p p l i c a b l e b e c a u s em o s to ft h e c a t e g o r i c a la t t r i b u t ed o m a i n sc a nn o tb ee n u m e r a t e di na n ys p e c i f i co r d e r i ti sn a t u r a l e x t e n s i o nt od e f i n et h ed i s t a n c eb a s e do nt h er e l a t i o n s h i p so fs e m a n t i cs i m i l a r i t y s u c hr e l a t i o n s h i p sc a nb ee a s i l yo b t a i n e di nt h ef r a m eo ft h et a x o n o m yt r e e ( 3 ) w ep r o p o s eae x t e n d e di n c o g n i t oa l g o r i t h mt o f u l f i l lt h eo s i m i l a r i t y k - a n o n y m i t ym o d e l t h ei n c o g n i t oa l g o r i t h m i sab o t t o m u pf u l l d i m e n s i o n s g e n e r a l i z a t i o na l g o r i t h mw h i c hi n d u c e sm u c hi n f o r m a t i o nl o s s s o ，i no r d e rt or e s o l v e t h ep r o b l e mo fm u c hi n f o r m a t i o nl o s s ，w ea l s os u g g e s tt h em u l t i d i m e n s i o n a ll o c a l r e c o d i n ga l g o r i t h mt of u l f i l lt h e 口一s i m i l a r i t yk - a n o n y m i t ym o d e l c o m p a r e dw i t h 缸a n o n y m i t y m o d e l a n d - d i v e r s i t ym o d e l ，q - s i m i l a r i t y k - a n o n y m i t ym o d e lc a n r e s o l v et h es i m i l a r i t yat m c kp r o b l e mw h i c ha l w a y sg o e sw i t h p u b l i s h e dm i c r o d a t a e x p e r i m e n t a lr e s u l t ss h o wt h a tt h em o d e lc o u l dr e d u c et h er i s k o fp r i v a c yb r e a c hs i g n i f i c a n t l y k e y w o r d s ：p r i v a c yp r e s e r v a t i o n ，m i c r o d a t ap u b l i s h i n g ，k - a n o n y m i t y , a t t r i b u t e d i s c l o s u r e ，s i m i l a r i t ya t t a c k ，s e m a n t i cs i m i l a r i t y i v 江苏大学硕士研究生毕业论文 目录 1 绪论 1 1 1 课题背景l 1 2 数据发布隐私保护的研究现状一3 1 3 本课题研究内容及关键问题一6 1 4 本文所做的工作7 1 5 论文的组织结构8 2 相似性攻击问题和近邻漏洞问题研究一9 2 1 典型的隐私保护模型一9 2 1 1k - a n o n y m i t y 隐私保护模型9 2 1 2 - d i v e r s i t y 隐私保护模型1 l 2 1 3t - c l o s e n e s s 隐私保护模型1 2 2 1 4 增强的p s e n s i t i v ek - a n o n y m i t y 隐私保护模型1 2 2 2 相似性攻击问题13 2 2 1 问题描述13 2 2 2 目前的解决方法与存在的不足1 3 2 3 近邻漏洞问题14 2 3 1 问题描述1 4 2 3 2 目前的解决方法与存在的不足1 6 2 4 本章小结1 6 3 基于敏感属性语义关系的隐私保护模型17 3 1 数值敏感属性语义关系的计算1 7 3 1 1 - 记录之间语义关系的计算1 8 3 1 2 等价类相似度的计算l9 3 2 分类敏感属性语义相似性的计算2 l 3 2 1 分类树的概念2l 3 2 2 记录之间语义距离的计算2 2 3 2 3 等价类相似度的计算2 5 3 3a s i m i l a r i t yk - a n o n y m i t y 隐私保护模型2 8 v 江苏大学硕士研究生毕业论文 3 3 1 基于敏感属性语义关系的a s i m i l a r i t yk - a n o n y m i t y 模型2 8 3 3 2 模型分析2 8 3 4 相关工作比较2 9 3 5 本章小结3 0 4 算法与分析3l 4 1 改进的i n c o g n i t o 算法3 l 4 1 1b a s i ci n c o g n i t o 算法介绍一3 2 4 1 2 口一s i m i l a r i t yk - a n o n y m i t y 性质3 3 4 1 3 改进的i n c o g n i t o 算法描述3 4 4 2 基于局部重编码的多维空间分割算法3 6 4 2 1 局部重编码方式的特点3 7 4 2 2 基于局部重编码的多维空间分割算法描述3 8 4 3 实验比较与分析4 0 4 3 1 实验环境一4 0 4 3 2 隐私保护技术的性能指标4 2 4 3 3 抵御相似性攻击的安全性分析4 4 4 3 4 执行效率分析4 6 4 3 5 数据可用性比较：4 8 4 4 相关工作比较5 0 4 5 本章小结51 5 总结与展望一5 2 5 1 论文工作总结5 2 5 2 研究展望5 3 参考文献5 4 致 谢5 9 在学期间发表的学术论文及其他科研成果6 0 v l 江苏大学硕士研究生毕业论文 1 1 课题背景 1绪论 现实中，随着数据库技术、网络技术和计算技术的快速发展，包含个人信息的 数据呈指数增长。大量个人数据的存在导致了数据挖掘工具的广泛使用，同时也引 起人们对保护个人隐私的极大关注【1 1 。然而，出于研究和统计分析等目的，大量组 织和机构往往需要发布一些包含个人敏感信息的个人数据，例如医疗信息表、人口 普查信息等。如何在发布个人数据的同时又能保证个人的隐私信息不泄露已经成为 众多学者关注的问题。数据发布中的隐私保护技术【l l 的出现就是为了解决上述问题。 在典型的数据发布中，实施隐私保护的的原始数据一般为数据表形式存在。表中每 一条记录( 或每一行) 对应具体的一个人，包含若干个属性值。根据属性在识别身 份过程中的不同作用，本文将这些属性分为以下三类： 1 ) 显式标识属性( e x p l i c i ti d e n t i f i p r ) ：能唯一标识单一个体的属性，如身份证 号码、姓名、i d 号等。 2 ) 准标识属性( q u a s i i d e n t i f i e r s ) 联合起来能唯一标识一个人的多个属性， 如邮编、生同、性别、受教育程度等。 3 ) 敏感属性( s e n s i t i v e a t t r i b u t e ) ：即包含隐私数据的属性，如疾病、薪资等。 例如，表1 1 为一个原始医疗数据表，每一条记录对应一个病人的健康状况， 其中n a m e 属性为显式标识符，a g e 、s e x 、z i pc o d e 为准标识属性，h e a l t hc o n d i t i o n 为敏感属性。 出于隐私保护的目的，在对这些个人数据进行发布之前，需要对这些原始数据 进行匿名化处理，尽可能不泄露数据中个体的敏感信息。数据发布中的隐私泄露主 要可以分为两种【2 l ：身份泄露( i d e n t i t yd i s c l o s u r e ) 和属性泄露( a t t r i b u t ed i s c l o s u r e ) 。 身份泄露是指具体的某个人可以唯一与匿名表中条记录相对应。属性泄露是指关 于一些个体的新的敏感信息被揭露，也就是说根据观察匿名表可以推导出关于个体 的一些新的特征。当一个身份泄露发生时，伴随的敏感属性也就被暴露，属性泄露 可以伴随也可以不伴随身份泄露而发生，属性泄露是普遍存在的。 同时，发布的数据出于可用性的目的，又应该尽量的保持信息的完整性和准确 江苏大学硕士研究生毕业论文 性，即仍然能够根据发布的匿名数据进行较准确的数据统计和分析，例如：集合查 询等。传统的做法是通过删除表的显式标识属性如姓名、身份证号码等，对原始数 据表进行去显式标识( d e i d e n t i f y ) 匿名处理。但是，对原始数据进行去显式标识处 理并不能有效满足隐私保护的要求。在美国，l s w e e n u y 的一项研究表明1 3 ，通过 准标识属性的集合，例如出生地、性别和住址等和一些公开可用的数据库如选民数 据库，民意调查数据库等进行链接，8 7 的公民可以被唯一的识别。下面的例子很 好的描述了这种链接攻击( l i n k i n g a t t a c k ) 。 表1 1 原始数据 n a m e a g e s e x z i p c o d e h e a l t hc o n d i t i o n 墓，b o b ， 2 3m1 1 0 0 0a s t h m a 叠 锄一t“ ” k e n2 7m1 3 0 0 0 c a r d i o p a t h y 表1 2 额外数据源 n a m e a g e s e x z i pc o d e ，“ 7 彩 雾， b o b2 3m1 1 0 0 0-o，m ?i i ，? ， b ，艘 例1 1 假设某家医院要将原始医疗信息表1 1 发布给医学研究者，其中h e a l t h c o n d i t i o n 为敏感属性。根据传统的隐私保护方法，对原始数据进行去显示标识符处 理，也就是再发布之前，删除表1 1 中的显示身份属性n a m e 。然而，这种匿名方 法不能够有效保护个人隐私不被泄露。假设攻击者知道目标个体b o b 的年龄为2 3 ， 住址的编号为1 1 0 0 0 ，通过链接额外数据源，如：人口普查信息表1 2 ，可以很轻松 获取目标个体的隐私信息对应表1 1 中的第一条记录，由此可以推断出b o b 患有 “a s t h m a 疾病。 显然，根据传统的数据隐私保护方法得到的匿名数据根本不能有效的阻止以上 的链接攻击。所谓的链接攻击是指，虽然对待发布数据进行了去显示标识符处理， 但是攻击者通过将准标识属性信息和额外数据库数据进行链接，仍然能够获取目标 个体的敏感信息，构成严重的隐私泄露。因此，必须对待发布的数据进行更加严格 的匿名处理才能达到隐私保护的目的。数据发布中的隐私保护是一个新兴的研究领 域。尽管目前已经有越来越多的研究者开始关注这一领域，但数据发布中的隐私保 护仍然存在很多值得研究的问题。 2 江苏大学硕士研究生毕业论文 1 2 数据发布隐私保护的研究现状 隐私保护技术的出现就是为了解决这种问题。目前信息发布隐私保护主要可以 分为三大类1 4 l ：( 1 ) 隐私保护模型的研究，它主要是作为一个衡量的标准来判断发 布的匿名数据能否为包含在数据中的个体提供足够的隐私保护，例如广泛使用的缸 匿名1 5 , 6 , 7 j 、- d i v e r s i t y l 8 1 、t - c l o s e n e s s l 9 j 等隐私保护模型。( 2 ) 根据某种隐私保护模型 获取匿名数据的算法研究，例如最先提出的计算满足肛匿名模型要求的匿名数据的 二分查找算法【7 1 和一些近似算法等【1o 1 1 l ；( 3 ) 在不损害隐私保护的前提下，尽可能 提高匿名数据的可用性研究，例如a n a t o m y ! 坦】方法等。 驴匿名是最早的关于数据发布隐私保护问题的隐私保护模型，由p s a m a r a t i 和 l s w e e n e y l 6 , 7 】最先提出。该模型要求所发布的数据表中的每一条记录都至少有肛1 条其他记录与之等价，这里的等价只针对准标识属性而言，敏感属性不做处理。缸 匿名方法通常采用泛化【6 ，1 1 , 1 3 , 1 4 , 1 5 , 1 6 1 和抑铝l j 7 , 1 7 】技术对原始数据进行匿名处理以得 到满足缸匿名规则的匿名数据。 缸匿名模型要求每个等价类中至少包含k 条记录，从而使阻止攻击者不能根据 准标识属性信息唯一的识别目标个体所的对应记录，在一定程度上保护了个人的隐 私。然而，肛匿名模型存在严重的缺陷。首先，肛匿名模型并没有对敏感属性做任何 约束，并不能有效的解决属性泄露问题。这个问题在文献1 8 , 1 8 】中有详细讨论，并且 在文献【8 】中还描述了两种针对肛模型模型的攻击，分别为同质攻击( h o m o g e n e i t y a t t a c k ) 和背景知识攻击( b a c k g r o u n d k n o w l e d g e a t t a c k ) 。其次，计算最优的缸匿名 是一个n p h a r d 【1 0 】问题，目前一般采用近似算法和大约算法来产生符合驴匿名要求 的匿名数据集。最后，a g g a r w a l l l 9 】指出肛匿名模型在准标识属性维数不高的情况下 比较适用，但不能有效的处理高维准标识属性情况下的隐私保护问题。 为了解决舡匿名在属性泄露方面的不足，a m a c h a n a v a j j h a l a 等人提出了 - d i v e r s i t y t 8 】模型。该模型仍然将原始数据划分为多个等价类，并要求每个等价类中 至少包含，个符合“w e l l - r e p r e s e n t e d ”敏感属性值。因此，攻击者最多以l 刀的置信 度准确推测出目标个体的敏感信息。x x i a o 和yt a o 通过实验验证和理论分析证明 了- d i v e r s i t y 模型能够为个体提供更强的隐私保护1 2 0 1 。但它仍然存在两个缺点。首 先，- d i v e r s i t y 模型仍然采用泛化技术来得到满足隐私要求的匿名数据，而泛化技术 的根本性缺点在于丢失原始数据中的大量信息。因此，- d i v e r s i t y 模型仍然没有解 3 江苏大学硕士研究生毕业论文 决肛匿名模型会丢失原始数据中大量信息的缺点。其次，- d i v e r s i t y 并不能很好的解 决相似性攻击问题( s i m i l a r i t y a t t a c k ) 1 9 1 。n i n g h u il i 等人提出了一种可以阻止相似 攻击的隐私保护模型一t - c l o s e n e s s 模型【9 l 。t - c l o s e n e s s 模型要求匿名数据集中的每个等 价类中的敏感属性值的分布接近于原始数据中的敏感属性整体上的分布，要求这两 种分布之问的语义距离不超过阈值，并采用e a r t hm o v e rd i s t a n c e l 2 l j 来衡量两个分 布之间的距离。x s u n ，h w a n g 等人在p s e n s i t i v e 模型的基础上提出了增强的 p s e n s i t i v e 肛匿名模型f 2 2 ，2 3 1 ，试图来解决针对敏感属性的相似性攻击问题。他们在 p s e n s i t i v e 的基础上增加了对等价类敏感度的限制，防止高敏感信息的集中发布所带 来的信息泄露。另外，基于泛化技术的隐私保护模型还包括l - d i v e r s i t y 的变形1 9 , 2 5 , 2 6 1 、 v a r i a n c ec o n t r o l t 2 7 1 、( 屯p ) a n o n y m i t y l 2 8 1 、化d s a f e t y l 2 9 1 、p r i v a c y s k y l i n e l 3 0 1 、 6 一p r e s e n c e 3 l j 等。 除了泛化技术，其他方法也可以实现匿名发布的目的。例如k i f e r 和g e h r k e p 2 1 提出了边缘发布( m a r g i n a lp u b l i c a t i o n ) 方法。该方法通过发布原始数据在不同属 性集上的投影的匿名数据来达到隐私保护的目的。x x i a o 和y t a o 提出了一种提高 数据可用性的a n a t o m y 1 2 j 方法，它将原始数据中的准标识属性集合和敏感属性分成 两个不同的表来进行发布，从而可以避免对准标识属性进行泛化处理所带来的信息 丢失，很大程度上提高了发布数据的可用性。a g g a r w a l 和y u l 3 3 j 提出了一种浓缩发 布( c o n d e n s a t i o np u b l i c a t i o n ) 方法，该方法仍然将待发布的数据中的记录划分成若 干个等价类，并选择性的发布关于每个等价类的统计信息来达到隐私保护的目的， 这样在很大程度上避免了个人隐私信息的泄露。r a s t o g i 等人1 3 4 j 利用随机扰动 ( p e r t u r b a t i o n ) 3 5 , 3 6 】技术对待发布的原始数据进行匿名处理。另外，除了在数据发 布的隐私保护研究中存在匿名问题，在许多其他环境中也存在匿名问题。例如，统 计数据库3 7 1 、密码计算【3 8 】和访问控韦l j 3 9 4 0 j 等研究领域。 关于算法研究方面，人们提出了许多通过泛化和抑制技术来获取符合缸匿名要 求的匿名数据。s a m a r a t i 7 l 等人提出了一种基于泛化世系结构之上的二分查找算法， 用来寻找最小肛匿名表。根据频繁项目集挖掘算法的思想，文献1 1 3 j 提出了i n c o g n i t o 算法来计算匿名数据集，而文献【4 l 】则提出了多维肛匿名的概念，并根据k d t r e e 的分 割方法提出了m o n d f i a n 算法，该方法允许同一时刻在多维准标识属性上进行泛化 处理。b a y a r d o 和a g r a w a l l 4 2 】等人提出了一种最优肛匿名算法，该算法从完全泛化 4 江苏大学硕士研究生毕业论文 开始，然后按照最小匿名的要求逐步进行具体化。f u n g i l 5 1 和w a n g l l 4 1 分别提出的自 顶向下和自底向上的泛化处理算法，用来将数据表转变成肛匿名形式进行发布。 g h i n i t a 等人【4 3 j 利用空间填充曲线将高维准标识属性映射到低维空问中，不仅使得泛 化更加容易，同时还能减少原始数据中的信息丢失量。x x i a o 和yt a o 2 5 1 探讨了个 人数据多重发布情况下的隐私保护算法。t 1 w u c h u k w u 和j f n a u g h t o n 4 4 j 提出了 基于空间索引原理的肛匿名泛化处理算法。k w a n g 和b c m f u n 9 1 4 5 1 提出了用 于解决了连续数据发布中的隐私保护问题的匿名算法。然而，这些方法都可能受到 最小性攻击，r c ww o n g 等人通过引入随机化来避免最小型攻击1 4 6 j 。作为理论研 究的结果，m e y e r s o n 和w i l l i a m s i l o 】等人根据被泛化和抑制的单元格和属性的数量证 明了最优缸匿名问题是n p h a r d ，同时还给出了一个时间复杂度为o ( k l o g k ) 的近似 算法。a g g a r w a l 等【4 7 】人在文献f l o l 的基础上进一步降低了算法的近似比率，给出了 一个时间复杂度为o ( 硒的近似算法。 采用泛化技术得到的匿名数据不可避免的会丢失原始数据中的部分信息，从而 降低数据分析的准确性。理想状况下的隐私保护保证发布的匿名数据不泄露任何隐 私信息。然而，这种隐私保护方法往往会对原始数据进行过度扭曲，会严重损害数 据的可用性【4 8 , 4 9 1 ，即不泄露任何隐私信息的匿名数据可能会导致集合查询结果的不 准确或完全错误。 目前，已经提出了一些标准用来衡量匿名数据可用性。最早提出的衡量匿名数 据可用性的标准是泛化高度( g e n e r a l i z a t i o nh i g h ) 1 5 0 j 标准。泛化高度标准使用匿名 过程中所有泛化步骤的总和来近似的描述匿名数据的可用性。但是，基于泛化高度 来衡量匿名数据可用性存在的问题，并不是所有的泛化步骤都会导致等量的信息丢 失。即在某一个属性上的泛化可能会导致分到同一个等价类中的记录数比在另一个 属性上的泛化导致分到同一个等价类中的记录数多，而一个等价类中的记录数和记 录在准标识属性上的分布都会影响信息丢失的量。因此，基于泛化高度标准并不能 准确的衡量原始数据中的信息丢失量。 此外，数据的可用性可以从匿名结果来衡量，比较常见的两种基于等价类大小 的衡量标准是等价类的平均大小f 8 】和区分度【4 2 】标准。等价类的平均大小是指匿名数 据中的所有记录的总和与等价类个数的比值。区分度标准则为每条记录赋一个值， 并根据不能与该记录相互区分开来的记录个数来决定这个值的大小。然而，这些基 5 江苏大学硕士研究生毕业论文 于匿名结果的衡量标准同样存在缺陷，即并没有考虑原始数据的分知情况。例如： 根据准标识属性平均分布的原始数据得到的等价类的信息损失量要远小于根据准标 识属性倾斜分却的原始数据得到的等价类的信息损失量【3 列。 k l e f e v r e 等人1 4 l l 提出了一种利用集合查询的平均相对错误率来衡量匿名数 据的可用性的标准。k i f e r 和g e h r k e l 3 2 l 提出了一种形式化的方法来衡量数据的可用 性，根据这个新的衡量方法，作者提出在七匿名表和- d i v e r s e 表中加入额外的信息 来提高数据分析的准确性。而x x i a o 和y t a o l 2 0 l 提出了基于数据可用性的隐私方法 - - a n a t o m y ，通过将原始数据中的准标识属性和敏感属性分成两个不同的表进行发 布，从而避免了对准标识属性进行泛化处理所带来的信息丢失。 目前，国内也有很多关于隐私保护的研究，比如，隐私保护的数据挖掘方法研 究【5 、基于关联规则的隐私保护算法研究1 5 2 1 等。然而，这些研究大多偏向于数据挖 掘领域。关于数据发布中的隐私保护研究则并不多见。 1 3 本课题研究内容及关键问题 本课题的研究内容主要涉及以下几方面： 1 ) 数据发布隐私保护：在对个人信息进行发布的过程中，如何保证个人的隐 私信息不被泄露，同时又能保证匿名数据的可用性。 2 ) 身份泄露和属性泄露：隐私泄露的两种方式，身份泄露是指目标个体能够 与具体某条记录相关联；属性泄露是指，通过观察属性集合额外获取关于 目标个体的一些新信息。 3 ) 数值属性和分类属性：按照属性域的不同，可以将数据表中的属性分为两 种；数值属性域中的值具有数值有序的，存在数值上的差异；分类属性域 中的值一般是离散的，并不具有数值上的差异。 4 ) 分类属性值的语义距离：分类属性值并不存在数值上的差异，为了有效的 评价分类数值的语义距离，本文从语义学角度出发，引入了分类树的框架 来对分类属性值之间的语义距离进行衡量。 5 ) 基于敏感属性语义相似性的隐私保护研究：传统的隐私保护模型在对数据 进行匿名化处理时，并没有考虑到敏感属性的语义相似性，容易受到相似 性攻击和近邻漏洞攻击。在此，本文将敏感属性的语义相似性归纳于隐私 6 江苏大学硕士研究生毕业论文 保护的考虑范围之内，提出了新的隐私保护模型。 本课题研究的关键问题有： 1 ) 属性泄露问题研究：传统的隐私保护模型主要集中在对身份泄露问题的研 究上，本文主要目的是对属性泄露i u j 题进行研究，包括相似性攻击问题和 近邻漏洞问题。 2 ) 分类敏感属性隐私保护问题研究：分类属性的属性域并不是简单有序的， 对于这些离散的分类属性值，如何正确的评价属性值之间的语义相似性成 为防止属性泄露问题的关键。在本文中我们采用分类的框架来衡量分类敏 感属性语义距离。 1 4 本文所做的工作 本文在广泛阅读国内外相关文献的基础上，认识到目前的隐私保护方法在解决 属性泄露问题上仍然存在一些不足。比如并不能很好的解决相似性攻击问题和近邻 漏洞问题等。为了有效地解决属性泄露问题，提供更好的隐私保护效果，本文提出 了基于敏感属性语义相似关系的q s i m i l a r i t yk - a n o n y m i t y 隐私保护模型。该模型在 肛匿名的基础上，首次考虑到敏感属性的语义相似性，并从语义学角度出发对敏感 属性的语义距离进行衡量。针对属性域的不同，本文首先将敏感属性属性的分为数 值属性和分类属性两种，并对这两种属性分别采用不同的方法来衡量它们值之问的 语义相似关系。实验结果表明基于敏感属性语义关系的隐私保护模型能够很好的解 决属性泄露问题，提供更好的隐私保护效果。所做的工作主要包括： 1 ) 本文首先对数据发布隐私保护的研究现状和发展趋势进行总结，认识到数据 发布隐私保护发展的几大关键问题。针对数据发布隐私保护所面临的属性泄 露问题进行了深入的研究，并阐述相似性攻击问题和近邻漏洞问题产生的原 因、对匿名数据集的影响以及国内外解决方法。认识到传统的隐私保护模型 并不能有效的解决相似性攻击和近邻漏洞攻击。 2 ) 传统的隐私保护模型主要侧重于对身份泄露问题的研究，而忽略了敏感属性 的语义相似性，容易受到属性泄露的攻击。如：相似性攻击和近邻漏洞攻击 等，会严重损害匿名数据集的隐私保护效果。为此，本文提出了一种基于敏 感属性语义关系的口一s i m i l a r i t yk - a n o n y m i t y 模型。在缸匿名模型很好解决身 7 江苏大学硕士研究生毕业论文 份泄露的同时，增加了对敏感属性相似性的限制，能够有效的解决属性公开 问题，防止相似性攻击的发生。 3 ) 为了精确计算敏感属性相似度，本文首