差分隱私的數(shù)據(jù)流關(guān)鍵模式挖掘方法?

王金艷,劉 陳,傅星珵,羅旭東,李先賢

1(廣西多源信息挖掘與安全重點實驗室(廣西師范大學),廣西 桂林 541004)2(廣西師范大學 計算機科學與信息工程學院,廣西 桂林 541004)

隨著大數(shù)據(jù)分析技術(shù)的發(fā)展,從數(shù)據(jù)流中挖掘頻繁模式有著廣泛的應(yīng)用,如生物信息學數(shù)據(jù)分析、網(wǎng)絡(luò)流量分析和 Web使用分析等多種在線應(yīng)用[1,2].然而,許多頻繁超集可以推導出與其子集重復的關(guān)聯(lián)規(guī)則.此外,當數(shù)據(jù)集是密集型或者最小支持度閾值較低時,挖掘出的頻繁模式會導致組合爆炸問題[3].因此,研究者們提出了閉合頻繁模式和最大頻繁模式等簡潔模式[4-6],其中使用最廣泛的是閉合頻繁模式,它是頻繁模式的一個有限子集,但包含了頻繁模式所有的非冗余信息[5].Das和 Zaniolo[7]提出一種被稱為關(guān)鍵模式的簡潔模式,并證明了它是閉合頻繁模式的有效子集.關(guān)鍵模式需要更少的存儲空間,并且可以高效無損地提取頻繁模式.因此,事務(wù)數(shù)據(jù)流環(huán)境下更適合挖掘最簡潔的關(guān)鍵模式.然而,當事務(wù)數(shù)據(jù)流含有個人的敏感信息時(如顧客的購買記錄、用戶的行為記錄等),直接發(fā)布挖掘的統(tǒng)計信息會給數(shù)據(jù)流中的個人隱私帶來很大的威脅[8].顯然,數(shù)據(jù)流連續(xù)窗口定期發(fā)布統(tǒng)計信息比靜態(tài)情況下泄漏隱私更為嚴重:一方面,如果我們將每個滑動窗口視為靜態(tài)數(shù)據(jù)集,那每個窗口的隱私泄漏程度則與靜態(tài)數(shù)據(jù)相同;另一方面,由于相鄰時間戳中的數(shù)據(jù)具有相關(guān)性,所以連續(xù)發(fā)布相鄰窗口的統(tǒng)計信息會增強攻擊者的推理能力.因此,攻擊者需要更少的背景知識就可以推斷出目標的敏感信息.

圖1的實例表明,連續(xù)發(fā)布數(shù)據(jù)流上挖掘出的關(guān)鍵模式將導致隱私泄露問題.假設(shè)圖1(a)數(shù)據(jù)流中的事務(wù)代表病人在某醫(yī)院的購藥記錄,最小支持度閾值為2;圖1(b)中的兩個關(guān)鍵模式統(tǒng)計信息分別表示了從圖1(a)的第1個窗口和第2個窗口挖掘出的關(guān)鍵模式集.假設(shè)攻擊者的背景知識為知道Mike是數(shù)據(jù)流中的第3條記錄并且患有艾滋病,那么他/她想知道Alice是否患有艾滋病.顯然,攻擊者可以從圖1(b)中所示的統(tǒng)計信息得出,用于治療艾滋的藥物a和b的計數(shù)在第1個窗口中為2,而在第2個窗口中小于2.這樣,他/她只需要知道Coco的信息就可以推斷出Alice是否患有艾滋病.

Fig.1 A sliding window example with window size=2 and pane size=2圖1 窗口大小為2窗格大小為2的數(shù)據(jù)流滑動窗口模型

目前,差分隱私[9]已經(jīng)成為一種廣泛應(yīng)用的隱私保護模型,它能提供嚴格的理論證明,而且不需要假設(shè)攻擊者的背景知識.迄今為止,關(guān)于差分隱私頻繁模式挖掘的研究主要集中在靜態(tài)場景[10-16],而現(xiàn)有的關(guān)于數(shù)據(jù)流下差分隱私的研究僅限于構(gòu)成數(shù)據(jù)流的元組是數(shù)值或者分類值的情況[17-23].據(jù)掌握的資料來看,尚未有差分隱私的工作研究數(shù)據(jù)流上關(guān)鍵模式的挖掘這類更復雜的挖掘任務(wù).此外,上述靜態(tài)場景中的差分隱私頻繁模式挖掘方法不適用于數(shù)據(jù)流上保護用戶隱私的關(guān)鍵模式挖掘:一方面,靜態(tài)場景下的這些方法需要對整個數(shù)據(jù)集進行多次掃描,而數(shù)據(jù)流的動態(tài)性要求算法只能對傳入的數(shù)據(jù)掃描一次并提供實時響應(yīng);另一方面,現(xiàn)有的靜態(tài)場景下的研究大多傾向于挖掘少量的 top-k個頻繁模式,這樣并不能得到所有頻繁模式的完整信息.針對上述問題,本文提出了一種差分隱私關(guān)鍵模式挖掘算法DP-CPM,實現(xiàn)從事務(wù)數(shù)據(jù)流中挖掘滿足差分隱私的關(guān)鍵模式.

為了考慮隱私和數(shù)據(jù)效用之間以及挖掘時間與維護成本之間的權(quán)衡,DP-CPM 算法在每個時間戳設(shè)計一種兩階段機制:差異計算階段和噪音挖掘階段.在差異計算階段,為了防止一個窗口中包含的w個時間戳分配的隱私預算之和超過總預算,我們首先檢查當前的時間戳是否需要強制近似.如果當前時間戳隱私預算足夠不需要強制近似,則改進Das和Zaniolo[7]提出的關(guān)鍵模式挖掘算法,先構(gòu)造當前滑動窗口的前綴樹Ti,并調(diào)整Ti使其更加緊湊,然后通過調(diào)用關(guān)鍵模式計算算法 CPC[7]從當前滑動窗口中挖掘出準確的關(guān)鍵模式集CPi.最后計算CPi與最近的隱私發(fā)布Ot(Ot∈(O1,…,Oi-1))之間的差異disi,然后根據(jù)差異disi決定當前時間戳是進入噪音挖掘階段返回低噪音統(tǒng)計值還是直接返回精確的近似統(tǒng)計值.在噪音挖掘階段,我們設(shè)計了兩步順序加噪方法來獲得隱私的關(guān)鍵模式及其噪音支持度.通過隱私分析,證明了DP-CPM算法滿足εi-差分隱私,并且預算吸收策略滿足w-event隱私.在密集和稀疏數(shù)據(jù)集上的大量實驗結(jié)果表明:DP-CPM算法不僅提高了隱私和數(shù)據(jù)效用之間的權(quán)衡,而且還提高了挖掘時間和維護成本之間的權(quán)衡.

本文的主要貢獻如下:

1) 首次討論在數(shù)據(jù)流上挖掘關(guān)鍵模式存在的隱私問題,并指出由于連續(xù)時間戳的發(fā)布可作為背景知識增強了攻擊者的推斷能力,所以動態(tài)數(shù)據(jù)流上挖掘的隱私泄漏比靜態(tài)場景更嚴重;

2) 為了解決隱私問題,根據(jù)關(guān)鍵模式的性質(zhì)設(shè)計了兩步順序加噪方法來發(fā)布隱私的關(guān)鍵模式及其噪音支持度;

3) 為了對一個窗口內(nèi)所包含的w個時間戳進行合理的隱私預算分配,我們在每個時間戳設(shè)計了一種兩階段機制;

