張鴻鳴，鮑曉涵，倪巍偉+

(1.江蘇方天電力技術(shù)有限公司 智能電網(wǎng)服務(wù)中心，江蘇 南京 210000；2.東南大學 計算機科學與工程學院，江蘇 南京 211189)

0 引 言

目前，差分隱私是解決隱私保護數(shù)據(jù)流頻繁項集發(fā)布[1-3]的主要技術(shù)。Wang等[4]采用三階段機制進行頻繁項集發(fā)布；Liang等[5]提出基于閾值指數(shù)機制的頻繁項集發(fā)布方法。已有方法均基于w-滑動窗口進行頻繁項集發(fā)布，需滿足窗口外數(shù)據(jù)對頻繁項集發(fā)布的影響忽略不計的前提條件，也就是w-窗口假設(shè)。已有方法主要存在以下不足：①依賴w-窗口假設(shè)問題，隱私預算分配依賴w值，w取值不合理可能導致所發(fā)布頻繁項集精度大幅下降；②隨機劃分導致截斷誤差較大，難以兼顧數(shù)據(jù)可用與隱私安全。

聚焦發(fā)布精度方面的這些不足，考慮根據(jù)數(shù)據(jù)新增幅度調(diào)節(jié)滑動窗口長度，實現(xiàn)w-滑動窗口的隱私預算動態(tài)分配，提升發(fā)布頻繁項集的精度；利用w-窗口內(nèi)CAN樹頻繁信息，引入負項概念，對新增數(shù)據(jù)進行事務(wù)截斷，有效降低截斷誤差；進一步設(shè)計CAN樹數(shù)據(jù)更新策略，支持帶負項的滿足差分隱私的頻繁項集發(fā)布。

論文主要貢獻如下：

(1)利用當前窗口CAN樹頻繁信息，引入負項概念，對數(shù)據(jù)流進行事務(wù)截斷，降低截斷誤差。

(2)提出滑動窗口窗格長度調(diào)整策略，設(shè)計w-滑動窗口隱私預算動態(tài)分配方法，規(guī)避w取值不合理對所發(fā)布頻項集準確性的影響。

(3)提出隱私保護數(shù)據(jù)流頻繁項集發(fā)布方法DP_DFIM，在兼顧隱私的同時，實現(xiàn)數(shù)據(jù)流頻繁項集高精度發(fā)布，設(shè)計實驗驗證所提方法的有效性。

1 相關(guān)工作

近年來，數(shù)據(jù)流分析挖掘中的隱私問題得到研究者持續(xù)關(guān)注。隱私保護數(shù)據(jù)流頻繁項集發(fā)布的對象是從數(shù)據(jù)流中提取的頻繁項集，需要在不泄露數(shù)據(jù)流隱私的同時，充分維持所發(fā)布頻繁項集的準確性。

目前，針對數(shù)據(jù)流的隱私保護頻繁項集發(fā)布研究還處于起步階段。Wang等[4]采用三階段機制(預處理階段、深度計算階段和噪聲挖掘階段)進行頻繁項集發(fā)布，為減少對關(guān)鍵模式計算算法的調(diào)用次數(shù)，第一個階段返回低噪聲統(tǒng)計量或精確逼近統(tǒng)計量。當需要低噪聲統(tǒng)計量時，該算法進入噪聲挖掘階段，否則進入深度計算階段；Liang等[5]提出基于閾值指數(shù)機制的頻繁項集發(fā)布方法，通過更改較小窗格隱私預算進行自適應(yīng)隱私預算分配，采用隨機劃分方法進行長事務(wù)分割，對丟失信息通過后續(xù)發(fā)布進行概率補償，提升頻繁項集的準確性。盡管Liang等的方法能夠在滿足差分隱私的同時盡可能維持頻繁項集挖掘結(jié)果準確可用，但仍然存在發(fā)布頻繁項集的精度依賴窗口規(guī)模設(shè)置合理與否，以及基于隨機劃分的事務(wù)截斷缺少對數(shù)據(jù)分布特征的關(guān)注，存在截斷誤差較大，難以兼顧頻繁項集準確性與隱私安全問題。

