数据仓库与商务智能实验室团队论文在计算机学报上发表
ABOUT
标题：一种面向数据流top-k频繁模式发布的差分隐私保护方案
作者：梁文娟(中国人民大学),陈红(中国人民大学),赵素云(中国人民大学),李翠平(中国人民大学)
团队：中国人民大学数据仓库与商务智能实验室
论文接收情况：Publishedby计算机学报
本文面向不断更新的事务流，设计了一种top-k频繁模式发布的差分隐私保护方案。方案不仅能满足动态场景中隐私化处理的高效性要求，也能保证隐私处理后发布数据的高可用性。该方案在多个真实数据集上频繁模式发布任务中均取得较好效果。
研究动机
目前已有很多基于差分隐私的频繁模式发布方案研究，但它们大都是面向静态数据做一次性发布的隐私保护。由于信息系统中事务数据的更新速度很快，相关研究不能满足对不断更新数据发布的隐私保护需求。为此，本文旨在面向不断更新的事务数据流，设计一种满足差分隐私保护的top-k频繁模式发布方案。面向事务流的隐私保护处理面临两大挑战：一是隐私保护处理过程必须满足一遍事务扫描的高效处理要求；二是持续发布中候选模式集的增大会造成发布结果误差较大和发布效率较低。因此，本文探讨了如何在兼顾高效发布的同时，提高隐私发布频繁模式的可用性问题。
解决方案
图1.方案总体框架。方案基于动态频繁模式挖掘的数据结构-Cantree设计，为在满足差分隐私要求的前提下提高数据可用性和发布效率，方案中设计了两个核心策略，分别是：基于模式估计的事务拆分和结合蓄水池抽样的指数发布机制。
差分隐私下面向事务流的频繁模式发布机制必须满足以下三条约束：一是结合隐私保护处理的发布过程必须实现对事务的单次扫描，以满足数据流处理的特点；二是持续发布过程中，由于候选模式集的持续增大，会造成发布结果误差较大；因此需设计满足差分隐私的候选模式空间缩减方案，以降低发布结果误差；三是在对每个发布时刻的候选模式空间遍历挖掘top-k模式时，需设计高效且满足差分隐私的top-k采样策略以满足实时发布要求。针对上述约束，方案首先基于动态频繁模式挖掘的数据结构-Cantree设计发布机制以满足第一个约束。然后方案设计了一种基于模式估计的长事务拆分预处理策略来应对第二种约束。最后是设计结合蓄水池抽样和指数机制的top-k模式采样策略以满足第三种约束。
基于模式估计的长事务拆分
在频繁模式发布过程中，生成的候选模式越少，所需添加的噪声量会越少。原因是候选模式减少会降低发布敏感度，同等隐私级别下噪声量可以减少。同时，候选模式减少可以降低遍历时间，发布效率也会提高。为此，我们设计了一种基于模式估计的事务拆分预处理策略，目标是通过拆分事务来缩减候选模式空间。策略中充分利用事务数据集中1-项集和2-项集的统计信息，估计出长事务中的频繁项，将经常一起出现的频繁项拆分到同一短事务中。这样不仅可以缩减候选模式空间，还可以降低信息丢失率，保障发布数据的高可用性。同时，该策略可以在一次事务扫描中完成，也可以保障发布的高效性。具体见如图2。
图2基于模式估计的拆分
以往研究中，也有截断事务或拆分事务的预处理策略，为降低信息丢失率，他们会先找出所有项之间的依赖关系或真实频繁模式等统计信息来指导预处理过程。与以往研究不同，我们的策略是找出当前事务中项之间的关系而非全部项之间的依赖关系来指导事务处理过程。其优点有两个：一是降低预处理时间。由于事务集中包含的项非常多，相比于统计全部项的关系，只统计当前事务中项的关系所需的处理时间更少；同时，拆分事务时的搜索空间大大降低，同样降低了预处理时间。二是降低信息丢失率。基于模式估计找出当前事务中的频繁项集，拆分时可以将频繁项尽量保留在同一个事务中，从而最大限度的降低信息丢失率。
该策略设计的挑战在于，首先模式估计涉及对用户真实事务的统计，会存在隐私泄露问题。针对这一问题，我们对该过程中计算任务的敏感度和隐私预算进行了分析，设计了对应的噪声添加方案以满足差分隐私。其次，为降低拆分带来的信息丢失，我们会在当前待拆分的长事务T中重复找出最优短事务。因此，如何衡量事务的优劣需要进行定义。针对这一问题，我们定义了最优短事务，并设计了满足最优短事务要求的贪心事务拆分算法。如图4所示：
结合蓄水池抽样和指数机制的发布策略
基于拆分后的事务集，在调用指数机制(EM机制)实现发布过程的差分隐私性时，我们发现EM机制中采用的是权重随机抽样方法，该方法需要遍历候选模式集两遍：第一遍是计算各候选模式的权重值wi，然后基于权重值计算各模式的抽样概率；第二遍基于各模式的抽样概率，执行k遍抽样出top-k模式。由于候选模式集一般较大，遍历两次集合效率太差。针对这一问题，我们考虑设计结合蓄水池抽样和指数机制的发布策略。原因在于蓄水池抽样方法只需对候选模式集进行一次遍历，效率较高。并且针对同样的抽样集，蓄水池抽样和权重随机抽样输出相同模式的概率是一样的，能保证抽样结果的正确性。
结合蓄水池抽样和指数机制策略设计的挑战在于，EM机制的设计核心是需要为每个候选模式设计打分函数，基于打分值计算模式的抽样概率，使得抽样出的top-k噪声模式满足差分隐私要求的同时尽量降低发布结果的误差。每个候选模式e设计了打分函数设计如下：
基于候选模式的打分函数，为每个候选模式设计了其蓄水池抽样权重，确保基于该权重的蓄水池抽样结果的准确性。
该策略的具体执行过程为：在递归挖掘频繁模式的过程中，每生成一个候选模式，计算其蓄水池抽样权重；根据该模式的权重值，判断是否将其添加或替换到蓄水池中。最后蓄水池中保留的top-k模式既能满足差分隐私保护要求。
实验结果
基于真实数据集BMS-WebView-1(WV1)、PUMSB、POS，对所提方案的可用性及效率进行评估和验证。对比方法包括PFP和PrivSuper，PFP是基于所有项之间的关联进行长事务拆分，PrivSuper是通过隐私化发布最大频繁模式集来节约隐私预算。实验分别评估了不同k值、不同隐私预算?值的可用性和不同方案的运行效率。
图3k值和?值对可用性的影响
图4模式估计和蓄水池抽样的优点评估
实验表明，相比于现有方案，我们发布方案在可用性上能提高3-9%。具体分析如下：PrivCE要比PrivSuper的可用性数值在所有情况下高出3％～5％．其主要原因在于PrivCE中采用的是基于模式估计的拆分，而PrivSuper中是基于随机抽样的拆分．后者因拆分所导致的信息丢失率较大．在所有情况下，PrivCE要比PFP的可用性高5％～9％．原因如下：在拆分时，PrivCE方案只需根据拆分事务的频繁模式集进行拆分，而PFP则需要提前找出所有事务包含的项目之间的依赖关系，并根据结果进行拆分．因此，PrivCE拆分会更准确．在效率上能降低大约10s-s的处理时间，如图3和图4。
总结
针对面向数据流持续发布top-k频繁模式中的隐私泄露问题，本文提出了一种满足事件级差分隐私保护方案。方案中设计了两种策略提高发布结果可用性和发布效率：一是基于模式估计的长事务拆分策略，在降低候选模式空间的同时提高发布效率；二是蓄水池抽样和ＥＭ机
制相结合的发布策略提高top-k模式发布效率．我们不仅理论证明了该方案满足?-差分隐私，并且实验验证了该方案的高可用性和效率。
作者介绍
梁文娟,中国人民大学级博士生，计算机应用技术专业，主要研究方向为数据隐私保护、数据挖掘，参与“隐私保护研究”的国家自然科学基金项目2项，曾在SCIENCECHINAInformationSciences、ComputersSecurity、软件学报、计算机学报以及ICICS等重要国际期刊和会议上发表论文5篇。
导师介绍
陈红，中国人民大学信息学院教授、博士生导师。中国计算机学会数据库专业委员会常务委员、物联网络专业委员会委员。主要研究方向数据库、数据隐私保护和大数据系统。主持和参加国家重大专项项目、国家项目、国家计划项目、国家自然科学基金重点项目等项目30余项；在国内外学术期刊和学术会议上发表论文余篇，出版数据库方面的著译作8部。参加了具有自主版权的并行数据库系统软件的研制，主持了具有自主版权的联机分析处理系列软件的研制。获得国家发明专利多项。获教育部科技进步一等奖和二等奖、北京市科学技术进步二等奖、北京市科学技术二等奖、中国计算机学会科技进步一等奖、国家精品课程奖、国家精品资源公共课、北京市精品课程奖、中国人民大学十大教学标兵等奖励，5年入选教育部新世纪优秀人才支持计划。
预览时标签不可点收录于话题#个上一篇下一篇