基于屬性分割的高維二值數(shù)據(jù)差分隱私發(fā)布

洪金鑫 吳英杰 蔡劍平 孫 嵐

1(福州大學數(shù)學與計算機科學學院 福州 350108)2(廈門華廈學院信息與智能機電工程學院 福建廈門 361024)

隨著大數(shù)據(jù)產(chǎn)業(yè)的日趨成熟，在日常生活中有越來越多的數(shù)據(jù)被采集.通常這些數(shù)據(jù)蘊含著大量的隱私信息，例如交通數(shù)據(jù)中的個人移動軌跡、醫(yī)療數(shù)據(jù)中的病人患病記錄等.如果直接使用這些數(shù)據(jù)很有可能會導致隱私的泄露.因此在使用時需要采取一些措施來保證數(shù)據(jù)的隱私安全.

差分隱私[1-5]是一種嚴格可證的隱私保護技術(shù)，它通過向數(shù)據(jù)注入滿足特定分布的噪聲干擾，使攻擊者難以對特定的隱私數(shù)據(jù)進行精確的計算.經(jīng)過擾動后的數(shù)據(jù)仍然保留著原始的統(tǒng)計學特征，但攻擊者無法重構(gòu)出真實的原始數(shù)據(jù).這樣便能夠在保證數(shù)據(jù)安全的前提下，提高數(shù)據(jù)共享和使用的效率.

高維數(shù)據(jù)的隱私發(fā)布問題一直以來都是差分隱私領(lǐng)域里的一個研究熱點與難點問題.如何在有效地保護數(shù)據(jù)中隱私信息的同時保證數(shù)據(jù)的可用性是該問題的研究重點.當前已有許多基于差分隱私的高維數(shù)據(jù)發(fā)布方法，這些方法大體上可以分成2類:

1)通過對高維數(shù)據(jù)進行降維來減小擾動原始數(shù)據(jù)時產(chǎn)生的噪聲大小，主要包括主成分分析[6-9]、隨機投影[10-13]、仿射變換[14]、截斷分組[15-16]、PriView視圖[17]等方法.

2)通過構(gòu)建數(shù)據(jù)集的概率圖模型來計算數(shù)據(jù)屬性間的概率分布，然后對概率分布進行加噪，并用來生成合成數(shù)據(jù)發(fā)布，以此來避免直接擾動原始數(shù)據(jù)時產(chǎn)生的巨大噪聲干擾.這類方法主要有樸素貝葉斯分類器[18]、貝葉斯網(wǎng)絡[19-25]、Markov網(wǎng)絡[26-28]等.

第1類方法(降維方法)是一個比較簡單有效的方法，但是該類方法無法發(fā)布一個完整的高維數(shù)據(jù)集，這也限制了它的作用范圍.一般這類方法主要用于回答一些查詢操作或者作為數(shù)據(jù)挖掘、機器學習等領(lǐng)域的預處理方式.

第2類方法(概率圖模型方法)通過生成合成數(shù)據(jù)的方式，能夠發(fā)布一個完整的高維數(shù)據(jù)集，這使得它的適用范圍更加廣泛.

雖然現(xiàn)有的概率圖模型方法在一定程度上能夠解決高維數(shù)據(jù)的隱私發(fā)布問題，但當它應用于實際場景時，這些方法仍然存在著一些問題:

第一，這些方法都過于統(tǒng)一地認為屬性間是相互獨立或是相互關(guān)聯(lián)的.其實對于不同的數(shù)據(jù)集來說，它們屬性間的關(guān)聯(lián)性是不一樣的，有的屬性間是具有聯(lián)系的，有的屬性間是相互獨立的.為了能夠讓構(gòu)建的概率圖模型更符合真實的分布規(guī)律，就不能對這些關(guān)聯(lián)性不同的屬性一概而論.而是需要找到一種能夠識別屬性間不同關(guān)聯(lián)性的方法，并以此來將不相干的屬性分開處理.

第二，實現(xiàn)這些方法所需的時間復雜度普遍偏高.尤其是在構(gòu)建概率圖模型的過程中，大部分方法都使用了指數(shù)級時間復雜度的算法.雖然理論上這些方法都可適用于任意維度的高維數(shù)據(jù)，但是在實際使用時由于時間因素的影響，大多數(shù)的方法都只能處理到中低維數(shù)據(jù)，這明顯無法滿足實際應用的需求.

第三，這些方法中很少有針對高維二值數(shù)據(jù)的方法，以致于忽視了高維二值數(shù)據(jù)中存在的可以利用的性質(zhì)，例如利用條件概率在二值數(shù)據(jù)上的取值特點.導致在對概率分布加噪時很容易出現(xiàn)概率值大規(guī)模失真問題，使得后續(xù)由該概率分布生成的合成數(shù)據(jù)的精度下降.

為解決上述3個問題，本文提出了PrivSCBN(differentially private spectral clustering Bayesian network)方法.本文的主要貢獻包括4個方面:

1) 為了解決高維二值數(shù)據(jù)的差分隱私發(fā)布問題，本文提出了一種滿足差分隱私的高維二值數(shù)據(jù)發(fā)布方法PrivSCBN.該方法由3個子算法組成，每個子算法都滿足差分隱私的定義.然后基于每個子算法的噪聲公式，設計了一種策略來分配隱私預算ε.最后，通過實驗驗證了PrivSCBN方法在時間性能和發(fā)布精度上都要優(yōu)于現(xiàn)有的發(fā)布方法.

