增量式隱私保護頻繁模式挖掘算法

張亞玲，王 婷，王尚平

(西安理工大學(xué) 計算機科學(xué)與工程學(xué)院，西安 710048)(*通信作者電子郵箱ylzhang@xaut.edu.cn)

0 引言

隨著信息與網(wǎng)絡(luò)技術(shù)的飛速發(fā)展，數(shù)據(jù)挖掘,尤其是頻繁項集的挖掘[1]在揭示各類隱藏的模式或知識的同時，也相應(yīng)地產(chǎn)生了隱私保護方面的隱憂，因為在數(shù)據(jù)挖掘過程中一些個人隱私或者共同隱私容易受到侵犯。如消費者在使用信用卡、會員卡、醫(yī)療保健卡和電子商務(wù)網(wǎng)站購物等活動中，個人信息很容易被公司或企業(yè)獲取，因此，隱私保護[2]和信息安全[3]成為數(shù)據(jù)挖掘中一個迫切需要解決的問題，越來越引起人們的廣泛關(guān)注。

隱私保護技術(shù)是指采用某種技術(shù)來隱藏敏感數(shù)據(jù)或敏感知識,它對于能否有效地隱藏數(shù)據(jù)或知識以及能在多大程度上進行隱藏有重要影響。目前，在隱私保護數(shù)據(jù)挖掘中所采用的算法主要分為兩類：1)基于安全多方計算技術(shù)的方法[4-5]；2)基于隨機的方法[6-7]。

基于隨機的方法根據(jù)具體的需要對原始數(shù)據(jù)庫中的記錄進行模糊化處理的同時保持數(shù)據(jù)的統(tǒng)計特性，在經(jīng)過處理的數(shù)據(jù)庫上進行數(shù)據(jù)挖掘，通過對數(shù)據(jù)的原始統(tǒng)計特性的估計來得到較為準確的處理結(jié)果，同時又不泄露用戶的原始數(shù)據(jù)。在布爾數(shù)據(jù)集上基于概率變換的支持度重構(gòu)的方法是基于隨機方法的一個重要研究分支。文獻[8]結(jié)合隱私保護查詢限制與數(shù)據(jù)干擾這兩種基本策略提出一種部分隱藏的隨機化回答(Randomized Response with Partial Hiding， RRPH)算法，在對原始數(shù)據(jù)進行隱藏與變換為基礎(chǔ)上進行數(shù)據(jù)干擾，之后采用高效且簡單的頻繁項集生成算法，最后進行隱私保護關(guān)聯(lián)規(guī)則挖掘。該算法存在重構(gòu)真實項集支持度上的指數(shù)級運算和頻繁掃描數(shù)據(jù)庫的缺點，使得其在效率上受到了嚴重的制約。文獻[9]中提出了RRPH算法的改進算法，該算法使用集合運算和分治策略對RRPH進行改進，消除重構(gòu)真實數(shù)據(jù)集支持度上的指數(shù)級別的巨大的運算量。然而，由于Apriori需要多次對數(shù)據(jù)庫進行掃描，文獻[9]的算法效率仍然會受到多次掃描數(shù)據(jù)庫的影響。針對以上問題，本文的研究思路是，首先引入bitmap[10]對數(shù)據(jù)庫中的事務(wù)進行表示，避免了算法執(zhí)行中對數(shù)據(jù)庫的多次掃描；其次，通過引入增量更新模型，使得算法在面臨數(shù)據(jù)更新問題時，仍然具有高效性。

1 RRPH算法及其改進算法的分析

部分隱藏的隨機化回答(RRPH)算法[8]是一種基于部分隱藏隨機化回答技術(shù)的隱私保護的頻繁模式挖掘算法，該算法結(jié)合查詢限制和數(shù)據(jù)干擾兩種策略，對隨機化參數(shù)的選擇沒有限制,不需要額外的信息,該算法適用于分布式數(shù)據(jù)庫和集中式數(shù)據(jù)庫。