4) 通過隱私分析證明了 DP-CPM 算法滿足εi-差分隱私;并且在密集和稀疏數(shù)據(jù)集上的大量實驗也表明了DP-CPM算法的效用性和執(zhí)行效率.

本文第 1節(jié)對相關(guān)工作進行討論,并說明我們的工作與現(xiàn)有工作的不同.第 2節(jié)介紹全文所涉及的符號以及差分隱私和關(guān)鍵模式挖掘算法.第3節(jié)首先詳細描述DP-CPM算法以及兩個關(guān)鍵技術(shù),然后證明DP-CPM算法滿足εi-差分隱私,最后證明預算吸收策略滿足w-event隱私.第4節(jié)給出實驗結(jié)果分析.最后,第5節(jié)對本文進行總結(jié),并給出下一步研究工作.

1 相關(guān)工作

本節(jié)從靜態(tài)環(huán)境下滿足差分隱私的頻繁模式挖掘方法、數(shù)據(jù)流中精確頻繁模式挖掘方法和數(shù)據(jù)流下滿足差分隱私的數(shù)據(jù)發(fā)布方法這3個與本文直接相關(guān)的方面闡述現(xiàn)有的研究工作,并指出我們方法與其不同之處.

1.1 靜態(tài)環(huán)境下滿足差分隱私的頻繁模式挖掘方法

從靜態(tài)數(shù)據(jù)集中挖掘滿足差分隱私的頻繁模式的方法有很多,這些方法都是基于經(jīng)典的 Apriori[24]和 FP-growth[15]算法設(shè)計的.例如,Bhaskar等人[10]采用指數(shù)機制[25]和拉普拉斯機制[26]提出了兩種不同的差分隱私頻繁模式挖掘算法.這兩種方法通過截斷頻率來挖掘隱私的top-k個頻繁模式,盡管截斷頻率有效地減少了候選集的大小,但當用戶定義的最終輸出模式的數(shù)目k或事務(wù)的最大長度限制l很大時,這些方法的效率和性能就會降低.為了解決事務(wù)數(shù)據(jù)庫維度較高的困難,Li等人[11]結(jié)合θ-基和投影技術(shù)提出了Privbasis方法,該方法首先挖掘出所有的頻繁模式,然后從中識別出最頻繁的模式對,根據(jù)這些模式對構(gòu)造θ-基集合B,最后為θ-基集合B產(chǎn)生的頻繁模式候選集C(B)里的每個模式的支持度添加隨機拉普拉斯噪音.為了應(yīng)對 Privbasis造成的數(shù)據(jù)效用損失過高的問題,Lee等人[12]表明:閾值查詢集相比于計數(shù)查詢集而言,可以結(jié)合前綴樹的效用性和緊湊性來修剪候選集,進而提高數(shù)據(jù)效用性.然而,該方法不適用于k很大的情況.Zhang等人[13]提出了DP-top-kP方法,該方法處理噪音支持度時,通過后處理步驟來保持一致性.同樣,該方法無法處理k或l很大的情況.由于直接截斷事務(wù)會導致信息損失量太大,Sen等人[14,15]指出:在處理事務(wù)長度約束時,拆分比截斷能夠保留更多的有用信息.因此,他們分別基于 Apriori[24]和 FP-growth[15]設(shè)計了兩種分割算法.這兩個方法的主要思想是:如果事務(wù)長度大于最大長度限制l,則采用加權(quán)分裂方法將其劃分為多個子集,最終每個子集的長度都在限制范圍內(nèi)并且更好地保留了原始事務(wù)包含頻繁模式的結(jié)構(gòu).但是,事務(wù)拆分技術(shù)只適用于包含大量短事務(wù)的數(shù)據(jù)集.Ning等人[16]提出一種新的算法 Privsuper,該算法與以往的差分隱私頻繁模式挖掘算法從頻繁單個模式開始相反,它采用超集優(yōu)先的方法,僅在最大頻繁模式的支持度中加入噪音來獲得所有的隱私頻繁模式,從而大大減少了噪音的加入.

為了解決全局敏感性高的問題,DP-CPM 算法首先通過一個判斷查詢集在不考慮候選集大小的前提下從所有模式中篩選出關(guān)鍵模式候選集,然后對候選集中的每個關(guān)鍵模式的支持度加入隨機拉普拉斯噪音.同時,我們挖掘的是關(guān)鍵模式,既能解決只挖top-k帶來的模式損失的問題,又能解決挖掘全部頻繁模式帶來的組合爆炸和冗余問題.

1.2 數(shù)據(jù)流中精確頻繁模式挖掘方法

現(xiàn)有的研究大都集中在不考慮隱私的情況下從事務(wù)數(shù)據(jù)流中挖掘精確的頻繁模式.Leung等人[27,28]基于FP-tree提出了CanTree和DSTree兩種方法.為了滿足數(shù)據(jù)流一次掃描的限制,他們把掃描進的新事務(wù)按照字典順序插入到前綴樹中.然而,這樣構(gòu)造的前綴樹不具有像FP-tree一樣的緊湊性,從而導致挖掘效率較低.Mozafari等人[29]提出了SWIM算法,該算法采用快速計數(shù)技術(shù)減少挖掘時間,但是當前綴樹的尺寸較大時,該算法的性能無法令人滿意.Tanbil等人[1]提出了一種 CPS-Tree,該方法同樣按字典順序?qū)呙璧男率聞?wù)插入到前綴樹,然后再按照降序?qū)η熬Y樹進行重構(gòu).然而在這種情況下,因為需要在每個滑動窗口都完全按降序重構(gòu)前綴樹,這就會帶來相當大的維護開銷.由于在事務(wù)數(shù)據(jù)流上挖掘頻繁模式會產(chǎn)生能推出冗余關(guān)聯(lián)規(guī)則的頻繁子集和頻繁超集,所以一些研究更傾向于在事務(wù)數(shù)據(jù)流上挖掘頻繁模式的有限子集[7,30,31],這些簡潔的模式包括閉合頻繁模式、最大頻繁模式和關(guān)鍵模式等.一些研究[30,31]強調(diào):當新的事務(wù)到達時,它們一方面只需要對已有的節(jié)點的支持度進行相應(yīng)的更新,另一方面需要從新的分支中挖掘新的模式.其中,Chi等人[30]提出一種內(nèi)存閉合枚舉樹方法,該方法可以有效地監(jiān)視數(shù)據(jù)流上的閉合頻繁模式.最近,Das和Zaniolo[7]提出在數(shù)據(jù)流中挖掘關(guān)鍵模式,并且提高了之前研究中挖掘時間和維護開銷的權(quán)衡.該算法的主要思想是:采用兩種排序方案對新掃描的事務(wù)進行排序,即:對“一次性頻繁”的項采取已有的順序(?est)排序,而對“仍然不頻繁”的項采取降序(?desc)排序.因為他們認為,隨著窗口的滑動,“仍然不頻繁”的項的相對順序會發(fā)生改變,而“一次性頻繁”的項不用考慮.換句話說,對于窗口滑動導致頻繁項變得不頻繁時,他們會保留這樣的垃圾節(jié)點,直到這些垃圾節(jié)點在頻繁節(jié)點中占一定比例才完全重建樹.

