用于短頻繁項的隱私保護關(guān)聯(lián)規(guī)則挖掘方法

張翠翠,阮樹驊

(四川大學(xué) 計算機學(xué)院,四川 成都　610065)

?

用于短頻繁項的隱私保護關(guān)聯(lián)規(guī)則挖掘方法

張翠翠,阮樹驊

(四川大學(xué) 計算機學(xué)院,四川 成都610065)

摘要隨著數(shù)據(jù)量的增長,隱私保護的問題也愈發(fā)突出,文中是介紹了目前數(shù)據(jù)挖掘過程中隱私保護相關(guān)的基本技術(shù),提出了一種數(shù)據(jù)集中式分布下布爾數(shù)據(jù)集的關(guān)聯(lián)規(guī)則的挖掘算法,此方法在實現(xiàn)了隱私保護的同時,通過與或運算實現(xiàn)了數(shù)據(jù)集的壓縮。相關(guān)實驗數(shù)據(jù)表明,該算法有效減少了挖掘時間,并保證了誤差在可接受的范圍之內(nèi)。

關(guān)鍵詞隱私保護;關(guān)聯(lián)規(guī)則;壓縮;數(shù)據(jù)挖掘;短頻繁項集

1研究意義與研究現(xiàn)狀

1.1背景和意義

關(guān)聯(lián)規(guī)則挖掘是數(shù)據(jù)挖掘中主要技術(shù)之一,可用于發(fā)現(xiàn)存在于數(shù)據(jù)庫中項目或者屬性之間事先未知的或隱藏的關(guān)系。世間萬物事情的發(fā)生多少會有一些關(guān)聯(lián):一件事情發(fā)生,可能會引發(fā)另外一件事情的發(fā)生,或者說兩個事件在較大程度上會一起發(fā)生[1]。通過這個關(guān)聯(lián)規(guī)則,可由一件事情的發(fā)生來推測另一事件的發(fā)生,從而更好地了解和掌握事物的發(fā)展、動向等。

數(shù)據(jù)挖掘的目的在于從大量的數(shù)據(jù)中抽取出潛在的、有技術(shù)價值的知識。傳統(tǒng)數(shù)據(jù)挖掘技術(shù)不可避免地暴露敏感數(shù)據(jù),而這些敏感數(shù)據(jù)是數(shù)據(jù)所有者不希望被揭露的。另一方面,數(shù)據(jù)發(fā)布應(yīng)用中,如果數(shù)據(jù)發(fā)布者不采用適當(dāng)?shù)臄?shù)據(jù)保護措施,將可能造成敏感數(shù)據(jù)的泄露,從而給數(shù)據(jù)所有者帶來危害[2]。隱私保護技術(shù)就是為了解決上述問題產(chǎn)生的。實施數(shù)據(jù)隱私保護主要考慮兩個問題:如何保證數(shù)據(jù)應(yīng)用過程中不泄露隱私;如何更有利于數(shù)據(jù)應(yīng)用。

1.2研究現(xiàn)狀

目前,基于隱私保護的關(guān)聯(lián)規(guī)則挖掘的研究工作成果眾多,本文從所保護內(nèi)容的角度將關(guān)聯(lián)規(guī)則的隱私保護分為兩方面:(1)對敏感數(shù)據(jù)的隱藏保護。1)基于隨機化的處理方法。隨機響應(yīng)技術(shù)[3]是1965年Warner在統(tǒng)計學(xué)中為了保護被調(diào)查者的隱私而設(shè)計的數(shù)據(jù)隱藏技術(shù),后來用于關(guān)聯(lián)規(guī)則挖掘的隱私保護中。這對后來的隱私保護算法有較大的影響,2004年Aggarwal提出了一種MASK算法[4],之后張鵬等人提出了一種RRPH算法[5],對MASK進行了改進;2)分布式數(shù)據(jù)的安全計算。2002年,Clifton提出了垂直分布下基于兩個參與者的安全計算算法[6]。同年,文獻[7]中提出的SMC算法被廣泛應(yīng)用于水平分布的數(shù)據(jù)庫中。

