一种面向数据流top-k频繁模式发布的差分隐私保护方案

摘要

频繁模式挖掘是事务数据分析的常用技术,面向数据流的频繁模式挖掘具有重要的应用价值.然而当事务为敏感信息时,直接发布频繁模式及支持度会导致个体隐私泄露.差分隐私是一种严格且可证明的隐私保护模型,目前虽然已有基于差分隐私的频繁模式发布方案,但它们大都是面向静态数据做一次性发布的隐私保护.本文是面向数据流频繁模式发布的隐私保护,旨在设计一种兼顾可用性和发布效率的持续发布的差分隐私保护方案.与静态发布方案不同,面向数据流的隐私保护处理面临两大挑战:一是持续发布过程中隐私预算的累计消耗会造成发布结果可用性较低;二是候选模式集增大会造成发布结果误差较大和发布效率较低.为解决隐私预算的累计消耗问题,方案设计了满足event级差分隐私的保护机制.该机制可以最大化隐私预算利用率,提高发布结果可用性.为降低候选模式集大小,从而提高发布结果可用性和发布效率,方案首先设计了一种基于模式估计的长事务拆分预处理策略,并对拆分所致的信息丢失率进行了分析和弥补.然后在持续发布阶段,在基于Cantree的挖掘中,先基于支持度阈值对候选模式集进一步缩减.基于缩减后的候选模式集,本文设计了 一种蓄水池抽样和指数机制(EM)相结合的持续更新发布策略,该策略通过一遍扫描抽样集,在保证可用性和隐私保护级别的前提下提高了发布效率.最后,理论证明了该方案满足ε-差分隐私,实验结果验证了该方案具有较好的可用性和较高的工作效率.