（管理科学与工程专业论文）隐私保护数据挖掘研究.pdf

隐私保护数据挖掘研究 摘要 随着数据挖掘技术的不断发展以及数据挖掘技术在人类生活和工作中越来 越深入的应用，数据挖掘技术正日益影响着人们的生活。在不断挖掘出新的规 律、给人类带来知识和提供便利的同时，数据挖掘也不可避免地涉及到人们的 隐私问题。同时，伴随着人们对个人隐私关注的不断提高，数据挖掘技术在完 成挖掘任务时也遇到了越来越多的新困难。隐私保护数据挖掘正是在这种情况 下产生的，其目的j 下是跨越数据隐私与知识发现之间的这道鸿沟。 本文首先综述了现阶段隐私保护数据挖掘算法的研究现状，指出其存在问 题：数据集中分布的隐私保护分类挖掘算法仅适用于布尔属性数据，或者要求 原始数据必须满足一定的概率分布且不太适用于分类类型的数据；其次，提出 了一种适宜于分类属性数据的隐私保护分类挖掘算法，该算法通过随机取值方 法对原始数据进行变换，从而起到对数据进行保护的目的，通过修改决策树挖 掘算法中的信息增益比例计算方法适应变换后的数据，实现具有隐私保护的分 类挖掘。该算法可以处理分类类型的原始数据，并且对原始数据的概率分布没 有要求。最后，通过实验分析，证明该算法是切实可行的。 关键词：隐私保护；数据挖掘；分类：决策树 m r e s e a r c ho np r i v a c y - p r e s e r v i n gd a t am i n i n g a b s t r a c t w i t ht h ed e v e l o p m e n ta n dt h ef u r t h e ra p p l i c a t i o ni nh u m a nl i r e ，d a t am i n i n gi s a f f e c t i n go u rl i f ed a yb yd a y b u ti ta l s oo f f e n d so u rp r i v a c yw h i l ei tb r i n g st h e k n o w l e d g ea n dm a k e sc o n v e n i e n c et ou s a tt h es a m et i m e ，p e o p l ep a ym o r e a t t e n t i o nt ot h e i ro w np r i v a c y ，a n di tm a k e sm o r ed i f f i c u l tt oc o m p l e t ed a t am i n i n g t a s k p r i v a c y p r e s e r v i n gd a t am i n i n gh a se m e r g e dt os o l v et h i sp r o b l e m i ta i m sa t b r i d g i n gt h eg a pb e t w e e np r i v a c y p r e s e r v i n ga n dk n o w l e d g ed i s c o v e r y f i r s to fa l l ，t h ep a p e rs u m m a r i z e st h et y p i c a la l g o r i t h m so fr e s e n tr e s e a r c ho n p r i v a c y p r e s e r v i n gd a t am i n i n g ，a n dt h e ni tp o i n t so u tt h ep r o b l e mt h a tt h ep r i v a c y - p r e s e r v i n gc l a s s i f i c a t i o na l g o r i t h m so fc e n t r a l i z e dd a t ao n l ys u i to nb i n a r y a t t r i b u t eo rt h ed a t am u s ts a r i s f ys o m ec e r t a i np r o b a b i l i t yd i s t r i b u t i o na n di td o e s n o ts u i to nc a t e g o r i c a la t t r i b u t ed a t a ；s e c o n d ，t h ep a p e ri n t r o d u c ean e w a l g o r i t h m t h a ts u i t so nc a t e g o r i c a la t t r i b u t e ，t h i sa l g o r i t h mu s e st h em e t h o do fg e n e r a t i n g r a n d o md a t at op r o t e c to r i g i n a ld a t aa n di tm o d i f i e st h e w a yo fc a l c u l a t i n g i n f o r m a t i o ng a i nr a t i ot oa c c o m p l i s hc l a s s i f i c a t i o nm i n i n g t h i sa l g o r i t h mc a nd e a l w i t hc a t e g o r i c a ld a t aa n dd o e sn o tr e q u i r et h ed a t af o l l o ws o m ec e r t a i np r o b a b i l i t y d i s t r i b u t i o n a tl a s t ，t h ee x p e r i m e n ts h o w st h ea l g o r i t h mi sc o r r e c t k e y w o r d s ：p r i v a c y - p r e s e r v i n g ；d a t am i n i n g ；c l a s s i f i c a t i o n ；d e c i s i o nt r e e i v 插图清单 1 - 1k d d 模型。2 2 - 1 保护规则的挖掘算法模型1 6 3 - 1 典型的决策树2 3 4 - 1 数据变换3 1 4 - 2 在原始数据集上进行决策树分类挖掘3 2 4 - 3p = 0 1 时隐私保护挖掘算法的误差率3 3 4 - 40 = o 3 时隐私保护挖掘算法的误差率3 3 4 - 59 = 0 。5 时隐私保护挖掘算法的误差率3 4 4 - 69 = 0 9 时隐私保护挖掘算法的误差率3 4 4 - 7 隐私保护算法精度随参数变化图。3 5 4 - 8 训练集1 2 0 0 条，秒= o 1 时隐私保护挖掘算法的误差率3 6 4 - 9 训练集3 0 0 0 条，秒= o 1 时隐私保护挖掘算法的误差率3 6 4 - 1 0 在扩充数据集上的精度统计3 7图图图图图图图图图图图图图 表格清单 表4 - i 原始数据属性及类型表3 0 表4 - 2 类值以及属性值的编号转换表3 1 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得佥墅王些太堂 或其他教育机构的学位或证书而使用过的材料。与我一同 工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示谢意。 学位论文作者签名目细 签字日期：2 0 诱年6 月多日 学位论文版权使用授权书 本学位论文作者完全了解金胆王些太堂有关保留、使用学位论文的规定，有权保留并向国 家有关部门或机构送交论文的复印件和磁盘，允许论文被查阅和借阅。本人授权盒胆王些盔堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者签名：闭塞地 签字日期：硼孑年f 月多日 学位论文作者毕业后去向： 工作单位： 通讯地址： 导师签名：夸芒l 訇 移 。 签字日期：2 君年6 月弓日 电话： 邮编。 致谢 时光飞逝，转眼间三年的时光就快过去了。回首往事，感慨良多。 首先，衷心地感谢我的导师李兴国教授。恩师虽然工作繁忙，但是仍然抽 出大量时间对我的学习、工作进行指导，我所取得的每一分进步无不倾注了恩 师的大量心血。恩师广博渊源的知识、高尚的师德、严谨的治学态度永远是我 学习的目标和内心的灯塔。感谢恩师，给我指引了工作、学习的方向和做人、 做事道理。 感谢钟金宏副教授、杜习英副教授、顾东晓老师、杨颖老师、卢光松老师， 从论文开题到定稿，你们都给予了我大量帮助和指导。 感谢管理学院及学校的各位领导、老师。是你们的辛勤工作，给我提够了 这样一个优越的学习、生活环境。 感谢龚芳、张薇、顾峰、郭瑞、杨贞、邓云、徐莹、田冲、谢伟等同学， 三年来的朝夕相处，使我感受到了人生最可宝贵的友情，和你们在一起学习、 工作，我感到非常愉快和幸运。 特别感谢我的女友，是她无微不至的关心和帮助，使我顺利地走到了今天。 感谢父母的养育之恩和一直以来对我的关心、支持和帮助。 感谢所有关心和帮助我的朋友。 感谢各位评审专家在百忙中抽出时间对我的论文进行仔细的评阅。 v 作者：周志纯 2 0 0 8 年4 月 第一章绪论 1 1 数据挖掘简述 近年来，由于计算机性能的提高、成本的下降以及存储技术和数据库技术 的快速发展，使得各企业、研究机构信息化程度越来越高，同时也积累了大量 数据。“数据丰富，知识匮乏 ，人们迫切地希望从这些海量数据中提取有用的 信息，这促使人们对数据分析工具、数据分析方法产生强烈的需求。通常，由 于数据量太大，以及数据本身的非传统特点，无法使用传统的数据分析工具和 传统的技术处理它们，因此，数据挖掘技术便应运而生了。 数据挖掘技术将传统的数据分析方法与处理大量数据的复杂算法相结合， 使得数据处理技术发展到一个更高级的阶段。数据挖掘是一门交叉学科，它融 合了数据库技术、统计学、人工智能、机器学习、信息检索、高性能计算、面 向对象以及数据可视化等最新技术地研究成果，吸引了计算机科学家、工程技 术人员统计学家的极大兴趣。 数据挖掘的定义很多，表达方式各不相同。从技术角度看，数据挖掘是从 大量的、不完全的、有噪声的、模糊的、随机的实际数据中，提取隐含在其中 的、人们不知道的、但又是潜在有用的信息和知识的过程；从商业角度看，数 据挖掘是一种崭新的商业信息处理技术。其主要特点是对商业数据库中的大量 业务数据进行抽取、转化、分析和模式化处理，从中提取辅助商业决策的关键 知识，即从一个数据库中自动发现相关商业模式。 数据挖掘是数据库中知识发现( 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 ) 中的一部分，而k d d 是将原始数据转化为有用知识的整个过程。k d d 是一个多 步骤的过程，典型的k d d 过程包括如下几个步骤： ( 1 ) 数据抽取与集成 在弄清数据的信息和结构的基础上，根据选取的数据源和抽取原则，准确 地从每个数据源抽取所需的数据，对数据进行合并处理，以达到数据集成的目 的。 ( 2 ) 数据预处理与清理 数据预处理是指对数据进行再加工，检验数据的完整性及一致性，对噪音 数据进行平滑，对丢失的数据进行填补，消除错误数据、重复记录等。常见的 数据预处理方法有：数据清洗、数据变换、维规约、特征子集创建、离散化和 二元化等等。数据预处理是进行数据分析和数据挖掘的基础，如果所集成的数 据不正确，数据挖掘的结果必然是不准确的。因此，数据预处理是数据挖掘中 必不可少的环节。 数据清理是指去除数据源中不完整、 数据的办法有：使用一个全局值来填充； 不一致、含噪声的数据。常见的修补 用该属性的所有非空值的平均值来填 充：使用同类对象属性的平均值来填充等。 ( 3 ) 数据选择与变换 数据选择是指从数据库中选择与挖掘任务相关的数据。 数据变换是指将数据变换或统一成适合挖掘的形式。 ( 4 ) 数据挖掘 经过数据抽取、预处理及数据变换后，进入了数据挖掘阶段，即使用不同 的方法从数据中提炼模式、模型和知识的过程。 ( 5 ) 模型评估 根据需要，对知识发现过程中的某些处理阶段进行优化，直到达到要求， 识别表示知识的模式。 ( 6 ) 知识表示 将得到的知识存入知识库中，通过检查和维护知识库的一致性，确定得到 新的和有效的知识。使用可视化等各种知识表示技术，向用户提供所挖掘的知 识。一个常见的k d d 模型如图l 一1 所示： 图i - ik d d 模型 1 2 隐私权与信息隐私权 隐私是人类社会文明不断演进的产物，是不断发展的概念。最初，隐私的 概念源于人类的原始感知，原始人用兽皮、树叶等遮住自己身体的敏感部位， 免于在公共场合暴露，这是一种原始的隐私保护意识。随着社会的发展和文明 的不断进步，人类的隐私意识也不断得到增强和转化。在现代社会中，隐私是 2 指私人生活安宁不受他人非法干扰，私人信息保密不受他人非法搜集、刺探和 公开。 隐私权是社会民主制度发展到一定阶段的产物。隐私权的概念起源于美国， 1 8 9 0 年，美国著名学者w a r r e n 和b r a n d e is 在哈佛法律评论中发表了一篇 论隐私权的文章，文章中将隐私权界定为“让我独处的一种权利，不受别 人打扰的一种权利”。从此，隐私权作为一个法律概念正式得以确认。美国的 法律中，将侵权行为定义为以下几种情况：不合法的侵入他人之秘密；窃用他 人之姓名和肖像；不合理的公开他人之私生活；使他人有不实形象之公开心1 。 在现代的概念中，隐私权是指公民享有的私人生活安宁与私人信息依法受到保 护，不被他人非法侵扰、知悉、搜集、利用和公开的一种个人权利口1 。 随着信息科技的巨大发展，人们的交往方式发生了很大转变，人类更多地 通过互联网进行信息交流。而在网络时代，人们的信息更容易暴露，随之而来 的是人们的隐私权受到了前所未有的严重冲击，信息隐私问题变得越来越突出。 个人资料如姓名、生日、电话号码、病例、职业、身份证号码、电子邮箱地址、 q q 号码、i p 地址等等被大量、全面地收集，这些数据在被计算机分析处理后， 可以迅速地进行传递和应用，其所带来的危害比传统社会严重地多。因此，信 息隐私权的概念便应运而生了。信息隐私权是指个人享有的对于其本人信息的 控制权和处理权；是指自然人享有的私人信息依法受到保护，不被他人非法知 悉、搜集、利用、公开等的一种人格权。 信息隐私权的客体可以分为以下几个方面h 1 ： ( 1 ) 个人属性的隐私( p r i v a c yo fap e r s o n sp e r s o n a ) ：如一个人的姓名、 身份、肖像、声音等可以直接识别个体、涉及个人领域的第一层次，可谓是直 接的个人属性，为隐私保护的首要对象。 ( 2 ) 个人资料的隐私权( p r i v a c yo fd a t aa b o u tap e r s o n ) ：当个人属性被 抽象成文字的描述或记录，如个人的消费习惯、病历、宗教信仰、财务资料、 工作、犯罪前科等记录，若其涉及的客体为一个人，则这种资料即含有高度的 个人特性而得以间接识别该个体，可以说“间接 的个人属性也应以隐私权加 以保护。 ( 3 ) 通信内容的隐私权( p r i v a c yo fap e r s o n sc o m m u n i c a t i o n s ) ：个人 的思想与感情，原本存于内心之中，别人不可能知道：当与外界通过电子通信 媒介如网络、电子邮件沟通时，即充分暴露于他人的窥探之下，所以通信内容 应加以保护，以保护个人人格的完整发展。 ( 4 ) 匿名的隐私权( a n o n y m i t y ) ：匿名发表的方式是网络虚拟世界的显著特 征，在历史上也一直都扮演着重要的角色，这种方式可以保障人们自由言论、 发表意见；保障人们愿意对社会制度提出一些批评。这种匿名权利的适度许可， 可以鼓励个人的参与感，并保护其自由创造力空间；而就群体而言，也常能由 3 此获利，真知直谏的结果推动社会的整体进步。 1 3 隐私保护数据挖掘的产生背景 在当今这个信息大爆炸的时代，随着计算机技术、互联网以及存储技术的 发展，人们积累了大量的数据，这些数据记录了人们的相关资料，如个人消费 习惯、超市物品选择、收入和理财习惯、网页浏览取向等等。而隐藏在这些数 据后面的是具有潜在价值的信息。 传统的数据库系统可以实现数据的录入、查找、删除、统计等基本功能， 但是却无法发现在数据背后隐藏的关系和规则，无法通过数据进行预测。因此， 如何在这些海量数据中寻找模式、趋势和异常之处，并且以简单的模型对其进 行归纳，是当今信息时代的巨大挑战。 数据挖掘是在大型数据存储库中，自动地发现有用信息的过程。数据挖 掘技术广泛地应用于科技研究、商业智能处理等领域，例如定向销售、顾客分 析、超市商品分类、商店分布和欺诈检测等。 然而，事物总是具有两面性。随着数据挖掘技术的不断发展，大量的私人 信息如电话号码，就诊病例、信用卡号码、消费清单、犯罪记录等等被广泛的 收集和分析，这些分析在医疗诊断、商业决策、预防犯罪等方面起到了许多积 极的作用。然而，在进行这些数据采集、分析的同时，人们逐渐感到个人隐私 受到了侵害。更严重的是，如果这些数据及相关分析利用不当，或被不法分子 所得，将对人们的隐私安全带来严重的威胁。 试想一下，某日当您用信用卡为您的医疗就诊结账后，几天之内突然收到 药材公司和医疗器械公司的产品广告或者保险公司的投保订单时，您会作何感 想：当您在网上购物后，许多类似产品信息在您的邮箱中不期而至时，您是否 感到自己的隐私收到了侵害。正因为如此，在西方发达国家，很多人出于保护 隐私的目的，宁愿使用现金而不是信用卡消费；许多在网上购物后收到垃圾邮 件的人从此放弃了网上购物念头。 出于保护隐私的目的，当进行产品调查时，人们在提供信息时，往往会提 供错误的信息甚至拒绝提供涉及自己隐私的信息。在一份w e b 用户的调查拍3 表 明，1 7 的被调查者表示会拒绝透露涉及自己隐私的任何信息，2 7 的被调查者 表示会认真考虑后，决定是否给予涉及自己隐私的信息：而5 6 的被调查者表 示，如果数据收集机构可以确保个人隐私信息得到有效保护，他们可以提供涉 及自己隐私的信息。从以上的调研材料可以看出，在产品调查时，如果无法保 证被调查者的隐私，所收集到的数据往往和真实的数据存在很大的误差甚至无 法完成数据收集。如果在这些错误数据的基础上进行数据挖掘，那么所得到的 结果必然是不准确甚至完全错误的。 与此同时，在一些商业合作分析中，经常进行多方合作数据挖掘，由于种 4 种原因，参与者不愿意共享他们的原始数据而只愿意共同分享挖掘结果。 因此，摆在人们眼前的问题是： ( 1 ) 如何才能使得在产品调查中取得真实的数据，或者说如何才能获得可以 顺利进行数据挖掘的数据： ( 2 ) 如何才能在商业合作分析中，在满足不泄露各方数据的基础上成功地进 行数据挖掘。 以上这些原因促使了隐私保护数据挖掘算法研究的产生。 1 4 隐私保护数据挖掘的研究现状与研究意义 1 4 1 研究现状 隐私保护数据挖掘是数据挖掘的一个重要研究方向，同时也是一个极具挑 战性的课题。1 9 9 9 年，r a k e s ha g r a w a l 在k d d 9 9 中将隐私保护数据挖掘作为未 来的研究重点之一。从此，隐私保护数据挖掘便迅速地发展起来，各种新的方 法不断涌现。 2 0 0 0 年，r a k e s ha g r a w a l 和r a m a k r i s h n a ns r i k a n t 率先提出了一种通过 添加随机量的方法对原始数据进行变换哺3 ，然后利用贝叶斯公式来推导原始数 据的密度函数，从而构造判定树的隐私保护挖掘算法。这种算法适用于考察数 据的概率分布而非具体数值的挖掘算法。该算法提出了一个重要的研究思想， 即能否在不访问原始数据精确值的情况下进行数据挖掘。 w e n l i a n gd u 和z h i j u nz h a n 将一种源于统计学的技术一随机响应技术应 用于数据集中分布的分类挖掘h ，实现了对原始数据的变换，并使用i d 3 决策 树算法在变换后的数据上进行分类挖掘。其他一些文献将这种技术与其他数据 挖掘算法进行结合。 y l i n d e l l 和b p r i n k a s 探讨了在两个不愿意共享数据的数据持有者之间， 如何进行数据挖掘的应用，并具体讨论了i d 3 算法在这种假设下的实现，由此引 进安全多方计算协议3 。 在隐私保护聚类挖掘算法方面，s t a n l e yr m 0 1i v e i r a 等人在2 0 0 3 年， 提出了一种隐私保护聚类挖掘算法n 3 。该算法主要通过几何转换如平移，缩放 和简单的旋转等转化原始数据，从而达到对数据进行保护的目的。但是，这个 方法存在一定的缺陷。在进行数据变换时，容易改变数据的相似性，从而造成 聚类的误差：同时，这个方法对于空间的维数也有一定的限制。因此，2 0 0 4 年 s t a n l e yr m 0 1 i v e i r a 等再次提出了一种针对聚类挖掘的隐私保护算法“叫。该 算法提出了一种基于旋转变换r b t 变换数据的方法，实现了多维空间中点的等 距变换，达到了很好的隐私保护效果。在保护数据隐私的同时保证变换后的数 据之间的相对距离保持不变，从而保持了聚类挖掘效果的正确性。张国荣，印 鉴3 在r b t 算法的基础上，提出了一种利用等距变换实现初始数据隐私保护的 5 改进算法i b t ( i s o m e t r i c b a s e dt r a n s f o r m a t i o n ) 。 j a i d e e pv a i d y a 和c h r i sc l i f t o n 【1 2 3 提出了一种新的点积协议应用于数据 垂直划分的聚类挖掘问题，使得每个站点在得到聚类结果时，不会泄露自己站点 内部各自的属性值。m e r u g us 等人n 3 1 也提出了一种解决分布式聚类分析的隐 私保护方法，在这个方法中，每个站点共享部分原始的数据或扰乱的数据，在每 一个本地站点生成合适的参数，然后把参数传送给中心站点，通过合理的抽样 完成高质量的分布式聚类。p a u lb u n n 和r a f a i lo s t r o v s k y u 也提出了一种安 全多方计算的k 均值挖掘算法，用来保护分布式聚类挖掘中的信息。 在隐私保护关联规则挖掘算法方面e d v a s s i1i o s 和s v e r y k i o s n5 1 们等 人提出两种方法应用于隐私保护的关联规则挖掘，一种方法是通过隐藏频繁项 集来防止需要保护的关联规则产生：另一种方法是通过使重要规则的置信度小 于用户指定的最低置信度，从而防止需要保护的规则被挖掘出来。 s r m 0 1 i v e i r a 和o s m a rr z a i a n e 【l 刀在已有研究的基础上，提出一种隐私 保护的频繁项集挖掘算法，该算法通过一个交易检索方法来过滤数据记录，保护敏感 规则，并减少数据清洗阶段的影响，实现了在发现尽可能多的规则和保护隐私数据之 间的一定程度的平衡。其他的文献n 卜3 阳也提出了一些隐私保护数据挖掘的算法和 框架。 1 4 2 研究意义 隐私保护数据挖掘是未来数据挖掘一个非常重要的研究领域，该问题一经 提出，受到数据挖掘研究者的极大重视。 目前，在数据集中分布的隐私保护分类挖掘中，主要采用以下两种挖掘方 法： ( 1 ) 随机响应方法：采用一种源于统计学的模型一一“沃纳模型 ，对数据 随机进行变换，并在变换后的数据上推导原始数据的取值概率，最终进行分类 挖掘的算法。 ( 2 ) 添加随机偏移量方法：一种通过在原始数据中加入随机偏移量，然后对 数据的分布进行重构的方法。 随机响应技术和分类算法相结合，应用于隐私保护数据挖掘中。由于其简 单、易用，效率较高，因此取得了不错的效果。但是随机响应技术也存在着一 定的局限性：它只能处理属性值为布尔值类型的数据( 二元数据) 。 同时，对原始数据添加随机量的方法要求原始值必须是已知的，这就产生 了泄密的可能性；另外，该方法还要求原始数据满足一定的概率分布，不太适 用于分类属性的数据，计算量也比较大。 本文针对这些方法的局限性，提出了一种新的隐私保护分类挖掘算法。该 算法可以处理分类属性的原始数据，同时对于原始数据的分布没有要求。算法 的第一部分通过数据变换来伪装数据：第二部分通过修改决策树挖掘算法中的 6 信息增益比例计算方法，来适应变换后的数据，实现具有隐私保护的分类挖掘。 实验证明，该方法是切实可行的。 1 5 论文结构安排 本文的结构安排根据要解决的问题和所涉及的内容共分为五章，论文结构 如下： 第一章，简述隐私保护数据挖掘的产生背景、研究现状，以及本文的研究 意义，并介绍各章节安排。 第二章，分析了数据挖掘所带来的隐私问题，并按照数据分布形式和数据 挖掘算法的不同，介绍了现阶段一些主要的隐私保护挖掘算法。 第三章，针对现阶段数据集中分布隐私保护分类挖掘算法的局限性，提出 了一种新的隐私保护分类挖掘算法。 第四章，通过实验对所提出的算法加以验证。 第五章，总结全文，并对未来的研究工作进行展望。 7 第二章隐私保护数据挖掘算法综述 隐私保护数据挖掘是数据挖掘的一个重要研究方向，同时也是一个极具挑 战性的课题。1 9 9 9 年，r a k e s ha g r a w a l 在k d d 9 9 中将隐私保护数据挖掘作为未 来的研究重点之一，从此，隐私保护数据挖掘便迅速地发展起来，各种新的方 法不断涌现。 本章中将首先分析数据挖掘对人们隐私的侵犯，接着对现阶段一些主要的 隐私保护数据挖掘算法进行了归纳、总结。 2 1 数据挖掘对隐私的侵犯 随着数据挖掘技术的不断发展，数据挖掘技术在人类生活和工作中得到了 广泛地应用，对人们的生活产生极大的影响。然而，数据挖掘技术在不断挖掘 出新规律，给人们带来知识和提供便利的同时，也不可避免地涉及到人们的信 息隐私问题。 技术的发展使得人们可以收集和处理海量的数据，包括个人身份证号码、 q q 号码、电子邮箱、犯罪记录、客户的购买习惯、信用卡消费记录以及医疗历 史记录等等。这些信息如果能得到正确处理，无疑会给人类的生活和社会的发 展带来巨大的帮助，例如：使用数据挖掘技术分析医疗历史，可以帮助医生更 好地分析病人的病情和病因；分析信用卡消费记录，可以掌握用户的消费习惯， 最大可能地避免信用卡欺诈：分析犯罪记录，可以帮助警方侦破案情和最大可 能地预防犯罪等等。 根据z d n e tc h i n a 报道显示，一份关于美国联邦机构的调查显示，有多达 1 2 0 个应用程序在收集和处理大量个人数据，并以此对个人行为进行预测，该 调查还发现，这种被称作数据挖掘的行为几乎无所不在。美国国防部不惜余力 地采用数据挖掘技术中4 7 个数据挖掘项目，跟踪调查所有的事件，从n a v v 的 学术成就到船舶零件，以及有嫌疑的恐怖分子。审计局通过对联邦机构的调查 分析发现，其中有5 2 家机构曾系统地对数据库进行了过滤。这些机构报道了 1 9 9 个数据挖掘项目，其中6 8 个已做了计划，另外有1 3 1 个正在操作，这1 9 9 个项目当中，至少采用了诸如姓名、电子邮件、社会保障号、驾驶执照等作为 识别信息，其中有5 4 个项目的信息来源于信用报告或信用卡交易记录等私有部 门。7 7 个项目采用了来自其他联邦机构的数据，如学生贷款记录、银行账户以 及纳税人账户等；政府的这些数据挖掘引发诸多个人隐私问题阳1 。 人们对于自己的隐私受到侵犯感到忧虑。美国的一份民意调查显示，有7 0 以上的被采访者反对将医疗记录不受限制地应用于研究；有7 8 的被采访者认 为，计算机威胁到个人隐私，因此，如果要保护隐私，将来要严格控制计算机 的使用；将近7 6 的人觉得自己已经失去了对个人信息的控制，隐私受到了威 胁。 8 时代周刊、英国广播电视和其他最近的研究表明：至少有9 3 被采访者认 为，公司在出售个人数据之前必须得到个人的允许。另一项调查显示，有9 6 的采访者认为，私人信息不应该在没有得到允许的情况下使用；超过2 0 的被 采访者亲身遭遇过隐私被侵犯。相比较而言，在1 9 7 0 年的同样调查中，只有 3 3 的人认为计算机技术对个人隐私是一个威胁哺1 。 同时，除了数据挖掘的对象一一数据会对人们的隐私产生威胁之外，数据 挖掘所获得的知识同样会威胁到人们的隐私。 一个简单的关联分析的应用，可以将电话记录和银行记录联系起来，从而 决定顾客解决期权贷款的可能性，电话公司为了计费不得不监测电话记录，银 行必须跟踪其客户的账户交易，但是，当这些数据被用于不被授权的其他目的 时，就成为一个严重的隐私问题。一个模式可以用来推测机密特性，同样，它 也会导致传统和偏见，如果模式是建立在诸如种族、性别或者国籍上，并且该 模式数据没有得到用户的授权，那么问题可能会变得更加敏感，并引发争议。 例如银行可能会使用数据挖掘工具来分析不同种族之间的不同行为模式，然后， 基于这种特征拒绝给某个种族提供信用，或者根据种族的不同实行不同的政策； 这些方法实际上都涉及到人们的隐私。相信很多人如果知道这些情况，在进行 数据收集时，很有可能会拒绝提供自己的个人数据。 另一方面，如果隐私保护对数据实行太多的限制，数据的可用性将会变得 很差，数据挖掘如果不能充分地访问数据，那么挖掘任务将会难于进行，许多 政策和计划都无法制定。例如，如果不对医疗记录进行分析，就无法了解、控 制和治疗疾病：如果不统计调查犯罪记录，将对侦破案情和有效地预防犯罪产 生极大的影响。人们在数据被收集的过程中，获得了知识和帮助，同时也承担 着隐私被泄露的风险。隐私保护不能简单的通过限制数据收集和数据分析来达 到。因此，必须在隐私保护、数据挖掘和知识发现之间找到一个平衡点。 2 2 隐私保护数据挖掘的分类 隐私保护数据挖掘是未来数据挖掘一个非常重要的研究领域，1 9 9 9 年， r a k e s ha g r a w a l 在k d d 9 9 中将隐私保护数据挖掘作为未来的研究重点之一，从 此，隐私保护数据挖掘便迅速地发展起来，各种新的方法不断涌现。 2 0 0 4 年，v a s s i l i o ss v e r y k i o s 和e 1 i s f lb e r t i n o 等人口刀从数据分布、 数据修改、数据挖掘算法、数据及规则的隐藏以及隐私保护技术五个角度对现 有的较为典型的隐私保护数据挖掘算法进行了分类。 ( 1 ) 数据分布( d a t ad is t r i b u t i o n ) ：这个角度主要涉及到数据的分布方式。 一些算法主要研究数据集中分布的情况，另外一些算法主要研究分布式数据挖 掘的情况，其中，分布式数据挖掘又可以分为数据水平分布和数据垂直分布两 种。 9 ( 2 ) 数据修改( d a t am o d i f i c a t i o n ) ：这个角度主要涉及到数据修改的方案。 一般来说，为了确保被公开数据的隐私安全性，原始数据在被公开之前需要经 过修改，进行伪装，数据修改方案需要和隐私保护策略相结合。常用的数据修 改方法包括： 数据扰乱( d a t ap e r t u r b a t i o n ) ：即将原始数据的属性值替换为一个新的 值，如在布尔属性值中进行0 一l 互换，添加噪声数据等； 数据阻塞( b l o c k i n g ) ：即用“? 来替代存在的值，以保护敏感数据和规 则；合并或聚合多个详细数据成为一个更高层次的数据； 取样( s a m p l i n g ) ：即对数据进行抽样。 ( 3 ) 数据挖掘算法( d a t am i n i n ga 1 9 0 r i t h m ) ：这个角度主要考虑适用于不 同的数据挖掘算法，如分类算法、关联规则挖掘算法、聚类分析算法等。 ( 4 ) 数据及规则的隐藏( d a t ao rr u leh id i n g ) ：这个角度主要考虑需要隐 藏的是原始数据还是规则。原始数据主要指用户的姓名、身份证号码、银行卡 号码、住址、工资等敏感数据：规则主要指使用数据挖掘算法从数据中挖掘出 来的侵犯隐私的信息等。隐私保护数据挖掘的目标是通过使用修正原始数据的算 法，使得在进行数据挖掘之后，属于隐私的数据和信息依然保持隐藏而未被发现。对 原始数据的保护难点在于，必须在保护隐私的同时，高效地挖掘出数据背后隐藏的知 识；而对于规则来说，保护难点在于，隐私保护者希望通过隐私保护算法所隐藏的信 息，却经常会被非专业的用户从公开的数据中发现。通常隐藏规则比伪装原始数据 的复杂度要高，有时通过保护敏感规则，往往能同时起到保护重要原始数据的 目的。 ( 5 ) 隐私保护( p r i v a c yp r e s e r v a t i o n ) 技术：这个角度主要考虑的是修改数 据所采用的技术。隐私保护技术是五个分类标准中最重要的，因为它能直接反 映隐私保护的程度。从隐私保护技术这个角度又可以分为： 基于启发式技术的方法，例如自适应地进行数据更改技术，该方法只改 变部分选中数值，而并非所有数值： 基于密码学技术的方法，该方法主要利用密码学知识对数据进行加密， 例如安全多方计算( s m c ) 方法，即参与计算的各方只能获得自己所提供的输入数 据以及最终结果，而对于其他参与者的数据他们一无所知： 基于重构技术的方法，即从被随机扰乱的伪装数据中重构原始数据的分 布。 下面本文将根据数据分布形式的不同，分别介绍现阶段主要的隐私保护挖 掘算法。 1 0 2 3 数据集中分布的隐私保护数据挖掘算法 2 3 1 数据集中分布的隐私保护分类挖掘算法 在数据集中分布的隐私保护分类挖掘中，现阶段主要采用以下两种方法： ( 1 ) 添加随机偏移量方法：一种通过在原始数据中加入随机偏移量，然后对 数据的分布进行重构的方法。 r a k e s ha g r a w a l 和r a m a k r i s h n a ns r i k a n t 率先提出了一种基于数据重构 技术的隐私保护分类挖掘算法】。首先，该算法通过添加随机变量的方法实现 对原始数据的变换，然后从变换后的数据中推导出原始数据的密度函数，从而 构建判定树。 该算法的主要思想是：首先，作者假设有n 个原始数据值一，x 2 ，x 3 ，吒， 相对应有n 个独立同分布的随机变量墨，置，墨，五，其中每个随机变量都与 随机变量x 的分布相同。为了保护这n 个原始数据，分别给它们加上n 个数据 值m ，奶，y 3 ，只进行数据扰动，这n 个数据值对应于1 2 个对立同分布的随机变 量x ，艺，e ，艺，其中每个随机变量都与随机变量y 的分布相同。y 可以是一个 分布区间为【一口，+ 口】、均值为0 的均匀分布，也可以是一个均值为0 、标准方差 为口的高斯分布。得到n 个新的数据值而+ y l ，+ 儿，黾+ 乃，+ 后，问题 则转化为如何在已知y 的分布函数e 和 n 个数据值 而+ m ，恐+ y 2 ，玛+ y 3 ，+ 只情况下，推导出x 的分布函数目的问题。 设w ，= 而+ 乃( f = 1 ，2 ，3 刀) ，令w = x + y ，由贝叶斯公式可知，置的后验 分布函数为： ) = i a ( w , - z 一) z ( z ) d z ( 2 一1 ) l 乃( w z ) a ( z ) a z 依次计算f ( 而) ，f 7 ( 嘞) ，f ( 毛) 。然后计算它们的平均值，即为z 的 后验分布函数。 e ( 拓) = 墨丝墨丝：墨! 竺( 2 2 ) 对f ( x ) 求导，得到x 后验密度函数： 删= 丢喜卷淼 3 ， 由( 2 3 ) 式可知，当原始数据量较大，即，2 较大时，则f ( x ) 可以逼近厂( 功。 然后设定一个阈值，使用迭代法来得到( 功，具体的方法即为： 肭= 吉喜篇老羝， 4 ， 最后当+ 1 ( 甜) 一( “) 小于预先设定的阈值时，便停止迭代。 在实际计算时，为了加快计算速度，可以把数值划分为不同的区间，属于 同一区间的数值都以相同的值替代，这样便只需计算一次即可，从而可以节省 时间，提高效率。 d a k s h ia g r a w a l 和c h a r u 瞳针对上述算法中对原始数据进行重构的过程， 提出一种期望最大化( e m ) 算法，其原理也是基于贝叶斯公式。文中证明，期望 最大化方法在扰乱后的数据上，可以得到原始数据的最大似然估计，当数据量 较大时，该算法可以得到和原始数据分布非常接近的估计。 ( 2 ) 随机响应方法：根据一种源于统计学的模型一沃纳模型，对数据随机进 行变换，并在变换后的数据上推导原始数据的取值概率，最终进行分类挖掘的 算法。 随机响应( r a n d o m iz e dr e s p o n s e ，r r ) 技术最初应用于统计学中，由 w a r n e r 【2 妇率先提出，目的是为了解决以下调查问题：为了估计人群中具有彳属 性人群的比例，需要向人群发送问卷，由于问卷中可能涉及人们的隐私问题， 因此一些被调查者可能拒绝回答或者做出与事实不符的回答。相关问题模型 ( r e l a t e d q u e s t i o nm o d e l ) 和不相关问题模型( u n r e l a t e d q u e s t i o nm o d e s ) 被 设计用来解决此类问题。 在相关问题模型中，问卷不再直接询问被调查者是否具有属性彳，取而代 之的是两个答案互为否定的相关问题。例如： 问题1 ：被调查者具有属性么。 问题2 ：被调查者不具有属性彳。 调查者首先确定一个实数0 【0 ，1 ，0 0 5 ，被调查者通过随机数发生器产 生一个随机实数， 0 ，1 】，若， 0 和口2 0 ，求解秒的范围岛se 岛，使得口 满足( 4 一群) 的方差d ( 4 一群) a 。，( 4 4 ) 的方差d ( 4 一形) 吃。 第三步：秒随机取【岛，岛】上的一个值，重新计算，= 尺毒s 。依次计算每 一对属性值对，最终得到变换后的数据d 。 由于r b t 算法是基于旋转变换的等距变换，因此，基于距离的聚类挖掘算 法，在变换后的数据集d 7 上的挖掘结果和在原始数据集d 上的挖掘结果相同。 然而，r b t 算法也存在一定的缺陷。由于r b t 算法的旋转角度p 选择范围是 根据要求的最低的隐私保护度来确定的，所以，当对隐私保护的要求较高时， 算法可能无法取得合适的旋转角度，即无法得到合适的口值；而且，r b t 算法没 有对所有的等距变换进行分析讨论。 1 4 2 0 0 6 年，张国荣，印鉴n 1 在r b t 算法的基础上，提出一种利用等距变换实 现初始数据隐私保护的改进算法i b t 。 该方法主要是对任意组合的属性值对进行等距变换，对于每一个属性值， 先随机选择一种等距变换方法进行变换，然后，再根据要求的相对隐私保护度 来确定旋转角度0 的取值范围，接着，在满足要求的取值范围内随机选取一个 旋转的角度秒，最后，根据所选择的秒值对数据进行变换。该算法由于随机选择 一种等距变换扰乱数据，使得数据在保持相似性即距离不变的情况下，实现了 数据的变换。并且确保了无法从变换后的数据中推导出原始数据，从而有效保 证了数据的隐私度，而距离不变保证了数据在变换后的相异矩阵不变，即不会 对聚类的结果产生影响。 i b t 算法因为使用相对隐私保护度，来确定变换角度的选择范围，因此，当 数据挖掘对数据集的隐私保护程度要求较高时，可以通过计算最优隐私保护度 来确定最低的隐私保护度，这样能够确保变换的过程总是可以取到合适的变换 角度。从而解决了r b t 算法中当对隐私保护的要求较高时，可能无法取得合适的 旋转角度的问题，文章对所有的等距变换进行了讨论。而在算法复杂度方面， i b t 算法的复杂度并没有增加。 2 3 3 数据集中分布的隐私保护关联规则挖掘算法 数据集中分布的隐私保护关联规则挖掘算法，按照保护的对象不同，又可 以分为保护规则的算法和保护原始数据的算法。目前大多数算法都是基于保护 规则的，因此，下面主要介绍保护规则的算法。 保护规则的提出源于数据转移。保护规则是指，确保数据挖掘者在数据中 只能挖掘出预先设定的规则，而数据拥有者想要保护或者说想要隐藏的规则不 被暴露。 举例来说，d 表示原始数据集，胄表示从数据集d 中能够挖掘出来的规则， 但是，对于规则r ，有一些规则r 是数据拥有者不希望被挖掘出来的，如何将 原始数据集d 转化成一个可以公开的数据集d ，并且保证数据挖掘者在数据集 d 上能够成功挖掘出，除了规则r 以外的规则。图2 - 1 显示了一个保护规则的 挖掘算法的模型。 对于保护规则的问题，一种方法是选定某个数据项，将其中的1 值替换为o 值，这样，便会降低所要保护规则的支持度，并且保证发布的更改后的数据库 中，被隐藏的非保护规则的支持度不受太大的影响。 后来的研究将更改敏感数据项问题扩展到敏感规则清洗。e d y a s s i li o s 和s v e r y k i o s 轧埔1 等人提出两种方法：一种方法是通过隐藏频繁项集来防止 需要保护的关联规则产生；另一种方法是通过使重要规则的置信度小于用户指 定的最低置信度，从而防止需要保护的规