RRPH算法對數(shù)據(jù)的隨機化隱藏的過程為：對于布爾類型的數(shù)據(jù)庫，選定隨機參數(shù)p1,p2,p3，其中p1+p2+p3=1且0≤p1,p2,p3≤1，對于數(shù)據(jù)庫中的項a∈{0,1},設(shè)r1=a,r2=1-a,r3=0,給定隨機函數(shù)r(a)和函數(shù)pj的概率取值rj(j=1,2,3)。假如數(shù)據(jù)庫中屬性的個數(shù)為k，則原始事務(wù)A=(a1,a2,…,ak)經(jīng)過干擾之后轉(zhuǎn)變?yōu)槭聞?wù)B=(b1,b2,…,bk)的概率可以由B=R(A)計算得到，其中bi=r(ai)，即bi取值為ai的概率為p1,取值為ai的反的概率為p2，取值為0的概率為p3。

針對RRPH算法在重構(gòu)頻繁項集真實支持度時的指數(shù)級別的運算量而導(dǎo)致算法效率下降的問題，文獻[9]采用集合運算和分治策略提出了改進的RRPH算法，消除了重構(gòu)真實支持度時指數(shù)級別的復(fù)雜度，提高了算法效率。

由于文獻[9]的改進主要是針對RRPH算法的重構(gòu)支持度的改進，該算法仍然需要完全的數(shù)據(jù)庫掃描以及呈指數(shù)級別增長的比較操作，因此算法的效率仍是制約該算法的關(guān)鍵問題。此外，文獻[8-9]都沒有考慮數(shù)據(jù)增量更新的問題。事實上，在大數(shù)據(jù)時代，每天會產(chǎn)生數(shù)以萬計的增量數(shù)據(jù)，這些增量數(shù)據(jù)很有可能對數(shù)據(jù)挖掘結(jié)果產(chǎn)生巨大的影響。具有增量更新性質(zhì)的隱私保護的頻繁模式挖掘算法更具有實際意義。本文將基于以上兩個問題，提出一種增量的基于位圖的RRPH(Incremental Bitmap-based RRPH, IBRRPH)算法。

2 IBRRPH算法的原理和分析

2.1 使用bitmap技術(shù)轉(zhuǎn)換數(shù)據(jù)

假設(shè)用R來表示關(guān)系模式，A={A1,A2,…,An}表示組成R的屬性集合，任一屬性Ai在Di(1≤i≤n)的范圍內(nèi)取值，則定義在該模式上元組的真實取值范圍為U=D1×D2×…×Dn。

定義1 給定r是關(guān)系模式R上的任一關(guān)系，任一屬性Ai(1≤i≤n)在r上的真實取值范圍簡稱活動域，表示為ADom(Ai,r)={d∈Di|?t∈r,t(Ai)=d}。通?？梢詫Dom(Ai,r)簡稱為ADom(Ai)。

定義2 給定r是關(guān)系模式R上的任一關(guān)系，則ADom(Ai)到r的映射F可以表示為F:V→ADom(Ai)，V表示r中元組的全集。ADom(Ai)中任何一個可能值表示為c(c∈ADom(Ai))，關(guān)系r中在Ai上值為c的元組全集稱為c在r上的逆像，表示為F-1(c)={t|t∈V,t(r)=c}。

定義3 假設(shè)R上的任一關(guān)系r含有m個元組，而r在Ai上的某一可能取值表示為c(c∈ADom(Ai))，則可以使用m位二進制數(shù)來代表關(guān)系r在Ai上值為c的位置，稱此m位二進制數(shù)為關(guān)系r中在Ai上值為c的bitmap，記為Bin(Ai,c)。如果ts是r中第s個元組，倘若ts∈F-1(c)，則Bin(Ai,c)中第s位的取值范圍為{0,1}。