2) 為了解決不同屬性間關(guān)聯(lián)性不一致的問題.本文針對高維二值數(shù)據(jù)，設計了一種基于Jaccard距離的屬性間關(guān)聯(lián)程度衡量指標，并從理論論證了相比于常用的互信息，Jaccard距離在二值數(shù)據(jù)屬性上擁有更低的全局敏感度和更高的準確度.然后基于該衡量指標，本文提出了一種滿足差分隱私的譜聚類(differentially private spectral clustering, DPSC)算法來對數(shù)據(jù)屬性進行合理的劃分，然后根據(jù)劃分結(jié)果進一步分割原始數(shù)據(jù)集，以此達到獨立屬性分開處理和數(shù)據(jù)降維的雙重目的.

4) 為了解決概率分布加噪時容易出現(xiàn)的概率值失真問題.本文利用貝葉斯網(wǎng)絡最大入度數(shù)的限制和條件概率在二值數(shù)據(jù)上的取值特點，提出了一種概率分布加噪算法BNC(binary noisy conditionals)來為每個從貝葉斯網(wǎng)絡中提取的概率分布進行加噪，在一定程度上減少了出現(xiàn)概率值失真的問題.

1 相關(guān)工作

目前，概率圖模型方法已取得了一些研究成果.

Qardaji等人[17]針對高維二值數(shù)據(jù)的隱私保護問題提出了PriView方法，該方法假設所有屬性都是相互獨立，通過構(gòu)建一組帶噪聲的View視圖來回答用戶的α-way查詢.Zhang等人[19-20]針對高維數(shù)據(jù)隱私發(fā)布問題提出了PrivBayes方法，該方法認為屬性間都是相互關(guān)聯(lián)的，通過貪心算法GreedyBayes來構(gòu)建貝葉斯網(wǎng)絡，然后利用貝葉斯網(wǎng)絡和拉普拉斯機制計算出屬性間帶噪聲的條件分布，并通過貝葉斯網(wǎng)絡的近似推理來計算出所有屬性的聯(lián)合分布，最后基于這個聯(lián)合分布來生成合成數(shù)據(jù)發(fā)布.在PrivBayes方法的基礎(chǔ)上，加權(quán)PrivBayes[21]、平滑PrivBayes[22]、PrivBayes_Hierarchical[23]等一系列方法被相繼被提出.王良等人[21]提出了加權(quán)Priv-Bayes方法，該方法認為不同屬性的敏感程度是不一樣的，并不能一概而論，因此該方法通過為每個屬性分配一個權(quán)值，然后在構(gòu)建貝葉斯網(wǎng)絡的過程中優(yōu)先選擇權(quán)值高的屬性結(jié)點，以此來構(gòu)建更好的貝葉斯網(wǎng)絡.Li等人[22]提出了平滑PrivBayes方法，該法方法引入了差分隱私的平滑敏感度機制，使其能夠在犧牲部分隱私保護程度的情況下減少產(chǎn)生的噪聲大小，從而提高聯(lián)合分布的精度.郝志峰等人[23]提出了PrivBayes_Hierarchical方法，該方法利用語義樹來對數(shù)據(jù)屬性的語義層次關(guān)系進行抽象，然后在構(gòu)建貝葉斯網(wǎng)絡的過程中考慮父結(jié)點的語義層級對子結(jié)點的影響，從而能夠平衡數(shù)據(jù)的可用性與安全性.

除了基于貝葉斯網(wǎng)絡的有向圖模型方法，還有基于Markov網(wǎng)絡的無向圖模型方法.Chen等人[26]提出了Jtree方法，該方法先是使用基于稀疏向量的采樣技術(shù)來探索屬性間的關(guān)系，然后基于這些關(guān)系來構(gòu)建Markov網(wǎng)絡，接著將該網(wǎng)絡分割成若干個完全團，并基于這些完全團通過聯(lián)合樹算法和拉普拉斯機制計算出屬性間帶噪聲的聯(lián)合分布.張嘯劍等人[27]在Jtree方法的基礎(chǔ)之上提出了PrivHD方法，該方法通過高通濾波技術(shù)來加速Markov網(wǎng)絡的構(gòu)建，然后利用最大生成樹算法來構(gòu)建更好的聯(lián)合樹.

從這些分析中可以看出，現(xiàn)有的概率圖模型方法主要集中在研究如何更好更快地構(gòu)建概率圖模型、減少產(chǎn)生的噪聲干擾、獲得更準確的概率分布值，從而生成更高精度的合成數(shù)據(jù).但是這些方法仍然存在著時間復雜度過高、沒有考慮屬性間不同程度的關(guān)聯(lián)性、注入的噪聲過大導致概率值失真等問題.為此本文提出了PrivSCBN方法來進行解決.

2 理論與定義

2.1 差分隱私

定義1.ε-差分隱私[1].設兄弟數(shù)據(jù)集D和D′，它們彼此相差1條記錄.給定1個隨機算法A，若A滿足ε-差分隱私，則有

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

(1)

其中，ε表示隱私預算，預算越小則隱私的保護程度就越高.Pr[A(D)=O]，Pr[A(D′)=O]分別表示算法A在數(shù)據(jù)集D和D′上輸出為O的概率.

實現(xiàn)差分隱私的機制主要有拉普拉斯機制[2]和指數(shù)機制[3].這2種機制產(chǎn)生的噪聲大小與查詢函數(shù)的全局敏感度有關(guān).

定義2.全局敏感度[2].設查詢函數(shù)f:D→n，其全局敏感度定義為

(2)

定理1.拉普拉斯機制[2].設查詢函數(shù)f:D→n，給定1個隨機算法A，若A滿足ε-差分隱私，則有

A(D)=f(D)+Lap(Δf/ε),

(3)

其中，Lap(Δf/ε)表示滿足拉普拉斯分布的噪聲變量.隱私預算ε越大或全局敏感度Δf越小，產(chǎn)生的噪聲就越小.

定理2.指數(shù)機制[3].設評分函數(shù)u(x)表示輸出結(jié)果為x的評分，給定一個隨機算法A，若A滿足ε-差分隱私，則有

(4)

