基于差分隱私的數據流頻繁項集發布

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

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

0 引 言

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

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

論文主要貢獻如下：

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

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

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

1 相關工作

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

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

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

2 問題描述和相關定義

2.1 問題描述

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

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

2.2 相關定義

2.2.1 數據流

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

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

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

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

2.2.2 差分隱私

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

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

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

(1)

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

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

(2)

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

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

定義5[1]w-事件隱私：設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是數據流頻繁項集發布的差分隱私定義，若提出的隱私保護發布方法滿足定義5，表明該方法滿足差分隱私，w-鄰居數據流指的是兩個流數據之間每個時間戳之間的數據都是相鄰數據。

3 DP_DFIM方法

3.1 算法思路

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

3.2 數據流發布協議

3.2.1w-動態滑動窗口協議

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

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

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

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

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

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

圖1 w-動態滑動窗口協議

算法1：w-動態滑動窗口算法

輸出：頻繁項集序列

(1)版本號flag=1

(2)whiletransin D

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

(7) 進行窗口更新

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

(10) 調用LMU算法刪除非頻繁節點

(11) 發布噪聲頻繁項集

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

(13)end while

3.2.2 窗口更新算法

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

3.3 單次隱私保護發布算法

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

定義10 數據流帶權最佳截斷長度slopt:給定單位窗格的最佳截斷長度lopt， 以及舊數據流帶權最佳截斷長度sloptold， 新數據定義為

(4)

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

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

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

4 理論與實驗分析

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

4.1 隱私保護效果分析

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

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

定理2w-動態滑動窗口協議滿足w-ε-差分隱私。

4.2 實驗配置與評估標準

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

表1 數據集參數說明

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

4.3 實驗結果分析

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

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

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

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

圖4 F-SCORE隨w變化趨勢

圖5 RE隨w變化趨勢

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

圖6 效率隨數據集大小變化趨勢

5 結束語

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