（计算机应用技术专业论文）基于r树的k匿名技术研究.pdf

内蒙古科技大学硕士学位论文 论文题目：苎三竖塑塑竺垦鱼垫查堕窒 作者： 指导教师： 协助指导教师： 李猛 张晓琳教授 单位： 单位： 单位： 论文提交日期：2 0 1 0 年0 6 月1 2 日 学位授予单位：内蒙古科技大学 信息工程学院 。一塞0 i ， !_ | ，lr py一，吖，霎_纠争薏囊嚣p一分hi 基于r 树的雌名技术研究 r e s e a r c ho nk - a n o n y m i t yt e c h n o l o g yb a s e do nr - t r e e 研究生姓名：李猛 指导教师姓名：张晓琳 内蒙古科技大学信息t 程学院 包头0 1 4 0 1 0 ，中国 a n d i d a t e - l i m e n g s u p e r v i s o r ：z h a n gx i a ol i n s c h o o lo fi n f o r m a t i o ne n g i n e e r i n g i n n e rm o n g o l i au n i v e r s i t yo fs c i e n c ea n dt e c h n o l o g y b a o t o u0 1 4 0 1 0 ，p r c h i n a c 独创性说明 本人郑重声明：所呈交的论文是我个人在导师指导下进行的研究工 作及取得研究成果。尽我所知，除了文中特别加以标注和致谢的地方 外，论文中不包含其他人已经发表或撰写的研究成果，也不包含为获得 内蒙古科技大学或其他教育机构的学位或证书所使用过的材料。与我一 同工作的同志对本研究所做的任何贡献均已在论文中做了明确的说明并 表示了谢意。 签名址嗽掣、 关于论文使用授权的说明 本人完全了解内蒙古科技大学有关保留、使用学位论文的规定， 即：学校有权保留送交论文的复印件，允许论文被查阅和借阅；学校可 以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保 存论文。 ( 保密的论文在解密后应遵循此规定) 签名：建垃一 导师签名：鍪蠡遂日期：砂夕p 内蒙占科技人学硕十学位论文 目录 摘要i a b s t r a c t i i l 绪论l 1 1 研究背景1 1 。2 研究意义2 1 3 国内外研究现状3 1 3 1k 一匿名技术的发展过程3 1 3 2k 匿名算法的划分和分析3 1 3 3 索引匿名技术的研究现状及分析4 1 3 4 空问索引技术在匿名数据集方面的优势5 1 4 本文的主要研究内容6 2 基于r 树k 一匿名技术的理论基础7 2 1 隐私保护技术的分类7 2 2k 一匿名的基本概念和方法1o 2 2 1i ( - 匿名的基本概念一lo 2 2 2l ( _ 匿名的基本方法1 0 2 3r 树的基本原理1 2 2 4 聚类算法的基础知识1 4 2 5 聚类问题转化为k 匿名问题17 3r 树k 匿名实现算法2 0 3 1 数据预处理2 0 3 1 1o i 属性向空问点数据的转化2 0 3 1 2 数据清洗2 0 3 1 3 空间点数掘向审f h j 矩形的转化2 3 3 2 动态r 树的构造算法2 4 3 2 1r 树的初始化2 4 3 2 2k m e a n s 多路分裂算法的描述2 4 3 3 聚类效果的判定算法2 6 内蒙占科技人。学硕士学位论文 3 4 确定平移对象2 7 3 5 添加噪声2 7 3 6 修改数据2 8 3 7k 一匿名衰的生成2 8 4 实验测试和结果分析3 0 4 1 实验环境3 0 4 2 实验数据3 0 4 3 测试结果及分析一3 0 5 结论3 3 参考文献3 4 在学研究成果3 8 致 谢3 9 内蒙_ 占科技人学硕- ：学位论文 摘要 在当今的信息社会，信息的电子化和网络技术的发展，为大规模信息的共享提供了 便利快捷的手段。与此同时，也为隐私保护提出了新的挑战。面l 】信息共享的隐私保护 技术的研究，方面r 口j 以为防t t ：乐l 、仃敏感信息的泄漏提供有力的技术保障，消除信息拥 有者在共享信息时的顾虑，促进信息交流和共享；另一方面还强调减少实施隐私保护所 带来的非敏感信息损失，保证共享信息的质量，提高共享信息的可用性。 现有的隐私保护算法大都是针对静态数槲集的漩名处理，f f l 是频繁接触的数击| i ：集大 多是动念的，针对动念数据集隐私保护算法的研究将是未来的热点。随着数据库索引技 术的h 益成熟，基于空问索引的r 树的k - 匿名技术，具有很好的扩展性且能支持增量的 数掘发信。但对于固定的m ( r 树节点中索引项的最大值) ，随着k 值的不断增大， 已有的：二路分裂算法不是涉及剑具体的m b r ( 最小限制矩形) 增量，根节点下面的孩 子节点索引项之间的相似度较差，隐私保护程度降低，影响了匿名的质量。 基于k m e a n s 多路分裂算法的r 树k 一匿名技术，较好的解决了对于固定的m ，随 着k 值的增大，节点相似性的| 口j 题，有效地提高了匿名质量；基于k - m e a n s 多路分裂算 法所构造的r 树更加合理，降低了m b r 的相交的面积，从而提高了匿名表的食询效 率。 通过实验证明，基于k - m e a n s 多路分裂算法的r 树k 匿名技术，有效地提高了匿 名质量和匿名表的查询效率。 关键词：r 树；k _ 匿名：k - m e a n s 多路分裂算法；动态数据 内蒙占科技人学硕仁学能论文 一一 a b s t r a c t i nt o d a v t si n f o r m a t i o ns o c i e t y ，e l e c t r o n i ci n f o r m a t i o n a n dn e t w o r kt e c h n o l o g y1 0 r l a r g e - s e a l ei n f o r m a t i o ns h a r i n gp r o v i d e s ac o n v e n i e n ta n de f f i c i e n tm e a n s a tt h es 锄et i m e , p r i v a c yp r o t e c t i o nf o rn e wc h a l l e n g e sp r e s e n t e d p r i v a c yp r o t e c t i o n f o ri n f o 肿a t l o n s n a n n g t e c h n 0 1 0 9 yr e s e a r c h ，o nt h eo n e h a n dt op r e v e n tl e a k a g eo fs e n s i t i v ei n f o r m a t i o np r i v a t et o p r o v i d es t r o n gt e c h n i c a ls u p p o r t ，a n dr e m o v ei n f o r m a t i o no w l l e r s t os h a r em f o 肿a t l o nmt h e c o n c e m ，a n dp r o m o t ei n f 0 仃n a t i o ne x c h a n g ea n ds h a r i n g ；o n t h eo t h e rh a n da l s os t r e s s e dt h a t t h ei m p l e m e n t a t i o no fp r i v a c yp r o t e c t i o nt o r e d u c et h el o s s e sc a u s e db yn o n s e n s l t l v e i n f o h n a t i o na 1 1 d e n s u r et h eq u a l i t yo fi n f o r m a t i o ns h a r i n g ，i m p r o v e t h es h a r i n go f i n f o r m a t i o na v a i l a b i l i t y e x i s t i n gp r i v a c yp r o t e c t i o na l g o r i t h m s f r e q u e n tc o n t a c tw i t hm o s to ft h ed a t as e t f o rs t a t i cd a t as e ta n o n y m o u st r e a t m e n t ，b u t i sd y n a m i c ，t h ed y n a m i cd a t as e tf o rp r i v a c y p r o t e c t i o na l g o r i t h mw i l lb e t h en e x th o ts p o t w i t ht h ei n d e xd a t a b a s et e c h n o l o g i e s b e c o m em o r es o p h i s t i c a t e d ，r t r e es p a t i a li n d e xb a s e do nt h ek - a n o n y m i t yt e c h n i q u e ，h a s g o o ds c a l a b i l i t y a n dc a ns u p p o r tt h ei n c r e m e n t a ld a t ar e l e a s e ，h o w e v e r ，f o r 丘x e dm ( r t r e en 0 1 1 e t h em a x i m u 】mv a l u eo fi n d e xe n t r i e s ) ，a s t h ekv a l u ei n c r e a s i n g ，t h ee x m t l n gt w o 。s p l i t t i n g a l 甜吼i sn o tr e l a t e dt ot h es p e c i f i cm b ri n c r e m e n t ，c h i l d r e n b e l o wt h e 瑚tn o d et i l e s i m i l a r i b 酣v e e nt h ei n d e xe n t r i e sp o o r ，l e v e lo fp r i v a c yp r o t e c t i o nr e d u c e d ，a f f e c t i n gt h e q u a l i t y o fa n o n y m i t y b a s e d0 nk _ m e a l l sa l g o r i t h mf o rm u l t i s p l i tr - t r e ek - a n o n y m i t yt e c h n i q u e ，t h eb e t t 盯t o s o l v et 1 1 a tf o rf i x e dm ，w i t ht h e c o n t i n u o u si n c r e a s eo f kv a l u e ，t h en o d es i m i l a rp r o b l e m ，h a s e f 敝t i v e l vi m p r o v e dt h ea n o n w n o u sq u a l i t y ；b a s e do nk - m e a n s a l g o r i t h mf o rm u l t i 。s p l i tr - t 嗽 i sm o r er e a s o n a b l e ，t or e d u c et h es i z eo f t h ei n t e r s e c t i o no ft h em b r ，t h u si m p r o v i n gt h eq u c r y e f f i c i e n c ya n o n y m o u s t a b l e n ee x p 甜m e n tp r o v e dt h a t ，b a s e do nk - m e a n sm u l t i p l er t r e es p l i a i n ga l g o r i t h m k 。 a n o n y m i t yt e c h n i q u e ，e f f e c t i v e l yi m p r o v e t h eq u a l i t yo fa n o n y m i t ya n da n o n y m o u st a b l eo f q u e 珂e f f i c i e n c y k e vw o r d s ：r t r e e ；k - a n o n y m i t y ；t h ek - m e a n sm u l t i s p l i ta l g o r i t h m ；d y n a m i c d a t a 内蒙古科技大学硕士学位论文 1 绪论 1 1 研究背景 数据挖掘技术的出现为人们从大型数据库中发现有用的模式和趋势提供了工具。目 前，数据挖掘被广泛应用于多个领域，尤其是在电信、银行、保险、交通、零售等商业 领域。一个公司为了更好地管理客户，需要对收集到的数据进行挖掘，此时数据源中可 能含有能够识别客户身份的一些标识，如姓名、地址、电话号码等，泄露这些信息将可 能侵犯客户的隐私。当然，为了符合隐私管理的要求，管理员可能会从提交的记录中删 除这些标识。但是发布的数据也不表示受到完全的保护，客户的记录可能包含一些到其 他数据库的关联属性，从而可以识别出客户特征和身份的信息。当这些数据被合并使用 时，就容易侵犯到客户的个人隐私；由于工作、生活和学习的关系，人们需要向学校、 银行、医院等机构和企业提供自己的个人信息。这些信息可能会被共享以满足机构运 作、企业经营发展以及科学研究等需求。但是这些信息中常常含有一些敏感信息，与人 格、尊严、隐私有着密切的关系，如果在信息共享中被泄漏将会侵犯到个人隐私权盹 在当今社会，由于社会分工的日益细化和全球经济的一体化，企业之间协作和信息 共享日益频繁。虽然信息共享为合作双方在降低生产经营成本、开拓新市场等方面都带 来了很大便利，但是对于企业自身的商业秘密( 也称之为商业隐私) 也带来了威胁1 2 】。从 商业竞争的现实性考虑，商业隐私的泄漏无疑将严重破坏企业的核心竞争力，使之在竞 争中处于被动的不利地位：举例来说，两家银行有一个记录了客户账户活动情况的数据 库，为了其共同利益，这两家银行决定合作，在他们的数据库中进行关联规则挖掘。然 而其中一家或者两家银行都绝对不想公开他们数据库中的一些战略性的模式，也称限制 的关联规则给其他的银行，他们想通过转换数据来使得战略性的模式隐藏，而另外的模 式与其它的银行分享。此时，如果无法隐藏战略性模式也可认为侵犯了隐私。 另一方面，随着电子化数据的爆炸式增长，数据挖掘技术被广泛应用以发现和抽取 数据中隐含的有用知识信息，如某商场的消费者购买行为特征等等，但是也加剧了隐私 泄漏的风险。因为数据挖掘发现的知识不仅可用于从非敏感信息推导出敏感信息，同时 数据挖掘发现的一些知识本身可能就是敏感信息，涉及到国家安全、商业秘密和个人隐 私等等。这就要求不仅对原始数据，而且对从原始数据导出的知识，都能够提供有效的 隐私保护技术。 注，并且涌现出越来越多的隐私保护技术。对于未来隐私保护技术的发展，首先，隐私 保护程度的度量标准的一致性是今后隐私保护挖掘算法的个重要衡量指标。统一隐私 保护的度量标准，就能够使得不同隐私保护算法的性能得以转换成标准度量，从而达到 算法之间的可比性。其次，准确性，即个有效的解决方案应该能够在隐私和挖掘结果 的精确度之间找到平衡。另外，目前所有隐私保护的数据挖掘算法都是基于全部数据处 于加密保护状态下进行研究的，对于数据只有部分加密和全部数据未经加密的情况，现 有的隐私保护挖掘算法都不能适用。因此，部分加密和未加密数据的隐私保护技术将是 未来挖掘算法研究的方向之一最终，数据挖掘的隐私保护技术应当形成具有适应多种 数据集、统一的隐私保护程度度量标准、适用于分类【3 l 、关联规则嗍、聚类 5 1 等数据分 析技术和挖掘技术的整体模型。 例如企业的员工数据，医院的病例数据，政府的各项经济指标数据和人口统计数 据等等，都是动态变化的。如何保证动态数据集的匿名质量和共享信息的可用性，将是 隐私保护技术相当重要的研究领域。 当今国际上一系列关于信息隐私权保护的政府报告、行为指引与示范法当中阐述了 若干已被普遍遵守的核心原则，其中著名的公平信息实施原则是专注于数据隐私保护的 一个原则，它涵盖了数据收集、使用、公开、个体参与和责任等方面的内容。它包含以 下要求： ( 1 ) 目的说明和使用限制收集数据的时候必须指定数据的使用目的，不能超出此 目的的范围使用数据。 ( 2 ) 公开性人们有权利知道关于他们的什么样的信息被收集，由谁来访问该数 据，以及数据将被如何使用。依据这些原则，在挖掘收集到的信息时必须考虑如何进行 隐私保护。这就产生了数据挖掘中隐私保护的问题。即如何在保证个人和公共隐私的前 提下进行数据挖掘。 内蒙古科技火学硕士学位论文 1 3 国内外研究现状 1 3 1k - 匿名技术的发展过程 1 9 9 8 年s a m a r a t ip 和s w e e n e yl j 6 7 】提出k - 匿名技术，它要求公布后的数据中存在一 定数量的不可区分的个体，使攻击者不能判别出隐私信息所属的具体个体，从而防止了个 人隐私的泄密。k 匿名自提出以来，得到了学术界的普遍关注，国内外很多学者都从不同 层面研究和发展了该技术。 2 0 0 1 年，s a m a r a t ip 【8 】采用泛化和隐匿技术实现k - 匿名来保护个体隐私信息，并给出了 k 最小匿名化定义；i b mw a s t o n 实验室的i y e n g a rv 9 】提出基于遗传算法的不完全随机 搜索方法，解决了k 匿名中的数据挖掘分类问题；y a oc 等【l o 】给出视图中的k - 匿名验证 问题；m a c h a n a v a j j h a l aa 等【】的1 多样性算法是k - 匿名的改进模型，它保留了数据表中足 够多的信息，不足之处是该算法只适用于单个个体对应单条元组的数据表，对单个个体对 应多条元组的数据表的隐私信息不能保证，而且该算法一次只能处理一个敏感属性；于戈 等0 2 1 对单一约束k - 匿名化方法进行扩展，提出了多约束k - 匿名 1 3 , 1 4 方法 c l a s s f l y + ，c l a s s f l y + 继承了c l a s s f l ) j 1 5 , 1 6 1 的元组泛化思想，减少了信息损失，保证了匿名精 度。 2 0 0 6 年s i g m o d 会议上，) ( i a o k u ix i a o 等【l 刀提出了基于人性化匿名的新泛化框架，该 方法实现了满足个体需求的最小泛化，保留了原数据中大量信息。a g g a l - w a l 1 8 j w 论t 高 维情况下k - 匿名的灾难。 1 3 2l - 匿名算法的划分和分析 1 、k - 匿名算法的划分： 目前已出现很多算法来实现k - 匿名，下面从不同的角度对其进行划分： 从泛化约束角度，可将k - 匿名算法划分成两类即全域泛化和局部泛化全域泛化指 准标识符中的整列属性均同时被泛化成一般域，它要求给定属性的所有值都属于同一个 域，s a m a r a t ip 【1 9 1 设计了一种寻找最小全域泛化的二叉搜索算法。文献描述了实现全域泛 化的贪婪启发式算法d a t a f l y , 文献例提出了一种高效率全域k - 匿名化方法局部泛化指 在域泛化层的某一子树中搜索局部最小匿名，即仅泛化属性列中的某些单元，并非整个属 性列。文献【2 l 】采用遗传算法搜索局部最小匿名，它使用单维全子树编码模型和单维有序 集划分模型分别来泛化描述型属性( 如性别等) 和数值型属性( 如年龄等) 从数据分布方式角度，可分为分布式数据匿名化和集中式数据匿名化。大多数k - 匿 名算法主要基于集中式数据库进行设计。然而，当在双方或多方合作进行数据挖掘时，由 于某种原因，参与者往往不愿将数据与他人共享，而只愿共享数据挖掘的结果。这就要求 内蒙古科技大学硕士学位论文 人们对此类数据库的匿名化提出相应的算法。目前针对分布式数据，主要的算法有 j i a n g 提出了一种通信协议，数据所有者遵循该协议合并分布式的数据来获得匿名表。z h o n g 2 2 】 等通过构建一个横向划分表来取代分布式k - 匿名方法 从维数角度，可分为单维k 匿名吲和多维k - 匿名两大类。单维k _ 匿名指每个值只 有一种泛化类型。l e f e 、r r e 【刎等提出了卜匿名的多维模型，他指出这类泛化问题属于 n p 难题，提出了一种贪婪近似值算法。 从推理攻击角度，m a c h a n n v a j j h a l aa ( 1 1 】等描述了两种可能的推理攻击，即同质推理 攻击和背景知识推理攻击。同质推理攻击指攻击者根据k _ 匿名表能1 0 0 地推导出某个 体的敏感信息背景知识推理攻击指攻击者利用预先知道的某些额外信息来进行攻击。 从具体算法的研究方法来看，k - 匿名除了对泛化和隐匿技术进行改进外，还与其它 方法相混合，如s o c ( s t a t i s t i c a ld i s c l o s u r ec o n t r 0 1 ) 。d o m i n g o - f e r r e r 等 5 1 提出了 微聚类法( m i - c r o a g g r e g a t i o n ) ，该方法将类的范围设定在 k ，2 k 之间，要求将数据集划 分成多个类，每个类中至少包含k 个元组。最优k - 划分准则为：在同一类中的元组之间 尽可能“接近 或相关而不同类中的元组之间尽可能“远离一或不同，使得信息的丢 失量会尽可能的少。 2 、k - 匿名算法的分析： 文献 3 1 描述了实现全域泛化的贪婪启发式算法d a t a f l y ，尽管其泛化结果能达到k - 匿名，但它并不能保证得到的是最小匿名化表。 文献刚提出了二种高效率全域k - 匿名化方法，减少了执行时间，但文献没有针对信 息损失给出有效的解决方案。筒而言之，全域泛化常常导致不必要的信息丢失。 l c 刚矧等提出的k - 匿名的多维模型，虽然在匿名的精确性方面考虑的很多， 但是却忽略了匿名的质量。 1 3 3 索引匿名技术的研究现状及分析 1 、索引匿名技术的研究现状 目前绝大部分k _ 匿名算法是基于单维的如i _ t - a r g u s 算法刚、d a t a f l y 算法 5 1 文献【1 2 1 基于k d 树提出了在多维空间里面进行分析，从而产生了在多维空间内的 k - 匿名算法。 文献【2 5 l 基于r 树的多维k - 匿名实现算法，利用经典的空间索引技术来实现一匿 名，具有很好的扩展性且能很好地支持增量的数据发布： 。 可扩展到大的数据集中( s c a l a b i l i t yt ol a r g ed a t as e t s ) 批量加载( b u l k - l o a d i n g ) 数据库索引技术把焦点放在了内存驻留的数据集上，大 量的批量加载技术被应用n t 空间索引中： ( 1 ) 基于空间填充曲线( s p a c e - f i l l i n gc u r e s ) 的分类批量加载技术 内蒙古科技大学硕士学位论文 ( 2 ) 基于缓冲区树( b u f f e r t r e e ) 的非分类批量加载技术 增量效用( i n c r e m e n t a lu t il i t y ) 早期的匿名化算法把没有匿名的数据集作为一个整体进行输入，产生完整的匿 名后的数据集作为输出，如果想要用这些算法匿名更新的数据集，唯一的途径就是重 新匿名原始数据加新的数据记录对于频繁的更新来说，这样的做法显然是没有效果 的 随着数据库索引对记录的插入，删除和更新操作日益成熟，并把它应用到了匿名 技术中，我们得到了一个动态机制叫增量匿名 2 、索引匿名技术的分析 文献【3 l 中介绍的d a t a f l y 算法，不能从整体上保证隐私保持的完整性，也不能保证 算法的有效性。 文献【叼介绍的k _ d 树是要求先给出所有的点，然后根据这些点来进行空间的划 分。这样的划分往往是针对某一固定数据集，或者对数据改动比较小的情况下而采用 的。对于一些经常变动的数据集，如频繁进行插入和删除，要产生卜匿名化数据，则 需要重新对整体空间进行划分，这样往往会带来效率上的问题。因此，基于k - d 树的 k _ 匿名算法不适用于动态变化的数据。 文献瞄l 提到的基于r 树的多维k - 匿名实现算法适用于频繁更新的数据集，具有 很好的扩展性且能支持增量的数据发布，但对于固定的m ，随着k 值的不断增大，隐私 保护程度降低，影响了匿名的质量。基于k - m e a n 多路分裂算法的r 树，较好的解决了 对于固定的m ，随着k 值的增大，节点平均分配的问题，有效地提高了匿名质量。基于 k - m e a n s 多路分裂算法的r 树，节点间的相似程度加大，降低了相交的面积，从而提高 了匿名表的查询效率。 1 3 4 空间索引技术在匿名数据集方面的优势 随着数据库的索引技术的日益成熟，它提供了有效和动态的匿名技术，比单一的匿名 算法具有如下优势： ( 1 ) 有效的索引结构算法，对数据集提供了更快的批量匿名时间 ( 2 ) 支持批量加载的索引结构算法，匿名的数据集可以达1 0 0 ，0 0 0 ，0 0 0 条记录 ( 3 ) 在没有考虑最小包围矩形索引域留下的间隙的情况下，可以对匿名数据提供更高 的精确性 ( 4 ) 空间索引技术可以通过在特殊q i 属性上建立索引和有偏分割算法两种方式来减 少查询工作量 内蒙古科技大学硕士学位论文 1 4 本文的主要研究内容 随着网络信息技术的发展，人类大量信息被政府部门、商业机构等存储、发布， 这极大激发了各部门从海量数据中挖掘有用信息的需求。但事物往往具有两面性，当数 据挖掘用于公开分析大量的私人信息( 如购物习惯、犯罪记录、病史、信用记录韵 时，它在为人们提供强大知识发现功能的同时，也对个人隐私带来威胁。 现有的隐私保护算法大都是针对静态数据集的匿名处理，但是频繁接触的数据集大 多是动态的，基于r 树的k 匿名技术，具有很好的扩展性且能支持增量的数据发布 但由于受到原始二路分裂算法的影响，对于固定的m ，随着k 值的不断增大，分裂算法 已经完全根据平均分配而言，而不是涉及到具体的m b r 增量，该k 匿名化已经效果不 佳，因为分裂的时候基本没有考虑m b r 因素，从而一个根节点下面的孩子节点相似度 不够，隐私保护程度降低，影响了匿名的质量。 基于k - m e a n s 多路分裂算法的r 树k 匿名技术，较好地解决了对于固定的m ，随 着k 值的增大，节点平均分配的问题。通过实验证明，基于k - m e a n s 多路分裂算法的r 树k 匿名技术有效地提高了匿名质量和匿名表的查询效率。具体步骤如下： 1 、数据预处理：q i 属性向空间点数据的转化：数据清洗；空间点数据向空间矩 形的转化。 2 、动态r 树的构造算法：r 树的初始化；二路节点分裂算法及其不足； k - m e a n s 多路分裂算法的描述 3 、k _ 匿名表的生成 4 、性能测试 5 、相关工作总结 ( 1 ) 值替代方法，按不可倒推的方法用一个新的值替代原有的值；或者用一个符 号如“? 一替代一个已存在的值，以保护敏感数据和规则； ( 2 ) 聚集方法，就是将几个值进行合并或抽象而成为个相糙集； ( 3 ) 交换方法，就是单个记录间值的交换； ( 4 ) 取样方法，就是抽样，用于挖掘的数据只是总样本中的一个样本。 3 、数据挖掘算法 目前数据隐藏技术都是在每一个数据挖掘算法中单独进行考虑的。例如：决策树算 法、关联规则算法、粗糙集以及聚类等数据挖掘算法。 4 、隐私保护的对象 主要是指针对原始数据或其隐含的规则的隐藏。以规则的形式隐藏聚集数据的层次 比隐藏原始数据要高。通过保护敏感规则，同样可以保护重要的原始数据。 5 、隐私保护技术 指修改原始数据所采用的技术。修改能使隐私在不受危害的情况下获得较高的技术 实用性有效减少有用信息的丢失。隐私保持技术主要分三类： ( 1 ) 基于启发式的隐私保持技术：仅修改特定值来减少挖掘效果的偏离修改数据 的方法主要有：值替代和分组。s t a n l e yrm 0 1 i v e i r a 提出了一种频繁项集挖掘算 法，通过一个基于倒排文件索引和布尔查询的检索引擎来过滤数据。举例来说：设d 是源数据库，r 是能从d 中挖掘出的重要的频繁模式，rh 是r 中需要隐藏的规则，rp 是需要隐藏的模式，rp = r ，则当且仅当r p 能够推导出r h 。如何将d 转换为向外界公 开的d ，同时也能从d 中挖掘出除了r h 以外的所有规则。为了达到这个目的，必 须有选择地修改数据，使得敏感规则的支持度降低。数据处理方法是，从d 中找出所 内蒙古科技大学硕士学位论文 有r ，将r 根据安全规则分成r h 和r p ，再根据检索引擎将d 中的敏感规则找出来，运 行删除限制模式的处理算法，将d 找出来。 ( 2 ) 基于密码学的隐私保持技术：利用密码学方法来进行数据加密，基于密码学的 隐私保持技术针对的数据对象是分布式的。因此，它包括分布式数据的垂直分割与水平 分割两种情形。对于数据垂直分割的情形，w e n l i a n gd u 根据安全标量积协议提出了一 个系统转换结构允许将一个计算转换为安全的多方计算。假设有分布站点a 、b ，s 表示 其代表的数据集；b i 表示第i 个属性；e a 表示仅与a 站点有关的属性的表达式，e b 表示仅与b 站点有关的属性的表达式；v 表示n 维矢量，v a ( i ) - i 表示a 站点第i 个记 录满足e a ，v a ( i ) = 0 表示a 站点第i 个记录不满足e a , 同理假设v b , y j ( i ) = 1 表示第i 个记录属于类j ，v j ( i ) = o 表示第i 个记录不属于类j ；p j 表示s 中类j 的记录数。则 个非零项v = v a v b 表示同时满足e a 和e b ，因而属于数据集s 为了创建判定树，需 找出v 中非零项的记录数个数，即求p j = v a ( v b v j ) ，为了不向a 、b 站点对方互相暴露 属性，提出了通过第三方生成随机n 维向量经计算后互换的方法。根据p j 计算 e n t r o p y ( s ) 和6 a i n ( s ，b e i ) ，从而不断找到最佳分裂属性和分裂点，直至建立判定 树。对于数据水平分割的情形，y e h u d al i n d e l l 提出依据不经意求值协议依赖一个半 可信第三方，通过寻求双方站点中的最佳属性来建立判定树。 该方面的相关研究主要是将安全多方计算( s e e u r e m u l t i p a r t y ( ：o i i l p u t a t i o n ) 的 思想应用于分布式数据挖掘中，以实现对参与挖掘计算各方的原始数据的隐私保护，同 时能够让参与计算的各方共享挖掘所得的全局知识。安全多方计算的概念最初在文献i 碉 中提出，要求在保证各参与方自有数据的隐私性基础上，完成所需的协同计算。各参与 方可以得到协同计算的结果，但是不能得知除了自己以外其它方所拥有的具体数据信 息。其基本思想是在协同计算的过程中，由参与计算各方将经过加密处理的数据信息传 送给其它方作为计算的输入。但是对于数据挖掘来说，数据量很大和实际计算的复杂 性，一般性的安全多方计算方法在许多具体情况下并不适用。因此，需要针对具体的数 据挖掘任务和数据的分布情况，来设计具体的安全多方计算方法。这一类的工作侧重于 实现安全多方计算的加密协议的研究，具体包括以下一些工作： 文献基于p o h l i g h e l l m a n 加密算法，提出了面向水平分布数据的关联规则挖掘 的安全多方计算方法。文献i z 7 j 提出了面向垂直分布数据的关联规则挖掘的安全多方计算 方法，该方法实质上是一个基于代数运算的安全标量乘运算协议。文献c z 8 】将文献闭的工 作扩展到可支持连续型属性( 经离散化处理) 的量化关联规则挖掘。文献 2 9 1 在以前工作的 基础上，给出了面向安全多方计算的求和、集合并、求交集大小以及标量乘等四种基本 协议，并提出了基于这些基本协议的关联规则挖掘和聚类挖掘方法。 内蒙古科技大学硕士学位论文 针对数据水平分布在两个站点的情况，给出了建立全局i d 3 决策树的方法；针对数 据垂直分布在两个站点情况下，给出了基于安全标量积协议来建立决策树的方法，随后 将这一工作扩展到数据垂直分布在多个站点的情况。 文献刚和p 1 】分别针对水平分布的数据和垂直分布的数据，给出了建立朴素贝叶斯分 类器【3 2 】的安全多方计算方法。文献1 3 3 1 针对水平分布的数据和垂直分布的数据，给出了建 立s v m 分类器刚的安全多方计算方法。针对垂直分布的数据和水平分布的数据，给出 了k m e a n s 聚类的安全多方计算方法；随后文献【3 5 l 将这一工作扩展到可处理任意分 布的数据。文献p q 利用安全求和协议，给出了基于期望最大化的分布式聚类的安全多方 计算方法。 ( 3 ) 基于重构的隐私保持技术：将数据进行变换后，再进行重构原始分布，重构 技术都是针对集中式分布的数据源，主要分为数值型数据的重构技术以及二进制数据与 分类数据的重构技术。r a k e s h g r a w a l 提出了用离散化的方法与值变形的方法，通过 添加随机偏移量来修改原始数据，然后用重构算法构造原始数据的分布，这种算法只针 对集中式分布的数值型数据有效。对于二进制数据与分类数据的重构技术， a l e x a n d r e e v f i m i e v s k i 利用了随机化技术对部分数据进行修改的关联规则挖掘算法， s j r i z i v 等人则是利用贝努利概率模型对数据进行修改的关联规则挖掘算法，既保证 了数据的使用率又达到了隐私保护的目的。 该方面的研究考虑这样的情况：数据拥有者要共享数据给他人做挖掘分析，但是数 据拥有者又不愿意透露原始数据的精确值，以免造成隐私泄漏。由于数据挖掘着重于从 大量数据中发现具有统计意义的知识，数据项自身的精确性对于数据挖掘的结果影响不 大。所以只要能够保持数据的分布特性，或者能够重构数据的分布特性，就可以保证数 据挖掘结果的准确性。基于这一思想，数据拥有者可以事先对原始数据做一定的干扰处 理，然后共享经干扰处理后的数据，这样就不会泄漏精确的原始数据值。而数据接收者 可以在经干扰处理后的数据上，来挖掘发现相关知识。如果干扰处理改变了原始数据的 分布特性，则数据拥有者还需要提供干扰处理相关参数，以便数据接收者能够重构原始 数据的分布特征。这一类的工作侧重于数据干扰方法及其随后的数据分布重构的研究， 典型的研究工作包括：在关联规则挖掘方面，文献p 7 】提出根据贝努利概率模型对原始数 据做随机变换处理，并提供了一种称为m a s k 的方法，可以在干扰数据集上挖掘并进 一步反推出原始数据集上的关联规则。文献i 弼j 提出了一种基于“s e l e c t a s i z e 和“e u t a n d p a s t e 随机变换操作来隐藏原始数据集的方法，并给出了从变换后 的数据集中挖掘和导出原始数据集上的关联规则的过程。文献例提出基于部分隐藏的随 机响应技术，以对原始数据进行变换和隐藏，并给出了相应的隐私保护关联规则挖掘算 法。 内蒙古科技大学硕士学位论文 2 2 1l 滩名的基本概念 定义l ：k - 匿名：令t a 。，如e e o a i ) 是个表，q i 是与t 相关联的准标识符，当 且仅当在t q i 中出现的每一个有序的值至少要在t q i 中出现k 次的话，我们就说t 满足卜匿名 定义2 ：k _ 最小匿名化：给定数据表t i 、t j ，毛为t i 的匿名表，标记为1 讯，m a x s u p 为 可以接受的最大隐匿数。t i 是数据表t i 的最小匿名表，当且仅当满足：( 1 ) t j 满足k _ 匿名， 且其隐匿的元组数要少于m a x s u p ，即it i | _ ir ji 姗a x s u p 。( 2 ) 不存在泛化表t z ，t z 满足 k - 匿名，隐匿数少于l l a x s u p ，且泛化的程度小t i 。 定义3 ：类标识符( q i ) ：对于一个表f r r ( a 1 ，a 2 ，a n ) ，若j 属性集合q b i ， j ，满足对于另外一个独立数据表t ( b i ，b 2 ，b n ) ，q b i ，j s a 1 ，a 2 ， a n 并且q b i ，e g oj s b l ，b 2 ，b n ，使得| 元组t ，满足t i ，j s f r r ( i ，j ) t i ，j s t ( i ，j ) ，则称属性集合q b ( i ，j ) 为类标识符。 定义4 ：敏感属性( s e n s i t i v ea r t r i b u t e ) ：包含个人隐私数据的属性，如疾病、 薪水等。 定义5 ：等价组：在准标识符上的具有完全相同的记录组成等价组，即：等价组中 所有记录在准标识符上的属性值完全相同，其他属性可以不同。 2 2 2l r 匿名的基本方法 k _ 匿名主要通过泛化和隐匿技术实现，这两种技术不同于扭曲、扰乱、随机化等方 法，它们能保持数据的真实性。在典型的关系型数据库系统中，经常用域来描述属性值的 集合。比如：邮政编码域、数值域、时间域等。泛化主要涉及两个概念：域泛化和值泛 化。域泛化通常是将一个给定的属性值集合概括成一般值集合，比如原始邮政编码域 9 4 1 3 8 ，9 4 1 3 9 ，4 1 4 1 ，9 4 1 4 2 ，通过去掉最右数字，泛化成 9 4 1 3 ，9 4 1 4 ，使得语义上指示 了一个较大范围，该范围称为泛化域( d o m ) ，泛化域包含各自原先的泛化值，并且两者之间 存在一一对应关系，标记为d 。 给定隐私表t 关于属性a 的两个域d i 、d j ，如d j e d o m , d i r d d j 表明域d i 中的值是域d i 中的泛化值。泛化关系d 在一系列域上定义了一个偏序关系，该关系要求满足以下两 个条件： c 1 ：& d bd ；，d z e d o r a ：d i 弋 d d $ ，d i d d z d j d d z v d z 吗。 c 2 ：所有d o m 的最大元素都是单个值。 条件c 1 说明，对于任意域d i ，其域泛化集是有序的，故域d i 至多只有一个直接泛化 内蒙古科技大学硕士学位论文 域d j 。条件c 2 保证每个域中的所有值总能被泛化到单个值。泛化关系的定义决定了域 泛化层的存在，标记