屈晶晶，蔡 英，范艷芳，夏紅科

北京信息科技大學(xué)計(jì)算機(jī)學(xué)院，北京100101

大數(shù)據(jù)時(shí)代，數(shù)據(jù)的發(fā)布和利用是推動(dòng)知識(shí)、經(jīng)濟(jì)和社會(huì)進(jìn)步的關(guān)鍵。相關(guān)研究機(jī)構(gòu)會(huì)利用這些數(shù)據(jù)資源，進(jìn)行挖掘分析，從而為大眾提供更好的服務(wù)。然而在提供巨大利益的同時(shí)，向公眾發(fā)布個(gè)人數(shù)據(jù)將對(duì)用戶的隱私構(gòu)成相當(dāng)大的威脅。為了確保用戶隱私安全，需要對(duì)其進(jìn)行保護(hù)。但是，如何保證所發(fā)布的數(shù)據(jù)既是可用的，又不會(huì)泄露數(shù)據(jù)中所包含的隱私信息，成為數(shù)據(jù)發(fā)布隱私保護(hù)研究的重難點(diǎn)。

k-anonymity[1]及其擴(kuò)展的系列算法是保護(hù)用戶隱私信息的重要方式。k-anonymity 旨在使每個(gè)記錄與至少k-1 個(gè)其他記錄無(wú)法區(qū)分。k-anonymity 側(cè)重于處理準(zhǔn)標(biāo)識(shí)符屬性（例如，年齡、性別、郵政編碼和民族），因?yàn)樗鼈兛涉溄拥酵獠靠勺R(shí)別的數(shù)據(jù)源中的類似屬性。雖然k-anonymity 已被證明可提供相當(dāng)有用的匿名結(jié)果，但是在攻擊者可能獲得其他背景知識(shí)的前提下，對(duì)于小k，它很容易受到缺乏非匿名機(jī)密屬性的多樣性攻擊。已提出對(duì)k-anonymity 模型的若干改進(jìn)，包括l-diversity[2]和t-closeness[3]，可以防止這種情況發(fā)生。

差分隱私模型[4]作為一種眾所周知的隱私保護(hù)模型，可以在不對(duì)攻擊者的背景知識(shí)做任何假設(shè)的前提情況下，通過(guò)向數(shù)據(jù)查詢或者分析結(jié)果中添加一定量的噪聲進(jìn)行對(duì)數(shù)據(jù)的擾動(dòng)從而提供隱私保證。通過(guò)這種方式，發(fā)布的數(shù)據(jù)不會(huì)影響任何個(gè)人的隱私，因此差分隱私提供了比k-anonymity 模型更加強(qiáng)大的隱私保證。

差分隱私數(shù)據(jù)發(fā)布分為交互式框架和非交互式框架。在非交互式框架下，一般通過(guò)兩種形式生成差分隱私數(shù)據(jù)集：一種是數(shù)據(jù)管理者針對(duì)用戶可能提出的所有查詢請(qǐng)求計(jì)算查詢結(jié)果，然后執(zhí)行差分隱私保護(hù)算法進(jìn)行一次性發(fā)布，該結(jié)果與采用kanonymity 模型技術(shù)發(fā)布的通用數(shù)據(jù)集相比，無(wú)法提供數(shù)據(jù)分析需要的更多數(shù)據(jù)細(xì)節(jié)；另一種是發(fā)布一個(gè)經(jīng)過(guò)差分隱私處理的通用數(shù)據(jù)集，用戶可對(duì)處理過(guò)的數(shù)據(jù)集進(jìn)行任意的查詢操作，該方法需要在發(fā)布的數(shù)據(jù)集中加入大量噪聲，可能會(huì)破壞數(shù)據(jù)可用性。研究表明，可以通過(guò)降低查詢敏感度、合理分配隱私預(yù)算來(lái)提高差分隱私保護(hù)數(shù)據(jù)發(fā)布的可用性[5]。

