（计算机应用技术专业论文）分布式序列模式挖掘中隐私保护技术研究.pdf

l ”鼍+ ； 独创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中己注明引用的内容以外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果，也不包含为获得江苏大学或其他教育机构 的学位或证书而使用过的材料。对本文的研究做出重要贡献的个人和集体，均已 在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：丧只天享 3 q f 年石月f 1 日 学位论文版权使用授权书 江苏大学、中国科学技术信息研究所、国家图书馆、中国学术期刊( 光盘版) 电子杂志社有权保留本人所送交学位论文的复印件和电子文档，可以采用影印、 缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相一致， 允许论文被查阅和借阅，同时授权中国科学技术信息研究所将本论文编入中国 学位论文全文数据库并向社会提供查询，授权中国学术期刊( 光盘版) 电子杂 志社将本论文编入中国优秀博硕士学位论文全文数据库并向社会提供查询。 论文的公布( 包括刊登) 授权江苏大学研究生处办理。 本学位论文属于不保密 学位论文作者签名：占月天摹 舢1 1 年月ii e l 舯狮躲音咿 如1 1 年石月f a 日 摘要 在序列模式挖掘过程中，隐私保护是一个必须要考虑的前提，尤其在分布式 环境下更加值得关注。现有的分布式数据挖掘隐私保护问题研究主要集中在关联 规则挖掘方面，而对于分布式序列模式挖掘中的隐私保护方法研究的却很少。因 此，深入研究分布式序列模式挖掘的隐私保护方法将具有较高的学术价值和十分 重要的现实意义。 论文介绍了分布式序列模式挖掘中隐私保护方法的国内外研究现状和基本 知识，重点对分布式序列模式挖掘及其隐私保护方法进行研究。针对现有隐私数 据保护方法可能会影响到序列模式挖掘结果的可用性和有效性，提出了一种面向 隐私数据保护的分布式序列模式挖掘方法。针对分布式序列模式挖掘中敏感序列 保护方法中存在的不足，利用关联规则挖掘中规则隐藏的思想，提出了一种分布 式序列模式挖掘中敏感序列保护方法。并在序列模式挖掘中隐私数据和敏感序列 保护算法的基础上，设计并实现了一种基于隐私保护的分布式序列模式挖掘原型 系统。 论文的主要研究成果包括以下几个方面： 1 、总结了分布式序列模式挖掘中隐私保护的研究现状，介绍了经典的序列 模式挖掘算法，对序列模式挖掘中隐私数据和敏感序列隐藏算法进行研究。 2 、针对现有分布式隐私数据保护方法可能会影响到序列模式挖掘结果的可 用性和有效性等问题，提出了通过修改事务相应的项目来实现序列模式中隐私数 据保护的方法i t - p p s p m ，该方法既可以实现隐私数据的有效保护，又能确保序 列模式挖掘结果的有效可行性。 3 、分析研究了分布式序列模式挖掘算法的分合思想，结合关联规则挖掘中 实现隐私保护的思想，研究并提出了一种分布式序列模式挖掘的隐私保护算法 l d s a ，该方法通过删除原始序列来降低敏感序列的支持数来达到隐藏的目的。 4 、综合本文的研究成果，设计了基于隐私保护的分布式序列模式挖掘系统。 该系统主要包括数据预处理、隐私数据处理、敏感序列处理和分布式序列模式挖 掘四个功能模块。 关键字：数据挖掘，分布式数据挖掘，序列模式，隐私数据，敏感序列 江苏大学硕士学位论文 a b s t r a c t i nt h ep r o c e s so fs e q u e n t i a lp a t t e r nm i n i n g ，p r i v a c yi sm u s tt ob et a k e ni n t o c o n s i d e r a t i o n ，e s p e c i a l l yi nt h ed i s t r i b u t e de n v i r o n m e n t c u r r e n tp r i v a c yp r e s e r v i n g a l g o r i t h mo fd i s t r i b u t e dd a t am i n i n gm a i n l yc o n c e r nw i t ht h ea s s o c i a t i o nr u l e sm i n i n g ， t h er e s e a r c ho ft h ep r i v a c yp r e s e r v i n gf o rs e q u e n t i a lp a t t e r nm i n i n gw a sl a c k i n g t h e r e f o r e ，i ti s o fh i g hv a l u a b l ef o ra c a d e m i cs t u d ya n do fm o m e n t o u sc u r r e n t s i g n i f i c a n c ef o rs t u d y i n gt h ep r i v a c yp r e s e r v i n gb a s e dd i s t r i b u t e ds e q u e t i a l p a t t e r n m i n i n gi nd e p t h t h i sp a p e ri n t r o d u c e st h es t a t u sa n db a s i ck n o w l e d g eo fd i s t r i b u t e ds e q u e n t i a l p a t t e r nm i n i n gm e t h o do fp r i v a c yp r e s e r v i n g a th o m ea n da b r o a d a n dm a i n l y i n t r o d u c e st h ed i s t r i b u t e ds e q u e n t i a lp a t t e r nm i n i n ga n dp r i v a c yp r e s e r v i n gm e t h o d f o rt h ee x i s t i n gm e t h o d so fp r i v a c yd a t ap r e s e r v i n gm a ya f f e c tt h ea v a i l a b i l i t ya n d v a l i d i t yo ft h es e q u e n t i a lp a t t e r nm i n i n gr e s u l t s ，am e t h o do fp r e s e r v i n gd i s t r i b u t e d s e q u e n t i a lp a t t e r np r i v a c yd a t ai sp u tf o r w a r d i no r d e rt om a k eu pf o ri n s u f f i c i e n t m e t h o d so fs e q u e n t i a lp a t t e r nm i n i n gi nt h ed i s t r i b u t e de n v i r o n m e n t ，am e t h o do f p r e s e r v i n gs e n s i t i v es e q u e n c ea c c o r d i n gt o ah i d d e nt h o u g h ti na s s o c i a t i o nr u l e m i n i n gi sp u tf o r w a r d a n dad i s t r i b u t e ds e q u e n t i a lp a t t e mm i n i n gp r o t o t y p es y s t e m w a sd e s i g n e da n di m p l e m e n t e db a s e do ns e q u e n t i a lp a t t e mm i n i n gi nt h ep r e s e r v i n g o fp r i v a t ed a t aa n ds e n s i t i v es e q u e n c ea l g o r i t h m t h em a i na c h i e v e m e n t sa b o u tt h i sp a p e ra r ed e s c r i b e da sf o l l o w s ： 1 s u m m a r i z et h er e s e a r c hs i t u a t i o no ft h e s e q u e n t i a lp a t t e r nm i n i n gi n d i s t r i b u t e d p r i v a c yp r e s e r v i n g i n t r o d u c et h ec l a s s i cs e q u e n t i a lp a t t e mm i n i n g a l g o r i t h m a n ds t u d yo nt h es e q u e n t i a lp a t t e r nm i n i n ga l g o r i t h mo fh i d d e np r i v a t e d a t aa n ds e n s i t i v es e q u e n c e 2 f o rt h ee x i s t i n gm e t h o d so f p r i v a c yd a t ap r e s e r v i n gm a ya f f e c tt h ea v a i l a b i l i t y a n de f f e c t i v e n e s so ft h es e q u e n t i a lp a t t e r nm i n i n gr e s u l t s ，ap r i v a c yd a t ap r e s e r v i n g m e t h o dw h i c hb ym o d i f y i n gt h ei t e m so ft h et r a n s a c t i o nt oa c h i e v et h ep r i v a c y p r e s e r v i n gi sp u tf o r w a r d t h i sm e t h o dn o to n l yc a l lp r o t e c tt h ep r i v a t ed a t ae f f i c i e n t l y ， i i i 江苏大学硕士学位论文 b u ta l s oa s s u r et h et h ea v a i l a b i l i t ya n de f f e c t i v e n e s so ft h es e q u e n t i a lp a t t e r nm i n i n g r e s u l t s 3 a c c o r d i n gt oa n a l y z i n gt h ed i v i s i o nt h o u g h to fd i s t r i b u t e ds e q u e n t i a lp a t t e r n m i n i n ga l g o r i t h m s ，c o m b i n i n gw i t ht h et h o u g h to fp r i v a c yp r e s e r v i n gi na s s o c i a t i o n r u l em i n i n g ，ad i s t r i b u t e dp r i v a c yp r e s e r v i n gs e q u e n t i a lp a t t e mm i n i n ga l g o r i t h m l d s ai sp u tf o r w a r d i tc a nh i d ew e l lb yr e d u c i n gt h es u p p o r tn u m b e ro fs e n s i t i v e s e q u e n c e 4 a c c o r d i n gt ot h er e s u l t so ft h i ss t u d y ，ad i s t r i b u t e ds e q u e n t i a lp a t t e r nm i n i n g p r o t o t y p es y s t e mw a sd e s i g n e da n di m p l e m e n t e db a s e do ns e q u e n t i a lp a t t e r nm i n i n g i nt h ep r e s e r v i n go fp r i v a t ed a t aa n ds e n s i t i v e s e q u e n c ea l g o r i t h m t h es y s t e m i n c l u d e sf o u rf u n c t i o n a l m o d u l e s ，i n c l u d i n gd a t ap r e p r o c e s s i n g ，p r i v a c yd a t a p r o c e s s i n g ，s e n s i t i v es e q u e n c ep r o c e s s i n ga n dd i s t r i b u t e ds e q u e n t i a lp a t t e r nm i n i n g k e yw o r d s ：d a t a m i n i n g ，d i s t r i b u t e dd a t am i n i n g ，s e q u e n t i a lp a t t e r n ，p r i v a c yd a t a , s e n s i t i v es e q u e n c e i v 目录 第一章绪论。1 1 1 课题研究背景与意义。1 1 2 国内外研究现状2 1 2 1 分布式序列模式挖掘中隐私数据保护的研究现状。2 1 2 2 分布式序列模式挖掘中敏感序列保护的研究现状4 1 3 本文研究内容6 1 4 本文的结构7 第二章分布式序列模式挖掘及其隐私保护方法概述8 2 1 数据挖掘预备知识8 2 1 1 数据挖掘的基本概念和步骤8 2 1 2 数据挖掘方法的分类9 2 2 序列模式挖掘l0 2 2 1 基本概念及定义1 1 2 2 2 序列模式挖掘的一般步骤1 2 2 2 3 经典序列模式挖掘算法研究1 3 2 3 分布式序列模式挖掘1 7 2 3 1 分布式序列模式挖掘的基本定义和性质1 7 2 3 2 分布式序列模式挖掘的方法1 9 2 4 隐私保护算法研究2 0 2 4 1 隐私数据保护算法的研究2 0 2 4 2 敏感序列保护算法的研究2 2 2 4 3 隐私保护算法的评价标准2 3 2 5 本章小结2 4 第三章分布式序列模式挖掘中敏感序列的保护算法2 5 3 1 分布式序列模式挖掘中敏感序列保护方法的基本知识2 5 3 1 1 敏感序列模式保护2 5 3 1 2 分布式敏感序列保护算法的度量指标2 6 3 2 分布式敏感序列保护算法l d s a 2 8 3 2 1l d s a 算法的基本思想2 8 3 2 2l d s a 算法权值的选择与更新3 0 3 2 3l d s a 算法流程的描述3 0 3 3 算法实验结果及分析3 5 3 3 1 实验数据和实验环境3 5 3 3 2 算法实验性能比较3 6 3 4 本章小结3 9 第四章分布式序列模式挖掘中隐私数据的保护算法。4 0 4 1 相关定义及主要性质4 0 4 2 面向隐私数据保护的分布式序列模式挖掘方法i t - p p s p m 4 1 4 2 1 i t - p p s p m 算法的基本思想4 1 4 2 2 隐私数据项的确定4 2 4 2 3 隐私数据项的修改4 2 4 2 4 记录的整型化4 2 4 2 5 数据的传输4 3 v 江苏大学硕士学位论文 4 2 6 隐私数据项的恢复4 3 4 2 7 序列模式的挖掘4 3 4 3 算法实验结果及分析4 7 4 3 1 算法评价标准4 7 4 3 2 算法实验结果4 8 4 3 3i t - p p s p m 算法的结果分析4 9 4 4 本章小结5 0 第五章基于隐私保护的分布式序列模式挖掘原型系统。5 l 5 1 系统模型介绍5 1 5 2 系统设计思想及结构5 2 5 2 1 数据预处理模块5 2 5 2 2 隐私数据处理模块5 3 5 2 3 敏感序列处理模块5 4 5 2 4 分布式序列模式挖掘模块5 5 5 3 原型系统的实现5 6 5 3 1 系统开发环境5 6 5 3 2 系统运行环境5 6 5 3 3 系统运行的流程5 6 5 4 本章小结5 7 第六章总结与展望5 8 6 1 本文总结5 8 6 2 进一步研究工作5 8 善 考文献6 0 致谢6 4 附录一i 读研期间发表和录用论文目录6 5 v i 1 1 课题研究背景与意义 数据挖掘【l 】是数据库技术与人工智能技术相结合的产物，旨在从大量的、有 噪声的、随机的、模糊的数据库中挖掘出事先未知但又是潜在有用的知识和规律， 以帮助人们正确理解和认识数据并进行科学决策。序列模式挖掘【2 ，3 1 是数据挖掘 技术中一个新兴的研究方向，即从序列数据库中发现频繁子序列以作为模式，它 是指挖掘出相对时间或其它出现频率高的模式。它是一类重要的数据挖掘问题， 有着非常广泛的应用前景，包括顾客购买行为的分析、网络访问模式分析、自然 灾害预测等等。 然而随着现实生活中数据集规模的迅速增长，海量的数据使得传统的单计算 机系统在功能和性能上已不能满足对数据处理能力的需要，由网络连接多台计算 机所构成的分布式系统己成为当今的主流系统。对于分布式的序列数据，在单机 系统上执行挖掘算法所得到的序列模式只是针对局部数据有效的，无法获得对分 布式系统中所有数据全局有效的序列模式。如何有效地挖掘如此巨大且分布式存 放的数据集，越来越多的分布式序列模式挖掘算法应用而来。 随着分布式序列模式挖掘技术的发展，人们可以快速地从海量数据中获取有 用的信息。然而任何事情都有其利弊，在人们获取有价值信息的同时，隐私信息 的泄露将成为一个不可忽视的问题。目前，在分布式序列模式挖掘中，参与挖掘 的各个数据拥有者出于自身利益的考虑，不想泄露自己的隐私数据和其中蕴含的 敏感序列。因此，如何既能挖掘到准确的结果，又能保证各参与方的隐私不被泄 露成为分布式序列模式挖掘所要研究的主要内容，在分布式序列模式挖掘过程中 解决好隐私保护问题已经成为数据挖掘领域中的一个非常关键的问题。 一般情况下，隐私保护问题包含两个方面的问题1 4 l ：一是数据库中敏感序列 模式的保护1 5 j ，所谓敏感序列模式是指数据拥有者不愿公开的模式，这些模式的 不法使用可能会威胁到数据拥有者的权益；二是隐私数据的保护【5 】【6 1 ，隐私数据 是指数据拥有者不愿公开的数据，它可能包括姓名、身份证号、银行帐号、住址、 工资等。 江苏大学硕士学位论文 对于敏感序列模式的保护问题，目前常用的方法是借鉴关联规则隐藏的思 想，通过删除原始序列降低支持数的方式实现了敏感序列的隐藏。由于这些方法 都在删除过程执行之前就确定好被删除的敏感序列，而且没有考虑先删除的序列 对后删除的序列的影响。这样会删除掉可以不必删除的序列。因此，我们可以通 过在被删除序列的选择过程中采用贪心算法，尽可能减少被删除序列的数量，降 低非敏感规则丢失率。 对于隐私数据的保护问题，目前常用的方法是采取数据干扰技术，即通过数 据变换或在数据中增加噪声等方法来对隐私数据进行干扰，序列模式挖掘是在干 扰后的数据集上进行的，因而，该种方法很有可能影响到挖掘结果的可用性和有 效性，即挖掘出一些原始数据库中本来不存在的且有误导作用的规则，丢失一些 原始数据库中存在的非常有用的规则，从而失取了数据挖掘本身的意义。因此， 我们可以通过修改事务相应的项目来实现隐私数据的保护。 由此可见，对分布式环境下序列模式挖掘隐私保护问题的研究不仅具有重要 的理论意义，而且具有非常广泛的应用前景。 1 2 国内外研究现状 1 2 1 分布式序列模式挖掘中隐私数据保护的研究现状 1 9 9 5 年a g r a w a l 和s r i k a n t 针对消费者的购买序列提出了序列模式挖掘的算 分，此后产生了很多序列模式挖掘算法，最初都是针对单机环境设计运行的。1 9 9 5 年s r i k a n t 和a g r a w a l 在文献 7 a e 首次提出了序列模式挖掘算法a p r i o d a l l 。1 9 9 6 年 他们又在文献 8 】中提出了一种基于a p r i o r i 的改进算法g s p ( g e n e r a l i z e ds e q u e n t i a l p a t t e r n s ) ，此算法对序列规定了时间限制、滑动时间窗口和用户规定的分类，并 在文中总结了序列模式的定义。文献 9 】中提出了经典的频繁序列模式挖掘及更 新算法d y n a m i c s o m e ，该算法的候选序列模式不是在前半部分产生，而是在中间 阶段产生，从而提高了效率。以上所提出的大多数算法是基于a p r i o d ，该方法需 要多次构造哈希树，其运算量是很大的。 随着分布式计算技术的发展和应用领域的扩大，分布式序列模式挖掘的研究 也越来越多。文献 1 0 】提出了基于树投影技术的两种不同的并行算法来解决分布 2 学位论文 式环境中序列模式发现的问题。针对数据水平分布的序列模式挖掘问题，文献【1 1 】 提出了通过语法序列树减小数据传输量的d m g s p 算法，文献【1 2 】提出了d m s p 算 法。文献【1 3 】对分布式环境下的序列模式挖掘算法的并行执行进行了研究，指出 了算法研究的重点。但是对于分布式序列模式挖掘过程中的隐私问题却没有考 虑。 隐私保护技术作为新兴的研究热点课题，不论在理论研究还是实际应用方面 都有非常重要的研究价值。从隐私保护问题提出之后，产生了很多隐私保护算法， 如数据扰乱技术1 4 , 1 5 1 、阻挡技术 1 6 , 1 7 1 、重建技术等。2 0 0 0 年，文献 1 9 ，2 0 】同 时从两个不同的角度提出了两种不同的隐私保护数据挖掘问题，并分别采用数据 扰乱技术和安全多方计算协议加以解决，推动了相关技术的研究。文献 1 9 提出 了一种基于随机化的方法一一随机响应技术，利用这种源于统计学研宄中隐私保 护的方法，来实现在不泄露隐私数据的情况下进行一定精度的建模，文中主要探 讨了与i d 3 决策树算法结合进行分类的方法。文献【2 0 】将这种技术与其他数据挖 掘算法进行结合，设计了其他算法框架。文献【2 l 】针对数据库动态更新的序列模 式挖掘的隐私保护问题提出了解决方法，通过增加噪声数据的方法来对隐私数据 进行保护，并能保证挖掘结果的准确性。 z h a n ge t a l 提出了序列模式挖掘的隐私保护方法1 2 2 1 。用于解决分布式两方或 者三方序列数据库挖掘中隐私数据保护的问题。由于此方法不能用于大于三方的 分布式序列模式挖掘，j u s t i nz h a n 于2 0 0 7 年提出了一种使用同态加密技术对分 布式序列模式挖掘中的隐私数据进行保护的方法 2 3 1 ，该方法适用于多方分布式 序列模式挖掘，并且在数据挖掘过程中隐私数据的泄露达到最小。 文献 2 4 ，2 5 中，将分布式环境下关联规则挖掘中的安全多方计算方法运用到 序列模式挖掘中，文献 2 4 】将关联规则挖掘中隐私保护的同态加密思想引入到序 列模式发现算法，给出两方参与的序列模式隐私保护算法。在此基础上，文献 2 5 】 将两方问题推广至多方，提出了安全多方参与序列模式挖掘的隐私保护算法，并 且从理论上分析证明了协议的私密性和正确性。但该方法加密过程比较复杂，运 算量比较大。 文献 2 6 1 中提出了基于数据干扰的保密序列模式发现算法，为了保留序列数 据库中的原有数据，在客户交易序列中随机插入若干事件，然后利用已有的序列 3 江苏大学硕士学位论文 模式发现算法从处理后的序列数据库中发现所有可能的频繁序列，再逐层重构这 些频繁序列在原序列数据库中的支持度，从而得到真正的序列模式。实验表明该 方法简单并容易实施，支持度重构的准确性比较高。但是对挖掘结果的可用性和 有效性还是有一定的影响。 1 2 2 分布式序列模式挖掘中敏感序列保护的研究现状 关于序列模式挖掘中敏感序列的隐私保护，s r m o l i v e i r a 及o r z a i a n e 于 2 0 0 2 年提出了一种序列模式隐藏算法【2 7 】。算法是以隐私阈值( p r i v a c yt h r e s h o l d ) 来做开放程度的控制，由使用者控制隐私阈值，使使用者能自行控制信息开放的 程度，用来在取得隐私权和合法取得数据之间获得一种平衡。这个隐私权闽值介 于0 1 0 0 之间，当隐私权阈值为0 时，表示没有任何受限制的隐私规则可以 被挖掘出来；当隐私权阈值为1 0 0 时，表示没有任何限制，即所有的隐私序列 都可以被挖掘出来。通过这种方式可以让共享信息更具有弹性，使用者可以针对 不同的共享对象采用不同的开放程度。但s r m o l i v e i r a 和o r z a i a n e 所提出的隐 私权阈值仅能模糊控制开放的程度，它无法了解隐私阂值与接收者使用的最小支 持度之间会有何种关系，即不能保证在数据接收者以何种最低支持度挖掘的情况 下，才能达到对隐私数据的保护。 为了进一步了解处理后的状况，国内学者使用另外一种能够比较容易了解隐 藏的敏感序列保护情况的参数，称之为预期最小支持度。文献【2 8 】中就文献【2 7 】 的问题首次提出了三个敏感序列隐藏算法一一m s a 、m s r a 和s d i 心。这三种算 法都采用了预期最小支持度来保证敏感序列的隐藏效果，算法借鉴了关联规则隐 藏的思想，通过删除原始序列降低支持数的方式实现了敏感序列的隐藏。但m s a 和m s r a 算法在选择被删除序列时没有做任何优化，s d r f 对候选删除序列只进 行了基本的筛选，仍存在删除原始序列过多的问题，而且算法引入的预期最小支 持度可能会导致敏感序列隐藏失败情况的出现。由于这三种算法都采用了预期最 小支持度来保证敏感序列的隐藏效果，它们在删除过程执行之前就确定好了被删 除的原始序列，不能动态反映出已删除序列对未删除序列的影响，删除掉了一些 不必要删除的序列，某些序列模式也会被意外隐藏，还可能产生一些虚假模式。 文献 2 9 1 针对复杂形式的序列模式提出了一种有效的敏感序列保护方法，通 4 学位论文 过很少的数据干扰来达到对敏感序列的隐藏，使得敏感序列得到了很好的保护。 而且，为了从候选方法中找到最好的序列标准化方法，提出了一种高效的权重计 算方法。 燕彩荣提出了一种基于隐私保护的序列模式挖掘算法p p s p m 3 0 1 ，通过修改 原始数据库中的隐私数据，使得受限序列模式的支持度降低，从而达到隐藏隐私 的目的。但是该方法在对数据库进行修改前要建立客户的模式贡献表，根据贡献 值的大小来修改客户数据。这样做可以避免在大多数模式都需要的客户数据上修 改，减少非受限模式的损失，但是个别贡献小的客户数据中可能隐藏着一些重要 的敏感序列，可能会被泄露。而且该方法只针对单机的序列模式挖掘的隐私保护 研究，没有扩展到分布式环境下。 对于分布式序列环境下序列模式挖掘的隐私保护研究，v i s h a lk a p o o r 等人 于2 0 0 6 年提出了针对分布式数据库挖掘序列模式的p p s p 算法【3 l 】，它是以s p a m 算法为基础，为了有效地计算支持度，将每个客户的事务用垂直位图表示，在挖 掘的过程中对敏感序列进行了保护。从效率和功能来看这个算法更适合于挖掘现 实生活中的数据。 文献 3 2 1 针对分布式环境下敏感序列保护的问题提出了的序列模式保护方 法c l s d ，通过删除原始序列来降低支持数以达到敏感序列隐藏的目的，在执行 挖掘操作之前对原始数据集进行处理防止敏感序列被挖掘出来。但是对于数据通 信过程中的安全性没有很好的考虑。 综上所述，尽管国内外对序列模式挖掘的隐私保护方法已经展开了深入研 究，并取得了一定进展，但仍存在以下几个方面的不足： ( 1 ) 在确定候选频繁序列模式以及计算候选频繁序列模式支持数的过程中， 没有考虑算法的效率问题，以上所提出的大多数算法是基于a p r i o r i ，该方法需 要多次构造哈希树，其运算量是很大的。 ( 2 ) 对于隐私数据保护的研究，没有充分考虑对挖掘结果的可用性和准确 性影响，即挖掘出一些原始数据库中本来不存在的且有误导作用的规则，丢失一 些原始数据库中存在的非常有用的规则。 ( 3 ) 没有考虑先删除的序列对后删除的序列的影响。这样可能会删除掉可 以不被删除的序列，影响了挖掘结果的正确性。 江苏大学硕士学位论文 ( 4 ) 对于分布式环境下多台计算机同时挖掘序列模式的问题研究较少。各 个站点之间传输的中间数据过多因此网络通信量较大，并且数据在通信过程中的 安全性受到威胁。 为此，本文首先根据现有序列模式挖掘中隐私数据保护算法，提出了面向隐 私数据保护的分布式序列模式挖掘方法，并从隐私数据的隐藏程度以及挖掘结果 的准确性两方面对该方法进行了分析比较。实验结果表明该算法既可以有效的保 护隐私数据，又能确保序列模式挖掘结果的准确性。其次对序列模式挖掘中敏感 序列保护的算法进行深入研究，结合关联规则挖掘中规则隐藏的算法，提出了一 种改进的分布式敏感序列保护算法。实验结果表明，改进的算法能够更有效地实 现敏感序列的完全隐藏，并且不会产生虚假模式，提高了算法的性能。最后，构 建了一个基于隐私保护的分布式序列模式挖掘原型系统，进一步论证了本文所提 方法的有效性和可行性。 1 3 本文研究内容 本文主要研究分布式序列模式挖掘的隐私保护问题，分别对分布式环境下序 列模式挖掘中隐私数据和敏感序列的保护问题进行了探讨，通过理论分析与模拟 实验验证相结合的方式，提出改进的方法。 本文的主要工作内容包括： ( 1 ) 总结了分布式序列模式挖掘中隐私保护的研究现状，介绍了经典的序 列模式挖掘算法，对序列模式挖掘中隐私数据和敏感序列隐藏算法进行研究。 ( 2 ) 针对现有分布式隐私数据保护方法可能会影响到序列模式挖掘结果的 可用性和有效性等问题，提出了通过修改事务相应的项目来实现序列模式中隐私 数据保护的方法i t - p p s p m ，该方法既可以实现隐私数据的有效保护，又能确保 序列模式挖掘结果的有效可行性。 ( 3 ) 分析研究了分布式序列模式挖掘算法的分合思想，结合关联规则挖掘 中实现隐私保护的思想，研究并提出了一种分布式序列模式挖掘的隐私保护算法 l d s a ，该方法通过删除原始序列来降低敏感序列的支持数来达到隐藏的目的。 。( 4 ) 综合本文的研究成果，设计了基于隐私保护的分布式序列模式挖掘系 统。该系统主要包括数据预处理、隐私数据处理、敏感序列处理和分布式序列模 6 江苏大学硕士学位论文 式挖掘四个功能模块。 1 4 本文的结构 本文在分析了分布式序列模式挖掘和隐私保护理论的基础上，主要对分布式 序列模式挖掘中隐私数据和敏感序列保护这两个主要问题进行研究，并提出了相 应的解决方法。本文共分六章，各章节具体安排如下： 第一章绪论 介绍本文的研究背景及意义、国内外的研究现状、研究内容及主要工作和各 章节内容安排。 第二章分布式序列模式挖掘及其隐私保护方法概述 首先介绍了数据挖掘和序列模式挖掘的基本知识，给出了经典的序列模式挖 掘算法。然后对分布式序列模式数掘进行了简要介绍，并对序列模式挖掘的隐私 保护算法进行了简要介绍和分析。 第三章分布式序列模式挖掘中敏感序列的保护算法 介绍了分布式序列模式挖掘中敏感序列保护的相关知识、定义及定理，提出 了一种分布式序列模式挖掘中敏感序列保护的算法l d s a 。概述了模拟实验的系 统环境及具体配置，给出了实验结果及分析。 第四章分布式序列模式挖掘中隐私数据的保护算法 介绍了分布式序列模式挖掘中隐私数据保护的基本定义，针对现有的隐私数 据保护方法可能会影响到序列模式挖掘结果的可用性和有效性等问题，提出了一 种基于项目变换的面向隐私数据保护的分布式序列模式挖掘算法。并通过模拟实 验对算法的隐私性和准确性进行了验证。 第五章基于隐私保护的分布式序列模式挖掘原型系统 综合本文的研究成果，设计了基于隐私保护的分布式序列模式挖掘系统。该 系统主要包括数据预处理、隐私数据处理、敏感序列处理和分布式序列模式挖掘 四个功能模块。 第六章总结与展望 总结本文的研究工作，根据自己的研究成果和体会，确定下一步研究工作的 重点及方法。 7 江苏大学硕士学位论文 第二章分布式序列模式挖掘及其隐私保护方法概述 本章首先介绍了数据挖掘和序列模式挖掘的基础知识，并阐述了几种经典的 序列模式挖掘算法。其次介绍了分布式序列模式挖掘的基础知识。最后介绍了隐 私保护算法中关于隐私数据和敏感序列保护的经典算法。 2 1 数据挖掘预备知识 数据挖掘是一个多学科交叉研究领域，它融合了数据库技术、人工智能、机 器学习、统计学、知识工程、面向对象方法、信息检索、高性能计算以及数据可 视化等最新技术的研究成果。概括地说，数据挖掘技术是人工智能和数据库两个 分支学科发展和演进的结果。用数据库管理系统来存储和管理数据，用人工智能 中机器学习技术来分析数据，挖掘大量数据背后隐蔽的知识，这两者的结合促成 了数据挖掘技术【3 3 】的产生。 2 1 1 数据挖掘的基本概念和步骤 数据挖掘( d a t am i n i n g ) ，又称数据库中的知识发现( k n o w l e d g ed i s c o v e r yi n d a t a b a s e ) 。一种比较公认的数据挖掘定义是：从大量的、不完整的、有噪声的、 模糊的、随机的实际应用数据中，提取隐含在其中的、人们事先并不知道的、 具有潜在价值的信息和知识的过程。提取的知识表示为概念( c o n c e p t s ) 、规则 ( r u l e s ) 、规律( r e g u l a t i o n s ) 、模式( p a t t e m s ) 、约束( c o n s t r a i n t s ) 、可视化 ( v i s u a l i z a t i o n s ) 等形式。简单的说，数据挖掘就是从大量数据中提取或挖掘出对 人类有用的知识。 数据挖掘实施的步骤主要有三个阶段：数据准备、数据挖掘、结果的评价 和表达【3 4 1 。也可细分为：数据准备、清除脏数据、数据挖掘、表达、评价五个 阶段。 ( 1 ) 数据准备 此阶段将从数据库中提取和分析与任务相关的数据。首先清除噪声、读入 的脏数据和不一致的数据，然后对数据进行集成并删除一些无用的数据并对数 8 ( 2 ) 数据挖掘 此阶段将采用合适的数据挖掘方法，分析经过预处理的数据并从中提取相 关的规则。简单地说，就是用智能的方法提取数据模式。 ( 3 ) 结果表达与评价 此阶段将以用户可以理解和观察的方式输出数据挖掘中获取的特征和规 则，然后对数据挖掘中所发现的特征和规则进行评价，再根据某种兴趣度度量 识别真正有趣的模式。 2 1 2 数据挖掘方法的分类 数据挖掘的任务是从大量的数据中发现模式，所谓模式是指关于数据集的某 种抽象描述。一般而言，模式按照其作用的不同可以分为两大类：预测型模式( 如 序列模式、分类模式、回归模式、偏差分析等) 和描述型模式( 如聚类模式、关联 模式等) 。预测型模式能够根据已有的数据集，预测某些未知的未来数据项的值。 描述型模式是对数据中存在的规律、规则作出一种描述，或者根据数据间的相似 性将数据分组，它一般不能直接用于预测。 数据挖掘技术分析方法很多，在此仅列举目前常用的几种技术1 3 引。 ( 1 ) 关联分析( a s s o c i a t i o na n a l y s i s ) 关联规则挖掘是由r a k e s ha p w a l 等人首先提出的。两个或两个以上变量的 取值之间存在某种规律性，就称为关联。数据关联是数据库中存在的一类重要的、 可被发现的知识。关联分为简单关联、时序关联和因果关联，关联分析的目的是 找出数据库中隐藏的关联网。一般用支持度和置信度两个阈值来度量关联规则的 相关性，并且不断引入兴趣度、相关性等参数，使得所挖掘的规则更符合需求。 ( 2 ) 聚类分析( c l u s t e r i n ga n a l y s i s ) 聚类是将数据按照相似性归纳成若干类别，同一类中的数据彼此相似，不同 类中的数据相异。聚类分析可以建立宏观的概念，发现数据的分布模式，以及可 能的数据属性之间的相互关系。 ( 3 ) 分类( c l a s s i f i c a t i o n ) 分类是对一个类别的概念描述，它代表了这类数据的整体信息，即该类的本 9 江苏大学硕士学位论文 质描述，并用这种类别描述来构造模型，一般用规则或决策树模式表示。分类是 通过一定的算法对训练数据集进行处理而得到的分类规则。分类可用于规则描述 和预测。 ( 4 ) 序列模式( s e q u e n t i a lp a t t e r n ) 序列模式是由r a k e s ha g r a w l 等人提出的又一重要的k d d 研究课题，它是 从序列数据库中发现相对时问或者其他顺序所出现的高频率子序列。其最初动机 是通过在带有交易时间属性的交易数据库中发现频繁序列，以发现某一段时间内 客户的购买活动规律。 ( 5 ) 预测( p r e d i c t i o n ) 预测是利用历史数据找出变化规律来建立模型，并根据此模型对未来数据的 种类及特征进行预测。预测所关心的是精度和不确定性，通常用预测方差来度量。 ( 6 ) 时序模式( t i m es e r i e sp a t t e r n ) 时序模式是指通过时间序列挖掘出的重复概率较高的模式。与回归一样，它 也是用己知的数据预测未来的值，但这些数据的区别是变量所处时间的不同。 ( 7 ) 偏差分析( d e v i a t i o n ) 在偏差中包括很多有用的知识，数据库中的数据存在很多异常