本文也采用了兩種排序方案對新掃描進的事務(wù)進行排序.我們的方法與文獻[7]的不同之處在于:隨著窗口的滑動,我們不僅將新的頻繁節(jié)點冒泡到已有的順序(?est)中,而且還從已有的順序(?est)中去掉了由頻繁變得不頻繁的垃圾節(jié)點,因為差分隱私關(guān)鍵模式算法的性能會受前綴樹的緊湊性影響,并且垃圾節(jié)點在加噪后也有可能成為關(guān)鍵節(jié)點,干擾了關(guān)鍵模式的候選集的篩選.

1.3 數(shù)據(jù)流下滿足差分隱私的數(shù)據(jù)發(fā)布方法

近年來,數(shù)據(jù)流下滿足差分隱私的數(shù)據(jù)發(fā)布研究大多局限于輸入記錄是數(shù)值或分類值的情況[32].Dwork[17]在計數(shù)中添加Lap(1/ε)的拉普拉斯噪音,但是這種方法在稀疏數(shù)據(jù)中是無效的.Chan等人[18]考慮在分布式場景下使用不可信聚合器持續(xù)監(jiān)測多條流,他們希望保證每個流的隱私,同時允許不可信的聚合器準確地檢測事件及其近似頻率.但該方法只檢測是否超過閾值并不發(fā)布具體的統(tǒng)計值.Bolot等人[19]考慮最近的數(shù)據(jù)比過去的數(shù)據(jù)更重要,使用衰減窗口來處理數(shù)據(jù)流.Fan等人[20]利用滑動窗口模型提出了 FAST方法,該方法包含若干個子機制,且每個子機制都處理一個包含w個時間戳的不相交的窗口.因此,他們給每個子機制分配ε/2的隱私預算,并將每個子機制包含的子序列當成長度為w的有限流來處理.此外,該方法根據(jù)預先指定的數(shù)目進行抽樣,對抽樣的時間戳進行發(fā)布,對跳過的時間戳直接根據(jù)抽樣的結(jié)果近似.然而,該方法的預算分配取決于樣本的數(shù)量和流的長度,所以它不適合無限流.Cao等人[21]先在時域內(nèi)指定一組范圍查詢,其中每個查詢請求更新的和,這樣做的目的是,通過使用較小子區(qū)間的噪音回答來響應(yīng)較大范圍的查詢.為了合理地分配隱私預算,進一步提高數(shù)據(jù)發(fā)布的效用性,Kellaris等人[22]在二進制流上提出了兩種隱私分配策略來保護任意w個連續(xù)時間戳的事件序列的隱私.為了實現(xiàn)滑動窗口中w個連續(xù)時間戳的隱私發(fā)布,該方法計算當前時間戳的精確統(tǒng)計值與最近一個隱私時間戳的噪音發(fā)布值之間的差異,然后根據(jù)這個差異決定當前時間戳是返回低噪音統(tǒng)計值還是精確的近似統(tǒng)計值.Zhang等人[23]提出一種自適應(yīng)采樣技術(shù)來實現(xiàn)連續(xù)時間戳的隱私直方圖發(fā)布,該方法的主要思想是:當預測值和準確值的差值小于一定閾值時,發(fā)布預測值;否則,需要添加隨機噪音來發(fā)布隱私值.

本文研究復雜事務(wù)數(shù)據(jù)流上滿足差分隱私的關(guān)鍵模式挖掘方法.為了合理分配隱私預算,我們也采用了差異的計算來決定當前時間戳是返回低噪音統(tǒng)計值還是精確的近似統(tǒng)計值,與Kellaris等人[22]在二進制流中使用的方法不同之處在于噪音規(guī)模.在二進制流中,只需要對計數(shù)添加Lap(1/ε)的噪音,因為添加或刪除一個用戶最多只影響計數(shù)為 1.而在我們考慮的事務(wù)數(shù)據(jù)流中,添加或刪除一條事務(wù)會影響查詢集里多個模式的支持度.具體的加噪細節(jié)將在第3節(jié)給出.

綜上所述,與現(xiàn)有的靜態(tài)下頻繁模式隱私保護方法不同,本文考慮先使用判斷查詢集擾動關(guān)鍵模式再對候選集中模式的支持度進行加噪來提高數(shù)據(jù)效用與隱私的權(quán)衡.我們挖掘的關(guān)鍵模式是頻繁模式的最佳無損子集,更加適合數(shù)據(jù)流實時動態(tài)的特性.另一方面,對于已有的數(shù)據(jù)流下快速挖掘頻繁模式的相關(guān)研究,通常會犧牲一定的緊湊性來提高連續(xù)挖掘的效率,而本文首次考慮數(shù)據(jù)流下連續(xù)挖掘關(guān)鍵模式的隱私問題,所以為了提高數(shù)據(jù)效用性,我們提出了前綴樹調(diào)整方法,保證在挖掘滿足差分隱私的關(guān)鍵模式之前盡可能提高樹的緊湊性.最后,本文研究的是復雜事務(wù)數(shù)據(jù)流,與已有的簡單的二進制流下加噪不同,我們需要考慮不同的噪音規(guī)模.

2 預備知識

2.1 基本概念

給定字母表I={i1,...,in},S是由事務(wù)ti構(gòu)成的事務(wù)數(shù)據(jù)流,其中,ti?I.本文使用圖1所示的滑動窗口模型[33]來處理事務(wù)數(shù)據(jù)流.滑動窗口模型只對當前數(shù)據(jù)感興趣.在滑動窗口模型中,挖掘算法僅維護并挖掘固定寬度為w的當前窗口中的關(guān)鍵模式,每個滑動窗口包含[i-w+1,i]個時間戳的連續(xù)子窗口序列,我們稱這些子窗口為窗格,且每個窗格固定寬度為p,即一個滑動窗口包含w個窗格,每個窗格包含p條事務(wù).當時間戳過期,超出了當前滑動窗口時,需要刪除過期的窗格徹底消除它對當前挖掘結(jié)果的影響.當時間戳前進,我們需要把新到達的窗格加入,挖掘新滑動窗口的關(guān)鍵模式.圖1給出了一個事務(wù)數(shù)據(jù)流和兩個連續(xù)的滑動窗口,每個窗口包含兩個窗格,每個窗格包含兩條事物.

設(shè)supp(W)表示一個滑動窗口W中模式P的支持度,即W中包含P的事務(wù)條數(shù).給定最小支持度閾值τ,當一個模式P滿足supp(W)≥τ時,則稱P是滑動窗口W中的頻繁模式.本文使用的符號描述見表1.

Table 1 Notations表1 標記

接下來介紹關(guān)鍵模式的相關(guān)概念.分支號[7]是分配給前綴樹中包含頻繁項的節(jié)點的唯一標簽,分配條件是:(i) 如果一個節(jié)點是葉子節(jié)點;或者(ii) 如果一個非葉子節(jié)點的支持度大于其所有孩子節(jié)點的支持度之和.有效分支號組合[7]表示一個模式分支號的集合,例如,集合{1,2}是圖2中模式ab的有效分支號組合.如果一個頻繁模式的有效分支號組合里至少有一個分支號沒有出現(xiàn)在該模式的任何頻繁超集的有效分支號組合中,就稱該頻繁模式為關(guān)鍵模式[7],例如,圖2中的h,ab,bh是第1個窗口挖掘出的所有關(guān)鍵模式.

Fig.2 A set enumeration tree of the first window whenτ=2圖2 最小支持度閾值為2時第1個窗口的集合枚舉樹

2.2 差分隱私保護模型

Dwork在2006年提出了差分隱私模型[9],該模型有兩大優(yōu)勢:(1) 定義了相當嚴格的攻擊模型,不需要假設(shè)攻擊者的背景知識;(2) 對隱私保護水平給出了嚴格的理論證明和量化方法.

