数据挖掘和隐私保护的分析研究Word格式文档下载.docx
《数据挖掘和隐私保护的分析研究Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《数据挖掘和隐私保护的分析研究Word格式文档下载.docx（64页珍藏版）》请在冰点文库上搜索。
（1）系统的阐述数据挖掘技术的基本理论和应用前景。
（2）详细的阐述关联规则挖掘算法的工作原理和实现方法，并对典型的Apriori算法进行详细的分析。
Apriori算法产生的候选集过大，算法必须耗费大量的时间处理候选项集，根据分段可连接性，在算法设计上使用段标识来记录本段后续项集可匹配的个数使得连接得到优化。
根据先验知识k-项集如果是频繁项集，那么它的所有（k-1）-项子集均是频繁项目集来减少k-项集中非频繁项集。
再通过对项集出现频度的升序排列，减少3-项集的项数。
利用空间交换时间的方法,用布尔矩阵来记录数据库的各项交易记录，只需要一次扫描数据库，大大提高算法的执行效率。
（3）在序列分割挖掘时，所有的记录被多个参与方所拥有，多个参与方在不想泄露各自隐私信息的同时联合进行对各个参与方的时序序列进行分割。
本文将联合计算时序规则各频度问题转化成秘密比较大小的问题，并对现有的算法和协议利用秘密比较协议和同态加密协议进行改进，提出新协议。
关键词：
数据挖掘，关联规则，时序规则，安全多方计算，秘密比较
WiththerapiddevelopmentofglobalInternettechnology,networkcommunic-ationtechnologyandcomputertechnology,globalinformationnetworksystemhasbeenthecurrentsustainableinfrastructureinallwalksoflife,networkinformationsystemdevelopmenthavemadetremendouscontributionsinthecommunity.Sincedataminingtechnologyminefromamassofusefulinformationouttopeople,sothatdataminingisanimportantsteptowardsknowledgediscovery.Dataminingtechnologyalonecaneasilyleadtomeaninglessormisleadingdiscoverymode,itisimportanttohaveacorrectunderstandingoftheapplicationtousedatamining.Byassociationrulemining,wecangetthevaluableusefulinformationhiddeninhugeamountsofdata.Withthedevelopmentofnetworkcommunicationtechnology,dataminingtechnologycannotonlyprovidepeoplewithknowledgeandinformationbutalsoexposetheprivateinformation.Protectionofprivatedataorsensitivedatainthedataminingprocesscannotbecompromisedwhilediggingoutthemoreaccuratetheresultshasbecometheemphasisandfocusofthestudyofdataminingtechnology.
Themainresearchworkincludethefollowing:
（1）Acomprehensivedescriptionofthebasictheoryandapplicationofthedataminingtechnology.
（2）Detailtheworkofassociationruleminingalgorithmprincipleandmethod,andanalyzesthetypicalApriorialgorithm,BecausethecandidatesetwhichApriorialgorithmgenerateistoolarge,thealgorithmmustspendsomuchtimedealingwithcandidateitems,accordingtosegmentationconnectivity,thealgorithmuseslabelstorecordthenumberofmatchingitemsetsfollowedbythisparagraphandhasbeenoptimized.Accordingtothepriorknowledgeofk-itemsetisfrequentitemset,thenallits（k-l）-itemsareasubsetoffrequentitemsetssubtractthenon-frequentitemsetsinthek-items.reducingthenumberof3-itemsetsitems.Usingspaceexchangetimemethod,Booleanmatrixisusedtorecordthetransactionrecordsofdatabase,onlyonescanningthedatabase,soitgreatlyimprovestheexecutingefficiencyofalgorithm.
（3）Whileminingdivisioninthesequence,allrecordsareownedbyvariousparticipants,manyparticipantsdonotwanttodisclosetheirprivateinformationatthesametimeasjointparticipantsinthetimingofeachsplitsequences.Weconverthetimingruletocalculatethejointfrequencyofrelativelyproblemintothecomparisonofthesecretproblem,andimprovetheexistingalgorithmsandprotocolsbyusingthecomparisonofthesecretagreementandhomomorphicencryptionagreement,thenweputforwardthenewagreement.
Keywords:
Datamining,Associationrules,Timingrules,Securemultipartycomputation,Secretcomparison
in
独创性声明
本人声明所呈交凶学住论文是本人在旱梅指导下it行的研死工作及取缗的研究成果.据我所知.除了文中特异.加以标注和致谢的地力外，论文中不包含其但人已经发表成软写过的钥芜成果,危不包含为获得焰J收瘙或其化教育机枸的学位或证书疗便用过的W料.与我一同工作的同志对本研究所仗的任何贡就妁巳在论文中作了明确的说史井米示谢意.
学位论文作者签名：
£
和郊 签字E期：
＞做 午夕月MH
（保密的学位论文在解碧后适用本授权书）
学位论文版权使用授权书
本学位论文作巾完全了您¥
喊大尊有关保割、使，里孕位论文蚀规定,
有权保留才向国家有关部门或机为送交论文的复沏件和磁级，允许论文核查用和信闽.本人授权％KM尊可以珞学位论文为全部或部分内容编入有关姣据库进行检食.可以采用彩勺，编市或有席等殳制手段保移、汇粮学位论文.
（保密的学位论文在解费后适用本授双书）
学位论文作.老签名：
2*的
导忏签名：
笠字B期：
3.0/0年3月G8B
签字日榜：
事年J-月日
电话：
1*8。
结12尚
邮埃:
63对°
学位论文作.老毕'
，夫向：
如t
工作单位:
索制普隆社染*通宛地址:
座财篥润市学物嫉
第•章绪论
第一章绪论
1.1课题背景及意义
数据挖掘概念出现于20世纪80年代后期，90年代成为研究的焦点，数据挖掘是数据库研究、开发及其应用中最活跃的分支之一。
数据挖掘是数据和信息系统及其应用的前沿学科。
数据挖掘也是多学科交叉的融合，从数据库技术、统计学、机器学习、神经网络、模式识别、知识库系统、信息检索、入侵检测系统中汲取相关理论基础，提供发现隐藏在集中的、大型的数据中提取有用的、感兴趣的模式技术。
这是项极具挑战性的技术研究。
面对全球信息系统的流行和数据库的爆炸性增长，激发了数据挖掘以智能的方式挖掘出海量数据中的微量信息并转化成人们所关心的、感兴趣的、有用的信息和知识。
市场需求与技术研究两者兼备的前提下，数据挖掘技术和数据库知识发现KDD的概念及技术就从应运而生到广泛发展不断走向成熟。
数据挖掘技术中关联规则挖掘是从海量数据中发现项与项之间有趣的关联和相关，研究背景开始源于对购物篮分析，扩展到网络入侵检测、关联规则分类、文本文档词频分析、股票事务分析、网页访问日志推断模式等方面，并得到广泛应用研究。
理论研究也从最初的频繁模式挖掘扩展到闭合模式挖掘、最大模式挖掘、扩展型关联规则、衍生型关联规则、隐私保护、增量挖掘、挖掘后处理、主观兴趣度度量、相关模式、数据流等多种数据类型的关联规则挖掘。
本文中还研究了数据挖掘中安全多方计算的应用，又称该领域为保护私有信息的数据挖掘（（Private-preservingDataMining,PPDM）,隐私保护在数据挖掘领域的研究是近几年一个新型热点。
通常情况下，数据挖掘领域中的所涉及的私有信息被划分为两大类：
一类是原始数据本身具有的隐私（用户的个人基本信息,例如：
姓名、省份证、户籍、工作单位、手机号码等）；
另一类是原始数据所隐含的隐私知识（用户某些私人行为信息，例如：
商场购物信息、医疗信息等），如果用户的这些隐私信息有意或无意的泄露可能会引来不必要的麻烦。
因此，隐私数据的保护是数据挖掘技术中是非常有意义的研究。
本文将对数据挖掘中的关联规则挖掘的核心算法Apriori算法及其改进算法所面临的瓶颈问题进行详细分析，提出自己对Apriori算法改进的方案。
同时本文也对数据挖掘中时间序列模式进行分析研究，将时序挖掘结合隐私保护来提高数据库系统的安全管理，基于半可信第三方引入的不可靠性，提出了一个新的安全两方协议，在各自不泄露自己私有信息的情况下秘密比较两个数的大小的问题。
1.2国内外研究现状
关联规则挖掘中最经典的一个算法是Agrawal等人于1994年提出的…Apriori算法⑴，随后的很多算法都是围绕着如何提高Apriori算法的效率而展开研究的。
为了进一步提高关联规则挖掘算法的效率，都对原有的Apriori算法进行了改进，如引入了选样、事务压缩、划分、散列方法和动态项集计数等思想。
频繁模式挖掘算法一FP-growth算法不产生候选项集，两次扫描数据库，挖掘频繁模式的速度比Apriori算法有一个数量级的提高，但挖掘效率不高，占用空间较大。
为此不少研究人员又提出了多种基于FP-growth算法的变形和改进：
文献［2］中的FP-growth算法利用FP-array技巧改善了挖掘性能。
文献［3］提出了H-Min算法使用超链接结构H-struct,在挖掘过程中可以动态修改数据链接求得频繁项集。
文献［4］使用特殊的树P-tree仅需遍历数据库一次就可求得所有关联规则。
文献［5］用临时根节点的技巧，解决挖掘过程中不断产生与释放条件模式树的缺点。
隐私保护技术作为新兴的研究热点课题，不论在理论研究还是在实际应用方面都有非常重要的研究价值，我国对隐私保护技术的研究包括：
中国科技大学、北京大学、复旦大学、东北大学、华中科技大学等很多大学的多个课题组的研究受到学术界的关注和重视。
目前国内关于隐私保护技术的研究主要集中在数据失真和数据加密技术方面的研究，例如：
关联规则挖掘算法、隐私保护分类挖掘算法、网络访问控制等方面。
总的来说我国国内关于隐私保护技术的研究还处于起步阶段，拥有良好的研究前景。
1.3本文研究内容和论文结构
本文的主要研究内容包括：
数据挖掘技术中的关联规则挖掘和时序规则以及安全多方计算的基础理论和基础协议。
对关联规则挖掘中的典型算法--Apriori算法进行分析研究和改进，在联合序列分割中隐私保护里引入安全多方计算知识--多方联合进行序列分割，同时给出相应协议的改进。
本文的论文结构如下所述：
第一章，绪论，主要介绍本论文的研究背景和意义、国内外研究现状以及论文的主要研究内容和论文结构的工作安排。
第二章，数据挖掘与关联规则挖掘，首先介绍数据挖掘的基本概念、分类和特点；
再简要介绍关联规则挖掘问题和Apriori算法及其改进算法分析的相关理论。
第三章，安全多方计算相关知识，介绍安全多方计算的基础理论和基础协议。
第四章，关联规则挖掘算法的改进，详细阐述并分析了典型的Apriori算法,由于该算法在连接过程中很多项集出现的频度很小，然而生成的频繁候选项集非常多，需要在再次扫描数据库时造成了不必要的浪费，尤其是在2-项集生成候选3-项集的过程中，在本文给出了相应的改进，并给出详细证明。
第五章，联合序列分割中隐私保护，引入隐私保护在序列挖掘的一个新的应用…多方联合进行序列分割，同时给出了相应改进协议。
第六章，总结和展望，对本论文的研究工作进行总结和展望。
3
第二章数据挖掘
面对当前“海量数据，微量信息”的现状，数据挖掘的重要研究分支--关联规则，作为一种高级和智能的数据处理和分析技术的研究正方兴未艾。
通过关联规则挖掘，可以得到隐含于海量数据中具有应用价值的有用信息。
关联规则的目标是以有效的方式提取最有趣的模式。
迄今为止已提出了许多高效的关联规则挖掘算法，其中以Agawal等人提出的Apriori算法最为著名，其它挖掘算法大多数都是建立在Apriori算法基础之上。
但是Apriori算法无论在时间效率还是空间伸缩性上都面临着挑战，因此研究人员探索出很多新的挖掘方法，并拓展了关联规则概念及应用范围。
本章详细分析了具有影响力的数据挖掘中关联规则的经典算法-Apriori算法和时序挖掘模式。
再从宽度、深度、划分、采样、增量式更新等几个角度对关联规则挖掘进行了分类讨论，然后运用文献查询和比较分析的方法对常见的关联规则挖掘算法进行了概述。
同时也描述了时序挖掘算法GSP、SPADE、PrefixSpan等算法。
这几种典型的算法都直接或间接的利用了Apriori算法的性质
2.1数据挖掘预备知识
2.1.1数据挖掘基本概念步骤
数据挖掘（DataMining）,又称为数据库中的知识发现（KnowledgeDiscoveryinDatabase）,是从大量的、不完整的、有噪声的、模糊的、随机的大型数据中提取隐含在其中的、人们事先未知的、具有潜在价值的信息和知识的过程回。
简单的说，数据挖掘就是从大量数据中提取或“挖掘”出人们有用的知识。
数据挖掘实施的步骤有主要的三个阶段：
数据准备、数据挖掘、结果的评价和表达口。
也可以细分为：
数据准备、清楚脏数据、数据挖掘、表达、评价五个阶段。
（1）数据准备此阶段将从数据库中提取与分析和任务相关的数据，消除噪声、清除读入的脏数据和不一致的数据，然后对数据进行进行集成并删除一些无用的数据和预处理，以便于适合用于挖掘的形式。
C2）数据挖掘此阶段将综合利用前面所提到的六种数据挖掘方法，分析经过预处理的数据，并从中提取相关规则。
简而言之，就是用智能的方法提取数据模式。
（3）结果表达与评价此阶段将从挖掘中获取的特征和规则以用户可以理解和观察的方式反应给系统。
最后评价通过数据挖掘所发现特征和规则，再根据某种兴趣度度量识别真正有趣的模式。
2.1.2数据挖掘方法的分类和优缺点
数据挖掘技术从功能上可将数据挖掘分析方法分为以下几种：
关联分析、序列模式分析、分类和预测、聚类分析、孤立点分析、演变分析。
（1） 关联分析关联分析目的就是从指定的数据库中挖掘出满足一定条件的依赖性关系和隐藏在数据间的相互关系。
（2） 序列模式分析序列模式分析与关联分析很相似，其目的也是为了挖掘数据间的联系，但序列模式分析的侧重点在于分析数据间的前后关系，简言之就是它侧重于数据之间顺序的关联性。
（3） 分类和预测分类分析研究的是对重要数据类的模型或预测未来的数据发展趋势进行提取和描述。
其本质是分析数据为每个类做出准确的描述或建模，然后用它对数据库中的数据进行分类或将上升之为分类规则。
分类是预测分类标号，预测是建立连续值的函数模型。
（4） 聚类分析聚类分析的记录集是一组来标定的记录，也就是说此时输入的记录没有被进行任何分类。
其目的是根据一定的规则，合理地划分记录集合,并用显式或隐式的方法描述不同的级别。
而所依据的这些规刖是由聚类分析工具定义的。
由于聚类分析法可以采用不同的算法，所以对相同的记录集合可以有不同的划分。
（5） 孤立点分析孤立点分析也称作孤立点挖掘，它研究的对象是从数据库中找出一些数据对象，它们与数据的一般行为或模型不一致。
很多数据挖掘方法常将孤立点视为噪声或者是异常而丢弃。
然而一些实际的应用中，某些罕见的事件可能比正常事件更有趣、有用。
（6） 演变分析演变分析描述的是随时间变化的对象的规律或者趋势并对其进行建模。
尽管这可能包括时间相关数据的特征化、区分、关联、分类或聚类,这类分析的不同特点包括时间序列数据分析、序列或周期模式匹配和基于类似性的数据分析。
数据挖掘优点：
能从海量的数据中用归纳性的推理挖掘出潜在有用的模式。
数据挖掘缺点：
数据库信息的日益增大，数据的种类的不断多样化，关联规则库的不断增加，挖掘出潜在有用规则的难度也极具加大，改进挖掘算法的效率也是亟待解决的事情。
2.1.3隐私保护的数据挖掘
在数据挖掘的研究领域中，隐私数据或者隐私信息被划分为两大类：
一类是原始数据本事具有的隐私；
另一类是原始数据所隐含的隐私知识。
传统的数据挖掘技术研究的原始数据都是来自未加密的数据，所以说在数据挖掘中的保护隐私数据或隐私信息主要应该考虑两个方面：
一是对敏感的原始数据进行保护；
二是对数据库中所提取的敏感知识进行保护。
隐私保护数据挖掘技术研究的的主要目的就是对现有数据挖掘算法的改进来修改原始数据，使得挖掘出来的敏感规则和知识不被泄露。
隐私保护的数据挖掘新的技术包括数据分布方式、数据修改方式、数据挖掘算法、隐私保护对象和隐私保护技术五个方面。
目前一些典型的隐私保护的数据挖掘算法主要有：
随机化方法、抽样法、交换法等。
2.2关联规则预备知识
关联规则的目标是以有效的方式提取最有趣的模式，是一种高级和智能的数据处理和分析技术。
大量数据中的关联和相关关系的发现对市场的选择、决策的分析、商务管理各个方面都有很大的用处。
关联规则挖掘从此被广泛和深入的研究应用于各个学术界并获得跨越式的发展。
关联规则挖掘是从简单的购物分析，或者称为单位单层布尔型关联规则挖掘的研究中发展起来的，随着各个应用领域的需求关联规则的形式得到很好的扩充，规则的兴趣度和度量以及挖掘语言都得到深入的研究。
伴随着各种各样的高级数据库数据形式的出现，关联规则的概念也得到很多扩展。
下面我们将对关联规则的基本知识做进一步的了解。
2.2.1关联规则基本概念
1.数据项与数据项集
设集合1=｛心2,…im｝，其中ik（k=l,2,•••m）表示项。
如果XuL集合X被称为项集。
当|X|=k,则X被称为k-项集。
2.事务
事务二元组T=（tid,X）,tid是事务唯一的标识符称为事务号。
数据集D=｛ti,t2,…tn｝是由tbt2,-tn事务组成的集合。
3.数据项的支持度
设乂="
为数据项集，B为事务集D中包含X的事务的数量，A为事务集D中包含的所有事务的数量，贝擞据项集x的支持度（suppo）rt定义为：
support（X）项集X的支持度support（X）描述了项集x的重要性。
4.关联规则
关联规则可以描述为：
形如AnB的蕴涵式，其中AuLBuL并且AnB=a。
项集X的支持度s是D中包含X的事务数占所有事务数的百分比，记为：
s0）=P（X）=些护 （公式1）
5.关联规则的置信度
项集X的置信度c是D中同时包含XUY的事务数占包含X的所有事务数的百分比，记为：
c（X）=P（XW）=^K （公式2）
6.最小支持度和最小置信度
至于最小支持度minsup和最小置信度mincof都是由用户所给定，如果项集X的sup（X）>
minsup,那么项集X被称为频繁项集，其中生成的关联规则中所有支持度和置信度都不小于minsup和minconf的被称为强关联规则。
关联规则的支持度表示在整个数据库中的重要性，而置信度反映其可靠程度。
只有支持度和置信度较高的关联规则才是用户感兴趣的、有用的关联规则。
2.2.2关联规则基本过程及其分类
关联规则提取中有两个关键的步骤：
一是发现所有的频繁项集；
二是产成强关联规则。
发现频繁项集是关联规则数据挖掘中的关键步骤。
在Apriori算法还利用了“频繁项集的子集是频繁项集，非频繁项集的超集是非频繁项集”这一个性质，它可以有效的对其频繁项集进行修剪，同时这个性质也被绝大部分关联规则算法所继承和应用。
根据不同的标准，关联规则可以用很多不同的方法分成若干类型回：
1） 根据挖掘模式的完全性
根据挖掘模式的完全性可以分类为挖掘频繁项集的完全性、闭频繁项集、
升级会员 