因此，在發(fā)布差分隱私通用數(shù)據(jù)集的過(guò)程中，如何設(shè)計(jì)合適的算法降低查詢敏感度，減少噪聲誤差，提升數(shù)據(jù)可用性將會(huì)是本文重點(diǎn)考慮的問(wèn)題。除此之外，目前提出的差分隱私通用數(shù)據(jù)集發(fā)布方法大都針對(duì)處理單一屬性類型[6-8]，例如只對(duì)數(shù)值型屬性或者分類型屬性進(jìn)行數(shù)據(jù)發(fā)布，對(duì)于混合型數(shù)據(jù)發(fā)布的研究相對(duì)較少。然而，在實(shí)際應(yīng)用中，很多數(shù)據(jù)集都是包含混合屬性，如醫(yī)療數(shù)據(jù)、人口普查數(shù)據(jù)等。因此，研究針對(duì)混合數(shù)據(jù)集的差分隱私數(shù)據(jù)發(fā)布方法對(duì)滿足實(shí)際應(yīng)用需求具有重要意義。

1 相關(guān)工作和預(yù)備知識(shí)

1.1 相關(guān)工作

差分隱私最初被用于限制在數(shù)據(jù)庫(kù)上返回查詢答案時(shí)產(chǎn)生的披露風(fēng)險(xiǎn)，但是這種交互式場(chǎng)景下的應(yīng)用嚴(yán)格限制了數(shù)據(jù)分析，因?yàn)樗辉试S回答有限數(shù)量的查詢，從而促進(jìn)了非交互式場(chǎng)景下數(shù)據(jù)發(fā)布的隱私保護(hù)研究。

在非交互式場(chǎng)景下，發(fā)布滿足差分隱私數(shù)據(jù)集的主要方法是基于直方圖發(fā)布[9-12]。然而，當(dāng)屬性數(shù)量增加時(shí)，基于直方圖的方法具有嚴(yán)重的局限性：對(duì)于固定屬性粒度，直方圖區(qū)間的數(shù)量隨著屬性的數(shù)量呈指數(shù)增長(zhǎng)，這對(duì)計(jì)算成本和準(zhǔn)確性都有嚴(yán)重影響。除此之外，直方圖發(fā)布方法僅是提供了分區(qū)數(shù)據(jù)的近似計(jì)數(shù)而無(wú)法提供數(shù)據(jù)細(xì)節(jié)，因此限制了數(shù)據(jù)分析效用。因此可以通過(guò)生成滿足差分隱私的通用數(shù)據(jù)集來(lái)克服此限制。最簡(jiǎn)單的方法是收集一組滿足差分隱私的查詢結(jié)果，該組查詢要求查詢?cè)紨?shù)據(jù)集中的每個(gè)單獨(dú)記錄。但是，為此類查詢獲得滿足差分隱私所需的噪聲量太大，以至于差分隱私數(shù)據(jù)集無(wú)法保持可用性?？梢酝ㄟ^(guò)降低查詢敏感度、減少噪聲添加量來(lái)提高差分隱私保護(hù)數(shù)據(jù)發(fā)布的可用性。

聚類算法在依據(jù)屬性差異度對(duì)數(shù)據(jù)進(jìn)行分組預(yù)處理后，可以實(shí)現(xiàn)函數(shù)查詢敏感度由單一個(gè)體數(shù)據(jù)到組數(shù)據(jù)的分化，通過(guò)降低查詢敏感度可降低滿足差分隱私所需的噪聲量，從而提升數(shù)據(jù)可用性。

Li 等人[13]構(gòu)建了一種新模型，即將k-anonymity算法與差分隱私保護(hù)相結(jié)合，并將該隱私保護(hù)模型應(yīng)用于微數(shù)據(jù)的發(fā)布。趙興旺等人[14]提出了一種基于差分隱私保護(hù)k-means 聚類隱私保護(hù)方法，即區(qū)分所選中心點(diǎn)與設(shè)定點(diǎn)之間的隱私，但該方法的聚類可用性不僅依賴于隱私保護(hù)預(yù)算，還取決于數(shù)據(jù)集大小。Soria 等人[15-18]提出了一種非交互式方法，該方法使用微聚集和k-anonymity 模型將記錄分組到至少k個(gè)記錄中的簇中，以降低查詢函數(shù)靈敏度和添加到已發(fā)布數(shù)據(jù)集的噪聲量。文獻(xiàn)[15]指出，對(duì)于大小為n的數(shù)據(jù)集，至少需要k＞。文獻(xiàn)[16]設(shè)計(jì)了混合屬性數(shù)據(jù)集分組時(shí)需要的特殊微聚集算法，然后將k個(gè)微聚集數(shù)據(jù)集作為輸入，進(jìn)行差分隱私保護(hù)。文獻(xiàn)[17]通過(guò)執(zhí)行單個(gè)排名微聚合來(lái)解決前兩個(gè)文獻(xiàn)存在的問(wèn)題，可以實(shí)現(xiàn)k≥2，但是只能處理包含單個(gè)屬性的數(shù)據(jù)集。文獻(xiàn)[18]針對(duì)不同應(yīng)用場(chǎng)景，選擇出最佳差分隱私數(shù)據(jù)發(fā)布方案。文獻(xiàn)[19]研究了兩類交叉矩陣微聚集算法，分別為矩陣系數(shù)形式和頻譜分解形式。然后結(jié)合質(zhì)心和其他統(tǒng)計(jì)信息代替簇中的原始記錄。劉曉遷等人[20]提出了一種基于DBSCAN（density-based spatial clustering of applications with noise）聚類的差分隱私數(shù)據(jù)發(fā)布方法，但該方法僅適用于數(shù)值屬性數(shù)據(jù)集。王紅等人[21]提出一種基于OPTICS（ordering points to identify the cluster structure）聚類的差分隱私保護(hù)算法，但該方法同樣只適用于數(shù)值屬性數(shù)據(jù)集。