給定最多相差一條記錄的鄰居數(shù)據(jù)集D和D′,差分隱私確保更改輸入數(shù)據(jù)庫中的單個記錄不會影響任何查詢的輸出結(jié)果,從而達到隱私保護的目的.差分隱私的形式化定義如下:

定義1(ε-差分隱私[9]).對于所有相差一條記錄的鄰居數(shù)據(jù)集D和D′,給定隱私算法M,若對于所有輸出O∈Range(M)都滿足下列不等式,則算法M滿足ε-差分隱私:

其中,參數(shù)ε是隱私保護預算,用來決定隱私保護的程度.

定義2(w-鄰居流前綴[22]).給定一個正整數(shù)w,如果兩個流前綴′滿足:(i) 對于每個都有是相鄰的;(ii) 對于每個都有i2-i1+1≤w,則稱流前綴是w-鄰居流前綴.

定義3(w-event隱私[22]).對于所有w-鄰居流前綴′,給定一個機制M,若對于所有輸出O∈Range(M)都滿足下列不等式,則M滿足w-event隱私:

噪音機制是用來實現(xiàn)差分隱私的主要技術(shù),其中,基于機制且滿足差分隱私算法所需要的噪音大小與全局敏感性[9]密切相關(guān).

定義4(全局敏感性[9]).對于任意一個函數(shù)f:D→Rd,函數(shù)f的全局敏感性為:

其中,D和D′為相差一條記錄的鄰居數(shù)據(jù)集,d表示函數(shù)f的查詢維度,R表示所映射的實數(shù)空間.全局敏感性只與查詢函數(shù)本身有關(guān).

最常用的噪音機制是拉普拉斯機制[26],該機制通過拉普拉斯分布產(chǎn)生的噪音去擾動真實的結(jié)果值,以達到隱私保護的目的.

定理1(拉普拉斯機制[26]).對于任意一個函數(shù)f:D→Rd,若算法M的輸出結(jié)果滿足下列等式,則算法M滿足ε-差分隱私:

其中,Lapi(Δf/ε)(1≤i≤d)是相互獨立的拉普拉斯變量,噪音規(guī)模與Δf成正比,與ε成反比,即:函數(shù)f的全局敏感性越大,所需的噪音越多.

通常,一個實際的問題都需要多個隱私算法組合實現(xiàn),這就需要用到差分隱私的序列組合性[34].

定理2(序列組合性[34]).給定數(shù)據(jù)庫D,設(shè)Mi為任意一個隨機算法(1≤i≤n)滿足εi-差分隱私,則算法Mi在D上的順序操作滿足差分隱私.

2.3 關(guān)鍵模式挖掘算法

下面描述基于FP-growth[15]的數(shù)據(jù)流關(guān)鍵模式挖掘[7]的過程.如圖3中的前綴樹所示,Das和Zaniolo[7]在每個節(jié)點上都用一個數(shù)組分別存儲單個窗格項的支持度,這樣有利于窗口滑動的更新.在第 1個窗口,他們先按照字典順序?qū)呙璧降氖聞?wù)插入到樹中構(gòu)造當前窗口的前綴樹,然后按照降序來調(diào)整前綴樹更加緊湊,一旦得到調(diào)整好的前綴樹,就根據(jù)分支號分配條件給樹中的節(jié)點分配分支號.接下來根據(jù)條件模式基得到如圖2所示的集合枚舉樹,最后調(diào)用關(guān)鍵模式計算算法CPC[7]從集合枚舉樹中識別出關(guān)鍵模式.

Fig.3 Tree with branch IDs at the first window圖3 第1個窗口帶有分支號的前綴樹

對于后續(xù)的窗口滑動,采用前綴樹的增量維護來減少每個窗口完全重建樹的操作.一旦窗口滑動,一方面只需要相應(yīng)地更新已有節(jié)點存儲項的支持度的數(shù)組;另一方面,對于新來的分支,則按照前一時間戳項頭表的順序插入到前綴樹.例如,圖4就是由圖3窗口滑動得到的.因為挖掘算法的性能與包含頻繁項的子樹的緊湊性密切相關(guān),因此他們采用兩種排序方式來提高挖掘時間和維護成本的權(quán)衡.對于新掃描進的事務(wù),他們將“一次性頻繁”的項按照已有的順序(?est)排序,而把“一直不頻繁”的項按照降序(?desc)進行排序.窗口滑動一般會面臨兩種情況:(i) 頻繁的項變得不頻繁;(ii) 不頻繁的項變得頻繁.對于情況(i),不采取任何行動;而對于情況(ii),一旦?desc中有不頻繁的項變得頻繁,則使用冒泡法將這些項冒泡到?est里,并從這些新的頻繁節(jié)點所在分支挖掘新的關(guān)鍵模式.

Fig.4 Tree with branch IDs at the second window圖4 第2個窗口帶有分支號的前綴樹

3 DP-CPM算法

本節(jié)介紹基于差分隱私的數(shù)據(jù)流關(guān)鍵模式挖掘算法 DP-CPM,用來實現(xiàn)事務(wù)數(shù)據(jù)流上關(guān)鍵模式的隱私發(fā)布.在第3.1節(jié),受Kellaris[22]在二進制流上提出的預算吸收的啟發(fā),我們提出了作用在每個時間戳的兩階段機制Mi.第3.2節(jié)提出實現(xiàn)數(shù)據(jù)流上滿足差分隱私的關(guān)鍵模式挖掘算法DP-CPM的兩個子算法.一方面,為了提高挖掘算法的性能和數(shù)據(jù)效用性,我們提出了維護緊湊的前綴樹算法來獲得更緊湊的前綴樹;另一方面,為了提高隱私和數(shù)據(jù)效用之間的權(quán)衡,我們提出了擾動關(guān)鍵模式候選集算法,該算法受NoisyCut算法[12]中的l-閾值查詢集的啟發(fā),利用判斷查詢集從所有模式中篩選出關(guān)鍵模式候選集.第 3.3節(jié)先證明了擾動關(guān)鍵模式候選集算法滿足εi.1-差分隱私,再根據(jù)差分隱私的序列組合性證明 DP-CPM 算法滿足εi-差分隱私,最后,證明預算吸收策略滿足w-event隱私.

3.1 兩階段機制

兩階段機制由差異計算階段和噪音挖掘階段組成,不僅考慮了隱私和數(shù)據(jù)效用之間的權(quán)衡,而且考慮了挖掘時間和維護成本之間的權(quán)衡.在第1階段,我們計算當前時間戳的準確關(guān)鍵模式集CPi和最近的噪音時間戳的隱私發(fā)布Ot之間的差異.在時間戳i我們需要區(qū)分兩種情況:(i) 如果之前的時間戳已經(jīng)吸收了隱私預算,則為了滿足差分隱私的序列組合性,εi必須強制為 0,在這種情況下,當前時間戳直接用Ot來近似發(fā)布Oi;(ii) 如果之前的時間戳隱私預算沒使用,則εi吸收之前跳過的隱私預算,在這種情況下,我們根據(jù)計算差異進一步?jīng)Q定當前時間戳是返回低噪音統(tǒng)計值還是返回準確的近似值.

