基于聚類分析的差分隱私高維數(shù)據(jù)發(fā)布方法

陳恒恒，倪志偉*，朱旭輝，金媛媛，陳 千

（1.合肥工業(yè)大學(xué)管理學(xué)院，合肥 230009；2.過程優(yōu)化與智能決策教育部重點實驗室（合肥工業(yè)大學(xué)），合肥 230009）

（*通信作者電子郵箱zhwnelson@163.com）

0 引言

隨著大數(shù)據(jù)時代的全面到來，數(shù)據(jù)發(fā)布過程中的個人隱私面臨更嚴重的威脅，如何做好隱私防護顯得尤為重要。差分隱私作為一種可以對保護強度進行量化評估的隱私保護技術(shù)，無需考慮攻擊者背景知識，在數(shù)據(jù)發(fā)布方面得到了廣泛應(yīng)用，逐漸成為隱私保護領(lǐng)域的一個研究熱點［1］。現(xiàn)有研究對低維數(shù)據(jù)的發(fā)布問題作了諸多努力，但實際應(yīng)用中高維數(shù)據(jù)的發(fā)布需求往往更為強烈，并且低維數(shù)據(jù)的隱私發(fā)布方法難以處理高維數(shù)據(jù)，直接加噪會導(dǎo)致數(shù)據(jù)可用性降低、查詢結(jié)果敏感度增大等問題［2］。

針對高維數(shù)據(jù)的差分隱私發(fā)布，通常使用的方法是降維，利用有效的維度轉(zhuǎn)換方法得到低維數(shù)據(jù)，再對轉(zhuǎn)換后的低維數(shù)據(jù)集添加噪聲，已有研究涉及閾值過濾技術(shù)［3］、隨機投影［4］、主成分分析［5］、概率圖模型［6-8］等方法。文獻［3］基于閾值過濾技術(shù)選擇部分屬性達到降維目的，文獻［4］通過隨機投影技術(shù)學(xué)習(xí)原始數(shù)據(jù)集向量之間的L2 距離，文獻［5］將主成分降維用于差分隱私數(shù)據(jù)發(fā)布，文獻［6］利用貝葉斯網(wǎng)絡(luò)來推理屬性之間的關(guān)聯(lián)關(guān)系，文獻［7］基于Markov 網(wǎng)絡(luò)構(gòu)建屬性集群，文獻［8］采用隱樹模型對高維數(shù)據(jù)的維度相關(guān)性進行結(jié)構(gòu)學(xué)習(xí)，文獻［9］利用組合原理選擇低維視圖構(gòu)建低維加噪邊緣表用于數(shù)據(jù)發(fā)布，文獻［10］結(jié)合截斷和分組兩種技術(shù)以提高隱私數(shù)據(jù)發(fā)布結(jié)果準確性，文獻［11］計算Copula 函數(shù)來描述多變量隨機向量之間的相關(guān)性。此外，依據(jù)屬性間關(guān)系假設(shè)的不同，高維數(shù)據(jù)發(fā)布方法又可分為數(shù)據(jù)獨立的發(fā)布方法與數(shù)據(jù)相關(guān)的發(fā)布方法。文獻［3-4］和文獻［9-10］沒有考慮到屬性之間的依賴關(guān)系，屬于數(shù)據(jù)獨立發(fā)布方法。數(shù)據(jù)相關(guān)發(fā)布方法假設(shè)屬性間相互依賴，現(xiàn)有研究多通過概率圖模型判別屬性間的關(guān)聯(lián)性，如貝葉斯網(wǎng)絡(luò)、Markov 網(wǎng)絡(luò)，隱樹模型或者其他判別屬性間相關(guān)性的方法，如皮爾遜相關(guān)系數(shù)、卡方關(guān)聯(lián)測試［12］等。

