（计算机软件与理论专业论文）基于时空特性的数据挖掘隐私保护方法研究.pdf

摘要 论文题目：基于时空特性的数据挖掘隐私保护方法研究 学科专业：计算机软件与理论 研究生：陈晓明 指导教师：李军怀副教授 摘要 签名： 签轹御 近年来，随着信息产业广泛而深入的发展，面向不同应用领域的数据激增。人们迫切 需要将这些数据转换成有用的信息和知识，由此带来了对强有力数据分析工具的需求，数 据挖掘技术正是在此需求上产生的。现在，数据挖掘及知识发现技术已经取得了进步，使 用这些技术使我们可以从海量的信息中提取出隐藏的、有用的数据或知识，但是这同时也 增加了当资料公开给外界时所存在的风险，对隐私和信息安全构成威胁。数据挖掘隐私保 护技术就是研究解决此类问题的方法，其目标在于建立某种关联，跨越数据挖掘和数据机 密性之间的鸿沟。 在数据挖掘隐私保护的研究中，隐私数据的时间特性以及空间特性是历来研究中所常 常被忽视的。众所周知，时间性和空间性是现实世界数据库本身固有的因素，更是构成隐 私数据的两大基本属性，把它们作为约束条件，就可以研究更为真实的现实情况。本文针 对这两个特性开展了数据挖掘隐私保护方法的研究。论文首先介绍了数据挖掘、隐私保护 的基本概念，并从数据分布方式、数据修改方式、数据挖掘算法、隐私保护对象和隐私保 护技术五个角度分析和评价了目前几种典型的隐私保护数据挖掘方法。接着研究了含有时 间性约束和含有空间性约束的隐私保护方法，在此方法中定义了数据安全级概念，对不同 的项目或事务，按照其相应的安全级采用不同等级进行属性分层，使数据的隐私得到保护。 然后将数据安全级与时间和空间相结合，引入了数据安全级的时效性以及空效性，然后综 合时间和空间特性，研究了基于时空特性的隐私保护方法。最后，将该方法应用于基于时 空约束关联规则的数据挖掘隐私保护中，研究了隐私保护关联规则挖掘算法，并通过实验 对算法的信息损失度、执行时间、算法效能等性能进行了分析和验证。 本研究得到了陕西省自然科学基金“数据挖掘中的隐私保护方法研究”( 编号： 2 0 0 5 f 0 5 ) 的资助。 关键词：隐私保护；时空约束；数据安全级；数据分层；关联规则 a b s t r a c t t i t l e ：s t u d yo np r l v a c yp r e s e r v i n ga p p r o a c h e sb a s e do n t e m p o r a la n ds p a 丁i a lc h a r a c t e r i s t i c s m a j o r - c o m p u t e rs o f t w a r ea n dt h e o r y n a m e ：x i a o m i n gc h e n s u p e r v i s o r = a s s o c i a t ep r o f j u n h u a il i a b s t r a c t s i g n a t u 陀：2 【f 蚀迹9 西孙 s i g n a t ur e - 压五一f w i t ht h ef u r t h e rd 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 , s t r o n gd e m a n d so ff i n d i n gu s e f u l k n o w l e d g ef r o mt h em a s s i v ed a t ab r i n ga b o u tt h ee m e r g e n c eo fd a t aa n a l y s i st o o l s s u c ht h a t t h e r ea p p e a r st h ec o n c e p to fd a t am i n i n g n o w a d a y s ，d a t am i n i n ga n dk n o w l e d g ed i s c o v e r y t e c h n o l o g i e sh a v em a d eg r e a tp r o g r e s s w i t ht h eh e l po f t h e s et e c h n o l o g i e s m a n y u s e f u lh i d i n g k n o w l e d g eo rd a t u mc o u l db ef e t c h e do u t h o w e v e r , t h e r ea l s oh a v ei n c r e a s i n gr i s k sw h e nt h e d a t ai so p e nt op u b l i c ，a sr e s u l t ，t h ep r i v a c yi sf a l l e nu n d e rt h r e a t e n p r i v a c y - p r e s e r v i n gd a t a m i n i n g ( p p d l v 0h a se m e r g e dt oa d d r e s st h e s ei s s u e s n 怆r e s e a r c ho fp p d m i sa i m e da t b r i d g i n gt h eg a pb e t w e e nc o l l a b o r a t i v ed a t am i n i n ga n dd a t ac o n f i d e n t i a l i t y i nt h er e s e a r c ho fp p d m a st w oi m p o r t a n tb a s i cc h a r a c t e r i s t i c so fp r i v a c yi n f o r m a t i o n ， t e m p o r a la n ds p a t i a l i t ya r eo f t e ni g n o r e d t h e s et w oe l e m e n t sc o u l db e t t e rh e l pu ss t u d yt h e a c t u a ld a t a b a s ei f b e e nt a k e ni n t oa c c o u n t r e s e a r c ho f t h i st h e s i si sb a s e do nt h i sm a i ni d e a f i r s to fa l l ，s o m eb a s i cc o n c e p t so fd a t am i n i n ga r eb r o u g h tf o r w a r d t h e n ，w ei n t r o d u c e a n da n a l y z es o m et y p i c a lp r i v a c yp r e s e r v i n ga l g o r i t h m sf r o md a t ad i s t r i b u t i o n ，d a t a m o d i f i c a t i o n , d a t am i n i n ga l g o r i t h m , h i d i n go b j e e l sa n dp r i v a c yp r e s e r v i n gt e c h n o l o g y d i m e n s i o n s s e c o n d l y , n o v e la b o u tp r i v a c yp r e s e r v i n gd a t am i n i n gw i t ht h et e m p o r a la n ds p a t i a l c o n s t r a i n ti sp r o p o s e d t h ek e yc o l e 印t ，w h i c hi sc a l l e dd a t ac o n f i d e n t i a ll e v e l ，i sd e f i n e di nt h e t h e s i s p r i v a c yo fd a t ao rt r a n s a c t i o n si sp r e s e r v e db yu s i n gc o n c e p tg e n e r a l i z a t i o nh i e r a r c h y a c c o r d i n gt oi t sd a t ac o n f i d e n t i a ll e v e l i n t e g r a t e dw i t ht i m ea n ds p a c e ，t h ed a t ac o n f i d e n t i a l l e v e li se x t e n d e dt oh a v ep r o p e r t i e so f t e m p o r a la n ds p a t i a l i t y t h e n , b a s e do nt h ef o r m e rc o n t e n t , m e t h o di sp r o p o s e di n t e g r a t e dw i t ht e m p o r a la n ds p a t i a l c o n s t r a i n t f u r t h e rm o r e ，t h em e t h o di sa p p l i e dt op r i v a c yp r e s e r v i n ga s s o c i a t i o nr o l e sm i n i n g a f t e rt h ea l g o r i t h mc o n s t r u c t i o n s o m ee v a l u a t em e a s u r e sa r eu s o dt ot e s t i f ya n da n a l y z et h e a l g o r i t h mp e r f o r m a n c e ，w h i c hi n c l u d ei n f o r m a t i o nl o s sa n d e x e c u t i o nt i m ea n da l g o r i t h mu t i l i t y a n ds o o n t i l i sr e s e a r c hi ss p o n s o r e db yn a t u r a ls c i e n t i f i cf o u n d a t i o no fs h a a n x ip r o v i n c e r e s e a r c h o np r i v a c yp r e s e r v i n gd a t am i n i n gm e t h o d s ( n o 2 0 0 5 f 0 5 ) k e yw o r d s ：p r i v a c yp r e s e r v i n g ；t e m p o r a la n ds p a t i a l c o n s t r a i n t ；d a t ac o n f i d e n t i a ll e v e l ； d a t ag e n e r a l i z a t i o nh i e r a r c h y ；a s s o c i a t i o nr u l e 独创性声明 秉承祖国优良道德传统和学校的严谨学风郑重申明：本人所呈交的学位论文是我个 人在导师指导下进行的研究工作及取得的成果。尽我所知，除特别加以标注和致谢的地 方外，论文中不包含其他人的研究成果。与我一同工作的同志对本文所论述的工作和成 果的任何贡献均已在论文中作了明确的说明并已致谢。 本论文及其相关资料若有不实之处，由本人承担一切相关责任 论文作者签名：醚盘旦日乡唧车弓月日 学位论文使用授权声明 本人睦选塑丛在导师的指导下创作完成毕业论文。本人已通过论文的答辩，并 已经在西安理工大学申请博士硕士学位。本人作为学位论文著作权拥有者，同意授权 西安理工大学拥有学位论文的部分使用权，即：1 ) 已获学位的研究生按学校规定提交 印刷版和电子版学位论文，学校可以采用影印、缩印或其他复制手段保存研究生上交的 学位论文，可以将学位论文的全部或部分内容编入有关数据库进行检索；2 ) 为教学和 科研目的，学校可以将公开的学位沦文或解密后的学位论文作为资料在图书馆、资料室 等场所或在校园网上供校内师生阅读、浏览。 本人学位论文全部或部分内容的公布( 包括刊登) 授权西安理工大学研究生部办 理。 ( 保密的学位论文在觎密后，适用本授权说明) 论文作者签名：堡幽导师签名：铀泐了年；月函日 前言 1 前言 1 1 课题来源 本课题来源于2 0 0 5 年陕西省自然科学基金“数据挖掘中的隐私保护方法研究”。 1 2 课题背景与意义 近年来，随着信息产业广泛而深入的发展，面向不同应用领域的数量激增，包括：科 学数据、医疗数据，人口统计数据、财经数据和市场数据等。人们迫切需要将这些数据转 换成有用的信息和知识，例如：超市的经营者希望将经常被同时购买的商品放在一起，以 增加销售额；保险公司想知道购买保险的客户一般具有哪些特征；医学研究人员希望从已 有的成千上万份病历中找出患某种疾病的病人的共同特征，从而为治愈这种疾病提供一些 帮助等等。对于这些问题，现有信息管理系统中的数据分析工具无法绘出解决办法，因为 无论统计或者查询，其处理方式都是对指定数据进行简单的数字处理，而不能对这些数据 所包含的内在信息进行提取。因此人们希望找到有关方法，对这些数据进行自动地分析、 自动地分类、自动地汇总，自动地发现和描述数据中的趋势，标记异常等等，从而将获取 的有用的信息和知识应用于决策支持系统。数据挖掘正是在此需求上产生的。 与此同时，由于被挖掘的资料或数据还包含着许多敏感性的数据或知识，因此必须受 到保护，即数据挖掘应该在隐私保护条件下开展。尤其是在现在，数据挖掘以及知识发现 技术已经取得了进步，使用这些技术我们可以在海量的信息中提取出隐藏的、有用的数据 或知识，因而更增加了当资料公开给外界时所存在的风险，会对隐私和信息安全构成威胁。 随着越来越多的信息可以电子形式或从网上得到，人们对自己隐私的保密要求变得越 来越迫切。调查显示，不管有没有隐私保护措施，1 7 的上网者不愿意将自身信息提供给 网站，而5 6 的调查者只有在好的隐私保护措施下才愿意提供自身的信息给网站1 1 1 在 这种情况下，如何在保证个人隐私的前提下进行数据挖掘，成了一个需要解决的问题。另 外一个方面，在双方或多方合作进行数据挖掘时，由于某种原因，参与者往往不愿意将数 据与他人共享而只愿意共享数据挖掘的结果。这种情况在科学研究、医学研究及经济和市 场动态研究等方面屡见不鲜1 2 3 1 。 因此，如何保护私有信息或敏感信息在挖掘过程中不被泄露就成为数据挖掘研究中的 一个很有意义的研究课题。保护隐私的数据挖掘( p r i v a c y - p r e s e r v i n g d a t a m i n i n g ，p p d m ) ， 就是研究解决此类问题的解决方案，其目标在于建立某种关联，跨越数据挖掘和数据机密 性之间的这道鸿沟1 4 , 5 1 它的研究内容涵盖众多领域，如统计学、计算机科学，甚至社会 科学等方面，其基本思想在于对原始数据或者挖掘方法进行某种改进，在不向非数据所有 西安理工大学硕士学位论文 者泄露敏感数据取值的同时，发现原始数据的某些统计规律或隐含的知识和规则1 4 , 5 | o p p d m 是未来数据挖掘的一个极其重要而富有挑战性的课题。2 0 0 0 年，文献【2 ，6 】 同时从两个不同的角度提出了两种不同的p p d m 问题，并分别采用数据扰乱( d a t a p e r t u r b a t i o n ) 技术和安全多方计算( s e c u r em u l t i - p a r t yc o m p u t a t i o n , s m c ) 协议加以解决，推 动了许多相关的研究。 1 3 论文主要研究内容与结构 本文针对时间和空间特性开展了数据挖掘隐私保护方法的研究。论文首先对现有隐私 保护数据挖掘方法进行了分析与评价，随后着重研究了基于时间和空间特性的隐私保护方 法，在此基础上研究了基于时空特性的关联规则数据挖掘隐私保护方法，并进行了方法的 实验和性能分析。 后续各章节的结构划分如下： 第一章，介绍了课题的来源、背景以及主要研究内容； 第二章，介绍数据挖掘、隐私保护的基本概念以及典型隐私保护数据挖掘方法： 第三章，在定义了与时间相关的概念后，研究了基于时间约束的隐私保护问题、模型 以及算法； 第四章，在定义了与空间相关的概念后，研究了基于时间约束的隐私保护问题及算法； 第五章，综合时间和空间特性约束，研究了基于时空约束的隐私保护方法及关联规则 数据挖掘隐私保护方法，并进行了实验和性能分析； 第六章，总结全文，对当前工作的不足进行总结，同时对下一步的研究进行展望。 2 隐私保护数据挖掘方法综述 2 隐私保护数据挖掘方法综述 2 1 基本概念 2 1 1 数据挖掘 a 数据挖掘定义 简单地说，数据挖掘是从大量的数据中提取，或“挖掘”知识t 3 1 ，它是一类深层次的 数据分析方法，它可以用来描述使用挖掘算法进行数据挖掘的子过程。而最近人们却逐渐 发现数据挖掘中有许多工作可以由统计方法来完成，并认为最好的策略是将统计方法与数 据挖掘有机的结合起来。 关于数据挖掘的定义，学术界有着许多的观点，以下是一些典型的定义： j w h a r t 在文献 7 1 中将数据挖掘定义为：“数据挖掘是指从数据库中提取模式的 过程，这些模式是有效的、新颖的、潜在可用和容易理解的。模式是指利用一些语言来描 述数据的一个子集或子集的一个可应用的模型”。 另外一种观点把数据挖掘看作是知识发现过程的一个基本步骤。文献【8 】中对它的 定义是： 数据挖掘是数据库中知识发现过程中的一个步骤。这个步骤由应用数据分析和发现算 法组成，在满足一定计算效率的约束下，从数据中产生一个特殊的模式。 j w h a n 的数据挖掘：概念与技术b 1 认为：从广义上理解，数据、信息也是知识 的表现形式，但是更把概念、规则、模式、规律和约束等看作知识，而数据挖掘是从存放 在数据库、数据仓库或其他信息库中的大量数据中提取或挖掘有趣知识的过程，是数据库 中知识发现的一个重要过程。 b 数据挖掘与传统分析方法的区别 数据挖掘与传统的数据分析( 如查询、报表、联机应用分析) 的本质区别是数据挖掘是 在没有明确假设的前提下去挖掘信息、发现知识。数据挖掘所得到的信息应具有先前未知， 有效和可实用三个特征。 先前未知的信息是指该信息是预先未曾预料到的，即数据挖掘是要发现那些不能靠直 觉发现的信息或知识，甚至是违背直觉的信息或知识，挖掘出的信息越是出乎意料，就可 能越有价值。在商业应用中最典型的例子就是一家连锁店通过数据挖掘发现了小孩尿布和 啤酒之间有着惊人的联系。 西安理工大学硕士学位论文 c 数据挖掘系统结构 尽管大多数人都同意数据挖掘是知识发现过程的一个步骤。然而，在产业界、媒体和 数据库研究界，术语“数据挖掘”比术语“数据库中知识发现”更流行。因此，数据挖掘 有一个更为广泛的概念：数据挖掘是从存放在数据库、数据仓库或其他信息库中的大量数 据中挖掘有兴趣知识的过程。基于这种观点，典型的数据挖掘系统具有如图2 - 1 所示的主 要组成部分”1 。 ( 1 ) 数据库、数据仓库或其他信息库：这是一个或一组数据库、数据仓库、电子表格 或其他类型的信息库。可以在数据上进行数据清理和集成。 ( 2 ) 数据库或数据仓库服务器：根据用户的数据挖掘请求，数据库或数据仓库服务 器负责提取相关数据。 ( 3 ) 知识库：这是领域知识，用于指导搜索，或评估结果模式的兴趣度。 4 9 固 数据库 数据库 图2 - 1 数据挖掘系统结构 f i g 2 1s t r u c t u r eo f d a t am i n i n gs y s t e m 隐私保护数据挖掘方法综速 ( 4 ) 数据挖掘引擎：这是数据挖掘系统基本的部分，由一组功能模块组成，用于特 征化、关联、分类、聚类分析以及演变和偏差分析。 ( 5 ) 模式评估模块：通常，此成分使用兴趣度度量，并与数据挖掘模块交互，以便 将搜索聚焦在有趣的模式上。它可能使用兴趣度阈值过滤发现的模式。模式评估模块也可 以与挖掘模块集成在一起，这依赖于所用的数据挖掘方法的实现。 ( 6 ) 图形用户界面：本模块在用户和数据挖掘系统之间通信，允许用户与系统交互， 指定数据挖掘查询或任务，提供信息、帮助搜索聚焦，根据数据挖掘的中问结果进行探索 式数据挖掘。此外，此成分还允许用户浏览数据库和数据仓库模式或数据结构，评估挖掘 的模式，以不同的形式对模式可视化。 d 数据挖掘的过程 数据挖掘过程如图2 - 2 所示，可以看出它不是一个单纯的线性过程，还包括了许多反 馈回路在内。这些过程在具体实施中可能需要重复多次，在每一过程中，需要不同专业人 员的参与，包括业务分析人员、数据分析人员和数据管理人员等。 在特定的数据挖掘应用设计和部署之前，需要先确定挖掘对象，确定应用的范围，了 解用户的需求，确定最后的挖掘目标。一般来说，数据挖掘使用的核心算法可以是关联规 则、分类、聚合、回归、相关分析建模等。 数据挖掘的过程大致可以分为以下4 个阶段。 ( 1 ) 确定业务对象 清晰地定义出业务问题，认清数据挖掘的目的是数据挖掘的重要一步。挖掘的最后结 构是不可预测的，但要探索的问题应是有预见的，为了数据挖掘而数据挖掘则带有盲目性， 是不会成功的。 ( 2 ) 数据预处理： 通常现实中的数据库极易受噪声数据、空缺数据和不一致数据的侵扰。因为数据库规 模庞大，通常大多数以g b 记。通过预处理可以使挖掘过程更加有效，更加容易。 数据预处理有许多方式方法，例如： 数据清理，通过填写空缺值，可以去掉或平滑数据中的噪声，同时识别、删除孤立 点，并解决不一致来“清理”数据。 数据集成，这种方法将数据由多个数据源中的数据合并成一致的数据存储，如数据 仓库。 数据变换，将数据转换成适合于挖掘的形式，例如规格化和聚集，借以改进挖掘算 法的精度和有效性 数据规约，通过聚集、删除冗余特性或者聚类等方法来压缩数据。 西安理工大学硕士学位论文 数据挖掘 评估与表示 门 l j 口 图2 - 2 数据库中知识发现的典型步骤 f i g 2 - 2t y p i c a ls t e p si nk d d 一般说来，数据预处理已经在生成数据仓库时完成了。数据变换的主要目的是将数据 转换成适合数据挖掘需要的形式，例如将文档信息转换成数值向量形式。另外还包括数据 维数的削减或降维( d i m e n s i o n r e d u c t i o n ) ，即从初始特征中找出真正有用的特征以减少数据 挖掘时要考虑的特征或变量个数。 ( 3 ) 数据挖掘 进入数据挖掘的核心步骤，先要根据知识发现过程的目标和确定的数据挖掘对象，选 择相应的数据挖掘方法，如统计分析的方法，机器学习和人工智能的方法。数据挖掘阶段 首先要确定挖掘的任务或目的是什么，如数据总结、分类、聚类、关联规则发现或序列模 式发现等。确定了挖掘任务后，就要决定使用什么样的挖掘算法。同样的任务可以选用不 同的算法来实现。选择实现算法又两个考虑因素：一是不同的数据有不同的特点，因此需 要用与之相关的算法来挖掘；二是用户或实际运行系统的要求，有的用户可能希望获取描 述型的、容易理解的知识( 采用规则表示的挖掘算法显然要好于神经网络之类的方法) ，而 有的用户或系统的目的时获取预测准确度尽可能高的预测型知识。 完成了上述准备工作后，就可以实施数据挖掘操作了。需要指出的是，尽管数据挖掘 算法是k d d 的核心，也是目前研究人员主要努力的方向，但要获得好的挖掘效果，必须 对各种挖掘算法的要求或前提假设有充分的理解。 ( 4 ) 模式评估与知识表示 6 隐私保护数据挖掘方法综述 先根据某种兴趣度度量，对于上一步数据挖掘的结果进行评估，筛选和评价有用部分， 查找可接受的结果；然后可以利用可视化和知识表示等方法，尽量直观的向用户展示和提 供挖掘所得结果，便于他们理解和使用；最后可能需要对所得知识进行巩固，一般是把挖 掘出的知识结合到执行系统中，了解这些知识的作用或证明这些知识，用已知且可信的知 识来检查和验证所挖掘的知识，解决可能存在的矛盾。 e 数据挖掘的功能 数据挖掘的功能用于指定数据挖掘任务中要找的模式类型。数据挖掘任务一般可以分 为描述性挖掘和预测性挖掘。描述性挖掘用于刻画数据库中数据的一般特性。预测性挖掘 的任务则是针对当前数据，在当前数据的基础上进行推理，进而预测。 数据挖掘的目标是从数据库中发现隐含的、有意义的知识，主要有以下五类功能 一1 。 ( 1 ) 概念类描述 数据可以与类或概念相关联，用汇总的、简洁的、精确的方式描述每个类和概念是有 用的，目的是对数据进行浓缩，给出它的总体的综合描述，实现对原始数据的总体把握t 3 l 。 这种类或概念的描述称为概念类描述。概念，类描述就是对某类对象的内涵进行描述，并 概括这类对象的有关特征。概念描述分为特征性描述和区别性描述，前者描述某类对象的 共同特征，后者描述不同类对象之间的区别。生成一个类的特征性描述只涉及该类对象中 所有对象的共性。生成区别性描述的方法很多，如决策树方法、遗传算法等。 通过概念类描述使得人们能够在复杂数据库中了解数据的意义以及产生数据的过 程。这种描述可以通过汇总所研究类的数据来获得，这个过程也叫数据特征化，通常成为 目标类的数据。基于数据立方体的o l a p 上卷操作来执行指定维的数据汇总就是一种很 有效的数据特征化的方法，数据特征的输出可以用多种形式提供，如饼图、条图、曲线、 多维数据立方体和包括交叉表在内的多维表等来形象的表现出来”1 。 ( 2 ) 关联分析 数据关联是数据库中存在的一类重要的可被发现的知识。数据库中的数据之间一般都 存在一定的关联关系，若两个或多个变量的取值之间存在某种规律性，就称为关联。关联 可分为简单关联、时序关联、因果关联。关联分析用来发现关联规则，这些规则展示了属 性与值在给定的数据集中频繁出现的条件。关联分析的目的是找出数据库中隐藏的关联 网。有时并不知道数据库中数据的关联函数，即使知道也是不确定的，因此关联分析生成 的规则带有可信度。关联分析广泛应用于购物篮或事务数据分析。 ( 3 ) 分类与预测 分类( c l a s s i f i c a t i o n ) 就是通过研究已分类的样本集的特征，分析样本集的属性，建立一 个可以描述并区分数据类或概念的分类模型函数，通过这个分类模型，未分类的新数据 就可以分派到不同的类别中，达到分类的目的。分类的方法有：决策树归纳、贝叶斯网络、 人工神经元网络( 如b p 网络等) 、粗糙集、遗传算法、k - m e a n s 分类和支持向量机等方 7 西安理工大学硕士学位论文 法。分类可以预测对象的类标签，当要预测的数据是数值数据( 连续值) ，而不是离散的类 别标志时，则称为预测1 1 0 1 0 预测主要使用回归方法，当然也可以使用人工神经元网络、 支持向量机等机器学习方法。此外分类和预测之前可能需要进行相关分析( r e l e v a n e e a n a l y s i s ) ，以识别对于分类和预测无用的属性，将它们排除妇1 。 ( 4 ) 聚类 数据库中的记录可被化分为一系列有意义的子集，即聚类。聚类增强了人们对客观现 实的认识，是概念描述和偏差分析的先决条件。聚类技术主要包括传统的模式识别方法和 数学分类学。8 0 年代初，m i c h a l s k i 提出了概念聚类技术，其要点是，在划分对象时不仅 考虑对象之间的距离，还要求划分出的类具有某种内涵描述，从而避免了传统技术的某些 片面性。 ( 5 ) 偏差检测 数据库中的数据常有一些异常记录，从数据库中检测这些偏差很有意义。偏差包括很 多潜在的知识，如分类中的反常实例、不满足规则的特例、观测结果与模型预测值的偏差、 量值随时间的变化等。偏差检测的基本方法是，寻找观测结果与参照值之间有意义的差别 1 9 1 f 数据挖掘常用的方法 数据挖掘的研究融合了多个不同学科领域的技术与成果，使的目前的数据挖掘方法表 现出多种多样的形式。数据挖掘的方法可粗分为：统计方法、机器学习方法、神经网络方 法。统计方法中，可细分为：回归分析( 多元回归、自回归等) 、判别分析( 贝叶斯判别、 费歇尔判别、非参数判别等) 、聚类分析( 系统聚类、动态聚类等) 、探索性分析( 主元分 析法、相关分析法等) 、以及模糊集、粗集、支持向量机等。机器学习中，可细分为：归 纳学习方法( 决策树、规则归纳等) 、基于范例的推理c b r 、遗传算法、贝叶斯信念网络 等。神经网络方法，可细分为：前向神经网络( b p 算法等) 、自组织神经网络( 自组织特 征映射、竞争学习等) 等。数据库方法主要是基于可视化的多维数据分析或o l a p 方法， 另外还有面向属性的归纳方法等。 ( 1 ) 人工神经网络方法 人工神经网络( a r t i f i c i a ln e u r a ln e t w o r k ，删系统是由大量简单的处理单元( 即神经元) 广泛连接而成的复杂网络系统。它模拟人脑神经元结构，并做了一定的简化和抽象为解决 大复杂度问题提供了一种相对来说比较有效的简单方法。神经网络由于本身良好的鲁棒 性、自组织自适应性、并行处理、分布存储和高度容错等特性非常适合解决数据挖掘的问 题。典型的神经网络模型主要分3 大类：以感知机、b p 反向传播模型、函数型网络为代 表的，用于分类、预测和模式识别的前馈式神经网络模型；以h o p f i e l d 的离散模型和连 续模型为代表的，分别用于联想记忆和优化计算的反馈式神经网络模型；以a r t 模型、 k o h o l o n 模型为代表的，用于聚类的自组织映射方法。 8 隐私保护数据挖掘方法综述 在数据挖掘中，神经网络主要用于获取分类模式。但是由于神经网络分类方法获取的 模式隐含在网络结构中，而不是显示地表达为规则，不容易被人们理解和解释，这也是神 经网络的缺点之一；另外要多次扫描训练数据，网络的训练时间较长。因此与其他数据挖 掘方法不同，神经网络用于数据挖掘，要解决好两个关键问题：一是降低训练时间，二是 挖掘结果的可理解性。 ( 2 ) 遗传算法 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种基于生物自然选择与遗传机理的随机搜索算 法，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。遗传算法是 一种仿生全局优化方法。遗传算法具有的隐含并行性、易于和其它模型结合等性质使得它 在数据挖掘中被加以应用。 s u n i l 已成功地开发了一个基于遗传算法的数据挖掘工具，利用该工具对两个飞机失 事的真实数据库进行了数据挖掘实验，结果表明遗传算法是进行数据挖掘的有效方法之 一。遗传算法的应用还体现在与神经网络、粗集等技术的结合上。如利用遗传算法优化神 经网络结构，在不增加错误率的前提下，删除多余的连接和隐藏单元；用遗传算法和b p 算法结合训练神经网络，然后从网络提取规则等。但遗传算法的算法较复杂，收敛于局部 极小的较早收敛问题尚未解决i l l | 。 ( 3 ) 决策树方法 决策树( d e c i s i o nt r e e ) 是建立在信息论基础之上，通过逼近离散值目标函数对数据 进行分类的一种方法。决策树是一种常用于预测模型的算法，它通过将大量数据有目的分 类，从中找到一些有价值的，潜在的信息。它的主要优点是描述简单，分类速度快，特别 适合大规模的数据处理。最有影响和最早的决策树方法是由q u i n l a n 提出的著名的基于信 息熵的i d 3 算法。它的主要问题是：i d 3 是非递增学习算法；i d 3 决策树是单变量决策树， 复杂概念的表达困难：同性间的相互关系强调不够；抗噪性差。针对上述问题，出现了许 多较好的改进算法，如s c h l i m m e r 和f i s h e r 设计了i d 4 递增式学习算法；钟鸣，陈文伟 等提出了i b l e 算法等 1 1 1 ( 4 ) 粗集方法 粗集( r o u g hs e t ) 理论是一种研究不精确、不确定知识的数学工具。粗集能够在缺少关 于数据先验知识的情况下，只以考察数据的分类能力为基础，解决模糊或不确定数据的分 析和处理问题。粗集理论可以用于分类，发现不准确数据或噪声数据内在的联系。找出可 以描述给定数据集中所有概念的最小属性子集是个n p 难问题。在给定的现实世界数据 中，往往有些类不能被可用的属性区分，那么就可以用粗集来近似地定义这些类。粗集方 法有几个优点：不需要给出额外信息；简化输入信息的表达空间；算法简单，易于操作。 粗集处理的对象是类似二维关系表的信息表。目前成熟的关系数据库管理系统和新发展起 来的数据仓库管理系统，为粗集的数据挖掘奠定了坚实的基础。但粗集的数学基础是集合 论，难以直接处理连续的属性。而现实信息表中连续属性是普遍存在的。因此连续属性的 9 西安理工大学硕士学位论文 离散化是制约粗集理论实用化的难点。 ( 5 ) 覆盖正例排斥反例方法 它是利用覆盖所有正例、排斥所有反例的思想来寻找规则。首先在正例集合中任选一 个种子，到反例集合中逐个比较。与字段取值构成的选择子相容则舍去，相反则保留。按 此思想循环所有正例种子，将得到正例的规则( 选择子的合取式) 。比较典型的算法有 m i c h a l s k i 的a q l l 方法、洪家荣改进的a q l 5 方法以及他的a e 5 方法。 ( 6 ) 统计分析方法 在数据库字段项之间存在两种关系：函数关系( 能用函数公式表示的确定性关系) 和相 关关系( 不能用函数公式表示，但仍是相关确定性关系) ，对它们的分析可采用统计学方法， 即利用统计学原理对数据库中的信息进行分析。可进行常用统计( 求大量数据中的最大值、 最小值、总和、平均值等) 、回归分析( 用回归方程来表示变量间的数量关系) 、相关分析( 用 相关系数来度量变量间的相关程度) 、差异分析( 从样本统计量的值得出差异来确定总体参 数之间是否存在差异) 等。 ( 7 ) 模糊集方法 即利用模糊集合( f u z z ys e t ) 理论对实际问题进行模糊评判、模糊决策、模糊模式识别 和模糊聚类分析。模糊集合和模糊推理是模糊方法的数学基础，模糊集理论以不确定性的 事物为研究对象，是经典集合理论的扩展。简单的说，系统的复杂性越高，模糊性越强， 一般模糊集合理论是用隶属度来刻画模糊事物的亦此亦彼性的。模糊推理注重的是把握结 论的趋势，是近似的而不是精确的结果当然，模糊推理的结果也可能是错的，所以还要实 践检验。李德毅等人在传统模糊理论和概率统计的基础上，提出了定性定量不确定性转换 模型云模型，并形成了云理论。 ( 8 ) 云理论 云( c 1 0 u d ) 理论是李德毅教授于1 9 9 5 年提出的用于处理不确定性的一种新理论。作为 处理模糊性问题的主要工具，模糊集理论提出了隶属度函数来刻画模糊事物的亦此亦彼 性；然而，一旦用精确的隶属度函数来描述模糊集，之后的模糊推理等环节就不再有模糊 性了。这就是传统模糊集理论的不彻底性。针对这一问题，李德毅教授在传统模糊集理论 和概率统计的基础上提出了定性定量不确定性转换模型一云模型，把定性概念的模糊性和 随机性完全集成到一起，构成定性和定量相互间的映射，作为知识表示的基础1 1 2 1 。 在数据挖掘中，云理论常和粗集理论相结合。前者研究的是数据的模糊性和随机性， 为定量定性间的不确定性转换提供模型；而后者强调的是数据的不完备性和不可分辨性， 但其处理方法是确定性的，要求属性值都是定性值，所以两者具有某种互补性。 l o 隐私保护数据挖掘方法综述 2 1 2 关联规则 a 关联规则的提出 a g r a w a l 等在1 9 9 3 年首次提出了关联规则挖掘的概念及问题描述和算法a i s 1 3 1 关 联规则挖掘目标在于发现大量数据中项集之间有趣的关联或相关联系3 1 。随着大量数据 不停的搜集和存储，许多业界人士对于从他们的数据库中挖掘关联规则越来越感兴趣。从 大量商务事务记录中发现有趣的关联关系，可以帮助许多商务决策的制定，如分类设计、 交叉购物和拍卖分析等。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中不 同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁的被顾客同时购买，这 种关联的发现可以帮助零售商制定销售策略。通过帮助零售商有选择的经销和安排货架， 这种信息可以引导销售，如将顾客频繁“捆绑”购买的物品放近一些，可以进一步刺激顾 客的同时购买这些商品1 3 1 9 另外，关联规则发现的思路还可以用于序列模式发现。如顾 客在购买物品时，除了具有上述关联规律，还有时间上或序列上的规律，这次买这些东西， 下次买同上次有关的一些东西等等。 b 关联规则的形式化描述 设i = i i ，i 2 ，i 。 由m 个不同的项目组成的集合，称为项集。给定集合d = t l ，t 2 ，t i i ) 称为事务数据库，其中t t 称为一个事务，是由项集i 中一组项目组成的，即t i c i 。每一 个事务拥有唯一的t i d ，称为事务标识符。设x 中包含k 个项目，则x 称为k - 项集， 对于事务t e d ，如果x c _ t 称t 包含项集x 。 关联规则就是形如x j y 的蕴涵式，其中x 和y 是项集且x n y = 由。 定义2 1 项集支持度 项集x 的支持度s u p p o r t ( x ) 是包含x 的事务t 在事务数据库d 中出现的次数同d 中 事务总和的比率，即 s u p p o r t 0 0 = 背 q 1 定义2 2 置信度 规则x j y 的置信度定义为在条件x 成立时成立的条件概率，即 confide胛ce(x=y)=等support(a) ( 2 2 ) 定义2 3 规则支持度 规则x j y 的支持度定义为x 和y 同时出现在t 中的概率，即： s u p p o r t ( xj 矽= s u p p o r t ( xu 矽 ( 2 3 ) 西安理工大学硕士学位论文 定义2 4 频繁项集 项集x 为频繁项集，当且仅当x 的支持度超过用户定义的最小支持度m i ns u p p 的 非空项集。即s u p p o r t ( 芝m i n _ s u p p 。 频繁k - 项集的集合通常记作l k 隐私保护的关联规则挖掘，就是要在不精确访问原始事务集d 的条件下，尽量准确地 发现其中的频繁项集，产生支持度和置信度分别不低于用户给定阈值的关联规则。 通常，关联规则挖掘的过程分为以下两步： 第l 步：发现频繁项集。 第2 步：根据第1 步发现的频繁项集，产生置信度不低于预先设定阂值的关联规则。 可以看出，第2 步是在第l 步结果的基础上进行的，面与原始事务集无关。 r a g r a w a l 等人提出的a p r i o r i 算法是关联规则的基本算法，以后出现的各种算法基 本上都是基于a p r i o f i 算法改进的。a p r i o r i 算法利用了如下两个基本性质：即任何强项 集的子集必定是强项集及任何弱项集的超集必定是弱项集，该算法的关键是尽可能生成较 小的侯选项目集，它的依据是一个频繁项目集的任一子集必定是频繁项目集，进而提出算 法的基本框架描述。本算法的突出特点是利用第k - l 趟扫描中得到的强项集的集l “来 生成k - 项集c k ，由a p r i o r i - g e n ( l k ) 实现。 a p f i o r i 算法是一种宽度优先算法，通过对数据库d 的多次扫描来发现所有的频繁项 目集，在每一次扫描中只考虑具有同一长度( 即项目集中所含项目的个数) 的所有项目集。 在第一次扫描中，a p r i o r i 算法计算d 中所有单个项目的支持度，生成所有长度为l 的频繁项目集。在后续的每一次扫描中，首先以k - 1 次扫描所生成的所有频繁项目集为基 础产生新的侯选项目集，然后扫描数据库d ，计算这些侯选项目集的支持度，删除其支持 度低于用户给定的最小支持度的项目集，最后，生成所有长度为k 的频繁项目集。重复上 述过程直到再也发现不了新的频繁项目集为止。 一个简化的流程如下： 1 ) 使k = l ，让候选集合( c a n d i d a t es e t s ) 只包含单个项目。重复以下步骤，直到没有 候选集合剩下： ( a ) 从文档中读取数据，并计算所有候选集合的支持度； ( b ) 删除所有支持度小于s 。n ( 最小值支持度) 的集合； ( c ) 保存剩下的集合用作输出； ( d ) 构造所有可能的( i 汁1 ) 一项目集，其所有的k 子集均包含在剩余的集合中，然后 让这些项目集成为新的备用集合； ( e ) 让k = k + 1 。 2 ) 输出所有保存的项目集。 相应地，a p r i o r i 算法的基本框架描述如下： 输入：数据库d 的事务，m i n ，_supp 1 2 隐私保护数据挖掘方法综迷 输出：d 的频繁集l i ( 1 ) l i = l a r g e1 - i t e m s e t s ； ( 2 ) f o r ( k = 2 ；h 1 o ；h 斗) ( 3 ) c k = a p d o r i _ g e n ( l k q ，m i n _ s u p p ) ；* 生成候选l 【项集+ ( 4 ) f o re a c ht r a n s a c t i o n st e d ( 5 ) c i = s u b s e t ( c k ，t ) 广候选集c k 中提取包含在事务t 中