一種無傳播誤差的差分隱私頻繁項集挖掘算法

廖 勇, 馮 山

(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

一種無傳播誤差的差分隱私頻繁項集挖掘算法

廖 勇, 馮 山*

(四川師范大學 數學與軟件科學學院, 四川 成都 610066)

差分隱私保護具有背景知識無關性,在隱私數據挖掘中可以抵御任意形式的攻擊.基于干擾的差分隱私保護算法SmartTrunc存在如下問題:1) 傳播誤差導致挖掘結果的可用性降低;2) 全局敏感度大導致擾動所需噪聲量預期值較大.為此,DFDP算法通過真實頻繁k項集而不是擾動后的頻繁k項集生成候選k+1項集,以徹底消除傳播誤差.同時,它通過一種新的函數映射將全局敏感度降為1,以減少干擾所需添加的噪聲量.理論分析與實驗結果均表明,DFDP算法能有效提升挖掘結果的可用性,同時所需添加的噪聲量更少.

頻繁項集; 隱私保護; 差分隱私; 拉普拉斯擾動; 傳播誤差

頻繁項集挖掘是數據挖掘研究領域的一個重要研究分支,是關聯規則挖掘的基礎.當事務數據集含有敏感數據時,直接發布頻繁項集及其真實支持度計數可能泄露用戶的隱私信息.因此,需對頻繁項集挖掘進行必要的隱私保護.傳統的隱私保護模型一般需特殊的攻擊假設,并隨新型攻擊的出現而不斷改進完善,不能提供及時、有效的安全保障,如K-匿名模型[1]不能抵御鏈接攻擊[2],其安全性與攻擊者掌握了多少背景知識相關,且不能嚴格證明和定量分析其隱私保護水平.背景知識是指除隱私保護對象外的所有其他與隱私保護模型相關的信息,如其他數據對象的信息、隱私保護模型和實現算法等.

為此,近年來研究人員試圖尋找與背景知識無關的隱私保護模型以抵御任意形式的攻擊;差分隱私保護模型[3]就在這一背景下產生.其攻擊模型為:最壞情況下,攻擊者已獲得除隱私保護對象外的所有背景知識,隱私保護對象的隱私信息仍能得到保護.差分隱私保護模型有嚴格的數學理論支撐,可嚴格證明和定量分析其隱私保護水平;一提出就被應用于隱私保護頻繁項集挖掘[4-8].

文獻[8]提出的SmartTrunc算法存在如下問題:1) 利用噪聲頻繁項集生成候選項集所產生的傳播誤差降低了挖掘結果的可用性,雙閾值法在一定程度上減少了傳播誤差,但并不能徹底消除;2) 一次性計算所有候選項集的真實支持度計數,導致全局敏感度較大,且與事務記錄長度相關;3) 截斷長事務記錄減小全局敏感度的量有限,且僅對短事務記錄比例較大的事務數據集性能較好,擴展性較差.為此,本文提出了一種無傳播誤差的差分隱私頻繁項集挖掘算法DFDP.DFDP無傳播誤差,全局敏感度更小,不需截斷長事務記錄,適用范圍更廣.

1 相關概念

性質 1(頻繁項集的先驗性質) 若項集X頻繁,其所有非空子集一定頻繁;否則,其所有超集一定非頻繁.

定義 1(傳播誤差) 在隱私算法中,由于算法本身的作用使得原本頻繁的項集X標記為非頻繁,而導致X的所有超集被非頻繁化的挖掘誤差稱為傳播誤差.

設事務數據集的集合D={Di|1≤i≤+∞},其中,Di(1≤i≤+∞)是具有相同屬性結構的事務數據集,|Di|表示Di中事務記錄總數.Rd={R1,R2,R3,…}是d維實數向量空間,其中Ri=〈ri1,ri2,…,rid〉是d維實數向量.

定義 2(相鄰數據集) 對任意D1,D2∈D,滿足D1?D2或D2?D1,D1與D2不同事務記錄的條數記為|D1ΔD2|.|D1ΔD2|=1時,D1、D2稱為相鄰數據集.

