一種基于差分隱私保護的數據挖據頻繁項集算法

武警工程大學 林煥楠 李慶鵬 耿新元

一種基于差分隱私保護的數據挖據頻繁項集算法

武警工程大學 林煥楠 李慶鵬 耿新元

差分隱私定義了一種比較嚴格和強健的隱私保護模型，通過添加噪音使數據失真達到隱私保護的目的。本文提出一種基于差分隱私的頻繁項集挖掘方法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.