其原因在于：現(xiàn)有方法基于時間戳劃分數(shù)據(jù)流滑動窗口，當滑動窗口的新增數(shù)據(jù)規(guī)模較小時，當前數(shù)據(jù)流統(tǒng)計信息受窗口外數(shù)據(jù)的影響較大，只統(tǒng)計當前窗口內(nèi)數(shù)據(jù)勢必導致所發(fā)布頻繁項集與數(shù)據(jù)流真實的頻繁項集的較大差異，導致滑動窗口窗格參數(shù)w的設(shè)置直接影響最終發(fā)布精度頻繁項集；其次，傳統(tǒng)的靜態(tài)事務(wù)截斷方法雖然截斷誤差小，但需多次掃描數(shù)據(jù)庫，不適用數(shù)據(jù)流發(fā)布場景。而采用隨機劃分方法，存在大量頻繁項被拆分成不頻繁項，導致較大的事務(wù)截斷誤差。例如長事務(wù)中包含頻繁項集 {a,b}， 但事務(wù)截斷將 {a,b} 拆分成兩條事務(wù)， {a,b} 的支持度隨之降低。

2 問題描述和相關(guān)定義

2.1 問題描述

隱私保護數(shù)據(jù)流頻繁項集發(fā)布需滿足以下約束：①發(fā)布的頻繁項集及其支持度精度不受w-滑動窗口取值影響，以保證隱私預算分配合理；②事務(wù)截斷的截斷誤差盡可能小，以兼顧所發(fā)布頻繁項集的精度。

為實現(xiàn)以上目標，主要思路如下：引入自適應(yīng)窗口，保證發(fā)布數(shù)據(jù)精度獨立于w取值，設(shè)計自適應(yīng)w-滑動窗口隱私預算分配方法；利用w-窗口內(nèi)的CAN樹頻繁項集信息進行事務(wù)截斷，引入負項的概念，抵消截斷過程產(chǎn)生的冗余項，有效降低截斷誤差；設(shè)計CAN樹更新策略，提升CAN樹的搜索效率。實現(xiàn)數(shù)據(jù)流隱私安全與所發(fā)布頻繁項集精度的兼顧。

2.2 相關(guān)定義

2.2.1 數(shù)據(jù)流

數(shù)據(jù)流與滑動窗口定義參見文獻[1,6]，具體如下：

定義1[1,6]數(shù)據(jù)流:數(shù)據(jù)流是一種僅能一次讀取的數(shù)據(jù)序列，具有實時、有序、到達速度快的特點。

定義2[1]w-滑動窗口:給定數(shù)據(jù)流DS，將DS劃分為若干塊(每塊為一個子序列)，分得的每一塊稱為一個基本窗口，表示為BW，滑動窗口SW為連續(xù)w個基本窗口組成的序列 (BW1,BW2,…,BWw)。

考慮數(shù)據(jù)流只能進行單次線性掃描的特點，事先對數(shù)據(jù)項進行排序，通過單次數(shù)據(jù)庫掃描構(gòu)建CAN樹，基于CAN樹[7]利用FP-Tree算法尋找條件模式基，獲得頻繁項集。

2.2.2 差分隱私

差分隱私定義參見文獻[3，9]，如下：

定義3[8,9]差分隱私：給定數(shù)據(jù)集D和D′，D和D′之間相差一條記錄，即 |DΔD′|=1。 對給定算法A，Range(A) 為A的取值范圍，若算法A在數(shù)據(jù)集D和D′上任意輸出結(jié)果滿足下列不等式，稱A滿足ε-差分隱私。

Pr[A(Q,D)=O]≤exp(ε)×Pr[A(Q′,D)=O]

(1)

