基于差分隱私的數(shù)據(jù)流頻繁項(xiàng)集發(fā)布

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

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

0 引 言

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

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

論文主要貢獻(xiàn)如下：

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

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

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

1 相關(guān)工作

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

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

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

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

2.1 問題描述

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

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

2.2 相關(guān)定義

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

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

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

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

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

2.2.2 差分隱私

差分隱私定義參見文獻(xiàn)[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上進(jìn)行Q查詢的查詢結(jié)果進(jìn)行處理的輸出。概率Pr[A(Q,D)=0] 表示輸出結(jié)果為A(Q,D)=O的概率。由定義可知，若算法滿足式(1)，則該算法可以防止數(shù)據(jù)集中隱私信息的泄露。

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

(2)

相鄰流前綴和事件隱私參見文獻(xiàn)[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為以任意大小的流前綴作為輸入的隱私保護(hù)機(jī)制，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ù)流頻繁項(xiàng)集發(fā)布的差分隱私定義，若提出的隱私保護(hù)發(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é)議，當(dāng)單位窗格內(nèi)數(shù)據(jù)新增超過閾值，對當(dāng)前窗口進(jìn)行單次隱私保護(hù)頻繁項(xiàng)集發(fā)布，同時進(jìn)行窗口滑動，采用帶更新標(biāo)記的CAN樹記錄數(shù)據(jù)，當(dāng)窗口滑動時，刪除帶有過期標(biāo)記的數(shù)據(jù)；針對單次頻繁項(xiàng)集發(fā)布，利用事務(wù)截斷降低隱私預(yù)算，為克服隨機(jī)劃分精度過低，引入負(fù)項(xiàng)概念，減少事務(wù)分割造成的冗余屬性，有效降低截斷誤差；利用條件模式基對CAN樹進(jìn)行挖掘，發(fā)布對應(yīng)頻繁項(xiàng)集。

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

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

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

針對頻繁項(xiàng)集發(fā)布精度受w值影響問題，提出動態(tài)窗格定義，窗格長度依賴頻繁項(xiàng)集變化，變化量由當(dāng)前CAN樹挖掘得到的頻繁項(xiàng)集與最近發(fā)布頻繁項(xiàng)集的距離衡量，若變化量達(dá)到閾值，產(chǎn)生新窗格，以均衡各窗格數(shù)據(jù)對發(fā)布結(jié)果的影響，同時為滿足差分隱私約束，在計(jì)算距離時需添加拉普拉斯噪聲，若噪聲距離大于閾值，則創(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〉， 平均分配隱私預(yù)算，每一窗格只發(fā)布一次，數(shù)據(jù)流在發(fā)布時判斷當(dāng)前窗格是否存在發(fā)布版本，若沒有，使用隱私保護(hù)發(fā)布方法進(jìn)行發(fā)布，若有，直接發(fā)布該版本。

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

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

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

輸出：頻繁項(xiàng)集序列

(1)版本號flag=1

(2)whiletransin D

(3) 對trans進(jìn)行事務(wù)截斷， 更新CAN樹， 同時對每次更新的節(jié)點(diǎn)標(biāo)注窗口號為flag， 維護(hù)1-項(xiàng)集列表L

(7) 進(jìn)行窗口更新

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

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

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

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

(13)end while

3.2.2 窗口更新算法

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

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

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

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

(4)

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

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

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

4 理論與實(shí)驗(yàn)分析

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

4.1 隱私保護(hù)效果分析

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

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

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

4.2 實(shí)驗(yàn)配置與評估標(biāo)準(zhǔn)

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

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

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

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

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

圖2 F-SCORE隨隱私預(yù)算變化趨勢

圖3 RE隨隱私預(yù)算變化趨勢

圖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算法準(zhǔn)確性對w值不敏感。圖5是算法RE值隨w變化的趨勢，其中ε=1,θ=0.6。 同樣，DDFIM算法的RE值隨著w增加而升高，w值越大，準(zhǔn)確性越差；而DP_DFIM算法的RE值隨w增加基本保持平穩(wěn)，表明DP_DFIM算法的準(zhǔn)確性對w不敏感。

圖4 F-SCORE隨w變化趨勢

圖5 RE隨w變化趨勢

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

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

5 結(jié)束語

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