基于屬性分割的高維二值數據差分隱私發布

洪金鑫 吳英杰 蔡劍平 孫 嵐

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 相關工作

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

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

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

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

2 理論與定義

2.1 差分隱私

定義1.ε-差分隱私[1].設兄弟數據集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在數據集D和D′上輸出為O的概率.

實現差分隱私的機制主要有拉普拉斯機制[2]和指數機制[3].這2種機制產生的噪聲大小與查詢函數的全局敏感度有關.

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

(2)

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

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

(3)

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

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

(4)

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

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

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

2.2 譜聚類

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

標準的譜聚類算法實現過程如算法1所示:

算法1.譜聚類算法.

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

輸出:分割結果集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}進行劃分得到劃分結果C;

⑧ returnC.

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

2.3 貝葉斯網絡

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

例如圖1是1張擁有5個結點的貝葉斯網絡圖，該網絡的最大入度數為3.

Fig. 1 Bayesian network of 5 nodes

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

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

(8)

通過貝葉斯網絡可將該聯合分布近似為

(9)

表1顯示了圖1中各個結點的父結點集:

Table 1 Parent Set of Each Node in Bayesian Network

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

(10)

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

2.4 互信息

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

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

(11)

其中，Pr[xi,yj]表示隨機變量X,Y取值為xi,yj的聯合分布.當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距離也可以用來表示同一數據集中2個二值屬性間的差異程度.

假設給定2個二值屬性X,Y，它們取值為X=1,Y=1的數據量為n11，取值為X=0,Y=1的數據量為n01，取值為X=1,Y=0的數據量為n10.那么這2個屬性之間的Jaccard距離為

(13)

可以看出距離越小，屬性間的關聯程度就越高.

3 PrivSCBN算法

3.1 概 述

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

Fig. 2 PrivSCBN algorithm flowchart

PrivSCBN算法的實現過程如算法2所示:

算法2.PrivSCBN算法.

輸入:數據集D={x1,x2,…,xn}、屬性集S={S1,S2,…,Sm}、類簇個數k、尺度參數σ、最大入度數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)ε;

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

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

⑥ fori=1 tokdo

⑩ end for

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

1) 通過DPSC算法將屬性集S劃分成k個屬性子集C1,C2,…,Ck，然后根據這些子集將原始數據集D分割成k個互不相交的數據集子集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節的最后一段滿足差分隱私性質的說明可知，步驟③⑦⑧中的DPSC，FGB，BNC算法均各自滿足ε1，ε2，ε3-差分隱私.雖然其中的FGB和BNC算法會被執行k次，但每次執行所使用的數據集Di之間是沒有交集的.由性質2可知，它們仍然滿足ε2，ε3-差分隱私.并且除了上述的3個算法之外，PrivSCBN算法沒有其他地方再涉及原始數據集D的使用.因此，由性質1可知，整個PrivSCBN算法滿足ε=(ε1+ε2+ε3)-差分隱私.

3.2 差分隱私譜聚類算法

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

Fig. 3 Black and white node network diagram

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

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

DPSC算法的實現過程如算法3所示:

算法3.DPSC算法.

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

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

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

(17)

② 執行算法1的步驟②～⑥;

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

④ returnC.

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

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

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

1) 減少的是X=1,Y=1的記錄，根據式(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)的全局敏感度，互信息的全局敏感度要來得更大.根據式(3)可知相比于互信息，使用Jaccard距離產生的拉普拉斯噪聲大小會更小.

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

綜上所述，我們可以得到加入邊權函數的拉普拉斯噪聲大小為

(21)

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

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

3.3 差分隱私貝葉斯網絡算法

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

GreedyBayes算法的實現過程如算法4所示:

算法4.GreedyBayes算法.

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

③ fori=2 tomdo

④ 初始化集合Ω=?;

⑦ end for

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

(22)

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

(23)

證畢.

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

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

Table 2 Enumeration Number of GreedyBayes Algorithm

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

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

FGB算法的實現過程如算法5所示:

算法5.FGB算法.

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

③ fort=2 to |Ci| do

④ 初始化集合Ω=?;

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

⑦ end for

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

DPBestParent算法的實現過程如算法6所示:

算法6.DPBestParent算法.

輸入:數據集Di={x1,x2,…,xn}、屬性Sj、新增父屬性fa、當前最大入度數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]表示結點集合，含義是結點Sj選擇l個結點作為父結點的最佳選擇情況.從步驟②～⑥的for循環中可以看出，實際上在新一輪的DPBestParent算法執行時，dp[Sj,l]就已經記錄了上一輪中在該狀態下的最佳父結點集的選擇情況.因此對于本輪來說，只需要關心上一輪新加入網絡的結點fa對當前最佳父結點集的選擇情況的影響即可.這里for循環采用的是倒序遍歷的方式，即從d′到1.其原因是為了保證當前更新的狀態不會影響到下一次的狀態更新，這個操作避免了結點fa被加入到同一個父結點集多次.

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

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

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

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

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

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

證畢.

除了解決GreedyBayes算法在執行效率上的問題之外，FGB算法還引入了差分隱私指數機制來擾動貝葉斯網絡的構建過程(步驟⑥)，從而解決了構建的貝葉斯網絡存在隱私泄露風險的問題.

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

(24)

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

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

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

(25)

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

3.4 差分隱私條件分布計算

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

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

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

算法7.BNC算法.

③ 求聯合分布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算法不會直接對聯合分布進行加噪，而是改為對由聯合分布和邊緣分布計算得來的條件分布進行加噪.這里利用了條件概率在二值數據上的取值特點，即當分布為條件分布時，有以下式子成立:

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

(26)

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

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

(27)

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

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

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

4 實 驗

4.1 實驗環境

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

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

Table 3 Experimental Platform Configuration Information

4.2 實驗數據集

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

Table 4 Description of Datasets

4.3 評價指標

(28)

4.4 實驗和結果

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

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

Table 5 Average Time Consumption Record

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

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

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

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

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

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

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

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

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

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

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

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

5 結束語

在未來的研究中，我們將進一步關注高維非二值數據的差分隱私發布問題，以及研究如何解決流式數據環境下的發布問題.

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