基于事務分離的差分隱私頻繁項集挖掘方法

2023-01-31 03:35:42丁蘇凡曾尚琦田冬艷

計算機工程與設計 2023年1期

關鍵詞：機制

丁蘇凡，曾尚琦，田冬艷

(1.中國礦業大學信息與控制工程學院，江蘇徐州 221000； 2.國電南瑞科技股份有限公司國網電力科學研究院，江蘇南京 211000)

0 引言

關聯規則研究是數據挖掘中關鍵課題，用于發現不同物品、信息之間的關聯。頻繁項集挖掘是發掘關聯規則中的重要部分，通過大量研究發現，將采集的數據集進行頻繁項集挖掘、關聯規則分析以后直接將結果發布會導致個人隱私暴露[1,2]，若被不法分子加以利用會造成不良后果。就此問題，在利用大量私人數據進行數據挖掘用于生產的過程中，加強隱私保護并提高數據可用性是當前需要進一步解決的問題。現有的隱私保護方法大多基于k匿名[3]及其拓展模型[4-6]。由于這兩種模型都只能抵擋特定的攻擊方法，所以當面臨的攻擊者擁有強大的知識背景的情況下，這種隱私保護模型就難以對用戶的隱私信息提供有效的保護。差分隱私模型(differential privacy)的提出解決了上述的問題，此方法是向需公開的數據集或是被請求的數據集中加入擾動信息，從而避免隱私泄露[7]。近年來，有關差分隱私保護下的頻繁項集挖掘算法研究成果很多。BHASKAR.R是此算法的奠基人，提出了基于指數機制(exponential mechanism)和拉普拉斯機制(Laplace mechanism)的TF算法[8]。TF算法取前k個支持度高的作為頻繁項集，該方法避免了在加噪過程中導致的頻繁項集變不頻繁的傳輸誤差。并且滿足差分隱私保護的要求，缺點是當k較大時，此算法無法保證輸出數據的準確性。為了解決此問題，PrivBasis算法產生了。DP-topk算法先采用FP-Growth算法進行項集的挖掘，然后采用指數機制將事務進行數據截斷處理[9]，再采用拉普拉斯機制進行支持度加噪使其輸出的數據滿足差分隱私。這種將對支持度的處理后置的方法，降低了算法中加入的噪聲。

1 理論基礎與問題描述

1.1 差分隱私

差分隱私技術能達到保護數據中的個人隱私的目的是通過向采集的數據集中加入噪聲的方法，使得輸出的數據失真，并且產生的結果不再為一固定值，而是具有隨機性；結果的隨機性可以保證即使攻擊者擁有相關的一系列相關的知識背景，也無法獲取原始數據集。從而保護了用戶隱私[10]。

定義1 鄰近數據集：設一個數據集為一個集合N={n1,n2,…nm}，另一個數據集為N′={n′1,n′2,…n′m}，若這兩個集合中只有一個ni≠n′i，其余都相等。則稱這一對數據集為鄰近數據集。

定義2ε-差分隱私[11]：將算法K作用在兩個相鄰數據集N與N′上，輸出S為K值域的子集。若算法K滿足不等式(1)，則算法K滿足ε-差分隱私，ε表示隱私保護的標準

Pr[K(N)∈S]≤eε×Pr[K(N′)∈S]

(1)

定義3 全局敏感度[12]：對于任何查詢函數q，我們將Δq定義為當應用于查詢函數的兩個相鄰數據集的輸入時，輸出結果的最大的差異

(2)

定理1 差分隱私保護的串行性質：設N是一個數據集，若n個查詢算法K={K1,K2,…,Kn} 同時作用于這個數據集上，并且每個查詢算法對數據集N進行隱私保護處理以后，都能保證算法輸出結果滿足ε-差分隱私保護，則稱這一系列算法所構成的組合滿足ε-差分隱私保護。

1.2 保護模型

目前差分隱私保護模型主要有兩種，分別是拉普拉斯機制和指數機制。這兩種機制分別適用于不同的數據類型，前者適合在連續型數據中加噪，后者適用于離散型數據中加噪，兩者都是通過對所要發布的或是被請求的原始數據集添加擾動機制來進行數據隱私保護，并從數學意義角度嚴格定義了一種隱私理論的框架。

定理2 拉普拉斯機制(Laplace mechanism)[13]：其基本思想是對數據集N用查詢函數q進行查詢，再向查詢結果中加入滿足拉普拉斯噪聲分布的x，其概率密度函數為

