差分隱私的數據流關鍵模式挖掘方法?

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

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

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

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

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

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

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

本文的主要貢獻如下:

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

2) 為了解決隱私問題,根據關鍵模式的性質設計了兩步順序加噪方法來發布隱私的關鍵模式及其噪音支持度;

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

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

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

1 相關工作

本節從靜態環境下滿足差分隱私的頻繁模式挖掘方法、數據流中精確頻繁模式挖掘方法和數據流下滿足差分隱私的數據發布方法這3個與本文直接相關的方面闡述現有的研究工作,并指出我們方法與其不同之處.

1.1 靜態環境下滿足差分隱私的頻繁模式挖掘方法

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

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

1.2 數據流中精確頻繁模式挖掘方法

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

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

1.3 數據流下滿足差分隱私的數據發布方法

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

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

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

2 預備知識

2.1 基本概念

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

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

Table 1 Notations表1 標記

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

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

2.2 差分隱私保護模型

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2.3 關鍵模式挖掘算法

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

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

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

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

3 DP-CPM算法

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

3.1 兩階段機制

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

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

Fig.5 Internal mechanics ofMi圖5 兩階段機制Mi的內部構造

· 差異計算階段

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

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

· 噪音挖掘階段

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

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

算法1.DP-CPM:關鍵模式隱私挖掘算法.

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

輸出:當前時間戳的統計發布Oi.

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

3.2 子算法描述

3.2.1 維護緊湊的前綴樹算法

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

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

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

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

3.2.2 擾動關鍵模式候選集算法

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

算法3.擾動關鍵模式候選集算法.

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

輸出:關鍵模式候選集Ci.

3.3 隱私分析

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

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

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

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

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

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

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

證明:當前時間戳i的隱私預算εi依賴于之前的時間戳,有如下3種情況: (1)εi必須強制為0;(2)εi可以吸收之前跳過的隱私預算;(3)εi可能被吸收.假設當前時間戳i可以從之前的α個時間戳中吸收跳過的隱私預算.根據預算吸收策略[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 實驗結果與分析

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

4.1 數據集

本實驗使用3個公開的真實數據集,其中,

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

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

數據集的特點見表2.

Table 2 Data characteristics表2 數據特點

4.2 實驗結果

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5 總結語

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