已阅读5页,还剩56页未读, 继续免费阅读
(计算机应用技术专业论文)支持隐私保护的数据挖掘研究.pdf.pdf 免费下载
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
支持隐私保护的数据挖掘研究 摘要 随着信息技术的飞速发展,网络中的数据共享和交换行为出现得越来越频繁。 由于数据挖掘能从信息数据中提取有用的信息,因此它被作为分析工具而得到了 广泛应用。而同时数据挖掘带来的隐私问题已经引起了人们的关注。本文主要研 究分布式下的隐私保护数据挖掘算法。论文的主要工作如下: 第一,对隐私保护数据挖掘算法进行了概括。然后,定义了数据挖掘中隐私 的基本概念,并指出了隐私保护机制的目标。 第二,本文结合数据分布方式、数据修改方式和隐私保护技术等角度,对当 前典型的隐私保护数据挖掘算法作了一个全面的分析和介绍。 第三,本文在相关研究的基础上,将同态加密和保序加密相结合,提出了一 种新的支持隐私保护的分类算法。本算法在保证挖掘结果的前提下,解决了密文 的数学运算和数值比较问题,满足的挖掘的隐私保护需求,并且降低了算法的通 信和计算复杂度。实验结果表明:相对于同类算法,本算法是一种通信复杂度为 线性级的高效解决方案,在计算效率方面也有了较大的提高。 第四,通过改变数据垂直分布条件下聚类步骤,提出了一种基于加密技术的 聚类方法。本文将该方法应用到了k 中心聚类算法当中,实现了保护数据隐私安 全的同时,能进行有效的聚类挖掘。实验结果表明:本文算法在计算开销和通信 开销之间可以达到一个较好的平衡,与同类算法相比,该算法具有运行效率高、 计算和通信开销较小的特点,并且通过隐藏明文的分布,使所有的站点都可以得 到有力的保护,解决了站点子集隐私泄漏的问题。 关键词:隐私保护;分类挖掘;聚类挖掘;同态加密;保序加密 i i 硕士学位论文 a b s 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 ,m o r ea n dm o r ea c t i v i t i e s o nd a t as h a r i n ga n de x c h a n 百n ga r ec o m i n gf o r t hi nt h en e t w o r k d a t am i n i n g ,w h i c h i s c a p a b l eo fa c q u i r i n gi n t e r e s t i n g k n o w le d g ef r o mr o u g hd a t a , h a sb e c o m ea n e x t e n s i v e l ya p p l i e da n a l y s i sm e t h o d c 0 n c e r n s i b o u ti n f 0 r m a t i o n a lp r i v a c yh a v e e m e r g e dg 】o b a l l y t b e r e f o r e ,p r j v a c yh a sb e c o m et h ef o c u so fm a n yd a t am i n i n g r e s e a r c h e s t h ef o c u so ft h i sp 印e ri sp r i v a c y p r e s e r v i n gd a t am i n i n go v e rd i s t r i b u t e d d a t a f i r s to fa 1 1 ,t h i sp a p e rp r o v i d e sa no v e n r i e wo fd a t am i n i n g t h e ni td e f i n e st h e n o t i o no fp r i v a c yi nd a t am i n i n ga l g o r i t h m sa n dp o i n t s o u tt h eo b je c t i v eo f p r i v a c y p r e s e r v i n gs c h e m e s e c o n d l y ,i ti n t r o d u c e sa n da n a l y z e ss o m et y p i c a lp r i v a c y p r e s e r 、r i n ga l g o r i t h m s f r o md a t ad i s t r i b u t i o n , d a t am o d i f i c a t i o na n d p r i v a c y - p r e s e r v i n g t e c h n o l o g y d i m e n s i o n s t h i r d l y ,b yc o m b i n i n gh o m o m o r p h i ce n c r y p t i o n w i t ho r d e r p r e s e r v l n g e n c r y p t i o n ,t h i sp a p e rp r o p o s e san e wc l a s s i f i c a t i o na l g o r i t h mb a s e do nt h e 1 a t e s t r e s e a r c h o nt h ep r e m i s eo fg a i n i n gt h ev a l i dr e s u l t s ,t h ea l g o r i t h mu t i l i z e s t h e a t t r i b u t i o n s :a d d i t i o no p e r a t i o na n dc o m p a r i s o no p e r a t i o no nc i p h e r t e x t 1 tr e d u c e st h e c o m m u n i c a t i o na n dc o m p u t a t i o nc o m p l e x i t y t h ee x p e r i m e n t a lr e s u l t ss h o wt h a tt h e a l g o r i t h mi sa ne 伍c i e n ts 0 1 u t i o nf o rl i n e a rc o m m u n i c a t i o nc o m p l e x i t y ,a n dh a sa g o o dp e r f o r m a n c ei nt e r m so fp r i v a c y ,a c c u r a c ya n d c a l c u l a t i o n f o u r t h l y ,an o v e lm e t h o do fp r i v a c y - p r e s e r v i n gc l u s t e r i n gb a s e d o nc r y p t o g r a p h y t e c h n i q u ei sd e v e l o p e dt h r o u g hc h a n g i n g t h es t e p so fc l u s t e r i n g o nv e r t i c a l l y p a r t i t i o n e dd a t a t h e nan e w k m e d o i d sc l u s t e r i n gb a s e do nt h i sn l e t h o di sp r o p o s e d t h i sp a p e ra n a l y z e st h ea l g o r i t h mi nt e r m so fc o r r e c t n e s s ,p r l v a c y ;c o m p u t a t l o n c o m p l e x i t ya n dc o m m u n i c a t i o nc o m p l e x i t y 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 e a l g o r i t h mc a na c h i e v eab e t t e rt r a d e o f f b e t w e e nc o m p u t a t i o nc o s ta n dc o m m u n i c a t i o n c o s t ,a n dh a ss u b s t a n t i a la d v a n t a g eo v e ro t h e rr e p r e s e n t a t i v ea l g o r i t h m si nc a l c u l a t i o n a n dc o m m u n i c a t i o no v e r h e a d ,a c c u r a c ya n dp r i v a c y t h er e s u l t ss h o wt h i sa l g o r i t h m i ss e c u r ef b ra l ls i t e sb yh i d i n gt h ep l a i n t e x td i s t r i b u t i o n i i i 支持隐私保护的数据挖掘研究 k e yw o r d s :p r i v a c yp r e s e r v i n g ;c 1 a s s i f i c a t i o n ;c l u s t e r i n g ;h o m o m o 印h i ce n c r y p t i o n ; o r d e rp r e s e r v i n ge n c r y p t i o ns c h e m e l v 硕十学位论文 插图索引 图3 1 垂直分布下的k 一最近邻算法2 4 图3 2 分类步骤描述图l 2 6 图3 3 分类步骤描述图2 2 6 图3 4 ,z 变化对通信开销的分析2 9 图3 5 ,变化对通信开销影响分析3 0 图3 6 厂接近栉时算法通信开销分析3 0 图4 1 聚类划分步骤描述图1 3 6 图4 2 聚类划分步骤描述图2 3 7 图4 3 加密效果图一4 0 图4 4 刀变化下聚类算法的通信开销分析4 l 图4 5 后变化下聚类算法的通信开销分析4 2 图4 6 ,变化下聚类算法的通信开销分析4 2 图4 7 聚类算法的计算开销分析_ 4 3 图4 8 原始数据分布图4 3 图4 9 同态加密后数据分布图。4 4 图4 1 0 保序加密分布图4 5 图4 1 1 改变分布的保序加密分布图4 5 l 支持隐私保护的数据挖掘研究 附表索引 表3 1 隐私保护k 一最近邻算法计算复杂度对比2 7 表3 2k 一最近邻计算开销分析3 1 表4 1 隐私保护k 一中心算法计算复杂度分析3 9 表4 2 聚类结果统计4 0 v l l l 湖南大学 学位论文原创性声明 本人郑重声明:所呈交的论文是本人在导师的指导下独立进行研究所取 得的研究成果。除了文中特别加以标注引用的内容外,本论文不包含任何 其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡献 的个人和集体,均已在文中以明确方式标明。本人完全意识到本声明的法 律后果由本人承担。 作者签名:裔够 日期: d 7 年歹月j 驴日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定,同意学 校保留并向国家有关部门或机构送交论文的复印件和电子版,允许论文被 查阅和借阅。本人授权湖南大学可以将本学位论文的全部或部分内容编入 有关数据库进行检索,可以采用影印、缩印或扫描等复制手段保存和汇编 本学位论文。 本学位论文属于 l 、保密口,在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“”) 作者签名:智汤 导师签名:夕旁仰 日期: 汐夕年 箩月力日 日期: p 少年 f 月? p 日 硕十学位论文 1 1 研究背景及意义 第l 章绪论 当今的时代是一个无可争议的信息时代,在信息化技术高速发展的今天,世 间很多的东西和行为都可以被信息化。电话通讯和信用卡电子交易会被记录;商 店的电子门锁可以跟踪顾客的进出情况;常用的消费购物卡会记录我们购买的东 西,甚至移动电话也开始可以准确定位电话所在地。人们的日常生活被搜集的数 据多得出乎想象。并且,随着收发电子邮件、网上购物、新闻和娱乐互联网的盛 行,几乎没有什么日常生活不被记录下来。而此时数据挖掘的出现为人们提供了 个去粗取精、去伪存真,将数据转换成知识的技术。自2 0 世纪8 0 年代诞生以来, 数据挖掘一直是数据库研究、开发和应用最活跃的分支之一,并以前所未有的速 度迅猛发展。数据挖掘是门新兴交叉性学科,融合了人工智能、数据库技术、 模式识别、统计学和数据可视化等多个领域的理论和技术。它通过仔细分析大量 数据来揭示有意义的新的关系、趋势和模式,不论在研究领域还是商业应用,数 据挖掘都取得了可喜的成果。 但与此同时,数据挖掘也面临着许多问题的挑战。其中,数据挖掘中的个人 隐私与信息安全问题尤其得到关注。现实生活中,数据信息泄漏的例子己经比比 皆是,如医院可以将患者的姓名、电话号码等个人信息泄漏给药店或保健公司, 车修公司将车主登记信息交给各类保险公司,婚姻登记处将新人信息出售给婚宴 筹办中介等等。这种误用、滥用数据可能导致用户敏感信息泄漏,越来越多的人 们表示担忧。这种担忧又导致了人们拒绝提供真实的信息或则提供虚假的信息。 显然易见,这影响了人们的正常生活,然而数据挖掘的出现使该问题变得比以往 任何时候都严重。这是因为在数据挖掘出现之前,任何有推理攻击企图的人必须 依靠个人的经验和知识来分析得到的数据,并从中找到感兴趣的东西。但是现在 的数据库用户有了功能强大的数据挖掘工具,使得用户的隐私保护变得更加复杂 和难以确定。数据挖掘可以用来对海量数据进行处理,从中抽取和发现感兴趣知 识的有效手段,但同时,数据挖掘也完全可以被攻击者用来对数据库进行推理攻 击和聚类攻击、偷取数据、破环系统的安全。 因此如何在保护数据隐私的前提下,进行数据挖掘,已经成为当前数据挖掘 研究中一个极为迫切的问题。我们可以想象一下如下的情景,例如:一个医院为 了研究的目的需要与其他机构共享一些病人的数据,而病人的记录在此过程中就 有可能被其他人或组织盗用,这就侵犯了病人的隐私。又如,两个或更多的公司 都有一个记录了顾客购买活动的数据库,为了他们的共同利益,这些公司决定合 支持隐私保护的数据挖掘研究 作在他们的数据库中进行关联规则挖掘。然而,其中的一些公司不想公开他们数 据库中的一些战略性的模式给其他的公司,他们想通过某种技术来使得战略性的 模式隐藏而以另外的模式与其他公司分享。因此必须实现一种能保护战略性模式 的同时与别人共享数据的技术。 综上所述可以得出,研究保护隐私的方法,防止数据被误用,找出更多保护 数据隐私和安全的解决方案己成为数据挖掘研究中一个重要的研究领域。在19 9 5 年召开的第一届数据挖掘会议上,隐私保护的数据挖掘就成为了一个专门的研究 主题,将隐私保护的数据挖掘作为未来的研究重点之一。自此以后,隐私保护的 数据挖掘越来越得到人们的重视,迅速成为近年来数据挖掘领域研究的热点之一。 各种新方法和新技术层出不穷,在国外,由于对隐私问题的重视,一些相关的论 文相继得到发表。到今天,越来越多的研究人员投入了关于隐私保护的研究中, 已经发表了大量的文章。然而,在国内,相关的研究才刚刚起步,系统且深入的 研究较少。所以,对数据挖掘的隐私保护技术进行研究有着重要的意义。 1 2 研究内容与章节安排 本文的研究的对象是分布式数据挖掘的隐私保护,这里的分布式主要是指在 数据垂直分布的环境下,以协同挖掘为主要保护对象的隐私保护算法及隐私保护 机制。 本文的章节安排如下。 第一章,对本文的研究背景及意义进行了介绍。 第二章,首先介绍数据挖掘的基本概念,然后回顾了数据挖掘中隐私保护的 概念、研究内容、所采用的主要技术和发展,并对现有的一些主流隐私保护数据 挖掘算法作了一个深入的介绍和分析,比较其原理、优缺点及其适用范围等一些 相关问题。 第三章,研究了分布式下的分类隐私保护挖掘方法,指出相关研究的缺点和 不足,并提出相应的解决策略,构建并实施了支持隐私保护的分类挖掘算法及通 过仿真实验对比分析了同类解决方法的效率和效果。 第四章,为在第三章的基础上,将基于加密技术的隐私保护方法与分布式下 的聚类挖掘算法的结合进行了研究,提出了相应的解决方案,并且从算法的隐私 安全和效率等角度进行了深入分析,最后用实验进行了验证。 最后,对本文进行总结,并对未来发展方向进行展望。 2 硕十学位论文 第2 章隐私保护挖掘算法综述 2 1 数据挖掘基本介绍 我们处在信息时代,计算机处理能力、存储技术以及互联网络的发展极大地 提高了信息的数字化处理程度,这些日益增多的信息就如一个无穷的宝藏一样, 其数据背后隐藏着许多比钻石还珍贵的知识,人们希望通过对积累的数据进行更 高层次的分析,找出数据内部一些潜在的关系和规则,将数据变为真正的财富。 如电信公司期望能够从大量的通信记录中找出优质客户的行为特征和消费习惯, 以帮助寻找潜在客户、刺激客户消费并创造更多的交叉销售的机会。再如大型超 市的市场部门,如何通过分析客户的购物记录,来帮助调整货物摆放、指导市场 营销和礼品的发放。这样的例子数不胜数,涵盖了社会的方方面面。但如何实现 这些商业分析行为是他们面临的一个重大难题。这些不断提出的新需求都迫使人 们去寻找新的、更为有效的数据分析手段来对各种数据宝藏进行有效的挖掘以发 挥其应用潜能。 人类的发展是一个永无止境的不断自我完善的过程。数据挖掘和知识发现正 是在这样的需求背景下应运而生了,它的出现为海量数据转化为有用的信息和知 识提供了手段。数据挖掘是通过仔细分析大量数据来揭示有意义的新的关系、趋 势和模式的过程。其出现于2 0 世纪8 0 年代后期,是数据库研究中一个很有应用 价值的新领域,是一门汇集了机器学习、模式识别、数据库、统计学、人工智能 以及管理信息系统等各学科的研究成果的新兴综合学科。多学科的相互交融和相 互促进,使得这一学科得以蓬勃发展,而且己初具规模。纵观数据挖掘的发展历 程可以发现,它的发展是一个逐渐演变的过程,首先是以电子数据处理的形式出 现的,当时人们就试图通过某些方法来实现自动决策支持,因此机器学习成为当 时人们关心的焦点。而后,随着神经网络技术的形成和发展,人们的注意力转向 知识工程,知识工程不同于机器学习那样给计算机输入范例,让它生成出规则, 而是直接给计算机输入己被代码化的规则,计算机通过使用这些规则来解决某些 问题。专家系统就是这种方法所得到的成果,但它有投资大、效果不甚理想等不 足。二十世纪八十年代人们又在新的神经网络理论的指导下,重新回到机器学习 的方法上,并将其成果应用于处理大型商业数据库。人们普遍定义知识发现是从 数据库中发现知识的全部过程,而数据挖掘是全部过程的一个关键的步骤,是指 应用特定算法从数据中提取模式。知识发现中的其它步骤则是用来保证从数据中 挖掘得到的知识是有用的知识,否则,盲目挖掘容易导致所发现的模式是无意义 的。当数据挖掘成为普及的涵盖面更广的术语时,我们就不必关心数据挖掘与k d d 3 支持隐私保护的数据挖掘研究 之间的明确界线。事实上,在现今文献中的大多数场合,这两个术语的使用是 不加区别的,本文也将不加区分地使用两者。 数据挖掘作为知识发现的过程,一般由如下几个步骤完成【2 j 。 1 数据清理( 消除噪声或不一致数据) 2 数据集成( 各种数据源可以组合在起) 3 数据选择( 从数据库中检索与分析任务相关的数据) 4 数据变换( 数据变换或统一成适合挖掘的形式,如通过汇总或聚集操作) 5 数据挖掘( 使用智能方法提起数据模式) 6 模式评估( 根据某种兴趣度度量,识别表示知识的真正有趣的模式) 7 知识表示( 使用可视化和知识表示技术,向用户提供挖掘的知识) 由此可知,知识发现的过程可以划分为由三个主要的阶段组成:数据准备、 数据挖掘、以及结果的解释评估。知识的发现可以描述为这三个阶段的反复过程, 如图2 1 所示,数据准备包含了上述四个子步骤:数据清理、数据集成、数据选 择和数据变换。数据选取的目的是确定发现任务的操作对象:即目标数据,他是 根据用户的需要从原始数据库中抽取的一组数据。数据挖掘可能涉及到内部多个 数据源,还可能需要一些外部的数据,这就需要将多个数据源中的数据结合起来 存放在一个一致的数据存储( 如数据仓库) ,以便于数据挖掘操作,这个过程即数 据集成。数据清理一般可能包括消除噪声、推导计算缺值数据、消除重复记录、 完成数据类型转换( 如把连续值数据转换为离散值数据,以便于符号归纳,或是把 离散值数据转换为连续值数据,以便于神经网络归纳) 等。当数据挖掘的对象是数 据仓库是,一般说来,数据预处理己经在生成数据仓库是完成了。数据变换的组 要目的是将数据转换成适合数据挖掘需要的形式,它可能会涉及到如下内容:平 滑、聚集、规范化、属性构造。数据挖掘阶段首先要确定挖掘的任务或目的是什 么,如数据总结、分类、聚类、关联规则发现或序列模式发现等。确定了挖掘任 务后,就要决定使用什么样的挖掘算法。同样的任务可以选用不同的算法来实现。 选择实现算法又两个考虑因素:一是不同的数据有不同的特点,因此需要用与之 相关的算法来挖掘:二是用户或实际运行系统的要求,有的用户可能希望获取描 述型的、容易理解的知识( 采用规则表示的挖掘算法显然要好于神经网络之类的方 法) ,而有的用户或系统的目的是获取预测准确度尽可能高的预测型知识。完成了 上述准备工作后,就可以实施数据挖掘操作了。具体的数据挖掘方法将在后面的 章节中作较为详细的论述。需要指出的是,尽管数据挖掘算法是k d d 的核心, 也是目前研究人员主要努力的方向,但要获得好的挖掘效果,必须对各种挖掘算 法的要求或前提假设有充分的理解。结果解释评估是指将挖掘出的结果以一种易 于理解的形式表示出来,并进行解释和评价。具体包括消除无关的、多余的模式, 过滤出要呈现给用户的信息:利用可视化技术将有意义的模式以图形或逻辑可视 4 硕士学位论文 化的形式表示,转化为用户可以理解的语言。一个成功的数据挖掘的应用应能将 原始数据转换为更简洁、更易理解、可明确定义关系的形式。此外还包括分析解 决当前发现的结果与以前知识的潜在冲突,以及利用统计方法来对模式进行评价, 决定是否需要重复或则修改以前的操作,以得到最优、最适合的模式。 根据发现的知识种类可分为:关联规则发现、分类或预测模型知识发现、数 据聚类、序列模式发现、依赖关系或依赖模型发现、异常和趋势发现等。其主要 方法如下: 关联规则挖掘是发现大量数据中项集之间有价值关联的过程】。这些关系是 未知的和被隐藏的,也就是说不能通过数据库的逻辑操作( 如:表的联接) 或统计的 方法得出。关联规则挖掘问题就是产生支持度和置信度分别大于用户给定的最小 支持度和最小置信度的关联规则。支持度表示规则的频繁性;置信度表示项集之 间的关联,它们分别反映规则的有用性和确定性。关联规则采掘过程可以分解为 以下两个步骤:找出所有的频繁项目集及其支持度;根据找到的频繁项目集导出 所有的置信度大于或等于用户指定的最小置信度的关联规则。关联规则的最经典 算法是a p r i o r i 算法是由a g r w a l 等人提出来的【3 】。a p r i o r i 算法通过称作逐层搜索的 迭代方法来找出所有的频繁项目集,k 项集用于探索( k + 1 ) 项集。厶代表频繁k 项集,为找厶,通过厶一与自己连接产生候选k 项集的集合。该算法使用a p r i o r i 性质:频繁项集的所有非空子集都必须也是频繁的。该性质属于一种特殊的分类, 称作反单调。因此,第k 次迭代时的候选项目集可由第k 1 次迭代时找出的所有频 繁k 1 项目集之间通过连接运算得到,并由称之为剪枝步骤得到最后得频繁项集。 而此后很多学者又对算法的效率进行了进一步的改进。 分类是一种有指导的学习方法,它反映同类事物共同性质的特征型知识和不 同事物之间的差异型特征知识【1 】。它分为两步:第一步建立一个模型,描述预定 的数据类和概念集;第二步用模型进行分类。对于分类规则的挖掘通常有以下几 种方法:决策树方法、贝叶斯方法、人工神经网络方法、粗糙集方法和遗传算法。 朴素贝叶斯方法直接利用贝叶斯公式进行预测,把从训练样本中计算出的各个属 性值和类别频率比作为先验概率,并假定各个属性之间是独立的,利用b a y e s 公式 和相应的概率公式计算出要预测实例的对各类别的条件概率值。选取概率值最大 的类别作为预测值。此方法简单易行并且具有较好的精度。q u i n l a n 提出的i d 3 算 法是最具影响力的一种数据挖掘决策树分类方法,它是一种有指导的学习方法。 该方法先根据训练样本数据集形成决策树。如果该树不能对所有对象给出正确的 分类,那么选择一些其他的训练子集加入到原来的训练集中,重复该过程一直到 形成正确的决策集。最终得到一棵树,其叶节点是类名,中间节点是带有分支的 属性,该分支对应该属性的某一可能值【| 7 1 。 聚类是一个将物理或则抽象对象的集合分组组成由类似的对象组成的多个类 5 支持隐私保护的数据挖掘研究 的过程。由聚类所生成的簇是一组数据对象的集合,这些对象与同一个簇中的对 象彼此相似,与其它簇中的对象相异,在许多应用中,一个簇中的数据对象可以 被做为一个整体来对待。相似或不相似的度量是基于数据对象描述的取值来确定 的【1 。通常就是利用对象与对象之间的距离来进行描述的。聚类分析就是从给定 的数据集中搜索数据对象之间所存在的有价值联系。而在许多应用中,一个聚类 中所有对象常常被当作一个对象来进行处理或分析。聚类的方法有很多,如k 均 值和k 中心点是比较常用的聚类方法。 预测是根据时间序列型数据,由历史的和当前的数据去推断未来的数据【1 】。 它与分类有类似:。分类是预测分类标号,而预测建立连续预测模型。目前时间序 列预测方法有经典的统计方法、神经网络和机器学习等。 2 2 隐私的概念 任何事情都有其两面性,数据挖掘领域也不例外,在挖掘数据产生财富的同 时,随之产生的就是隐私泄露的问题。在6 0 年代的美国,一名教授发表了关于隐 私的文章,提出了“信息隐私权”的概念,以应对信息时代隐私权所受到的冲击。 关于隐私的概念o l i v e i r a 提出他的观点,隐私可以被分成两类,种是个人隐私 ( i n d i v i d u a ip r i v a c y ) ,另一种是集体隐私( c o r p o r a t ep r i v a c y ) 阐。 ( 1 ) 个体的隐私 数据隐私性的首要目的就是要保护个人身份信息。一般来说,如果信息可以 直接或者间接地通过连接查询追溯到某个人,那么这类就是可以定位个人身份的 信息。那么当此类个人数据被用于挖掘工作的时候,关于个体的属性值就是有隐 私性要求的并且须要加以保护使之不被披露;挖掘者可以从全局模型,而不是从 特定、具体的个体特征来获取有用的知识。具体来说,比如一个人的姓名、身份、 肖像、声音等,由于其直接涉及个人领域的第一层次,可谓是“直接 的个人属 性,这些属于个人属性的隐私,为隐私权保护的首要对象,又如个人资料的隐私 权,它包括当个人属性被抽象成文字的描述或记录,如个人的消费习惯、病历、 宗教信仰、财务资料、工作、犯罪前科等记录,若其涉及的客体为一个人,则这 种资料即含有高度的个人特性而常能辨识该个人的本体,可以说“间接”的个人 属性也应以隐私权加以保护。还有一些特殊的隐私权,如个人的思想与感情,原 本存于内心之中,别人不可能知道,当与外界通过电子通信媒介如网络、电子邮 件沟通时,即充分暴露于他人的窥探之下,所以这些内容也应加以保护,以保护 个人人格的完整发展。 ( 2 ) 集体的隐私 在数据挖掘工作中,仅仅保护个人数据还不够,有时候我们需要防止代表一 个团体各种行为的敏感知识被窃取。这么做的目的类似于保护统计数据库的方法: 6 硕- 1 二学位论文 通过安全性控制机制来提供关于群体的总计信息,并同时保护个人的机密信息。 比如某个公司希望聘请某个财务公司对本公司的财务情况进行稽查。当然,财务 来往记录被这些部门严格有效的管理着。现在为了研究,调查把数据收集在一起, 并许诺提供有效的控制。但是如果万一数据脱离这些控制,那么一个人的全部财 务来往记录将全部暴露,这将严重损害集体的隐私。另一个保护集体隐私的重要 目的在于防止有关战略决策的关键模式被预期之外的对象获取。虽然这种应用对 于消费者和商业组织来说都有好处,但是当组织在某个合作项目中共享这类数据 时,就不光要保证用户个人身份信息的隐私性了,还要保证其自身的战略模式不 被泄露。使用有关战略模式的知识指导商业活动,被认为是可以获得竞争优势的, 因此此类信息也应该得到保护。 2 3 隐私保护的分类 2 0 0 4 年v a s s i l i o ss v e r y k o i s 等从以下5 个角度提出了数据挖掘中隐私保护算法 的分类【9 1 。 1 数据分布方式 根据数据的分布情况,隐私保护技术可以分为针对集中式数据的隐私保护技 术和针对分布式数据的隐私保护技术。分布式的隐私保护技术又分为数据水平分 布和数据垂直分布的隐私保护技术。数据的水平分布主要是指数据按记录分布于 多个机构或组织;数据的垂直分布主要是指数据按属性分布于多个机构或组织。 2 数据修改方法 为确保原始数据库中的隐私信息不被泄露,将数据库中某些敏感信息做一定 的修改。常用的方法主要有: ( 1 ) 值替代方法,按不可倒推的方法用一个新的值替代原有的值;或者用一 个符号如“? ”替代一个已存在的值,以保护敏感数据和规则; ( 2 ) 聚集方法,就是将几个值进行合并或抽象而成为一个粗糙集; ( 3 ) 交换方法,就是单个记录问值的交换; ( 4 ) 取样方法,就是抽样,指是用于挖掘的数据只是总样本中的一个样本。 3 数据挖掘算法 目前数据隐藏技术都是在每一个数据挖掘算法中单独进行考虑的。例如:决 策树算法、关联规则算法、粗糙集以及聚类等数据挖掘算法。 4 隐私保护的对象 主要是指针对原始数据或其隐含的规则的隐藏。以规则的形式隐藏聚集数据 的层次比隐藏原始数据要高。通过保护敏感规则,同样可以保护重要的原始数据。 6 隐私保护技术 指修改原始数据所采用的技术。修改能使隐私在不受危害的情况下获得较高 7 支持隐私保护的数据挖掘研究 的技术实用性,有效减少有用信息的丢失。隐私保持技术主要分三类: ( 1 ) 基于启发式的隐私保持技术:修改特定值来减少挖掘效果的偏离。 ( 2 ) 基于信息安全理论的隐私保持技术:利用信息安全领域的方法来进行数据 加密,典型的有多方安全计算方法和加密方法。 ( 3 ) 基于重构的隐私保持技术:将数据进行变换后,再进行重构原始分布,如 随机扰动技术。 2 4 集中式隐私保护挖掘 集中式隐私保护挖掘技术是针对数据集中这种情况下提出的种针对型的隐 私保护技术,它可以对个人隐私和集体隐私都能起到保护的作用。很多学者都提 出相关的解决办法,根据本文2 3 节可知,如果按照技术划分,又大约可以分为2 种,一种称之为启发式隐私保护挖掘。在更改和净化选择的数据是一个n p h a r d 问题的前提下,启发式的研究可用于解决这类复杂的问题。如适应性改变,它仅 仅改变挑选的属性值而不是全部。这样,可以最小化实用性损失。人们正是利用 启发式方法来解决挖掘算法中的复杂度的问题,将其适用到如分类、关联规则和 聚类等数据挖掘技术当中,而启发式的隐私保护挖掘自然而然也就是对此而展开 的一种隐私保护方法,但由于此种方法应用暂时还不是很广,且和本文讨论的隐 私保护方法没有太多关联,故不做深入介绍。而另外一种是称之为基于扰动技术 隐私保护挖掘,本文将在下面的内容针对这种隐私保护方法做一个系统的概述。 集中式隐私保护的主要思想是数据预处理针对数据库系统中的数值进行变换 处理的方法,将变换后的数据提供给挖掘者进行数据挖掘。对转换方法的要求是: 从变换后的数据中不能推算出初始数据,即保证隐私度;同时,转换方法只改变 单个属性值,不改变数据整体的变化趋势,从而确保挖掘结果的正确性。由于数 据挖掘在很多时候并不需要访问详细的明细数据,只需对一些汇总数据或则数据 分布进行分析,因此通过数据变化的方法来实现隐私保护正是根据挖掘算法的这 一特性而展开的。数据扰乱就是一种解决数据挖掘中个人隐私保护难题的常用方 法:通过数据记录之间交换数据从而保护了可靠的统计结果,但同时隐藏了真实 的数据值。扰乱技术的另一个主要方法是随机扰动:为数据增加“噪声”以保护 真实数据不被发现。通过对数据的随机化处理,数据不在反映真实的世界,从而 使得数据无法被滥用而侵犯个人的隐私。当然扰乱技术的关键在于如何从扰乱数 据中获得有效的数据挖掘结果。因此,扰动技术的另一个关键在于数据的重构, 如果数据不能有效的代表原始数掘,那么之前的扰乱不仅没有意义,而且还会破 坏数据挖掘结果的精度,从而造成更大的损失。 a g r a w a l 和s r i k a n t 根据这一特性提出了基于扰动技术的数据挖掘方法。他们 对数据的保护正是通过对原始数据加入些随机噪声数据,将真实的数据打乱, 硕十学位论文 用那些随机干扰后的新数据来取代原始数据,但同时确保这些被噪声处理后的数 据能够被有效地重构出来【l o 】。 原理概述如下,把门个原始值z ,工,看作是以个具有相同分布的独立随机 变量x ,x 护,以实例,其中随机变量x ,x ,咒同随机变量x 有相同的分布,其 分布函数为只。为了不泄露真实的数据置,对于每一个数据五加入一个随机参数 乃,即而+ y ,屯+ 乃,吒+ 只。其中已知随机参数】;:和它的分布函数e 。而后再在 数据挖掘前根据已知的c 和五+ 咒来重构t 的数据分布,即估算e 。根据b a y e s 定律的循环算法,定义墨的分布密度为正,定义,:的分布密度为f ,算法公式如 下: 肌,= 昙喜卷揣 亿1 , 而后作者结合i d 3 决策树算法进行了研究,利用扰动技术实现了支持隐私保 护的决策树挖掘算法。 其后,a g r a w a l 和a g g a r w a l 利用期望最大化算法提出了一个改进的基于贝叶斯 的重构方法。它更有效地实现了分布重构,最大可能的使重构分布接近于原始数 据的分布,降低了信息丢失的水平。同时也提出了一个很好的隐私定义和测量隐 私的方法。并证明,在扰乱后的数据集上,期望最大化算法可以得到原始分布的 极大似然估计,且当可获取的数据量足够大的时候,它给出了原始分布的强估计 【1 1 】 o 以上考虑的都是连续型数据,对于布尔型数据,r i z v i 等人提出了对于二进制 数据与分类数据的重构技术【12 1 ,其后e v 6 m i e v s k i 利用随机化技术对二进制数据和 分类数据进行修改【”】,实现了既保证数据的使用率又保护隐私的目的。其主要方 法是,将原始数据集构造成2 维的布尔稀疏矩阵数据模型,利用简单概率方法改变 数据的原始值,使得项目值以概率p 保持不变,以1 - p 的概率取反。若为项目从1 变成o 则相当于删除项目,反而则为添加噪声项目,实质是对数据集中的项目以一 定的概率进行增删或保持不变,从而对原始数据集的信息进行了保护。由于发现 关联规则必须先获得频繁项目集,因此须对项目集的支持度进行重构,估算项目 扰动前的支持度,从而发现频繁项目集。由于研究的是基于布尔形数据的关联规 则挖掘a p r i o r 算法,因此扰动的对象是单个项目,根据关联规则的计算特点,其 采取的是逐层重构项目的支持度。此后,p o l a t 等人则提出了应用在协同过滤技术 的随机扰乱方法,也能够很好的保护用户的隐私,满足隐私政策的要求。实验已 经证明,通过挖掘应用了随机化扰乱技术后的数据集得到的结果和挖掘原始数据 集精确接近【14 1 。近几年,一些学者提出了称之为随机投影的数据扰乱方法,它使 得算法的开销更小,精度更高【】5 1 。 9 支持隐私保护的数据挖掘研究 当然,随机扰乱技术也有些不足,这是因为当对干扰后的数据进行分布重 构时,其重构的数据分布接近与原始数据分布,这仍会泄露隐私。下面是个关 于电信公司客户的年龄扰乱的例子。通过分析平时消费者的消费特征可以得知, 一般订购某类产品的消费者的年龄的分布是呈明显区间特征的,例如大部分消费 者都是2 0 岁以下。假如大家都知道选择区间 - 18 ,18 增加噪声随机化数据。虽然 重构的分布不会清楚的告诉我们任何个体的年龄,但是假如我们获取了一份数据 年龄在2 岁左右,且订购数量密集的分布图,我们可以从此推断出这个年龄段所 代表的消费人群,即获取了数据背后的隐私信息。通过上面例子可以发现,通过 分析,即便是扰动的数据仍有可能隐私被泄露。k a r g u p t a 等人正式分析了随机化 技术的安全性,并证明了在很多情况下,随机化对隐私的保护是有限的【l6 1 。而 e v n m i e v s k i 等人则提出一种隐私裂口的定义,并提出一种称为防止隐私裂口的方 法,使得在使用随机化技术保护数据挖掘中的隐私时能够防止隐私的破裂【1 7 】。 2 5 分布式隐私保护挖掘 除了集中式隐私保护挖掘,隐私保护的数据挖掘还与另外一个研究领域:分 布式数据挖掘( d d m ) 相关联,称之为分布式隐私保护挖掘( p d d m ) 。分布式环境下 考虑隐私保护的数据挖掘方法,按照所应用的数据分布形式可以分为基于水平分 布和基于垂直分布的两种。具体来说,水平分布就是指数据库中的数据按记录划 分在不同的站点,而垂直数据分布表示数据库中的数据按照其记录属性划分并存 储于不同站点。 从上述可知,分布式数据挖掘就是使用分布式计算,从分布式数据库中发现 知识的过程。一个好的分布式数据挖掘算法在分布式环境下进行数据分析时,应 该具有适中的数据通信开销。典型的分布式数据挖掘算法一般都分为两个步骤: 首先,进行局部数据分析得到局部的数据模型。然后,在全局范围内根据不同站 点的局部模型得到全局模型。尽管分布式数据挖掘在一定程度上保护了局部数据 的隐私,但是由局部模型生成的全局模型中仍然会包含敏感信息,而这些信息未 受到保护。所以分布式隐私保护挖掘关注于对信息隐私的保护,进行挖掘的前提 条件就是不能泄漏任何敏感信息。同理,根据数据挖掘的分类,那么分稚式下的 隐私保护挖掘算法也被分为二种:水平分布隐私保护数据挖掘,垂直分布隐私保 护数据挖掘。以下将针对这两种的展开讨论。 2 5 1 水平分布下的隐私保护挖掘 关于这两种不同分布下的挖掘隐私保护,很多学者都提出相关的解决办法, 根据本文2 3 节可知,如果按照技术实现,又大约可以分为2 种,一种是利用安全 多方计算实现的隐私保护挖掘,一种为利用密码体系来构建的隐私保护挖掘体系。 1 0 硕士学位论文 下文将分别对这2 种主流的隐私保护技术,针对水平分布和垂直分布分别进行一个 概括性的介绍。 网络在自身飞速发展的同时也促进了共同计算的前进,共同计算带来的利益 越来越明显。在很多情况下,人们需要相互合作才能完成计算任务,最终的计算 结果是在各自的数据输入基础上得到的。这些共同计算可能是在彼此信任的合作 者之间进行的,也有可能在相互不完全信任的合作者之间,还有可能在相互完全 不信任的竞争者之间发生。人们不仅关心自己数据信息的保密性,同时也保证不 会侵犯别人的数据隐私。安全多方计算正是针对这一问题而出现的。安全多方计 算协议要解决的问题可以描述如下:一组参与者希望共同计算某个约定的函数, 每个参与者提供函数的一个输入,出于安全考虑,要求参与者提供的输入对其他 人保密。如果存在安全可信第三方( 即称其为p p t ) ,则安全多方协议所要解决的问 题可以轻易地得到解决:只需各参与者将各自的输入交给p p t ,由p p t 计算出函数 值,再将函数值公布给其它参与者。但现实中很难找到这样的p p t ,从而安全多 方计算协议的研究应运而生,目前安全多方计算已得到许多学者的研究,其在密 码学上的地位也日益重要,它是电子选举、电子拍卖等密码学协议的基础。y a o 于19 8 2 年最早提出了两方安全计算协议【l 引。随着安全多方计算的研究发展,一系 列特殊的安全多方计算问题被提出。特别是在考虑隐私的共同计算方面的研究, 安全多方计算在这些特殊计算领域得到了很好的应用。 将安全多方理论和相关密码协议应用到隐私保护的数据挖掘中首先由l i n d e l l 和p i n k a s l 等人提出,针对两个水平分布数据的分类,他们利用密码工具构建了i d 3 决策树,并且在协议中保证了零知识泄露【1 引。i d 3 决策树算法的关键是要寻找最 小化条件熵的属性,而对于两方情形而言,条件熵的计算可以看作下述表达式的 和:心乜) 龇嘲。文献
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 2026年电动车用品行业以旧换新市场分析报告
- 2026年教育信息化行业报告:市场潜力与技术创新
- 2026年网络设备性能优化报告
- 2026年物流行业供应链优化与采购效率提升报告
- 2026年环保行业市场存量分析与用户生命周期价值研究报告
- 2026年弱电系统集成行业市场调研报告
- 2026年互联网广告行业监管报告及风险防范措施
- 2026年航空航天行业危机应对策略分析
- 2026年行业图书市场深度分析与未来发展趋势报告
- 《夏日绝句》李清照-2
- 2025成都农业科技职业学院教师招聘考试题目及答案
- 2025年棉花加工辅助工三级安全教育(班组级)考核试卷及答案
- 精神科药物依从性管理
- 中小学以体育强化为核心落实“健康第一”教育理念实施方案
- 间羟胺药物课件
- 产品经理年中述职报告课件
- 整县屋顶分布式光伏项目绿色施工方案
- GB/T 4337-2025金属材料疲劳试验旋转弯曲方法
- 输变电工程工程量清单计价规范宣贯材料
- 手术室精益管理汇报
- (重点)水利安全员B证近年考试真题题库-含答案
评论
0/150
提交评论