第i個時間戳的兩階段機制Mi如圖5所示,可以看出Mi又分成兩個子機制Mi.1和Mi.2,這兩個子機制獨立且按順序執(zhí)行.其中,Mi.1先檢查時間戳i是否必須強制近似,如果不需要強制近似,就調(diào)用CPC算法[7]挖掘精確的關(guān)鍵模式集CPi,然后根據(jù)CPi和Ot計算當前時間戳的差異disi.這個差異用來判斷當前時間戳是使用隱私預算加噪合適還是使用最近的隱私發(fā)布來近似合適.接下來,Mi.2首先使用判斷查詢集從所有模式中篩選出關(guān)鍵模式候選集,然后調(diào)用 CPC算法[7]從擾動過的前綴樹中挖掘出關(guān)鍵模式,最后給篩選出的關(guān)鍵模式候選集里的每個模式的支持度添加隨機的拉普拉斯噪音.

Fig.5 Internal mechanics ofMi圖5 兩階段機制Mi的內(nèi)部構(gòu)造

· 差異計算階段

算法1的第1部分給出了差異計算階段的偽代碼.一開始,DP-CPM算法先檢查之前的隱私預算是否足夠被最近的噪音時間戳吸收,根據(jù)最近的噪音時間戳的隱私發(fā)布Ot和它所使用的隱私預算εt,用εt除以一個窗口內(nèi)w個時間戳平均分得的隱私預算再減去 1,就可以得到被εt吸收了的時間戳的個數(shù)(即tonullify)(第 2行),因此,如果i-t＜tonullify,則說明隱私預算不夠(第3行),所以DP-CPM算法需要強制εi為0,并用Ot來近似Oi(第4行).相反,如果隱私預算足夠的話,εi則吸收之前跳過的隱私預算(第5行～第7行).βi是用來與差異disi進行比較的拉普拉斯噪音分布的標準差[23](第 8行).因為前綴樹的緊湊性決定了關(guān)鍵模式挖掘算法的性能,所以 DP-CPM 算法調(diào)用維護緊湊的前綴樹算法得到緊湊的前綴樹′(第9行).接下來,DP-CPM算法調(diào)用CPC算法[7]挖掘CPi(第10行).根據(jù)CPi,我們計算出CPi和Ot之間的差異disi(第11行).一方面,如果disi＞βi,則需要進入噪音挖掘階段使用隱私預算去挖掘當前時間戳的隱私關(guān)鍵模式(第12行～第14行);否則,DP-CPM算法直接用Ot來近似Oi(第15行、第16行).

差異計算階段主要設(shè)計了一個公式來計算當前時間戳的精確關(guān)鍵模式集CPi和最近的噪音時間戳的隱私發(fā)布Ot之間的差異(即disi),因為需要計算兩個集合里所包含模式支持度上的差異,所以要遞歸檢查|Ot∪CPi|個模式支持度的變化,最終計算出模式支持度總差異值的均值來與計數(shù)查詢的拉普拉斯標準差進行比較.

· 噪音挖掘階段

算法1中的噪音挖掘函數(shù)對應(yīng)子機制Mi.2的偽代碼(第17行).首先,DP-CPM算法調(diào)用擾動關(guān)鍵模式候選集算法得到擾亂的關(guān)鍵模式候選集Ci(第19行);然后,DP-CPM算法給Ci里的每個模式的支持度添加:

噪音得到最終的噪音支持度(第20行、第21行).

算法1.DP-CPM:關(guān)鍵模式隱私挖掘算法.

輸入:前綴樹Ti,排好序的項頭表Li′,當前時間戳的隱私預算前綴(ε1,…,εi-1),之前的統(tǒng)計發(fā)布(O1,…,Oi-1);

輸出:當前時間戳的統(tǒng)計發(fā)布Oi.

算法 1(DP-CPM 算法)作為每個時間戳的總算法,調(diào)用了維護緊湊的前綴樹和擾動關(guān)鍵模式候選集兩個子算法,經(jīng)過分析可知:DP-CPM 算法的時間復雜度就是兩個子算法時間復雜度的較大值,也是O(n2);而空間復雜度為O(max(|Oi|,|Ot|)+6+|CPi|+(1+|V|)n+|I|),其中,n為前綴樹的規(guī)模,|Oi|,|Ot|和|CPi|分別為時間戳i發(fā)布的關(guān)鍵模式集大小、離當前時間戳i最近的噪音時間戳的隱私發(fā)布集大小以及時間戳i挖掘的精確關(guān)鍵模式集的大小.|V|為每個節(jié)點有效分支號組合的大小,|I|為項頭表Li′的大小.因為DP-CPM算法在第2行、第6行～第8行、第11行以及第9行調(diào)用的維護緊湊的前綴樹算法里的排序操作都需要消耗一個內(nèi)存空間,所以空間復雜度為O(6);并且算法1分兩種情況輸出,所以輸出的空間復雜度為O(max(|Oi|,|Ot|)).第9行調(diào)用維護緊湊的前綴樹算法不僅需要一個內(nèi)存空間來存儲節(jié)點信息和一個數(shù)組來存儲該節(jié)點的分支號組合V,還需要|I|個內(nèi)存空間存儲項頭表,所以前綴樹的空間復雜度為O((1+|V|)n+|I|);第10行消耗|CPi|個內(nèi)存空間.

3.2 子算法描述

3.2.1 維護緊湊的前綴樹算法

因為挖掘算法的性能取決于前綴樹的緊湊性,所以我們需要對前綴樹進行調(diào)整使其更緊湊.給定一個原始前綴樹Ti和一個按兩種排序方式排好序的項頭表Li′,算法 2首先遞歸檢查項頭表中的每個元素來獲得可能挖掘出關(guān)鍵模式的所有路徑集PathArrayi(第2行～第7行).對于PathArrayi中的每條路徑,維護緊湊的前綴樹算法遞歸檢查路徑中的每個節(jié)點Nk(第9行、第10行).如果節(jié)點Nk中包含的項在樹Ti′中已經(jīng)存在節(jié)點包含相同的項,則直接將Nk的支持度添加到已有的那個節(jié)點支持度上(第11行、第12行);否則,需要將Nk插入到前綴樹iT′中(第9行、第10行).一旦一條新路徑插入完成,維護緊湊的前綴樹算法根據(jù)分支號分配條件給路徑中的節(jié)點分配新的分支號(第13行、第14行).我們提出了一個時間復雜度為O(n2)、空間復雜度為O((1+|V|)n+|I|+1)的維護緊湊的前綴樹算法,以犧牲一定的空間來降低查詢時間的開銷,以達到提高效率的目的.其中,n表示前綴樹的規(guī)模.因為算法 2先遍歷原始樹中每條路徑的每個節(jié)點并需要查找該節(jié)點對應(yīng)的項是否已經(jīng)存在于排好序的前綴樹中,所以時間復雜度為O(n2).而算法2使用C#編程實現(xiàn),對于前綴樹里的每個節(jié)點,不僅需要一個內(nèi)存空間來存儲節(jié)點信息,還需要分配一個數(shù)組來存儲該節(jié)點的分支號組合V,所以前綴樹的空間復雜度為O((1+|V|)n);而且前綴樹所對應(yīng)的項頭表Li′也需要一個大小為|I|的數(shù)組來存儲,空間復雜度為O(|I|);最后還需要消耗一個內(nèi)存空間來存儲當前節(jié)點對應(yīng)的項用于后面步驟去樹中進行查找匹配操作.綜上所述,算法 2的空間復雜度為O((1+|V|)n+|I|+1).

算法2.維護緊湊的前綴樹算法.

輸入:原始前綴樹Ti,排好序的項頭表′;

