基于聚類分析的差分隱私高維數據發布方法

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

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

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

0 引言

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

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

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

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

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

2）針對貝葉斯網絡構建提出改進方法，為高效挑選出具有依賴關系的屬性對，改進候選屬性對的生成機制，采用基于關系矩陣的過濾技術來縮減指數機制的搜索空間，優化貝葉斯網絡構建質量和效率。

1 相關工作

1.1 差分隱私

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

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

其中：D+tr表示將記錄tr添加到數據集D后產生的數據集?；谙噜彅祿o出ε?差分隱私定義如下。

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

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

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

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

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

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

1.2 貝葉斯網絡

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

圖1 含5個節點的貝葉斯網絡Fig.1 Bayesian network with five nodes

1.3 最大信息系數

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

定義5最大信息系數。給定屬性X，Y和有序對，樣本數量為n，將當前x?y平面劃分為a×b的網格G，并使屬性數據點都落入網格G中，定義屬性X和Y的最大互信息計算式（5）如下：

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

2 基于聚類分析技術的發布方法

2.1 PrivBC方法

PrivBayes 方法采用基于依賴統計分析的方法，在構建小規模網絡時可以得到理想結果；但在面臨大規模稀疏數據集時，方法的計算復雜性和網絡結構復雜度都將呈現出爆炸式增長，這勢必造成方法的可用性降低。文獻［22］引入方法分團思想對動態貝葉斯網絡進行分割，以降低抽樣狀態空間。文獻［23］指出，針對高維數據的發布需要輔以對屬性進行聚類或分組等方式進行降維?；耍疚尼槍傩灾g的復雜關系，引入方法聚類的思想，提出基于屬性聚類的貝葉斯網絡隱私數據發布方法，首先計算高維數據屬性之間的相關性，并對屬性進行聚類，然后分別對具有不同內部相關性的子集簇使用貝葉斯網絡作近似推理。

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

圖2 PrivBC數據發布方法流程Fig.2 Flowchart of PrivBC data publishing method

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

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

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

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

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

4）合成數據集發布：根據網絡結構N和加噪條件概率分布依次采樣每個屬性，生成擾動數據集(i=1，2，…，c)，根據此得到合成數據集D*，并將合成數據集進行發布。

2.2 屬性聚類方法

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

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

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

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

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

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

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

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

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

2.3 Bayes網絡改進

PrivBayes方法在構建貝葉斯網絡時為避免因過度訪問數據集而產生大量噪聲，采用貪婪方法選取屬性AP（Attribute Parent）對，每次AP對的選取都需要全部計算候選屬性集合中屬性對的評分，弱相關性屬性對的評分在節點選取中被重復計算，這無疑消耗了過多的計算資源?；诖?，本文采用關系矩陣過濾技術來壓縮候選空間，過濾掉Ω中弱相關屬性對。

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

2.4 方法復雜度分析

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

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

3 實驗與結果分析

3.1 實驗設置

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

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

表1 4個數據集信息描述Tab.1 Description of four datasets

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

3.2 方法誤差分析

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

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

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

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

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

3.3 方法有效性分析

為了對發布數據的有效性進行分析，參考文獻［4，7］選取NLTCS 和Adult 數據集，以加噪合成數據集的80%作為訓練集，20%作為測試集，在通過PrivBC、PrivBayes 方法產生的加噪合成數據集上構建分類模型。優秀的分類方法有文獻［28］的基于完全隨機森林的類噪聲濾波學習（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）方法構建分類模型。圖8 展示了不同數據集上方法基于參數ε變化的平均誤分類率，在NLTCS 數據集上，依據某個人：（a）是否能夠外出（如圖8（a）中Y=Outside）；（b）是否能夠游泳作為分類屬性作出預測。在Adult數據集上，依據某個人：（c）是否為男性；（d）是否結婚作為分類屬性作出預測。其中PrivBR 方法為經過候選屬性對縮減處理的PrivBayes 加噪方法，PrivateERM［30］方法通過對風險函數添加噪聲并優化擾動來輸出SVM 分類器，NoPrivacy在不加噪原始數據集上直接構建分類器。

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

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

3.4 方法性能分析

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

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

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

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

4 結語

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