因此，本文提出了一種數(shù)據(jù)發(fā)布算法，可以對(duì)混合屬性數(shù)據(jù)集進(jìn)行差分隱私保護(hù)。k-prototype 聚類算法是處理混合數(shù)據(jù)類型的典型聚類分析算法。因此，本文針對(duì)k-prototype 算法改進(jìn)了對(duì)數(shù)據(jù)集中數(shù)值屬性和分類屬性的差異度計(jì)算公式，能夠更好地對(duì)混合數(shù)值屬性和分類屬性數(shù)據(jù)進(jìn)行聚類；除此之外，該算法通過(guò)聚類分組，可以降低差分隱私的敏感性從而減少所需添加的噪聲量，因此可以在提供隱私保護(hù)的同時(shí)提高數(shù)據(jù)可用性。

1.2 差分隱私保護(hù)

1.2.1 差分隱私定義

差分隱私保護(hù)技術(shù)通過(guò)向查詢結(jié)果中添加定量噪聲實(shí)現(xiàn)對(duì)數(shù)據(jù)的擾動(dòng)，以確保在任一數(shù)據(jù)集中插入、更改、刪除記錄的操作不會(huì)影響查詢結(jié)果，進(jìn)而達(dá)到隱私保護(hù)的目的。

定義1（ε-差分隱私[22]）設(shè)有隨機(jī)算法K，以及任何相鄰數(shù)據(jù)集D1和D2。若算法K滿足ε-差分隱私，則有：

其中，參數(shù)ε是隱私預(yù)算。算法K的隱私保護(hù)等級(jí)可以通過(guò)ε推導(dǎo)出來(lái)。ε越小，則表明隱私保護(hù)程度越高；反之，ε越大，則表明隱私保護(hù)程度越低。

1.2.2 噪音機(jī)制

實(shí)際應(yīng)用中，常用的噪音機(jī)制包括Laplace機(jī)制[22]與指數(shù)機(jī)制[23]。噪聲量會(huì)影響數(shù)據(jù)安全性和可用性，與全局敏感度[13]密切相關(guān)。

定義2（全局敏感度[22]） 存在任意一個(gè)函數(shù)f:D→Rd，f的全局敏感度定義為：

其中，D1和D2表示任何相鄰的數(shù)據(jù)集，f是在數(shù)據(jù)集D上執(zhí)行的查詢函數(shù)。全局敏感度Δf由查詢函數(shù)f決定。

定理1（Laplace 機(jī)制[22]）對(duì)于任意數(shù)據(jù)集D和函數(shù)f:D→Rd，若算法K的輸出結(jié)果滿足：

則算法K滿足ε-差分隱私保護(hù)。其中代表添加的噪聲量，噪音量與Δf成正比，與ε成反比，即查詢函數(shù)f的全局敏感度越大，所需噪音越大。Laplace機(jī)制主要處理數(shù)值型數(shù)據(jù)。

定理2（指數(shù)機(jī)制[23]） 給定一個(gè)可用性函數(shù)u:(D,r)→R，若算法K滿足：

