（计算机应用技术专业论文）保护隐私的贝叶斯网络学习研究.pdf

中文摘要 互联网的飞速发展使得网络中数据的共享和交换行为出现得越来越频 繁。一方面，政府部门、商务机构以及其他的一些组织希望能够充分地利用 共享数据并从中受益；另一方面，隐私的存在及对隐私的保护性关注又在很 大程度上限制了数据的共享范围。保护隐私的分布式数据挖掘由此应运而 生。本文重点研究了保护隐私情况下的贝叶斯网络学习方法，并取得了如下 成果： 系统分析了已有的贝叶斯网络学习方法，并结合安全多方计算的概念、 协议和常用算法，提出了从同构分布或异构分布的数据中，保护隐私地学习 贝叶斯网络的结构和参数，为实现保护隐私的分布式数据挖掘提供了新思 路。 针对同构完整数据条件下保护隐私的贝叶斯网络学习，提出并实现了 p p h c t p d a 方法。该方法使用相关性分析思路进行结构学习，按照有向边 安全统计协议，统计各站点得到的结构边；然后取局部互信息算术平均值作 为全局的互信息，并应用到学习过程中。实验结果验证了所提方法的性能和 效率。 针对异构完整数据条件下保护隐私的贝叶斯网络学习，提出并实现了 p p v c s m d l 方法。该方法基于m d l 算法的连续搜索版本，利用多向量点 积份额协议计算多向量点积和结构熵，并将其应用到网络的构建过程中。在 学习结构的同时，获得网络参数。与已有方案相比，该方法具有更高的安全 性、精确性、适用性和学习效率。 针对同构不完整数据条件下保护隐私的贝叶斯网络学习，提出并实现了 基于e m 算法框架的p p h i - e m 方法。该方法交替进行当前候选模型的参数 优化迭代和搜索模型的迭代，取局部打分函数值的权和作为全局打分函数 值，并应用到网络的学习过程中。该方法能够在搜索结构的同时，最优化网 络参数。实验结果验证了所提方法的性能和效率。 关键词：保护隐私的数据挖掘贝叶斯网络分布式数据库安全多方计算 a b s t r a c t w i t ht h es p r e a do fi n t e m e t , m o r ea n dm o r ea c t i v i t i e so nd a t as h a r i n ga n d e x c h a n g i n ga c o m i n g f o r t hi nt h en e t w o r k g o v e r n m e n t 螂缸恤搿怄， c o m m e r c i a lo r g a n i z a t i o n sa n do t h e rp a r t i e sm a yw i s ht ob e n e f i tf r o mc o o p e r a t i v e 鸺eo ft h e i rd a t a t ot h ec o n t r a r y , p r i v a c yr e g u l a t i o n sa n do t h e rp r i v a c yc o n c c t n s m a yp r e v e n tt h ep a r t i e sf r o ms h a r i n gt h e i rd a t a p r i v a c y - p r e s e r v i n gd i s t r i b u t e d d a t am i n i n ge m e r g e s 船t h et i m e sr e q u i r e i nt h i sp a p e r , p r i v a c y - p r e s e r v i n g b a y e s i a nn e t w o r k ( b n ) l e a r n i n gi ss t u d i e dt e c h n i c a l l y ，a n ds o m er e s u l ta r c o b t a i n e da sf c l l l o w s ： b a s e do no fk n o w nb nl e a r n i n gm e t h o d s ，w i t hc o n s i d e r i n gt h ec o n c e p t s ， p r o t o c o l sa n da l g o r i t h m so fs 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 ) ，a ni d e ao f l e a r n i n gb ns t r u e t u r ea n dp a r a m e t e r so nt h ev e r t i c a lo rh o r i z o n t a ld a t a b a s ei na p r i v a c y - p r e s e r v i n gw a yi sp r o p o s e d ，w h i c hh e l pt oa c h i e v i n gp r i v a c y - p r e s e r v i n g d i s t r i b u t e dd a t am i n i n g f o rp r i v a c y - p r e s e r v i n gb nl e a r n i n go nt h eh o r i z o n t a l l yp a r t i t i o n e dd a t a b a s e w i t hc o m p l e t ed a t a ，t h ep a p e rp u t sf o r w a r d sa n dr e a l i z e sp p h c t p d a ( p r i v a c y - p r e s e r v i n gt p d al e a r n i n g o nh o r i z o n t a l l yp a r t i t i o n e dd a t a b a s ew i t h c o m p l e t ed a t a ) m e t h o du s i n gi n f o r m a t i o nt h e o r e t i ca n a l y s i s i nt h i sm e t h o d ， a c c o r d i n gt ot h es e c u r es t a t i s t i cp r o t o c o lo fo r i e n t e de d g e s ，w ec a l lo b t a i nt h e s t a t i s t i c a ln u m b e ro f s t r u c t u r ee d g e sf r o me v e r ys i t e t h e nt h ea r i t h m e t i cm e a no f l o c a lm u t u a li n f o r m a t i o n ，r e g a r d e da st h eg l o b a lm u t u a li n f o r m a t i o n ，i sa p p l i e di n t h eb nl e a r n i n g e x p e r i m e n t a lr e s u l t ss h o wt h eg o o dp e r f o r m a n c ea n dh i g h e f f i c i e n c yo f t h i sm e t h o d f o rp r i v a c y - p r e s e r v i n gb nl e a r n i n go nt h ev e r t i c a l l yp a r t i t i o n e dd a t a b a s e w i t hc o m p l e t ed a t a ，t h ep a p e rp r o p o s e sp p v c s m d l ( p r i v a c y - p r e s e r v i n gs e r i a l s e a r c ha l g o r i t h mo fm d ll e a r n i n go nv e r t i c a l l yp a r t i t i o n e dd a t a b a s ew i t h c o m p l e t ed a t a ) m e t h o db a s i n go nas e r i a ls e a r c ha l g o r i t h mo fm d l i nt h i s m e t h o d ，p r i v a t eg e n e r a l i z e ds c a l a rp r o d u c ts h a r ep r o t o c o li sd e p l o y e dt oc o m p u t e g e n e r a l i z e ds c a l a rp r o d u c ta n de m p i r i c a le n t r o p y , w h i c hc a nb eu s e di nt h e p r o c e s so fc o n s t r u c t i n gn e t w o r k w ec a no b t a i nt h en e t w o r kp a r a m e t e r sw h i l e l e a r n i n gs t r u c t u r e c o m p a r e dw i t hk n o w nm e t h o d s ，i ts h o w sb e t t e rp e r f o r m a n c e ， p r i v a c y , a c c u r a c ya n dh i g h e re f f i c i e n c y f o rp r i v a c y - p r e s e r v i n gb nl e a r n i n go nt h eh o r i z o n t a l l yp a r t i t i o n e dd a t a b a s e w i t hi n c o m p l e t ed a t a , t h ep a p e ri m p l e m e n t sp p h i - e m ( p r i v a c y - p r e s e r v i n ge m l e a r n i n go nh o r i z o n t a l l yp a r t i t i o n e dd a t a b a s ew i t hi n c o m p l e t ed a t a ) m e t h o d b a s i n go nt h es t a n d a r de x p e c t a t i o nm a x i m i z a t i o n ( e da l g o r i t h m 1 m sm e t h o d a l t e r n a t e sb e t w e o nt h ei t e r a t i o n st h a to p t i m i z e st h ep a r a m e t e r sf o rt h ec u r r e n t m o d e lc a n d i d a t ea n dt h ei t e r a t i o n st h a ts e a r c h e sf o rad i f f e r e n tm o d e l t h ew e i g h t m 1 mo f l o c a ls c o r e si sr e g a r d e da st h eg l o b a ls c o r ea n da p p l i e di nt h eb n l e a r n i n g p p h i - e mm e t h o dc o m b i n e sp a r a m e t e r o p t i m i z i n g 谢t hm o d e ls t r u c t u r es e a r c h i n g e x p e r i m e n t a lr e s u l t ss h o wt h eg o o dp e r f o r m a n c ea n dh i 【g he f f i c i e n c yo ft h i s m e t h o d k e yw o r d s ：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 ，b a y e s i a nn e t w o r k , d i s t r i b u t e dd a t a b a s e ，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 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究工作和取得的 研究成果，除了文中特另i j d n 以标注和致谢之处外，论文中不包含其他人已经发丧 或撰写过的研究成果，也不包含为获得：叁壅盘茔或其他教育机构的学位或证 书而使用过的材料。与我一同工作的同志剥本研究所做的任何贡献均已在论文中 作了明确的说明并表示了谢意。 学位论文作者签名：王纽物签字目期：o 掰年5 月石同 学位论文版权使用授权书 本学位论文作者完全了解墨垄盘堂有关保留、使用学位论文的规定。 特授权墨壅盘堂可以将学位论文的全部或部分内容编入有关数据库进行检 索，并采用影印、缩印或扫描等复制手段保存、汇编以供查阅和借阅。同意学校 向国家有关部门或机构送交论文的复印件和磁盘。 ( 保密的学位论文在解密后适用本授权说明) 学位论文作者签名：3 - 红梅导师签名匙执 签字月期：o “年6 月6 日签字日期：加6 年月日 天津大学博士学位论文 第一章绪论 第一章绪论 随着越来越多的活动通过计算机和计算机网络展开，政府、商务机构和其他 一些组织存储的敏感数据的数量也越来越大。不同组织希望从他们数据的合作中 受益，但隐私的存在以及对隐私的关注却阻止了各组织共享数据，保护隐私的分 布式数据挖掘算法应运而生，己成为未来数据挖掘技术发展的一个富有前景的方 向。本章给出了基于隐私保护数据挖掘的研究现状，分析了该研究领域的分类模 式。对各方面研究做了详细介绍，最后给出论文的主要工作和组织结构。 1 1 引言 数据挖掘和知识发现作为数据库中的两大研究领域，旨在从大量数据中自动 提取出未知的模式。随着越来越多的信息以电子形式可以从网上得到，并且有越 来越多的数据挖掘工具开发出来并投入使用，数据挖掘已经对隐私和数据安全构 成威胁。近来，在数据收集、分发和相关技术方面，也开辟出了一个全新的研究 领域从安全的角度重新考虑数据挖掘算法。 越来越多的数据挖掘需要处理多方数据。例如，不同银行希望从共享数据中 得到欺诈行为的模式；政府机构需要和航天部门合作，挖掘恐怖行为的踪迹。但 是，隐私的关注阻碍了他们共享原始数据的脚步。在一些国家，法规的制订也阻 止了不同部门共享信息，例如h i p a a ( t h eh e a l t h i n s u r a n c ep o r t a b i l i t ya n d a c c o u n t a b i l i t ya c t ) 【l 】和欧洲的隐私指南【2 【3 】。 一些公用算法提供了对任意分布数据的保护隐私挖掘【4 】【5 】。然而，这些解 决方法仅仅适用于小规模的数据计算，对大型应用并不有效。而且，保护隐私的 数据挖掘集中关注于对特殊的数据挖掘问题提供有效的解决方法。 考虑到这些，许多保护隐私的数据挖掘算法f 6 7 】【8 【9 】【l o 】【1 1 1 2 1 3 1 4 】 【1 5 被开发出来，不要求任何一方得到完整的源数据集。按照最严格的保护隐私 要求，任一部分除了得知从自身的数据和最终的挖掘结果推导出的信息外，不能 获得任何其他信息。在数据挖掘算法中需要输入大量的数据时，特殊化的定制加 密算法更有效。a g r a w a l 和s r i k a n t 7 弓l 入的随机方法，比加密技术更有效，但却 不能有效地保护隐私。一般来说，允许更多的信息泄漏会产生更有效的解决方法。 保护隐私的数据挖掘在数据挖掘和统计数据库的研究中是个新颖的研究方 向。它主要分析数据挖掘算法对数据安全带来的负作用。在隐私保护数据挖掘中 主要考虑两点。第一，对于源数据中的敏感属性值，如身份号码、名字、地址等 天津大学博士学位论文第一章绪论 值，应该在源数据库中做修改或处理；一些非敏感属性值或其函数，被另一方直 接调用时，也需要加以处理；这样，数据的接受者就不能危及他人的隐私。第二， 使用数据挖掘算法能从数据库中挖掘出敏感知识，这些敏感知识危及了数据隐 私，也应该被剔除。保护隐私数据挖掘的主要目的是开发出以某种方式改变源数 据的算法，这样，即便经过了挖掘算法，个人数据和个人知识依旧保持隐私。未 经授权的用户从公开发布的数据中得到机密消息的问题，也常被称为“数据库推 论”问题。这一部分给出了已经在保护隐私数据挖掘领域发展起来的不同技术和 方法的分类状况及扩展描述。 基于隐私保护的角度，也就是基于已选择性更改的数据上的隐私保护技术， 对保护隐私的数据挖掘进行如下分类： 基于启发式研究( h e u r i s t i c - b a s e d ) 的技术。在更改和净化选择的数据是一 个n p - h a r d 问题的前提下【1 6 】，启发式的研究可用于解决这类复杂的问 题。如适应性改变，它仅仅改变挑选的属性值而不是全部。这样，可以 最小化实用性损失。 基于加密的技术。在分布式网络中，每个参与者有自己的输入，确保输 入的独立性、计算的正确性，并且确保在计算时，除了参与者的输入信 息和输出信息外，没有向参与者泄漏更多的信息，这个计算就是安全的。 基于重建的技术。为了执行挖掘，首先混淆数据，然后聚集，数据的初 始分布在一个聚集的水平上重建起来。这里，聚集指的是将几个属性值 放到一个粗糙的范畴中。 更改数据会导致数据库操作性能的损失。为了量化性能的损失，主要使用两 种方法。第一种，测量机密数据的保护；第二种，测量功能性的损失。 1 2 基于启发式研究的技术 在更改和净化选择的数据是一个n p h a r d 问题的前提t 0 6 ，启发式的研究 可用于解决这类复杂的问题。以标准的形式隐藏聚集数据的复杂性很高，为此， 已经开展了许多启发式的研究。 1 2 1 基于混淆的保护隐私关联规则挖掘 在关联规则挖掘中隐藏大量敏感项的最优净化是一个n p h a r d 问题，这个结 论在文献 1 7 1 q b 给出了形式证明( 完善而可信的数学论证，它为每个证明步骤、每 个理论或一套理论的真实性提供充足的逻辑证明) 。该问题是：设d 是源数据库， 矗是能够从d 中挖掘出来的重要的关联规则的集合。设兄是r 的一个子集。如 天津大学博士学位论文第一章绪论 何把数据库d 转化为数据库d _ ，以至于除了最之外，所有的r 中的规则都能够 从口中挖掘出来。这里启发式研究基于数据混淆方法。所谓混淆，是指改变属 性的取值。例如，属性值1 改为0 ，或者增加噪声。降低了敏感规则的支持度， 使公开的数据库的实用性达到最佳。这里实用性用非敏感规则的数量来测量。 随后的工作是将大量敏感项集的净化延伸到敏感规则的净化【1 8 】。在这项工 作中采取的方法有两个，如图l - l 。或者通过隐藏产生敏感规则的频繁集，阻止 敏感规则的产生；或者将敏感规则置于用户指定的闽值之下，减小敏感规则的秘 密。根据这两种方法可以得到隐藏敏感规则的一些策略。考虑这一些策略，需要 提及的最重要的是将二进制数据库中的1 值转换为0 值和将0 值转化为l 值的概 率。数据的灵活更改会产生这样的副作用：除了非敏感关联规则会变成隐藏的外， 非频繁规则也会变成频繁规则。称这种规则为“幽灵规则”。假定隐藏了敏感规 则，那么被隐藏的非敏感规则和变成频繁规则的非频繁规则就会降低公开数据库 的实用性。为此，考虑到不危及隐私，启发式研究必须对于实用性问题更加敏感。 【1 8 】的工作建立在这个观点之上。文献【2 0 】在前面论述的基础上，最小化净化处 理的影响或最小化意外隐藏和幽灵规则，旨在信息隐私和信息泄漏之间找到平 衡。 图1 1 敏感项集的净化和敏感规则的净化 1 2 2 基于阻塞的保护隐私关联规则挖掘 数据阻塞是安全关联规则挖掘的另一个数据更改方法 2 h 。所谓阻塞，是将 已经存在的属性值用“? ”来代替。该方法通过用问号来取代一些数据项中的特 定属性值来实现。在一些特殊的应用中，比如医疗应用，用一个未知的值而不是 一个错误的值代替真实值更加合适。文献【2 2 】将阻塞应用到安全关联规则挖掘。 将这一全新的特殊符号引入数据集，改变了关联规则中的支持度和置信度的定 天津大学博士学位论文第一章绪论 义，将最小支持度和最小置信度相应改变为最小支持区间和最小置信区间。只要 敏感规则的支持度和或置信度处于这两个范围中，就认为没有违背数据的机密 性。文献 2 3 】中详细讨论了这项研究工作的扩展问题安全重构规则的效果问 题。 1 2 3 基于阻塞的保护隐私分类规则挖掘 文献【2 4 中提供了一个全新的框架，将分类规则分析和吝啬的降格结合在一 起。这里注意，在分类规则框架中，数据管理员把阻塞类标识的值作为目标。这 样做的结果是，信息的接受者将不能对未被降格的数据形成情报模型。从安全场 合( 安全性高) 到公开场合( 安全性低) ，降格信息数据集都可以被整理出来。假定 推理渠道存在的话，吝啬的降格是用于形式化这些被整理出的信息现象的一个框 架结构。在吝啬降格中，成本的测量被定为不能公开的潜在的降格信息。发现与 未降格的数据相关联的功能性的损失，是否值得额外的加密，是这项工作中需要 完成的主要目的。分类规则，尤其是判定树，用在吝啬降格中，来分析需要被降 格的数据中潜在的推理渠道。 用在降格中的技术是一个创造，称为参数基础集。特殊地，参数0 ，0 0 l 代替被阻塞的值，它代表了属性取得可能值之一的概率。计算出阻塞之前 的初始熵值和阻塞之后的初始熵值。将这两个熵值的差异与从判定树中产生的规 则机密的减少相比，来判断用数据实用性的损失换取更多的安全性能是否值得。 图1 - 2 理性降格器 文献【2 5 】中作者给出了软件系统理性降格器的设计，它基于吝啬降格的 思路。系统由基于知识的决策制造者、一个守卫和一个吝啬降格者组成。如图 1 2 。决策支持者用来确定可被推断出的规则，守卫用来测鼍泄漏信息的总数， 天津大学博士学位论文第一章绪论 吝啬降格者用来改变初始的降格决策。降格数据的算法裁决，需要用从判定树归 纳中引起的哪个规则对隐私数据进行分类。这样，不支持这种方式发现的规则的 任何数据，连同所有的没有在规则条款中阐明的属性，都被排除在降格之外。从 剩余的数据中，算法应该决定哪个值转变为漏测值。这样做是为了最优化规则混 淆。守卫系统决定规则混淆的可接受水平。 1 3 基于加密的技术 在保护隐私数据挖掘的算法中，为了解决安全多方计算( s e c u m u l t i p a r t y c o m p u t a t i o n 。s m c ) 的问题，许多基于加密的方法被挖掘出来。所谓安全多方计算， 是指两个或多个部分想在其秘密输入的基础上进行计算，但每一部分都不想把它 自己的输出泄漏给任何其他部分。就是在保持输入保密的情况下，如何进行计算。 特殊地，一个s m c 问题需要计算这样一个函数：在分布式网络中，每个参与者 有自己的输入，确保输入的独立性、计算的正确性，并且确保在计算时，除了参 与者的输入信息和输出信息外，没有向参与者泄漏更多的信息。 文献【2 6 】提出了一个转换框架，系统地将正常计算转换为s m c 。还讨论了将 不同的数据挖掘问题转换为s m c 。在该领域描述到的数据挖掘应用包括数据分 类、数据聚类、关联规则挖掘、数据概化、数据总结和数据描述。 1 3 1 异构分布保护隐私关联规则挖掘 异构分布，即垂直的数据分布，指的是同一项的不同属性值存放在不同地点。 从垂直分布数据中挖掘秘密的关联规则可以通过扩展已经存在的a p r i o r i 算法来 实现。a p r i o r i 算法的大多数步骤可以在每个站点局部实现。至关重要的一步是 发现项集的支持度。如果这样的项集的支持度可被保护隐私地计算，那么就可以 检测这个支持度是否大于阈值，然后决定该项集是否是频繁的。 将一个完整的记录数据库看成是一个布尔矩阵。矩阵中1 代表某项出现在某 记录中，相应地，0 代表没有出现。计算项集支持度的主要元素是计算代表各部 子项集的向量的点积。因此，若点积可以安全计算出来，那么支持度也可以计算 得到。 另外一个计算支持度的方法是：设第i 部分用集合s 来表示它的子集，该子 集只包括那些支持子集的记录。那么所有这些局部子集的交集( 1 s i ，s = n ：s ) 基 数，就是项集的支持数。可以用安全交集基数的方法来完成这个计算。 这些协议设想了一个半诚实模式。参与者一方面公正地执行协议，但是后来 试着从接收到的数据中推断附加信息。这样做的后果之一是参与者不允许给协议 天津大学博士学位论文第一章绪论 一伪造的输入。例如，如果参与者可以给出伪造的输入，那它就可以探测对方某 特定项的值。例如，设一方的输入为( o ，o ，1 ，o ，0 ) ，那么点积的结果就会告 诉探测方对方对应记录是否为1 这种进攻也称为探针进攻。现在所有提议的协 议都易受到探针的进攻。应用于这种预谋模式下的更好的技术需要警惕这种进 攻。 7 用随机数来代替方程中的真实值，方程的代数解作为计算得到的点积，这一 算法在文献 2 7 1 q b 有详细描述。点积协议的安全性在于每个站点都不能解多于k 个未知数的k 个方程。一些未知数是随机选择的，从安全角度可以认为是秘密的。 在文献 2 8 1 e e 提出了一个类似的方法。另外一个计算支持度的方法是使用文献【2 9 】 中描述的交集的安全基数。 1 3 2 同构分布保护隐私关联规则挖掘 定义关联规则挖掘如下；设i = 瓴， 是项集。d b 是记录集。记录 t d b 是一个包含于，的项集，即了j 。设x 是一个项集，记录r 包含z 当且 仅当x e r 时。关联规则是形如x j y 的蕴涵式，其中x c i ，y c l ， x n y = 彩。规则x j y 在记录集d b 中成立，具有支持度s ，其中j 是d b 中记 录包含z u y 的百分比。规则x j y 在记录集d b 中具有置信度c ，如果d b 中包 含x 的记录同时也包含y 的百分比为c 。有k 个项的项集称为k 项集。挖掘关联 规则，就是要发现所有的规则，其支持度和置信度大于最小支持度阈值和最小置 信度阈值。 同构分布，也即水平分割的分布，指的是记录的不同字段值存放在不同的站 点：设记录分配在n 个站点。项集的全局支持数日是全部局部支持数据的和。如 果一个项集x 的全局支持度大于数据库全体记录数的5 ，那么项集x 就在全局 满足最小支持度。如果一个k 项集在全局满足最小支持度，那么就称之为全局频 繁项集。规则x j y 的全局置信度按照 j u 】 s u p x s u p 来计算。如果一个k 项 集是全局支持的，就称之为全局k 项频繁集。文献 3 0 6 f l 提出一种算法，挖掘分 布式关联规则。 挖掘分布式关联规则的主要目的是发现所有的关联规则，它们的支持度和置 信度大于用于最小支持度阈值和置信度阙值。f d m 算法是用于分布式挖掘关联 规则的快速的方法。总结如下： 候选集的产生。将全局的k 一1 项集与局部k l 项集取交得到候选集。然 后使用经典的a p r i o r i 候选生成方法，得到候选k 项集。 局部剪枝。对于局部候选集中的每个项集x ，遍历局部数据库计算x 的 局部支持度。如果工是局部频繁的，那么它就包括在局部频繁项集列表 天津大学博士学位论文第一章绪论 中。 项集的交换。将局部频繁项集向所有站点广播。局部频繁项集的联合体， 是全局可能频繁项集的父集( 也就是说，如果x 是全局支持的，那么它至 少在一个站点是局部支持的) 每个站点和局部频繁集一起，还使用 a p f i o d 计算项支持度。 支持度交换。广播计算出的支持度。由此，每个站点计算全局频繁k 项 集。 前面的方法没有泄漏个体的记录，却公布了每个站点规则支持度的重要信 息。文献【8 】使用安全联合和安全和的保护隐私s m c 操作，对该算法做了改进。 在保持与上述算法效率相当的基础上，不要求任何一个站点泄漏它局部的频繁 集、支持度或记录数。这样，在项集的交换步骤，应用安全并集的算法，得到安 全并集。然后，通过安全和的方法可以很容易发现全局支持的项集。同样，频繁 集的置信度也可以使用这个方法发现。需要指出的是，如果目标是要求一个完全 安全的方法，那么并集这一步必须被取消。然而，虽然安全并集的方法泄漏了可 以控制的少量信息，但具有比较高的效率。可以通过添加噪音来减少信息泄漏的 有效性。而且每个站点都可以向实际的局部频繁项集中添加一些虚假的频繁项 集。在剪枝阶段，虚假的项被排除。详细讨论见文献【8 】。 1 3 3 异构分布保护隐私判定树归纳 文献 3 1 1 研究了垂直分布的数据库中判定树分类器的建立过程。文中提出的 协议是建立在使用第三方服务器的安全点积协议的基础上。 1 3 4 同构分布保护隐私判定树归纳 文献【3 2 】使用s m c 方法，对于保护隐私的分类问题提出了一个解决方法， 也就是所谓的水平分割数据的遗忘转移协议( o b l i v i o u st r a n s f e rp r o t o c 0 1 ) 。考虑到 一般的s m c 解决方法没有实际值，作者集中在判定树归纳问题上，特别的是i d 3 归纳。i d 3 是一种非常流行而且应用广泛的判定树归纳算法。i d 3 算法通过比较 实值熵来选择认为最好的预测属性。只要不同属性的值相互接近，就认为从中任 选一个得到的判定树会有几乎相同的预测结果。从形式上说，如果对属性的信 息增益差值比6 值还小，那么它们就有相当6 的信息增益。这个定义给出了i d 3 的一个近似。文献 3 2 】提出了一个安全计算的特殊i d 36 算法协议，也就是通过 运行i d 3 算法，在相当6 信息增益的属性中选择任意一个属性，产生所有可能树 的集合。保护隐私的i d 36 算法协议也包括较少的保护隐私计算。其中最困难的 计算简化为对函数x i n x 的估计。 天津大学博士学位论文第一章绪论 1 3 5 保护隐私聚类 文献【2 9 】中给出了保护隐私的安全聚类e m 算法。这儿只给出一维的情况。 可以直接延伸到多维情况。符号协定如表i - i ，i , j 。，分别表示簇、数据点和站点 的大小f 表示迭代的步骤。从传统的e m 混合聚类模型，假定数据数据乃在 j ( 1 9 l s ) 个站点上分割。每个站点有个数据项，所有站点的总和为玎。 表1 - 1 ：聚类中符号约定 簇的总数 分布式站点的总数 数据点的总数 站点，中数据点的总数 在一维情况下观察到的数据点 一维情况下，簇f 的平均值 一维情况下，簇f 的方差 簇i 中项的比例估计 簇成员。如果j ，簇i ，则乃* l ；贝j j z ga o 为了获得”、砰”和硝“”的全局估计，( e 步) 要求全局”值和 z ：5 ，= 乃 ，1 ，；l j = 1 月5m z ，s ，= 艺瑞 ( 1 - 1 ) 1 - 2 ) 孝( 乃一“”) 2 = 喘( 乃一“”) 2 ( 1 - 3 ) 产-，= i ，；l 观察知，上面每个式子中的第二个和为： 氐。- z ( tyi(1-4) t i m 岛= 毋 ( 1 5 ) i = i g = 拶( 乃一”1 ) 2 ( 1 6 ) j = l 可以看出，共享这些值不会泄漏y ，。进一步说，共享吩，4 ，岛和g 是没有必要 的，只需要计算全局和。安全和给出了安全计算这些和的办法。已知全局量肛， j刀坼乃岛砰衙勺 天津大学博士学位论文第一章绪论 砰和巧，估计z 的计算可以分割到本地： 护= 番龋 m 乃 其中乃是站点，的数据点e 步和m 步重复执行，直到l 心“一叠。阵占其中 。”，z ij ，) = 窆j 。l 圭i - 1 拶 1 0 9 乃z ( 够l 伊”) ) 。 1 3 6 异构分布贝叶斯网络学习 【3 3 1 1 3 4 从分布式异构完整数据条件下保护隐私学习贝叶斯网络结构和参 数。这部分的详细说明见论文的第五章。 1 4 基于重建的技术 最近提出了许多保护隐私挖掘的技术。为了执行挖掘，其中许多技术是混淆 数据、在一个聚集的水平上重建分布。下面，对这些技术进行列举和分类。 1 4 1 对数字型数据的重建技术 文献【7 】中讨论了从训练数据中建立判定树分类器的问题，这里的训练数据 中，个体的记录值已经被打乱。而精确估计个体数据记录中的初始值是不可能的， 作者就提出了一个重建程序，去精确估计原始数据值的分布。作者根据重建分布 建立的分类器的精确度可以与根据初始数据建立的分类器相媲美。对于数据的失 真问题，作者考虑了离散化的方法以及数值失真的途径。他们还考虑了贝叶斯方 法来重建初始分布。同时也提出了依靠重建分布，建立精确的判定树的三种算法。 使用最大期望算法，建立基于贝叶斯的重建程序，从而达到分布的重建。文 献【3 5 】对此方法做了改进。而且作者还证明，e m 算法可以聚集到被打乱数据原 始分布的最大似然估计。他们也显示了当大每数据有效时，e m 算法可以提供原 始分布的稳定的估计。还显示了当挖掘者从重建聚集分布中获得额外的知识，而 且这些知识包含在问题表达中时，文献【7 冲提到的隐私的估计必须被降低。 1 4 2 对二进制数据和分类数据的重建技术 文献1 3 6 、f 6 】在关联规则挖掘中处理了二进制和分类数据的问题。当他们对 数据集有高的实用性时，这两篇文章都考虑了提供隐私的随机技巧。 天津大学博士学位论文第一章绪论 1 5 课题背景与论文工作 数据挖掘可能对人们的隐私和数据安全构成威胁。然而，为防止收集的数据 误用，已经提出了许多解决方法。而且，数据库系统中的安全增强技术也可以用 在数据挖掘中，来保证收集到的数据或挖掘出来的数据的安全。 本章基于隐私保护的角度，对保护隐私的数据挖掘进行如下分类：基于启发 式研究( h e u r i s t i c - b a s e d ) 的技术：基于加密的技术；基于重建的技术。基于启发式 研究技术中，已有以下相关论文发表：基于混淆的保护隐私关联规则挖掘、基于 阻塞的保护隐私关联规则挖掘和基于阻塞的保护隐私分类规则挖掘；基于加密技 术中。在异构分布保护隐私关联规则挖掘、同构分布保护隐私关联规则挖掘、异 构分布保护隐私判定树归纳、同构分布保护隐私判定树归纳、保护隐私聚类异构 贝叶斯网络学习方面，已有一些研究成果；基于重建的技术分为基于数字型数据 和基于二进制数据的重建。本文给出了保护隐私数据挖掘算法的分类、扩展描述 和归纳，保护隐私的贝叶斯网络学习是其子课题。 目前，贝叶斯网络已经广泛应用于数据挖掘、医疗诊断、工业控制、投资风 险分析、预测、语音识别等领域，具有非常广阔的研究前景。2 0 0 4 年，国家自 然科学基金项目“面向隐私保护的数据挖掘方法研究”立项；2 0 0 3 年，美国国 家科学基金项目“保护隐私的分布式数据挖掘研究”立项。目前为止，其主要研 究成果是保护隐私的分布式关联规则挖掘。 论文主要主要研究保护隐私的贝叶斯网络的学习。数据源分为异构和同构， 分别在完整数据和不完整数据情况下，保护隐私学习贝叶斯网络。这四种情况， 第一种异构完整数据，已有相关论文发表。本文提出了一种基于m d l ( m i n i m a l d e s c r i p t i o ni e l l g m ，最小描述长度) 的学习方法，比之更安全、精确、适用。另三 种情况下，异构不完整数据、同构完整数据、同构不完整数据的贝叶斯网络学习， 尚未见公开发表的研究成果。本论文对同构完整数据和同构不完整数据、异构完 整数据这三种情况进行了研究。主要创新点如下： 在安全集合并【2 9 】和安全和f 9 2 】的基础上，本文提出了安全事件统计和安 全矩阵求和的安全计算方法；然后应用到基于相关性分析学习网络 t p d a 5 7 ( t h r e e p h a s ed e p e n d e n c y a n a l y s i s ) 算法中，得到有向边安全统 计协议和全局贝叶斯网络参数学习协议。 提出并实现保护隐私学习同构完整数据条件下贝叶斯网络的 p p h c - t p d a ( p r i v a c y - p r e s e r v i n gt p d al e a r n i n go nh o r i z o n t a l l yp a r t i t i o n e d d a t a b a s ew i t hc o m p l e t ed a t a ) 方法。借鉴了t p d a 算法中的相关性分析思 路，进行结构学习，然后按照有向边安全统计协议，将各站点得到的结 天津大学博士学位论文 第一章绪论 构中的边合并。在分布学习中，分别取分布互信息和分布条件互信息的 算术平均值作为整体的互信息值和条件互信息值，并应用到学习的评价 过程中。a l a r m 9 3 和h a i l f m d e r 上的实验结果表明，本章提出的分布式 学习算法p p h c - t p d a 与已有的算法t p d a 相比，效率更高，随着样本 条数增大，学习的精度越接近。 4 提出并实现了从异构完整数据条件下学习贝叶斯网络的p p v c s m d l ( p r i v a c y - p r e s e r v i n gs e r i a ls e a r c ha l g o r i t h mo fm d ll e a r n i n g0 1 1v e r t i c a l l y p a r t i t i o n e dd a t a b a s ew i t hc o m p l e t ed a t a ) 方法。该方法将保护隐私和m d l 方法有机地结合在一起，利用文献 9 0 1 中给出的多向量点积份额协议计 算多向量点积、结构熵，结合利用m d l 方法构建网络，在学习结构的 同时，获得参数。实验验证所提方法与已有方法【3 3 】相比，具有更高的 安全性、适用性、精确性。 o 提出并实现了从同构不完整数据条件下学习贝叶斯网络的p p h i e m ( p r i v a c y - p r e s e r v i n ge ml e a r n i n go l lh o r i z o n t a l l yp a r t i t i o n e dd a t a b a s ew i t h i n c o m p l e t ed a t a ) 方法。基于e m 算法框架进行具有丢失数据的贝叶斯网 络结构和参数的学习，使用期望充分统计因子代替不存在的充分统计因 子，在每一次迭代中，结构都有所改进，使结构序列收敛；同时，每个 网络结构确定的情况下，迭代求解对应的网络参数，使网络参数最优。 引入缺失数据的实验说明，分布学习方法p p h i - e m 与集中学习方法 a m s e m 的学习结果已经比较接近，对于有相对合理丢失率的数据，性 能的降低是缓慢的或者是不可察觉的。引入隐藏变量的实验说明，当实 例数增加时，可以学习更复杂的结构，分布学习和集中学习性能相近。 但对于较小的样本，分布学习性能较差，添加隐藏变量带来较坏的影响。 本文是这样来组织的。第二章首先介绍了贝叶斯网络的发展历史、贝叶斯基 本方法、贝叶斯网络的构造，然后总结了目前为止在完整数据和不完整数据情况 下学习贝叶斯网络的方法。第三章介绍安全多方计算的协议和常用的几种算法。 第四章针对同构完整数据，提出并实现保护隐私学习贝叶斯网络结构和参数的 p p h c - t p d a 方法。各部分首先利用t p d a 算法进行结构学习，然后按照有向边 安全统计协议，将各站点得到的结构中的边合并。随后按照加密算法处理待定边， 可以得到同构完整数据条件下的贝叶斯网络。最后推导加密的计算开销，评价泄 漏信息。第五章针对异构完整数据，提出并实现了一种基于s m d l ( s e r i a ls e a r c h a l g o r i t h mo f m d l ) 的p p v c s m d l 方法。该方法将保护隐私和m d l 方法有机地 结合在一起，利用文献【9 0 】中给出的多向量点积份额协议计算多向量点积，结构 熵，结合利用m d l 方法构建网络，在学习结构的同时，获得参数。实验说明所 天津大学博士学位论文第一章绪论 提方法与已有方法相比，具有更高的安全性、适用性、精确性和效率。第六章针 对同构不完整数据或隐藏变量，提出p p h i e m 方法。它建立在f r i e d m a n 等人 3 8 1 1 3 9 的a m s e m 方法基础上，基于e m 算法框架进行具有丢失数据的贝叶斯 网络结构和参数的学习，使用期望充分统计因子代替不存在的充分统计因子，在 每一次迭代中，结构都有所改进，使结构序列收敛；同时，每个网络结构确定的 情况下，迭代求解对应的网络参数，使网络参数最优。第七章给出全文总结和研 究展望。 天津大学博士学位论文第二章学习贝叶斯网络结构和参数 第二章学习贝叶斯网络结构和参数 贝叶斯网络将有向无环图与概率理论有机结合，不但具有正式的概率理论基 础，同时也具有更加直观的知识表示形式。本章首先介绍了贝叶斯网络的发展历 史、贝叶斯基本方法、贝叶斯网络的构造，然后阐述了目前为止在完整