設M為一隨機算法,D1、D2為D中任意相鄰數據集.M(D1)和M(D2)分別表示M在D1和D2上所有可能輸出結果的范圍.在函數映射fM:D→Range(M)中,Range(M)表示M在D上所有可能輸出結果的范圍.

定義 3[3](差分隱私) 對D中任意相鄰數據集D1、D2及任意z∈Range(M),若M滿足(1)和(2)式,則M滿足s-差分隱私.

(1)

(2)

其中,s為隱私保護預算,Pr[M(D1)=z]和Pr[M(D2)=z]分別是M(D1)=z和M(D2)=z的概率.

對差分隱私而言,s越大,滿足(1)和(2)式越容易.理論上,可取到合適的s來保證在D1中添加或刪除一條事務記錄時,M在D1及其相鄰數據集D2上輸出同一結果的概率無明顯變化.

噪聲擾動是差分隱私中的常用技術.它通過向查詢或統計結果添加噪聲來保護隱私,但噪聲過多會降低結果的可用性,過少又沒有足夠的安全保障.為了更準確地確定需添加的噪聲量,差分隱私用全局敏感度和隱私保護預算共同決定噪聲量的大小.

定義 4[3](全局敏感度) 設函數Q:D→Rd,D1、D2為D中任意相鄰數據集,則Q(D1)與Q(D2)之間的差異值稱為Q在相鄰數據集D1和D2上的敏感度.相應地,D中所有相鄰數據集中的最大差異值稱為Q在D上的全局敏感度,記為

(3)

其中,‖Q(D1)-Q(D2)‖1是Q(D1)與Q(D2)之間的1-階范數距離,ΔQ由Q本身定義的映射關系決定,與D無關.

拉普拉斯擾動是差分隱私中常用的擾動方法.拉普拉斯概率密度函數[9]

μ是位置,b(b>0)是尺度.μ=0時的概率密度函數記為p(x),對應的分布記為Lap(b).顯然p(x)>0,圖像關于x=0對稱,越靠近x=0點函數值越大(圖1).故用Lap(b)擾動時,越靠近0的值的取值概率越大.

定理 1[10](拉普拉斯擾動原理) 設函數Q:D→Rd的全局敏感度為ΔQ.隱私保護預算為s,隨機變量Yi(1≤i≤d)相互獨立且服從Lap(ΔQ/s)分布.對任意Dj(Dj∈D),若隨機算法M滿足(4)式,則M滿足s-差分隱私.

(4)

對Lap(ΔQ/s),由圖1知,ΔQ越大,p(x)的圖像越扁平,添加的噪聲預期值越大.同理,s越大,添加的噪聲預期值越小;即噪聲量的大小與ΔQ成正比,與s成反比.

性質2表明,M較復雜時,只要M涉及隱私的子序列均滿足差分隱私,M就滿足差分隱私.

2 SmartTrunc算法

SmartTrunc[8]和Apriori[12]都利用性質1迭代生成頻繁項集,其不同在于生成候選k+1項集時,前者利用噪聲頻繁k項集,后者利用真實頻繁k項集.若真實頻繁k項集X在SmartTrunc中標記為非頻繁,由性質1,X的所有超集也非頻繁.故SmartTrunc存在傳播誤差,這降低了挖掘結果的可用性.為此,文獻[8]引入雙閾值法以在一定程度上減少傳播誤差,其中生成候選項集的閾值小于生成頻繁項集的閾值;但雙閾值法并不能徹底消除傳播誤差.

例如,D1是某文具店的部分購物事務記錄(表1),其生成候選項集的閾值和生成頻繁項集的閾值分別為2和3.D1的真實頻繁項集如表2所示.在SmartTrunc下,頻繁k項集X的真實支持度計數的擾動結果是隨機的,則X的噪聲支持度計數<2時,將不會用于生成候選k+1項集,直接導致X的所有超集非頻繁.如表2中{A}的噪聲支持度計數<2時(如1.7),{A}就不會用于生成候選2項集,直接導致真實頻繁項集{AB}非頻繁.故傳播誤差仍存在.