(3)

對于函數q：N→Rn來說，如果差分隱私算法M的輸出結果滿足式(4)，則M滿足ε-差分隱私算法。可以看出，全局敏感度與噪聲大小成正比

(4)

定理3 指數機制(exponential mechanism)[14]：指數機制由一個可能輸出的有限集O(稱為范圍)和一個實值函數q：Dn×R×R參數化，它根據輸入算法M，為每個可能的輸出r分配一個分數q(M，r)。給定O、q、T和ε，產生盡可能高分數的輸出結果。若算法M滿足式(5)，則隱私保護算法M提供ε-差分隱私保護

(5)

由式(5)可知，評價函數是關鍵，評價分數越高的時候輸出項r被選擇輸出的概率也就越大。

1.3 問題描述

頻繁項集挖掘[15]過程中進行隱私保護，多采用對支持度進行拉普拉斯加噪方式提供ε-差分隱私保護。拉普拉斯加噪機制主要是將函數的全局敏感度和差分隱私預算的比值作為主要調節的參數，用來控制加噪的大小。由定義2可知，當輸入兩個相鄰數據集后，輸出的概率比值無限接近于1時，此結果表明隱私預算ε很小的前提下，對于相鄰數據集結果進行查詢，得出同一結果的概率非常相近，即隱私保護水平越高。當ε趨于0時，加入的噪聲非常大，會導致數據可用性很低。并且根據全局敏感度的定義可以知道，全局敏感度越大對應添加的噪聲越大，以至于數據的可用性越低。為了增加數據可用性，可以通過降低全局敏感度的方式解決問題。又因為相鄰數據集可以等效為對同一數據集增加一條事務或減少一條事務，由此可知，當數據集增加一條很長的事務，這條事務中每個項的支持度也會對應增加1，這會導致敏感度大幅增長。根據敏感度增加的問題，本文采取限制事務長度的辦法，進而降低敏感度、提高數據集的可用性。

2 基于事務分離的差分隱私頻繁項集挖掘

現有限制事務最大長度的方法是在挖掘頻繁項的過程中，先將較長的事務中的非頻繁項剔除，但當一個事務包含過多的頻繁項集的情況下，即使去除了非頻繁項，該事務的長度依舊大于事務最大事務限制長度，采取事務截斷的方法進行處理。首先將項進行支持度從高到低排序，然后從最后一項開始截斷，直到事務滿足最大限制長度以后才停止階段。這種方法雖然可以降低敏感度，但此方法必然會導致截斷誤差，項的支持度變小以后會影響頻繁項集的生成從而導致結果的不準確。因此本文提出事務分離的方法，將長事務分離成多個短事務，避免了截斷誤差的產生。

2.1 基于指數機制的事務分離

在介紹基于指數機制的事務分離方法之前，首先說明項集與事務之間的距離的定義。

定義4 事務與項集之間的距離：現有事務T1和項集ci，則事務T1和項集ci之間的距離定義為

di=len(ci)-|T1∩ci|

(6)

其中，len(ci)為項集ci的長度，即ci中包含多少個項，而 |T1∩ci| 表示為項集ci事務T1中重復數據項的個數。

