王广艺，杨 庚

（1.南京邮电大学计算机学院、软件学院、网络空间安全学院；2.江苏省大数据安全与智能处理重点实验室，江苏南京 210023）

0 引言

频率估计是数据挖掘领域研究的一个基本问题，旨在计算特定数据项出现的频率，有助于云服务运营商了解客户端软件最新统计数据，检测恶意软件行为，也可应用于频繁出现的数据项（heavy hitter）查询、用户行为预测等。然而，如果直接采集用户信息，可能存在严重的隐私泄露隐患，攻击者可通过链接攻击、前景知识攻击等方式推测用户持有的数据项，不可信的第三方数据收集者也可能意外泄露用户敏感信息。如何高效地兼顾隐私保护与频率估计准确性是数据挖掘领域亟需解决的问题。

差分隐私（Differential Privacy，DP）［1］是一种基于数据扰动的隐私保护方法，具有严格的数学定义，可对隐私保护程度进行量化分析；同时，差分隐私无需考虑特殊的攻击假设，攻击者无法根据不同的输出判断记录是否在原数据集中。差分隐私分为中心差分隐私（Central Differential Privacy，CDP）和本地差分隐私（Local Differential Privacy，LDP）［2-4］，因而针对频率估计问题的差分隐私算法包括CDP 频率估计算法和LDP 频率估计算法。

在传统CDP 频率估计中，数据管理员向数据库添加随机化噪声，发布查询结果。CDP 频率估计可与机器学习算法深度融合，如频繁项集挖掘、频繁序列挖掘、频繁子图挖掘等［5］。但是，由于数据存储系统安全性、用户对数据管理员的信任度等因素限制，CDP 频率估计在实际应用中存在较大局限。

为了应对CDP 频率估计存在的问题，Kasiviswanathan等［3］于2011 年正式提出LDP。……