則K滿足ε-差分隱私。其中，Δu為u(D,R)的全局敏感度。指數(shù)機(jī)制的關(guān)鍵技術(shù)是如何設(shè)計(jì)可用性函數(shù)u(D,R)（r∈Range，其中r表示從輸出域Range中所選擇的輸出項(xiàng)），u(D,R)用來(lái)評(píng)估輸出值r，u(D,R)越大，r被輸出的概率越大。指數(shù)機(jī)制主要處理非數(shù)值型數(shù)據(jù)。

1.2.3 差分隱私的組合性質(zhì)

差分隱私保護(hù)技術(shù)存在兩個(gè)重要的組合性質(zhì)[24]：序列組合性和并行組合性。

性質(zhì)1（序列組合性[24]）給定數(shù)據(jù)庫(kù)D，存在n個(gè)隨機(jī)算法K，設(shè)Ki(1 ≤i≤n)滿足εi-差分隱私，則Ki在D上的順序操作滿足差分隱私。

性質(zhì)2（并行組合性[24]）給定數(shù)據(jù)庫(kù)D，存在n個(gè)隨機(jī)算法K，設(shè)Ki(1 ≤i≤n)滿足εi-差分隱私，則Ki在D上的并行操作滿足max(εi)-差分隱私。

2 基于k-prototype 聚類的差分隱私混合數(shù)據(jù)發(fā)布算法（DP-k-prototype）

在隱私數(shù)據(jù)發(fā)布的背景下，可以將數(shù)據(jù)發(fā)布視為對(duì)數(shù)據(jù)集中每條記錄的連續(xù)查詢的收集答案。本章提出了基于k-prototype 聚類的差分隱私混合數(shù)據(jù)發(fā)布算法（DP-k-prototype）：采用k-prototype 聚類算法，首先隨機(jī)選取初始類中心，根據(jù)改進(jìn)的元組屬性差異度計(jì)算方法對(duì)數(shù)據(jù)集進(jìn)行聚類；然后根據(jù)最佳聚類結(jié)果，對(duì)每個(gè)聚類中的數(shù)值型屬性計(jì)算聚類中心，分類型屬性生成屬性值集合；接下來(lái)遍歷每一個(gè)數(shù)據(jù)記錄并確定其聚類類別，將數(shù)值型屬性替換為聚類中心值并采用拉普拉斯機(jī)制添加噪聲，對(duì)分類型屬性采用指數(shù)機(jī)制進(jìn)行選擇；最后生成差分隱私數(shù)據(jù)集。由于查詢函數(shù)的靈敏度被分化到每組數(shù)據(jù)的k個(gè)記錄中，因此可減少噪音添加量，提高數(shù)據(jù)可用性。

2.1 元組屬性差異度計(jì)算

現(xiàn)有的大多數(shù)數(shù)據(jù)表都是混合數(shù)據(jù)表，也就是說(shuō)，表中的數(shù)據(jù)屬性分為數(shù)值型和分類型。對(duì)于具有不同類型屬性的數(shù)據(jù)，存在不同的屬性差異度計(jì)算方法。假定在具有n個(gè)記錄和d維屬性的混合數(shù)據(jù)集D中，包含q維數(shù)值型屬性和p維分類型屬性（d=p+q），表示第i個(gè)數(shù)值型屬性，表示第j個(gè)分類型屬性。

與數(shù)值型屬性不同，分類型屬性需要通過(guò)建立概化層次樹(shù)來(lái)計(jì)算屬性差異度。每一個(gè)分類型屬性都要建立一棵概化層次樹(shù)。圖1 為Country 屬性的概化層次樹(shù)，葉子節(jié)點(diǎn)為Country 屬性上的各個(gè)屬性值。

Fig.1 Generalization hierarchy tree for“Country”圖1 Country 屬性概化樹(shù)

分類型屬性數(shù)據(jù)在不同程度上會(huì)影響著聚類結(jié)果，本文根據(jù)分類型屬性數(shù)據(jù)對(duì)聚類結(jié)果的影響程度和k-prototype 算法中分類型屬性權(quán)重所對(duì)應(yīng)的權(quán)值計(jì)算元組間的差異度,從而提高聚類精度。兩個(gè)元組間的差異度計(jì)算公式為：

其中，wj表示在第j個(gè)分類型屬性所占的權(quán)重。

k-prototype 聚類需要選擇一個(gè)合適的損失函數(shù)來(lái)計(jì)算數(shù)值型和分類型變量對(duì)聚類中心點(diǎn)的距離。假定數(shù)據(jù)集的聚類個(gè)數(shù)為k，yim取值為{0,1}，表示在第m(1 ≤m≤k)個(gè)聚類中是否存在元組i，存在則為1，不存在則為0，則損失函數(shù)可以定義為：