其中，Δu表示評分函數(shù)u(x)的全局敏感度.輸出Oi的評分越高，則被選中的概率就越大.

此外，在設計和證明滿足差分隱私的算法過程中，需要用到2條重要的差分隱私組合性質(zhì).

性質(zhì)2.并行組合性質(zhì)[4].給定數(shù)據(jù)集D，將D分割成m個互不相交的子集D={D1,D2,…,Dm}.設算法A1(D1),A2(D2),…,Am(Dm)均各自滿足ε-差分隱私，并且任意2個算法的隨機過程相互獨立.那么這些算法的組合算法A也滿足ε-差分隱私.

2.2 譜聚類

譜聚類(spectral clustering)[28]是一種基于圖論的分割式聚類方法，通常能夠收斂于全局最優(yōu)解.它的作用機理是先將數(shù)據(jù)集映射成一張帶權(quán)無向圖，然后通過對圖中的結(jié)點進行分割，使得子圖內(nèi)部的結(jié)點盡量相似，子圖外部的結(jié)點盡量不同.

標準的譜聚類算法實現(xiàn)過程如算法1所示:

算法1.譜聚類算法.

輸入:數(shù)據(jù)集D={x1,x2,…,xn}、類簇個數(shù)k、尺度參數(shù)σ;

輸出:分割結(jié)果集C={C1,C2,…,Ck}.

① 使用式(5)計算n×n的距離矩陣W:

(5)

② 使用式(6)計算n×n的相似度矩陣A:

(6)

③ 使用式(7)計算n×n的度矩陣B:

(7)

④ 計算拉普拉斯矩陣L=B-1/2(B-A)B-1/2;

⑤ 計算L的特征值，然后從小到大排序，取前k個特征值計算其特征向量u1,u2,…,uk;

⑥ 將k個特征向量(列向量)組成n×k的矩陣U=(u1,u2,…,uk)，令yi為矩陣U的第i行向量，并對其進行單位化yi=yi/|yi|;

⑦ 使用k-means聚類算法對新樣本點Y={y1,y2,…,ym}進行劃分得到劃分結(jié)果C;

⑧ returnC.

算法1中的拉普拉斯矩陣L是對稱的半正定矩陣，可以計算出n個非負實數(shù)的特征值和n個對應的特征向量.因此，該算法最終一定可以得到k個聚類的結(jié)果.

2.3 貝葉斯網(wǎng)絡

貝葉斯網(wǎng)絡(Bayesian network)是一種概率圖模型，主要用來探索一組隨機變量之間的關(guān)系.貝葉斯網(wǎng)絡通常使用1張有向無環(huán)圖來表示，圖中結(jié)點代表隨機變量、邊代表隨機變量之間的關(guān)系.

例如圖1是1張擁有5個結(jié)點的貝葉斯網(wǎng)絡圖，該網(wǎng)絡的最大入度數(shù)為3.

Fig. 1 Bayesian network of 5 nodes

一般給定一組屬性S={S1,S2,…,Sm}，由條件概率的鏈式法則可得這組屬性的聯(lián)合分布為

Pr[S]=Pr[S1]×Pr[S2|S1]×…×Pr[Sm|S1,…,Sm-1],

(8)

通過貝葉斯網(wǎng)絡可將該聯(lián)合分布近似為

(9)

表1顯示了圖1中各個結(jié)點的父結(jié)點集:

Table 1 Parent Set of Each Node in Bayesian Network

利用式(9)，可得該屬性集的近似聯(lián)合分布為

(10)

實際上越復雜的貝葉斯網(wǎng)絡所蘊含的信息就越豐富，計算出來的聯(lián)合分布也會越接近真實的分布規(guī)律.但由于時間因素的影響，通常在構(gòu)建貝葉斯網(wǎng)絡時會限制整個網(wǎng)絡的最大入度數(shù)，以此來降低構(gòu)建網(wǎng)絡所需的時間成本.

2.4 互信息

互信息常用來表示1個變量由于已知另一個變量所能減少的不確定程度.互信息也可以用于衡量2個屬性間的相互依賴程度.互信息越大，則屬性間的相互依賴程度就越高.

定義3.互信息.給定2個離散的隨機變量X∈{x1,x2,…,xn},Y∈{y1,y2,…,ym}，它們間的互信息為

(11)

其中，Pr[xi,yj]表示隨機變量X,Y取值為xi,yj的聯(lián)合分布.當I(X,Y)→0時，有Pr[xi,yj]→Pr[xi]Pr[yj]，即隨機變量X與Y接近于相互獨立.

2.5 Jaccard距離

Jaccard距離常用來表示2個集合間的差異程度.距離越小，集合間的差異程度就越小.

定義4.Jaccard距離.給定2個集合X,Y，它們之間的Jaccard距離為

(12)

Jaccard距離也可以用來表示同一數(shù)據(jù)集中2個二值屬性間的差異程度.

假設給定2個二值屬性X,Y，它們?nèi)≈禐閄=1,Y=1的數(shù)據(jù)量為n11，取值為X=0,Y=1的數(shù)據(jù)量為n01，取值為X=1,Y=0的數(shù)據(jù)量為n10.那么這2個屬性之間的Jaccard距離為

(13)

可以看出距離越小，屬性間的關(guān)聯(lián)程度就越高.

3 PrivSCBN算法

3.1 概 述

PrivSCBN算法的整體流程如圖2所示:

Fig. 2 PrivSCBN algorithm flowchart

PrivSCBN算法的實現(xiàn)過程如算法2所示:

算法2.PrivSCBN算法.

輸入:數(shù)據(jù)集D={x1,x2,…,xn}、屬性集S={S1,S2,…,Sm}、類簇個數(shù)k、尺度參數(shù)σ、最大入度數(shù)d、隱私預算ε;