文獻［6］提出的PrivBayes 方法是數(shù)據(jù)相關(guān)發(fā)布方法的典型代表，通過構(gòu)建貝葉斯網(wǎng)絡(luò)進行降維，更加容易保持屬性間概率的一致性和完整性，在實現(xiàn)降維的同時較好保留原始數(shù)據(jù)的固有特征，因此許多研究在其基礎(chǔ)上進行應(yīng)用和改進。如：文獻［13］構(gòu)建了在本地化眾包應(yīng)用場景中的高維數(shù)據(jù)發(fā)布方法，文獻［14］解決了分布式環(huán)境下的隱私發(fā)布問題，文獻［15］提出了一種高維感知數(shù)據(jù)本地隱私保護發(fā)布機制，文獻［16］提出了一種加權(quán)貝葉斯網(wǎng)絡(luò)方法，文獻［17］提出了一種基于語義樹的貝葉斯網(wǎng)絡(luò)隱私數(shù)據(jù)發(fā)布方法。然而，由于該類方法在構(gòu)建網(wǎng)絡(luò)時存在大量的候選屬性對，會在降低指數(shù)機制選擇精度的同時，帶來大量的計算開銷。此外，基于概率圖模型的高維數(shù)據(jù)發(fā)布方法雖考慮了屬性間關(guān)聯(lián)關(guān)系，但是因其過高的計算時間復(fù)雜度往往只適用于小規(guī)模網(wǎng)絡(luò)。

當前差分隱私研究的核心問題是提高發(fā)布數(shù)據(jù)的可用性及方法的計算效率，為了克服已有方法的不足，本文提出了一種基于聚類分析技術(shù)的差分隱私高維數(shù)據(jù)發(fā)布方法PrivBC，主要工作包括：

1）設(shè)計了一種基于K-means++的屬性聚類方法，引入聚類的思想對貝葉斯網(wǎng)絡(luò)進行分割，以縮減網(wǎng)絡(luò)結(jié)構(gòu)空間，降低方法計算復(fù)雜性，并減少隱私預(yù)算的分割次數(shù)，提高指數(shù)機制選擇精度。

2）針對貝葉斯網(wǎng)絡(luò)構(gòu)建提出改進方法，為高效挑選出具有依賴關(guān)系的屬性對，改進候選屬性對的生成機制，采用基于關(guān)系矩陣的過濾技術(shù)來縮減指數(shù)機制的搜索空間，優(yōu)化貝葉斯網(wǎng)絡(luò)構(gòu)建質(zhì)量和效率。

1 相關(guān)工作

1.1 差分隱私

差分隱私保護模型的主要思想是，通過向待發(fā)布數(shù)據(jù)集或計數(shù)中添加適當噪聲，以至于攻擊者不能推斷出某個記錄是否在發(fā)布的數(shù)據(jù)集中，因此用戶的隱私可以得到保護［18］。

定義1 相鄰數(shù)據(jù)集［19］。設(shè)D={t1，t2，…，tn}為原始高維數(shù)據(jù)集，當且僅當數(shù)據(jù)集D'與D滿足式（1）時，稱D與D'為相鄰數(shù)據(jù)集。

其中：D+tr表示將記錄tr添加到數(shù)據(jù)集D后產(chǎn)生的數(shù)據(jù)集。基于相鄰數(shù)據(jù)集給出ε?差分隱私定義如下。

定義2ε?差分隱私［19］。給定隨機方法O，對于任意相鄰數(shù)據(jù)集D和D'以及方法任何可能輸出集合Ω，若方法O滿足式（2），則稱隨機方法O嚴格提供ε?差分隱私保護。

其中參數(shù)ε稱為隱私保護預(yù)算，其值與方法的隱私保護強度成反比，值越小，保護程度越高。任何滿足定義1 的機制都可以視為差分隱私，例如Laplace 機制通過向查詢結(jié)果中添加Laplace 分布噪聲來滿足差分隱私，指數(shù)機制則通常用于輸出為非數(shù)值型的方法。

定義3Laplace 機制［20］。對任意查詢函數(shù)f：D→Rd，若方法A滿足式（3），則稱方法滿足ε?差分隱私。

其中：Δf為查詢f的全局敏感性；lapi(Δf/ε)為彼此獨立的Laplace 噪聲變量。由式（3）可知噪聲量大小與Δf成正比，而與隱私預(yù)算ε成反比。

