隐私保护数据挖掘算法综述陈晓明.docx
- 文档编号:10338480
- 上传时间:2023-05-25
- 格式:DOCX
- 页数:20
- 大小:29.35KB
隐私保护数据挖掘算法综述陈晓明.docx
《隐私保护数据挖掘算法综述陈晓明.docx》由会员分享,可在线阅读,更多相关《隐私保护数据挖掘算法综述陈晓明.docx(20页珍藏版)》请在冰点文库上搜索。
隐私保护数据挖掘算法综述陈晓明
隐私保护数据挖掘算法综述*)
陈晓明1 李军怀1 彭 军2 刘海玲2 张 璟1
(西安理工大学计算机科学与工程学院 西安710048)1 (重庆科技学院电子信息工程学院 重庆400050)2
同时考虑的是数据垂直分布在两个站点上的情况。
设数据库是由n条记录构成,对于其中的一个k-项集,站
点A拥有其中的p个属性a1,a2,…,ap,ai1,ai2,…,aip,表示
第i条记录对应在这些属性上的值,X表示一个n维矢量,第
i维的值xi=∏p
j=1aij;站点B拥有剩余的q个属性b1,…,bq,
bi1,…,bip表示第i条记录对应在这些属性上的值。
对于B,
类似的有:
一个n维矢量Y,其第i维的值yi=∏q
j=1bij,于是有k
=p+q。
这样,通过计算X·Y=∑n
i=1xi*yi,可以得出k-项集
的支持计数,从而得出全局频繁集以及关联规则。
但是,如果按照上面的方法,要计算支持计数,那么站点
A或B都必须公布各自的私有信息,暴露了自己的隐私。
针
对这样的情况,JaideepVaidya提出的算法就是一种不向对方
公布自己的向量的情况下计算标量积的方法。
他的根据就是
解一个n元线性方程组,而方程的个数小于n,其结果是不确
定的。
通过这样的方法达到保护隐私的目的,同时还能保证
各方只能得到全局的频繁项集和关联规则。
对各站点将其拥
有的属性构成一个n维系数矩阵,通过产生随机的n个数
R1,R2,…,Rn,使之与其拥有的属性线性组合,通过交换计算
结果得到规则。
2.4 其他
除了以上提到的一些典型方法,其他的学者也提出了另
外的一些隐私保护算法。
例如:
Y.Saygin等在文[15]中通过
在记录中添加“?
”的方法,来对敏感规则进行保护。
文[16]中
利用安全标量积协议提出了一个在数据垂直分布情况下,通
过生成随机向量的方法进行隐私保护;文[17]中在数据水平
分布方式下,利用加密方法建立判定树保护隐私。
Zhan-
gqiangYang等在文[18]中所提到的是一种基于分类规则的
隐私保护方法,算法针对全分布环境下的数据,使用一种简单
的加密方法,各个站点间仅仅向挖掘者进行一次数据传输,在
保护隐私的同时最大限度地保证挖掘的准确性。
LinXia-
odong等在数据水平分布环境下,使用聚类理论提出一种期
望最大化(EM)混合模型[19]。
3 算法的评价标准
目前国内外已经产生出了针对不同环境下的很多的隐私
保护算法。
通过上面对一些目前典型的算法的介绍可以看
出,很明显,在进行隐私保护数据挖掘研究中,对算法作出适
当的评价。
或者说,在进行应用开发的时候,采用哪一种隐私
保护算法是非常重要的。
隐私保护算法可以从下列方面进行
评价和比较:
(1)保密性。
也就是说站在隐私保护的角度,如何能够最
大限度地防止入侵者非法获取隐私数据,对隐私进行有效的
保护。
在现有的算法中,保密是一个最基本的方面,各个算法都
从不同的角度进行了实现。
但是不同的算法都设定了一个特
定的数据模型,而且更重要的是这些算法针对非法入侵者都进
行了一个基本假定,即所有的非法入侵者都是采用同样的入侵
手段来获得数据的。
而实际中,这显然是理想化的。
综合来
看,前面提到的不同算法,所能做到的保密性都是有限的。
(2)规则效能。
规则效能是指在使用隐私保护算法处理
数据的时候,对原始信息的修改使得挖掘结果,也即最终得出
的全局关联规则,与原始数据之间关系的匹配程度。
规则效能其实反映的是挖掘结果的有效性、可用性。
很
多的隐私保护算法是用了混乱或者相似的技术对原有数据进
行了“净化”,主要是针对其中的隐私数据进行了处理。
这样,
处理后的数据如果经过挖掘得出的是错误的,或者说不能反
映真实状况的规则,那么原有的数据也就失去了价值,而这样
处理数据的算法也同样失去了效用。
因而在考虑保护个人隐
私的同时,算法还要能在整体上反映出规则联系。
例如,对于基于关联规则的隐私保护算法,可以从经过挖
掘算法处理后的数据库所得到的规则数目与原始规则的数目
相比较,来得出算法的规则效能;针对分类规则,也可以使用
类似的方法。
(3)算法复杂性。
具体指算法的时间复杂性和空间复杂
性,也即算法的执行时间以及在进行数据处理时使用处理资
源的消耗程度上,可以说这是直接与计算效率直接相关的一
条标准。
算法复杂性的高低体现在该算法所需要的计算机资源的
多少上。
所需资源越多,该算法的复杂性就越高;反之,所需
资源越少,该算法的复杂性就越低。
具体来说需要时间资源
的量称为时间复杂性,需要空间资源的量称为空间复杂性。
特别地,在分布式环境下,通讯复杂性也是一个主要因素。
无
疑,复杂性尽可能低的算法设计算法时所追求的一个重要目
标。
(4)扩展性。
指对算法在处理海量数据集时的能力,或者
是在数据量增加时,其处理效率的变化趋势。
算法的扩展性的好坏直接反映在当所处理的数据量急剧
增大的时候,算法的处理效率是否下降得很剧烈。
很明显,一
个扩展好的算法在数据量增大的同时,其效率的变化是相对
缓慢的。
算法的扩展性在一定程度上是与其复杂性相关的。
例如
基于混乱技术的算法在处理数据时,算法从时间复杂度上讲
是相对较低的,但是从空间复杂度方面,由于其要遍历整个数
据库,计算其中的频繁集,对内存资源的消耗是很大的。
特别
是数据库中的数据量急剧增大的时候,其处理效率会显著降
低,扩展性不好。
结束语 本文对目前比较典型的各种算法进行了一定的
介绍和分析,综合提出了评价隐私保护算法好坏的4条标准。
实际上,上述这些算法在保密的准确度方面差别不大,在当今
数据量急剧增长的时代,算法的复杂性、扩展性以及规则的效
能等特性更为重要。
此外,由于算法针对的目标不同,效果一
般和数据的特点有关,目前还不存在能适合各种不同数据的
最佳通用方法。
一种各方面特性都很好的算法,仍有待进一
步研究。
参考文献
1CranorLF,ReagleJ,AckermanMS.Beyondconcern:
Under-
standingnetusers'attitudesaboutonlineprivacy:
[TechnicalRe-
portTR99.4.3.].AT&TLabs-Research,1999.http:
//www.
2VaidyaJ,CliftonC.Privacypreservingassociationruleminingin
verticallypartitioneddata.In:
the8thACMSIGKDDInternational
ConferenceonKnowledgeDiscoveryandDataMining,2002.639
~644
3HanJiawei,KamberM.数据挖掘概念与技术.范明,孟小峰,等
译.北京:
机械工业出版社,2001.8
4VerykiosVS,BertinoE,NaiFovinoI.State-of-the-artinPrivacy-
preservingDataMining,SIGMODRecord,2004,33
(1)
5OleveiraSRM,ZaianeOR.ProtectingSensetiveKnowledgeby
DataSanitization.In:
ProceedingsoftheThirdIEEEInternational
ConferenceonDataMining,2003
(下转第199页)
·186·
根据修改后的数据来发现关联规则。
以下是其中的关键
性概念。
①隐私漏洞
我们知道项集A产生了一个等级为ρ的隐私漏洞,如果
对某个项目a∈A以及某个i∈1…N,有P[a∈tiAt′i]≥
ρ,也就是说一个在随机化交易中的项集A,如果A中的某个
项出现在非随机化交易中的概率不小于ρ的话,那么就可以
说项集A产生了等级为ρ的隐私漏洞。
②select-a-size运算符
对于每个可能输入的规模为m的交易,一个“选择一个
规模(select-a-size)”运算符R有如下参数:
a)某一个项默认的随机化等级ρm∈(0,1);
b)交易子集规模选择的概率pm[0],pm[1],…,pm
[m],且每个pm[j]>=0,pm[0]+pm[1]+…+pm[m]=
1。
对于给定的交易序列T=(t1,t2,…,tN),运算符独立
地取走每条交易ti,并且按以下步骤处理t′i(m=ti):
a)运算符从集合{0,1,…,m}随机选择一个整数j,这样
P[j被选择]=pm[j]。
b)运算符同样是随机地从ti中选择j个项目(没有替
换),这些项目(不含其他ti)被放入t′i。
c)运算符反过来考虑每个项目ati,然后以“正面”概率
为ρm、“反面”为1-ρm抛出一枚硬币。
所有结果是“正面”的
项目加入到t′i。
③cut-and-paste运算符
一个“剪切粘贴(cut-and-paste)”运算符是select-a-size运
算符中特殊的一类。
对于每种可能输入规模为m的交易,它
有两个参数:
一个ρm∈(0,1)和一个整数Km>=0,运算符独
立地处理每个交易ti并按以下方法得到交易t′i(m=ti):
a)选择在0与Km间随机选择一个整数j;如果j>m,那
它会设置j=m。
b)随机地从ti中选择j个项目放入t′i。
c)每个项(包括ti剩余的部分)以概率ρm独立地放入
t′i。
ShariqJ.Rizvi等学者在文[11]中根据朴素贝努里概型
提出了一种称为MASK的隐私保护算法。
作者使用的数据
库是由固定长度的0,1序列形成的记录组成的。
算法的具体
实现是通过对所有原始数据按照贝努里概型进行变换,具体
来说,设原始数据X={Xi},Xi=0或1,使用变换函数Y=
distort(X),其中Yi=XiXORri,ri是服从贝努里分布的一
个随机变量,即取1的概率为p,取0的概率为1-p。
考虑到
对原始数据进行变换所耗费的时间和空间,远比在数据挖掘
时对数据的重建的消耗要大很多,因而Shariq后来对MASK
算法进行了一些优化。
(2)基于分类的隐私保护
数据挖掘通过对大量数据的统计计算找出趋势,而不一
定要知道百分之百真实的数据。
R.Agrawal在文[12]中提出
了一种基于重建式的技术,算法针对数值型数据概率分布的
重建,该算法通过添加随机偏移量对原始数据进行随机化混
乱,然后使用贝叶斯公式,根据原始数据的分布来重建决策
树。
通过重建数据分布可以建立一种准确程度接近真实数据
分布的分类标记。
同时,R.Agrawal引入了一些量化方法来
检验通过上述方法处理后的数据隐私泄漏状况,从置信度以
及预测的准确程度上对算法进行了检验。
具体地讲,如果可
以以c%的置信度预测出某个数值x处在某个区间内,那么
这段区间的宽度就决定了带有c%置信程度的隐私数量。
但
是由于贝叶斯定理的成立本身需要一个很强的独立性假设前
提,而此假设在实际情况中经常是不成立的,因而其分类准确
性就会下降。
2.2 数据水平分布
从表1中我们可以看出,如果数据的分布方式不再是集
中式的,那么如果要进行隐私保护,那么大多数数据挖掘领域
采用的是基于加密的技术。
特别是在分布式环境下的隐私保
护问题,安全多方计算(SMC)是最为常用的一个协议。
安全
多方计算是在一个互不信任的多用户网络中,各用户能够通
过网络来协同完成可靠的计算任务,同时又能保持各自数据
的安全性[13]。
下面所提到的基于加密的隐私保护算法,以及
后面数据垂直分布情况下的基于加密的隐私保护算法都是可
以划归为一个特殊的安全多方计算协议。
在基于加密技术的隐私保护方面,对于隐私的定义,Ben-
nyPinkas在文[8]是这样给出的:
限制通过分布式计算所能
获得的满足其要求的所泄漏的信息称之为隐私。
Benny
Pinkas对安全多方计算在基于加密技术的隐私保护方面的应
用作了一定的探讨,认为安全两方计算的构建要易于安全多
方计算,同时影响协议的一个重要方面是用于计算评价函数
的最佳组合电路的规模,而影响计算的因素则来自健忘传输
协议以及协议的改进程度。
MuratKantarcioglu在文[14]中提出了一种数据水平分
布下的针对关联规则的隐私保护数据挖掘算法。
数据水平分
布是指数据按照记录分布在各个站点,在此条件下,各个站点
不必知道其他站点的具体记录信息,就可以计算出全局的关
联规则。
算法提出的目标就是各个站点除了知道全局的结果
之外,对其他各站点的信息一无所知。
算法通过两个步骤找出全局频繁项集:
第一步使用交换加密的方法发现候选集。
各个站点加密
各自的频繁项集,然后将结果传递到下一个站点。
传递的同
时去掉重复的集合,整个过程一直持续到所有的站点加密完
所有的项集,然后各个站点使用自己的密钥对得到的结果进
行解密,最后得到一个公共的项集。
第二步找出满足条件的全局频繁集。
首先第一个站点计
算由第一步得到的项集在本地的支持度与最小支持度阈值之
间的差,然后加上一个随机数R,将结果传给下一个站点;第
二个站点做与第一个站点相同的工作,同时加上第一个站点
传来的值,接着将结果传递至下一个站点;依次直至传递完所
有站点,最后的值传递回第一个站点。
最后在第一个站点将
结果与R比较,如果该值不小于R,则说明该项集为全局频繁
项集。
最后通过计算开销和通讯开销对上述算法进行了评价,
同时MuratKantarcioglu还提出了一些改进的方向。
2.3 数据垂直分布
JaideepVaidya在文[2]中提出了一种数据垂直分布条件
下的基于关联规则的隐私保护算法。
垂直分布是指数据按照
属性分布在各个站点,在这种条件下,可以通过发现项集的支
持计数来进行数据挖掘。
如果某个项集的支持计数可以被安
全地计算,那么通过检查计数和预先设定的阈值比较,就可以
知道该项集是否是频繁项集。
JaideepVaidya通过安全地计
算代表子项集的标量积的方法来得到项集的支持计数。
在这
里,作者同样将目标数据库视作是由固定长度的0、1序列构
·185·
保护技术大体上可基于下面因素对它们分类:
数据分布、
隐私保护技术、数据或规则更改方法、数据挖掘算法。
表1所示的是根据数据分布方式对现有一些典型算法的
一种划分。
下面将着重对其进行归纳和介绍。
表1 隐私保护算法分类
数据分布
方式
隐私保护
技术
数据更改
方法
数据挖掘
算法文献
集中式
启发式
滑动窗口法关联规则[5]
随机修改部分值为
1的数据为0关联规则[7]
添加随机数关联规则[15]
重建式
添加随机偏移量分类[12]
随机修改部分数据关联规则[10]
贝努里概率模型关联规则[11]
水平分布加密式加密、添加随机数关联规则[14]
垂直分布加密式加随机数关联规则[2]
其他[15]、[16]、[17]、
[18]、[19]
2.1 数据集中分布
2.1.1 启发式技术
针对数据挖掘中的隐私保护,很重要的一个方面都是集
中在对关联规则的应用,从根本上来说都是通过各种方法来
降低敏感规则的支持度或者置信度,由此诞生出了分类、聚类
等方法来发现敏感规则或者敏感数据。
理论上说,这些技术
都是基于一种假设,即选择性的数据清理与修改是一个NP-
Hard问题。
而启发式算法在解决这一问题上,可以省略大量
无谓的搜索路径,提高效率。
(1)基于关联规则的隐私保护
StanleyR.M.Oleveira和OsmarR.Zaiane在文[5]中提
出一种基于启发式的隐私保护方法,该算法通过一种单次扫
描算法来实现对敏感规则的保护。
与其他的混乱式的方法不同,混乱式的方法是通过修改
现有数据或者在原始数据中添加随机数据达到隐藏敏感规则
的目的。
而StanleyR.M.Oleveira提出的算法是一种非混乱
式的算法,该算法通过移除部分信息的方法实现数据清理,从
而隐藏敏感规则,并不对原始数据库添加任何噪声,文中称作
是滑动窗口的算法。
具体讲,设D是交易数据库,Rr是敏感
规则,~Rr是非敏感规则,R是D中全部的关联规则,可以看
出Rr∪~Rr=R。
只要交易中包含有任何敏感规则,那么它
就被称作是敏感交易。
为了达到隐藏敏感规则的目的,就必
须对原始记录中涉及到敏感规则的敏感数据项进行处理,通
过去除部分敏感项,使得规则在某种阈值范围内隐藏,而那些
候选要被去除的敏感项在文中被称作是牺牲项(victimi-
tem)。
从具体实现上,数据库D被分成若干组数据交易,每组
交易包含有K个记录,K称作是窗口大小。
数据清理的过程
分为5个步骤,
第一步,从D中找出所有的R,同时区分出Rr和~Rr,
并把~Rr直接复制到处理后的数据库D';
第二步,选取在当前交易敏感规则中出现频率最高的项
作为牺牲项;
第三步,通过设定暴露阈值,计算要清理的交易数量;
第四步,针对每一个敏感规则,对前一步中的敏感交易按
照其规模进行排序,将规模最小的作为被清理的对象,以达到
对原始数据的影响尽可能地小;
第五步,删除每条敏感规则中的敏感项,将清理后的数据
复制到不含敏感规则的数据库D'。
最后使用清理敏感规则后生成的数据库D'公布给外界,
以此达到保护隐私的目的。
StanleyR.M.Oleveira等人还在文[6]中提出了类似的
方法,算法通过一个基于倒排文件索引和布尔查询的交易检
索引擎来实现对数据库的清理,同样是通过减少敏感规则中
的敏感数据,达到支持度的降低,从而实现对敏感规则的隐
藏。
同时文中针对算法提出了三条评价标准:
HidingFail-
ure,也就是从清理后的数据库D'中发现敏感规则的百分比;
MissesCost,即在清理数据库D'中隐藏的非敏感规则所占的
比例;ArtifactualPattern,即虚假的规则所占的比例。
ElenaDasseni等在文[7]中提出了一种基于混乱的方法,
通过隐藏与敏感规则相关的频繁项集,以及通过设定阈值来
减少置信度,防止敏感规则的产生。
在其具体实现上,是通过
将频繁项集中的二进制数反转,即数值为1的变为0,为0的
数值变为1的方式。
这样,隐藏关联规则的方法存在一个很
明显的缺点,就是会产生一些“影子规则”(ghostrules)[4],因
为通过以上的反转,将会使得一些原本是非敏感的规则变为
“敏感规则”。
(2)基于分类规则的隐私保护
分类是这样一个过程,它找出描述并区分数据类或概念
的模型或函数,以便能够使用模型预测类标记未知的对象类。
导出模型时基于对训练数据集(即其类标记已知的数据对象)
的分析[3]。
分类的目标就是要构造一个分类模型,从而预测
未来的数据趋势。
从目前来看,分类采用的方法主要有分类
规则、决策树、神经网络等。
而基于隐私保护的分类技术则是
要在数据挖掘过程中建立一个没有隐私泄露的准确的分类模
型[8]。
文[9]中提出的一种隐私保护方法就是结合了分类规则
以及一种称作是吝啬降级法(parsimoniousdowngrading)。
吝啬降级法是这样的一种算法:
针对要降级的数据中将
要去掉的信息的一种形式化描述,其中所谓的降级是指从敏
感级或隐私级(称之为高级别)降低到可以公布级(低级别)。
算法的主要目标是要找出由于修改而导致的数据库功能性的
损失是否是值得的。
就其实现而言,算法通过产生一个称之
为参变量基础集的方法来实现数据的降级。
使用一个参数θ
∈[0,1]来取代敏感数据(θ表示某种属性取得一个可能的值
的概率)。
同时对于降级前和降级后的数值的熵进行计算,使
用二者的差值同数据库变化前后置信度的降低程度比较,从
而得出这种对数据库的修改是否是可以接受的,也即是否对
数据库的影响是最小的。
2.1.2 重建式技术
(1)基于关联规则的隐私保护
A.Evfimievski等在文[10]中提出了一种基于重建式的
隐私保护算法,该算法使用了一种称之为统一随机化的方法
(UniformRandomization)。
所谓的统一随机化是指在将一个
交易发送给服务器前,客户端取走每一个项时,将之以概率p
替换为原先在交易中没有的新项,这个过程叫做统一随机化。
算法针对的是分类数据(categoricaldata),重点是为了发现关
联规则挖掘中的频繁项集。
文中对隐私漏洞(PrivacyBrea-
ches)进行了定义,提出了使用“select-a-size”和“cut-and-
paste”等随机运算符来修改原始数据,控制隐私漏洞的发生。
·184·
863项目资助(编号:
2002AA414060)和2005年陕西省自然科学基金资助(编号:
2005F05)。
陈晓明 硕士研究生,主要研究方向为Web数
据挖掘及Web应用;李军怀 副教授,主要研究方向为分布式计算、CSCW;彭 军 副教授,主要研究方向为计算机应用、网络安全;张 璟
教授,博士生导师,主要研究方向为Internet技术及应用;刘海玲 硕士,研究方向为分布式计算、Web服务。
表1 孤立点挖掘结果列表
孤立点序号会员编号X1X2X3
1464514848450774
2708115698441891
3535145628432381
4978155232243462
5989114445334373
61071175619140252
7302263694655740
8938315530445005
表2 三个指标的平均值与标准差
X1X2X3
平均值13.39213391.412999.33
标准差3.2857611.835831.29
表3 各指标相关系数
X1X2X3
X11.00000.39800.5390
X20.39801.00000.9238
X30.53900.92381.0000
从表3可以看出,各指标存在一定的相关性,有必要用独
立成分分析的方法对原指标数据进行处理。
从表1与表2可
以看出,孤立点1,7,8的三个指标都很明显偏离中心值,孤立
点2,3,4,5,6,7的指标X2,X3偏离中心值,与实际情况基本
相符合。
如果孤立点数据被确定,应当对其内容进行细查,根
据其特征和挖掘目的而确定其是否为真正的孤立点数据。
我
们从该航空公司的会员信息表中查询,确认对表1中列出的
八个会员为该航空公司的金卡会员,是重点客户,这也说明了
IMVOM模型的合理性。
小结 一般高维数据的内部十分复杂,很难被探测,而人
眼视觉对二维的几何空间分布却有着绝佳的分析能力,如果
能够将高维数据资料转成人眼可以观察到的图形的话,对于
高维数据的孤立点挖掘将是很有帮助的。
本节在ICA与
MViSOM的基础上提出了一个IMVOM孤立点挖掘模型,
IMVOM模型先通过ICA去除了数据之间的相关性,并通过
MViSOM算法保持数据之间一定的拓扑结构不变性,并取得
数据的可视化
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 隐私 保护 数据 挖掘 算法 综述 陈晓明