正如第1.2節(jié)所述,現(xiàn)有的數(shù)據(jù)流精確頻繁模式挖掘方法中,通常采用PathAdjustingMethod[7]來調(diào)整前綴樹的緊湊性.與本文提出的維護緊湊的前綴樹算法不同:在不考慮隱私泄露的數(shù)據(jù)流精確頻繁模式挖掘時,為了提高挖掘效率,通常通過保留垃圾節(jié)點(支持度不滿足最小支持度閾值)以犧牲緊湊性為前提來減少樹的調(diào)整工作;而本文的維護緊湊的前綴樹算法第 1次考慮到數(shù)據(jù)流關(guān)鍵模式挖掘中的隱私泄露問題,所以需要通過維護緊湊的前綴樹算法,在保證一定效率的前提下,盡可能維護最緊湊的前綴樹.與之前的調(diào)整方法不同,本文提出的維護緊湊的前綴樹算法不僅去掉了原始前綴樹中的垃圾節(jié)點以提高數(shù)據(jù)的效用性,而且在檢查每條路徑的時候考慮了分支號條件,高效地獲取可能挖掘出關(guān)鍵模式的所有路徑集.

3.2.2 擾動關(guān)鍵模式候選集算法

算法3,我們詳細介紹噪音挖掘階段的第1步加噪,即:通過判斷查詢集,從所有模式中得到擾動的關(guān)鍵模式候選集.從所有模式中擾動關(guān)鍵模式候選集不僅要考慮一個模式的支持度是否大于最小支持度閾值,而且還要考慮一個模式的支持度是否滿足分支號分配條件.擾動關(guān)鍵模式候選集算法首先給最小支持度閾值加上Lap(4/εi.1)的噪音,這個噪音閾值用來篩選模式是否頻繁(第 3行).然后,擾動關(guān)鍵模式候選集算法遞歸地給前綴樹中代表相應(yīng)模式的節(jié)點的支持度添加Lap(8/3εi.1)的噪音(第4行、第5行).需要注意的是:這一步篩選操作我們只考慮一個模式是不是關(guān)鍵模式,還沒有得到滿足差分隱私的支持度.一旦得到一棵擾動的前綴樹,擾動關(guān)鍵模式候選集算法需要更新加噪后的項頭表,并按照兩種排序方案重新調(diào)整好順序(第6行),再調(diào)用維護緊湊的前綴樹算法來調(diào)整樹iT′的緊湊性(第7行).最后,對調(diào)整完的前綴樹Ti′使用CPC算法[7]挖掘出關(guān)鍵模式候選集(第8行).因為算法3調(diào)用了算法2,且經(jīng)過分析可得出,該算法的時間復雜度就等于算法2維護緊湊的前綴樹算法的時間復雜度,所以算法3的時間復雜度為O(n2).用C#實現(xiàn)算法3,所消耗的空間復雜度為O(1+(1+|V|)n+1+|I|+|Ci|).其中,n為前綴樹的規(guī)模,|V|為每個節(jié)點有效分支號組合的大小,|I|為項頭表Li′的大小,|Ci|為最終從前綴樹中挖掘出的關(guān)鍵模式的個數(shù).因為第3行需要一個內(nèi)存空間存儲最小支持度閾值,第4行、第5行需要(1+|V|)n個內(nèi)存空間存儲樹中節(jié)點信息以及每個節(jié)點的分支號信息,第6行排序的空間復雜度為O(1),第7行調(diào)用算法2,需要考慮給項頭表Li′分配一個數(shù)組空間,最后,第 8行需要消耗|Ci|個內(nèi)存,所以,算法 3的空間復雜度為O(1+(1+|V|)n+1+|I|+|Ci|).

算法3.擾動關(guān)鍵模式候選集算法.

輸入:緊湊的前綴樹Ti′,排好序的項頭表Li′,當前時間戳篩選步驟的隱私預算εi.1;

輸出:關(guān)鍵模式候選集Ci.

3.3 隱私分析

我們對DP-CPM算法進行了嚴格的理論分析:首先證明了噪音挖掘階段的第1步加噪擾動關(guān)鍵模式候選集算法滿足εi.1-差分隱私,接下來證明了每個時間戳的Mi(即DP-CPM)滿足εi-差分隱私,最后證明了預算吸收滿足w-event隱私.

定理3.算法3擾動關(guān)鍵模式候選集算法滿足εi.1-差分隱私.

證明:分 2步證明從所有模式中擾動關(guān)鍵模式候選集滿足εi.1-差分隱私,其中,分配εi.1/4隱私預算用來計算噪音閾值,分配3εi.1/4隱私預算用來識別關(guān)鍵模式候選集.值得注意的是,此階段不返回所有模式的噪音支持度,而是返回所有滿足關(guān)鍵模式判斷條件的查詢集的二進制結(jié)果,所以只需要把隱私預算使用在滿足條件的查詢集上,直接對不滿足條件的模式添加其孩子節(jié)點的噪音,不消耗任何隱私預算.根據(jù)關(guān)鍵模式的定義可知:判斷一個模式是否關(guān)鍵不僅需要考慮模式的支持度是否滿足最小支持度閾值,還需要考慮模式的支持度是否滿足分支號分配條件,并且這兩個步驟是獨立的.因此,給定D和D′是鄰居數(shù)據(jù)集,相差一條事務(wù)最多影響最小支持度閾值為 1,所以給τ加上拉普拉斯噪音Lap(4/εi.1)滿足εi.1/4-差分隱私.另外,在與噪音閾值比較判斷每個模式是否是關(guān)鍵模式時,需要分兩個條件判斷,其中每個判斷查詢集返回一個二進制的向量v,滿足判斷條件返回 1,否則返回 0.一方面,相差一條事務(wù)最多會影響每個模式的支持度為 1,即影響滿足最小支持度閾值的候選集的二進制結(jié)果為 1;另一方面,相差一條事務(wù)最多也會影響支持度滿足分支號分配條件的模式候選集的二進制結(jié)果為1.再根據(jù)NoisyCut[12]算法中定理2閾值查詢集的隱私證明,同樣可證無論滿足判斷條件的查詢有多少個,判斷查詢集都滿足差分隱私.所以,給前綴樹中的每個節(jié)點的支持度添加拉普拉斯噪音Lap(8/3εi.1)滿足 3εi.1/4-差分隱私.最后,根據(jù)差分隱私的序列組合性,算法3擾動關(guān)鍵模式候選集滿足εi.1-差分隱私. □

定理4.算法1(即Mi)滿足εi-差分隱私.

證明:值得注意的是,算法1中只有Mi.2是隱私的,所以我們將所有的隱私預算都投資在它上面.在噪音挖掘階段,我們采用兩步加噪來得到最終擾動的關(guān)鍵模式及其噪音支持度,其中每個步驟各分配一半的隱私預算(即εi=2εi.1=2εi.2),其中,第1步加噪就是算法3擾動關(guān)鍵模式候選集算法,我們在定理3已經(jīng)證明它滿足εi.1-差分隱私.因此,這里證明第2步得到噪音支持度滿足εi.2-差分隱私.給定鄰居數(shù)據(jù)集D和D′,它們最多相差一個關(guān)鍵模式,則敏感性為

其中,Y表示前綴樹中的所有節(jié)點,Z表示Y的所有孩子節(jié)點.因此,向關(guān)鍵模式的支持度中添加Lap(Δf/εi.2)滿足εi.2-差分隱私.根據(jù)定理2差分隱私的序列組合性,可證明算法 1滿足εi-差分隱私,其中,εi=εi.1+εi.2. □

定理5.預算吸收滿足w-event隱私.