定義4指數(shù)機制［20］。設(shè)S為指數(shù)機制下的某個隱私方法，若其在打分函數(shù)F(ni)作用下的輸出結(jié)果滿足式（4），則稱方法S滿足ε?差分隱私。

其中：ΔF為打分函數(shù)F(ni)的全局敏感性。由式（4）可知ni的打分函數(shù)越高，被選擇輸出的概率越大。

1.2 貝葉斯網(wǎng)絡(luò)

貝葉斯網(wǎng)絡(luò)N是一種較為常用的概率圖模型，它借助屬性節(jié)點間有向邊來描述屬性之間的依賴關(guān)系，能更加直觀地表達屬性間的條件獨立性。具體來說，它由屬性代表的節(jié)點ai和節(jié)點之間的有向邊(ai，aj)組成，有向邊代表著節(jié)點之間的依賴關(guān)系，并用有向邊連接屬性節(jié)點間的條件概率大小定量表示節(jié)點之間的依賴程度。假設(shè)屬性對(ai)表示ai節(jié)點與其所有父節(jié)點的集合Πi，則對于給定的屬性集合A和屬性對集合(a，Π)，聯(lián)合概率分布可表示為PA(a1，a2，…，ad)=。圖1 表示包含5 個節(jié)點的貝葉斯網(wǎng)絡(luò)，圖中所有節(jié)點a1，a2，…，a5的聯(lián)合概率可計算為：

圖1 含5個節(jié)點的貝葉斯網(wǎng)絡(luò)Fig.1 Bayesian network with five nodes

1.3 最大信息系數(shù)

互信息是用于衡量兩個屬性間關(guān)聯(lián)程度的常用指標，但對于連續(xù)型屬性，互信息的計算結(jié)果對離散化的方式很敏感，且對于不同數(shù)據(jù)集計算出的結(jié)果無法比較。最大信息系數(shù)（Maximum Information Coefficient，MIC）［21］的提出可以解決上述問題。它以互信息和信息論為基礎(chǔ)，采用網(wǎng)格劃分的方法，可以更準確地識別出大數(shù)據(jù)集中屬性間的線性或非線性關(guān)系，以及非函數(shù)依賴關(guān)系，具有普適性、公平性、計算復(fù)雜度低等特性。

定義5最大信息系數(shù)。給定屬性X，Y和有序?qū)Γ瑯颖緮?shù)量為n，將當前x?y平面劃分為a×b的網(wǎng)格G，并使屬性數(shù)據(jù)點都落入網(wǎng)格G中，定義屬性X和Y的最大互信息計算式（5）如下：

其中：B為網(wǎng)格劃分a×b的上限值，通常取值為n0.6。

2 基于聚類分析技術(shù)的發(fā)布方法

2.1 PrivBC方法

PrivBayes 方法采用基于依賴統(tǒng)計分析的方法，在構(gòu)建小規(guī)模網(wǎng)絡(luò)時可以得到理想結(jié)果；但在面臨大規(guī)模稀疏數(shù)據(jù)集時，方法的計算復(fù)雜性和網(wǎng)絡(luò)結(jié)構(gòu)復(fù)雜度都將呈現(xiàn)出爆炸式增長，這勢必造成方法的可用性降低。文獻［22］引入方法分團思想對動態(tài)貝葉斯網(wǎng)絡(luò)進行分割，以降低抽樣狀態(tài)空間。文獻［23］指出，針對高維數(shù)據(jù)的發(fā)布需要輔以對屬性進行聚類或分組等方式進行降維。基此，本文針對屬性之間的復(fù)雜關(guān)系，引入方法聚類的思想，提出基于屬性聚類的貝葉斯網(wǎng)絡(luò)隱私數(shù)據(jù)發(fā)布方法，首先計算高維數(shù)據(jù)屬性之間的相關(guān)性，并對屬性進行聚類，然后分別對具有不同內(nèi)部相關(guān)性的子集簇使用貝葉斯網(wǎng)絡(luò)作近似推理。

圖2 展示了PrivBC 隱私保護方法的發(fā)布流程，具體由屬性子集的聚類劃分、加噪貝葉斯網(wǎng)絡(luò)構(gòu)建、加噪條件分布生成、合成數(shù)據(jù)集的發(fā)布四個階段組成。其中二、三階段分配的總隱私預(yù)算分別為ε1和ε2，其中ε=ε1+ε2。