2.2 混合數(shù)據(jù)表中聚類中心點(diǎn)計(jì)算

對(duì)于具有不同屬性的數(shù)據(jù)，若使用單一方法通常會(huì)導(dǎo)致信息丟失和中心偏差等問(wèn)題。因此，本文采用了一種混合數(shù)據(jù)表的聚類中心求解方法。

假設(shè)存在具有n個(gè)記錄和d維屬性的混合數(shù)據(jù)集D，包括q維數(shù)值屬性和p維分類型屬性（d=p+q），數(shù)據(jù)集經(jīng)過(guò)聚類算法被聚為k類。

假設(shè)輸入數(shù)據(jù)集中的q維屬性Aq是數(shù)值屬性的。因此，如果屬性(i=1,2,…,q)已被聚類，則聚類Cm(m=1,2,…,k)具有km個(gè)記錄表示等價(jià)類Cm中的j(j=1,2,…,km)元組中屬性Aqi的值。聚類的數(shù)值屬性中心計(jì)算為：

式中，km是聚類Cm中的元組數(shù)。

2.3 噪音添加方式

針對(duì)數(shù)值型屬性，采用Laplace 機(jī)制為聚類中心添加噪聲，計(jì)算公式如下：

與數(shù)值型屬性不同，分類型屬性從一組有限類別中獲取值，由于將拉普拉斯噪聲添加到聚類中心沒(méi)有任何意義，另一種獲得差分隱私輸出的方法在于以概率方式選擇聚類中心，這可以通過(guò)指數(shù)機(jī)制來(lái)完成。該機(jī)制根據(jù)輸入數(shù)據(jù)、差分隱私參數(shù)和質(zhì)量標(biāo)準(zhǔn)選擇最接近最佳的中心點(diǎn)。在這種情況下，質(zhì)量標(biāo)準(zhǔn)是每個(gè)分類型屬性值出現(xiàn)的概率。形式上，給定具有離散輸出r的函數(shù)，該機(jī)制根據(jù)輸入數(shù)據(jù)和質(zhì)量標(biāo)準(zhǔn)選擇接近最優(yōu)的輸出，同時(shí)保留ε-差分隱私。每個(gè)輸出與選擇概率Pr(r)相關(guān)聯(lián)，選擇概率Pr(r)隨質(zhì)量標(biāo)準(zhǔn)呈指數(shù)增長(zhǎng)，如下所示：

2.4 算法描述

在本文中，基于k-prototype 聚類的差分隱私靜態(tài)數(shù)據(jù)發(fā)布算法主要用于發(fā)布包含數(shù)值型屬性和分類型屬性的混合數(shù)據(jù)集。本文算法分為聚類分組階段和數(shù)據(jù)發(fā)布階段，第一階段利用改進(jìn)的k-prototype 聚類算法實(shí)現(xiàn)對(duì)數(shù)據(jù)的聚類劃分，第二階段實(shí)現(xiàn)差分隱私數(shù)據(jù)發(fā)布。算法的具體流程如算法1 所示。

算法1DP-k-prototype

本算法第1～10 行是聚類分組階段，第11～17 行是差分隱私數(shù)據(jù)發(fā)布階段。第1 行，進(jìn)行m次初始中心點(diǎn)的選擇。第2～9 行，是初始中心點(diǎn)選擇后的聚類過(guò)程：首先，遍歷數(shù)據(jù)集中的每一個(gè)元組ta，采用元組屬性度計(jì)算方法分別計(jì)算元組ta與中心值Cj(1 ≤j≤k)的差異度div(ta,Cj)；其次，將其分到距離最近（具有最小差異度）的聚類中；再次，對(duì)于每個(gè)聚類，重新定位中心點(diǎn)并計(jì)算其中心值Cj(1 ≤j≤k)；最后，確定每個(gè)聚類中的元組是否發(fā)生更改，如果更改，返回第4行；如果沒(méi)有更改，則計(jì)算損失函數(shù)值Ei。第10 行，比較m次初始點(diǎn)選擇中損失函數(shù)值的結(jié)果，選擇損失函數(shù)值最小時(shí)的聚類結(jié)果。第11、12 行，對(duì)于每一個(gè)聚類，針對(duì)數(shù)值型屬性計(jì)算第j個(gè)聚類中的聚類中心值；針對(duì)分類型屬性則生成屬性值集合。第13～15行，針對(duì)數(shù)據(jù)集D中的每一條數(shù)據(jù)記錄ta：首先，判斷其聚類類別。其次，判斷每一維屬性是屬于數(shù)值屬性還是分類屬性。如果是數(shù)值型屬性，則將其替換為聚類中心值，然后采用Laplace 機(jī)制噪聲獨(dú)立地添加到每個(gè)屬性值中；如果是分類型屬性，則根據(jù)所屬聚類屬性值集合中該屬性的中心候選者的選擇標(biāo)準(zhǔn)，使用指數(shù)機(jī)制選擇所輸出的屬性值。最后，將數(shù)據(jù)集D中每一個(gè)數(shù)據(jù)記錄替換為滿足差分隱私的數(shù)據(jù)記錄；第16、17 行，生成并返回滿足差分隱私保護(hù)的數(shù)據(jù)集。