A(Q,D) 表示使用A算法對從數(shù)據(jù)集D上進行Q查詢的查詢結(jié)果進行處理的輸出。概率Pr[A(Q,D)=0] 表示輸出結(jié)果為A(Q,D)=O的概率。由定義可知，若算法滿足式(1)，則該算法可以防止數(shù)據(jù)集中隱私信息的泄露。

定義3提出了滿足差分隱私的條件，而差分隱私實現(xiàn)的主要技術(shù)手段是添加噪聲，通過添加噪聲使得算法A的輸出在一定范圍內(nèi)波動，從而使得攻擊方無法獲取隱私信息。本文采取拉普拉斯噪聲機制[10]，算法A的輸出結(jié)果O服從方差為ΔQ/ε、 均值為0的拉普拉斯分布，如式(2)所示

(2)

相鄰流前綴和事件隱私參見文獻[1]，具體如下：

定義4[1]w-相鄰流前綴：對正整數(shù)w，若流前綴St,S′t滿足：①對i∈[1,t] 且St[i]≠S′t[i]， 其中St[i],S′t[i] 是相鄰的；②對于每個i1

定義5[1]w-事件隱私：設(shè)M為以任意大小的流前綴作為輸入的隱私保護機制，O為M的所有可能輸出集合。若對于所有輸出集合o∈O， 所有的w-相鄰流前綴St,S′t， 以及所有t， 若

Pr[M(St)∈o]≤exp(ε)×Pr[M(S′t)∈o]

(3)

則M滿足w-事件-ε-差分隱私(簡稱w-事件隱私)。

定義5是數(shù)據(jù)流頻繁項集發(fā)布的差分隱私定義，若提出的隱私保護發(fā)布方法滿足定義5，表明該方法滿足差分隱私，w-鄰居數(shù)據(jù)流指的是兩個流數(shù)據(jù)之間每個時間戳之間的數(shù)據(jù)都是相鄰數(shù)據(jù)。

3 DP_DFIM方法

3.1 算法思路

算法思路如下所示：為規(guī)避w取值對發(fā)布精度的影響，提出數(shù)據(jù)流w-動態(tài)窗口協(xié)議，當單位窗格內(nèi)數(shù)據(jù)新增超過閾值，對當前窗口進行單次隱私保護頻繁項集發(fā)布，同時進行窗口滑動，采用帶更新標記的CAN樹記錄數(shù)據(jù)，當窗口滑動時，刪除帶有過期標記的數(shù)據(jù)；針對單次頻繁項集發(fā)布，利用事務(wù)截斷降低隱私預算，為克服隨機劃分精度過低，引入負項概念，減少事務(wù)分割造成的冗余屬性，有效降低截斷誤差；利用條件模式基對CAN樹進行挖掘，發(fā)布對應(yīng)頻繁項集。

3.2 數(shù)據(jù)流發(fā)布協(xié)議

3.2.1w-動態(tài)滑動窗口協(xié)議

定義6 動態(tài)窗格：設(shè)置頻繁項集變化量閾值，按照子序列對應(yīng)頻繁項集改變量大于閾值的原理，將數(shù)據(jù)流劃分為多個子序列，每個子序列稱為一個動態(tài)窗格，記為DW。

針對頻繁項集發(fā)布精度受w值影響問題，提出動態(tài)窗格定義，窗格長度依賴頻繁項集變化，變化量由當前CAN樹挖掘得到的頻繁項集與最近發(fā)布頻繁項集的距離衡量，若變化量達到閾值，產(chǎn)生新窗格，以均衡各窗格數(shù)據(jù)對發(fā)布結(jié)果的影響，同時為滿足差分隱私約束，在計算距離時需添加拉普拉斯噪聲，若噪聲距離大于閾值，則創(chuàng)建新窗格。

定義7w-動態(tài)滑動窗口：一個滑動窗口SW， 對應(yīng)一個連續(xù)的基本窗口序列 〈DW1,DW2,…,DWw〉， 它所容納的窗格數(shù)量為w， 每一個窗格都有窗口號，窗口號隨數(shù)據(jù)流動不斷更新。