圖2 PrivBC數(shù)據(jù)發(fā)布方法流程Fig.2 Flowchart of PrivBC data publishing method

特別地，設(shè)子集簇數(shù)量為c，每個子集簇根據(jù)擁有的屬性個數(shù)占c個子集簇擁有的總屬性個數(shù)比例分配隱私預(yù)算：

根據(jù)差分隱私的組合性質(zhì)可知，PrivBC 方法滿足ε?差分隱私。PrivBC方法四個階段的概述如下。

1）屬性子集的聚類劃分：獲取原始數(shù)據(jù)集，對于非二進制數(shù)據(jù)集中的連續(xù)型屬性采用二分K均值方法進行個性離散化處理。隨后計算屬性之間的相關(guān)性，采用改進的屬性聚類方法將高維屬性集劃分成c個屬性子集，進而根據(jù)屬性子集將原始數(shù)據(jù)集D劃分成c個數(shù)據(jù)子集Di(i=1，2，…，c)。

2）加噪貝葉斯網(wǎng)絡(luò)構(gòu)建：對于聚類得到的每個數(shù)據(jù)子集，分別使用改進Bayes 方法構(gòu)建加噪貝葉斯網(wǎng)絡(luò)Ni(i=1，2，…，c)，使構(gòu)建的每個貝葉斯網(wǎng)絡(luò)滿足ε1i的差分隱私。

3）加噪條件分布生成：對于加噪得到的每個貝葉斯網(wǎng)絡(luò)，分別根據(jù)加噪聯(lián)合概率分布計算加噪條件概率分布Pi(i=1，2，…，c)，使構(gòu)建的條件概率分布滿足ε2i的差分隱私。

4）合成數(shù)據(jù)集發(fā)布：根據(jù)網(wǎng)絡(luò)結(jié)構(gòu)N和加噪條件概率分布依次采樣每個屬性，生成擾動數(shù)據(jù)集(i=1，2，…，c)，根據(jù)此得到合成數(shù)據(jù)集D*，并將合成數(shù)據(jù)集進行發(fā)布。

2.2 屬性聚類方法

區(qū)別于數(shù)據(jù)對象聚類方法，屬性聚類方法旨在依據(jù)屬性間相關(guān)性對屬性進行聚類，使得同一簇中屬性具有較高相似度。文獻［24］提出的屬性聚類算法（Attribute Clustering Algorithm，ACA）能較準確地對屬性進行聚類，但實際應(yīng)用中尚存在一些問題：一方面，ACA 采用K-means 方法隨機選取初始聚類中心屬性，存在很大的不確定性，最終導(dǎo)致聚類結(jié)果誤差較大；另一方面，ACA 采用互信息度量屬性間的依賴關(guān)系，需要通過聯(lián)合熵對互信息值作歸一化處理，對于連續(xù)型屬性離散化的方式較為敏感。

針對K-means 方法存在的缺陷，諸多研究作了相應(yīng)努力。如：文獻［25］和文獻［26］分別提出了精確加速方法YinyangK-means 和BallK-means，在減少距離計算次數(shù)的同時能獲得更好聚類質(zhì)量。在初始聚類中心的選取上，文獻［27］基于聚類中心間距離應(yīng)當盡可能大的原則，提出了K-means++方法，使方法可以獲取全局最優(yōu)結(jié)果，在聚類結(jié)果準確性上有較大提升。此外，最大信息系數(shù)能高效檢測大數(shù)據(jù)集中不同類型維度間關(guān)聯(lián)關(guān)系，無需歸一化處理。因此，考慮到上述兩點不足，本文借鑒K-means++方法原理選取初始聚類中心屬性，并采用最大信息系數(shù)量化屬性間關(guān)聯(lián)程度，提出改進的屬性聚類方法MACA（Maximum Attribute Clustering Algorithm），如方法1所示。

定義6相對依賴關(guān)系。給定任意兩個屬性vi和vj，定義屬性之間相對依賴關(guān)系計算式為：