3 隱私分析

本文將從差分隱私的概念及組合性質(zhì)兩方面對(duì)DP-k-prototype算法的隱私性進(jìn)行分析證明。

定理3DP-k-prototype算法滿足ε-差分隱私。

證明設(shè)有任何相鄰數(shù)據(jù)集D1和D2，K(D1)和K(D2) 分別表示在數(shù)據(jù)集D1和D2上執(zhí)行DP-kprototype 算法后輸出的結(jié)果，S和O分別表示DP-kprototype 算法在相鄰數(shù)據(jù)集D1和D2上所有數(shù)值屬性數(shù)據(jù)和分類屬性數(shù)據(jù)輸出的結(jié)果,?表示滿足差分隱私的數(shù)據(jù)集。根據(jù)差分隱私保護(hù)的要求，在原始數(shù)據(jù)集中改變?nèi)我庖粭l記錄后，算法K的輸出結(jié)果概率幾乎沒(méi)有顯著變化，因此即證明≤exp(ε)。令f(D1)和f(D2)分別表示在數(shù)據(jù)集D1和D2的查詢結(jié)果，表示在上的查詢結(jié)果。針對(duì)數(shù)值屬性數(shù)據(jù)，Pr[K(D1)∈S]∝，則：

根據(jù)差分隱私的并行組合性質(zhì)[17]，對(duì)于數(shù)據(jù)集D中沒(méi)有交集的數(shù)據(jù)執(zhí)行隱私保護(hù)預(yù)算為ε的隨機(jī)算法K，那么整個(gè)數(shù)據(jù)集均滿足ε-差分隱私。在DPk-prototype 算法中，由于k個(gè)聚類內(nèi)的數(shù)據(jù)均無(wú)交集，根據(jù)差分隱私的并行組合性質(zhì)，為每個(gè)聚類分配的隱私預(yù)算均為該算法的整體隱私預(yù)算ε。與此同時(shí)，每個(gè)聚類中數(shù)值型屬性和分類型屬性數(shù)據(jù)也均無(wú)交集，根據(jù)差分隱私的并行組合性質(zhì)，為每個(gè)屬性維度分配的隱私預(yù)算均為該聚類的隱私預(yù)算ε，且已證明數(shù)值型屬性數(shù)據(jù)和分類型屬性數(shù)據(jù)的計(jì)算查詢滿足ε-差分隱私。因此，DP-k-prototype 算法滿足ε-差分隱私。

4 實(shí)驗(yàn)評(píng)估

4.1 實(shí)驗(yàn)數(shù)據(jù)集

實(shí)驗(yàn)數(shù)據(jù)集選擇隱私保護(hù)研究領(lǐng)域被廣泛使用的UCI 機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)中的Adult 數(shù)據(jù)集，該數(shù)據(jù)集由48 842 個(gè)記錄和14 個(gè)屬性組成。刪除具有空屬性的記錄后，共有30 162 條記錄。為了同時(shí)考慮具有異構(gòu)屬性類型的數(shù)據(jù)，本文從“Adult”選取8 個(gè)屬性如表1 所示，派生5 個(gè)評(píng)估數(shù)據(jù)集。其中第一個(gè)評(píng)估數(shù)據(jù)集包括3 個(gè)屬性（2 個(gè)數(shù)字型屬性和1 個(gè)分類型屬性），每個(gè)評(píng)估數(shù)據(jù)集增加1 個(gè)分類型屬性，最后一個(gè)評(píng)估數(shù)據(jù)集包括8 個(gè)屬性（2 個(gè)數(shù)字型屬性和6 個(gè)分類型屬性）。

