一種無傳播誤差的差分隱私頻繁項(xiàng)集挖掘算法

廖 勇, 馮 山

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

一種無傳播誤差的差分隱私頻繁項(xiàng)集挖掘算法

廖 勇, 馮 山*

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

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

頻繁項(xiàng)集; 隱私保護(hù); 差分隱私; 拉普拉斯擾動(dòng); 傳播誤差

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

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

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

1 相關(guān)概念

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

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

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

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

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

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

(1)

(2)

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

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

噪聲擾動(dòng)是差分隱私中的常用技術(shù).它通過向查詢或統(tǒng)計(jì)結(jié)果添加噪聲來保護(hù)隱私,但噪聲過多會(huì)降低結(jié)果的可用性,過少又沒有足夠的安全保障.為了更準(zhǔn)確地確定需添加的噪聲量,差分隱私用全局敏感度和隱私保護(hù)預(yù)算共同決定噪聲量的大小.

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

(3)

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

拉普拉斯擾動(dòng)是差分隱私中常用的擾動(dòng)方法.拉普拉斯概率密度函數(shù)[9]

μ是位置,b(b>0)是尺度.μ=0時(shí)的概率密度函數(shù)記為p(x),對應(yīng)的分布記為Lap(b).顯然p(x)>0,圖像關(guān)于x=0對稱,越靠近x=0點(diǎn)函數(shù)值越大(圖1).故用Lap(b)擾動(dòng)時(shí),越靠近0的值的取值概率越大.

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

(4)

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

性質(zhì)2表明,M較復(fù)雜時(shí),只要M涉及隱私的子序列均滿足差分隱私,M就滿足差分隱私.

2 SmartTrunc算法

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

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

表 1 數(shù)據(jù)集D1

表 2 D1的真實(shí)頻繁項(xiàng)集

3 DFDP算法

對D中的事務(wù)數(shù)據(jù)集D1,設(shè)最小支持度計(jì)數(shù)閾值為min_count,隱私保護(hù)預(yù)算為s,Ck為候選k項(xiàng)集集合,Lk為真實(shí)頻繁k項(xiàng)集集合,Yk為噪聲頻繁k項(xiàng)集集合,|Ck|為Ck中項(xiàng)集總數(shù).

3.1 基本思想與計(jì)算過程

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

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

輸入:事務(wù)數(shù)據(jù)集D1,最小支持度計(jì)數(shù)閾值min_count,隱私保護(hù)預(yù)算s

輸出:D1的噪聲頻繁項(xiàng)集集合Y

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

for ?t∈D1{//掃描D1進(jìn)行計(jì)數(shù)

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

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項(xiàng)子集

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;//輸出噪聲頻繁項(xiàng)集

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

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

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

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

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

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

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

又因

則

故

因此

成立.

同理,因

因此

成立.

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

因?qū)Α萲Ck中每個(gè)項(xiàng)集的真實(shí)支持度計(jì)數(shù)添加Lap(1/s)噪聲均滿足s-差分隱私,由性質(zhì)2,DFDP滿足|∪kCk|×s-差分隱私.|∪kCk|無法預(yù)先確定,DFDP沒有給定總的隱私保護(hù)預(yù)算,而是為每次添加噪聲的操作分配等額的隱私保護(hù)預(yù)算s.由(1)和(2)式知,只要s大小合適,DFDP仍具有很好的隱私性.

3.3 實(shí)例 數(shù)據(jù)集D1如表1所示,最小支持度計(jì)數(shù)閾值設(shè)為3,其真實(shí)頻繁項(xiàng)集如表2所示.在DFDP下,擾動(dòng)后的候選項(xiàng)集如表3所示,噪聲頻繁項(xiàng)集如表4所示.

表 3 DFDP擾動(dòng)后的候選項(xiàng)集

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

表 4 DFDP的噪聲頻繁項(xiàng)集

4 誤差分析與實(shí)驗(yàn)結(jié)果

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

(5)

從統(tǒng)計(jì)意義上講,δMAE越小,隱私算法挖掘結(jié)果的支持度計(jì)數(shù)誤差越小.

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

(6)

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

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

2個(gè)算法中Lap(1/s)取值均限制為[-10,10],生成頻繁項(xiàng)集的閾值均設(shè)為4.SmartTrunc生成候選項(xiàng)集的閾值設(shè)為2,并截?cái)嗌唐范嘤?種的事務(wù)記錄.隱私保護(hù)預(yù)算s將從0.2漸變到1,每個(gè)s值重復(fù)試驗(yàn)5次并取其平均值作為最終結(jié)果(保留3位小數(shù)).實(shí)驗(yàn)結(jié)果的δMAE和F-score及其對比分別如圖2和圖3所示.

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

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

5 結(jié)束語

本文針對SmartTrunc算法存在的不足,提出了一種改進(jìn)的DFDP算法.DFDP無傳播誤差,全局敏感度更小,不需截?cái)嚅L事務(wù)記錄,適用范圍更廣.理論分析與實(shí)驗(yàn)結(jié)果均表明,改進(jìn)的DFDP減小全局敏感度和提升可用性的方法是有效的,但DFDP所基于的候選項(xiàng)集可能很大.在確保算法優(yōu)勢的前提下,如何縮減候選項(xiàng)集以提升DFDP的時(shí)空效率有待進(jìn)一步深入研究.

[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] 譚瑛. 數(shù)據(jù)挖掘中匿名化隱私保護(hù)研究發(fā)展[J]. 科技導(dǎo)報(bào),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]. 計(jì)算機(jī)研究與發(fā)展,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] 方開泰,許建論. 統(tǒng)計(jì)分析[M]. 北京:科學(xué)出版社,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

四川省教育廳自然科學(xué)重點(diǎn)基金(15ZB0029)

TP311

A

1001-8395(2017)01-0127-06

10.3969/j.issn.1001-8395.2017.01.021

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