其中：MIC代表兩個屬性之間的最大信息系數(shù)。

定義7復(fù)合依賴關(guān)系。給定任意一個屬性vi和屬性集C={vj|j=1，2，…，m}，為衡量屬性與屬性集中所有其他屬性的相對依賴關(guān)系，定義屬性到屬性集的復(fù)合依賴關(guān)系為各相對依賴關(guān)系之和。

為驗證采用K-means++方法選擇初始聚類中心屬性，代替K-means 隨機選取方法的效用性，以相互依賴關(guān)系度量的總和作為評分函數(shù)，在多個真實數(shù)據(jù)集上對比平均聚類結(jié)果。如圖3 所示，各個數(shù)據(jù)集的評分函數(shù)值都有所提升，說明改進方法在一定程度上減少了聚類誤差。在聚類數(shù)目k的選取上，給定高維數(shù)據(jù)集D和屬性集合V，數(shù)據(jù)集的聚類數(shù)目可參考相互依賴度量的總和值進行選取；以NLTCS（National Long Term Care Survey）數(shù)據(jù)集為例，結(jié)合圖4選取其最佳聚類數(shù)目為2，以ACS 數(shù)據(jù)集為例，結(jié)合圖5 其聚類數(shù)目選取為3；此外，Adult和TPC-E數(shù)據(jù)集的聚類數(shù)目分別取2、3。

圖3 MACA與ACA這兩個屬性聚類方法的聚類評分值對比Fig.3 Comparison of clustering scores of two attribute clustering algorithms called MACA and ACA

圖4 不同聚類數(shù)目k在NLTCS數(shù)據(jù)集上的相互依賴度量總和值Fig.4 Total interdependence measure with different cluster number k on NLTCS dataset

圖5 不同聚類數(shù)目k在ACS數(shù)據(jù)集上的相互依賴度量總和值Fig.5 Total interdependence measure with different cluster number k on ACS dataset

2.3 Bayes網(wǎng)絡(luò)改進

PrivBayes方法在構(gòu)建貝葉斯網(wǎng)絡(luò)時為避免因過度訪問數(shù)據(jù)集而產(chǎn)生大量噪聲，采用貪婪方法選取屬性AP（Attribute Parent）對，每次AP對的選取都需要全部計算候選屬性集合中屬性對的評分，弱相關(guān)性屬性對的評分在節(jié)點選取中被重復(fù)計算，這無疑消耗了過多的計算資源。基于此，本文采用關(guān)系矩陣過濾技術(shù)來壓縮候選空間，過濾掉Ω中弱相關(guān)屬性對。

在前文計算出的V中每對屬性節(jié)點間最大信息系數(shù)的基礎(chǔ)上構(gòu)造屬性鄰接矩陣M，確定每個節(jié)點vi的最大信息系數(shù)，記為MMIC(vi)，如果屬性節(jié)點vi和vj(i≠j)之間的MIC(vi，vj)滿足式（7），可知屬性間相對依賴關(guān)系很弱，將其在鄰接矩陣中的標識位設(shè)置為0，否則設(shè)置為1，據(jù)此得到屬性間關(guān)系矩陣Rv。改進后的Bayes 構(gòu)建如方法2 所示。對于PrivBayes 方法，未加入集合S的節(jié)點v都要計算與父節(jié)點Π的評分，循環(huán)共需計算d(d-1)/2 次，而，計算候選空間|Ο|=d(d-1)；對于PrivBC 方法，通過分析方法2 可知過縮減后的，候選空間|Ο'|=d(d-1)，因為|S'|<|S|，因此，方法運行效率得到提升。

2.4 方法復(fù)雜度分析

為更好說明方法可行性，有必要對方法復(fù)雜度進行理論分析。設(shè)D為高維數(shù)據(jù)集合，d為總屬性維度，n為樣本數(shù)量，c為屬性聚類子集簇數(shù)目，v為子集屬性維度。