表 1 數據集D1

表 2 D1的真實頻繁項集

3 DFDP算法

對D中的事務數據集D1,設最小支持度計數閾值為min_count,隱私保護預算為s,Ck為候選k項集集合,Lk為真實頻繁k項集集合,Yk為噪聲頻繁k項集集合,|Ck|為Ck中項集總數.

3.1 基本思想與計算過程

3.1.2 計算過程 1) 掃描D1得到C1;2) 由C1生成L1;3) 用Lap(1/s)擾動C1中項集的真實支持度計數;4) 據C1及噪聲支持度計數生成滿足min_count的Y1;5) 用L1生成C2;6) 用C2成L2;7) 用Lap(1/s)擾動C2中項集的真實支持度計數,據C2及噪聲支持度計數生成滿足min_count的Y2,然后用L2生成C3,再用C3生成L3;8) 重復7),Lk=?時結束;9) 輸出Y=∪kYk.

3.1.3 DFDP算法 DFDP的簡要描述如下:

輸入:事務數據集D1,最小支持度計數閾值min_count,隱私保護預算s

輸出:D1的噪聲頻繁項集集合Y

C1=candidate_1_itemsets(D1);//D1→C1

for ?t∈D1{//掃描D1進行計數

Ct1=subset(C1,t);//t的1項子集

for ?c∈Ct1{c.count++;}

}

L1={c∈C1|c.count≥min_count};

for ?c∈C1{c.count=c.count+Lap(1/s);}

Y1={c∈C1|c.count≥min_count};

for (k=2;Lk-1≠?;k++){

Ck=gen_candt(Lk-1);//Lk-1生成Ck

for ?t∈D1{

Ctk=subset(Ck,t);//t的k項子集

for ?c∈Ctk{c.count++;}

}

Lk={c∈Ck|c.count≥min_count};

if (Lk≠?){

for?c∈Ck{c.count=c.count+Lap(1/s);}

Yk={c∈Ck|c.count≥min_count};

}

}

returnY=∪kYk;//輸出噪聲頻繁項集

3.2 隱私分析 設D1為D中的事務數據集,D1的所有候選集的集合記為∪kCk,|∪kCk|是∪kCk中項集總數.項集Xi∈∪kCk(1≤i≤|∪kCk|)對應的真實支持度計數查詢函數為Qi,ΔQi=1(1≤i≤|∪kCk|).對D1中的項集Xi的真實支持度計數添加Lap(1/s)噪聲的算法記為Mi,即

Yi(1≤i≤|∪kCk|)是服從Lap(1/s)分布的隨機變量,則Mi滿足s-差分隱私.對D中任意相鄰數據集D1、D2,Qi(D1)和Qi(D2)分別是Xi在D1和D2中的真實支持度計數,Range(Mi)是Xi在D上所有可能的噪聲支持度計數的集合.

證明Mi滿足s-差分隱私的證明如下.

對D中任意相鄰數據集D1、D2及Xi的任意噪聲支持度計數z∈Range(Mi)有

Yi為z-Qi(D1)和z-Qi(D2)的概率比值就是其概率密度函數值之比,故

因p(x)=1/(2b)×exp(-|x|/b),b=1/s,故

由不等式|a|-|b|≤|a-b|有

又因

則

故

因此

成立.

同理,因

因此

成立.

綜上所述,由定義3,Mi滿足s-差分隱私.

因對∪kCk中每個項集的真實支持度計數添加Lap(1/s)噪聲均滿足s-差分隱私,由性質2,DFDP滿足|∪kCk|×s-差分隱私.|∪kCk|無法預先確定,DFDP沒有給定總的隱私保護預算,而是為每次添加噪聲的操作分配等額的隱私保護預算s.由(1)和(2)式知,只要s大小合適,DFDP仍具有很好的隱私性.