Table 1 Adult dataset properties表1 Adult數(shù)據(jù)集屬性

4.2 實(shí)驗(yàn)評(píng)價(jià)標(biāo)準(zhǔn)

在本文提出的方法中，數(shù)據(jù)可用性是通過(guò)由聚類中心替換聚類內(nèi)的記錄且采用差分隱私保護(hù)技術(shù)所產(chǎn)生的信息損失來(lái)測(cè)量。其中，信息損失可以通過(guò)誤差平方和（sum of squared errors，SSE）量化，這是聚類中通用的信息損失測(cè)量方法。SSE 被定義為待發(fā)布數(shù)據(jù)集中的原始記錄元組與差分隱私數(shù)據(jù)集中對(duì)應(yīng)元組之間距離的平方和，計(jì)算公式如下：

對(duì)于數(shù)值型屬性，d(ta(Ai),ta′(Ai))對(duì)應(yīng)于標(biāo)準(zhǔn)歐幾里德距離，而對(duì)于分類型屬性，使用式（7）計(jì)算其距離。

隱私保護(hù)能力通過(guò)信息披露來(lái)衡量，信息披露越小，隱私保護(hù)能力越強(qiáng)。信息披露表示為與差分隱私數(shù)據(jù)集正確匹配的原始數(shù)據(jù)記錄的百分比，即記錄關(guān)聯(lián)（record linkages，RL）：

其中，n表示原始數(shù)據(jù)集的數(shù)據(jù)記錄數(shù)量，差分隱私數(shù)據(jù)記錄t′的記錄關(guān)聯(lián)概率Pr(t′)計(jì)算為：

其中，G是距離t′最小的原始記錄集合，距離采用式（13）進(jìn)行計(jì)算。如果正確的原始記錄t在G中，則Pr(t′) 表示在G中猜測(cè)t的概率，即1/|G| ；否則，Pr(t′)=0。由于差分隱私并不排除記錄鏈接成功的可能性。因此，RL 越小，隱私泄露的可能性就越低，隱私保護(hù)能力就越好。

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

該實(shí)驗(yàn)將本文提出的DP-k-prototype 算法與MDAV（maximum distance to average vector）[16]算法以及標(biāo)準(zhǔn)差分隱私算法在Adult 數(shù)據(jù)集上進(jìn)行比較。選擇MDAV 算法的原因是，該算法是處理混合屬性數(shù)據(jù)集的差分隱私數(shù)據(jù)發(fā)布算法，且為該領(lǐng)域的經(jīng)典算法。而標(biāo)準(zhǔn)差分隱私算法則是不對(duì)混合數(shù)據(jù)集進(jìn)行任何分組處理，對(duì)每一條記錄執(zhí)行查詢并進(jìn)行差分隱私處理。

將隱私參數(shù)ε設(shè)置為{0.01,0.10,1.00,10.00}，根據(jù)不同屬性個(gè)數(shù)d(d={4,8}) 不斷調(diào)整聚類個(gè)數(shù)k(3 ≤k≤100)的大小，以進(jìn)行數(shù)據(jù)可用性對(duì)比實(shí)驗(yàn)，實(shí)驗(yàn)中信息損失SSE 結(jié)果如圖2 所示。當(dāng)ε={0.01,0.10}時(shí)，SSE 較大，當(dāng)ε={1.00,10.00}時(shí)，SSE 較小，并逐漸減小。當(dāng)ε=0.01 時(shí)，所添加噪聲量非常高，即使在采用本文算法降噪的情況下，數(shù)據(jù)可用性也非常低。隨著聚類個(gè)數(shù)k值增大，當(dāng)ε={1.00,10.00}時(shí)，數(shù)據(jù)可用性逐步提升。

Fig.2 Changes in SSE when d is unchanged and k is changed圖2 當(dāng)d 值確定、k 值變化時(shí)，SSE 變化情況

Fig.3 Changes in SSE when k is unchanged and d is changed圖3 當(dāng)k 值確定、d 值變化時(shí)，SSE 變化情況

