满足差分隐私的频繁模式挖掘研究

Frequent pattern mining is one of the most fundamental problems in data mining, which has a wide range of applications. However, if the data sets involve sensitive personal information, directly publishing or sharing discovered frequent patterns might lead to serious privacy leakage. Differential privacy proposed in recent years provides a feasible way to address such problem. Unlike the anonymization-based privacy models, differential privacy offers a provable privacy guarantee without making assumptions about the adversary’s prior knowledge. How to improve the effectiveness and efficiency of mining while satisfying differential privacy is the major challenge for differentially private frequent pattern mining. In this project, we plan to study the differentially private frequent pattern mining problem for three main types of patterns, i.e., itemset, sequence and subgraph. In particular, we plan to study the following problems: 1) differentially private frequent itemset mining based on depth-first search; 2) differentially private frequent sequence mining with gap constraints; 3) differentially private frequent subgraph mining based on Laplace mechanism. Our research findings will build a solid foundation for the usage of differentially private frequent pattern mining in real-world applications and further studies.

频繁模式挖掘是数据挖据领域最重要的基础性问题之一，具有广泛的应用。然而，如果数据集涉及个人敏感信息，直接发布或分享挖掘得到的频繁模式可能会导致严重的个人隐私泄露问题。近年来提出的差分隐私技术为解决上述问题提供了一种可行的方案。与传统的基于匿名的隐私保护模型不同，差分隐私提供了一种可证明的隐私保证，并且不依赖于攻击者所具有的背景知识。如何在满足差分隐私的条件下，提高挖掘结果的效用和挖掘效率是满足差分隐私的频繁模式挖掘面临的主要挑战。本项目拟针对项集、序列和子图三类主要模式，开展满足差分隐私的频繁模式挖掘研究。具体拟研究：1）满足差分隐私的基于深度优先搜索的频繁项集挖掘方法；2）满足差分隐私的带有间隙约束的频繁序列挖掘方法；3）满足差分隐私的基于拉普拉斯机制的频繁子图挖掘方法。研究成果将为满足差分隐私的频繁模式挖掘在实际领域中的应用以及满足差分隐私的频繁模式挖掘问题的进一步研究奠定坚实基础。

频繁模式挖掘是数据挖据领域最重要的基础性问题之一，具有广泛的应用。然而，如果数据集涉及个人敏感信息（例如，医疗记录、用户行为等），直接发布或分享挖掘得到的频繁模式可能会导致严重的个人隐私泄露问题。近年来提出的差分隐私技术为解决上述问题提供了一种可行的方案。与传统的基于匿名的隐私保护技术不同，差分隐私提供了一种严格、可量化的隐私保护手段，并且所提供的隐私保护强度几乎不依赖于攻击者所掌握的背景知识。通过对相关工作的深入分析，我们发现现有方法在挖掘结果的效用和挖掘效率等方面仍不能满足实际应用需求。因此，本项目对满足差分隐私的频繁模式挖掘问题开展了系统、深入的研究，并提出了一系列的满足差分隐私的频繁模式挖掘新方法。特别地，针对满足差分隐私的频项集挖掘问题，我们首次提出一种基于深度优先搜索的满足差分隐私的频繁项集挖掘方法；针对满足差分隐私的频繁序列挖掘问题，我们首次提出一种支持非连续频繁序列挖掘的满足差分隐私的频繁序列挖掘方法；针对满足差分隐私的频繁子图挖掘问题，我们首次提出一种两阶段的满足差分隐私的频繁子图挖掘方法。实验结果表明，与现有方法相比，本项目所提出的方法能够在相同的隐私保护强度下获得更好的性能。本项目的研究成果完善了满足差分隐私的频繁模式挖掘的理论体系，为满足差分隐私的频繁模式挖掘提供了新思路和新方法，进而推动了频繁模式挖掘在涉及个人敏感信息的数据挖掘任务中的应用。