定義4 假設(shè)任一關(guān)系r中包含N個元組，r在(A1,A2,…,Al)上的值為(c1,c2,…,cl)，則根據(jù)定義3，用bitmap可定義為Bin((A1,A2,…,Al),(c1,c2,…,cl))。設(shè)P=(c1,c2,…,cl)為r上模式，其長度為l，那么P的支持度計數(shù)表示為freq(P)=Count(Bin((A1,A2,…,Al),(c1,c2,…,cl)))，函數(shù)Count()表示bitmap中1的數(shù)量。假設(shè)最小支持度閾值為θ(0<θ<1)，當(dāng)freq(P)≥θN時，P是頻繁模式；否則P不是頻繁模式。

定義5 給定數(shù)據(jù)庫D共包含N條事務(wù){(diào)T1,T2,…,Tn}，其中Ti是屬性集{A1,A2,…,An}的子集，則D可視為共有N個元組的關(guān)系，其中任意事務(wù)Ti都含有n個屬性，ADom(Ai,r)={‘0’,‘1’}。如果任一事務(wù)Tj在Ai上取值是‘1’，則意味著Ai出現(xiàn)在事務(wù)Tj中，為‘0’則意味著Ai沒有出現(xiàn)在事務(wù)Tj中。

原始數(shù)據(jù)庫表中的任意一條記錄在bitmap中具有唯一的位置偏移。每個事務(wù)均勻地分布在這一固定的位置偏移上。

伴隨著使用bitmap對數(shù)據(jù)庫中記錄的轉(zhuǎn)變，算法中的計數(shù)方式也隨之發(fā)生了改變，BRRPH算法采用“位與”操作作為計數(shù)方式，可以有效提高支持度的計數(shù)速度。

設(shè)存在表1所示的事務(wù)數(shù)據(jù)庫，則bitmap規(guī)范之后的交易列表如表2所示。其中：TID為事務(wù)ID，ItemId為項ID。

表1 事務(wù)數(shù)據(jù)庫D

表2 規(guī)范之后的交易列表

使用位與運算可以快速對項集計數(shù)。例如：項集{I1}的bitmap表示為100110111；{I2}的bitmap表示為111101011，則{I1，I2}的bitmap表示為10010001，因此，統(tǒng)計{I1，I2}的bitmap表示100100011中1的個數(shù)，即可得項集{I1，I2}的支持度為4。通過對bitmap中的項集交集操作，可以提高算法的效率。

2.2 BRRPH算法

基于Bitmap的部分隱藏的隨機化回答(Bitmap-based Randomized Response with Partial Hiding, BRRPH)算法是基于Bitmap技術(shù)對文獻[9]算法進行的改進，目標(biāo)是提高算法的效率。BRRPH算法可以描述為以下3步：

步驟1 預(yù)先設(shè)置隨機化參數(shù)p1,p2,p3的值，采用文獻[9]算法對數(shù)據(jù)庫中的原始記錄進行隱藏或變換。

步驟2 將經(jīng)過扭曲的數(shù)據(jù)保存在Bitmap文件中，使用Bitmap技術(shù)中的位與技術(shù)，可以提高算法得到頻繁項集的效率。

步驟3 在轉(zhuǎn)化后的文件上使用文獻[9]算法進行數(shù)據(jù)挖掘，結(jié)合Bitmap計算和分治策略等方法重構(gòu)原始數(shù)據(jù)的真實支持度，從而得到頻繁項集。

BRRPH算法的總體框架如圖1所示。

圖1 BRRPH的總體框架

2.3 IBRRPH算法原理

2.3.1 增量更新算法基礎(chǔ)