由于窗口外的流數(shù)據(jù)會從CAN樹上剔除，窗口號在滑出窗口后不會再被使用到，為保證窗口號的可靠存儲，窗格版本號為有限數(shù)量，在滑動窗口滑動過程中循環(huán)使用，且窗口號個數(shù)為窗格數(shù)量+1，可保證在窗口滑動過程中不會出現(xiàn)窗口號沖突。

定義8w-動態(tài)滑動窗口協(xié)議：對于一個動態(tài)滑動窗口序列 〈DW1,DW2,…,DWw〉， 平均分配隱私預算，每一窗格只發(fā)布一次，數(shù)據(jù)流在發(fā)布時判斷當前窗格是否存在發(fā)布版本，若沒有，使用隱私保護發(fā)布方法進行發(fā)布，若有，直接發(fā)布該版本。

如圖1所示，每個窗格長度由頻繁項集改變量決定，每個窗格僅發(fā)布一次，如圖所示，若在t5后進行發(fā)布，利用條件模式基挖掘當前頻繁項集，然后通過項集距離進行度量，若距離超過閾值，則開啟新窗口，并清除過期數(shù)據(jù)，發(fā)布滿足差分隱私的頻繁項集。窗口協(xié)議的隱私預算按照窗口數(shù)平均分配，其中部分預算用戶判斷項集距離，其余預算用于當前窗格的頻繁項集發(fā)布，動態(tài)滑動窗口設(shè)置方法見算法1。

圖1 w-動態(tài)滑動窗口協(xié)議

算法1：w-動態(tài)滑動窗口算法

輸出：頻繁項集序列

(1)版本號flag=1

(2)whiletransin D

(3) 對trans進行事務(wù)截斷， 更新CAN樹， 同時對每次更新的節(jié)點標注窗口號為flag， 維護1-項集列表L

(7) 進行窗口更新

(8) 利用DP-FIM算法獲取噪聲頻繁項集, 并且記錄算法執(zhí)行時間t

(10) 調(diào)用LMU算法刪除非頻繁節(jié)點

(11) 發(fā)布噪聲頻繁項集

(12)flag=(flag+1)%(w+1)

(13)end while

3.2.2 窗口更新算法

為保證CAN樹的有效存儲和高效搜索，提出帶有更新標記的窗口更新算法。CAN樹節(jié)點由事務(wù)項trans， 支持度sup， 標志位flag組成，標志位記錄本節(jié)點最后一次更新的窗口號，當進行窗口滑動時，調(diào)用滑出窗口刪除算法處理CAN樹中的失效數(shù)據(jù)。同時，由于CAN樹記錄整個窗口內(nèi)的所有數(shù)據(jù)，包括頻繁項和非頻繁項，會存在對于后續(xù)挖掘結(jié)果無用的非頻繁節(jié)點，若CAN樹搜索時間過久，調(diào)用CAN樹調(diào)整算法，刪除CAN樹中滿足要求的非頻繁節(jié)點，若被刪除節(jié)點有子節(jié)點，則將其所有子節(jié)點都連到該節(jié)點的父節(jié)點上，繼續(xù)進行搜索，沒有刪除所有非頻繁節(jié)點是因為部分非頻繁節(jié)點有可能會變成頻繁節(jié)點，尤其是接近支持度閾值的節(jié)點，這些節(jié)點記為未來頻繁節(jié)點。為減少刪除未來頻繁節(jié)點的情況，采用LMU算法(最早最小刪除算法)，優(yōu)先更新標記最早支持度最小的非頻繁節(jié)點。為高效判定節(jié)點是否為頻繁節(jié)點，使用哈希表記錄所有1-項集及其支持度。

3.3 單次隱私保護發(fā)布算法

定義9 最佳截斷長度存在lopt:使得γ%的事務(wù)數(shù)據(jù)的長度都小于lopt, 其中γ%為經(jīng)驗值。

