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

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

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

0 引言

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

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

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

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

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

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

1 相關(guān)工作

1.1 差分隱私

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

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

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

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

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

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

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

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

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

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

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

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

1.3 最大信息系數(shù)

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

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

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

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

2.1 PrivBC方法

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

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

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

特別地，設(shè)子集簇?cái)?shù)量為c，每個(gè)子集簇根據(jù)擁有的屬性個(gè)數(shù)占c個(gè)子集簇?fù)碛械目倢傩詡€(gè)數(shù)比例分配隱私預(yù)算：

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

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

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

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

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

2.2 屬性聚類方法

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

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

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

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

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

為驗(yàn)證采用K-means++方法選擇初始聚類中心屬性，代替K-means 隨機(jī)選取方法的效用性，以相互依賴關(guān)系度量的總和作為評(píng)分函數(shù)，在多個(gè)真實(shí)數(shù)據(jù)集上對(duì)比平均聚類結(jié)果。如圖3 所示，各個(gè)數(shù)據(jù)集的評(píng)分函數(shù)值都有所提升，說(shuō)明改進(jìn)方法在一定程度上減少了聚類誤差。在聚類數(shù)目k的選取上，給定高維數(shù)據(jù)集D和屬性集合V，數(shù)據(jù)集的聚類數(shù)目可參考相互依賴度量的總和值進(jìn)行選?。灰訬LTCS（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這兩個(gè)屬性聚類方法的聚類評(píng)分值對(duì)比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ò)改進(jìn)

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

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

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

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

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

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

3.1 實(shí)驗(yàn)設(shè)置

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

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

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

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

3.2 方法誤差分析

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

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

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

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

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

3.3 方法有效性分析

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

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

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

3.4 方法性能分析

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

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

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

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

4 結(jié)語(yǔ)

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