馬 煜,荀亞玲

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

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

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

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

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

1 相關(guān)工作

1.1 基于高效用模式集挖掘

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2 差分隱私的高效用模式樹(shù)

2.1 相關(guān)描述

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

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

表2 利潤(rùn)表

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

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

(1)

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

定義2(項(xiàng)目集X的效用) 事務(wù)Td中項(xiàng)目集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ù)庫(kù)總效用) 事務(wù)數(shù)據(jù)庫(kù)D的總效用就是所有事務(wù)效用的總和,定義為:

(4)

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

定義5(事務(wù)加權(quán)利用率) 一個(gè)項(xiàng)目集的事務(wù)加權(quán)利用率表示為T(mén)WU(X),定義為:

(5)

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

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

(6)

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

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

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

(7)

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

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

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

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

定義10(Laplace機(jī)制) 給定數(shù)據(jù)集D,通過(guò)在查詢(xún)結(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,輸出的查詢(xún)函數(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ī)制混淆項(xiàng)頭 表順序,建立樹(shù)的過(guò)程為每個(gè)節(jié)點(diǎn)添加拉普拉斯噪聲;(2)通過(guò)算法DPUP-Growth從生成的樹(shù)結(jié)構(gòu)DPUP-Tree獲得候選高效用模式集;(3)從候選高效用模式集中識(shí)別真正的高效用模式?；诓罘蛛[私的高效用項(xiàng)目集挖掘方法步驟如下:

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

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

表3 項(xiàng)目及其TWUs

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

表5 項(xiàng)目及其miut

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

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

輸入:交易加權(quán)利用率TWU,最小效用閾值Minutl輸出:混淆項(xiàng)頭表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,建立樹(shù)的過(guò)程為每個(gè)節(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時(shí),第一個(gè)節(jié)點(diǎn){C}被創(chuàng)建。{C}.nu的增加是通過(guò)T1的RTU減去T1中{C}項(xiàng)后面的剩余項(xiàng)的效用,即{C}.nu=RTU(T1)-(u({A},T1)+u({D},T1) =4.第二個(gè)節(jié)點(diǎn){A}是{C}子節(jié)點(diǎn)。計(jì)數(shù)=1和{A}.nu=(p({C})×q({C},T1)+p({A})×q({A},T1)=8.同理,第三個(gè)節(jié)點(diǎn){D}由{D}創(chuàng)建。當(dāng)T2={(C,2)(E,3)(A,4)(G,1)}插入到樹(shù)中的時(shí)候,{C}.nu增加p({C})×q({C},T2=2和{C}的計(jì)數(shù)增加到3.然后,在帶有{E}的節(jié)點(diǎn){C}下創(chuàng)建一個(gè)新節(jié)點(diǎn){E}.計(jì)數(shù)=3和{E}.nu=14.同樣,在節(jié)點(diǎn){E}下創(chuàng)建一個(gè)新節(jié)點(diǎn){A}的計(jì)數(shù)=4和{A}.nu=30.在插入所有重組的事務(wù)之后,DPUP-tree被完全構(gòu)建。如圖1所示樹(shù)結(jié)構(gòu)。

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

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

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

表6 {D}-CPB

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

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

從DPUP-tree生成高效用模式集,得到一組高效用項(xiàng)集,即:{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)平臺(tái):實(shí)驗(yàn)所使用的系統(tǒng)是64位的Windows 10,CPU為英特爾i7處理器,內(nèi)存8 GB.

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

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

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

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

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

在如圖2和圖3中可清楚看到,隨著最小效用閾值逐漸降低,候選高效用項(xiàng)集的個(gè)數(shù)逐漸增多,因此,3組算法的運(yùn)行時(shí)間均增長(zhǎng),DPUP-Growrh算法和UP-Gr owrh算法運(yùn)行時(shí)間相差不大,但優(yōu)于D-HUI.因?yàn)镈P UP-Growrh算法和UP-Growrh都是以項(xiàng)的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í)間實(shí)驗(yàn)

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

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

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

圖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),以對(duì)比UP-Growrh和DPUP-Growth兩種算法的數(shù)據(jù)完整性。以D-HUI算法挖掘出高效模式集為原始數(shù)據(jù),即其數(shù)據(jù)完整性為100%.

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

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

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

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

4 總結(jié)與展望

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