① 計算a1=(m-1)/(n-1)，a2=2m/(nk)，a3=2m/(nk)，并計算a=a1+a2+a3;

② 計算ε1=(a1/a)ε，ε2=(a2/a)ε，ε3=(a3/a)ε;

③ 求屬性劃分結(jié)果集C={C1,C2,…,Ck}←DPSC(D,S,k,σ,ε1);

④ 依據(jù)C分割原始數(shù)據(jù)集D={D1,D2,…,Dk};

⑥ fori=1 tokdo

⑩ end for

PrivSCBN算法可以拆解成4個獨立的步驟:

1) 通過DPSC算法將屬性集S劃分成k個屬性子集C1,C2,…,Ck，然后根據(jù)這些子集將原始數(shù)據(jù)集D分割成k個互不相交的數(shù)據(jù)集子集D1,D2,…,Dk.

(14)

(15)

(16)

故可得隱私預算ε1，ε2，ε3的分配策略為ε1=(((m-1)/(n-1))/a)ε，ε2=((2m/(nk))/a)ε，ε3=((2m/(nk))/a)ε，而a=(m-1)/(n-1)+2m/(nk)+2m/(nk).

最后，說明PrivSCBN算法滿足ε-差分隱私.由3.2～3.4節(jié)的最后一段滿足差分隱私性質(zhì)的說明可知，步驟③⑦⑧中的DPSC，F(xiàn)GB，BNC算法均各自滿足ε1，ε2，ε3-差分隱私.雖然其中的FGB和BNC算法會被執(zhí)行k次，但每次執(zhí)行所使用的數(shù)據(jù)集Di之間是沒有交集的.由性質(zhì)2可知，它們?nèi)匀粷M足ε2，ε3-差分隱私.并且除了上述的3個算法之外，PrivSCBN算法沒有其他地方再涉及原始數(shù)據(jù)集D的使用.因此，由性質(zhì)1可知，整個PrivSCBN算法滿足ε=(ε1+ε2+ε3)-差分隱私.

3.2 差分隱私譜聚類算法

由于高維數(shù)據(jù)的來源非常廣泛，其屬性間的關(guān)系錯綜復雜，即有的屬性間是具有聯(lián)系的、有的屬性間是相互獨立的.一般在構(gòu)建概率圖模型時，是希望模型能夠很好地反映出這些屬性間的關(guān)系.但由于高維數(shù)據(jù)中可能存在著毫無因果關(guān)系的屬性對，而如果將這些屬性對放到一起來構(gòu)建概率圖模型，那么得到的模型將無法很好地反映真實的分布規(guī)律.因為，這時引入了一些全局無關(guān)的變量(屬性)，導致模型為這些無關(guān)的變量建立了有關(guān)的聯(lián)系.舉個例子，給定一個屬性集S，滿足下標奇偶性相同的屬性間是具有聯(lián)系的、奇偶性不同的屬性間是相互獨立的.如圖3所示:

Fig. 3 Black and white node network diagram

從圖3可以看出通過將黑白結(jié)點分開并分別構(gòu)建網(wǎng)絡圖，可以消除圖中所有錯誤的依賴關(guān)系.當然這是在能夠?qū)⒑诎捉Y(jié)點完全區(qū)分開來的最理想條件下實現(xiàn)的，但在一般情況下是無法完全將它們區(qū)分開的.因此，如何找到一種較好的區(qū)分方法是本文研究的重點.為此本文提出了一種滿足差分隱私的譜聚類算法DPSC來對數(shù)據(jù)集屬性進行合理的劃分.

考慮如何衡量屬性間的關(guān)聯(lián)程度，一個比較常用的方法是使用互信息來進行衡量.但是這在處理高維二值數(shù)據(jù)時可能遇到一個問題，那就是高維二值數(shù)據(jù)通常是稀疏型數(shù)據(jù)，其中存在大量同時取值為0的屬性對.而在一般的高維二值數(shù)據(jù)中能夠反映出客觀規(guī)律的是同時取值為1的屬性對.因此，如果使用互信息來作為衡量指標，那么會很容易得出所有屬性都是具有聯(lián)系的這種無效結(jié)論.而由式(13)可知Jaccard距離是不會考慮這種情況的，并且它也能很好地反映出2個屬性間的差異程度.因此，DPSC算法采用Jaccard距離來作為屬性間關(guān)聯(lián)程度的衡量指標.

DPSC算法的實現(xiàn)過程如算法3所示:

算法3.DPSC算法.

輸入:數(shù)據(jù)集D={x1,x2,…,xn}、屬性集S={S1,S2,…,Sm}、類簇個數(shù)k、尺度參數(shù)σ、隱私預算ε1;

輸出:屬性劃分結(jié)果C={C1,C2,…,Ck}.

① 使用式(17)計算m×m的距離矩陣W:

(17)

② 執(zhí)行算法1的步驟②～⑥;

③ 使用k-means++聚類算法對新樣本點Y={y1,y2,…,ym}進行劃分得到劃分結(jié)果C;

④ returnC.

DPSC算法先將屬性集S映射成一張帶權(quán)無向圖.圖中以每個屬性Si(1≤i≤m)作為頂點，以屬性間的關(guān)聯(lián)程度作為邊權(quán)，邊權(quán)使用的是屬性間的Jaccard距離進行度量.由于在計算邊權(quán)時涉及到了原始數(shù)據(jù)集D的使用，為了保護數(shù)據(jù)中的隱私信息不被泄露，我們需要對計算結(jié)果進行擾動.這里使用拉普拉斯機制來進行擾動，擾動所產(chǎn)生的噪聲大小與邊權(quán)函數(shù)的全局敏感度有關(guān).因此，我們需要先考慮Jaccard距離的全局敏感度大小.

定理3.Jaccard距離的全局敏感度為ΔJ=1/(n-1).