(2)對敏感規(guī)則的隱藏保護。對于敏感關(guān)聯(lián)規(guī)則的隱藏即是設(shè)計一種算法,在阻塞盡量少數(shù)據(jù)值的情況下,將敏感關(guān)聯(lián)規(guī)則可能的支持度和置信度控制在預(yù)定閾值以下。

基于阻塞的技術(shù)。阻塞技術(shù)與隨機化技術(shù)修改數(shù)據(jù)、提供非真實數(shù)據(jù)的方法不同,阻塞技術(shù)采用的是不發(fā)布某些特定數(shù)據(jù)的方法,因為某些應(yīng)用更希望基于真實數(shù)據(jù)進行研究。2010年,文獻[9]中提出了一種DSRRC算法,利用統(tǒng)計信息在盡量少修改數(shù)據(jù)的同時完成對敏感關(guān)聯(lián)規(guī)則的隱私保護。

2關(guān)聯(lián)規(guī)則挖掘的概念與步驟

2.1基本概念

設(shè)I={I1,I2,…,In}是項的集合。設(shè)任務(wù)相關(guān)的數(shù)據(jù)D是數(shù)據(jù)庫事務(wù)的集合,其中每個事務(wù)t是項的集合,且t?I。每個事務(wù)有唯一的標(biāo)識符TID。設(shè)a是一個項集,事務(wù)t包含a,當(dāng)且僅當(dāng)a?t。一個關(guān)聯(lián)規(guī)則是形如a?b的蘊含式,其中a?I,b?I且a∩b=φ。規(guī)則a?b在事務(wù)集D中成立,具有支持度s,其中s是同時包含a和b的事務(wù)與總事務(wù)的比值,即事務(wù)集D中包含a∪b的百分比。

支持度的計算公式為

(1)

規(guī)則A?B在事務(wù)D中具有置信度c,其是事務(wù)集D中包含A的事務(wù)同時也包含事務(wù)B的百分比,即

(2)

2.2關(guān)聯(lián)規(guī)則的挖掘算法原理

Apriori關(guān)聯(lián)規(guī)則挖掘原理的過程分為以下兩步:

步驟1發(fā)現(xiàn)支持度不低于用戶給定的最小支持度閾值的頻繁項集。

步驟2根據(jù)步驟1發(fā)現(xiàn)的頻繁項集,產(chǎn)生置信度不低于用戶給定的最小置信度閾值的關(guān)聯(lián)規(guī)則。