數(shù)據(jù)庫中所包含的數(shù)據(jù)并不是一成不變，而是會隨著時間的流逝而產(chǎn)生或大或小的變化，由于數(shù)據(jù)庫的更新，會引入新的關(guān)聯(lián)規(guī)則并使一些現(xiàn)有的關(guān)聯(lián)規(guī)則失效，頻繁項集也存在類似的更新問題。一般情況下，人們更專注于設(shè)計和研究隱私保護的關(guān)聯(lián)規(guī)則挖掘方面的相關(guān)算法，卻忽略了數(shù)據(jù)庫發(fā)現(xiàn)的規(guī)則只反映數(shù)據(jù)庫的當(dāng)前狀態(tài)這一事實。為了使揭露的規(guī)則穩(wěn)定可靠，應(yīng)在相當(dāng)長的一段時間內(nèi)收集大量數(shù)據(jù)。所以，在算法的設(shè)計中，要使研究更具有實際意義，不僅要關(guān)注與設(shè)計頻繁模式關(guān)聯(lián)規(guī)則挖掘算法，更要解決其更新帶來的相關(guān)規(guī)則的變化。數(shù)據(jù)庫中的事務(wù)有增加和減少兩種不同的變換情況，應(yīng)對這兩種變換的基本策略沒有太大差異，減量型挖掘算法可以對比增量型挖掘算法完成，本文將討論數(shù)據(jù)增量型頻繁模式的挖掘算法。

如圖2所示，D為以前的舊的數(shù)據(jù)庫，D+為增加的數(shù)據(jù)庫，D′為新增一些數(shù)據(jù)之后的新數(shù)據(jù)庫。在增量式挖掘中，主要解決當(dāng)一個數(shù)據(jù)集D+增加到原來的數(shù)據(jù)庫中時，引入新的關(guān)聯(lián)規(guī)則并使一些現(xiàn)有的關(guān)聯(lián)規(guī)則[11]失效。本文在BRRPH算法的基礎(chǔ)上加入了增量更新技術(shù)，用于維護數(shù)據(jù)挖掘過程中發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則。

圖2 數(shù)據(jù)庫增量示意圖

針對數(shù)據(jù)庫中數(shù)據(jù)新增的問題，首先想到的方法是在整個更新的數(shù)據(jù)庫上重新運行關(guān)聯(lián)規(guī)則挖掘算法。這種方法雖然簡單，卻造成了之前挖掘結(jié)果的極大浪費。最初在找出舊的大項目集時完成的所有計算都被浪費，新的頻繁項集都必須重新開始計算。文獻[12]提出了一種有效的算法——FUP(Fast UPdate)，用于計算更新數(shù)據(jù)庫中的大項集。在FUP中舊的大項目信息可以重復(fù)使用。此外，獲得新數(shù)據(jù)庫的頻繁項集之后，便可以大量修剪候選項集。FUP算法的優(yōu)勢主要體現(xiàn)在減量式和增量式數(shù)據(jù)挖掘中，如分布式環(huán)境中并行處理大數(shù)據(jù)、使用改進的增量式關(guān)聯(lián)規(guī)則數(shù)據(jù)挖掘算法分析警報信息、增量式計算等。本文將用到FUP算法中介紹的引理。

設(shè)A.supportD表示屬性集A在原始數(shù)據(jù)庫D中的支持度，A.supportD+表示屬性集A在增加的數(shù)據(jù)庫D+中的支持度。A.supportD′為增加一部分數(shù)據(jù)庫后新數(shù)據(jù)庫D′中屬性A的支持度，d表示原始數(shù)據(jù)庫D的事務(wù)個數(shù)，d+表示增加的數(shù)據(jù)庫D+的長度，Lk是D中的頻繁k項集，Lk′是D′中的頻繁k項集，Ck是第k次迭代產(chǎn)生的候選k項集，那么，存在以下增量更新的性質(zhì)[12]。

性質(zhì)1 1項集A在原始數(shù)據(jù)庫D中不為頻繁1項集，在數(shù)據(jù)庫D′中不為頻繁1項集，當(dāng)且僅當(dāng)A.supportD′

性質(zhì)2 1項集A在原始數(shù)據(jù)庫D中不是頻繁項集，A.supportD+>d+×c是A在數(shù)據(jù)庫D′中為頻繁1項集的必要不充分條件。

性質(zhì)3 {A1,A2,…,Ak-1}在第k-1次迭代中是原始數(shù)據(jù)庫D中的頻繁項集，即{A1,A2,…,Ak-1}?Lk-1，但不是D′中的頻繁項集，即{A1,A2,…,Ak-1}?Lk-1′，那么，D中子集包含{A1,A2,…,Ak-1}的頻繁k項集均不在D′的頻繁k項集中。