算法1采用差分隱私的指數機制來選擇防止泄露事務數據集信息。設計質量函數q，進而對所有可能的事務長度進行打分，遍歷最優限制比例S(S∈(0,1))，求得當輸出頻繁項集可用性最高時S的值，然后通過指數機制進行選擇事務最大限制長度。首先掃描數據集D中每條事務i的長度Zi及此條事務中最小支持度項Supzi。將數據集D按照事務長度從小到大排序為D。然后根據指數機制設計質量函數q(D′,zi)。當升序后的數據集長度和最優限制比例的乘積等于zj(j

由指數機制公式

(7)

其中，Δq為全局敏感度函數，其最大值為Supzi。根據式(5)可知，長度zj為限制事務最大長度的概率為公式

(8)

基于指數機制的事務分離算法由算法1和算法2組成。

算法1：Exponential_length

輸入：初始數據集D，隱私預算ε1，最優分離比例S

輸出：最大限制事務長度L

(1) Apriori(D)→候選1-頻繁項集及其對應的支持度

(2) for每條事務i∈D

(3) 按照事務長度zi降序排序

(4) 獲取項最小支持度Supzi

(5) end for

(6) returnD′

(7) fori∈D′

(8) 設計質量函數

(10) end for

(11) 根據Pr(L=zj)隨機選擇事務長度作為最大限制事務長度L

通過算法1得到最大限制事務長度L以后，進行長事務到短事務的分離。

算法2：事務分離

輸入：事務T，候選項集Ci，事務最大限制長度L

輸出：子事務集TM

(1)TM→?，Tm=?

(2)C′i={ci&Ci&&ci∈T}

(3) whileC′i≠? do

(4) 隨機選擇ci添加入Tm并delci

(5) while |Tm|

(6)a=ci∩Tm

(7)di=len(ci)-a

(8) pickciwith minimum ofdifromC′

(9) if |ci∩Tm|≤Lthen

(10) 將ci添加到Tm中；

(11) end if

(12) 從C′中刪除ci

(13) 將Tm添加到TM中

(14)m++

(15) end while

(16) returnTM

具體描述在確定最大限制事務長度以后，將長事務t進行分離。首先挖掘頻繁1-項集，進行長事務第一次分離，將不頻繁項舍去，進而挖掘候選頻繁2-項集，每次挖掘頻繁項集時都對長事務進行一次分離。在挖掘出候選頻繁k-項集以后，首先從包含于事務T的潛在頻繁k-項集集合C中隨機選擇一個項集，添加進事務T1中；然后計算C中余下的每個Ci與T1之間的距離di。挑選出距離最小的Ci，并剔除Ci與T1中重復的數據項，將剩余的數據項添加進T1中。然后再將此步驟重復，循環往復的計算距離、剔除重復并添加數據項，直到將集合C中的數據項剔除完。在這個過程中，將距離最小的項添加進T1的同時要判斷T1的長度，若大于最大限制長度則繼續剔除，當等于最大限制長度的時候，建立T2，并且此事務長度為0，將Ci中剩余的項集重復計算距離、挑選最短距離的項、剔除重復項、這3個步驟，將數據項步驟添入事務T2中，完成對長事務的分離。

2.2 基于雙閾值的頻繁項集挖掘

在拉普拉斯加噪過程中，由于拉普拉斯函數的特性，可能會產生正向和負向的噪聲，因此當噪聲過大的時候會產生支持度大于頻繁(k-1)-項的k-頻繁項，違背了Apriori頻繁項集挖掘的先驗定理。對于此問題，采取設置兩個不同的支持度閾值的辦法來解決。首先給定一個項集X的噪聲支持度，分析該概率方式計算其在原始數據庫中的支持度。第二步量化了加噪過程中的信息損失。假設在包含子項集X的不同事務之間存在均勻的分布。使用一個項集的平均信息損失來檢查它是否頻繁，以及使用最大的信息損失來確定是否使用它來生成候選項集。因此，鑒于有噪聲的支持度，已經改變了閾值，以確定X是否頻繁，以及是否使用X來生成(k+1)項集為用此方法放松這兩個閾值。

給定k-項子集Y，Y的真實支持度計數用Rs表達、項集的噪聲支持用Ns表達。 Pr(Rsi|Ns) 是用噪聲支持度去估計真實支持度的條件概率

(9)

在加入噪聲前，項集Y的真實支持度數值在加入噪聲之前其分布可認為是在其值域內的均勻分布，即P(Rs1)=P(Rs2)=…P(Rsm)=1/m。因此，上式可簡化為

(10)

由于采用拉普拉斯機制，則

(11)

又Pr(Nc|Rcj) 積分值為1，由此可得

(12)

在加噪后，(k-1)-項集支持度小于k-項集支持度時，對兩者的支持度進行修正，都將其降低或增加為兩者的中值。用此方法對支持度進行調整以后，使其符合先驗定理，提高了數據的可用性。

頻繁k-項集挖掘算法如下：

算法3：頻繁k-項集挖掘

輸入：原始數據集D；隱私預算ε1、ε2；最小支持度閾值Supmin；(k-1)-項集集合Gk-1；事務最大限制長度L；最大事務長度限制比例S；

輸出：頻繁k-項集集合Fk；生成候選項集的項集集合Gk

(1) 事務分離策略(D,Gk-1,S,ε1)→D′

(2) 通過Lk-1生成候選k-頻繁項集Ck

(3) for ?k-項集 inD′

(4)Supk=Supk+Lap(CLk/ε1/k-1)

(5) 當Supk≥Supmin時，將此k-項集加入Fk

(6) if存在Supk-1

(7)Supk=(Supk+Supk-1)/2，Supk-1=(Supk+Supk-1)/2

(9) 將k-項集加入Gk

(10) end for

(11) returnFk,Gk

由于支持度修正策略使用的數據為差分隱私保護后的帶噪頻繁項集及其支持度，根據差分隱私性質中的繼承性，可知修正支持度后的算法滿足ε-差分隱私。

2.3 隱私分析

為了檢驗基于指數機制的差分隱私頻繁項集挖掘方法是否滿足ε-差分隱私定義，需分別分析基于指數機制的限制事務最大長度計算方法和基于拉普拉斯機制添加噪聲的方法是否滿足ε1-差分隱私保護以及ε2-差分隱私保護。用FIM-TSDP表示本文提出的方法。

設M(D′) 是由長度升序排列后的數據集D′經過指數機制計算出的最大限制事務長度，此方法所分配的隱私預算為ε1，設D′和D″是鄰近數據集。根據ε-定義可得

(13)

可得Pr(M(D′)=L)≤eε1×Pr(M(D″)=L)。因此算法1滿足ε1-差分隱私保護的定義。

下面驗證加噪后的項集是否依然滿足嚴格的數學定義

(14)

D和D′為相鄰數據集，YNs、Gk為Y的噪聲支持度和真實支持度。又式 |YNs-YD′|-|YNs-YD|≤1。因此條件概率比值可化簡為

(15)

由此不等式可得，對支持度進行拉普拉斯加噪滿足ε2-差分隱私保護。并且調整支持度是在加噪后的支持度上修正的，因此也滿足差分隱私。可以驗證FIM-TSDP滿足ε-差分隱私保護。

3 實驗與分析

本實驗比較事務最大限制比例在不同事務數據集下對F-score的影響，以及算法FIM-TSDP和SmartTruncate在不同閾值下F-score和RE參數的對比。

F-score[16]為概括準確率和召回率關系的綜合性能指標。準確率表示預測正確的個數占總預測結果的概率；召回率準確結果并且被挖掘出來的概率。兩者間呈現負相關，為了平衡準確率和召回率的影響，使用F-score進行綜合評判，即F-score越高，數據集可用性越好

(16)

(17)

(18)

RE[16]則用于衡量算法輸出結果中項集支持度與真實支持度間的相對誤差。其定義為

(19)

Y是差分隱私保護下生成的頻繁項集，SupY是項Y的真實支持度，Sup′Y是項Y的噪聲支持度。RE越小說明誤差越小。

3.1 實驗數據與設置

實驗環境：Intel(R) Core(TM) i5-8265U CPU @ 1.60 GHz，4 GB內存，windows10 64位操作系統。采用python3.7語言進行實驗。實驗采用廣泛應用于頻繁項目集挖掘算法分析的數據集kosarak、retail和accident，表1總結了本實驗中所用數據集的參數設置。

表1 數據集信息

3.2 實驗結果與分析

為了說明事務最大限制長度對降低敏感度的有效性，實驗采取了3個特點的數據集，由于差分隱私算法的隨機性，實驗對每組數據重復進行10次實驗，并取其平均值。

設定k=100，總隱私預算ε=1.0，分析事務最大限制長度比例S取值不同時，分析不同S的取值對F-score以及RE的影響。

從圖1可以看出，隨著事務最大長度限制比例的增加，accident數據集F-score下降緩慢，是由于數據集隨著S的變化，事務最大長度沒有明顯的變化。而當事務最大限制長度比例較小的時候，kosarak數據集和retail數據集F-score明顯升高，說明了限制事務最大長度的方法有效降低了敏感度，提升了算法的可用性。

圖1 S在不同事務數據集下對F-score的影響

由圖2可知，在S=0.85時，3個點重合了，說明此時的總誤差較小，數據集可用性較高。從而后續實驗中都采取比例為0.85。并且從圖中可以看出將kosarak數據集進行長度限制時，隨著限制比例的變化，RE取值的變化最明顯。這是由于此數據集中事務長度分布不均，比較分散。并且由于限制事務最大長度通過指數機制進行挑選，會導致S的取值稍有變化會明顯影響RE。而accident與retail兩個數據集中事務長度相對集中，因此無論事務最大長度限制比例怎樣取值，經過指數機制挑選出的限制長度取值范圍很有限，這使得RE變化相對很小。由此可知，S取值越小，誤差越大，雖然全局敏感度更小了但是總誤差變大了。并且從圖1可知，隨著當S大于0.85以后，會導致誤差增大，增幅更快。由此可知，可推知分離誤差對可用性的影響比噪音誤差對可用性的影響更大。