定義10 數(shù)據(jù)流帶權(quán)最佳截斷長度slopt:給定單位窗格的最佳截斷長度lopt， 以及舊數(shù)據(jù)流帶權(quán)最佳截斷長度sloptold， 新數(shù)據(jù)定義為

(4)

定義11 負項:在事務(wù)截斷時，用于抵消劃分過程中所添加額外的項。

假設(shè)事務(wù)數(shù)據(jù) {a,b,c,d} 的頻繁項集為 {a,b,c}, {a,b,d}, 由于slopt=3， 為保留頻繁項集，將事務(wù)數(shù)據(jù)拆分成 {a,b,c}, {a,b,d}， 此時可發(fā)現(xiàn) {a,b}, {a},  的計數(shù)值均增大1，為抵消計數(shù)值的影響，添加負項數(shù)據(jù) {-a,-b}， 抵消計數(shù)值偏移，同時保存頻繁項集信息。

算法主要包括頻繁項集發(fā)布以及每次發(fā)布之后的后處理。頻繁項集發(fā)布的主要思想是:(1)從CAN樹上獲取條件模式基和其對應(yīng)支持度;(2)若其超集出現(xiàn)在負項頻繁項集中，其支持度需減去負項對應(yīng)支持度;(3)對計算得到的支持度添加拉普拉斯噪聲，并判斷該項集是否頻繁，若是，則添加頻繁項集列表中，否則返回固定的噪聲值;(4)回到步驟(1)直到CAN樹已被搜索完畢;(5)發(fā)布頻繁項集列表。后處理主要包括:(1)根據(jù)當前窗口計算得到截斷的長度閾值為slopt， 用于新數(shù)據(jù)到來時事務(wù)截斷的依據(jù);(2)對挖掘得到的最大頻繁項集組合，進行分組，分組依據(jù)是超集的并集長度小于等于slopt; (3)按照分組對新到來事務(wù)數(shù)據(jù)進行截斷，保證截斷后記錄項集只來自同一組，以保證截斷后事務(wù)記錄長度小于等于slopt， 可以不被分割成兩條事務(wù)數(shù)據(jù)，從而減少負項的產(chǎn)生;(4)事務(wù)截斷導致負項的產(chǎn)生，為抵消計數(shù)偏移，所添負項插入負項CAN樹中，維護方式同CAN樹一致，采用帶更新標記的更新方法不斷更新負項CAN樹。

4 理論與實驗分析

本節(jié)對算法效果進行理論和實驗分析，首先證明DP_DFIM算法滿足差分隱私保護約束，隨后對算法所發(fā)布頻繁項集的準確性進行實驗分析，對比算法采用DDFIM算法。

4.1 隱私保護效果分析

定理1 算法單次發(fā)布方法滿足差分隱私。

證明：分2步證明，假設(shè)隱私預算為εtp， 首先事務(wù)截斷是將輸入數(shù)據(jù)流進行事務(wù)截斷，并且將數(shù)據(jù)插入到CAN樹上，由于后續(xù)挖掘都在CAN樹上進行，可將CAN樹作為原始數(shù)據(jù)考慮，所以事務(wù)截斷不涉及隱私問題。其次后續(xù)在利用條件模式基進行挖掘時，分析噪聲閾值以及項集支持度計算分別只需要占用1/4和1/2的隱私預算。對于所有生成的頻繁項集支持度，添加拉普拉斯噪聲，只需消耗剩余的四分之一隱私預算，故而，算法單次頻繁項集發(fā)布滿足εtp-差分隱私。

定理2w-動態(tài)滑動窗口協(xié)議滿足w-ε-差分隱私。

4.2 實驗配置與評估標準

實驗采用的數(shù)據(jù)集參數(shù)見表1， |D| 為交易記錄條數(shù)， |I| 表示交易項規(guī)模，Max|t| 和Avg|t| 分別對應(yīng)最大交易長度以及平均交易長度。

表1 數(shù)據(jù)集參數(shù)說明

