桂林电子科技大学|DP-PartFIM:基于差分隐私和分区技术的频繁项集挖掘算法(TETC 2024)

文摘   2024-09-25 08:30   上海  

在大数据时代背景下,频繁项集挖掘(FIM)技术被广泛应用于发现和提取大规模数据集中的有价值信息。然而,数据集中往往包含敏感的私人信息,直接挖掘或共享挖掘结果可能会引发隐私泄露的风险。因此,如何有效地保护数据隐私,同时又能从数据中挖掘出有价值的信息,成为了一个亟待解决的问题。差分隐私作为一种先进的隐私保护技术,通过引入噪声机制来保护个人信息,与传统隐私保护手段相比,它具有更高的安全标准和更强的防护能力,同时还能保持数据的可用性。在以往的研究中,基于差分隐私的频繁项集挖掘常采用长事务截断策略以降低算法的敏感度,但这可能会引入截断误差,影响隐私预算的有效利用。


针对这一问题,本文设计了一种基于差分隐私和分区技术的频繁项集挖掘算法——DP-PartFIM。该算法在保护数据隐私的同时,提高了挖掘效率和数据的可用性。DP-PartFIM算法的核心思想是将大数据集划分为多个小的数据分区,然后在每个分区上独立进行频繁项集的挖掘。通过这种方式,算法能够有效地控制数据表的大小,降低计算复杂度,图1展示了使用DP-PartFIM进行挖掘的示例。在挖掘过程中,算法采用了分层剪枝策略,减少了候选项集的数量,从而提高了挖掘效率。此外,算法在合并分区结果时,采用了平均预算策略对候选项集添加噪声,进一步增强了隐私保护。

图1 DP-PartFIM示例    


与传统的隐私保护方法相比,DP-PartFIM首次将分区技术应用于基于差分隐私的频繁项集挖掘算法中,通过合并分区结果来构建候选项集,避免了长事务造成的高敏感度,可以有效利用隐私预算。本文通过理论证明DP-PartFIM满足  -差分隐私。此外,扰乱数据的期望和方差为:  。实验结果表明,DP-PartFIM在多个真实数据集上均有更好的性能表现,不仅在数据的隐私保护方面表现出色,同时也保证了数据的实用性和挖掘结果的准确性。在 Connect 数据集上三个算法的平均相对误差(ARE)和 F-Score 分别如图2和图3所示。

图2 Connect数据集的ARE

图3 Connect数据集的F-Score


DP-PartFIM算法的提出,为隐私保护下的数据挖掘提供了一种新的解决方案。它不仅提高了数据挖掘的效率,同时也有效地保护了数据隐私,对于促进数据挖掘技术的发展和应用具有重要意义。


论文信息


相关论文已被期刊 IEEE Transactions on Emerging Topics in Computing 录用,DOI: 10.1109/TETC.2024.3443060,作者为桂林电子科技大学硕士生刘鑫宇、博士生余乐乐、导师刘忆宁教授(通讯作者),以及暨南大学的甘文生副教授。


X. Liu, W. Gan, L. Yu and Y. Liu, "DP-PartFIM: Frequent Itemset Mining using Differential Privacy and Partition," in IEEE Transactions on Emerging Topics in Computing, doi: 10.1109/TETC.2024.3443060.(点击下方阅读原文查看论文全集)




供稿:刘鑫宇,刘忆宁


隐者联盟
本公众号主要推介多媒体、人工智能、信息安全等方面的最新研究进展,愿与同行携手,共同推动科学研究向前发展。
 最新文章