（计算机应用技术专业论文）基于隐私保护的关联规则挖掘研究.pdf

中国民航大学硕士学位论文 摘要 随着信息技术、网络技术、数据存储技术和高性能处理器技术的快速发展，数据的 收集和管理变得越来越方便。数据挖掘技术可以从收集到的大量数据集中挖掘出潜在的 知识，这就可能把涉及到个人隐私的信息挖掘出来，从而产生了隐私保护下的数据挖掘。 首先阐述了数据挖掘的基本理论和隐私保护关联规则挖掘的国内外研究现状，然后 从输入隐私和输出隐私两个角度对隐私保护关联规则的挖掘方法进行了研究。 输入隐私方面研究了国外学者提出的m a s k 算法和对m a s k 算法进行改进的 e m a s k 算法，m a s k 算法估算，l 一项集真实支持度需要计算c r m 。c d ，其中m 是阶 数为k ( 七；2 ”，甩一l2 ，3 ) 的概率变换矩阵，计算m 。的时间复杂度为o ( k 3 ) 。本文将分 治策略运用到m a s k 算法，提出了改进的m a s k 算法，提出了递归计算2 4 阶m 。1 的方法， 计算m 。1 的时间复杂度仅为o ( k ) ，比原m a s k 算法计算m 。的时间复杂度提高了两个数 量级。实验结果表明改进的m a s k 算法时间效率比原m a s k 算法有了提高。在不考虑空 间开销的前提下，本文又将分治策略运用到e m a s k 算法，提出了改进的e m a s k 算法。 e m a s 玲睁，l 一项集对应的m 从2 4 阶降维到t l + 1 的阶数，计算该，l + 1 阶矩阵m 以的时间复 杂度为o ( n 4 1 。改进的e m a s k 算法仍然认为m 是2 “阶的，提出了计算m 。1 的递归方法， 时间复杂度为0 ( 2 “) 。理论分析表明在项集咒较小时，改进的e m a s k 算法计算n 一项集 对应的m 1 时间复杂度比原e m a s k 算法低。实验结果表明本文对e m a s k 算法的改进是 有意义的。 从输出隐私的角度研究了保护敏感规则的关联规则挖掘方法，给出了保护敏感规则 的三种算法并分析了算法的时间有效性。 关键词：关联规则，隐私保护，输入隐私，输出隐私，敏感规则，效率 中国民航大学硕士学位论文 a b s t r a c t w i t ht h ed 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 、n e t w o r kt e c h n o l o g y 、d a t as t o r a g e t e c h n o l o g ya n dh i g h l ye f f i c i e n tp r o c e s s o rt e c h n o l o g y , t h ec o l l e c t i n ga n dm a n a g i n gd a t a b e c o m em o r ea n dm o r ee a s y t h ek n o w l e d g ew h i c hi sp o t e n t i a la n dh i d d e n b e h i n dl o t so fd a t a c a nb em i n e di nm e a n so fd a t am i n i n gt e c h n o l o g ya n dp a r to ft h ek n o w l e d g em a yi n f r i n g e p e r s o n a lp r i v a c y t h eb a s i ct h e o r yo fd a t am i n i n ga n dt h ec u r r e n tr e s e a r c hs i t u a t i o no fa s s o c i a t i o nr u l e m i n i n gb a s e do np r i v a c yp r e s e r v i n ga r es t u d i e d t h e n ，a s s o c i a t i o nr u l em i n i n gb a s e do n p r i v a c yp r e s e r v i n gi ss t u d i e df r o ma s p e c t so fi n p u tp r i v a c ya n do u t p u tp r i v a c y f r o mi n p u tp r i v a c ya s p e c t ，m a s ka l g o r i t h ma n de m a s k a l g o r i t h mw h i c h i si m p r o v e d o nt h eb a s i so fm a s ka r ei n t r o d u c e d t h ee q u a t i o nc r m 一1 c di sc o m p u t e dt or e c o n s t r u c t t h er e a l s u p p o r t o f，l i t e m s e ti nm a s k a l g o r i t h m t h e o r d e ro fm 一1i s k ( k = 2 “，l = l 2 ，3 ) ，t h e n t h et i m e c o m p l e x i t y o fc o m p u t i n gm 一1i s o ( k 3 ) t h e d i v i d e - a n d - c o n q u e rs t r a t e g yi sa p p l i e dt om a s ka n da ni m p r o v e dm a s ka l g o r i t h mi s p r e s e n t e di nt h i sp a p e r am e t h o do fc o m p u t i n gk - b y km a t r i xm 一1i ss t u d i e da n dt h et i m e c o m p l e x i t yi so n l y0 ) t h ee x p e r i m e n ts h o w st h er u n t i m ee f f i c i e n c yo fm a s ki sb e t t e r t h a no r i g i n a lm a s k t h e nt h ed i v i d e a n d - c o n q u e rs t r a t e g yi sa p p l i e dt oe m a s k a g a i na n d a ni m p r o v e de m a s k a l g o r i t h mi sp r e s e n t e d t h eo r d e ro fmc o r r e s p o n d e db yn - i t e m s e ti s r e d u c e df r o m2 4t o 刀+ 1i ne m a s kw h i l ei t ss t i l l2 “i ni m p r o v e de m a s k ar e c u r s i o n m e t h o do fc o m p u t i n gm 一1i sd i s c o v e r e di ni m p r o v e de m a s ka n dt h et i m ec o m p l e x i t yi s 0 ( 2 ”) w h i l et h et i m ec o m p l e x i t yo fo r i g i n a le m a s k i s o ( n 4 ) w h e nn - i t e m s e ti ss m a l l e r ， t h ec o m p l e x i t yo fc o m p u t i n gm i ni m p r o v e de m a s ki sb e t t e rt h a no r i g i n a le m a s k a t l a s t ，e x p e r i m e n ts h o w st h ei m p r o v e de m a s k i ss i g n i f i c a n t f r o mo u t p u tp r i v a c ya s p e c t ，t h ei d e at op r e s e r v es e n s i t i v er u l e si ss t u d i e d t h r e e e f f e c t i v ea l g o r i t h m sa r ep r e s e n t e df o rp r e s e r v es e n s i t i v er u l e s t h e nt h et i m ee f f e c t i v i t yo ft h e a l g o r i t h m si sa n a l y z e d k e y w o r d s ：a s s o c i a t i o nr u l e ，p r i v a c yp r e s e r v i n g ，i n p u tp r i v a c y , o u t p u tp r i v a c y , s e n s i t i v e r u l e ，e f f i c i e n c y i i 中国民航大学学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。 尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过 的研究成果，也不包含为获得中国民航大学或其它教育机构的学位或证书而使用过的材料。 与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 研究生签名：期：垡多：多：? 中国民航大学学位论文使用授权声明 中国民航大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的 复印件和电子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和 纸质论文的内容相一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包 括刊登) 论文的全部或部分内容。论文的公布( 包括刊登) 授权中国民航大学研究生部办理。 研究生签名： 导师签名：b 晰日期： 中同民航大学删l 。学址论立 1 1 数据挖掘简介 第一章绪论 数据挖掘是二十世纪9 0 年代兴起的一项新技术，是从大量的、不完全的、有噪声的、 模糊的、随机的数据集中识别有效的、新颖的、潜在有用的以及最终可理解的模式的过 程。它是一门涉及面广泛的交叉学科，包括机嚣学习、数理统计、神经网络、数据库、 模式识别、粗糙集、模糊数学等相关技术。 数据挖掘是数据库中知识发现( k d d ) 的一个重要步骤，典型的数据库中知识发现的 步骤如图1 - 1 所示1 1 i 。 m * # 图1 - 1 数据库中知识发现的典型步骤 1 、数据清理( 消除噪声或不一致数据) 2 、数据集成( 各种数据源可以组合在一起) 3 、数据选择( 从数据库中检索与分析任务相关的数据) 4 、数据变换( 数据变换或统一成适合挖掘的形式，如通过汇总或聚集操作等) 5 、数据挖掘( 使用智能方法提取数据模式) 6 、模式评估( 根据某种趣度度量，识别表示知识的真正有趣的模式) 7 、知识表示( 使用可视化和知识表示技术，向用户提供挖掘的知识) 数据挖掘所发现的知识最常见的有以下几类： 1 、广义知识：广义知识是对类别特征的概括性描述。根据数据的微观特性发现其 表征的、带有普遍性的、较高层次概念的和宏观的知识反映同类事物共同性质，是对 数据的概括、精炼和抽象1 2 1 1 ”。 乡。一一皋 中国民航大学硕士学位论文 2 、关联知识：它反映一个事件和其他事件之间依赖或关联的知识。如果两项或多 项属性之间存在关联，那么其中一项的属性值就可以依据其他属性值进行预测，最为著 名的关联规则挖掘方法是r a g r a w a l 提出的a p r i o r i 算法和h a nj i a w e i 提出的不产生候选 项集的f p g r o w t h 算法1 4 j 【5 】1 6 j 【7 j 。 3 、分类知识：它反映同类事物共同性质的特征型知识和不同事物之间的差异性特 征知识。最为典型的分类方法是基于决策树的分类方法，它是从实例集中构造决策树， 是一种有指导的学习方法。最为典型的决策树学习系统是i d 3 ，它采用自顶向下不回溯 策略，能保证找到一个简单的树。算法c 4 5 和c 5 0 都是i d 3 的扩展，它们将分类领域 从类别属性扩展到数字型属性【8 】【9 】【1 0 】【1 1 】。 4 、聚类：聚类是把整个数据对象分成不同的群组。它的目的是要群与群之间差别 很明显，而同一个群之间的数据对象尽量相似。与分类不同，在开始聚类之前你不知道 要把数据对象分成几组，也不知道怎么分，k 一均值算法是比较常用的聚类算法【1 引。 5 、预测型知识：它根据时间序列型数据，由历史的和当前的数据去推测未来的数 据，也可以认为是以时间为关键属性的关联知识。目前，时间序列预测方法有经典的统 计方法、神经网络和机器学习等。1 9 6 8 年b o x 和j e n k i n s 提出了一套比较完善的时间序 列建模理论和分析方法，这些经典的数学方法通过建立随机模型，如自回归模型、自回 归滑动平均模型、求和自回归滑动平均模型和季节调整模型等，进行时间序列的预测1 1 引。 随着数据挖掘和知识发现技术的发展，数据挖掘和知识发现的研究已经涵盖了几大 学科的内容如机器学习、数理统计、神经网络、数据库、模式识别、粗糙集、模糊数学 等。它把人们对数据的应用从低层次的简单查询，提升到从数据中挖掘知识，提供决策 支持。目前数据挖掘和知识发现的主要研究内容包括基础理论、统计方法、关联规则、 分类、聚类、并行和分布挖掘、知识可视化、文本挖掘、知识管理，以及一些基于特定 领域的研究，如：生物医学挖掘、半结构和非结构化数学挖掘、时间和空间数据挖掘、 多媒体数据挖掘、图模型发现、w e b 数据挖掘和流挖掘等。 1 2 信息隐私权的发展 任何事物都有其两面性，数据挖掘也不例外，在挖掘数据产生知识的同时，随之产 生的就是隐私泄露问题。“隐私权 最早是在1 8 9 0 年1 2 月美国人沃伦和布兰代斯所写的 隐私权一书中被正式定义，“隐私权”被界定为“生活的权利”和“不受干扰的权 利”。他们两人认为，隐私权本质上是一种个人对其自身事务是否公开给他人的权利， 保护个人的隐私权就是保障个人的“思想、情绪及感受不受他人打扰的权利，保护自 己人格不受侵犯的权利。n 2 0 世纪6 0 年代，隐私权的观念逐渐为美国法律界所熟悉，但 隐私权的内容为何，却始终未见有明确的界定。1 9 6 0 年，w i l l i a ml p r o s s e r 教授在加 州法律评论上发表了隐私一文，试图就隐私权的内容做一归纳。根据他的整理， 法律上的隐私权侵害包含四种侵权行为，包括：对他人私生活隐私权的侵害；公开他人 2 中国民航大学硕士学位论文 的姓名、肖像或揭发其他不愿为他人所知悉的私人信息；使他人处于人为误解情况；基 于商业上的目的侵犯他人人格等1 1 训。 随着信息技术、特别是网络技术、数据存储技术和高性能处理器技术的飞速发展， 海量数据的收集、管理和分析变得越来越方便。这样，传统上对隐私权保护的思想就必 须转向以“数据保护”为重心的思路上来，于是就出现了“信息隐私权”的概念以应对 信息时代隐私权所受到的冲击。例如，通过对医院病人的病历数据进行挖掘，可以发现 各种疾病之间的关联，但在使用一般方法进行挖掘的过程中，不可避免地会使病例数据 暴露，从而造成病人隐私的泄露；还有治安系统中的违法记录、保险公司的理赔情况、 银行卡客户的交易行为等信息中的关联关系，都对政府和企业决策具有相当重要的意 义，但同时又都是公民非常注重的个人隐私【1 5 】。国外已经发生了多起由于个人信息泄密 而造成个人账号被盗用的例子，以及由于个人电话号码被一些机构出卖，而遭到一些中 介、盈利机构频频骚扰的例子，所以说信息时代的隐私权保护要比传统的隐私权保护重 要的多。信息隐私权保护的客体可分为以下四个方面1 1 4 j ： 1 、个人属性的隐私权：如一个人的姓名、身份、肖像、声音等，由于其直接涉及 个人领域的第一层次，可谓是“直接的个人属性，为隐私权保护的首要对象。 2 、个人资料的隐私权：当个人属性被抽象成文字的描述或记录时，如个人的消费 习惯、病历、宗教信仰、财务资料、工作、犯罪前科等记录，若其涉及的客体为一个人， 则这种资料即含有高度的个人特性而常能辨识该个人的本体，可以说这些“间接”的个 人属性也应以隐私权加以保护。 3 、通信内容的隐私权：个人的思想与感情原本存于内心之中，别人不可能知道， 当与外界通过电子通信媒介如网络、电子邮件沟通时，即充分暴露于他人的窥探之下， 所以通信内容应加以保护，以保护个人人格的完整发展。 4 、匿名的隐私权：匿名发表在历史上一直都扮演着重要的角色，这种方式可以保 障人们愿意对社会制度提出一些批评。这种匿名权利的适度可以鼓励个人的参与感，并 保护其自由创造力空间；而就群体而言，也常能由此获利，真知直谏的结果是推动社会 的整体进步。 1 3 隐私保护数据挖掘的研究背景和现状 数据挖掘的恰当使用会挖掘出切实有用的知识，但是如果被恶意使用的话，就会泄 露用户的隐私。一般来说，在数据挖掘领域，隐私被划分为两类：一类隐私是原始数据 本身具有的。由于传统的数据挖掘技术是基于未加密过的原始数据来进行的，也就是说 必须将包含个人或企业隐私的原始数据交给数据挖掘者才能挖掘出有用的知识，如个人 的家庭电话、银行账号、财产状况、信用等级等信息，这些信息一旦泄露的话，极可能 会对个人的生活产生不良影响。另一类隐私是原始数据所隐含的知识，如某公司优质客 户的行为特征等规则，这些知识如果被别有用心的人非法获得，将会严重影响企业的核 3 中国民航大学硕士学位论文 心竞争力。 在这种情况下，人们会不会由于担心隐私被泄露而拒绝提供任何信息资料呢? 为了 了解人们对隐私保护的态度，1 9 9 9 年有人对网上用户作了一个调查【1 6 】，结果表明：在回 答者中，1 7 的网上用户是正统的隐私保护主义者，他们即使在采取保护隐私的措施下 也不愿意提供自己的真实信息；5 6 的网上用户是实用主义者，在采取保护隐私的措施 下，他们提供真实信息的可能性大大提高；其余2 7 的网上用户虽然也考虑隐私，但还 是愿意提供自己的真实信息。该调查结果说明，在数据挖掘能够提供的益处面前，只要 数据采集者采取措施保证个人的隐私不被泄露，大部份人还是愿意参与调查并提供自己 的隐私数据，同时也说明保护隐私程度的高低将直接关系到是否能够收集到足够真实的 信息，从而关系到挖掘出的信息是否可靠有用。 在1 9 9 5 年召开的第一届k d d 会议上，隐私保护的数据挖掘就已经成为了一个专门的 研究主题。1 9 9 9 年r a k e s ha g r a w a l 在k d d l 9 9 91 - _ 作了一场精彩的主题演讲，他将隐私保 护的数据挖掘作为未来的研究重点之一【1 7 】。自此以后，隐私保护的数据挖掘越来越得到 人们的重视，迅速成为近年来数据挖掘领域研究的热点之一。 现有的隐私保护数据挖掘算法可以从数据分布方式、数据修改方法、数据挖掘算法、 隐私保护对象和隐私保护技术五个角度进行归纳【1 引。 1 、数据分布方式：数据挖掘有的是研究集中式数据，有的是研究分布式数据。分 布式又分为水平分布和垂直分布两种，水平分布是指数据按记录分布在不同的站点，垂 直分布是指数据按属性分布在不同的站点。 2 、数据修改方法： ( 1 ) 按不可逆推的方法修改数据为一个新值； ( 2 ) 用“? ”来替代存在的值，以保护敏感数据和规则； ( 3 ) 合并或抽象详细数据为更高层次的数据； ( 4 ) 对数据进行抽样。 3 、数据挖掘算法：适用于不同知识的挖掘算法，如分类、关联规则、聚类等。 4 、隐私保护的对象：即隐藏原始数据或其隐含的规则。规则比原始数据的层次要 高，通过保护敏感规则，同样可以保护重要的原始数据。 5 、隐私保护技术：即修改数据所采用的技术，主要有 ( 1 ) 启发式技术：通过仅仅修改特定值、而非全部值来减少挖掘效果的失真； ( 2 ) 密码技术：采用密码学技术进行数据加密，如多方安全计算等； ( 3 ) 重建技术：从变换后的数据中恢复原有数据的分布。 以上各种方法都有其各自的特点，各类隐私保护数据挖掘算法的评价标准如下【1 8 】： 1 、性能：计算开销以及分布式环境下的通讯开销； 2 、算法精度：与非隐私保护的同类算法相比，其判断精度、丢失比率和错误生成 比率； 3 、隐私保护程度：防止原始数据或其隐含的知识被推导出的程度； 4 中国民航大学硕士学位论文 4 、通用程度：适应各种数据挖掘技术的程度。 在国外，研究人员对隐私保护下的数据挖掘问题进行了深入研究，发表了大量文章， 并且取得了很多理论成果。然而，国内在这方面相关的研究才刚刚起步，也仅有几篇文 章谈及，所以，对数据挖掘的隐私保护技术进行研究有着重要的意义。 1 4 论文的研究内容 从输入隐私保护的角度研究分析了国内外已有的几种隐私保护关联规则挖掘算法， 以其中的m a s k 算法和e m a s k 算法为研究重点。m a s k 算法用来挖掘0 - 1 事务集单维布 尔关联规则，在恰当选择算法参数时，可以同时得到令人满意的隐私保持度和准确度j 但是运行时间效率较差，难以在实践中应用。本文的一个研究重点就是针对m a s k 算法 时间效率低下的缺点对m a s k 算法进行改进，m a s k 算法在估算玎一项集的真实支持度时 需要计算2 1 阶矩阵m 的逆，随着珂的增大该逆矩阵的计算越来越耗时。本文基于分治 策略提出了改进的m a s k 算法，在该算法中提出了递归计算m 。的方法，计算m 4 的时 间复杂度仅为d 似) ( k = 2 ”，咒= 2 ，3 ，4 ，) 。原m a s k 算法计算m 以的复杂度为o ( k 3 ) ， 通过实验结果证明改进的m a s k 算法在保持算法的隐私保持度和准确度与原m a s k 算法 相同时，时间效率有了提高。把分治策略运用到e m a s k 算法，提出了改进的e m a s k 算 法，在不考虑空间开销的条件下，改进的算法在时间效率上比原e m a s k 算法高，同时 算法的隐私保持度和准确度跟原e m a s k 算法相同。 从输出隐私的角度研究了保护敏感规则的方法，从降低规则的支持度和置信度两个 角度给出了保护敏感规则的三种具体算法并分析了算法的时间有效性。 1 5 论文的组织结构 论文按如下方式组织： 第二章介绍了隐私保护关联规则挖掘的基本概况； 第三章从输入隐私保护的角度进行分析研究，论述了国外学者提出的m a s k 算法和 e m a s k 算法，创新性地将分治策略运用到这两种算法中，提出了改进的m a s k 算法和 e m a s k 算法，通过时间复杂度分析和实验结果比较得知对这两种算法的改进是有效的。 第四章从输出隐私保护的角度研究了保护敏感规则的方法，给出了保护敏感规则的 三种算法，并分析了算法的时间有效性。 第五章是全文的总结并介绍了未来需要更进一步研究的工作。 5 中国民航大学硕士学位论文 第二章基于隐私保护的关联规则挖掘概述 2 1 关联规则挖掘 关联规则挖掘是发现大量数据中项集之间有趣的关联或相关联系。随着大量数据不 停地收集和储存，许多业界人士对从数据库中挖掘关联规则越来越感兴趣。从大量商务 事务记录中发现有趣的关联关系，可以帮助去做商务决策的制定，如分类设计、交叉购 物和贱卖分析等1 1j 。 关联规则挖掘的一个典型例子是购物篮分析。该过程通过发现顾客放入其购物篮中 不同商品之间的联系，分析顾客的购买习惯。通过了解哪些商品频繁地被顾客同时购买， 这种关联发现可以帮助零售商制定营销策略。例如顾客在同一次去超级市场，如果购买 牛奶，他也购买面包的可能性有多大? 通过帮助零售商有选择地经销和安排货架，这种 信息可以引导销售。例如，将牛奶和面包尽可能放近一些，可以进一步刺激顾客一次去 商店同时购买这些商品。 关联规则挖掘的基本概念如下：设i = ，i 2 ，) 是项的集合，d 是任务相关的数据 事务的集合，丁是每个事务项的集合，满足丁，且使得每一个事务都有唯一标识t i d 。 设a 是一个项集，则a 支持事务z 当且仅当a t 。关联规则是形如a 号b 的蕴涵式，其 中4c ，口c ，并且彳nb = 囝。规则a 号b 在事务中成立，具有支持度s ( s u p p o r t ) ， 其中s 是数据库d 中事务包含彳u 曰的百分比，即 s 似号口) 。坚掣1 0 0 ( 2 1 ) 、。 | d i 规则ajb 具有置信度c ( c o n f i d e n c e ) ，其中c 是指包含彳的事务中同时也包含b 的 百分比，即 c 似j 曰) = p ( bi 彳) ( 2 2 ) 支持度是统计意义上的衡量，而置信度是对规则强度的衡量。同时满足最小支持度 和最小置信度的规则称为关联规则。 项的集合称为项集。包含k 个项的集合称为k 一项集。项集的出现频率是包含项集的 事务数，简称为项集的频率、支持计数或计数。项集满足最小支持度m i n _ s u p ，如果项 集的出现频率大于或等于m i ns u p 与d 中事务总数的乘积，则称它为频繁项集。 通常，关联规则挖掘的过程分为以下两步： 1 、发现频繁项集。频繁项集是指支持度不低于预先设定阈值的项集； 2 、根据第1 步发现的频繁项集，产生置信度不低于预先设定阈值的关联规则。 6 中国民航大学硕士学位论文 2 2a p r i o r i 算法 a p r i o i 算法是经典的挖掘布尔关联规则频繁项集的算法，它使用逐层搜索的迭代方 法，k 一项集用于探索( k + 1 ) 一项集。首先找出频繁1 一项集合，该集合记作厶，厶用于找 频繁2 一项集l ：，而厶用于找厶，如此下去，直到不能找到频繁k 一项集。找每个厶需 要扫描一次数据库。 为提高频繁项集逐层产生的效率，a p r i o r i 使用一个重要性质压缩搜索空间，下面介 绍一下这个性质。 a p r i o r i 性质：频繁项集的所有非空子集都必须是频繁的。根据定义，如果项集，不 满足最小支持度阈值m i ns u p ，则，不是频繁的，即p ( ，) m i ns u p 。如果项a 添加到i ， 则结果项集八- j 彳不可能比，更频繁出现。因此，八_ j 么也是不频繁的，即 p ( iu a ) m i n s u p 。 利用a p r i o r i 性质从k 一。到t 需要两个步骤来完成： 1 、连接步：为找到乙，通过厶一，与自己连接产生候选k 一项集的集合。该候选集的 集合记为g 。设和z ：是乙一，中的项集。记号t 【门表示t 的第j 项。为方便起见，假定事 务或项集中的项按字典次序排序。执行连接乙一。q 睁l k - 1 ，其中厶一。的元素是可连接的， 如果他们前k 一2 个项相同。即k 一，的元素f 1 和z ：是可以连接的，如果 ( f l 【1 】= 1 2 1 ) a ( 1 l 【2 】= 1 2 1 2 ) a a ( f 1 陋一2 】= 1 2 k 一2 1 ) a “陋一1 】 1 2 k 一1 】) ( 2 3 ) 条件( f 1 坼一1 】 9 k ； ce c fic c o u n t m i n _ s u p ； 1 0 】 1 1r e t u r n l = u i 丘； p r o c e d u r ea p d o d _ g e n ( l k 1 ，m i n _ s u p ) 1f o re a c hi t e m s e tf l t 一1 2f o re a c hi t e m s e t ，2 厶一l 3 i f ( i 1 1 一1 2 1 ) ( f ，【2 】一d 2 ) ( 1 l 【七- 2 1 = 1 2 k 一2 】) ( 厶【七一1 1 m ，则设置j 一m ： 2 、从f ，中随机均匀地选择个项，放入f 中； 3 、对其它项( 包括的剩余部分) ，随机地以正面为p 。、反面为1 一以的概率抛硬 币，将那些结果为正面的项加入t 中。 设r 是总数为的事务集合，a 是一个项集，则定义a 的交集为，的局部支持度为 s u p m ；坐掣 ( 2 5 ) 假设随机运算符是保持事务和项不变的，设一个长度为m 的事务t ，以及一个长度为 k 的项集a ，t 被随机化为f ，定义威p - ，) 一p t - - * l 】墨研 批f q a ) = 川 批f 3 a ) = ， 】， 这里z ，z 都是 0 1 ，七) 中的整数。对于“s e l e c t a s i z e ”随机运算符： 或o _ i 。) ；艺p m “拶弘- t p , - q ( 1 刊一，叼 ( 2 6 ) 或o _ 。) = 【】掣( 1 一p ) 卜卜r 叼 ( 2 6 ) j q - m a x 0 ，+ l - m ，i + 1 一k 。“ 再假设丁中所有的条事务长度都为m ，则对一个长度为k 的项集a ，随机向量 幸瓯，s ：，s ：) 是一个 + 1 ) 个独立的多项式分布的随机向量的和，这里t ；s u p , ) 。 它的期望值e “，s ：，文) r ；p 木( s 。，s ，s 。) r ，其中p 是七+ 1 阶矩阵，p = p 1 呻，1 。它 的协方差c d ，( 磊，吱) r2 砉宰荟墨d p 】，d 【f 】是七+ 1 阶的矩阵， d p 】 = p 1 呻zi 】幸谚= j - p 1 一f 】枣p 1 _ j 】，当i = _ 时噬f 等于1 ，其它情况等与o ；_ 代 表s u p ；( a ) 。 设j = ( s o ，墨，s k ) t ，s 一( ，墨，& ) t ，则 e s 一p 枣s ( 2 7 ) 设q = p 一，则 s = q 木es = e o 幸s ( 2 8 ) 由随机化后的局部支持度计算得到原始数据支持度的无偏差估计值为s 。，一q 拳s 。 所以 c o y s e a t = 铆( q sv ) zq ( c d ，sf ) q r2 专术s , o o z ( 2 9 ) 用s 表示s 。r 的第k 个坐标，口【z z1 表示q f ，则用s 估计s 有 s2 磊凶毒q k , - - z t 】 ( 2 1 0 ) 1 3 中国民航大学硕士学位论文 该式子用于恢复项集的支持计数。 随机响应技术最早是由w a r n e r 在1 9 6 5 年提出的，用于解决如何获取一个回答者可能 不愿意如实做答的敏感问题的准确答案【2 引。国外一些研究者把此技术应用于隐私保护关 联规则取得了不少成果【2 3 】【2 4 】【冽【2 6 】。国内学者张鹏等提出一种基于随机响应技术的集中 式隐私保护方法( r r p h ) 曙丌，该方法将数据干扰和查询