隱私保護的關(guān)聯(lián)規(guī)則的挖掘,就是要在不精確訪問原始事務(wù)集D的條件下,盡可能精確的產(chǎn)生支持度和置信度分別不低于預(yù)先給定的閾值的關(guān)聯(lián)規(guī)則?；陔[私保護的基本框架如圖1所示。

圖1　隱私保護挖掘關(guān)聯(lián)規(guī)則基本框架

3關(guān)聯(lián)規(guī)則的挖掘

3.1與或運算數(shù)據(jù)壓縮的關(guān)聯(lián)規(guī)則挖掘

從現(xiàn)有的隱私保護方法來看,主要是通過改變個體信息,保留或者按照可計算的方式改變總體的統(tǒng)計信息,從而實現(xiàn)隱私保護數(shù)據(jù)挖掘。

現(xiàn)有的算法所需要的時間為

t=t關(guān)聯(lián)規(guī)則挖掘+t支持度還原

(3)

式(3)中,T關(guān)聯(lián)規(guī)則挖掘∝N。本文提出了一種新的基于短頻繁項的隱私保護方法,其中短頻繁項是指頻繁項中的項的個數(shù)比較小這種隱私保護方法能夠有效的減少事務(wù)的數(shù)量,從而加快關(guān)聯(lián)規(guī)則的挖掘時間。

該算法的思想是隨機抽取兩個樣本以概率p進行或運算,以概率q=(1-p)進行與運算。然后通過與或運算后產(chǎn)生的新的數(shù)據(jù)集中項的支持度計算出原本數(shù)據(jù)集中對應(yīng)的項的支持度,從而確定頻繁項。該算法的優(yōu)點是進行與或運算后能將數(shù)據(jù)集的數(shù)量壓縮1/2,從而使得關(guān)聯(lián)規(guī)則的挖掘時間減少了1/2,即T關(guān)聯(lián)規(guī)則挖掘時間∝N/2。這樣使得整個算法的時間減少,效率大幅提高。

3.2計算1項集的支持度

設(shè)i是一個項,π表示i在D中的支持度,λ表示i在D’中的支持度。下表描述了項i進行與或操作的結(jié)果,文中根據(jù)i在D和D,中的值是否相同得到關(guān)于λ和π的等式,從而得出i的支持度。

表1　1項集的與或結(jié)果

相對應(yīng)各項的概率如圖表2所示。

表2　1項集的與或概率

由表1和表2可知,1項集的計算方程

P×(1-π)×(1-π)+(1-P)×(1-π)×(1-π)+(1-P)×π×(1-π)+(1-P)×π×(1-π)=1-λ

P×π×(1-π)+P×π×(1-π)+P×π×π+(1-P)×π×π=λ

(4)

其解如式(5)所示

(5)

這樣可利用D’中項i的支持度λ計算出i在D中的支持度π,當(dāng)π≥預(yù)定支持度閾值時,文中便可確定項i是一個頻繁項。

3.3計算k項集的支持度

設(shè)A={i1,i2,…,ik-1,ik}是一個k項集,其中k的相對比較小,包含了事務(wù)集T={t1,t2,t3,…,tn-1,tn},n=2k欲求得D中各事務(wù)的支持度,則需要先通過Apriori算法來求得D’中各事務(wù)的支持度,然后利用事務(wù)之間的關(guān)聯(lián)關(guān)系來建立方程。定義1運算如式(6)所示

(6)

(7)

將所有事務(wù)的關(guān)系聯(lián)立方程如(8)所示

?

(8)

其中

(9)

通過求解Si可得到原有的各支持度。

可利用支持度之間的關(guān)系來減少挖掘量,例如當(dāng)需要計算二項集S(A,B)時,只需要挖掘出S(A,B),然后利用式(10)計算出項S(A,B)的其他相關(guān)值

(10)

3.4算法實現(xiàn)

可將以上方法應(yīng)用到現(xiàn)有各種頻繁項集生成的算法中,從而挖掘出感興趣的關(guān)聯(lián)規(guī)則。本文使用 Apriori 算法,對于變換后的數(shù)據(jù),文中先利用 Apriori 算法得出候選項集的支持度,然后應(yīng)用上述方法還原出候選項在數(shù)據(jù)變換前的支持度,進而確定頻繁項集。算法步驟如下:

//對每個項i計數(shù)

scan,for each item I∈I count I.count;

for (k=2;L(k-1)≠φ;k++) {

Ck=aproiri_gen (Lk-1);

//生成候選k項集ck

for each transaction t∈D′ {

for (j=1;j≤k;j++) {

//事務(wù)t中恰好包含j項的候選k項集

Ct,j=partial_subset (Ck,t,j);

for each candidate c∈Ct,j

c.countj++;

}

}

for each candidate c∈Ck {

c.count=f(c.count0,c.count1,c.countn);

//通過現(xiàn)有關(guān)系求得c.count.

L(k)={{c}|c∈Ck,c.count/N≥s};

}

}

return L=∪L(k);

4實驗與分析

文中通過一組實驗來對比本算法與MASK方法在進行隱私保護關(guān)聯(lián)規(guī)則挖掘時的效果,并說明參數(shù)P的選擇,數(shù)據(jù)集大小對挖掘結(jié)果準(zhǔn)確性的影響。

4.1實驗方法

頻繁項I的計算誤差為

(11)

項集F的平均誤差為

(12)

本文通過挖掘1項集的支持度來驗證算法的可行性,將P設(shè)置成不同的值來觀察P對SE(I)的影響。然后將P設(shè)置成0.4,利用上述算法來求得1項集的支持度,并與實際支持度做對比分析。最后將P設(shè)置為0.5,通過修改數(shù)據(jù)集的大小來觀察數(shù)據(jù)集對SE(I)的影響。

4.2實驗結(jié)果

4.2.1頻繁項長度對誤差的影響

首先將閾值設(shè)置為1%,P設(shè)置為0.4,將允許挖掘頻繁項的長度逐步增大,結(jié)果如圖2所示,可看出隨著最大項集的增大,誤差越來越大,因此本算法只適用于短頻繁項的挖掘?，F(xiàn)實數(shù)據(jù)中,長頻繁項并不多見,因此本算法具有一定的實際應(yīng)用價值。

圖2　誤差隨最大頻繁項集的長度的變化

4.2.2p對支持度誤差的影響

1項集的SE(I)和SVE隨P變化的情況分別如圖3所示所示(P的變化步長為0.1)。

圖3　2項集SEV隨p變化情況

由圖3可知,當(dāng)在0.1～0.9的區(qū)間變化時,不同P對結(jié)果總誤差的影響差不多,因此的選取對SEV的影響較小。

4.2.3數(shù)據(jù)集對誤差和時間的影響

由圖4可知,當(dāng)數(shù)據(jù)集越大的時候誤差趨向于減小。因此,可知對于該算法數(shù)據(jù)集越大精確度越高。由圖5可知,當(dāng)數(shù)據(jù)集增大時,本算法在時間上的優(yōu)勢愈發(fā)明顯。

圖4　誤差隨數(shù)據(jù)集大小的變化

圖5　計算時間T隨數(shù)據(jù)集大小的變化

4.3結(jié)果分析

4.3.1隨機性選取對結(jié)果的影響

由于在數(shù)據(jù)壓縮的過程中,即選取隨機兩個樣本事務(wù)進行與或運算的過程中,如何選取兩個樣本事務(wù)是還原支持度的關(guān)鍵,因此,選取一種隨機抽取方法是本算法實施的重要環(huán)節(jié)。

4.3.2數(shù)據(jù)集大小對結(jié)果的影響

當(dāng)數(shù)據(jù)集較小時,本算法在還原支持度時會造成嚴(yán)重失真,因此本算法只能用于數(shù)量級較大的數(shù)據(jù)集上。由圖4可知,當(dāng)數(shù)據(jù)集越大時誤差趨向于減小。因此,可知對于該算法數(shù)據(jù)集越大精確度越高。由圖5可知,當(dāng)數(shù)據(jù)集增大時,本算法在時間上的優(yōu)勢愈發(fā)明顯。同時由圖2也可以看到隨著最大頻繁項集長度的增加,誤差也會越來越大,因此該方法適用于短頻繁項計算。

4.3.3實驗準(zhǔn)確性分析

有實驗的結(jié)果對比如圖2所示,文中由經(jīng)過算法變換之后還原一項集合二項集的支持度與直接從原始數(shù)據(jù)中挖掘數(shù)據(jù)項的支持度相比誤差較小,達到了理想效果。同時,經(jīng)過實驗證明當(dāng)項集的長度在一定范圍內(nèi)增加時,實驗結(jié)果的準(zhǔn)確度幾乎不變。說明該算法在段頻繁項上的應(yīng)用是可行的,準(zhǔn)確度相對較高。

5結(jié)束語

當(dāng)頻繁項的項數(shù)太多時會導(dǎo)致本算法的未知項過多,計算量過大,消耗時間長等問題,因此該算法只適用于短頻繁項。由實驗結(jié)果可知,在減少了一半事務(wù)的前提下本實驗結(jié)果的誤差在可接受的范圍內(nèi),說明此算法在短頻繁項中有較好的應(yīng)用。

隱私保護技術(shù)在諸多領(lǐng)域都有廣泛的應(yīng)用,是近年來學(xué)術(shù)界新興的研究課題。本文在壓縮數(shù)據(jù)集的情況下進行了隱私保護關(guān)聯(lián)規(guī)則挖掘的試探性工作。首先提出了通過對數(shù)據(jù)進行與或操作對數(shù)據(jù)集進行壓縮,從而隱藏原始數(shù)據(jù)中的信息,同時使得變換后的數(shù)據(jù)集減少了一半,這樣數(shù)據(jù)集變換后所占用的空間減少了1/2。本文不僅從理論上分析了運用該算法進行挖掘的準(zhǔn)確性,且通過實驗驗證了這一結(jié)論。通過合理的數(shù)據(jù)選擇,文中能實現(xiàn)在空間量減小一半的情況下,實現(xiàn)與原來方法效果相似的隱私性和準(zhǔn)確性,且還具有較好的使用性。

參考文獻

[1]Nkweteyim D L,Hirtle S C.A new joinless apriori algorithm for mining association rules[J].Computer Science,2005,3(3):284-288.

[2]周水庚,李豐,陶宇飛,等.面向數(shù)據(jù)庫應(yīng)用的隱私保護研究綜述[J].計算機學(xué)報,2009,32(5):847-861.

[3]Warner S L.Randomized response:a survey technique for eliminating evasive answer bias[J].Journal of the American Statistical Association,1965,60(30):63-69.

[4]Aggarwal C C,Yu P S.A condensation approach to privacy preserving data mining[J].Lecture Notes in Computer Science,2004,25(12):183-199.

[5]張鵬,童云海,唐世渭,等.一種有效的隱私保護關(guān)聯(lián)規(guī)則挖掘方法[J].軟件學(xué)報,2006,17(8):1764-1774.

[6]Yan-Hua F U,Si-Yang G U.Privacy preserving association rule mining in vertically partitioned data[J].Journal of Computer Applications,2002,26(1):639-644.

[7]Kantarcioglu M,Clifton C,Kantarcioglu M.Privacy-preserving distributed mining of association rules on[J].IEEE Transactions on Knowledge & Data Engineering,2002,16(9):1026-1037.

[9]Saygin Y,Verykios V S,Elmagarmid A K.Privacy preserving association rule mining[J].Research Issues in Data Engineering:Engineering E-Commerce/E-Business Systems,2002,35(2):151-158.

[10]Modi C N,Rao U P,Patel D R.Maintaining privacy and data quality in privacy preserving association rule mining[C].San Diego,CA,USA:2010 International Conference on IEEE,IEEE,2010.

[11]葛偉平.隱私保護的數(shù)據(jù)挖掘[D].上海:復(fù)旦大學(xué),2005.

[12]張海濤,黃慧慧,徐亮,等.隱私保護數(shù)據(jù)挖掘研究進展[J].計算機應(yīng)用研究,2013,30(12):3529-3635.

[13]陳永春,王曉.隱私保護關(guān)聯(lián)規(guī)則挖掘算法分析及研究進展[J].哈爾濱師范大學(xué)自然科學(xué)學(xué)報,2012,28(2):57-59,68.

[14]王銳,劉杰.隱私保護關(guān)聯(lián)規(guī)則挖掘算法的研究[J].計算機工程與應(yīng)用,2009,45(26):126-130.

[15]湯琳,何豐.隱私保護的數(shù)據(jù)挖掘方法的研究[J].計算機技術(shù)與發(fā)展,2011,21(4):156-159.

[16]劉浩然,劉方愛,李旭,等.有效的不確定數(shù)據(jù)概率頻繁項集挖掘算法[J].計算機應(yīng)用,2015(6):1757-1761.

[17]Borgelt C.Frequent item set mining[J].Wiley Interdisciplinary Reviews:Data Mining and Knowledge Discovery,2012(6):437-456.

A Privacy Preserving Association Rules Mining Method for Short Frequent Itemsets

ZHANG Cuicui,RUAN Shuhua

(College of Computer,Sichuan University,Chengdu 610065,China)

AbstractThe explosion of data poses increasingly challenges on privacy preservation.This paper introduces basic technologies related to the privacy preservation in data mining,and puts forward a mining algorithm under association rule to deal with the Boolean data set distributed in a centralized manner.The method compresses the data set while preserving privacy,thus enormously reducing the time of data mining.Test results show that the mining time is significantly reduced with acceptable errors by this algorithm.

Keywordsprivacy preservation;association rule;compression;data mining;short frequent itemsets

doi:10.16180/j.cnki.issn1007-7820.2016.05.024

收稿日期:2015-10-18

作者簡介:張翠翠(1990—),女,碩士研究生。研究方向:人工智能等。阮樹驊(1966—),女,碩士,副教授。研究方向:數(shù)據(jù)庫系統(tǒng)等。

中圖分類號TP311.563

文獻標(biāo)識碼A

文章編號1007-7820(2016)05-088-05