基于差分隱私的高效用項目集挖掘算法

馬 煜,荀亞玲

(太原科技大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院,太原 030024)

隨著社會各領(lǐng)域數(shù)據(jù)的快速增長,用戶面臨著如何從數(shù)據(jù)海洋中挖掘出有價值信息的挑戰(zhàn)。關(guān)聯(lián)規(guī)則是數(shù)據(jù)分析知識的重要結(jié)構(gòu)[1],通過在數(shù)據(jù)對象之間建立連接和關(guān)聯(lián)來獲取重要知識。傳統(tǒng)的關(guān)聯(lián)規(guī)則挖掘(ARM)傾向于關(guān)注該商品是否出現(xiàn)在用戶的購買歷史中,以及同時出現(xiàn)在該商品購買歷史中的其他商品,這樣商家更容易鏈接到利潤。因此,高效用項目集挖掘(HUIM)[2]被提出,它不僅考慮要求信息的項目數(shù)量,還考慮效用價值,因此與傳統(tǒng)ARM相比更具有決策價值。同時,一些不法分子可以從中提取出一些與利益相關(guān)的競爭信息,從而損害數(shù)據(jù)所有者的利益。因此,隱私保護(hù)效用挖掘(PPUM)已成為高效用項目集挖掘中的一個重要研究課題。

傳統(tǒng)的隱私保護(hù)方式有同態(tài)加密過程[3]、k-anonymity[4]和l-diversity[5].它們都可以在一定程度上保護(hù)數(shù)據(jù)不被泄露。但是在同態(tài)加密中,其加密和解密的過程需要消耗大量的計算資源,同時該方案受到每個密文都有噪聲的限制,甚至使得密文變得十分困難;k-anonymity可以防止身份信息泄露,卻不能防止屬性泄露;當(dāng)用戶在元數(shù)據(jù)中有多個記錄時l-diversity隱私原則無法防止隱私泄漏,敏感屬性的性質(zhì)決定了即使保證了一定概率的diversity也容易泄露隱私。而差分隱私[6]通過使用拉普拉斯機(jī)制和指數(shù)機(jī)制添加噪聲,可減少個人信息泄露的風(fēng)險,數(shù)據(jù)的可用性得到了很大的保證,在隱私和可用性之間取得了平衡。且差分隱私保護(hù)所添加的噪聲量與數(shù)據(jù)集的大小無關(guān),因此,在大規(guī)模數(shù)據(jù)集的情況下,即使只添加少量的噪聲,也可以實(shí)現(xiàn)較好的隱私保護(hù)。

本文結(jié)合差分隱私保護(hù)提出一種高效用項目集挖掘算法,主要貢獻(xiàn)如下:

給出一個樹結(jié)構(gòu)DPUP-tree(based on Differen tial Privacy Utility Pattern Tree)來維護(hù)事務(wù)交易 項目及其效用信息,并提出了一種基于差分隱私的高效用項集挖掘算法DPUP-Growth(based on Differen tial Privacy Utility Pattern Growth).當(dāng)數(shù)據(jù)為數(shù)值型時,采用拉普拉斯機(jī)制;當(dāng)數(shù)據(jù)為序列型時,采用指數(shù)機(jī)制。實(shí)驗(yàn)結(jié)果表明,基于差分隱私的高效用項集方法可以有效保護(hù)高效用性項集的發(fā)布。

1 相關(guān)工作

1.1 基于高效用模式集挖掘

傳統(tǒng)關(guān)聯(lián)規(guī)則的挖掘方法只考慮項目集中項目出現(xiàn)的次數(shù),而項目集的利潤可能不同,Jerry Chun-Wei Lin等提出了一種依賴于緊湊的數(shù)據(jù)結(jié)構(gòu)HUI-DMiner[7],采用了一種存儲2項集之間關(guān)系的估計效用共現(xiàn)策略來提高計算速度。