證明.根據(jù)式(13)，不失一般性地假設n11+n01+n10=n，并且令x=n11.考慮減少一條記錄給dJ(X,Y)帶來的影響，存在2種情況:

1) 減少的是X=1,Y=1的記錄，根據(jù)式(2)有

(18)

2) 減少的是X=0,Y=1或X=1,Y=0的記錄，同樣由式(2)有

(19)

同理，當增加一條記錄時，有ΔJ+=1/(n-1)成立.

綜上所述，Jaccard距離的全局敏感度為ΔJ=max(ΔJ-,ΔJ+)=1/(n-1).

證畢.

實際上對于互信息，由Zhang等人[19]的論文可知，互信息在二值屬性上的全局敏感度ΔI為

(20)

很明顯相對于Jaccard距離ΔJ=1/(n-1)的全局敏感度，互信息的全局敏感度要來得更大.根據(jù)式(3)可知相比于互信息，使用Jaccard距離產(chǎn)生的拉普拉斯噪聲大小會更小.

在確定完邊權(quán)的全局敏感度之后，DPSC算法會對每個邊權(quán)值進行加噪，這個加噪過程會進行多次.由性質(zhì)1可知每次加噪都需要分配一部分的隱私預算.因此需要先確定加噪的總次數(shù)，即構(gòu)建距離矩陣W總共需要查詢原始數(shù)據(jù)集D的次數(shù).

綜上所述，我們可以得到加入邊權(quán)函數(shù)的拉普拉斯噪聲大小為

(21)

此外DPSC算法為了能夠進一步提升屬性的聚類效果，我們將原本算法1步驟⑦使用的k-means聚類算法換成了k-means++算法.該算法在初始點的選擇上更為合理，因此能夠產(chǎn)生更好的聚類效果.

在聚類完成后，算法會根據(jù)得到的樣本點Y的聚類情況，按照樣本點y1對應屬性S1，樣本點y2對應屬性S2，…，樣本點ym對應屬性Sm的對應規(guī)則，將每個屬性分配到其所對應的樣本點所在的類簇中，這樣就完成了對數(shù)據(jù)屬性的劃分.

3.3 差分隱私貝葉斯網(wǎng)絡算法

在現(xiàn)有的貝葉斯網(wǎng)絡模型方法中，大多都是使用由Zhang等人[19]提出的GreedyBayes算法來構(gòu)建貝葉斯網(wǎng)絡.該算法基于貪心的思想，即通過枚舉所有的情況，選擇能夠使整個貝葉斯網(wǎng)絡的互信息量達到最大的網(wǎng)絡結(jié)構(gòu)進行構(gòu)造.

GreedyBayes算法的實現(xiàn)過程如算法4所示:

算法4.GreedyBayes算法.

輸入:數(shù)據(jù)集D={x1,x2,…,xn}、屬性集S={S1,S2,…,Sm}、最大入度數(shù)d;

③ fori=2 tomdo

④ 初始化集合Ω=?;

⑦ end for

由于Zhang等人[19]在論文中沒有給出該算法具體的時間復雜度公式，故本文先對GreedyBayes算法的時間復雜度進行論證.

(22)

在最壞情況下，即d+2=(m+1)/2時，有

(23)

證畢.

很明顯由于時間復雜度的影響，GreedyBayes算法僅能適用于屬性維度m較小或者貝葉斯網(wǎng)絡最大入度數(shù)d很小的情況.

為了能夠更直觀地說明，我們以含有50個屬性的數(shù)據(jù)集為例.當貝葉斯網(wǎng)絡的最大入度數(shù)d分別為5，10，15，20，25時，GreedyBayes算法所需要枚舉的(Si,Πi)對的個數(shù)如表2所示:

Table 2 Enumeration Number of GreedyBayes Algorithm

從表2中可以看出，假設計算機每秒可以計算1萬個(Si,Πi)對的互信息.當最大入度數(shù)d=10時，就已經(jīng)需要184天每天24 h的不間斷處理才能完成.而當d=25時，就變得連計算機也無法解決，因為它一共需要728年零11天每天24 h的不間斷處理時間才能完成任務.

為了能夠“真正”地處理高維數(shù)據(jù)、構(gòu)建更復雜的貝葉斯網(wǎng)絡，本文提出了一種簡潔高效的貝葉斯網(wǎng)絡快速構(gòu)建算法FGB.該算法只需要O(nm2d2)的時間就能夠構(gòu)建出一個完整的貝葉斯網(wǎng)絡.

FGB算法的實現(xiàn)過程如算法5所示:

算法5.FGB算法.

輸入:數(shù)據(jù)集子集Di={x1,x2,…,xn}、屬性子集Ci={S1,S2,…,S|Ci|}、最大入度數(shù)d、隱私預算ε2;

③ fort=2 to |Ci| do

④ 初始化集合Ω=?;

⑤ 對每個Sj∈CiV和Πj←DPBestParent(Di,Sj,fa,min(t-1,d))，將(Sj,Πj)加入Ω;

⑦ end for

由算法4和算法5可知，F(xiàn)GB與GreedyBayes算法的一個主要區(qū)別在于步驟⑤求解每個待選結(jié)點的最佳父結(jié)點集的過程.FGB使用了一個時間復雜度為O(nd2)的算法DPBestParent來進行求解.而GreedyBayes算法是通過枚舉所有的情況，然后從中選擇最優(yōu)的.實際上在枚舉的過程中是存在著大量的重復計算和無意義計算的.而FGB算法利用了動態(tài)規(guī)劃的記憶化手段和最優(yōu)子結(jié)構(gòu)特性，在保證解是當前最優(yōu)解的前提下極大地減少了大量的重復計算和無意義計算.這在很大程度上提升了貝葉斯網(wǎng)絡的構(gòu)建速度.

DPBestParent算法的實現(xiàn)過程如算法6所示:

算法6.DPBestParent算法.

輸入:數(shù)據(jù)集Di={x1,x2,…,xn}、屬性Sj、新增父屬性fa、當前最大入度數(shù)d′;

輸出:最佳父屬性集Πj.

①dp[Sj,0]=?;

② forl=d′ to 1 do

③Π′=dp[Sj,l-1]∪fa;

④Π″=dp[Sj,l];

⑥ end for

⑦Πj=dp[Sj,d′];

⑧ returnΠj.

算法6中dp[Sj,l]表示結(jié)點集合，含義是結(jié)點Sj選擇l個結(jié)點作為父結(jié)點的最佳選擇情況.從步驟②～⑥的for循環(huán)中可以看出，實際上在新一輪的DPBestParent算法執(zhí)行時，dp[Sj,l]就已經(jīng)記錄了上一輪中在該狀態(tài)下的最佳父結(jié)點集的選擇情況.因此對于本輪來說，只需要關(guān)心上一輪新加入網(wǎng)絡的結(jié)點fa對當前最佳父結(jié)點集的選擇情況的影響即可.這里for循環(huán)采用的是倒序遍歷的方式，即從d′到1.其原因是為了保證當前更新的狀態(tài)不會影響到下一次的狀態(tài)更新，這個操作避免了結(jié)點fa被加入到同一個父結(jié)點集多次.

接下來證明FGB算法的時間復雜度.

定理5.FGB算法的時間復雜度為O(nm2d2).

證明.FGB算法的時間消耗主要集中在步驟③～⑦的for循環(huán).該for循環(huán)一共會執(zhí)行|Ci|-1次.

對于步驟⑤，循環(huán)每次執(zhí)行時都會調(diào)用|Ci|-t(t∈[1,|Ci|-1])次 DPBestParentSet子算法，而每次調(diào)用子算法所需的時間為O(nd2).因此，執(zhí)行完|Ci|-1次步驟⑤所需的總時間復雜度為O(n|Ci|2d2).

對于步驟⑥，循環(huán)每次都會為|Ci|-t個待選組合(St,Πt) 計算其被選擇的概率Pc(St,Πt)，而每次計算所需的時間為O(nd).因此，執(zhí)行完|Ci|-1次步驟⑥所需的總時間復雜度為O(n|Ci|2d).

又因為每個屬性子集的大小|Ci|∝m.因此，整個FGB算法的時間復雜度為O(nm2d2).

證畢.

除了解決GreedyBayes算法在執(zhí)行效率上的問題之外，F(xiàn)GB算法還引入了差分隱私指數(shù)機制來擾動貝葉斯網(wǎng)絡的構(gòu)建過程(步驟⑥)，從而解決了構(gòu)建的貝葉斯網(wǎng)絡存在隱私泄露風險的問題.

差分隱私指數(shù)機制的思想是依據(jù)評分函數(shù)以一定的概率來選擇當前加入貝葉斯網(wǎng)絡的(Si,Πi)對.我們使用互信息I來作為指數(shù)機制的評分函數(shù)u(S,Π)=I(S,Π).當(S,Π)對的互信息越大時，評分函數(shù)u(S,Π)的值就越高，則被選擇的概率也就越大.由式(20)可知，該評分函數(shù)的全局敏感度為

(24)

雖然Zhang等人[19]在PrivBayes方法中提出了一種全局敏感度更低的評分函數(shù)F，其全局敏感度僅為ΔF=1/n.但計算該評分函數(shù)所需的時間為O(n2d)，僅能適用于構(gòu)建d較小的貝葉斯網(wǎng)絡.因此本文不采用該方法，仍然使用互信息作為評分函數(shù).

在執(zhí)行FGB算法之前，PriveSCBN算法(算法2)的步驟④會將原始數(shù)據(jù)集D分割成k個相互獨立的數(shù)據(jù)集子集Di.由性質(zhì)2可知，處理這些子集的過程可以共享同一個隱私預算.

FGB算法會執(zhí)行步驟⑥共|Ci|-1次，每次都需要使用指數(shù)機制從Ω中選擇一個(St,Πt)對加入貝葉斯網(wǎng)絡.由性質(zhì)1可知，每次選擇都會消耗一部分的隱私預算.這里采用平均分配的方式，即將隱私預算ε2平均分成|Ci|份.結(jié)合指數(shù)機制，可得概率值Pc(St,Πt)的表達式為

(25)

其中，u表示評分函數(shù)，Δu表示評分函數(shù)的全局敏感度，Ω表示當前所有可選的組合情況.

3.4 差分隱私條件分布計算

通過貝葉斯網(wǎng)絡可以在很大程度上簡化聯(lián)合分布的計算過程，并且越好的貝葉斯網(wǎng)絡計算出來的聯(lián)合分布越接近真實值.但是如果直接使用貝葉斯網(wǎng)絡來進行計算，很有可能會導致隱私的泄露.因此，我們需要對計算出來的聯(lián)合分布做進一步的擾動，以此來達到保護隱私的目的.

Zhang等人[19]在論文中使用NoisyConditionals算法來實現(xiàn)貝葉斯網(wǎng)絡的安全計算.該算法通過向每個結(jié)點與其父結(jié)點集的聯(lián)合分布Pr[Sj,Πj]注入拉普拉斯噪聲來得到帶噪聲的聯(lián)合分布Pr*[Sj,Πj].雖然這樣做能夠保證聯(lián)合分布是受差分隱私保護的，但當屬性維度m較大或者屬性的取值情況較多時，計算得到的聯(lián)合分布的概率值會普遍偏小.而如果直接對這些較小的概率值注入噪聲干擾的話，那么很有可能會導致這些概率值被完全覆蓋，造成大規(guī)模的概率值失真問題，這將嚴重影響后續(xù)生成的合成數(shù)據(jù)的精度.因此，本文不直接采用NoisyConditionals方法，而是針對二值數(shù)據(jù)的取值特點提出了一種概率分布加噪算法BNC來實現(xiàn)貝葉斯網(wǎng)絡的安全計算.

