差分隐私的数据流关键模式挖掘方法

频繁模式挖掘是数据挖掘的重要任务之一,在数据流上挖掘简洁的关键模式比频繁模式更有优势,因为关键模式既可以避免频繁模式里包含的冗余信息以减少内存存储空间,又可以高效无损地提取频繁模式.但是由于相邻时间戳的统计信息可以作为背景知识增强攻击者的推理能力,所以从包含个人信息的数据流中挖掘关键模式比静态场景下更容易泄露隐私.分析指出了数据流关键模式挖掘的隐私泄露问题及原理,并提出了一种满足差分隐私的数据流关键模式挖掘算法DP-CPM,该算法在每个时间戳设计一种两阶段机制：差异计算阶段和噪音挖掘阶段.该机制既考虑了隐私和数据效用之间的权衡,又考虑了挖掘时间和维护开销之间的权衡.为了提高数据流中连续发布时的数据效用性,在第1阶段通过计算差异来决定当前时间戳是返回低噪音统计值还是精确的近似统计值.如果是返回低噪音统计值,算法进入噪音挖掘阶段.在噪音挖掘阶段,首先通过判断查询集筛选出关键模式候选集,然后通过给筛选出的候选集里的模式支持度加入服从拉普拉斯分布的随机噪音,得到最终的噪音支持度.最后,给出了严格的理论分析和大量的实验,表明DP-CPM算法的有效性和执行效率.

Crucial Patterns Mining with Differential Privacy over Data Streams

Frequent patterns mining is an important task for data mining. Nevertheless, mining concise crucial patterns is more promising than frequent patterns over data streams, since crucial patterns can avoid redundancy to reduce storage space and extract lossless information from frequent patterns. Nevertheless, mining crucial patterns from data streams which aggregate information from individuals is more likely to reveal privacy than static scenarios, because the background knowledge of the release at adjacent time instances can enhance the adversary''s inferential ability. This study points out the problems and principles of privacy leakage over mining crucial patterns in data streams, and proposes a differentially private crucial patterns mining algorithm which designs a two-phase mechanism at every timestamp. Specifically, the two-phase mechanism includes the dissimilarity calculation phase and the noise-mining phase, which considers not only the tradeoff between privacy and utility but also the tradeoff between mining time and maintenance cost. To improve data utility over successive releases in streams, the dissimilarity is computed to decide to return either low noisy statistic or accurately approximated statistic in the first phase. When the low noisy statistic needs to be turned, the algorithm goes into the noise-mining phase. In the noise-mining phase, crucial pattern candidate set with a judgment query set is firstly identified, and then random noise drawn from the Laplace distribution to their supports are added to obtain the noisy supports. Finally, strict theoretical analysis and extensive experiments are provided to confirm the effectiveness and efficiency of our algorithm.