3.3 實例 數據集D1如表1所示,最小支持度計數閾值設為3,其真實頻繁項集如表2所示.在DFDP下,擾動后的候選項集如表3所示,噪聲頻繁項集如表4所示.

表 3 DFDP擾動后的候選項集

結合算法1,對比表2和表4可知,表2中真實頻繁項集{A}在DFDP中沒有挖掘出來,是由差分隱私算法本身的噪聲擾動特性引起的,而不是由傳播誤差引起的.由L1生成C2時,C2={{AB},{BC},{AC}},因{AB}和{BC}的噪聲支持度計數大于最低閾值,它們是頻繁的,而{AC}擾動后依然非頻繁.在DFDP下,{A}的非頻繁并沒有導致真實頻繁項集{AB}的頻繁性失真.由性質1,用Yk生成Ck+1會導致傳播誤差.故在SmartTrunc下,用表4中的Y1生成C2時,因Y1不包含{A}而直接導致{AB}非頻繁.顯然,它偏離了DFDP的挖掘結果(表4),故SmartTrunc結果的可用性低于DFDP.

表 4 DFDP的噪聲頻繁項集

4 誤差分析與實驗結果

4.1 誤差分析 由拉普拉斯擾動原理,ΔQ較小時添加的噪聲預期值也較小.隱私保護預算s減小時Lap(1/s)的密度曲線更扁平,添加的噪聲預期值更大,隱私保護級別更高.為了更準確地評估和分析誤差,本文用平均絕對誤差(δMAE)衡量隱私保護預算s對支持度計數的影響,用F-score衡量噪聲頻繁項集的可用性.

(5)

從統計意義上講,δMAE越小,隱私算法挖掘結果的支持度計數誤差越小.

定義 6[13](F-score) 設Up為差分隱私下的噪聲頻繁項集集合,Uc為真實頻繁項集集合.Up∩Uc是Up和Uc的交集,|Up|、|Uc|和|Up∩Uc|分別是Up、Uc和Up∩Uc中項集的個數,則

(6)

顯然,F-score越大,Up和Uc的交集越大,即差分隱私下的噪聲頻繁項集的可用性越高.