方法的第一階段使用K-means++方法聚類，時間復(fù)雜度為O(cdt)，t為迭代次數(shù)。第二階段構(gòu)建貝葉斯網(wǎng)絡(luò)，考慮計算關(guān)系矩陣是一項獨立的任務(wù)，時間復(fù)雜度為O(d(d-1))；此外，對于每個子集簇，需計算屬性節(jié)點關(guān)聯(lián)度，根據(jù)上文對候選空間的分析，加之網(wǎng)絡(luò)構(gòu)建循環(huán)需進行v-1 次，時間復(fù)雜度為，k為父節(jié)點個數(shù)，S'為縮減后每次循環(huán)的父節(jié)點集合，因此該階段總時間復(fù)雜度為。第三階段，構(gòu)建加噪條件分布時每個子集循環(huán)需進行v次，時間復(fù)雜度為O(cv)。綜上所述，PrivBC 方法總的復(fù)雜度為，由于v為子集屬性維度，取值偏小，進而保證方法的優(yōu)良性能。

3 實驗與結(jié)果分析

3.1 實驗設(shè)置

為了對PrivBC 方法的有效性和運行效率進行驗證與說明，下面在真實高維數(shù)據(jù)集上開展具體的實驗，從方法誤差、方法有效性和方法性能方面與PrivBayes方法進行對比分析。

實驗環(huán)境是Windows10 操作系統(tǒng)，Intel Core i5-6400 CPU（2.70 GHz），8 GB 內(nèi)存。所涉及方法代碼用Python 及Java 語言實現(xiàn)。實驗所使用的4個數(shù)據(jù)集NLTCS、ACS、Adult、TPC-E均被廣泛使用于高維數(shù)據(jù)發(fā)布。NLTCS數(shù)據(jù)集源自美國護理調(diào)查中心，包含了21 574名殘疾人護理調(diào)查的記錄；ACS 數(shù)據(jù)集源自IPUMSUSA 的ACS樣本集，記錄了從2013和2014年中獲得的47 461 條個人信息；Adult 數(shù)據(jù)集源自美國人口普查中心，包含了45 222 條個人信息；TPC-E 數(shù)據(jù)集來自于某在線事務(wù)處理程序，記錄了40 000 條事務(wù)信息。實驗數(shù)據(jù)集的具體細節(jié)如表1所示。

表1 4個數(shù)據(jù)集信息描述Tab.1 Description of four datasets

對于上述4 種數(shù)據(jù)集，隱私預(yù)算預(yù)算分配策略為ε1=0.3ε，ε2=ε-ε1，即隱私預(yù)算ε1=0.3ε用于構(gòu)建加噪貝葉斯網(wǎng)絡(luò)，剩余隱私預(yù)算用于產(chǎn)生加噪條件分布。特別地，當ε取值為0.05、0.1 時，ε1=0.1ε，ε2=ε-ε1。在Bayes 網(wǎng)絡(luò)父節(jié)點個數(shù)k的取值上，對于NLTCS、ACS 和Adult 數(shù)據(jù)集，k默認取值3；對于屬性維度更高的TPC-E數(shù)據(jù)集，k默認取值為2。

3.2 方法誤差分析

為進一步評估加噪數(shù)據(jù)集的統(tǒng)計查詢精度：對于二進制數(shù)據(jù)集，通過對比前后邊緣表分布的L2錯誤距離來對發(fā)布數(shù)據(jù)的誤差進行評估；對于非二進制數(shù)據(jù)集，參照文獻［2，6］，通過對比加噪前后邊緣表2-way 以及3-way 的平均變量距離（Average Variable Distance，AVD）來衡量方法查詢結(jié)果的準確性。其中AVD 為加噪前后邊緣表分布L1 距離的一半

圖6（a）和圖6（b）分別對比了二進制NLTCS、ACS 數(shù)據(jù)集在隱私預(yù)算ε為0.1 和1.0 時PrivBC 方法與PrivBayes 方法的L2 錯誤距離，其中縱坐標是對數(shù)刻度，可以看出在絕大多數(shù)情況下，PrivBC 方法的準確度都得到了較大提升，只有在ACS數(shù)據(jù)集上ε=1.0 時，PrivBC 方法準確性較PrivBayes 方法有稍許降低，但考慮到此時L2 誤差都比較小，降低的查詢精度在可接受范圍內(nèi)，此外，當聚類誤差較加噪誤差足夠小時，該方法可以實現(xiàn)發(fā)布數(shù)據(jù)效用性及方法計算效率之間的良好折中，因此這表示為可接受的折中方案。