證明:當前時間戳i的隱私預算εi依賴于之前的時間戳,有如下3種情況: (1)εi必須強制為0;(2)εi可以吸收之前跳過的隱私預算;(3)εi可能被吸收.假設(shè)當前時間戳i可以從之前的α個時間戳中吸收跳過的隱私預算.根據(jù)預算吸收策略[22],要滿足:

(i)εi=(α+1)×ε/w;

(ii) 對于所有滿足(i-α≤t≤i-1)∧(i+1≤t≤i+α)有εt=0,

(iii) 0≤α≤w-1.

因此,對于任何包含時間戳i并且覆蓋n＞α個隱私預算為0的滑動窗口,這n個隱私預算要么被強制為0要么被εi吸收了,所以時間戳i擁有的總隱私預算最多為(α+1)×ε/w,即,最多的情況是這n+1個時間戳都使用均勻分配的隱私預算上面的分析對于任何決定吸收以前跳過的隱私預算的時間戳都是獨立的,所以. □

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

本節(jié)通過大量實驗表明 DP-CPM 算法的效用性和運行時間,具體分析了隱私預算ε、滑動窗長度W=窗口大小w×窗格大小p,以及相鄰窗口的重疊系數(shù)r這3個參數(shù)對算法性能的影響.實驗環(huán)境為Intel Core i7 CPU 3.60 GHz,8GB內(nèi)存,Windows 7操作系統(tǒng).使用C#實現(xiàn)了DP-CPM算法,且每個實驗數(shù)據(jù)是50次運行的平均值.

4.1 數(shù)據(jù)集

本實驗使用3個公開的真實數(shù)據(jù)集,其中,

· Chess和Accidents是密集型數(shù)據(jù)集:Chess由UCI提供;而Accidents是由Geurts提供的匿名的交通事故數(shù)據(jù)集,該數(shù)據(jù)集中事務(wù)的最大長度為63,平均長度為50.5;

