張亞玲，王 婷，王尚平

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

0 引言

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

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

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

1 RRPH算法及其改進(jìn)算法的分析

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

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

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

由于文獻(xiàn)[9]的改進(jìn)主要是針對RRPH算法的重構(gòu)支持度的改進(jìn)，該算法仍然需要完全的數(shù)據(jù)庫掃描以及呈指數(shù)級別增長的比較操作，因此算法的效率仍是制約該算法的關(guān)鍵問題。此外，文獻(xiàn)[8-9]都沒有考慮數(shù)據(jù)增量更新的問題。事實(shí)上，在大數(shù)據(jù)時(shí)代，每天會(huì)產(chǎn)生數(shù)以萬計(jì)的增量數(shù)據(jù)，這些增量數(shù)據(jù)很有可能對數(shù)據(jù)挖掘結(jié)果產(chǎn)生巨大的影響。具有增量更新性質(zhì)的隱私保護(hù)的頻繁模式挖掘算法更具有實(shí)際意義。本文將基于以上兩個(gè)問題，提出一種增量的基于位圖的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)取值，則定義在該模式上元組的真實(shí)取值范圍為U=D1×D2×…×Dn。

定義1 給定r是關(guān)系模式R上的任一關(guān)系，任一屬性Ai(1≤i≤n)在r上的真實(shí)取值范圍簡稱活動(dòng)域，表示為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)中任何一個(gè)可能值表示為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個(gè)元組，而r在Ai上的某一可能取值表示為c(c∈ADom(Ai))，則可以使用m位二進(jìn)制數(shù)來代表關(guān)系r在Ai上值為c的位置，稱此m位二進(jìn)制數(shù)為關(guān)系r中在Ai上值為c的bitmap，記為Bin(Ai,c)。如果ts是r中第s個(gè)元組，倘若ts∈F-1(c)，則Bin(Ai,c)中第s位的取值范圍為{0,1}。

定義4 假設(shè)任一關(guān)系r中包含N個(gè)元組，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的支持度計(jì)數(shù)表示為freq(P)=Count(Bin((A1,A2,…,Al),(c1,c2,…,cl)))，函數(shù)Count()表示bitmap中1的數(shù)量。假設(shè)最小支持度閾值為θ(0<θ<1)，當(dāng)freq(P)≥θN時(shí)，P是頻繁模式；否則P不是頻繁模式。

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

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

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

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

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

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

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

2.2 BRRPH算法

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

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

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

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

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

圖1 BRRPH的總體框架

2.3 IBRRPH算法原理

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

數(shù)據(jù)庫中所包含的數(shù)據(jù)并不是一成不變，而是會(huì)隨著時(shí)間的流逝而產(chǎn)生或大或小的變化，由于數(shù)據(jù)庫的更新，會(huì)引入新的關(guān)聯(lián)規(guī)則并使一些現(xiàn)有的關(guān)聯(lián)規(guī)則失效，頻繁項(xiàng)集也存在類似的更新問題。一般情況下，人們更專注于設(shè)計(jì)和研究隱私保護(hù)的關(guān)聯(lián)規(guī)則挖掘方面的相關(guān)算法，卻忽略了數(shù)據(jù)庫發(fā)現(xiàn)的規(guī)則只反映數(shù)據(jù)庫的當(dāng)前狀態(tài)這一事實(shí)。為了使揭露的規(guī)則穩(wěn)定可靠，應(yīng)在相當(dāng)長的一段時(shí)間內(nèi)收集大量數(shù)據(jù)。所以，在算法的設(shè)計(jì)中，要使研究更具有實(shí)際意義，不僅要關(guān)注與設(shè)計(jì)頻繁模式關(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)一個(gè)數(shù)據(jù)集D+增加到原來的數(shù)據(jù)庫中時(shí)，引入新的關(guān)聯(lián)規(guī)則并使一些現(xiàn)有的關(guān)聯(lián)規(guī)則[11]失效。本文在BRRPH算法的基礎(chǔ)上加入了增量更新技術(shù)，用于維護(hù)數(shù)據(jù)挖掘過程中發(fā)現(xiàn)的關(guān)聯(lián)規(guī)則。

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

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

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

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

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

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

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

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

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

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