由于BNC算法每次處理的是一個數(shù)據(jù)集子集Di，由性質(zhì)2可知，處理這些子集的過程可以共享同一個隱私預算. 因此，BNC算法的實現(xiàn)過程如算法7所示:

算法7.BNC算法.

③ 求聯(lián)合分布Pr[Sj,Πj]和邊緣分布

Pr[Πj];

④ 求條件分布Pr[Sj|Πj]=Pr[Sj,Πj]/

Pr[Πj];

⑤ 對Pr[Sj|Πj]加入噪聲得到

Pr*[Sj|Πj];

⑦ end for

⑧ forj=1 tod′ do

⑩ end for

從算法7中可以看出，BNC算法不會直接對聯(lián)合分布進行加噪，而是改為對由聯(lián)合分布和邊緣分布計算得來的條件分布進行加噪.這里利用了條件概率在二值數(shù)據(jù)上的取值特點，即當分布為條件分布時，有以下式子成立:

PrSj=0|Πj=Oj+PrSj=1|Πj=Oj=1,

(26)

其中，Sj表示當前結(jié)點所對應的屬性，Πj表示Sj的最佳父結(jié)點集所對應的屬性集，Oj表示Πj的某個取值情況.

由式(26)可知，在條件概率Pr[Sj=0|Πj=Oj]和Pr[Sj=1|Πj=Oj]中至少會存在一個條件概率的概率值比較大或者2個條件概率的概率值相差不大即都在0.5上下.這樣即使直接對條件概率注入噪聲干擾，也至少存在一個較大的條件概率的概率值不會被完全覆蓋.所以就不會出現(xiàn)2個概率值同時被覆蓋的情況，除非是注入的噪聲干擾原本就是非常大的，那在這種情況下即使采取任何措施也都無法避免概率值失真的情況發(fā)生.因此，利用條件概率在二值數(shù)據(jù)上的這個特點能夠在很大程度上減少概率失真發(fā)生的次數(shù).

(27)

注意到BNC算法在步驟⑨中計算Pr*[Sj,Πj](j∈[1,d′])是直接基于Pr*[Sd′+1,Πd′+1]計算的，不會涉及原始數(shù)據(jù)集Di的使用.因此不需要對其加入拉普拉斯噪聲干擾，這樣可以節(jié)省下d′個隱私預算的分配.

除了利用條件概率在二值數(shù)據(jù)屬性上的取值特點來減少概率失真發(fā)生的次數(shù)之外.根據(jù)式(27)可知，當貝葉斯網(wǎng)絡的最大入度數(shù)d′在不斷增加時，其所產(chǎn)生的拉普拉斯噪聲大小也在逐漸減小.因此，BNC算法還允許使用者通過控制d′來減小產(chǎn)生的噪聲大小，以此來進一步減少概率值失真發(fā)生的次數(shù).

考慮到在對條件分布注入拉普拉斯噪聲后，條件分布的概率值可能出現(xiàn)取值為負和每一對條件相同、取值相對的條件概率之和不為1的問題.BNC算法還會對加噪后的概率值進行“一致性處理”，即算法7中的步驟⑥，從而保障求出來的條件分布的概率值滿足概率的基本性質(zhì).

4 實 驗

4.1 實驗環(huán)境

本次實驗使用C++編程語言來實現(xiàn)所有的方法，其中貝葉斯網(wǎng)絡部分的實現(xiàn)參考了Zhang等人[20]論文的實驗相關(guān)代碼.

實驗平臺的具體配置信息如表3所示:

Table 3 Experimental Platform Configuration Information

4.2 實驗數(shù)據(jù)集

實驗采用3個真實的數(shù)據(jù)集NLTCS，ACS，Retail.其中NLTCS是一項美國長期護理調(diào)查記錄，其中包括21 574名老年殘疾人的日常生活、醫(yī)療情況;ACS是由IPUMS-USA所發(fā)布的全球人口普查和調(diào)查數(shù)據(jù)，記錄了47 461條個人信息;Retail是美國零售市場的88 162條購物記錄，每條記錄包含其所購買的商品條目，總共有16 469種商品類別，我們從中選取了前50個銷量最多的商品，并將它們處理成含有50個屬性的高維二值數(shù)據(jù)集.這3個數(shù)據(jù)集的具體信息如表4所示:

Table 4 Description of Datasets

4.3 評價指標

(28)

4.4 實驗和結(jié)果

我們將通過3個不同的實驗來驗證PrivSCBN算法的高效性和可用性.

第1個實驗是為了驗證PrivSCBN算法中的FGB子算法與傳統(tǒng)的GreedyBayes算法在構(gòu)建貝葉斯網(wǎng)絡的時間性能上的表現(xiàn).實驗將在NLTCS和ACS這2個數(shù)據(jù)集上進行100次隨機的重復實驗，貝葉斯網(wǎng)絡的最大入度數(shù)d分別設置為2，3，4.對于FGB算法所需的隱私預算ε，由于不是本次實驗關(guān)心的變量，因此我們將其恒定為1.實驗結(jié)果將通過對比這2個算法構(gòu)建貝葉斯網(wǎng)絡的平均時間消耗來進行驗證.實驗結(jié)果如表5所示:

Table 5 Average Time Consumption Record

從表5中可以看出，F(xiàn)GB算法在時間性能上的表現(xiàn)要明顯優(yōu)于GreedyBayes算法，這是符合我們預期的.當d=2時，GreedyBayes算法的時間消耗是FGB的9倍(NLTCS)和18倍(ACS)，并且隨著d的增加這個倍數(shù)也在逐漸擴大.當d=3時是18倍和54倍，當d=4時是30倍和137倍.這個實驗結(jié)果表明相較于傳統(tǒng)的GreedyBayes算法，使用FGB算法來構(gòu)建貝葉斯網(wǎng)絡更為高效.