圖6 二進制數(shù)據(jù)集上的L2錯誤距離Fig.6 L2 error distance on binary datasets

圖7（a）和圖7（b）分別對比了非二進制Adult 和TPC-E 數(shù)據(jù)集在不同隱私預(yù)算下的2-way、3-way 查詢誤差。由圖7 可知，在隱私參數(shù)相同時，PrivBC 平均變量距離小于PrivBayes，即便在數(shù)據(jù)維度很高的TPC-E 數(shù)據(jù)集上，PrivBC 方法同樣可以得到更好的精確度，尤其在隱私預(yù)算緊張時改進效果更加顯著。這是因為PrivBayes 方法候選空間的大小會隨屬性的增加呈指數(shù)上升，造成隱私預(yù)算急劇減小，導(dǎo)致數(shù)據(jù)誤差偏大，而PrivBC 方法由聚類形成的各個子集簇屬性數(shù)量較少，網(wǎng)絡(luò)結(jié)構(gòu)簡單，大大減少了計算屬性對數(shù)量，從而保證良好數(shù)據(jù)效用。

圖7 非二進數(shù)據(jù)集上k-way查詢誤差Fig.7 k-way query error on non-binary datasets

3.3 方法有效性分析

為了對發(fā)布數(shù)據(jù)的有效性進行分析，參考文獻［4，7］選取NLTCS 和Adult 數(shù)據(jù)集，以加噪合成數(shù)據(jù)集的80%作為訓(xùn)練集，20%作為測試集，在通過PrivBC、PrivBayes 方法產(chǎn)生的加噪合成數(shù)據(jù)集上構(gòu)建分類模型。優(yōu)秀的分類方法有文獻［28］的基于完全隨機森林的類噪聲濾波學(xué)習(xí)（Complete Random Forest based class Noise Filtering Learning，CRF-NFL）方法和文獻［29］的粒球支持向量機（Granular Ball Support Vector Machine，GBSVM）、粒 球K近 鄰（Granular BallK-Nearest Neighbors，GBKNN）方法等，這里參考文獻［2，4，6］選取支持向量機（Support Vector Machine，SVM）方法構(gòu)建分類模型。圖8 展示了不同數(shù)據(jù)集上方法基于參數(shù)ε變化的平均誤分類率，在NLTCS 數(shù)據(jù)集上，依據(jù)某個人：（a）是否能夠外出（如圖8（a）中Y=Outside）；（b）是否能夠游泳作為分類屬性作出預(yù)測。在Adult數(shù)據(jù)集上，依據(jù)某個人：（c）是否為男性；（d）是否結(jié)婚作為分類屬性作出預(yù)測。其中PrivBR 方法為經(jīng)過候選屬性對縮減處理的PrivBayes 加噪方法，PrivateERM［30］方法通過對風(fēng)險函數(shù)添加噪聲并優(yōu)化擾動來輸出SVM 分類器，NoPrivacy在不加噪原始數(shù)據(jù)集上直接構(gòu)建分類器。

圖8 不同數(shù)據(jù)集上的SVM誤分類率Fig.8 SVM misclassification rate on different datasets

從圖8可以發(fā)現(xiàn)，對比PrivBayes方法，PrivBR方法在NLTCS 數(shù)據(jù)集上的屬性誤分類率有所降低，這表明縮減候選屬性對空間能一定程度上優(yōu)化所構(gòu)建的貝葉斯網(wǎng)絡(luò)。此外，可以觀察到本文提出的PrivBC 方法的誤分類率在絕大部分情況下小于PrivateERM 方法，并在很大程度上小于PrivBayes方法，特別在二進制NLTCS 數(shù)據(jù)集上，PrivBC 方法即使在隱私預(yù)算很小時也能達到較高精度。平均來看，PrivBC 相較于PrivBayes 方法的誤分類率降低12.6%，這表明PrivBC 方法在有效保證數(shù)據(jù)隱私信息的同時，SVM分類精確性也有所提高，增強了數(shù)據(jù)發(fā)布效用。