圖3 根據(jù)聚類個(gè)數(shù)k(k={4,20,40})不斷調(diào)整混合數(shù)據(jù)集屬性個(gè)數(shù)，以進(jìn)行數(shù)據(jù)可用性對(duì)比實(shí)驗(yàn)。在圖2中，可以看到隨著屬性數(shù)量的不斷增加，SSE也不斷增加。與圖2的表現(xiàn)一致，當(dāng)ε={0.01,0.10}時(shí)，SSE較大（3 ≤d≤8），數(shù)據(jù)可用性較差；當(dāng)ε={1.00,10.00}時(shí)，SSE 差距較小，并逐漸減小。與此同時(shí)，在每次調(diào)整的混合數(shù)據(jù)集屬性個(gè)數(shù)（3 ≤d≤8）中，前兩個(gè)屬性始終是數(shù)值型屬性,每次只增加一個(gè)分類型屬性。由于不同的分類型屬性個(gè)數(shù)不同，因此生成概化樹(shù)產(chǎn)生的信息損失也不同。故隨著屬性的增加，信息損失量增長(zhǎng)趨勢(shì)與分類型屬性個(gè)數(shù)密切相關(guān)。

圖4 中，將屬性個(gè)數(shù)d設(shè)為8，隱私預(yù)算ε設(shè)為{0.01,0.10,1.00,10.00}，隨著聚類個(gè)數(shù)k的變化，信息披露RL 對(duì)比分析如圖4 所示。隨著聚類個(gè)數(shù)k的增加，當(dāng)ε={0.01,0.10,1.00}時(shí)，RL 值的變化幅度較小，基本維持在0.002%左右；當(dāng)ε=10.00 時(shí)，RL 值的變化呈現(xiàn)上升趨勢(shì)。這是因?yàn)楫?dāng)ε越大，添加的噪聲就越少，導(dǎo)致出現(xiàn)信息披露的風(fēng)險(xiǎn)就越高，因此隱私保護(hù)能力就越弱。從圖2 中可以看出，SSE 的大小直接取決于ε的值，當(dāng)ε=1.00 或10.00 時(shí)，其數(shù)據(jù)可用性差距不大，但是ε越大，其隱私保護(hù)能力越弱，因此當(dāng)ε=1.00 時(shí)獲得最佳結(jié)果。

Fig.4 Changes in RL when d equals 8 and k is changed圖4 當(dāng)d=8、k 值變化時(shí)，RL 變化情況

Fig.5 Comparison of three algorithms when ε=1.00,d is unchanged and k is changed圖5 當(dāng)ε=1.00、d 值確定、k 值變化時(shí)，三個(gè)算法情況比較

圖5 將本文提出算法DP-k-prototype 與同是處理混合屬性數(shù)據(jù)集的MDAV[9]算法以及標(biāo)準(zhǔn)差分隱私算法進(jìn)行比較。當(dāng)ε=1.00，d={4,8}時(shí)，隨著k的增加，MDAV 算法的SSE 在逐漸減小，DP-k-prototype算法的SSE 在逐漸減小后更趨于保持穩(wěn)定，且DP-kprototype 的數(shù)據(jù)可用性始終高于MDAV。這是因?yàn)镸DAV 算法對(duì)輸入數(shù)據(jù)的順序比較敏感，由微聚集形成的聚類不太均勻，因此會(huì)產(chǎn)生比較大的信息損失。而DP-k-prototype 算法在聚類的過(guò)程中，針對(duì)全局進(jìn)行考慮，將屬性差異度最小的數(shù)據(jù)聚為一類，與數(shù)據(jù)輸入順序無(wú)關(guān)。

5 結(jié)束語(yǔ)

本文提出了一種可以在混合數(shù)據(jù)集上執(zhí)行差分隱私的數(shù)據(jù)發(fā)布方法。針對(duì)這個(gè)問(wèn)題，考慮了改進(jìn)kprototype 聚類算法，并通過(guò)對(duì)數(shù)據(jù)集中的分類和數(shù)值屬性使用不同的方法計(jì)算屬性差異度。本文方法旨在將更可能相關(guān)的類似記錄分組，以降低差分隱私的敏感度和添加到查詢答案中的噪聲量。結(jié)合聚類中心值，對(duì)原始記錄采用差分隱私保護(hù)技術(shù)進(jìn)行處理保護(hù)，針對(duì)數(shù)值型屬性使用Laplace 機(jī)制，分類型屬性使用指數(shù)機(jī)制，從而在提供隱私保護(hù)的同時(shí)提高數(shù)據(jù)可用性。