（计算机软件与理论专业论文）隐私保护数据挖掘技术研究.pdf

摘要 曼曼曼! 曼! ! ! ! 曼曼曼曼! 曼曼鼍! ! ! 曼曼曼苎! ! ! 鼍i _ i i = i ! 蔓曼! 曼! ! ! 曼苎曼! 曼曼! ! 曼曼! 曼! ! ! 曼! 曼 摘要 随着信息技术的高速发展，数据库应用的规模、范围和深度不断扩大，产 生了“数据丰富而信息贫乏 现象。为了解决这一问题，人们提出了数据挖掘 技术。经过十几年的发展，数据挖掘成为数据库研究、开发和应用最活跃的分 支之一并在各领域都取得了可喜的成果。但与此同时，数据挖掘也面临着许多 问题和挑战。其中，隐私与信息安全问题尤其得到关注。误用、滥用数据挖掘 可能导致用户数据特别是敏感信息的泄漏，越来越多的人们对此表示担忧，甚 至拒绝提供真实的数据。如何在不暴露用户隐私的前提下进行数据挖掘，一直 是人们感兴趣的课题。问题的解决对实现安全、公平的数据挖掘有着重要的意 义。 为了解决这一矛盾，人们开始关注与研究数据挖掘中的隐私保护问题，到 目前为止己取得了一定成果，并提出了许多新的算法和思路，当然也伴随着不 少的争论。虽然已过了十多年，但仍属于正在兴起的研究领域。 本课题正是面向这一领域，重点研究了集中式数据的隐私保护数据挖掘问 题，主要集中于隐私保护数据挖掘算法的研究。 首先，在传统噪音算法的基础上，提出了独立噪音思想，并设计出独立噪 音算法。该算法通过向原数据叠加噪音来保护原始数据不被泄漏，噪音大小依 据元组在数据分布中的位置独立选择；所使用的噪音对数据分布不造成严重影 响，使得后期挖掘工作可以在干扰后的数据上直接进行。实验证明，该算法可 以在隐私保护程度与算法精度上都取得较好的结果。 接着，将概率转移算法成功的应用于文本挖掘，并设计出分割变换算法。 该算法先通过词条切分从原文本中分割出文本的特征词，再仿照概率转移算法 对特征词进行变换，从而保护原文本。在挖掘工作中可以通过重建特征词的原 始计数来完成对文本的关联规则挖掘。其中主要解决了在大量特征词条件下的 转移概率确定和计数重建问题。实验证明，该算法可以在保护隐私与挖掘正确 结果之问能够取得较好的平衡。 最后，针对实际应用的特点，设计并实现了的隐私保护数据挖掘系统。因 为实际应用中通常要根据需求设计专用的数据挖掘算法与隐私保护算法，所以 系统除了包含一些典型算法外，也支持从外部添加新的算法。 关键词数据挖掘；隐私保护；独立噪音；数据变换 a b s t r a c t a bs t r a c t w i t ht h er a p i dd e v e l o p m e n to fi n f o r m a t i o nt e c h n o l o g y ，t h eu s a g es c o p ea n d d e p t ho fd a t a b a s ee x p a n d i n gc o n s t a n t l y , a n dl e a d i n ga ”d a t ar i c ha n di n f o r m a t i o n p o o r ”p h e n o m e n o n i no r d e rt o s o l v et h i sp r o b l e m ，d a t am i n i n gt e c h n o l o g i e sw a s r a i s e d a f t e rm o r et h a n10y e a r s ，d a t am i n i n gb e c o m eo n eo ft h em o s ta c t i v e b r a n c h e si nd a t a b l a s e r e s e a r c h ，d e v e l o p m e n ta n da p p l i c a t i o n ，a n d h a v em a d e g r a t i f y i n ga c h i e v e m e n t s b u t a tt h es a m et i m e ，d a t am i n i n gi sa l s of a c e dw i t hm a n y c h a l l e n g e sa n dp r o b l e m s t h ep r i v a c ya n di n f o r m a t i o ns e c u r i t ya r ec o n c e r n e da b o u t i np a r t i c u l a r m i s u s i n ga n da b u s i n go fd a t am i n i n gt e c h n o l o g i e sm i g h tl e a dt ot h e l e a k a g eo fu s e rd a t aa n ds e n s i t i v ei n f o r m a t i o n 。m o r ea n dm o r ep e o p l ee x p r e s s e d c o n c e r na n de v e nr e f u s e dt op r o v i d er e a ld a t a h o wt op e r f o r md a t am i n i n gw i t h o u t t h ee x p o s i n go fu s e rp r i v a c yh a sb e e nat o p i co fi n t e r e s tt op e o p l e t h es e t t l e m e n to f t h ei s s u eh a si m p o r t a n ts i g n i f i c a n c et ot h ea c h i e v e m e n to fas e c u r i t ya n df a i rd a t a m i n i n g i no r d e rt or e s o l v et h i sc o n t r a d i c t i o n ，p e o p l es t a r t e dt op a ya t t e n t i o nt ot h e r e s e a r c hi nd a t am i n i n ga n dp r i v a c yp r o t e c t i o ni s s l l e s ，s of a rh a sa c h i e v e dc e r t a i n r e s u l t s ，a n dp u tf o r w a r dm a n yn e w i d e a sa n da l g o r i t h m s ，o fc o u r s e ，a c c o m p a n i e db y al o to f c o n t r o v e r s y i ti sp r e c i s e l yf o rt h i ss u b j e c ti nt h i sa r e a ，f o c u s i n go nac e n t r a l i z e dd a t ap r i v a c y p r e s e r v i n gd a t am i n i n g ，m a i n l yi nt h er e s e a r c ho fp r i v a c yp r e s e r v i n gd a t am i n i n g a l g o r i t h m s f i r s t ，b a s eo nt h et r a d i t i o n a lm e t h o do fa d d i n gn o i s e ，i n d e p e n d e n tn o i s ei d e ai s a p p r o a c h e d ，a n da ni n d e p e n d e n tn o i s ea l g o r i t h mi sd e s i g n e d 。t h i sa l g o r i t h mp r o t e c t s o r i g i n a ld a t ab ya d d i n gn o i s e s ，t h es i z e o fn o i s ei sc h o s e ni n d e p e n d e n t l yb yt h e p o s i t i o no fat u p l e e x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mc a nh a v eg o o dr e s u l t so n b o t ht h ep r i v a c yl e v e la n dt h em i n i n ga c c u r a c y t h e n ，t h ea t t e m p t i n go fu s i n gp r o b a b i l i t ya l g o r i t h mi nt e x tm i n i n gi s h e l d s u c c e s s f u l l y , a n das e p a r a t ea n de x c h a n g ea l g o r i t h mi sd e s i g n e d t h i sa l g o r i t h m s e p a r a t e st h ek e y w o r d sf r o mt h et e x ta n de x c h a n g e s t h e ms oa st om a k et h ep r i v a c y p r e s e r v e d a s s o c i a t i o nr u l e sm i n i n gc a nb ec o m p l e t e db yr e b u i l d i n g t h eo r i g i n a l k e y w o r d sc o u n t s f i n a l l y , ap r i v a c yp r e s e r v i n gd a t am i n i n gs y s t e mi sd e s i g n e da n da c h i e v e d i n t h ep r a c t i c a la p p l i c a t i o n ，s p e c i f i ca l g o r i t h m ss h o u l db ed e s i g n e da c c o r d i n gt ot h e r e q u i r e m e n t s s ot h es y s t e ms u p p o r t sa d d i n gn e wa l g o r i t h m sf r o mo u t s i d e k e y w o r d sd a t am i n i n g ；p r i v a c yp r e s e r v i n g ；i n d e p e n d e n tn o i s e ；d a t ae x c h a n g e i i i 独创性声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究成 果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经 发表或撰写过的研究成果，也不包含为获得北京工业大学或其它教育机构的学位或 证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 签名：王手元日期：脚：舌2 关于论文使用授权的说明 本人完全了解北京工业大学有关保留、使用学位论文的规定，即：学校有权保 留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内 容，可以采用影印、缩印或其他复制手段保存论文。 ( 保密的论文在解密后应遵：r 此舰定) 签名：王平元导帅签名： 同期：塑：竺 第l 章绪论 曼! 曼蔓! ! 曼曼皇! i 一 i i 。 i 曼曼曼! 曼皇曼! 曼曼曼 i i 研究背景 第1 章绪论 我们处在一个信息爆炸的大时代，计算机处理能力、存储技术以及互联网 络的发展又极大地提高了信息的数字化处理程度，据估计每隔二十个月，信息 量就会增加一倍。快速增长的数据背后隐藏着许多知识，人们希望通过对积 累的数据进行更高层次的分析，找出数据内部一些潜在的关系和规则，将数据 变为真正的财富。如银行的信用卡中心期望能够从大量的交易数据中找出优质 客户的行为特征和消费模式，以帮助寻找潜在客户、刺激客户消费并创造更多 的交叉销售的机会；银行的信贷管理部门，希望通过分析信贷历史记录，来帮 助设计贷款产品、指导市场营销和贷款的发放，以降低不良贷款率和银行风险。 这样的需求数不胜数，涵盖了社会的方方面面。 面对上述挑战，广大工程技术人员提出了数据挖掘技术来解决上述问题。 数据挖掘的发展是一个逐渐演变的过程。电子数据处理的初期，机器学习 成为人们关心的焦点，其过程是将一些己知的并已被成功解决的问题作为范例 输入计算机，机器通过学习这些范例总结并生成相应的规则，这些规则具有通 用性，使用它们可以解决某一类的问题。之后，随着神经网络技术的形成和发 展，人们的注意力转向知识工程，不同于机器学习那样给计算机输入范例，该 方法要求直接给计算机输入已被代码化的规则，计算机通过使用这些规则来解 决某些问题。专家系统就是这种方法所得剑的成果，但它有投资大、效果不甚 理想等不足。二十世纪八十年代人们又在新的神经网络理沦的指导下，重新回 到机器学习的方法上，并将其成果应用于处理大型商业数据库。二十世纪八十 年代末，人们普遍使用数据库中的知识发现，简称k d d ( k n o w l e d g ed i s c o v e ri n d a t a b a s e ) ，来描述整个数勃i 发掘的过程，包括最，丌始的制定业务目标到最终的 结果分析，而用数据挖掘( d a t am i n i n g ) 来描述使膈挖掘算法进行数据挖掘的子 过程。最近人们逐渐发现数据挖掘中宵诈：多：】：作可以山统计方法来完成，并认 为最好的策略是将统计方法与数据挖掘i 有机的结合起来比1 。 j i w e ih a n 在文献 3 中认为：从广义上理解，数据、信息也是知识的表现 形式，但是更把概念、规则、模式、规律和约束等看作知识，数据挖掘是从存 放在数据库、数据仓库或其他信息库中的大量数据中提取或挖掘有趣知识的过 程，是数据库中知识发现的一个重要过程。 任何事情都有其两面性，数据挖掘领域也不例外。在挖掘数据产生财富的 同时，随之产生的就是隐私泄露的问题。 北京i ：业大学工学硕十学位论文 “隐私权”最早在1 8 9 0 年1 2 月美国人沃伦和布兰代斯所写的隐私权 中正式定义它被界定为“生活的权利”和“不受干扰的权利”。两位作者认为， 隐私权本质上是一种个人对其自身事务是否公开给他人的权力，保护个人的隐 私权就是保障个人的“思想、情绪及感受”不受他人打扰的权力，保护自己人 格不受侵犯的权力。到2 0 世纪6 0 年代，隐私权的观念逐渐为美国法律界所熟 悉，但隐私权的内容为何，却始终未见有明确的界定。1 9 6 0 年，w i l l i a ml p o r s s e r 教授在加州法律评论上发表了隐私一文，试图就隐私权的内 容做一归纳。根据他的整理，法律上的隐私权侵害应包含四种侵权行为，这四 种类型的侵害包括：对他人私生活隐私权的侵害；公开他人的姓名、肖像或揭 发其他不愿为他人所知悉的私人信息；使他人处于人为误解情况；基于商业上 的目的，侵犯他人人格h 1 。 由于计算机处理能力、存储技术以及互联网络的发展，使得电子化数据急 剧增长，这样传统上对隐私权保障的思考，就必须转向以“数据保护 为重心 的思路上，于是就出现了“信息隐私权 的概念，以应对信息时代隐私权所受 到的冲击。如由于工作、生活、学习的关系，人们要在政府、学校、银行、医 院、警察、司法机关、工作单位等地方留下个人资料和信息，这些资料都被存 入了计算机，彼此传递运用，只要键入身份证号码后，就可将一个人所有资料 一览无遗，而这些都与人格、尊严、隐私有着密切的关系。国外已经发生了多 起由于个人信息泄密，而造成个人账号被冒用的例子，以及由于个人电话号码 被一些机构出卖，而遭到一些中介、盈利机构频频骚扰的例子，所以说信息时 代的隐私权保护要比传统的隐私权保护重要的多。 在数据挖掘领域，隐私被划分为两类。第一类隐私是原始数据本身具有的。 由于传统的数据挖掘技术是基于未加密过的原始数据来进行的，也就是说必须 将包含个人或企业隐私的原始数据交给数据挖掘者才能挖掘出有用的知识，如 联系电话、银行账号、财产状况、信用等级等，这些信息一旦泄露的话，极可 能对个人的生活产生不良影响。第二类隐私是原始数据所隐含的知识，如某公 司优质客户的行为特征等规则，这些知识如果被别有用心的人非法获得，将会 严重影响企业的核心竞争力。 在这种情况下，人们会不会由于担心隐私被泄露而拒绝提供任何信息资料 呢? 1 9 9 9 年的一次网上调查瞄1 结果表明：在响应者中，1 7 的网上用户是正统的 隐私保护主义者，他们即使在采取保护隐私的措施下也不愿意提供自己的真实 信息；5 6 的网上用户是实用主义者，在采取保护隐私的措施下，他们提供真实 信息的可能性大大提高：其余2 7 的网上用户虽然也考虑隐私，。但还是愿意提供 自己的真实信息。 该调查说明，人们并没有因噎废食，在数据挖掘能够提供的益处面前，只 2 第l 章绪论 曼! ! 曼! 曼詈曼! ! 曼! 曼! 曼! 皇曼i：i i i i i 皇! 皇! 皂曼曼 要数据采集者采取措施保证个人的隐私，大部份人还是愿意参与调查并提供自 己的隐私数据。同时也说明保护隐私程度的高低将直接关系到是否能够收集到 足够真实的信息，从而关系到挖掘出来的信息是否可靠有用。 1 2 研究现状 在1 9 9 5 年召开的第一届k d d 上，隐私保护数据挖掘就成为了一个专门的研 究主题。第二年，c l i f t o n 和m a r k s 发表了第一篇专门探讨数据挖掘中的安全 与隐私问题的论文哺1 ，文中还简要分析了解决问题的几种可行思路。1 9 9 9 年 r a k e s ha g r a w a l 在k d d 9 9 上作了一场精彩的主题演讲盯1 ，将隐私保护数据挖掘 作为未来的研究重点之一。自此以后，隐私保护数据挖掘越来越得到人们的重 视，迅速成为近年来数据挖掘领域研究的热点之一。 在2 0 0 0 年，a g a r w a l 等人提出了最早的隐私保护数据挖掘算法阳一1 。之后 更多的研究人员加入了这个行列，各种算法也相继被设计出来。典型的算法包 括：d s a 算法n0 。、m a s k 算法“h 坦1 、随机响应方法n3 。、几何变换算法n 、p p s v m 算法n 乳埔1 等 国内大约在2 0 0 0 年开始了数据挖掘的研究，对隐私保护数据挖掘的研究则 刚刚起步。主要的工作是在研究已有算法的基础上，进行改进和创新。有代表 性的成果包括：o s a 算法n7 j 、近似反频集挖掘算法n8 】、p p r h 算法n 引、概率转移 算法2 0 3 等。 目前，隐私保护的数据挖掘领域罩有以下几个研究热点： ( 1 ) 特定数据挖掘算法技术细节的研究 如果知道某个算法是如何定义它的兴趣度量的，那么可以让数据库系统向 用户提供的数据中不包括用户“感兴趣”的规则，或是提供一些经过处理的数 据，从这些数据中只能挖掘出伪规则，真正的规则却被隐藏起来。因此，如果 知道了这些算法是如何生成规则、兴趣度怎样定义、对低兴趣度项目集如何剪 枝，我们就能采取有效的措施来削弱数据挖掘工具破坏数据库系统安全的能力。 最理想的是能够找到各种数据挖掘算法的共同特性，这样就能提出一些通用的 方法来避免由这些挖掘算法造成安全威胁。 ( 2 ) 不同数据挖掘算法的研究 找到它们的特点，尤其是每个算法的适用领域和弱点，就能判断数据库系 统向外提供的数据集是否容易受到数据挖掘攻击。例如，了解了算法的计算复 杂性等特点，我们就能建立特别的数据库系统，其向外提供的数据难以被数据 挖掘算法所处理，即对这些数据的挖掘难以得到理想的结果，挖掘得到的结果 也不会影响数据库中敏感数据的安全。 北京丁业人学- 丁学硕十学位论文 ( 3 ) 利用数据挖掘工具发现数据库中潜在的推理攻击可能 一个数据库只要它同时包含了公开数据和只向部分具有特定安全级别用户 提供的敏感信息，就有必要采用此方法。因为，完全有可能存在一些规则，它 们以数据库向外提供的公开数据作为逻辑推理的前件，经过推理运算就能得到 一些敏感信息。而且，这可能会导致更多敏感信息泄漏。 ( 4 ) 利用己有的密码安全技术，开发针对特殊情形的安全多方计算协议 安全多方计算技术适用于多方合作的情况。因为在现实中，合作的各方都 是不完全可信的，而且也不存在完全可信的第三方。所以需要找到一些方法， 确保各单位原始数据内容在挖掘过程中不被泄露，并在挖掘完成后共同得到整 体数据的挖掘结果。 ( 5 ) 基于隐私保护的数据挖掘算法的研究 研究的目标是：提供给数据挖掘算法己经被加了噪音的样本数据、甚至连 原始数据集的分布规律都改变了，在不能重新恢复原始数据值的情况下，依旧 能进行所需的数据挖掘。 1 3 主要研究内容 本课题集中在隐私保护数据挖掘算法的研究，主要内容如下： ( 1 ) 研究了已有的隐私保护数据挖掘算法，了解它们的应用范围、核心技 术和主要优缺点。 ( 2 ) 设计了应用于隐私保护聚类挖掘的独立噪音算法。通过对聚类挖掘算 法的特点分析，对传统的噪音算法进行改进，提出了独立噪音思想，并应用这 一概念设计了独立噪音算法。 ( 3 ) 将隐私保护数据挖掘算法成功的应用于文本挖掘。借用文本挖掘中的 词条切分手段，以概率转移算法为基础，设计了分割变换算法。主要解决了在 大量特征同条件下的转移概率确定和计数重建问题。 ( 4 ) 设计并实现了隐私保护数据挖掘系统。为了应对多样的实际应用，系 统支持从外部添加新的算法。 1 4 本文结构 本论文的组织结构如下所示： 第一章概述论文的研究背景、研究意义、研究现状和主要研究内容。 第二章介绍隐私保护数据挖掘算法的分类及设计思路。 第三章介绍独立噪音算法。首先分析了聚类算法和现有隐私保护聚类挖掘 算法的特点，而后提出了独立噪音思想，最后给出了独立噪音算法的实现和试 4 第1 币绪论 验分析。 第四章介绍分组变换算法。首先分析了文本挖掘和概率转移算法的特点， 而后讨论了将概率转移算法应用于文本挖掘时所涉及到的问题，最后给出了分 组变换算法的实现和试验分析。 第五章介绍隐私保护数据挖掘系统的设计过程。 第2 章隐私保护数据挖掘剪法综述 第2 章隐私保护数据挖掘算法综述 2 1 1 隐私保护数据挖掘算法分类 v a s s i l i o ss v e r y k i o s 在文献 2 1 中，从数据分布方式、数据修改方法、 数据挖掘算法、隐私保护的对象和隐私保护技术五个角度对现有的一些隐私保 护数据挖掘算法作了一个归纳。 ( 1 ) 数据分布方式：有的是研究集中式数据，有的是研究分布式数据。分 布式又分为水平分布和垂直分布两种，水平分布指数据按元组分布在不同的站 点，垂直分布指数据按字段分布在不同的站点。 ( 2 ) 数据修改方法： a ) 按不可倒推的方法修改数据为一个新值： b ) 用无意义的常数值来替代存在的值，以保护敏感数据和规则； c ) 合并或抽象详细数据为更高层次的数据； d ) 对数据进行抽样： ( 3 ) 数据挖掘算法：适用于不同知识的挖掘算法，如分类、关联规则、聚 类等； ( 4 ) 隐私保护的对象：即隐藏原始数据或其隐含的规则。规则比原始数据 的层次要高，通过保护敏感规则，同样可以保护熏要的原始数据； ( 5 ) 隐私保护技术：即修改数掘所采用的技术。 a ) 启发式技术：通过仅仅修改特定值、而非全部值来减少挖掘效果的 失真； b ) 密码技术：采用密码学技术来进行数据加密，如多方安全计算： c ) 重建技术：从变换后的数据巾恢复原有数据的分布： 既然各种方法都有其特点，那么如何衡量它们的优越性昵? v a s s i l l o s s v e r y k i o s 同时也提出了对各类隐私保护算法的评估标准： ( 1 ) 性能：计算开销，以及分砸j 式环境下的通讯开销； ( 2 ) 算法精度：与非隐私保护的同类算法相比，其判断精度、丢失比率和 误生成比率： ( 3 ) 隐私保护程度：防止原始数据或其隐含的知识被推导出的程度； ( 4 ) 通用程度：适应各种数据挖掘技术的程度： 7 北京t 、i k 火学t 学硕i j 学位论文 2 2 分布式数据 对分布式数据进行隐私保护，大多数算法采用的是基于加密的技术，安全 多方计算( s m c ) 是最为常用的一个协议。安全多方计算是在一个互不信任的多用 户网络中，各用户能够通过网络来协同完成可靠的计算任务，同时又能保持各 自数据的安全性乜2 l 。在基于加密技术的隐私保护方面，对于隐私的定义，p i n k a s 在文献 2 3 中这样给出：限制通过分布式计算所能获得的满足其要求的所泄漏 的信息称之为隐私。p i n k a s 对安全多方计算在基于加密技术的隐私保护方面的 应用作了一定的探讨，认为安全两方计算的构建要易于安全多方计算，同时影 响协议的一个重要方面是用于计算评价函数的最佳组合电路的规模，而影响计 算的因素则来自健忘传输协议以及协议的改进程度。 2 3 集中式数据 针对集中式的数据挖掘通过对大量数据的统计计算找出趋势，而不一定要 知道百分之百真实的数据。r a g r a w a l 在文献 8 中提出了一种基于重建技术的 算法。该算法针对数值型数据，通过添加随机偏移量对原数据进行随机化扰乱， 然后使用贝叶斯公式，重建原数据的概率分布，并根据重建的原始分布来构造 决策树。同时，r a g r a w a l 引入了一些量化方法来检验通过上述方法处理后的 数据隐私泄漏状况，从置信度以及预测的准确程度上对算法进行了检验。具体 地讲，如果可以用c 的置信度预测出某个数值x 处在某个区间内，那么这段区 间的宽度就决定了带有c 置信程度的隐私度量。但是由于贝叶斯定理的成立本 身需要一个很强的独立性假设前提，而此假设在实际情况中经常是不成立的， 因而其分类准确性就会下降。 a e v f i m i e v s k i 等在文献 2 4 中提出了另一个基于重建技术的隐私保护算 法，该算法使用了一种称为统一随机化的方法( u n i f o r mr a n d o m i z a t i o n ) 。所谓 的统一随机化是指在将一个交易发送给服务器前，客户端取走每一个项时，将 之以概率p 替换为原先在交易中没有的新项，这个过程叫做统一随机化。 s h a r i qj r i z v i 等学者在文献 1 1 中根据朴素贝努里概型提出了一个称 为m a s k 的隐私保护算法。作者使用的数据库是由固定长度的0 ，1 序列形成的 记录组成的。算法的具体实现是通过对所有原数据按照贝努里概型进行变换。 考虑到对原数据进行变换所耗费的时间和空间，远比在数据挖掘时对数据的重 建的消耗要大很多，因而s h a r i q 后来对m a s k 算法进行了一些优化。 第2 章隐私保护数据挖掘算法综述 2 4 本章小结 本课题的研究重点是在集中式数据环境下保护数据隐私。这些算法通过对 原始数据进行不可逆的变换来实现隐私保护。通常在挖掘时，起到决策性作用 的并不是数据本身，而是某种统计数据，如相似度、计数分布等。只要能够通 过重建技术从变换后的数据中得到原始的统计数据，就可以获得正确的挖掘结 果。当变换对挖掘算法关心的统计数据不产生影响或影响极小时，甚至可以直 接在变换后的数据上进行挖掘。 9 第3 章独立噪音算法 第3 章独立噪音算法 针对聚类分析时如何保护隐私的问题，提出了独立噪音思想并设计了独立 噪音算法。该算法通过向原数据叠加噪音来保护原始数据不被泄漏，而且所使 用的噪音对数据分布不造成严重影响，使得后期挖掘工作可以在干扰后的数据 上直接进行。实验证明，该算法可以在隐私保护程度与算法精度上都取得较好 的结果。 3 1 引言 聚类是一个将数据集划分为若干组或类的过程，使得同一个组内的数据具 有较高的相似度，而不同组中的数据则是不相似的。聚类分析的基本指导思想 就是最大程度地实现类中数据相似度最大，类间数据相似度最小。相似或不相 似的度量是基于数据各属性的取值来确定的。通常就是利用各对象间的距离来 进行描述的。聚类分析是一个正在蓬勃发展的领域，其应用也变得越来越广泛， 如顾客的购买行为分析、模式识别、市场分析等。 在商业合作中，经常需要进行聚类分析。不同的公司，各自都拥有自己的 客户购买行为的数据集。为了共同的利益，决定利用聚集数据进行挖掘。假设 聚类的目标是对商场购买力较大的客户居住地进行分析，以帮助商场主管针对 相应客户群采取针对性的营销策略。那么各个公司必须确信能够在本公司客户 的隐私不受侵害的情况下获取最终的聚类挖掘结果。 对于聚类挖掘的隐私保护方法，o l i v e i r a 和z a i a n e 提出了“几何变换算法”。 它通过对原数据进行几何变换，使变换后的数据偏离原数据，同时几何变换也 保证了数据之l j 的相对距离保持不变。 最早的隐私保护数据挖掘算法使用的是叠加噪音的方法，并通过b a y e s 理 论重建原始分布，利用重建结果，构造决策树。虽然没有经过实验，但人们相 信叠加噪音的方法同样适用于隐私保护的聚类发掘心引。 本章讨论的“独立噪音算法( i n d e p e n d e n tn o i s em e t h o d ，本章中称为m 算法) ”正是对上述结论的实践。该算法通过扰乱机密的数值型数据来实现在聚 类挖掘中对数据的保护，而且这个算法不依赖特定的聚类算法j 不同于“几何变换算法”，烈m 算法是通过向原数据叠加噪音来保护隐私； 而且相较于以往的叠加噪音的算法，i n m 算法不需要重建原始分布，可以直接 在干扰后的数据上进行聚类挖掘。 北京t 、i k 大学工学硕l 学位论文 曼曼! ! ! ! ! ! 皇曼曼曼曼曼苎! 皇i ! 一i 曼! 曼! 皇! 曼! 曼! ! 曼曼曼 3 2 基本概念 为了方便理解i n m 算法，本节对相关的基本概念作一些简要的阐述。 3 2 1 数据干扰 数据干扰包括叠加噪音、数据变换等多种方法，在这里只讨论叠加噪音的 方法，也称为噪音算法。噪音算法的最简单形式是在原数据x 上叠加噪音y 得 到干扰后的数据x ，可以描述为x 习h l 这里】，是取自某种均值为0 的概 率分布( 例如正态分布或均匀分布) 。噪音算法主要应用于数值型或枚举型数据。 3 2 2 数据描述 设：原数据库d 由m 个数值型属性a ，么朋构成；数据库d 包含刀个数据 元组，记为：d = - ) ：每一个数据元组x 记为：= 黾气聊) ，其中，对 任意的i = l ，z ，卢1 一m ，x i d 是数值型数据。相应的，干扰后的数据库记为：d 7 = 7 - x 7 ) ，其中x7 = 托，7 。气用7 ) 。 3 2 3 隐私度度量 叠加噪音算法对隐私数据的保护程度是由原数据和干扰后的数据之间的差 异程度来度量的，称为数据安全度”n 钔。若各元组在属性4 上的取值记为 妒b ，l ，j ) ，对应的干扰后的数据记为4 = x d - x n d7 ) ，则属性a j 的数据 安全度定义为s e c # v a r ( a j - a j7 ) v a r ( a j ) 。函数玩， ) 表示取值集合仁j i ，。x 。，) 的 统计方差。对于m 个数值型属性a ，么朋，定义它们的“最低数据安全度”为： m s e c = m i n ( s e c ，) 。 l = 1 ， 3 2 4 有效性度量 隐私保护算法的有效性是指对干扰前后的数据分别进行数据挖掘所得结果 的偏差程度，偏差越大，有效性越低。对于聚类算法，一般采用“误分类率” 作为偏差的度量。设：一个聚类算法在原数据上得到“个簇，它们是 c 1 一乜) ； 同样的算法在干扰后的数据上得到，个簇，它们是 c z “c v7 ) 。其中，若g 与g 均存在，则c w 与c w 被识别为一对相对应的簇。据此定义函数血： 若在原数据上经聚类运算，数据元组x g ，x 经干扰后得到的元组为7 ，并 且有x7 c7 ，则只有在q = p 时，函数取值为o ，否则，函数取值为1 。于是， 1 2 第3 章独立噪音算法 定义误分类率为：讹= 去喜( z ) a 可见，误分类率越高，隐私保护算法 的有效性越低。 3 3 独立噪音思想 为了获得适当的有效性，噪音算法必须控制噪音的大小。当噪音很大时， 干扰后的数据分布与原数据分布差别很大，若要得到工f 确或近似正确的挖掘结 果，就必须通过一些方法重建原始分布( 如b a y e s 公式) 。 独立噪音算法要求直接在干扰后的数据上进行聚类计算并得到近似正确的 挖掘结果。为了使干扰后的聚类结果逼近正确的挖掘结果，需要让干扰后的数 据分布与原数据分布尽量相近。i n m 算法选用( 一z + 功间的均匀分布做为随机噪 音，称作大小为d 的噪音。 传统噪音算法对不同数据元组在同一属性上的数据叠加同样大小的噪音。 实验表明，只要噪音稍微偏大，就有可能使很多数据元组被误分类；而从另一 面讲，如果噪音变小，虽然误分类率可以降低，但同时数据安全度也会下降。 实验还发现，如果把数据库看作7 维的欧几里德空间，把数据元组看作空 间中的点，则产生误分类的元组全部集中在一个簇的边缘。这是因为，处在簇 中央的元组，即使叠加了比较大的噪音，也不足以使它们偏移到该簇以外；而 处在簇边缘的元组，只要噪音稍微偏大，就会使它们偏移到另一个簇的范围内。 这种不平衡的现象却提示了解决隐私度和有效性之间矛盾的一种可行方 法：增大叠加在簇中央的元组上的噪音，可以在不增加误分类的前提下提高隐 私度；减小叠加在簇边缘的元组上的噪音，可以在较大的隐私度条件下获得较 好的聚类运算的有效性。 这就是独立噪音的思想：( 1 ) 对处在簇中央的数据元组叠加较大的噪音； ( 2 ) 对处在簇边缘的数据元纣【叠加较小的噪音；( 3 ) 噪音的大小不使元组偏移 出原来簇的范围。 3 4 独立噪音算法设计与分析 实现独立噪音，关键在于估算每个数据元组在簇内的位置以及它到簇边界 的距离。为此，i n m 算法采用了称为直接归类的算法，利用该算法可以从原数 据库的样本数据中得到一些参考点，然后将每个数据元组与这些参考点作对比， 可以估算出数据元组在簇中的位置，并计算出将要对它叠加的噪音大小。 北京t 业大学工学硕一i ：学位论文 3 4 1 独立噪音算法设计 i n m 算法分为两个部分：直接归类和独立噪音的计算与叠加( 见图3 1 ) 。 第一部分是在样本数据上执行直接归类得到若干个参考点；第二部分是根据原 数据元组与参考点之间的距离，计算噪音的大小并对数据元组叠加噪音。 原数据库 剽燃。怄 干扰后的 数据库 图3 - 1 独立噪音算法 f i g u r e3 1t h ei n d e p e n d e n tn o i s em e t h o d i n m 算法中涉及到不同数据元组之间“距离 的计算。由于语义不同的属 性会有不同的域和“度量单位”，所以，两个数据元组、为之间的距离可以 定义为： d i s t ( x i ，x 2 ) = 其中，口是为了“规范”不同属性的域和度量单位而引入的规范化因子。 i n m 算法的第一部分中，样本数据是从原数据库中经过随机抽取部分数据 元组形成的。设：样本数据通过执行直接归类算法，被归并成b 个小类，每个 小类中所包含的数据元组个数，由c o u r t t ，指示( 产1 b ) ，每个小类的中心坐标 劬砬就是所求的参考点。下面是直接归类算法的具体过程： 步骤1 ：获取样本数据所有数据元组在各属性上的最大值和最小值：i b a x ， m a x ，m i n ，i n , ，并令p m a x = ( m a x ，- 伽心，p m i r f ( r a i n ，r a i n ) ； 步骤2 ：令r 严d i s t ( p m a x , p m i n ) 夕； 一 步骤3 ：从样本数据中取出一个元组胙( 西砧； 步骤4 ：初始化：令b = l ，卵( 西砧，c o u n t ，= l ； 步骤5 ：重复以下步骤直到样本数据集为空： 步骤5 1 ：从样本数据中另取一个数据元组x - - ( 局砧； 步骤5 2 ：从a 现中找到与j 距离最近的点。设该点为劬，它与j 的 距离为乃 步骤5 3 ：如果尺局则 更新纺，c o u r t t p c o u n t ，1 ，否则 b = b + l ，卵( z ，c o u n t r ：1 ； 步骤6 ：输出参考点劬醌。 1 4 冤3 币独市噪 f 算法 步骤5 3 中的“更新劬，是对研的每一个分量q i , j ( 户1 砌做如下的更新 运算：g 。，：旦兰竺掣。为了限定每个小类的空间大小，i n m 算法引入 。 ，o u n t ，+ l p 参数。显然鼻越大，参考点的数量就越多。 利用由直接归类算法得到的参考点劬酝，就可以计算原数据库刃中每个 元组的独立噪音大小，同时完成噪音叠加，生成干扰后的数据库刃7 。这一部分 算法过程如下： 步骤1 ：令刀7 为空； 步骤2 ：重复以下步骤，直到处理完毕口中所有的数据元组： 步骤2 1 ：顺序读取个数据元组片( 西柚； 步骤2 2 ：从劬识中找到与该元组距离最近的两个参考点。设：这两 个参考点与x 的距离分别为乃、乃，且有r a r z ； 步骤2 3 ：对于i = 1 肪依次计算：妒口盟，乃7 = x ；+ r a n d o m ( 一斫， 2 斫) ； 步骤2 4 ：将j 7 = ( x t7 矗7 ) 加入刃7 ； 步骤3 ：输出刃。 从i n m 算法的整体来看，第一部分是对样本数据的两次扫描，第二部分是 对全体数据的一次扫描。一般情况下，样本数据的容量远小于数据库的数据量， 因此，i n m 算法的i o 开销接近于一遍读取数据库数据。 i n m 算法的计算时间开销主要体现在计算数据元组与参考点之间的距离。 算法的第一部分中，样本数据的每个元组要与当前已得到的参考点计算一次距 离；而在第二部分中，数据库的每个元组要与每个参考点计算一次距离。因此， 算法的计算时间开销为0 ( b - ) 。 3 4 2 独立噪音算法思想分析 可以看出，执行i n m 算法时，处于簇中心的数据元组j 比较接近某一个参 考点，“一r 2 ) 相对较大，数据兀组叠加了较大的噪音；反之，处于簇边缘的 数据元组x 远离所有参考点时，( r l 一 ) 相对较小，数据元组叠加了较小的噪 音：这满足了“独立噪音思想”的自，j 两个要求。 下面证明算法满足“独立噪音思想”的第三个要求。 首先，i n m 算法给数据元组叠加的噪音不改变与j 距离最近参考点。设p ，、包分别是与数据元组j 距离最近与次近的两个参考点，其距离分别为n 、乃。 北京t 业大学t 学硕一l ：学位论文 这三个数据点经过规范化后的图像如图3 - 2 。其中，直线是线段纺岛的中垂线， j 7 是z 关于直线的对称点，线段m 7 与相交于只 xpx f 嗲 - ： 9 ， t q 2 图3 - 2 独立噪音算法分析 f i g u r e3 - 2t h ea n a l y s i so fl n d e p e n d e n tn o i s em e t h o d 根据对称性和三角形三边关系，不难得到： d ：盟：垒兰二垒型：垒塑二垒塑 生塑：f x 爿 22z2 所以，给数据元组j 叠加大小为d 的噪音时，j 仍将驻留在直线- 的左侧， 距离较近的参考点仍是纺。显然，对于其它距离较远的参考点来说，结论同 样成立。所以，给数据叠加大小为d 的噪音，可以保证与j 距离最近的参考 点仍保持不变。 其次，若以“距离哪个参考点最近”为标准，把数据元组空间分割成一些 小的区间，对比实际聚类结果后发现：这些小区间绝大部分是聚类所得的簇的 更细的划分。也有极少数的区间会跨越两个或多个簇，但这些区间普遍都很小， 因此，只要能够保证数据元组在叠加噪音后还能驻留在原来的区间，也就保证 了绝大部分元组不会偏移出原来簇的范围。 综合上面的讨论，可以得出i n m 算法满足了“独立噪音思想”的所有要求。 3 5 实验及讨论 3 5 1 实验及结果 算法检验采用了二维平面上的点坐标做为数据元组，不考虑噪音，共生成 5 个原数据库，分别对应簇个数k 为2 到6 的聚类，每一个原数据库包含1 0 0 0 0 个点的数据；算法中的夕取为5 ，样本数据分别取5 0 、1 0 0 、2 0 0 、1 0 0 0 个数 据元组；聚类算法选用k - m e a n s 算法和c h a m e l e o n 算法。在实验中，对每一个 原数据库，分别在不同的样本数据大小下，各生成1 0 个干扰后的数据库，以这 1 0 个数据库的安全度和误分类率的平均作为结果。实验结果数据列于表3 1 、 表3 2 和表3 3 。 1 6 第3 章独帝噪音算法 表3 - 1不同样本数据大小下的最低数据安全度( ) t a b l e3 1t h em s e cu n d e rd e f e r e n ts w a t c hs i z e 样本大小 k = 2k = 3k = 4k = 5k = 6 5 02 0 51 8 03 8 34 4 43 2 2 1 0 01 6 12 0 73