（计算机软件与理论专业论文）数据表匿名化的微聚集算法的研究.pdf

数据表匿名化的微聚集算法的研究 摘要 忌匿名作为一种简单有效的私有数据的保护技术得到了广泛的关注。它要求发布的 数据中存在一定数量( 至少为勋的在准标识符上不可区分的记录，使攻击者不能判别出 隐私信息所属的具体个体，从而保护了个人隐私。目前存在的珏匿名算法大都基于泛化 隐匿技术，然而，泛化隐匿技术在效率、连续性数据的语义保持等上存在一定的缺陷。 近年来，微聚集( m i c r o a g g r e g a t i o n ) 技术被应用到数据表的珏匿名化上，弥补了泛化隐匿 技术的不足，其基本思想是：将大量的数据按相似程度划分为若干类，要求每个类内元 组数至少为k 个，然后用类质心取代类内元组的值，实现数据表的结匿名化。 本文研究了全局搜索的微聚集算法，实现了面向混合型数据的微聚集算法，并且提 出了面向微聚集算法的评估模型，主要研究工作如下： ( 1 ) 提出了基于免疫克隆选择的微聚集算法( i c s m a ，i m m u n ec o l o n a ls e l e c t i o n m i c r o a g g r e g a t i o n a l g o r i t h m ) ，提高了微聚集算法产生的匿名数据的质量。该算法在传统 的克隆选择算法的基础上，引入调整算子，在抗体成熟的过程中，删除不合理抗体，加 快了收敛速度。实验结果表明，i c s m 算法较m d a v 算法能生成质量更好的匿名表。 ( 2 ) 针对目前微聚集算法在匿名化分类型数据上的不足，本文提出了一种面向混合 型数据的微聚集算法。该算法中，分类型数据采用层次距离，数值型数据采用欧氏距离， 将这两种距离的结合作为混合型数据的距离，并将数值型数据的均值向量与分类型数据 的众值向量并在一起作为类质心，用该类质心代替类中元组在准标识符上的值，以实现 肛匿名化。实验结果表明该方法在保证匿名表安全的情况下，可以降低匿名表的信息损 失量，提高可用性。 ( 3 ) 提出了微聚集算法的评估模型e m 4 a d o m ( e v a l u a t i o nm o d e lf o rk - a n o n y m i z e d d a t ao r i e n t e dt om i c m a g g r e g a t i o n ) ，该模型从数据的可用性、安全性、可用性和安全性 的权衡三个方面综合评估微聚集算法产生的匿名数据的质量。实验结果表明， e m 4 a d o m 能够较全面地评估微聚集算法。 i 关键词：尽匿名；泛化隐匿；微数据；微聚集：隐私保护；免疫克隆选择算法 m i c r o a g g r e g a t i o na l g o r i t h m f o r k - a n o n y m i z a t i o n a b s t r a c t in e 肛锄o n ”n i t ym o d e l h a sb e e ne x t e n s i v e l yi n v e s t i g a t e d f o ri t s s i m p l i c i wa n d p 贼t i c a b i l i t y t h em o d e l r e q u i r e st h a te l l c hr e c o r di nt h e a 1 1 0 n y m i z e d 讪l eb e 1 溅t l n g u l s h a b l ew i ma tl e a s tk - 1o t h e rr e c o r d sw i t h i nt h et a b l ew i t h r e s p e c tt oas e to f q u a s l 1 d e n t i f l e ra t t r i b u t e s i nt h i s c a s e ，i n d i v i d u a l sc a n n o tb e u n i q u e l yi d e n t i f i e db y a d v e r s 锄e s ，s ot h ei n d i v i d u a l s p r i v a c yc a r l b ep r e s e r v e d m o s te x i s t i n g 七- a n o n y m i z e d a l g o n t l l m sa r eb a s e do ng e n e r a l i z a t i o na n ds u p p r e s s i o nt e c 城q u e s ，w h i c h 1 1 a v es o m e d e 士e c t s o n e m c i e n c y a n d n u m e r i c a ld a t a s e m a n t i c s p r e s e r y a t i o n r e c e n t l y 助c r o a g g r e 鲥0 nt c c l u l i q u e sh a v e b e e ni n t r o d u c e dt oi m p l e m e n t d a t a s e t s 肛a n o n y l n j 删o n ， w m c hr e m e d ys o m ed e f e c t so fg e n e r a l i z a t i o na n d s u p p r e s s i o nt e c 蚵q u e s t h ei d e a0 f m l c r o a g 黜g 鲥o ni st h a tat a b l ei sp a r t i t i o n e di n t os e v e r a lc l u s t e 瑙b a s e do n s o m eh e u r i s t i c m 毗o d s ，w h i c hr e q u i r e se a c hc l u s t e rs h o u l dc o n t a i nk r e c o r d sa tl e a s t t h er e c o r d si nm e s 锄ec l u s t e ra r ea ss i m i l a ra sp o s s i b l e t h e nt h e r e c o r d so fe a c hc l u s t e ra r er e p l a c e d b y 此 c l u s t e r ，sc e n t r o i dt oi m p l e m e n t k - a n o n y m i z a t i o n i nt h i st h e s i s , w ei l l v e s t i g a t ea m i c r o a g g r e g a t i o na l g o r i t 胁f o r 薛o b a ls e a r c hs o l u t i o n 1 m p l e m e n tam i c r o a g g r e g a t i o na l g o r i t h mf o rm i x e dd a t aa n dp r o p o s ea c o m p r e h e n s i v e e v a j u a t l o n 盘锄e w o r kf o rm i c r o a g g r e g a t i o na l g o r i t h m t h e m a i nc o n t r i b u t i o n sa r e 船 f o l l o w e d ： ( 1 ) a ni c s m ( i 姗1 ec i 。n a ls e l e c t i o nm i c r o a g g r e g a t i o na l g o r i i s p r o p 0 s e d t 0m p wt h e q u a l i t yo fa n o n y m i z e dd a t a , w h i c h i m p r o v e dt h es t 趾d 砌i c s ab y 1 船o d u c l n g 砌u s t i n g0 p e r a t o rw m c hc a l ld e l e t ei n v a l i da n t i b o d y d u d n ga n t i b o d ye v o l u t i o n t oa c c e l e r a t ec o n v e r g e n c cs p e e d t h ee x p e r i m e n t a l r e s u l t ss h o wt h a ti c s m a g e n e r a t e s 锄o n y m l t yt a b i e sw i t l ll e s si n f o r m a t i o nl o s sa n dl o w e rd i s c l o s u r er i s ka sc o m p a r e d w i t l l m d a v a l g o r i t h m am l c a g g r a t i o na l g o r i t h mf o rm i x e dd a t ai sp r o p o s e dt 0 s o l v et h ed r a w b a c k0 f e x l s t l n gm l c r o a g 铲e g a t i o na l g o r i t h m so na n o n y m i z i n gt h ec a t e g o r i c a ld a t a m a l g o 打t 王u i l 1 1 i a d o p t e se u c l i d e a nd i s t a n c ef o rn u m e r i c a ld a t a ，a n da d o p t e sw e i g h t e dh i e r a r c h yd i s t a n c ef o r c a t e g o r i c a ld a t aa n dt h e nc o m b i n e sa b o v ed i s t a n c e sa sm i x e dd i s t a n c ef o rm i x e dd a t a w e t a k em o d ev a l u e sa st h ec e n t e r sf o rc a t e g o r i c a la t t r i b u t e s ，s i m u l t a n e o u s l y , t a k em e a nv a l u e s b et h ec e n t e r so fn u m e r i c a la t t r i b u t e s t h e nt h er e c o r dv a l u e so fe a c hc l u s t e ra r er e p l a c e d b ya b o v ec e n t r o i dt oi m p l e m e n tk - a n o n y m i z a t i o n e x p e r i m e n t ss h o wt h a tt h ed i s t a n c e m e a s u r e m e n tf o r c a t e g o r i c a l d a t ac a u s e sl e s s d i s t o r t i o n ，a n dt h ei m p r o v e d m i c r o a g g r e g a t i o na l g o r i t h mb a s e do nt h em i x e dd i s t a n c ee n j o y sb e t t e rc l u s t e r i n gq u a l i t y t h a nt h et r a d i t i o n a lm d a v a l g o r i t h m ( 3 ) a ne v a l u a t i o nm o d e lf o rk - a n o n y m i z e dd a t ao r i e n t e dt om i c r o a g g r e g a t i o n ( e m 4 a d o m ) i sp r o p o s e d t h em o d e lc a ne v a l u a t em i c r o a g g r e g a t i o na l g o r i t h mf r o mt h e v i e wo fd a t au t i l i t y , i n f o r m a t i o nl o s s ，a n dt h et r a d e o f fo fd a t au t i l i t ya n di n f o r m a t i o nl o s s e x p e r i m e n t a l r e s u l t ss h o wt h a tt h em o d e lc a ne v a l u a t et h e a n o n y m i t y d a t a c o m p r e h e n s i v e l y k e yw o r d s ：k - a n o n y m i z a t i o n ；g e n e r a l i z a t i o n s u p p r e s s i o n ；m i c r o d a t a ； m i c r o a g g r e g a t i o n ；p r i v a c yp r e s e r v a t i o n ；i r t l l t l u n ec l o n a ls e l e c t i o na l g o r i t h m i v 浙江师范大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。论文中除了特别加以标注和致谢的地方外，不包含其他人或其他机 构已经发表或撰写过的研究成果。其他同志对本研究的启发和所做的贡献均已在 论文中作了明确的声明并表示了谢意。本人完全意识到本声明的法律结果由本人 承担。 作者签名：劣靖靖日翌：币多月厂日 学位论文使用授权声明 本人完全了解浙江师范大学有关保留、使用学位论文的规定，即：学校有权保留 并向国家有关机关或机构送交论文的复印件和电子文档，允许论文被查阅和借阅，可 以采用影印、缩印或扫描等手段保存、汇编学位论文。同意浙江师范大学可以用不同 方式在不同媒体上发表、传播论文的全部或部分内容。 保密的学位论文在解密后遵守此协议。 作者签名矽暗暗新獬：韩甥日期：m 7 引月3 日 5 7 浙江师范大学学位论文诚信承诺书 我承诺自觉遵守浙江师范大学研究生学术道德规范管理条 例。我的学位论文中凡引用他人已经发表或未发表的成果、数据、 观点等，均已明确注明并详细列出有关文献的名称、作者、年份、 刊物名称和出版文献的出版机构、出版地和版次等内容。论文中未 注明的内容为本人的研究成果。 如有违反，本人接受处罚并承担一切责任。 承诺人( 研究生) ： 磅固乎增 指导教师：珲专远民 5 8 1 1 研究背景及意义 1 绪论 数据挖掘出现于2 0 世纪8 0 年代末，其目标是从大量的数据中提取有用的信息和 知识的过程，早期主要研究从数据库中发现知识( k n o w l e d g ed i s c o v e r yi nd a t a b a s e ， k d d ) 。1 9 9 5 年第一届知识发现和数据挖掘国际会议在加拿大召开，会议上，隐私 保护的数据挖掘成为了一个专门的研究主题。此后，数据挖掘这一概念逐渐为人们所 接受。1 9 9 9 年r a k e s ha g r a w a l 在k d d 9 9 上作了一场精彩的主题演讲【l 】，将隐私保护 的数据挖掘作为未来的研究重点之一。进行数据挖掘固然需要先进的算法、技术及各 项硬件设施，但如果缺乏一定数量和质量的数据，数据挖掘就成为无源之水。 微数据是指与个体( 比如个人、公司、社团、政党或国家等) 相关的数据，这些 数据对数据分析和科学研究( 比如公共基金管理、疾病研究和市场趋势分析等) 都具 有重要的意义，因此，很多组织都在收集或发布大量的微数据，然而微数据的发布会 对个体的隐私构成一定威胁。尽管微数据在发布前已经将与个体相关的显示标识符删 掉或加密，但攻击者利用数据表中其他属性，通过与外表的链接，仍旧可以唯一地标 识出信息所属的个体。例如，s w c e n e y 在【2 】中指出，依据性别、生日、邮编等信息， 8 7 的美国公民可以被唯一的标识出来。美国最近的民意调查显示：7 0 以上的被访 者反对将医疗记录不受制约地应用于研究目的，7 8 的被访者认为计算机技术代表了 对个人隐私的威胁。时代周刊、英国广播电视和其他研究表明：至少有9 3 的被 访者认为公司在出售个人数据之前必须获得个人的允许。另一项调查显示，9 6 的被 访者认为私人信息不应该在没有被允许的情况下使用，超过2 0 的被访者亲身体验过 隐私被侵犯。 目前，微数据发布中隐私保护问题已成为信息安全领域重要且有挑战性的课题。 保护微数据的目标是：保证个体的隐私信息得到保护。保证这些数据对数据分析 者而言是可用的，即分析者从这些数据中获得的知识不比从原始数据表中获得的知识 少。目前微数据保护技术大体上可分为两类：扰动技术和非扰动技术，扰动技术是指 对数据进行失真处理，比如：微聚集技术、随机化技术、添加噪音技术和分级交换技 术等。非扰动技术指并不改变原始数据，只是隐匿信息或减少信息的具体程度，比如： l 绪论 样本化技术、泛化和隐匿技术等。 在众多的数据挖掘隐私保护模型中，舡匿名化( k - a n o n y m i z a t i o n ) 以其简单有效 而得到了广泛的关注和研究。近几年，很多学者将s d 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 ) 技术中的微聚集( m i c r o a g g r e g a t i o n ) 方法引入到数据表的肛匿名化上，微聚集技术 成为了隐私保护的热点技术之一。 1 2 国内外研究现状 随着网络信息技术的发展，人类大量信息被政府部门、商业机构等存储、发布， 这极大激发了各部门从海量数据中挖掘有用信息的需求。但事物往往具有两面性，当 数据挖掘用于公开分析大量的私人信息( 如购物习惯、犯罪记录、病史、信用记录等) 时，它在为人们提供强大知识发现功能的同时，也对个人隐私带来威胁。目前，解决 该问题的主要方法有：匿名保护，有的机构为了保护个人信息，常常对姓名、社会 保险代码等能清楚标识用户信息的显式标识符进行删除或加密，但攻击者往往通过发 布数据中的其他信息如种族、生日、性别和邮编等和从其他渠道获得的数据进行链接， 推演出隐私数据。在数据清理时对初始数据进行扭曲、扰乱、随机化后再挖掘，这 类方法尽管能保持结果的整体统计特性，但通常是以破坏数据的完整性和真实性为代 价p j 。基于密码学的隐私保护技术。有些数据挖掘算法采用密码学技术解决实际的 隐私问题。如安全两方或多方计算问题等，该方法需要过多的计算资源。数据表的 肛匿名化。 数据表的红匿名化( k - a n o n y m i z a t i o n ) 是数据发布时保护私有信息的一种重要方 法。缸匿名技术是1 9 9 8 年由s a m a r a t i 和s w e e n e y 提出【4 】，它要求发布的数据中存在 一定数量( 至少为七) 的在准标识符上不可区分的记录，使攻击者不能判别出隐私信 息所属的具体个体，从而保护了个人隐私。肛匿名通过参数七指定用户可承受的最大 信息泄露风险程度。缸匿名化在一定程度上保护了个人的隐私，但同时会降低数据的 可用性。故肛匿名化的研究工作主要集中在保护私有信息的同时提高数据的可用性。 由于肛匿名技术简单有效，近年来得到广泛关注。2 0 0 1 年，s a m a r a t i 采用泛化和 隐匿技术实现数据表的肛匿名化，并提出k - 最小匿名概念【5 】。2 0 0 2 年，s w e e n e y 研究 了抵制几种攻击的后匿名模型 6 】。同年，她提出了基于泛化和隐匿的m i n g e n 算法 7 1 。 2 0 0 6 年，m a c h a n a v a j j h a l a 等提出了厶多样性算法，它保证每个等价类中敏感信息足 够多样，以抵制同质推理攻击和背景知识攻击【8 】，其中，等价类是指匿名表中对于准 标识符不可区分的记录组。l iz u d e 在【8 】的基础上，提出了抵抗推演攻击的( 七，d 模型 一j ，该模型根据敏感信息的敏感程度，事先指定每个元组的匿名度和敏感信息的多样 2 1 绪论 度，根据每个元组的( 后，d 约束完成匿名化处理，达到抵抗推演攻击的目的。w o n g 等人提出了( 口，k ) 匿名模型【i o l ，要求每个等价类的敏感值的频率不大于口。x i a o x i a o k u i 等提出了基于个性化匿名的泛化方法【l ，该方法实现了满足个性需求的最小 泛化，减少了匿名处理的信息损失量。杨晓春等提出了实现多约束肛匿名的c l a s s f l y + 算法【1 2 】。2 0 0 7 ，l in i n g h u i 等人提出了3 种最优泛化模式【1 3 】，并在【1 4 中指出扛多样 性算法的不足，提出了t - c l o s e n e s s 框架，该方法要求每个等价类的敏感值的分布要接 近于其在原始数据表中的分布。 以上研究工作大多集中在采用泛化隐匿技术实现数据表的肛匿名化，但该方法 存在明显不足，主要表现在：( 1 ) 计算复杂性高，m e y e r s o n 1 5 】和a g g a r w a l 等【1 6 】证明， 采用泛化隐匿获得最优乜匿名是n p h a r d 问题。故如何将泛化和隐匿技术最优地组 合还处在探讨阶段。( 2 ) 属性值的泛化是否合理取决于其语义，如何确定属性的合理泛 化域目前还没有可依据的方法。( 3 ) 泛化隐匿技术较适用于分类型数据( 标称型和序 数型) ，对数值型数据，泛化往往会丢失较多的数值语义【l 刀。 。 为了解决泛化隐匿技术的不足，近来，很多学者将s d c ( s t a t i s t i c a ld i s c l o s u r e c o n t r 0 1 ) 技术中的微聚集( m i c r o a g g r e g a t i o n ) 方法引入到数据表的肛匿名化上，其 基本思想是：通过某种启发式方法将数据集划分为若干类，要求每个类至少包含k 个 元组，类内数据最大程度地相似，类间数据最大程度地不同，然后用类质心来代替类 内所有元组，从而实现数据集的肛匿名化。由于微聚集用类质心取代类内元组的值， 故类内同质性越大，信息的损失量越小。微聚集算法最初用来处理数值型数据【1 8 】，现 已扩展到处理分类型数据【1 9 , 2 0 。2 0 0 1 年，o g a n i a n 等证明了多变量数据的最优微聚集 是一个n p h a r d 问题【2 1j 。2 0 0 2 年，h a n s e n 等证明了单变量数据的最优微聚集算法可 在多项式时间内实现，其时间复杂度为o ( 舻刀) 2 2 1 。为降低多变量微聚集算法的时间 复杂性，d o m i n g o f e r r e r t l 引，l a s z l o t 2 3 1 ，s o l a n a s 2 4 1 等分别提出多种启发式算法。2 0 0 6 年，d o m i n g o f e r r e r 提出了满足( p ，七) 约束的微聚集算法【2 5 1 ，并应用于定位信息保护。 s o l a n a s 提出了基于遗传算法的多变量微聚集算法【2 6 】和可变大小的多变量v m d a v 算法【2 7 1 。2 0 0 7 年，d o m i n g o f e r r e r 提出了基于树的多项式时间的p a p p r o x 算法【2 引。 c h i n - c h e nc h a n g 提出了t f i 冲( t w of i x e dr e f e r e n c ep o i n t s ) 算法【2 引。该领域中j o s e p d o m i n g o f e r r e r 做出了很多重要的贡献。目前国内对微聚集算法的研究比较少，还未 见相关的报告和文献。 如今该领域已取得很多出色的成果，但还有一些关键性的问题尚未解决，主要表 现在以下几个方面： ( 1 ) 现有的微聚集算法均在有限的解空间中搜索最优解，得到的匿名表并非最 优。如何利用智能优化算法，搜索到全局最优解，得到具有较高数据可用性的匿名表， 3 l 绪论 具有非常重要的意义。 ( 2 ) 现有的微聚集算法主要面向数值型数据，对分类型数据的研究比较少，而且 基本上没有考虑混合型数据的处理。然而大多数的微数据都以混合数据的形式存在， 故研究混合型数据的肛匿名具有非常重要的现实意义。 ( 3 ) 随着微聚集算法的不断涌现，如何统一、科学地评估微聚集算法，对算法的 选择也具有一定的现实价值。 针对以上问题，本课题研究了全局搜索的微聚集算法，实现了面向混合型数据的 微聚集算法，并且构建了面向微聚集算法的评估模型。本课题的研究对完善微聚集技 术，加强私有数据保护，提高匿名数据可用性均具有重要的理论意义和现实价值。 1 3 本文主要的工作 本课题针对1 2 节提出的问题，主要完成以下方面的研究工作： ( 1 ) 提出了基于免疫克隆选择的微聚集算法( i c s m a ，i m m u n ec o l o n 甜s e l e c t i o n m i c r o a g g r e g a t i o na l g o r i t h m ) ，最大程度地降低了匿名数据的信息损失量。该算法采 用十进制编码，并引入调整算子，在抗体成熟的过程中通过删除不合理抗体达到加快 收敛速度的目的。 ( 2 ) 提出了一种面向混合型数据的微聚集算法，弥补了目前微聚集算法处理分类 型数据的缺陷。该算法中，分类型数据采用层次距离，数值型数据采用欧氏距离，并 将这两种距离的结合作为混合型数据的距离。将数值型数据的均值向量与分类型数据 的众值向量并在一起作为类质心，并用该类质心代替类中元组在准标识符上的值，以 实现肛匿名化。 ( 3 ) 在现有的微数据保护评估模型的基础上，构建了微聚集算法的评估模型 e m 4 a d o m ( e v a l u a t i o nm o d e lf o rk - a n o n y m i z e dd a t ao r i e n t e dt om i c r o a g g r e g a t i o n ) ， 该模型从数据的可用性、安全性、可用性和安全性的权衡三个方面综合评估微聚集算 法的性能。 1 4 本文的基本框架 本文的章节结构组织如下： l 绪论 介绍了微数据发布中隐私保护问题的发展状况及现有的解决方案。主要分析了数 据表匿名化的微聚集算法的基本原理与研究现状，总结了全篇的研究目标和各章内 容。 4 l 绪论 2 数据表肛匿名化的微聚集技术 介绍了微聚集算法的基本思想、相关技术和当前动态，并对现有的微聚集算法进 行了分类分析。 。 3 多变量微聚集的免疫克隆选择算法 迄今为止，通过微聚集实现的肛匿名已被证明是n p 的组合优化难题。现存在的 微聚集算法大都在一个有限的解空间中搜索问题解，故只能获得局部最优解。鉴于此， 本文提出了一种基于免疫克隆选择的多变量微聚集算法( i c s m 算法) ，该算法对标 准免疫克隆选择算法进行改进，引入了调整算子，在抗体进化的过程中通过删除不合 理抗体来加快算法收敛速度，使其在全局解空间中搜索到全局最优解。 4 面向混合型数据的微聚集算法 为了实现混合型数据的匿名化，本文提出了面向混合型数据的微聚集算法。该算 法在传统微聚集技术中的分类型数据的距离度量方法的基础上，引入层次距离，并将 层次距离与欧式距离的结合作为混合型数据的距离，同时将数值型数据的均值向量与 分类型数据的众值向量并在一起作为类质心代替类中元组在准标识符上的值，实现数 据表的肛匿名化。 5 面向微聚集技术的匿名数据的质量评估 本文提出面向微聚集算法的评估模型e m 4 a d o m ( e v a l u a t i o nm o d e lf o r k - a n o n y m i z e dd a t ao r i e n t e dt om i c r o a g g r e g a t i o n ) ，该模型采用同质性差异法和统计 量差异法度量连续型数据的信息损失量，利用直接比较法和信息熵比较法度量分类型 数据的信息损失量；利用基于距离的记录链接法和区间泄密法度量数据的安全性，并 给出了数据可用性和安全性的综合评估模型。实验结果表明e m 4 a d o m 可从数据的 可用性、安全性、可用性和安全性的权衡三个方面综合评估微聚集算法的性能。 6 总结及展望 总结全文，对提出的算法、模型的不足之处以及未来的工作进行概括，并对一下 步的研究和应用做出展望 1 5 本章小结 本章介绍了本课题的研究背景及意义，讨论了数据表肛匿名化的微聚集技术在国 内外的研究现状，最后对本文主要的工作和基本框架进行了介绍。 5 2 数据表肛匿名化的微聚集技术 2 1 微聚集算法相关技术 2 1 1 微聚集算法的基本概念 泛化隐匿是实现数据表肛匿名化的典型技术，然而该技术在处理数值型数据时， 将数值型数据等同于分类型数据，这种做法会丢失数据的数值语义。例如，连续区间 【a ，b 中的任一值被上【咖】取代，此时原始值在区间rb 中的位置信息也随之消失。人 们通过三【柚】无法推断出原始值是处在【a ，b 】的下半部分还是上半部分，而且利用区间 数据三鼬1 进行数据分析也不方便。另外，泛化数值型数据时，需要定义泛化层次和区 间，效率低。 泛化的另一严重缺点是当准标识符的属性数量剧增时，任何泛化都必将丢失大量 的信息，即所谓的“维度灾难”【3 0 1 ，即在高维空间中，每个泛化值都具有极宽的区间， 这种情况下产生的公开表完全没有研究的价值。 近年来，微聚集技术被引入到数据表的舡匿名化上，弥补了泛化隐匿技术的不 足。其基本思想是：通过某种启发式方法将数据集划分为若干类，要求每个类至少包 含k 个元组，类内数据最大程度地相似，类间数据最大程度地不同，然后用类质心来 代替类内所有元组，从而实现数据集的肛匿名化。 数据表中的属性按其所起的作用可分为四类：( 1 ) 显示标识符，指能清楚标识个 体身份的属性，如用户身份证号码、社会保险号、姓名等。为了保护个人私有信息， 常常在数据发布前将这些属性删除或加密。( 2 ) 准标识符a i ( q u a s i i d e m i f i e r ) ，同时存 在于隐私表与外表中，可以利用链接来标识个体信息的一组属性称为准标识符f 4 1 ，如 属性组 r a c e ，b i r t h ，g e n d e r ，z i p 。准标识符不同于显示标识符，它的定义依赖于攻击 者所拥有的外表信息，故表中的任何属性都有可能成为准标识符。( 3 ) 敏感属性，该 类属性包含了个体的敏感信息，如薪水、宗教、政治派别、身体状况等。( 4 ) 非敏感 属性，该类属性包含了个体的非敏感信息，对原始数据进行保护时，该类属性不能被 忽略，因为该类属性的任意组合都有可能是准标识符。下面给出本章用到的几个术语 的定义【l7 1 。 6 2 数据表“匿名化的微聚集技术 定义2 1 ( k - 匿名) 给定数据表t ( a l ，a z ，a ) ，缈是丁的准标识符，鲫为z 在 讲上的投影( 可重复) ，当且仅当在鲫中出现的每组值至少在丌鲫中出现k 次时， 则称丁满足舡匿名。 定义2 2 ( 肛划分) 给定数据集t ( a i ，a 2 ，彳0 ，缈是丁的准标识符，弘含p 个属性，数据集中的元组x = ( x l ，劫可视为p 维空间中的p 一维向量点。将表丁基 于纠划分为g 个类，n i 为第f 类的元组数，要求对于v i ，玎，k ，且刀= ：l ，z r ， 则称该划分为数据集r 基于舛的髓划分。 定义2 3 ( 聚集) 给定数据集t ( a 1 ，a 2 ，彳刀) ，讲是r 的准标识符，基于妒的一 个缸划分将丁划分为g 个类，设c l 为第f 类的类质心，对于所有f ( 卢1 曲，用q 取代 第f 类中所有元素的操作称为聚集。 定义2 4 ( 等价类的最小基约束) 给定一数据集和约束参数k ，数据集经过划分后， 生成若干个等价类，要求每个等价类的元组的个数不能少于k 个，称该约束为等价类 的最小基约束。 ， 最优微聚集基于最优珏划分，它要求划分后的类内同质性最大。文献【1 8 】证明， 最优舡划分的等价类的大小应在阮2 k - 1 之间。 2 1 2b 匿名化微聚集算法的基本步骤 实现肛匿名的微聚集算法分为两个步骤：第一步，对数据表丁进行缸划分，生成 由g 个类组成的数据表；第二步，对类进行聚集操作，得到由g 个等价类组成的新数 据表z ，。例如：原始数据表r ，见表2 1 ，显式标识符为 c o m p a n y ，准标识符 泸 s u r f a c e ，n o e m p ) ，敏感属性为 t u r n o v e r , n e t p r o f i ，) 。舡匿名化的过程如下：( 1 ) 删 除显式标识符c o m p a n y ，数据被初步匿名化。( 2 ) 将数据表丁的剑属性值标准化， 再基于凹进行如划分( 庐3 ) 。( 3 ) 将标准化的值恢复为原范围数值，对如划分的数据 表进行聚集操作( 用平均值作为类质心) ，得到三个等价类，见表2 2 。 数据按其属性的性质可分为三种类型：( 1 ) 连续型：也称数值型，指可进行算术 运算且直接反映实际的物理或几何意义的属性，如年龄、收入等。( 2 ) 序数型：该类 属性反映特征的等级，具有一定次序关系，如职称，比赛名次等。( 3 ) 标称型：该类 属性反映某种性质，比如颜色，这类属性值既无数量含义，也无次序关系。后两类属 性属于分类型属性。 不同类型的数据，类内同质性以及聚类类质心的定义不同。下面分别说明各种类 型数据的距离、类质心以及信息损失量的度量方法。 7 2 数据表“匿名化的微聚集技术 表2 1 原始数据表， 表2 2 表，微聚集后的匿名表p ，如3 2 1 3 连续型数据的距离度量方法 连续型数据，常用的距离度量方法是欧氏距离，定义为式( 2 1 ) 。 d ( x ，y ) ；( 三。( 彳，一r ) 2 ) ； 其中，x ，k 表示向量x ，y 第i 维的属性值。 ( 2 1 ) 设g ，为缸划分产生的任一等价类，则g 朐类内同质性测度g s e 定义为式( 2 2 ) 。 g s e ( g ，) = ：d ( x “，霸其中豇= ：，x “ ( 2 2 ) 式中n i 表示类g l 中的元组个数，_ k ，x 口表示g f 类中的第，条元组，x ，表示q 类 8 2 数据表b 匿名化的微聚集技术 的类质心，g s e 越小，类内数据的同质性越强。 所有类的同质性测度s s e 定义为式( 2 3 ) 。 数据表的整体同质性测度鼹腚义为式( 2 4 ) 。 s s t ：。工。d ( x 玎，i ) 其中i = 2 。x ， ( 2 4 ) 其中叉表示为整个数据表丁的平均向量，即整个数据集的中心。 连续型数据的类质心计算比较简单，一般可用第f 类元组的均值向量x ，来定义该 类的类质心。 对给定的数据集而言，嬲碉定不变，但不同的肛划分，会导致不同的s s e ，类 内同质性越大，s s e 会越小，信息损失量也会越小，因此连续型的数据信息损失量儿 可用式( 2 5 ) 度量。 i l = s s e s s t ( 2 5 ) 其中尼越小，匿名表的数据可用性越强。第5 章的5 3 节中讨论了信息损失量 的其它度量方法。 2 1 。4 分类型数据的距离度量方法 分类型数据主要包括：序数型和标称型。d o m i n g o f e r r e r 分别给出了它们距离度 量方法【1 9 】。 对于序数型属性4 的不同值a ，b 6 ) 之间的距离定义为式( 2 6 ) 。 d ( a ，6 ) 爿 歹la 歹 以l id ( 4 ) l其中d ( 4 ) 为么l 的取值j 或 ( 2 6 ) 由式( 2 6 ) n - - 知，d ( a ，6 ) 为属性4 在【口，b 】之间的值的个数与属性4 所有值个数的比 值。 d o m i n g o f e r r e r 采用中位数或凸中位数定义序数型数据的类质心，计算方法如下： 设序数型属性4 取值集c = 弛，乞，c o ，q c 2 ，则对应的元素集合为 1 ，2 ，2 ，2 ，3 ，4 ，5 ，6 ，7 ) ，故s 的凸中位数为3 。 凸中位数法比中位数法较多地保留了序数型数据的语义。 对于标称型属性，d o m i n g o f e r r e r 1 9 】给出了简单的距离定义，令x ，y 为具有p 个 标称型属性的元组，则二者之间的距离定义为式( 2 8 ) 。 d ( x y ) = 私y ，) ，其中m 沪 ( ( 彬x j = y y j ，； ( 2 8 ) 标称型数据往往有一定的语义层次关系，式( 2 8 ) 没有考虑到这一点，因此采用式 ( 2 8 ) 来度量标称型数据的距离存在不合理的情况，如邮政编码属性， 1 5 1 4 0 0 ) 与 1 5 1 4 1 1 ) 的距离比 1 5 1 4 0 0 与 3 2 1 0 0 4 ) 的距离更近，而按式( 2 8 ) 计算，它们是等距的。 可借鉴文献 3 1 】定义的层次距离来度量标称量的距离，以改进肛划分的质量。 标称型数据类质心的选取是基于频率的，其属性值可确定为该等价类中各属性出 现频率最高的值，即各属性值的众数。 分类型数据匿名化的信息损失量的度量方法将在第5 章中讨论。 2 1 5 混合型数据的距离度量方法 混合型数据指数据集中既有连续型属性，又有分类型属性。目前面向混合型数据 的微聚集算法研究比较少。可借鉴文献 3 2 ，3 3 】中混合型数据的距离度量方法来实现混 合型数据的微聚集算法。 2 2 微聚集算法的分类 2 2 1 从肛划分所依据的属性个数的角度分类 从舡划分所依据的属性个数的角度，微聚集算法可分为单变量微聚集算法和多变 量微聚集算法两大类。单变量微聚集算法是指以准标识符的单个属性为依据进行缸 划分，方法有单轴排序法j 、遗传算法【l8 】等。多变量微聚集算法以准标识符的多个 属性为依据进行缸划分，尽管多变量数据集的最优肛划分是n p 难题，但采用启发式 方法 3 , 1 7 2 3 , 2 8 j ，也可获得高效的近似解。文献【3 】将w a r d 算法改进，提出k - w a r d 算法 来实现肛划分。并在k - w a r d 算法基础上提出了m d ( m a x i m u md i s t a n c e ) 算法，用 距离最远的两个向量作为初始类的中心，进行聚类，获得了较好的划分效果，但其初 始中心选择的时间复杂性较高，m d 算法的时间复杂度为o ( n 3 哟。：- a r g u s l 3 5 】软件 包中的距中心点最大距离m d a v ( m a x i m u md i s t a n c et oa v e r a g ev e c t o r ) 算法是m d 算法的改进，将时间复杂性降为o ( n 2 ) 。文献 1 7 】在m d a v 算法的基础上，定义了分 1 0 2 数据表“匿名化的微聚集技术 类型数据的距离度量方法，提出了适用于连续型和分类型两种属性的m d a v g e n e d e 算法，时间复杂性也为o ( n 2 ) 。 排序是实现微聚集较简单的方法，最初是针对单变量微聚集提出的，后扩展到多 变量微聚集。下面说明基于排序思想的微聚集算法【3 6 1 。 ( 1 ) 单轴排序算法 单轴排序主要思想：先选择数据表丁的某属性彳，根据属性4 取值的大小将表丁 中的记录进行排序，然后依排序顺序进行屉划分，最后对肛划分的结果进行聚集操作。 该算法可在多项式时间内实现。 单轴排序算法在处理多变量数据表时，排序变量选择的不同往往导致不同的排序 结果，最后肛划分的结果也就不一样，因此排序变量的选择是一个关键的问题。 ( 2 ) 第一主成分排序算法 第一主成分排序法解决了单轴排序算法中排序变量的选择问题。主成分技术最早 由k a r lp e a r s o n 提出 3 7 】，该技术能对给定的p 个相关变量五，五，以，生成实测变量 的线性不相关集合互，