4.2 實驗結果 通過仿真實驗結果來比較DFDP和SmartTrunc挖掘結果的誤差和可用性.實驗代碼用C語言完成,環境為Inter(R) Core(TM) i5-2400 CPU@3.10 GHz,2 GB內存,Windows 7.所用數據是某超市某月的部分銷售數據(http://www.datatang.com/data/44163),包括300條事務記錄和50種商品,平均每條事務記錄包含3種商品,且短事務記錄居多.

2個算法中Lap(1/s)取值均限制為[-10,10],生成頻繁項集的閾值均設為4.SmartTrunc生成候選項集的閾值設為2,并截斷商品多余7種的事務記錄.隱私保護預算s將從0.2漸變到1,每個s值重復試驗5次并取其平均值作為最終結果(保留3位小數).實驗結果的δMAE和F-score及其對比分別如圖2和圖3所示.

由圖2可知,隱私保護預算s越大，δMAE越小；即隱私算法挖掘結果的支持度計數誤差越小.DFDP中的δMAE明顯小于SmartTrunc中的δMAE,即DFDP結果的支持度計數誤差小于SmartTrunc,這與理論分析相符.

由圖3可知,隱私保護預算s越大,F-score越大,即隱私算法挖掘結果的噪聲頻繁項集的可用性越高.DFDP中的F-score明顯大于SmartTrunc中的F-score,即DFDP結果的可用性高于SmartTrunc,同樣與理論分析相符.

5 結束語

本文針對SmartTrunc算法存在的不足,提出了一種改進的DFDP算法.DFDP無傳播誤差,全局敏感度更小,不需截斷長事務記錄,適用范圍更廣.理論分析與實驗結果均表明,改進的DFDP減小全局敏感度和提升可用性的方法是有效的,但DFDP所基于的候選項集可能很大.在確保算法優勢的前提下,如何縮減候選項集以提升DFDP的時空效率有待進一步深入研究.

[1] SWEENEY L.k-anonymity:a model for protecting privacy[J]. International J Uncertainty Fuzziness and Knowledge based Systems,2002,10(5):557-570.

[2] 譚瑛. 數據挖掘中匿名化隱私保護研究發展[J]. 科技導報,2013(1):75-79.

[3] DWORK C. Differential privacy[C]//Proceedings of the 33rd International Colloquium on Automata Languages and Programming (ICALP06). Berlin:Springer,2006:1-12.

[4] BHASKAR R, LAXMAN S, SIMTH A, et al. Discovering frequent patterns in sensitive data[C]//Proceedings of the ACM SIGKDD International Conference on Knowledge Discovery Data Mining,2010:503-512.

[5] LI N, QARDAJI W, SU D, et al. Privbasis:frequent itemset mining with differential privacy[C]//Proceedings of the 38th Conference of Very Large Database,2012:1340-1351.

[6] 張嘯劍,王淼,孟小峰. 差分隱私下一種精確挖掘top-k頻繁模式方法[J]. 計算機研究與發展,2014,51(1):104-114.

[7] CHEN R, MOHAMMED N, FUNG B C M, et al. Publishing set-valued data via differential privacy [C]//Proceedings of the 37th Conference of Very Large Databases,2011:1087-1098.

[8] ZENG C, NAUGHTON J, CAI J Y. On differential private frequent itemsets mining[J]. Proceedings of the PVLDB Endowment,2012,6(1):25-36.

[9] 方開泰,許建論. 統計分析[M]. 北京:科學出版社,1987.

[10] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//Proceedings of the 3rd Conference on Theory of Cryptography Conference(TCC06). Berlin:Springer-Verlag,2006:265-284.

[11] MCSHERRY F. Privacy integrated queries:An extensible platform for privacy-preserving data analysis[C]//Proceedings of the ACM SIGMOD International Conference on Management of data (SIGMOD),2009:19-30

[12] AGRAWAL R, SRIKANT R. Fast algorithms for mining association rules[C]//Proceedings of the 1994 International Conference on Very Large Data Bases (VLDB’94),1994:487-499.

[13] MONREALE A, PEDRESCHI D, PENSA R G, et al. Anonymity preserving sequential pattern mining[J]. Artificial Intelligence and Law,2014,22(2):141-173.

(編輯 余 毅)

An Algorithm for Mining Frequent Itemset Based on Differential Privacy Without Propagation Error

LIAO Yong, FENG Shan

(CollegeofMathematicsandSoftwareScience,SichuanNormalUniversity,Chengdu610066,Sichuan)

Protection based on differential privacy method has nothing to do with the background knowledge related about the protection model and can be used to resist arbitrary form of attacks in data mining. For algorithm SmartTrunc based on idea of differential privacy protection with interference, its disadvantages are as following: The 1st is that usability of mining results will be reduced for the reason of propagation error. The 2nd is that global sensitivity will be increased very large and it will lead great expectation value used in noise disturbing. In order to eliminate the propagation error thoroughly, a new algorithm DFDP utilizes true frequentk-itemsets to generate candidatek+1-itemsets but not disturbed frequentk-itemsets like SmartTrunc. Meanwhile, to decrease the noise amount needed in interfering, a new mapping function is used to decrease the global sensitivity to 1. Theoretical analysis and experimental results show that the usability of the mining result can be effectively improved and the noise amount needed to assure the data mining protection can be obviously smaller with the algorithm DFDP.

frequent itemset; privacy preserving; differential privacy; Laplace disturbance; propagation error

2016-04-10

四川省教育廳自然科學重點基金(15ZB0029)

TP311

A

1001-8395(2017)01-0127-06

10.3969/j.issn.1001-8395.2017.01.021

*通信作者簡介:馮 山(1967—),男,教授,主要從事智能軟件平臺開發和數據挖掘的研究,E-mail:fengshanrq@sohu.com