由于找到合適的最小效用閾值對用戶比較困難,Tseng V S等提出了挖掘Top-K高效用項集的高效算法TKU和TKO[8],通過不設(shè)置最小效用閾值,能夠有效地生成候選項集,從而獲得所有高效用項目集。

Vincent S.Tseng等提出UP-Growth[9],使用效用模式的樹結(jié)構(gòu),用”模式增長”的方式挖掘。同時為了減少候選模式集的數(shù)量,該算法提出幾種剪枝策略,以達(dá)到提高算法性能的目的。

王晨等人提出了基于效用模式樹的兩階段效用模式挖掘UPTP算法[10],通過刪除全局的非候選模式集和降低全局的各個節(jié)點(diǎn)的效用值,生成全局的條件效用模式樹,進(jìn)而生成高效用項集。

Krishnamoorthy等提出了HUP-Miner算法[11],HU P-Miner是一種關(guān)于垂直結(jié)構(gòu)的算法,其引入了兩個新的剪枝策略,被稱為劃分效用剪枝和前向效用剪枝。

黃坤等人提出一個新的基于差集的高效用項集挖掘方法D-HUI算法[12],其引入數(shù)據(jù)結(jié)構(gòu)—項集列表,項集列表只需要存儲事務(wù)和效用信息。

1.2 基于隱私保護(hù)的高效用模式集挖掘

關(guān)于隱私保護(hù)效用挖掘(PPUM)的問題,引出了兩種新的算法HHUIF和MSICF[13]來隱藏敏感項集,使其他用戶不能從修改后的數(shù)據(jù)庫中挖掘項目集。

高效用項目集挖掘(HUIM)考慮數(shù)量和利潤因素來衡量一個項目或項目集是否有利可圖。隱私保護(hù)效用挖掘(PPUM)已經(jīng)成為HUIM的一個關(guān)鍵問題。對于隱藏敏感的高效用項集的問題,提出了一種新的算法,目的是減少挖掘過程中產(chǎn)生的副作用。

隱私政策是為阻止數(shù)據(jù)所有者共享挖掘數(shù)據(jù)。文獻(xiàn)為解決敏感效用的隱藏以及頻繁項集的問題,提出了MSMU和MCRSU兩種關(guān)于數(shù)據(jù)清理的算法[14],其把敏感效用和頻繁項集隱藏在修改后的數(shù)據(jù)庫中。該算法不僅能隱藏敏感項集,也能清理數(shù)據(jù)庫。

Chun-WeiLin提出了一種基于遺傳算法的隱私保護(hù)效用挖掘方法[15],其目的是找到合適的事務(wù)插入到數(shù)據(jù)庫中,從而隱藏敏感的高效用項目集。

如何以更小的副作用隱藏高效用挖掘結(jié)果中的敏感高效用項集,保證用戶在發(fā)布和共享數(shù)據(jù)時不會造成私密信息泄露。對此提出了基于競爭項分析的保護(hù)敏感項集算法[16],根據(jù)用戶指定保護(hù)項來分析出敏感項集。

在隱私保護(hù)的差分隱私背景下,挖掘結(jié)果的有效性已成為我們目前關(guān)注的一個重要問題。文獻(xiàn)[17]以頻繁挖掘模式(對象集、序列和子圖)考察了三個最重要的對象,深入的探討了滿足差分隱私的頻繁挖掘問題。

文獻(xiàn)[18]提出了一個有效的(k,l)-anonymity隱私原則,通過此原則隱私得到了有效地保護(hù)。在這個原則的基礎(chǔ)上,改進(jìn)之前的隱私算法并且提出了一個可以滿足這類型隱私原則的算法。

綜合上述分析,本文提出基于差分隱私的高效用項目集挖掘算法DPUP-Growth(based on Differenti al Privacy Utility Pattern Growth),數(shù)據(jù)擁有者使用差分隱私技術(shù)在數(shù)據(jù)發(fā)布的過程前對數(shù)據(jù)進(jìn)行隱私保護(hù),數(shù)據(jù)分析者在基于差分隱私上的樹結(jié)構(gòu)進(jìn)行高效用項目集挖掘,使得數(shù)據(jù)可以抵御任意形式的攻擊。