2.3.2 IBRRPH算法

本文的IBRRPH算法是一個(gè)具有隱私保護(hù)機(jī)制特性的考慮增量更新的頻繁模式挖掘算法。IBRRPH算法的第一步即需要將新增的部分?jǐn)?shù)據(jù)庫進(jìn)行隱藏和變換；然后在經(jīng)過了隱私保護(hù)的數(shù)據(jù)集上進(jìn)行數(shù)據(jù)挖掘，計(jì)算得到候選項(xiàng)集的支持度之后，結(jié)合分治策略和逆矩陣的方法求出該候選項(xiàng)集在原始數(shù)據(jù)庫中估計(jì)的支持度；最后，得到新的數(shù)據(jù)庫中的頻繁項(xiàng)集，因此在IBRRPH算法中，增量之后的數(shù)據(jù)庫的支持度的值為該項(xiàng)集在原始數(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+中為頻繁項(xiàng)集，當(dāng)A∈L，那么A.supportD≥d×c，則A為頻繁項(xiàng)集。當(dāng)A?L，需要重新計(jì)算A.supportD+A.supportD+，看是否滿足A.supportD+A.supportD+≥supportD′。

如果A.supportD+

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

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

2.4 IBRRPH算法描述

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

輸出：L′，表示所有頻繁項(xiàng)集。

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

2)生成L1′，即數(shù)據(jù)庫D+D+的頻繁1項(xiàng)集，k=1。在這個(gè)過程中，原始數(shù)據(jù)庫D中的頻繁1項(xiàng)集是已知的。挖掘頻繁1項(xiàng)集的具體過程如算法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加入候選項(xiàng)集C中，并初始化支持度計(jì)數(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中的項(xiàng)集

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)方法為獲取項(xiàng)集A的真實(shí)支持度

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

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

//不需要的項(xiàng)目

2.5 IBRRPH算法挖掘準(zhǔn)確度分析

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

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

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

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

3.1 BRRPH算法實(shí)驗(yàn)與分析

3.1.1 性能分析

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

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

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

圖3 兩種算法在不同項(xiàng)集個(gè)數(shù)時(shí)的運(yùn)行時(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-項(xiàng)集所需時(shí)間對比如圖4所示。

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

3.1.2 準(zhǔn)確性分析

本實(shí)驗(yàn)將從支持度誤差和頻繁項(xiàng)集誤差兩個(gè)方面來分析算法的準(zhǔn)確性。

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

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

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

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

3.2 IBRRPH算法實(shí)驗(yàn)與分析

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

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

由圖7可知：

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

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

3)因?yàn)樘幚碓隽繑?shù)據(jù)庫的時(shí)間越來越多，IBRRPH算法的優(yōu)越性隨著增量數(shù)據(jù)庫規(guī)模的增大越來越不明顯。

4 結(jié)語

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

References)

[1] 王鑫,劉方愛.改進(jìn)的多數(shù)據(jù)流協(xié)同頻繁項(xiàng)集挖掘算法[J].計(jì)算機(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ù)匿名化隱私保護(hù)方法[J].計(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ù)安全與隱私保護(hù)[J].計(jì)算機(jī)學(xué)報(bào),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] 方煒煒，謝偉，黃宏博,等.基于隱私保護(hù)的序列模式挖掘[J].計(jì)算機(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] 張鵬,童云海,唐世渭,等.一種有效的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘方法[J].軟件學(xué)報(bào),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] 顧鋮,朱保平,張金康.一種改進(jìn)的隱私保護(hù)關(guān)聯(lián)規(guī)則挖掘算法[J].南京航空航天大學(xué)學(xué)報(bào),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] 陳輝.一種基于位圖計(jì)算并行挖掘大數(shù)據(jù)頻繁模式算法[J].小型微型計(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].計(jì)算機(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.