论文部分内容阅读
随着大数据时代的到来,数据挖掘技术已经成为研究人员从数据中提取有用知识的重要工具。频繁模式挖掘是数据挖掘领域中的一个重要课题,用于得到事物之间的关联特性。频繁子图挖掘是频繁模式挖掘的一种具体形式,它从图数据集合中获得频繁子图结构,在图数据的分析中具有重要的意义。然而,如果这些子图中涉及敏感信息,直接发布或分享这些频繁子图就有可能造成个体用户信息的泄露。为了解决上述问题,本文提出了一种满足差分隐私的频繁子图挖掘算法DFG (Differential Private Frequent sub Graph mining algorithm)。DFG使用了一种两阶段算法的模型。第一阶段为频繁子图选择阶段,DFG算法在这一阶段中按照逐渐增大子图边数的方式挖掘频繁子图,并使用了二分估值算法和条件指数机制降低挖掘过程中所引入的噪音量;第二阶段为噪音支持度计算阶段,DFG算法在这一阶段中对频繁子图建立网格结构,并利用基于噪音量反馈的多路径建立算法得到覆盖网格的路径集合,最后通过计数累加算法和噪音合成规则得到每条路径中频繁子图的噪音支持度。理论分析表明DFG算法满足ε-差分隐私保护;后续的对比实验结果表明DFG算法的数据效用和运行效率均优于现有的满足差分隐私的频繁子图挖掘算法。本文还说明了 DFG算法可以被扩展到频繁模式挖掘中,并根据频繁项集挖掘的特点对网格结构进行优化,提出了 DFISL(Differential Frequent Itemset mining algorithm based on Sub Lattice)算法。实验分析表明DFISL算法的数据效用比现有的PFP-growth算法和DiffFPM算法更高。