性質(zhì)4 {A1,A2,…,Ak}是原始數(shù)據(jù)庫D中的頻繁k項集，即{A1,A2,…,Ak}?Lk，在數(shù)據(jù)庫D′中不為頻繁項集，當(dāng)且僅當(dāng){A1,A2,…,Ak}.supportD′

性質(zhì)5k項集{A1,A2,…,Ak}在原始數(shù)據(jù)庫D中不是頻繁k項集，{A1,A2,…,Ak}.supportd+≥c×d+是{A1,A2,…,Ak}在數(shù)據(jù)庫D′中為頻繁k項集的必要不充分條件。

性質(zhì)6A.supportD′=A.supportD+A.supportD+

下面將在BRRPH算法的基礎(chǔ)上，利用上述原理，在算法中加入增量更新模型，提高在增量更新情況下的隱私保護挖掘效率。

2.3.2 IBRRPH算法

本文的IBRRPH算法是一個具有隱私保護機制特性的考慮增量更新的頻繁模式挖掘算法。IBRRPH算法的第一步即需要將新增的部分數(shù)據(jù)庫進行隱藏和變換；然后在經(jīng)過了隱私保護的數(shù)據(jù)集上進行數(shù)據(jù)挖掘，計算得到候選項集的支持度之后，結(jié)合分治策略和逆矩陣的方法求出該候選項集在原始數(shù)據(jù)庫中估計的支持度；最后，得到新的數(shù)據(jù)庫中的頻繁項集，因此在IBRRPH算法中，增量之后的數(shù)據(jù)庫的支持度的值為該項集在原始數(shù)據(jù)庫中的支持度與新增數(shù)據(jù)庫的支持度之和，即X.supportD′=X.supportD+X.supportD+。

在IBRRPH算法中，supportD=d×c,supportD+=d+×c,supportD′= (d+d+)×c。

如果A.supportD+≥d+×c，即A在小數(shù)據(jù)庫d+中為頻繁項集，當(dāng)A∈L，那么A.supportD≥d×c，則A為頻繁項集。當(dāng)A?L，需要重新計算A.supportD+A.supportD+，看是否滿足A.supportD+A.supportD+≥supportD′。

如果A.supportD+

根據(jù)上述結(jié)論可得出增量訪問關(guān)系如表3所示。本文將此關(guān)系應(yīng)用于增量隱私保護數(shù)據(jù)挖掘算法中，以達到在利用之前挖掘結(jié)果的基礎(chǔ)上加速挖掘過程的目的。

表3 增量訪問關(guān)系

2.4 IBRRPH算法描述

輸入：1)D，表示原始數(shù)據(jù)庫； 2)Lk，表示D中的k頻繁項集，k=1,2，…r； 3)D+，表示新增數(shù)據(jù)庫； 4)s，表示最小支持度。

輸出：L′，表示所有頻繁項集。

1)根據(jù)文獻[9]算法對D+中的數(shù)據(jù)變換和隱藏，利用bitmap轉(zhuǎn)換規(guī)則將扭曲之后的數(shù)據(jù)轉(zhuǎn)換為bitmap文件。

2)生成L1′，即數(shù)據(jù)庫D+D+的頻繁1項集，k=1。在這個過程中，原始數(shù)據(jù)庫D中的頻繁1項集是已知的。挖掘頻繁1項集的具體過程如算法1所示。

算法1 Mining 1-itemsets of databaseD′。

M=L1;C=?;L1=?;Q=?;

for allt∈D+do

for all 1-itemsetA?L1do{

ifA∈MthenA.supportD+++;

else{

//將A加入候選項集C中，并初始化支持度計數(shù)

ifA?Cthen {C=C∪{A};A.supportD+=0;}

A.supportD+++;}

}

for allA∈Mdo

if getTureSupport(A,A.supportD+D+)≥c×(d+d+)

thenL1′=L1′∪{A}

for allA∈Cdo

//修剪C中的項集

if getTureSupport(A,A.supportD+)