3.4 方法性能分析

發(fā)布加噪數(shù)據(jù)集所需運行時間也是衡量隱私保護方法優(yōu)劣的一個極其重要的指標。圖9 對比了相同隱私預(yù)算條件下（如ε=0.8），貝葉斯網(wǎng)絡(luò)的度k=2，3 時，四個高維數(shù)據(jù)集上，PrivBC 方法與PrivBayes 方法在發(fā)布加噪數(shù)據(jù)集時的運行時間。從圖9 可看出，PrivBC 方法在NLTCS、ACS 維度較低數(shù)據(jù)集上，運行時間相較PrivBayes 方法沒有優(yōu)勢，但在Adult、TPC-E 維度較高數(shù)據(jù)集上，PrivBC 方法運行時間明顯短于PrivBayes 方 法，如 在k=2時，Adult數(shù)據(jù)集上PrivBC方法是PrivBayes 方法的1/3 左右，在TPC-E 數(shù)據(jù)集上為1/4 左右。此外，隨著貝葉斯網(wǎng)絡(luò)度k增大，PrivBC 方法運行時間的優(yōu)勢更加顯著。這是因為，隨著屬性個數(shù)的增加，PrivBayes方法的計算復(fù)雜度呈指數(shù)遞增，而PrivBC 方法的時間復(fù)雜度為每個低維子集簇計算時間的線性問題。平均來看，PrivBC 相較于PrivBayes 方法的運行時間降低30.2%（因k較高時，PrivBayes方法運行TPC-E 數(shù)據(jù)集因復(fù)雜度過高易造成內(nèi)存溢出，計算時排除該數(shù)據(jù)集）。

圖9 不同數(shù)據(jù)集上方法運行時間Fig.9 Algorithm running time on different datasets

圖10 比較了4 個隱私方法PrivBC、PrivBayes、PrivateERM和PrivLocal［31-32］在Adult 數(shù)據(jù)集上構(gòu)建SVM 分類器的運行時間。PrivBayes效率最低，其次是PrivBC、PrivateERM 和PrivLocal。這是因為PrivateERM 和PrivLocal 直接輸出分類器，而PrivBC 是一個生成合成數(shù)據(jù)集的通用框架，支持多個分析任務(wù)，這對于許多實際應(yīng)用十分重要。

圖10 基于SVM分類的不同方法在Adult數(shù)據(jù)集上的運行時間Fig.10 Running time of different algorithms based on SVM classification on Adult dataset

4 結(jié)語

針對PrivBayes 方法指數(shù)機制選擇精度低，計算效率不足的問題，本文提出了一種基于聚類分析技術(shù)的隱私數(shù)據(jù)發(fā)布方法PrivBC。在構(gòu)建貝葉斯網(wǎng)絡(luò)時輔以聚類分析以及基于關(guān)系矩陣過濾冗余候選屬性對，縮減了網(wǎng)絡(luò)結(jié)構(gòu)空間，減少了隱私預(yù)算分割次數(shù)。同時，改進連續(xù)型屬性編碼方式，提高了數(shù)據(jù)集的可用性。實驗結(jié)果表明，PrivBC 方法能很好地兼顧加噪數(shù)據(jù)發(fā)布精度和發(fā)布時間，與PrivBayes 方法相比，其在發(fā)布數(shù)據(jù)查詢誤差、數(shù)據(jù)有效性和方法運行時間等多個方面性能都有顯著提升。由于PrivBC 方法假設(shè)所有屬性關(guān)系都是有向的因果關(guān)系，這與高維數(shù)據(jù)真實的屬性關(guān)系存在差異；此外，由于方法需要計算屬性對依賴關(guān)系，相較于屬性獨立發(fā)布方法計算時間開銷較大。下一步可考慮將聚類思想與其他概率圖模型相結(jié)合，采用Mapreduce 等編程模式實現(xiàn)方法并行化，應(yīng)用于更多高維數(shù)據(jù)發(fā)布場景，如高維動態(tài)數(shù)據(jù)流的隱私發(fā)布。