· Retail是由 Brijs提供的稀疏型數(shù)據(jù)集,包含匿名的比利時零售市場購物籃數(shù)據(jù),該數(shù)據(jù)集中的每筆交易都是一個收據(jù)中的一組項目,其中,最大的事務(wù)長度為 76,平均事務(wù)長度為 10.3(http://fimi.ua.ac.be/data).

數(shù)據(jù)集的特點見表2.

Table 2 Data characteristics表2 數(shù)據(jù)特點

4.2 實驗結(jié)果

我們從兩個方面來評估算法的效用性:(1) 算法發(fā)布的結(jié)果集中模式的準確性;(2) 算法發(fā)布的關(guān)鍵模式的支持度的準確性.為此,我們在實驗中使用 F-score[15]和相對誤差 RE[11]作為效用性的度量標準,這兩個指標可以涵蓋以上兩個方面的效用性評價指標.

定義5(F-score).設(shè)C和C′分別表示精確的和已發(fā)布的關(guān)鍵模式的集合,則F-score的定義如下:

定義6(相對誤差RE).已發(fā)布的關(guān)鍵模式集合C′的相對誤差定義為

其中,Y是C′中的一個關(guān)鍵模式,c(Y)表示Y的真實支持度,表示發(fā)布的Y的支持度.

4.2.1 參數(shù)W和ε變化對效用性和運行時間的影響

為了表明參數(shù)W和ε對DP-CPM算法性能的影響,本組實驗固定r=75%,W從50變化到250,隱私預算從0.5變化到 2.5.根據(jù)不同數(shù)據(jù)集的大小和密集程度,我們給數(shù)據(jù)集設(shè)置了不同的最小支持度閾值.對于數(shù)據(jù)集Chess,Accidents和 Retail,τ分別為 40,45和 6.

圖6顯示了在W和ε變化時,F-score的變化趨勢.

Fig.6 Effect of parametersWandεon F-score圖6 參數(shù)W和ε對F-score的影響

從圖6(a)和圖6(c)我們可以看出:當隱私預算相同時,F-score不會隨著W的增加而改變.這是因為我們的擾動關(guān)鍵模式候選集算法與前綴樹的大小是不相關(guān)的,只依賴于前綴樹的緊湊性,因此在數(shù)據(jù)集 Chess和 Retail中,關(guān)鍵模式的擾動不會隨著W的增加而改變.相反,我們可以看到,圖6(b)中的F-score隨著W的增加而變得更好.這是因為數(shù)據(jù)集 Accidents比之前的兩個數(shù)據(jù)集更密集,所以尺寸越大的前綴樹會變得更加緊湊.因此,我們可以挖掘出更多準確的關(guān)鍵模式.為了理解參數(shù)ε如何影響 F-score,從圖6我們觀察到:ε越大,F-score越高,性能越好.這是因為更大的ε計算出的噪音更小;并且當ε≥1時,性能就變得趨于穩(wěn)定.因此,我們在其他組實驗中設(shè)置ε=1.

從圖7可以看出:隨著W增大,RE變小,算法性能更好;尤其是在密集型數(shù)據(jù)集Chess和Accidents中,效果更明顯.這是因為我們從更大的窗口中挖掘出來的模式支持度更大,而噪音的大小和窗口長度無關(guān),所以W越大RE越小.但隨著窗口變大,圖7(c)中的RE減少的比在其他數(shù)據(jù)集中更少.這是因為稀疏數(shù)據(jù)集Retail隨著W增大,模式的支持度增加的相對較少.從圖7中我們還注意到:當ε變大時,RE變得更小.因為ε越大,噪音越小.

Fig.7 Effect of parametersWandε on RE圖7 參數(shù)W和ε對相對誤差的影響

圖8通過改變W和ε來顯示我們DP-CPM算法的運行時間.可以看到:在每個數(shù)據(jù)集中,隨著ε的變化,運行時間并沒有任何規(guī)律.其原因是參數(shù)ε只影響算法效用性,而不影響算法的的運行時間.從圖8我們還可以看到:對于所有數(shù)據(jù)集,運行時間都會隨著W的增加而不斷增加.這是因為窗口越大,前綴樹越大,掃描的時間更長.

Fig.8 Effect of parametersWandεon runtime圖8 參數(shù)W和ε對運行時間的影響

4.2.2 參數(shù)r和ε變化對效用性和運行時間的影響

為了度量參數(shù)r和ε對DP-CPM算法的影響,本組實驗固定W=100,r從50%變化到90%,隱私預算從0.5變化到 2.5.根據(jù)不同數(shù)據(jù)集的大小和密集程度我們給數(shù)據(jù)集設(shè)置了不同的最小支持度閾值.對于數(shù)據(jù)集 Chess,Accidents和 Retail,τ分別為40,45和 6.

圖9顯示了在r和ε變化時,3個數(shù)據(jù)集上F-score的變化趨勢.首先,我們可以看到,隨著ε變大,F-score越大,算法性能會變得更好,原因是較大的ε會產(chǎn)生更少的噪音.同時,我們可以看到:當ε等于或大于1之后,性能趨于穩(wěn)定,所以我們在其他組實驗中設(shè)置ε=1.此外,從圖9中還可以觀察到:r越大,F-score越大,性能會變得更好.這是因為r越高,意味著相鄰窗口的重疊越多,所以兩階段機制計算出的差異就越小,我們就可以吸收更多跳過的隱私預算來挖掘更準確的隱私關(guān)鍵模式.

Fig.9 Effect of parametersrandε on F-score圖9 參數(shù)r和ε對F-score的影響

圖10顯示了在3個數(shù)據(jù)集上,通過改變ε和r對RE的影響.同樣地,當ε變得更大時,RE越小,算法的性能更好.這是因為越大的ε意味著越小的噪音.圖10(a)和圖10(b)分別顯示了在密集型數(shù)據(jù)集Chess和Accidents里的RE,我們可以看到,密集數(shù)據(jù)集里的 RE比圖10(c)中稀疏數(shù)據(jù)集里的 RE值更小.這是因為當W相同時,從密集數(shù)據(jù)集挖掘出的模式的支持度比稀疏數(shù)據(jù)集的大.因此,在密集數(shù)據(jù)集中RE更小.另外,從圖10我們還可以注意到:r越大,RE越小,性能越好.原因是較高的r意味著相鄰窗口的重疊更多,因此兩階段機制計算出的差異更小,可以吸收更多跳過的隱私預算來提高數(shù)據(jù)效用性.

Fig.10 Effect of parametersrandε on RE圖10 參數(shù)r和ε對相對誤差的影響

圖11給出了ε和r不同時算法的運行時間變化趨勢.

Fig.11 Effect of parametersrandε on runtime圖11 參數(shù)r和ε對運行時間的影響

很明顯,r越大,運行時間越少.原因如下:一方面,較高的重疊系數(shù)意味著窗口滑動時需要掃描更少的新事務(wù);另一方面,較高的r則意味著相鄰窗口的重疊更多,因此,我們根據(jù)計算出的更小的差異而直接返回近似統(tǒng)計值.此外,在每個數(shù)據(jù)集中,當r和W相同時,運行時間不隨著ε的變化而變化.這是因為參數(shù)ε只影響數(shù)據(jù)效用而不影響運行時間.

4.2.3 參數(shù)r和W變化對效用性和運行時間的影響

為了表明參數(shù)W和r如何影響DP-CPM算法的性能,本組實驗我們固定ε=1,W從50變化到250,r從50%變化到 90%.根據(jù)不同數(shù)據(jù)集的大小和密集程度,我們給數(shù)據(jù)集設(shè)置了不同的最小支持度閾值.對于數(shù)據(jù)集Chess,Accidents和 Retail,τ分別為 40,45和 6.

圖12顯示了在W和r變化時,F-score的變化趨勢.從圖12(a)和圖12(c)我們可以看出:當r相同時,F-score不會隨著W的增加而改變.這是因為我們擾動關(guān)鍵模式候選集算法與前綴樹的大小是不相關(guān)的,只依賴于前綴樹的緊湊性,因此在數(shù)據(jù)集Chess和 Retail中,關(guān)鍵模式的擾動不會隨著W的增加而改變.相反,我們可以看到,圖12(b)中的F-score隨著W的增加而變得更好.這是因為數(shù)據(jù)集Accidents比之前2個數(shù)據(jù)集更密集,所以尺寸越大的前綴樹會變得更加緊湊,因此我們可以挖掘出更多準確的關(guān)鍵模式.另外,從圖12也可以看出,r越大,F-score越大,性能會變得更好.這是因為r越高,意味著相鄰窗口的重疊越多,所以兩階段機制計算出的差異就越小,我們就可以吸收更多跳過的隱私預算來挖掘更準確的隱私關(guān)鍵模式.

Fig.12 Effect of parametersWandron F-score圖12 參數(shù)W和r對F-score的影響

從圖13我們可以看出:隨著W增大,RE變得更小,算法性能更好,尤其是在密集型數(shù)據(jù)集Chess和Accidents中效果更明顯.這是因為我們從更大的窗口中挖掘出來的模式的支持度更大,而噪音的大小和窗口長度無關(guān).綜上所述,W越大,RE越小.但隨著窗口變大,圖13(c)中的RE減少的比在其他數(shù)據(jù)集中更少.這是因為稀疏數(shù)據(jù)集Retail隨著W增大,相同模式的支持度增加的相對較少.另外,從圖13我們還可以注意到:r越大,RE越小,性能越好.原因是較高的r意味著相鄰窗口的重疊更多,因此兩階段機制計算出的差異更小,可以吸收更多跳過的隱私預算來提高數(shù)據(jù)效用性.

Fig.13 Effect of parametersWandron RE圖13 參數(shù)W和r對相對誤差的影響

圖14通過改變W和r來顯示我們DP-CPM算法的運行時間.我們可以看到:對于所有數(shù)據(jù)集,運行時都會隨著W的增加而不斷增加.這是因為窗口越大,前綴樹越大,掃描的時間更長.另外,r越大,運行時間越少.原因如下:一方面,較高的重疊系數(shù)意味著窗口滑動時需要掃描更少的新事務(wù);另一方面,較高的r意味著相鄰窗口的重疊更多,因此我們根據(jù)計算出小的差異而直接返回近似統(tǒng)計值.

Fig.14 Effect of parametersWandron runtime圖14 參數(shù)r和W對運行時間的影響

綜上所述:F-score與參數(shù)W的變化無關(guān);而相對誤差RE會隨著參數(shù)W的增加而減小,尤其是在密集型數(shù)據(jù)集里效果更明顯,并且運行時間會隨著參數(shù)W的增加而增加.這說明窗口越大,挖掘出的關(guān)鍵模式支持度上的誤差越小,而挖掘時間越長.另一方面,可以看出,隨著參數(shù)r的增加,F-score變大,相對誤差RE變小,且運行時間變小.這說明窗口滑動重合的部分越多,連續(xù)發(fā)布的數(shù)據(jù)效用性越高,連續(xù)挖掘的時間越少.運行時間與參數(shù)ε的變化無關(guān),而隨著ε的增加,F-score變大,相對誤差RE變小.這說明隱私預算越高,數(shù)據(jù)效用性越好.

5 總結(jié)語

隨著大數(shù)據(jù)的發(fā)展,挖掘頻繁模式不再局限于靜態(tài)的集值數(shù)據(jù),更多的是從動態(tài)的事務(wù)數(shù)據(jù)流中實時挖掘頻繁模式.目前,已有相關(guān)的工作分析并解決了靜態(tài)下頻繁模式挖掘的隱私問題;而隨著一些數(shù)據(jù)流下實時高效的頻繁模式挖掘工作的出現(xiàn),我們發(fā)現(xiàn)數(shù)據(jù)流下連續(xù)發(fā)布精確的頻繁模式比靜態(tài)更容易泄露隱私,且還沒有相關(guān)工作涉及這個亟待解決的問題.本文首次討論并指出了在事務(wù)數(shù)據(jù)流上挖掘關(guān)鍵模式存在的隱私問題,為了解決這個問題,我們利用差分隱私設(shè)計了一種包含兩階段機制的 DP-CPM 算法,該算法不僅提高了隱私和數(shù)據(jù)效用之間的權(quán)衡,而且還提高了挖掘時間和維護成本之間的權(quán)衡.在加噪階段,我們根據(jù)關(guān)鍵模式的特點,利用稀疏向量技術(shù)提出了一種新的加噪方法,可以在滿足隱私的前提下,最大限度地提高數(shù)據(jù)效用性.最后,我們在密集型數(shù)據(jù)集和稀疏型數(shù)據(jù)集上進行了大量的實驗來表明 DP-CPM 算法的效用性和效率性.目前,數(shù)據(jù)流上頻繁序列以及頻繁子圖的挖掘有著廣泛的應(yīng)用,但是這些挖掘方法也存在隱私泄露問題,因此在今后的工作中,可以改進我們的方法來實現(xiàn)數(shù)據(jù)流上頻繁序列和頻繁子圖挖掘的隱私保護.