then {C=C-{A};Q=Q∪{A}}

for allt∈Ddo

for all 1-itemsetA?tdo {

ifA∈CthenA.supportD++;

ifA∈Pthen removeAfromt;

}

for allA∈Cdo

ifA.supportD+D+≥c×(d+d+)

thenL1′=L1′∪{A};

returnL1′;

//getTureSupport(A,num)方法為獲取項集A的真實支持度

3)對于k=2,3,…,n,重復(fù)以下過程，生成Lk′，直到Lk′=null或者D+=?。在此過程中，原始數(shù)據(jù)庫D中的頻繁k-1項集Lk-1，候選k項集Ck等是已知的。頻繁k項集的挖掘過程如算法2所示。

算法2 Miningk-itemsets of databaseD′。

M=Lk;Lk′=?;

C=brrph-gen(Lk-1′)-Lk;

for allk-itemsetA∈Mdo

for all (k-1)-itemsetB∈Lk-1-Lk-1′ do

ifB?A

then {M=M-{A};break;}

for allt∈D+do{

for allA∈getSub(M,t) doA.supportD+++;

for allA∈getSub(C,t) doA.supportD+++;

reduce_db(t);

}

for allA∈Mdo

if getTureSupport(A,A.supportD+D+)≥c×(d+d+)

thenLk′=Lk′∪{A};

for allA∈Cdo{

if getTureSupport(A,A.supportD+)

thenC=C-{A};

reduce_db(t);

}

for allt∈Ddo{

for allA∈getSub(C,t) doA.supportD++;

reduce_db(t);

}

for allA∈Cdo

if getTureSupport(A,A.supportD+D+)≥c×(d+d+)

thenLk′=Lk′∪{A};

returnLk′;

//getSub(M,t)返回t中所有包含M中任一項的子集。

//reduce_db(t);刪除db或DB中一些在下一次迭代中

//不需要的項目

2.5 IBRRPH算法挖掘準確度分析

增量式隱私保護數(shù)據(jù)挖掘與普通隱私保護數(shù)據(jù)挖掘算法的不同之處主要在于利用了之前的挖掘結(jié)果。IBRRPH算法對增量數(shù)據(jù)集的挖掘，主要是利用了FUP算法的性質(zhì)，得到加入增量之后的挖掘結(jié)果。

在挖掘結(jié)果的準確度方面，IBRRPH算法分別分析原始數(shù)據(jù)集與增量數(shù)據(jù)集的頻繁項集，在算法過程中考慮了其所有可能的情況，根據(jù)表3的分析，在原始庫和增量庫中都不是頻繁項集的項集也不可能是全局頻繁項集，因此，本文算法在挖掘結(jié)果上與原BRRPH算法是等價的。

3 實驗結(jié)果與分析

本文算法實驗平臺為：Intel Core i5- 4460 CPU 3.2 GHz處理器和4 GB內(nèi)存,Windows 7操作系統(tǒng),開發(fā)軟件為eclipse 4.3。實驗中對于文獻[9]算法、BRRPH、IBRRPH等算法進行了實現(xiàn)和性能測試。實驗所用的數(shù)據(jù)全部由IBM Quest Market-Basket Synthetic Data Generator生成。本文所做實驗基于T10I4D100KN100等數(shù)據(jù)集。

3.1 BRRPH算法實驗與分析

3.1.1 性能分析

本節(jié)選取的參數(shù)為p1=p,p2=p3=(1-p1)/2，而p的取值分布于0.1～0.9。

圖3為BRRPH算法與文獻[9]算法的基于T10I4D100KN100數(shù)據(jù)集的運行時間對比。原始數(shù)據(jù)庫以參數(shù)為p1,p2,p3的概率進行干擾，其中p1=0.6,p2=0.2,p3=0.2，最小支持度為3%。

圖3表明，兩個算法隨著項集個數(shù)的增加，運行時間均呈遞增趨勢。當(dāng)n<5時，由于兩個算法消耗的時間均比較少，BRRPH算法的優(yōu)勢不明顯；隨著n的增加，BRRPH算法相對于文獻[9]算法在效率上的優(yōu)越性越來越明顯。實驗結(jié)果表明，與文獻[9]算法相比，BRRPH算法在效率上有了很大幅度的提高。