實驗環(huán)境：Windows 10操作系統(tǒng)，Intel Core i5-4200M CPU @ 2.5 GHZ，內(nèi)存8 GB。算法采用Java實現(xiàn)，開發(fā)IDE使用IDEA。利用經(jīng)典的F-SCORE和RE指標[5]衡量DP_DFIM算法所發(fā)布頻繁項集的準確性，所發(fā)布滿足差分隱私的頻繁項集與不考慮隱私背景下提取的頻繁項集重合度越高，算法發(fā)布頻繁項集的準確性越好。

4.3 實驗結(jié)果分析

對每組數(shù)據(jù)進行次實驗取平均值，圖2是算法在MSNBC、Kosarak、POS上F-SCORE值隨隱私預算變化的趨勢，其中w=5,θ=0.6,ε=1。F-SCORE值隨著隱私預算的增加而增加，說明數(shù)據(jù)隱私保護的越好，準確性越差，且算法DDFIM隨隱私預算的變化與DDFIM算法相近，表明兩種算法兼顧數(shù)據(jù)隱私性和發(fā)布頻繁項集準確性的能力大致相同。圖3是算法在MSNBC、Kosarak、POS上RE取值隨隱私預算變化的趨勢，其中w=5,θ=0.6，ε=1。 同樣，RE的值隨著隱私預算的增加而降低，表明隱私保護的越好，準確性越差，反之，準確性越好。算法DP_DFIM隨隱私預算的變化與DDFIM算法相近，表明兩種算法兼顧數(shù)據(jù)隱私性和發(fā)布頻繁項集準確性的能力大致相同。

圖2 F-SCORE隨隱私預算變化趨勢

圖3 RE隨隱私預算變化趨勢

圖4是算法在3個數(shù)據(jù)集上F-SCORE值隨窗口取值w變化的趨勢，其中ε=1,θ=0.6。 由上圖可見，DDFIM算法F-SCORE值隨著w的增加顯著降低，而DP_DFIM算法F-SCORE值隨著w的增加基本保持平穩(wěn)，表明DDFIM算法受w影響較顯著，而DP_DFIM算法準確性對w值不敏感。圖5是算法RE值隨w變化的趨勢，其中ε=1,θ=0.6。 同樣，DDFIM算法的RE值隨著w增加而升高，w值越大，準確性越差；而DP_DFIM算法的RE值隨w增加基本保持平穩(wěn)，表明DP_DFIM算法的準確性對w不敏感。

圖4 F-SCORE隨w變化趨勢

圖5 RE隨w變化趨勢

圖6為算法效率實驗結(jié)果,θ設(shè)置為0.6，w=5，ε=1。 如圖6所示，隨著數(shù)據(jù)規(guī)模增加，算法運行時長增長趨勢相近。DP_DFIM的運行時間比DDFIM多，原因在于DP_DFIM需要較為精確的事務(wù)截斷，消耗額外時間，保證發(fā)布結(jié)果具有更好的準確性。

圖6 效率隨數(shù)據(jù)集大小變化趨勢

5 結(jié)束語

針對數(shù)據(jù)流頻繁項集發(fā)布中隱私安全和頻繁項集準確性難以兼顧問題，提出基于差分隱私的數(shù)據(jù)流頻繁項集發(fā)布算法DP_DFIM，通過制定滑動窗口窗格長度的動態(tài)自適應(yīng)調(diào)整策略，設(shè)計w-滑動窗口的動態(tài)自適應(yīng)隱私預算分配方法，規(guī)避w取值不合理的不利影響；利用當前窗口CAN樹的頻繁信息，引入負項概念，對新增數(shù)據(jù)進行事務(wù)截斷，同時在后續(xù)發(fā)布進行概率補償，降低截斷誤差，提升發(fā)布頻繁項集的準確性。理論分析和實驗結(jié)果表明，所提方法能有效兼顧隱私安全和發(fā)布頻繁項集的有效性。