一种基于差分隐私保护的数据挖据频繁项集算法

武警工程大学 林焕楠 李庆鹏 耿新元

一种基于差分隐私保护的数据挖据频繁项集算法

武警工程大学 林焕楠 李庆鹏 耿新元

差分隐私定义了一种比较严格和强健的隐私保护模型，通过添加噪音使数据失真达到隐私保护的目的。本文提出一种基于差分隐私的频繁项集挖掘方法DPFM，该算法的挖掘策略结合Laplace机制，能够在保证计算性能的前提下实现差分隐私保护。通过实验表明，本文提出的DPFM算法在误差和拒真率以及两种指标的收敛速度上都优于TF方法。

spark；Apriori

0.引言

频繁模式挖掘是数据挖掘研究中的一个重要课题，其目的是找出频繁出现在数据集中的模式，是关联规则、相关性分析、分类、聚类和其他数据挖掘任务的基础，也是数据分析的主要技术之一[1]。作为最简单的FPM类型，频繁项集挖掘最初应用于事物数据库中关联规则的发现，同时也是其他模式挖掘的基础。Apriori和FP-growth算法是发现频繁项集的经典算法[2]。

Apriori算法是最具影响力的挖掘布尔关联规则频繁项集的算法，国内外学者做了大量卓有成效的研究工作。其中，文献[3]提出一种分组统计策略的Apriori并行算法，有效地减少了键/值对的产生，很大的提升了算法时间性能。文献[4]提出一种基于矩阵的并行关联规则算法Apriori_MMR，该算法结合了数据划分的思想进行并行化改进，简化了生成候选项的连接步骤，仅需对事务数据库扫描两次，同时在计算过程中还能对事务进行压缩从而进一步提高了算法的性能[5]。

本文提出一种基于差分隐私的频繁项集挖掘方法DPFM，该算法的挖掘策略结合Laplace机制和指数机制，能够在保证计算性能的前提下实现差分隐私保护。

1.差分隐私保护

差分隐私保护技术被公认为一种比较严格和强健的隐私保护模型，从本质上来说，它是一种借助数据扰动、加噪来保护数据敏感信息不被泄露的信息安全技术。

定义1 ε-差分隐私[6]（ε-differential privacy）对于给定的两个临近数据集D和D'，数据集间最多相差一条记录，给定一个隐私算法A，R为A的输出域，对任意子集，若算法A满足：

则称算法A提供ε-差分隐私保护，其中Pr[X]表示事件X发生的概率。

定义2 全局敏感度[7]设有函数，输入为一数据集D，输出为一d维实数向量。对于任意的邻近数据集D和D'，函数f的全局敏感度为：

2.DPFM算法设计

Step1.获取λ值，即支持度满足阈值θ的项的个数。

Step2.构建节点集F，F包含项集I中最频繁的λ项，即所有支持度满足阈值θ的频繁项，F将包含top-k项集中出现的所有频繁项。

Step3.基于F构建边集P，P由F中的所有长度为2且满足阈值θ的子集构成，即集合P将包含top-k项集中出现的所有频繁对。

Step4.基于F和P生成图G(F,P)，找出图G上的所有极大团M，构成θ-基集合B，每个极大团对应一个θ-基，最终找到一个宽度和长度都尽可能小的θ-基集。

Step5.由B构建候选集C(B)，计算C(B)中项集的支持度，并对支持度进行差分隐私处理，最终从中获得满足隐私约束top-k频繁项集的相关信息。

3.实验与分析

本文实验实施的硬件环境为：AMD Athlon Ⅱ X4 645 Processor 3.1GHz处理器，4GB内存。软件方面采用win7操作系统，使用Matlab实现和运行相关算法。

由于本文提出的DPFM算法在不同值的情况下有着不同的处理策略，本实验通过将本文提出的DPFM算法与TF方法置于三种具有代表性的数据集上进行测试，如表1所示：

表1　实验使用的真实数据集在确定

可以看出，随着隐私预算的增加，算法结果的拒真率和相对误差均呈现下降趋势，并在隐私预算取到0.6以上时逐渐趋于稳定，由于频繁项集的挖掘范围较小，两种算法在误差上的表现均比较优秀，综合来看，算法提供的结果的准确率较高，但本文提出的DPFM算法在误差和拒真率以及两种指标的收敛速度上都优于TF方法。

4.结束语

针对长事务数据上的挖掘效率与准确性较低等问题，提出了一种满足差分隐私约束的频繁项集挖掘算法DPFM，该算法从频繁项集挖掘的先验规则出发，结合极大团理论和-基映射技术，根据阈值将数据集中的大量事务压缩除冗，挖掘事务集合中保留有效信息的闭频繁项集来构建候选集，并结合Laplace机制对频繁项支持度隐私信息进行噪声扰动，实现了ε-差分隐私隐私处理，最终由候选集重构得到满足隐私安全策略的top-k频繁项集的支持度，由于算法有效的控制了候选集的规模，降低了添加的噪声量和所消耗的隐私预算，从而在保证数据隐私的前提下，提升了算法在挖掘top-k频繁项集时的性能和准确性。

[1]Ding Li ping,Lu Guoqing Survey of differential privacy in frequent pattern mining [J].Journal on Communication2014,35(10):200-209.

[2]Inokuchi A, Washio T, Motoda H.An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data[C].European Conference on Principles of Data Mining&Knowledge Discovery,2000:13-23.

[3]Huang Liqin, Liu Yanhuang,MapReduce based parallel Apriori algorithm improvement research[J].Journal of Fuzhou University (NATURAL SCIENCE EDITION),2011,39(5):34-39.

[4]Xie Zhiming, Wang Peng, a parallel matrix Apriori algorithm based on Reduce Map architecture[J].computer application research,34(1):17-21.

[5]Dwork C,Dwork C.The Differential Privacy Frontier[J]. Tcc, 2009:496--502.

[6]Xie Zhiming,Wang Peng, a parallel matrix Apriori algorithm based on Reduce Map architecture[J].computer application research,34(1):17-21.

[7]Wang Baoyi,Wang Dongyang,Zhang Shaomin. Short term distributed power load forecasting algorithm based on Spark and [J].IPPSO_ LSSVM electric power automation equipment,2016,36(1):117-122.