圖3 兩種算法在不同項集個數(shù)時的運行時間

數(shù)據(jù)集的總數(shù)分別取50×103,75×103,100×103,125×103，150×103,175×103,200×103,225×103,250×103,275×103，得到頻繁5-項集所需時間對比如圖4所示。

通過圖4可以得知，隨著事務(wù)個數(shù)的增加，與文獻[9]算法相比，BRRPH算法在效率上有了很大幅度的提高。由于BRRPH算法添加了將數(shù)據(jù)庫轉(zhuǎn)化為bitmap文件的過程，在數(shù)據(jù)規(guī)模較小時,BRRPH算法的優(yōu)勢較不明顯；而隨著數(shù)據(jù)規(guī)模的增長，BRRPH算法相對于文獻[9]算法優(yōu)勢明顯。

3.1.2 準確性分析

本實驗將從支持度誤差和頻繁項集誤差兩個方面來分析算法的準確性。

圖5給出在c=3%時，BRRPH算法和文獻[9]算法的項集誤差隨隨機參數(shù)p的變化曲線。圖6給出p1=0.6,p2=0.2,p3=0.2時，BRRPH算法和文獻[9]算法的項集的支持度誤差隨著最小支持度閾值c的變化曲線。

由圖5～6分析可知，在算法參數(shù)沒有差異的情況下，BRRPH算法相比文獻[9]算法，在項集誤差和支持度誤差上沒有明顯下降。

圖5 兩種算法在不同隨機參數(shù)p時的項集誤差

圖6 兩種算法在不同最小支持度閾值時的支持度誤差

3.2 IBRRPH算法實驗與分析

下面本文從保持支持度相同逐漸增加增量的角度和保持增量相同支持度不同的角度分別進行了文獻[9]算法和本文IBRRPH算法的性能測試，測試結(jié)果如圖7所示。

圖7 兩種算法不同增量和支持度時的性能對比

由圖7可知：

1)對于一定量的增量數(shù)據(jù)庫，IBRRPH算法相對于文獻[9]算法具有較高的效率。

2)支持度小于0.875時,IBRRPH算法的效率提高比較明顯(縱軸是算法運行時間,越低越好);而支持度大于0.875時，本文IBRRPH算法耗時稍多于文獻[9]算法。

3)因為處理增量數(shù)據(jù)庫的時間越來越多，IBRRPH算法的優(yōu)越性隨著增量數(shù)據(jù)庫規(guī)模的增大越來越不明顯。

4 結(jié)語

針對隱私保護的頻繁模式挖掘算法效率問題，通過引入基于bitmap技術(shù)和增量更新模型，本文提出了高效的隱私保護的頻繁模式挖掘新算法IBRRPH。引入bitmap技術(shù)將數(shù)據(jù)處理轉(zhuǎn)換為位與操作的模式，提高了算法的效率，然后以此為基礎(chǔ)，加入增量更新模型，使得算法在數(shù)據(jù)庫發(fā)生變化時具有更高效率。實驗結(jié)果表明，改進之后的算法BRRPH和IBRRPH相比文獻[9]的算法在效率上有了較大的提高。由于大數(shù)據(jù)本身多樣的數(shù)據(jù)類型和快速的數(shù)據(jù)流轉(zhuǎn)等特征，進一步的研究工作可以從以下幾個方面開展：如研究針對非布爾類型數(shù)據(jù)庫上的隱私保護挖掘算法以及研究數(shù)據(jù)水平式分布和數(shù)據(jù)垂直式分布的隱私保護的關(guān)聯(lián)規(guī)則挖掘算法等。

References)

[1] 王鑫,劉方愛.改進的多數(shù)據(jù)流協(xié)同頻繁項集挖掘算法[J].計算機應(yīng)用,2016,36(7):1988-1992.(WANG X, LIU F A. Improved algorithm for mining collaborative frequent itemsets in multiple data streams [J]. Journal of Computer Applications, 2016, 36(7): 1988-1992.).

