基于安全多方计算的分布式关联规则挖掘.ppt

1、基于安全多方计算的分布式关联规则挖掘的隐私保护,学生：胡天寒 导师：朱玉全,目录,研究背景及意义 国内外研究现状 研究目标与内容 研究方法 课题创新点 进度安排,研究背景及意义,近年来,随着技术的进步、计算能力以及存储能力的日益提高,挖掘数据集规模有了迅速的增长,而且这些数据集大部分都按地理位置分布于多个场所。为了挖掘如此巨大且分布式排列的数据集,越来越多的分布式算法被研究出来。分布式数据挖掘就是使用分布式计算,从分布式数据库中发现知识的过程。,数据的隐私性保护是分布式数据共享及计算得以广泛应用的主要障碍,数据是分布在不同的地点,分属于不同组织,在进行合作运算的同时相互之间并不希望其他参与方知

2、道自己的原始数据及一些能推测出有用信息的敏感中间计算结果,这就迫切需要发展一种能适用于在分布式环境下具有隐私保护特性的通用分布式计算方法,使得各参与节点在无法获取其他节点信息及敏感中间计算结果的条件下协作计算，得到准确的挖掘结果。,国内外研究现状,YAO 于1986 年提出了两方安全计算；随后Goldreich 将其推广为对于任何函数都成立的多方安全计算方法。 B. Pinkas 提出了将密码学理论的研究应用于数据挖掘中的隐私保护,并且证明了不同种类的数据挖掘问题都可以转化为安全的多方计算。 C. Cliffton等人提出了支持隐私保持的四种安全多方计算的方法。它们分别是:安全和,安全并集,安

3、全交集大小以及标量积方法。,M.Kantarcioglu 等提出了针对水平分割数据的保持隐私的关联规则挖掘的算法。探讨了如何在两个垂直分布的私有数据库的联合样本集上施行数据挖掘算法, 同时保证不向对方泄露任何与结果无关的数据库数据。 Jaidepe vaidya 提出一个从垂直分割的数据中挖掘全局关联规则的隐私保护算法，算法通过安全地计算代表子项集的标量积的方法来得到项集的支持计数。,黄毅群等人研究了一种基于向量点积的关联规则挖掘算法，给出了一种安全的向量点积协议。对于垂直划分的分布式数据库，该协议既可用于搜索频繁项集，又能保持各方数据的隐私。,研究目标与内容,本课题研究的内容是数据挖掘中基于

4、分布式关联规则的隐私保护问题。在保护数据方面，针对不同的数据分布分别进行研究并提出基于分布式关联规则挖掘的隐私保护算法。 对基于向量点积的分布式关联规则挖掘算法进行改进。此算法在分布式环境下,利用保持隐私数据挖掘的基本方法和安全多方计算协议,可以在不泄露任何隐私的基础上有效地对垂直型数据分布进行挖掘。,挖掘关联规则的步骤大体分为两步来描述 (1)找出所有的频繁项集。即找出所有那些支持度大于事先给定的支持度阈值的项集。 (2)在找出的频繁项集的基础上产生强关联规则。即产生那些支持度和置信度分别大于或等于事先给定的支持度阈值和置信度阈值的关联规则。 关联规则的关键在于项集支持度的计算。本课题是对第

5、一步频繁项集的挖掘进行研究，提出一种适合于多个站点(=3)的安全求解项集支持度算法。,研究方法,1)选择用于适合本实验的数据源。数据源要求是分布式数据库,或者是把集中式数据库按水平方式或垂直方式划分后分布在不同站点的分布式数据集(多于两个站点)。 本课题选择了三家零售商的交易数据库进行联合挖掘。三家零售商分别为A，B，C，每个零售商的交易数据库为Da,Db,Dc。各家零售商都希望在保护自己数据的同时得到有价值的挖掘结果，本课题研究的目标就是使各个站点得到有价值的信息，同时保证单个站点隐私的泄露。,2)改进基于向量点积的关联规则挖掘算法，由安全两方适用于安全多方。 有关垂直型数据库,现在的此方面

6、的算法大部分是基于Apriori为主应用两方安全计算,使用apriori-gen函数去产生所有的侯选集,对挖掘的每一项,算法都通过计算标量乘积的形式来判定是否为最大项目。,如果按照上面的方法，要计算支持计数，那么站点A 或B 都必须公布各自的私有信息,暴露了自己的隐私。 以安全三方为例，提出一种改进的安全向量点积方法来保护各方的隐私。 算法描述如下： Step1 L=large-1itemset Step2 for(k=2;Lk-1不为空；k+ do begin Step3 Ck=apriori-gen(Lk-1) Step4 对于所有的候选集 do begin Step5 如果C中所有属性属

7、于A或B或C Step6 A,B,C独立计算c.count,Step7 否则 Step8 假设A拥有C中的p个属性，B拥有q个属性，C拥有剩下的r个属性 Step9 三方各自计算向量X，Y，Z Step10 A,B,C三方各自产生三对数据(K1,V1),(K2,V2),(K3,V3) Step11 向量X乘上系数K1,再加上偏移量V1，得到向量x Step12 将变换后的向量x传给Y Step13 Y接到X，计算向量XY，并将y1+y2+yn传给向量X Step14 A方计算XY-V1(y1+y2+yn)/K1得到结果XY Step15 将XY传送给Z，并计算XYZ，得到c：count Step16 if c:count=minsupport,将候选c加入到Lk中 Step17 end,3)在Microsoft Visual C+ 6.0环境下编程实现第二步的算法。 4)从挖掘结果的正确性，计算开销，通信代 价和安全强度几个方面来评价算法的性能。,课题创新点,1) 改进了基于向量点积的分布式关联规则挖掘。 2)对多个站点(=3)安全求解项集支持度。,进度安排,2009.7-2009.11 参阅国内外相关资料，确定课题方向