從另一個角度來看，不管是隨著數(shù)據(jù)屬性維度m的增加還是隨著貝葉斯網(wǎng)絡最大入度數(shù)d的增大，F(xiàn)GB算法的時間消耗增長幅度都要比Greedy-Bayes小很多.例如當d=2，m從16增加到23時，F(xiàn)GB的運行時間只擴大了5倍左右，而GreedyBayes的運行時間擴大了10倍左右.并且隨著d的增加FGB的運行時間的增幅一直維持在5倍左右，而GreedyBayes的增幅是明顯變大的，d=3時是15倍，d=4時是24倍.這個結(jié)果表明FGB算法在執(zhí)行效率上具有一定的穩(wěn)定性.

因此，以FGB算法作為核心子算法的PrivSCBN算法本身也具有高效性和一定的穩(wěn)定性.

第2個實驗是為了分析PrivSCBN算法的可用性.為了能夠知道在無噪聲環(huán)境下，PrivSCBN算法本身可能會產(chǎn)生的噪聲大小.我們通過設置無差分隱私保護的NoPrivSCBN算法來與之進行對比.實驗將在NLTCS，ACS這2個數(shù)據(jù)集上進行100次隨機的重復實驗，隱私預算ε分別設置為0.05，0.1，0.2，0.4，0.8，1.0.實驗結(jié)果將通過200次隨機的α-way查詢進行驗證，其中α的取值為3，8，12.實驗結(jié)果如圖4所示.

從圖4中可以看出，即使是沒有差分隱私保護的PrivSCBN算法也會產(chǎn)生一定的誤差.其原因是PrivSCBN是一種貝葉斯網(wǎng)絡模型方法，在構(gòu)建貝葉斯網(wǎng)絡的過程中，以及通過貝葉斯網(wǎng)絡的近似推理求得的聯(lián)合分布本身，還有使用聯(lián)合分布生成的合成數(shù)據(jù)集，在這些過程中本身就會產(chǎn)生一定的誤差.因此隨著隱私預算ε的增加，PrivSCBN的誤差逐漸逼近NoPrivSCBN的誤差，這是符合差分隱私規(guī)律的.

注意到當隱私預算ε=0.05時，所有實驗的查詢誤差都達到了很高的量級.而當ε增大時，這些查詢誤差開始呈明顯的下降趨勢.這是符合我們的預期的.因為當ε=0.05時，注入的噪聲干擾是非常大的，這會使得大部分的概率值都出現(xiàn)失真問題，導致最后生成的合成數(shù)據(jù)的精度變得非常差.

通過進一步的觀察我們發(fā)現(xiàn)隨著隱私預算ε的增加，PrivSCBN算法的查詢誤差在快速地下降.最后會達到NoPrivSCBN的誤差界限，并且大多都只需要較少的隱私預算就能達到.這個實驗結(jié)果表明PrivSCBN具有較高的可用性.

Fig. 4 Analysis of α-way query error with or without differentially private on NLTCS and ACS datasets

第3個實驗是為了分析PrivSCBN算法在真正的高維數(shù)據(jù)集Retail上的表現(xiàn).為了能夠做更好的說明，本次實驗從現(xiàn)有的高維數(shù)據(jù)差分隱私發(fā)布方法中挑選了3個最具有代表性的方法來作為實驗對比.這3個方法為降維系列方法中的PriView[17]方法、貝葉斯網(wǎng)絡模型方法中的PrivBayes[19]方法、Markov網(wǎng)絡模型方法中的Jtree[26]方法，它們都是目前比較最經(jīng)典且權(quán)威的發(fā)布方法.以這3個方法作為實驗對比，能夠增加實驗結(jié)果的可信程度.

我們將在Retail數(shù)據(jù)集上進行100次隨機的重復實驗，隱私預算ε分別設置為0.1和1.0.實驗結(jié)果將通過200次隨機的α-way查詢進行驗證，其中α的取值為4，6，8.實驗結(jié)果如圖5所示.

Fig. 5 Error analysis of α-way query in different methods on Retail dataset

從圖5中可以看出，當隱私預算ε較小時(ε=0.1)，PrivSCBN方法的表現(xiàn)要明顯優(yōu)于其他3種方法.而當隱私預算ε較大時(ε=1.0)，PrivSCBN雖然仍優(yōu)于其他3種方法，但與Jtree方法的結(jié)果相差不大.這是符合差分隱私規(guī)律的.因為隨著隱私預算的不斷增加，算法的隱私保護程度將會不斷地下降，直至與無差分隱私保護算法的執(zhí)行結(jié)果一致.因此，可以看出通過PrivSCBN方法構(gòu)建的概率圖模型本身的精度與用Jtree方法構(gòu)建的模型精度相比，要來得更好一些.而與用PrivBayes方法構(gòu)建的模型精度相比，要來得更好許多.這也進一步驗證了本文提出的各種改進策略是有效的，并且取得了不錯的效果.本次實驗結(jié)果表明了PrivSCBN相較于其他3種方法具有更高的可用性.

5 結(jié)束語

在未來的研究中，我們將進一步關(guān)注高維非二值數(shù)據(jù)的差分隱私發(fā)布問題，以及研究如何解決流式數(shù)據(jù)環(huán)境下的發(fā)布問題.

作者貢獻聲明:洪金鑫負責分析問題，設計算法，驗證實驗和撰寫論文；吳英杰負責提出問題，參與算法討論，指導論文寫作；蔡劍平負責協(xié)助分析，參與算法討論，指導論文寫作；孫嵐負責協(xié)助分析，參與算法討論，指導論文寫作.