[2] 宋健,許國艷,夭榮朋.基于差分隱私的數(shù)據(jù)匿名化隱私保護方法[J].計算機應(yīng)用,2016,36,(10):2753-2757.(SONG J, XU G Y, YAO R P. Anonymized data privacy protection method based on differential privacy [J]. Journal of Computer Applications, 2016, 36 (10): 2753-2757.)

[3] 馮登國,張敏,李昊.大數(shù)據(jù)安全與隱私保護[J].計算機學(xué)報,2014,37(1):246-255.(FENG D G, ZHANG M, LI H. Big data security and privacy protection [J]. Chinese Journal of Computers, 2014, 37(1): 246-255.)

[4] SHI H Y, JIANG C, DAI W R, et al. Secure Multi-Party Computation Grid Logistic Regression (SMAC-GLORE) [J]. BMC Medical Informatics and Decision Making, 2016, 16(3): 89.

[5] CHANG X Y, DENG D L, YUAN X X, et al. Experimental realization of an entanglement access network and secure multi-party computation [J]. Scientific Reports, 2016, 6: article no. 29453.

[6] BATMAZ Z, POLAT H. Randomization-based privacy-preserving frameworks for collaborative filtering [J]. Procedia Computer Science, 2016, 96: 33-42.

[7] 方煒煒，謝偉，黃宏博,等.基于隱私保護的序列模式挖掘[J].計算機科學(xué),2016,43(12):195-199.(FANG W W, XIE W, HUANG H B, et al. Sequential pattern mining based on privacy preserving [J]. Computer Science, 2016, 43(12): 195-199.)

[8] 張鵬,童云海,唐世渭,等.一種有效的隱私保護關(guān)聯(lián)規(guī)則挖掘方法[J].軟件學(xué)報,2006,17(8):1764-1774.(ZHANG P, TONG Y H, TANG S W, et al. An effective method for privacy preserving association rule mining [J]. Journal of Software, 2006, 17(8): 1764-1774.)

[9] 顧鋮,朱保平,張金康.一種改進的隱私保護關(guān)聯(lián)規(guī)則挖掘算法[J].南京航空航天大學(xué)學(xué)報,2015,47(1):119-124.(GU C, ZHU B P, ZHANG J K. Improved algorithm of privacy preserving association rule mining [J]. Journal of Nanjing University of Aeronautics & Astronautics, 2015, 47(1): 119-124.)

[10] 陳輝.一種基于位圖計算并行挖掘大數(shù)據(jù)頻繁模式算法[J].小型微型計算機系統(tǒng),2014,35(7):1599-1603.(CHEN H. Parallel mining frequent patterns in big data based on bitmap computation [J]. Journal of Chinese Computer Systems, 2014, 35(7): 1599-1603.)

[11] 肖晗,黃誠.基于量化關(guān)聯(lián)規(guī)則的敏感性分析[J].計算機應(yīng)用,2017,37(S1):255-257.(XIAO H, HUANG C. Analysis of sensitivity based on quantitative association rules [J]. Journal of Computer Applications, 2017, 37(S1): 255-257.)

[12] CHEUNG D W, HAN J W, NG V T, et al. Maintenance of discovered association rules in large databases: an incremental updating technique [C]// Proceedings of the 12th International Conference on Data Engineering. Piscataway, NJ: IEEE, 1996: 106-114.

This work is partially supported by the National Natural Science Foundation of China (61572019), the Key Project of Shaanxi Scientific Research Program (2016JZ001), the Key Laboratory Research Project of Education Bureau of Shaanxi Province (16JS078).

ZHANGYaling, born in 1966, Ph. D., professor. Her research interests include privacy-preserving, data mining.

WANGTing, born in 1990, M. S. candidate. Her research interests include privacy-preserving, data mining.

WANGShangping, born in 1963, Ph. D., professor. His research interests include cryptographic theory, privacy-preserving.