2 差分隱私的高效用模式樹

2.1 相關(guān)描述

給定一組有限的項I={i1,i2,…,im}.每個項目ip(1≤p≤m)有一個單位利潤p(ip).項集x是k個不一致項{i1,i2,…,ik}的組成的,其中ij∈I,1≤j≤k,k是x的長度.長度為k的項集稱為k項集。一個事務(wù)數(shù)據(jù)庫D={T1,T2,…,Tn}中包含一組事務(wù),其中每個事務(wù)Td(1≤d≤n)都有唯一的標(biāo)識符d,叫做TID.交易Td中的每個項目ip都和一個數(shù)量q(ip,Td)相互關(guān)聯(lián),即在Td中ip為購買的數(shù)量。差分隱私常用的兩種機(jī)制是:拉普拉斯機(jī)制和指數(shù)機(jī)制。一個數(shù)據(jù)集的實(shí)例如表1所示。表2表示了每一項對應(yīng)的外部權(quán)重即利潤。

表1 示例數(shù)據(jù)庫

表2 利潤表

定義1(項目效用) 在事務(wù)Td中,交易中一個項目的效用表示為u(ip,Td),定義為:

u(ip,Td)=p(ip)×q(ip,Td)

(1)

例如,表1中u(A,T1)=3×4=12

定義2(項目集X的效用) 事務(wù)Td中項目集X的效用表示為u(X,Td),定義為:

(2)

例如,表1中u(AC,T1)=3×4+4×1=16

定義3(事務(wù)效用) 事務(wù)Td的事務(wù)效用表示為tu(Tq),定義為:

(3)

例如,表1中u(AC)=16+18+8=42

定義4(數(shù)據(jù)庫總效用) 事務(wù)數(shù)據(jù)庫D的總效用就是所有事務(wù)效用的總和,定義為:

(4)

例如,表1中TU=16+18+8=42

定義5(事務(wù)加權(quán)利用率) 一個項目集的事務(wù)加權(quán)利用率表示為TWU(X),定義為:

(5)

例如,表4中TWU=16+34+34+25+29=138

定義6(剩余效用) 數(shù)據(jù)庫的總效用表示為時間單位,定義為:

(6)

例如,表4中TU(T3)=4×1+3×4+2×2+1×4+2×2=28

定義7(最小項目效用表) 事務(wù)Td中的事務(wù)最小效用值記作miut,以維護(hù)所有全局有希望項目的最小項目效用,定義為:

miut(Td)=Min({u(ip)|ip∈Td})

(7)

例如,表1中mitu(A)=Min(3×4,4×4,1×4)=4

定義8(最小效用閾值) 設(shè)?表示由用戶設(shè)定的百分值,那么最小效用閾值表示為Minutl,定義為Minutl=TU×β.

例如,用戶設(shè)定的K為10%,那么Minutl=138×10%=13.8

定義9(高效用項集) 給定項集P及用戶指定最小效用閾值Minutl,若TWU(P)≥Minutl,則稱項集P為高效用項集．如果若TWU(P)

定義10(Laplace機(jī)制) 給定數(shù)據(jù)集D,通過在查詢結(jié)果添加關(guān)于拉普拉斯的噪聲,那么隨機(jī)算法M(D)=f(D)+Y提供ε-差分隱私保護(hù),其中Y～Lap(Δf/ε)服從尺度參數(shù)為Δf/ε的Laplace分布,公式如下:

M(D)=f(D)+Y

(8)

定義11(指數(shù)機(jī)制) 設(shè)隨機(jī)算法M的輸入為數(shù)據(jù)集D,輸出的查詢函數(shù)范圍為R∈Range,q(D,R)為可用性函數(shù),函數(shù)q(D,r)的敏感度是Δq,若函數(shù)以正比于exp(εq(D,r)/2Δq)的概率從Range中選擇輸出r,那么算法提供ε-差分隱私保護(hù),公式如下:

(9)

2.2 算法描述及實(shí)例分析

DPUP-Growth(based on Differential Privacy Utility Pattern Growth)該方法的框架由三部分組成:(1)構(gòu)造DPUP-tree(based on Differential Pri vacy Utility PatternTree)結(jié)構(gòu),使用指數(shù)機(jī)制混淆項頭 表順序,建立樹的過程為每個節(jié)點(diǎn)添加拉普拉斯噪聲;(2)通過算法DPUP-Growth從生成的樹結(jié)構(gòu)DPUP-Tree獲得候選高效用模式集;(3)從候選高效用模式集中識別真正的高效用模式?；诓罘蛛[私的高效用項目集挖掘方法步驟如下:

第一步:首先對數(shù)據(jù)庫進(jìn)行第一次掃描,根據(jù)定義2、5和7計算事務(wù)效用tu、事務(wù)加權(quán)利用率TWU和最小效用表miut.如果一個項的TWU小于最小效用閾值,那它的超集不可能是高效用項集,丟棄且更新tu.

假設(shè)事務(wù)數(shù)據(jù)庫最小效用閾值為40,從表3可以得到,項目F的TWU為34,根據(jù)定義9可知TWU(F)≤40,那么它的超集不可能是高效用項集。這個項目被稱為沒有希望的項目。由于{F}是沒有希望的項目,則從事務(wù)T3中刪除沒有希望的項{F}.并且在T2、T3的TU消除了{(lán)F}效用。事務(wù)中剩余的有希望的項{A}、{B}、{C}、{D}、{E}和{G}按TWU的降序排序,如表4.

表3 項目及其TWUs

表4 數(shù)據(jù)庫,TU及新TU

表5 項目及其miut

第二步:使用指數(shù)機(jī)制對項頭表(HeadTable)順序進(jìn)行混淆。偽代碼如下:

算法1混淆順序,并創(chuàng)建項頭表

輸入:交易加權(quán)利用率TWU,最小效用閾值Minutl輸出:混淆項頭表1:for each item in twu_dict do2:twu_dict[item]≥minutility 3:end for4:for each item in twu.keys()5:expMechDict_sorted[item]=twu[item]6:end for7:for each item in expMechDict_sorted do8:table[item]=[expMechDict_sorted_values[item],None]9:end for

第三步:建立DPUP-tree,建立樹的過程為每個節(jié)點(diǎn)添加拉普拉斯噪聲(noise).偽代碼如下:

算法2添加拉普拉斯噪聲

輸入:節(jié)點(diǎn)值輸出:噪聲節(jié)點(diǎn)1:rnd=random.uniform(0.0,1.0)2:uniform=rnd-0.53:for each item4:noise=mu-lambd ? sign ? uniform ? math.log(1-2.0 ?math.fabs(uniform))5:laplacian_count=noise + count6:laplacian_count=round(laplacian_count)7:end for

考慮表4中重組的事務(wù).當(dāng)T1={(C,4)(A,3)(D,4)}被插入到DPUP-tree時,第一個節(jié)點(diǎn){C}被創(chuàng)建。{C}.nu的增加是通過T1的RTU減去T1中{C}項后面的剩余項的效用,即{C}.nu=RTU(T1)-(u({A},T1)+u({D},T1) =4.第二個節(jié)點(diǎn){A}是{C}子節(jié)點(diǎn)。計數(shù)=1和{A}.nu=(p({C})×q({C},T1)+p({A})×q({A},T1)=8.同理,第三個節(jié)點(diǎn){D}由{D}創(chuàng)建。當(dāng)T2={(C,2)(E,3)(A,4)(G,1)}插入到樹中的時候,{C}.nu增加p({C})×q({C},T2=2和{C}的計數(shù)增加到3.然后,在帶有{E}的節(jié)點(diǎn){C}下創(chuàng)建一個新節(jié)點(diǎn){E}.計數(shù)=3和{E}.nu=14.同樣,在節(jié)點(diǎn){E}下創(chuàng)建一個新節(jié)點(diǎn){A}的計數(shù)=4和{A}.nu=30.在插入所有重組的事務(wù)之后,DPUP-tree被完全構(gòu)建。如圖1所示樹結(jié)構(gòu)。

圖1 DPUP-tree結(jié)構(gòu)Fig.1 DPUP-tree structure

第四步:從樹中挖掘潛在高效用模式,構(gòu)造當(dāng)前節(jié)點(diǎn)的條件模式基,并對其進(jìn)行分析。如考慮{D}的條件模式基。

表6顯示了{(lán)D}-CPB中的本地項目及其路徑效用。在表6中,標(biāo)識了一個本地不太可能的項目{G}.在對{D}-CPB進(jìn)行第二次掃描時,本地不太可能的項目{G}將分別從路徑{B,E,G}中刪除。A的效用為16+28>40,G的效用為21<40.如果pu(ip,{ai}-CPB)≥Minutl,則項ip在{ai}-CPB中稱為局部希望項;否則,ip被稱為本地沒希望的項目。

表6 {D}-CPB

表7 重構(gòu)后的事務(wù)數(shù)據(jù)庫

第五步:根據(jù)重構(gòu)后的事務(wù)數(shù)據(jù)庫的事務(wù)項集,從候選高效用模式集中選擇真正的高效用模式。

從DPUP-tree生成高效用模式集,得到一組高效用項集,即:{EG}∶40、{CEG}∶43、{BDE}∶44、{CDE}∶43、{AE}∶44、{ACE}∶50、{BE}∶46、{E}∶48、{CE}∶56、{BCE}∶52、{BCDE}∶49

3 實(shí)驗(yàn)結(jié)果及分析

3.1 實(shí)驗(yàn)環(huán)境及數(shù)據(jù)集

為檢驗(yàn)DPUP-Growrh算法的性能,將其與將經(jīng)典的挖掘算法UP-Growrh[9]和現(xiàn)有算法D-HUI[12]進(jìn)行比較。

實(shí)驗(yàn)平臺:實(shí)驗(yàn)所使用的系統(tǒng)是64位的Windows 10,CPU為英特爾i7處理器,內(nèi)存8 GB.

實(shí)驗(yàn)數(shù)據(jù)集:實(shí)驗(yàn)中使用了2個標(biāo)準(zhǔn)的數(shù)據(jù)集kos arak、T10I4D100K,數(shù)據(jù)密度分別為0.02%,1.16%.這2個數(shù)據(jù)集的數(shù)據(jù)特性如表8所示,其中包括:交易總數(shù);同項目的數(shù)量;平均交易長度;最大交易長度。實(shí)驗(yàn)中2個數(shù)據(jù)集都沒有提供對應(yīng)的數(shù)量和單位利潤．在這里,以產(chǎn)生隨機(jī)數(shù)據(jù)的方式生成項在事務(wù)中的數(shù)量和單位利潤數(shù)據(jù)。

表8 數(shù)據(jù)集的特征

3.2 實(shí)驗(yàn)結(jié)果的分析

3.2.1 算法的運(yùn)行時間實(shí)驗(yàn)

本實(shí)驗(yàn)主要測試在不同最小效用閾值時算法運(yùn)行時間的對比,在數(shù)據(jù)集T10I4D100K和kosarak進(jìn)行實(shí)驗(yàn)。在相同的最小效用閾值下的運(yùn)行時間。

在如圖2和圖3中可清楚看到,隨著最小效用閾值逐漸降低,候選高效用項集的個數(shù)逐漸增多,因此,3組算法的運(yùn)行時間均增長,DPUP-Growrh算法和UP-Gr owrh算法運(yùn)行時間相差不大,但優(yōu)于D-HUI.因?yàn)镈P UP-Growrh算法和UP-Growrh都是以項的TWU值降序進(jìn)行排列,這種排列能夠減少搜索空間的范圍,從而加快算法速度。

圖2 數(shù)據(jù)集T10I4D100KFig.2 Dataset characteristics T10I4D100K

圖3 數(shù)據(jù)集kosarakFig.3 Dataset characteristics kosarak

3.2.2 數(shù)據(jù)發(fā)布的運(yùn)行時間實(shí)驗(yàn)

發(fā)布時間是數(shù)據(jù)所有者完成數(shù)據(jù)加密并交付給數(shù)據(jù)分析者的執(zhí)行時間。本組實(shí)驗(yàn)通過改變數(shù)據(jù)集的大小來對比發(fā)布時間的變化。

實(shí)驗(yàn)過程中隨機(jī)選擇數(shù)據(jù)集T10I4D100K和kosar ak交易總數(shù),如20 000,30 000,40 000,50 000和60 000條,在相同的最小效用閾值時,通過數(shù)據(jù)交易總數(shù)的變化進(jìn)行算法發(fā)布時間分析。

根據(jù)圖4和圖5可以看出:隨著發(fā)布數(shù)據(jù)集總數(shù)越來越多,各算法運(yùn)行時間也逐漸增加。DPUP-Growrh算法和UP-Growrh算法運(yùn)行時間相差不大,但是優(yōu)于D-HUI.因?yàn)榘l(fā)布的數(shù)據(jù)集總數(shù)越多,運(yùn)行時間越長。數(shù)據(jù)集的密度越小,三個算法運(yùn)行時間就越相近。

圖4 數(shù)據(jù)集T10I4D100KFig.4 Dataset characteristics T10I4D100K

圖5 數(shù)據(jù)集kosarakFig.5 Dataset characteristics kosarak

3.2.3 挖掘結(jié)果的準(zhǔn)確性實(shí)驗(yàn)

在數(shù)據(jù)集T10I4D100K和kosarak進(jìn)行實(shí)驗(yàn),以對比UP-Growrh和DPUP-Growth兩種算法的數(shù)據(jù)完整性。以D-HUI算法挖掘出高效模式集為原始數(shù)據(jù),即其數(shù)據(jù)完整性為100%.

其中,priData是以D-HUI算法挖掘出高效模式集,otherData是其他算法挖掘出的高效模式集。

從圖6和圖7可以看出:DPUP-Growrh在兩個數(shù)據(jù)集的完整性分別維持在35%和70%左右。由于完整性在可接受范圍內(nèi),DPUP-Growrh算法有效增加了用戶數(shù)據(jù)的安全性,有利于對數(shù)據(jù)的保護(hù)。因?yàn)樵跀?shù)據(jù)集T10I4D100K的數(shù)據(jù)密度和平均長度都高于kosarak,數(shù)據(jù)更為集中。

圖6 數(shù)據(jù)集T10I4D100KFig.6 Dataset characteristics T10I4D100K

圖7 數(shù)據(jù)集kosarakFig.7 Dataset characteristics kosarak

4 總結(jié)與展望

本文提出了一種基于差分隱私的高效用項目集挖掘方法,該方法安全性能大大提高,均衡了準(zhǔn)確性和效率。實(shí)驗(yàn)結(jié)果表明,本文提出的差分隱私DPUP-Growth發(fā)布方法在效率方面與沒有差分隱私相差無幾,完整性在誤差可接受范圍,對原始數(shù)據(jù)集起到很好的保護(hù)作用,防止被不法分子直接利用。由于數(shù)據(jù)是不斷發(fā)生變化的,可以從動態(tài)數(shù)據(jù)集中提取最新的有價值的信息。另一方面,由于數(shù)據(jù)量爆炸式的增長,現(xiàn)階段的單機(jī)計算資源需求已經(jīng)不能滿足用戶要求。因此,分布式計算與增量挖掘技術(shù)和高效用模式集挖掘的結(jié)合得到了人們的廣泛關(guān)注。