楊高明，方賢進(jìn)，肖亞飛

安徽理工大學(xué) 計(jì)算機(jī)科學(xué)與工程學(xué)院，安徽 淮南 232001

1 引言

研究機(jī)構(gòu)和互聯(lián)網(wǎng)公司正在以各種方法收集個(gè)人數(shù)據(jù)，這些數(shù)據(jù)不可避免地包含個(gè)人隱私信息，如果直接發(fā)布這些數(shù)據(jù)將會(huì)導(dǎo)致用戶隱私信息的泄露[1-2]。如AOL（American Online）曾經(jīng)發(fā)布數(shù)據(jù)用于競(jìng)賽，結(jié)果導(dǎo)致一位老年婦人個(gè)人隱私泄露[3]。因此，必須在發(fā)布之前進(jìn)行數(shù)據(jù)凈化處理，以保護(hù)個(gè)人隱私信息。隱私保護(hù)的數(shù)據(jù)發(fā)布主要關(guān)注數(shù)據(jù)的微觀方面，這種方法把記錄的屬性分為三類：（1）身份屬性（如姓名、身份證號(hào)碼、微信賬號(hào)等），其相當(dāng)于數(shù)據(jù)庫(kù)的主鍵（key），可以唯一地標(biāo)識(shí)個(gè)體；（2）準(zhǔn)標(biāo)識(shí)符（quasi-identifier，QI）屬性（如郵政編碼、年齡和性別等），其值的組合可以潛在地標(biāo)識(shí)個(gè)體；（3）敏感屬性（如所患疾病和收入等），表明個(gè)人不想對(duì)外泄露的敏感信息。許多研究者已經(jīng)發(fā)現(xiàn)，在發(fā)布數(shù)據(jù)之前僅僅刪除用戶的身份屬性，并不能保護(hù)發(fā)布數(shù)據(jù)表中的個(gè)人隱私信息[4-5]。QI屬性可能被攻擊者與其他公共數(shù)據(jù)集聯(lián)系起來(lái)，獲得個(gè)人的隱私信息，這被稱作數(shù)據(jù)發(fā)布中的鏈接攻擊（link attack），這種攻擊主要導(dǎo)致用戶身份泄露和屬性泄露。如果攻擊者可以從發(fā)布的數(shù)據(jù)中識(shí)別個(gè)人，則會(huì)發(fā)生身份泄露；而攻擊者通過(guò)屬性鏈接揭示個(gè)人的敏感屬性則會(huì)發(fā)生屬性泄露。

為應(yīng)對(duì)鏈接攻擊導(dǎo)致的用戶身份泄露和敏感屬性泄露，學(xué)者們提出了許多隱私保護(hù)數(shù)據(jù)發(fā)布模型并試圖建立一種通用的隱私保護(hù)模型。k-匿名[3]是關(guān)系數(shù)據(jù)庫(kù)文獻(xiàn)中提出的第一個(gè)有影響力的模型，它使用泛化（generalization）概念來(lái)提供隱私保護(hù)，該方法將屬性的細(xì)粒度值泛化為不特定的粗粒度屬性值，以阻止攻擊者根據(jù)準(zhǔn)標(biāo)識(shí)符屬性值把具體的個(gè)人與其他k-1個(gè)體區(qū)分開來(lái)，其核心思想是確保至少k條準(zhǔn)標(biāo)識(shí)符屬性值相同的記錄在同一個(gè)組內(nèi)。后來(lái)，學(xué)者引入l-多樣性[6]來(lái)解決k-匿名存在的限制，以抵御身份泄露和屬性泄露，使攻擊者無(wú)法實(shí)現(xiàn)同質(zhì)攻擊或背景知識(shí)攻擊。t-closeness[7]進(jìn)一步優(yōu)化了多樣性的概念，并要求每個(gè)等價(jià)類的敏感值的分布與數(shù)據(jù)集的整體分布密切相關(guān)，在任何等價(jià)類中的敏感屬性的分布接近整個(gè)表中屬性的分布。以上基于泛化思想提出的隱私保護(hù)數(shù)據(jù)發(fā)布匿名化模型并不能完全阻止用戶的隱私泄露，后來(lái)Dwork[8]提出了差分隱私的概念，確保添加或刪除單個(gè)記錄不會(huì)顯著影響任何分析結(jié)果的輸出。差分隱私在交互式的基礎(chǔ)上實(shí)現(xiàn)隱私保護(hù)，其實(shí)現(xiàn)機(jī)制是添加拉普拉斯噪音或者指數(shù)噪音，目前很多研究者在差分隱私方面做了大量工作，取得了豐富的研究成果[9]。

除了以概化為基礎(chǔ)的匿名化和以添加隨機(jī)噪音為基礎(chǔ)的差分隱私之外，隨機(jī)響應(yīng)方法也被用于發(fā)布數(shù)據(jù)[10-11]。該方法不像匿名化一樣將QI屬性值泛化為粗粒度值，而是根據(jù)一定的概率將原始值擾動(dòng)為其他值，他們專注于評(píng)估將目標(biāo)個(gè)體成功鏈接到其他記錄的風(fēng)險(xiǎn)。如Shen等人[12]假設(shè)數(shù)據(jù)擾動(dòng)在客戶端進(jìn)行，用戶不知道其他用戶的信息。他們的工作集中在購(gòu)物籃數(shù)據(jù)或一般分類數(shù)據(jù)的隨機(jī)化，而不是在鏈接攻擊下研究隨機(jī)化的隱私泄露。Cormode等人[13]是通過(guò)引入經(jīng)驗(yàn)隱私和數(shù)據(jù)效用的概念來(lái)解決這些挑戰(zhàn)，并通過(guò)改變每個(gè)模型的相應(yīng)參數(shù)來(lái)比較傳統(tǒng)隱私模型與差分隱私。再者，已有的基于隨機(jī)調(diào)查數(shù)據(jù)的方法并不能直接用于中心數(shù)據(jù)的發(fā)布，因?yàn)殡S機(jī)調(diào)查方法的擾動(dòng)矩陣P由調(diào)查者決定，與用戶數(shù)據(jù)無(wú)關(guān)，而中心數(shù)據(jù)的方法，其擾動(dòng)矩陣除了受數(shù)據(jù)發(fā)布者決定之外，還受到數(shù)據(jù)分布的影響。在前人已有的基礎(chǔ)上，Wang等人[14]在理論上證明了隨機(jī)響應(yīng)方法實(shí)現(xiàn)差分隱私的可行性。

以上采用隨機(jī)化實(shí)現(xiàn)隱私保護(hù)主要使用均勻擾動(dòng)方法，沒有考慮數(shù)據(jù)的分布情況，導(dǎo)致數(shù)據(jù)的效用和隱私保護(hù)之間沒有得到很好的平衡[15]，本文結(jié)合數(shù)據(jù)分布的情況對(duì)數(shù)據(jù)進(jìn)行擾動(dòng)，即考慮擾動(dòng)準(zhǔn)標(biāo)識(shí)符屬性又考慮擾動(dòng)敏感屬性，其應(yīng)用場(chǎng)景主要包括：政府部門或者企事業(yè)單位外包數(shù)據(jù)進(jìn)行數(shù)據(jù)分析或者數(shù)據(jù)挖掘。具體貢獻(xiàn)如下：研究了鏈接攻擊下的身份披露和屬性披露問(wèn)題，重點(diǎn)關(guān)注攻擊者得到用戶的準(zhǔn)標(biāo)識(shí)符屬性以后，成功預(yù)測(cè)目標(biāo)個(gè)體敏感屬性值的風(fēng)險(xiǎn)；提出了一個(gè)隨機(jī)化技術(shù)實(shí)現(xiàn)局部差分隱私的框架，系統(tǒng)地研究了隨機(jī)化方法防止鏈接攻擊的策略，有效解決了隨機(jī)化方法實(shí)現(xiàn)局部差分隱私參數(shù)P選擇問(wèn)題，在數(shù)據(jù)集滿足隱私保護(hù)要求的同時(shí)，最大化數(shù)據(jù)效用。最后，使用UCI機(jī)器學(xué)習(xí)庫(kù)的Adult數(shù)據(jù)集進(jìn)行了廣泛的實(shí)驗(yàn)，利用數(shù)據(jù)分布(KL-散度、卡方距離)有效驗(yàn)證了數(shù)據(jù)的分布變化情況。

2 基本概念

設(shè)數(shù)據(jù)庫(kù)DB具有N條記錄，每個(gè)記錄具有m+1個(gè)屬性，其中A1，A2，…，Am是m個(gè)準(zhǔn)標(biāo)識(shí)符屬性，S是敏感屬性。屬性Ai(S)具有di(ds)個(gè)不同的值，用0，1，…，di-1(ds-1)表示，并使用Ωi(Ωs)表示Ai(S)的域，Ωi={0，1，…，di-1}，ΩQI=Ω1×Ω2×…×Ωm是準(zhǔn)識(shí)別符的域，Ωs敏感屬性的域。對(duì)于給定的個(gè)體，準(zhǔn)標(biāo)識(shí)符屬性值對(duì)攻擊者是透明的，其中S表示敏感屬性，其值不應(yīng)與攻擊者需要識(shí)別的個(gè)人相關(guān)聯(lián)。一般而言，數(shù)據(jù)庫(kù)DB也可能包含其他屬性，這些屬性既不是敏感屬性也不是準(zhǔn)標(biāo)識(shí)符屬性，它們通常在發(fā)布的數(shù)據(jù)中保持不變。由于這些屬性不會(huì)導(dǎo)致隱私泄露風(fēng)險(xiǎn)或數(shù)據(jù)效用損失，此處將不討論它們。另外，本文主要討論單敏感屬性，而多敏感屬性可以在現(xiàn)有討論的基礎(chǔ)上推廣。

隨機(jī)響應(yīng)實(shí)現(xiàn)局部差分隱私的基本思想主要是：（1）對(duì)每一個(gè)準(zhǔn)標(biāo)識(shí)符屬性Ak，選擇屬性轉(zhuǎn)換矩陣（2）使用概率2，…，dk)隨機(jī)改變?cè)紝傩灾禐閿_動(dòng)屬性值，使之滿足局部差分隱私要求，此處表示第k個(gè)屬性的第i個(gè)取值與之類似。隨機(jī)化過(guò)程根據(jù)每個(gè)記錄的屬性獨(dú)立執(zhí)行，即執(zhí)行隨機(jī)化過(guò)程不考慮記錄之間的關(guān)系，與樸素貝葉斯網(wǎng)絡(luò)類似，假設(shè)各個(gè)屬性之間的關(guān)系獨(dú)立，而記錄的屬性之間的關(guān)系若不獨(dú)立則需要另行考慮。確定隨機(jī)化矩陣以后就可以生成擾動(dòng)數(shù)據(jù)，數(shù)據(jù)接收者根據(jù)擾動(dòng)數(shù)據(jù)和擾動(dòng)矩陣可以取得數(shù)據(jù)的統(tǒng)計(jì)特征，以及進(jìn)行數(shù)據(jù)分析或者挖掘工作。

2.1 失真矩陣選擇

使用隨機(jī)化方法對(duì)數(shù)據(jù)進(jìn)行隱私保護(hù)主要是尋找失真矩陣，它確定隨機(jī)數(shù)據(jù)的隱私和效用，如何找到具有隱私或效用約束的最優(yōu)失真矩陣是一個(gè)具有挑戰(zhàn)性的問(wèn)題。Huang和Du[16]應(yīng)用一種進(jìn)化多目標(biāo)優(yōu)化方法，從單個(gè)屬性的整個(gè)搜索空間中搜索最優(yōu)失真矩陣。然而，由于其高度的復(fù)雜性，該方法難以處理多個(gè)屬性。目前的隨機(jī)化矩陣主要是均勻隨機(jī)化及其變種。它們將每個(gè)QI屬性Ai（或敏感屬性S）的隨機(jī)化參數(shù)限制為：

換句話說(shuō)，對(duì)于每個(gè)屬性Ak的所有值，其以相同的概率pk保持不變，以概率qk被擾動(dòng)到其他值。這種擾動(dòng)方法主要缺點(diǎn)是不能反映數(shù)據(jù)的分布情況，導(dǎo)致數(shù)據(jù)效用下降。為解決這個(gè)問(wèn)題，提出考慮原始數(shù)據(jù)分布的解決方案。

前面已經(jīng)介紹了隨機(jī)響應(yīng)的基本思想，下面介紹隨機(jī)響應(yīng)的基本過(guò)程。對(duì)于每個(gè)記錄Ri，i=1，2，…，N，數(shù)據(jù)所有者使用失真矩陣Pk獨(dú)立地隨機(jī)化屬性Ak，k=1，2，…，m。具體來(lái)說(shuō)，對(duì)于具有dk個(gè)值的屬性Ak，隨機(jī)化過(guò)程將屬性值以一定的概率替換為為方便起見用表示第k個(gè)屬性值為v轉(zhuǎn)換為值u的概率，即有：

式中，i，j=1，2，…，dk。令，則Pk稱為Ak的失真矩陣，Pk的列總和等于1。對(duì)于敏感屬性，其處理方式與準(zhǔn)標(biāo)識(shí)符屬性一樣。運(yùn)用失真矩陣，可以把原始數(shù)據(jù)庫(kù)DB擾動(dòng)為，然后發(fā)布隨機(jī)數(shù)據(jù)集和失真矩陣P。數(shù)據(jù)發(fā)布者發(fā)布失真矩陣，是為了讓數(shù)據(jù)分析人員了解原始數(shù)據(jù)的隨機(jī)化大小，幫助數(shù)據(jù)分析人員估計(jì)原始數(shù)據(jù)分布。

2.2 局部差分隱私

數(shù)據(jù)的隱私需求有兩種不同的上下文環(huán)境：局部隱私場(chǎng)景，如個(gè)人在社交網(wǎng)站主動(dòng)披露個(gè)人信息；全局隱私場(chǎng)景，如機(jī)構(gòu)發(fā)布包含個(gè)人信息數(shù)據(jù)庫(kù)或基于這些數(shù)據(jù)庫(kù)回答某些問(wèn)題（例如，美國(guó)政府發(fā)布人口普查數(shù)據(jù)，Netflix公司等發(fā)布專有數(shù)據(jù)供他人數(shù)據(jù)分析）。對(duì)于這兩種情況都可以通過(guò)在發(fā)布數(shù)據(jù)之前將數(shù)據(jù)隨機(jī)化來(lái)實(shí)現(xiàn)差分隱私。本文主要研究局部隱私情況，該模式的數(shù)據(jù)提供者不信任數(shù)據(jù)收集者或者數(shù)據(jù)分析師。

隱私保護(hù)的主要目的是使攻擊者在凈化數(shù)據(jù)上推理得到與原始數(shù)據(jù)幾乎相同的結(jié)果，同時(shí)使用戶的隱私信息得以隱藏，差分隱私就是在這個(gè)概念的基礎(chǔ)上產(chǎn)生的。在差分隱私模式下，即使攻擊者具有無(wú)限的計(jì)算能力并且可以訪問(wèn)數(shù)據(jù)庫(kù)中除查詢數(shù)據(jù)之外的每個(gè)記錄，也不能確定某個(gè)特定用戶是否在數(shù)據(jù)庫(kù)中。由于差分隱私具有理論基礎(chǔ)的支持，得到了廣泛研究和應(yīng)用，最近，差分隱私的概念已經(jīng)擴(kuò)展到局部隱私環(huán)境[17]。實(shí)際上局部差分隱私可以看作全局差分隱私的特例，即敏感度為1的情況。

定義1（局部差分隱私）設(shè)有n個(gè)數(shù)據(jù)記錄，Ak是數(shù)據(jù)集DB的第k個(gè)屬性，其轉(zhuǎn)換矩陣為Pk，k∈{0，1，…，m}。機(jī)制 M 是將 Ak∈ΩAk隨機(jī)映射到ΩAk閾值內(nèi)的任何一個(gè)值，且ΩAk內(nèi)每一個(gè)閾值獨(dú)立同分布。對(duì)于非負(fù)數(shù)值ε，如果機(jī)制M是ε-局部差分隱私的，則有：

ε越小隱私保護(hù)效果越好，然而當(dāng)多次查詢，耗盡ε則會(huì)導(dǎo)致隱私泄露，故ε的選擇也需要根據(jù)實(shí)際情況確定。

2.3 數(shù)據(jù)效用及度量標(biāo)準(zhǔn)

隱私保護(hù)的數(shù)據(jù)發(fā)布除了滿足不泄露用戶隱私信息之外，還要滿足數(shù)據(jù)分析者對(duì)數(shù)據(jù)效用的要求。發(fā)布數(shù)據(jù)的最終目標(biāo)是最大限度地保留數(shù)據(jù)效用，同時(shí)降低屬性披露的風(fēng)險(xiǎn)，任何數(shù)據(jù)集的效用，無(wú)論是否隨機(jī)化，都會(huì)依賴于可能執(zhí)行的任務(wù)。有許多數(shù)據(jù)效用的度量標(biāo)準(zhǔn)，匿名化使用的效用度量標(biāo)準(zhǔn)之一是數(shù)據(jù)泛化高度，它是指數(shù)據(jù)泛化步驟的總數(shù)。然而，在隱私保護(hù)的數(shù)據(jù)發(fā)布領(lǐng)域這種方法存在的問(wèn)題是：對(duì)泛化高度相等的兩個(gè)匿名化組，其數(shù)據(jù)效用差距巨大。鑒于目前許多數(shù)據(jù)挖掘應(yīng)用與數(shù)據(jù)的概率分布有關(guān)，在評(píng)估數(shù)據(jù)庫(kù)的效用時(shí)，本文采用KL-散度、卡方度量數(shù)據(jù)的效用。

KL-散度(Kullback-Leibler divergence)是離散概率分布P和Q之間的對(duì)數(shù)差，用于找到兩個(gè)頻率分布之間距離的度量，此處用于查找原始數(shù)據(jù)的分布與隨機(jī)化后的數(shù)據(jù)相同屬性分布之間的距離，即它表示當(dāng)原始數(shù)據(jù)集變換為擾動(dòng)數(shù)據(jù)集之后其分布信息的丟失量，其計(jì)算公式如下：

除了采用KL-散度量化數(shù)據(jù)效用，文中還采用卡方距離比較原始數(shù)據(jù)和重建數(shù)據(jù)之間的分布差異，即統(tǒng)計(jì)樣本的實(shí)際觀測(cè)值與理論推斷值之間的偏離程度，其決定卡方值的大小?？ǚ街翟酱螅挤植寂c擾動(dòng)分布的差異越大；卡方值越小，原始分布與擾動(dòng)分布的差異越小，若兩個(gè)值完全相等時(shí)，卡方值就為0，表明理論值完全符合。給定兩個(gè)分布P=(p1，p2，…，pm)，Q=(q1，q2，…，qm)，其卡方距離如下：

3 屬性披露和鏈接攻擊

確定隨機(jī)化概率轉(zhuǎn)換矩陣Pk以后，攻擊者將觀測(cè)值視為Ak的真實(shí)值是不合理的。相反，攻擊者可以根據(jù)觀察到的數(shù)據(jù)和發(fā)布的隨機(jī)參數(shù)來(lái)嘗試估計(jì)原始值。假設(shè)攻擊者能夠得到擾動(dòng)數(shù)據(jù)集及后驗(yàn)概率，并采用以下概率擾動(dòng)策略：對(duì)于任何u，v∈ΩAk，在概率情況下計(jì)算其中表示當(dāng)攻擊者觀察時(shí)，而實(shí)際原始值A(chǔ)k=u的后驗(yàn)概率。由貝葉斯定理可以得到以下計(jì)算公式：

式中，πw表示Ak=ω時(shí)的概率分布。下面，分別對(duì)二值屬性和多值屬性進(jìn)行討論，并進(jìn)一步討論其組合。

3.1 二值屬性隨機(jī)化矩陣的構(gòu)造

這種擾動(dòng)方式要求每列的概率和為1，在隨機(jī)響應(yīng)相關(guān)文獻(xiàn)中，一般設(shè)pu=pv。為有效地增加數(shù)據(jù)的隨機(jī)性和提高數(shù)據(jù)的效用，此處采用雙重?cái)_動(dòng)的方式。首先，計(jì)算二進(jìn)制屬性的每一個(gè)屬性的值在數(shù)據(jù)集中所占的比例，分別為pu、pv，并根據(jù)給定的隱私保護(hù)參數(shù)ε計(jì)算出pu、pv與ε的關(guān)系。第一次擾動(dòng)根據(jù)原始取值進(jìn)行擾動(dòng)，比如要擾動(dòng)的數(shù)據(jù)值為u，則生成隨機(jī)函數(shù)，并把隨機(jī)函數(shù)以pu為界分為兩部分，若隨機(jī)值位于[1，pu]，則擾動(dòng)值保持不變；若隨機(jī)值位于(pu，1]，則需要第二次擾動(dòng)。每一步擾動(dòng)都要根據(jù)它們?cè)跀?shù)據(jù)分布中的占比，并考慮隱私保護(hù)參數(shù)ε，具體過(guò)程見算法1。二值屬性得到的擾動(dòng)矩陣PBB為：

對(duì)于二進(jìn)制屬性，一般采用均勻擾動(dòng)，這種擾動(dòng)方法把對(duì)角線元素設(shè)為p，0.5＜p≤1，該方法的優(yōu)點(diǎn)是可以排除離群點(diǎn)對(duì)數(shù)據(jù)的干擾，缺點(diǎn)是所有數(shù)據(jù)均勻出現(xiàn)，違反了數(shù)據(jù)的自然規(guī)律，鑒于此，本文提出使用數(shù)據(jù)的原始分布作為隨機(jī)擾動(dòng)基礎(chǔ)，并在隨后的實(shí)驗(yàn)中分析該方法對(duì)離群點(diǎn)影響。下面給出二值擾動(dòng)的基本方法。由于二值屬性僅僅有兩個(gè)值，可以分別用u和v表示。若u在原數(shù)據(jù)集中所占的比例為pu，則v所占的比例為1-pu。即采用的擾動(dòng)矩陣PB為：

式中，puv=P(u|v)，表示原始值為v擾動(dòng)為u的概率。Geng等人[18]已經(jīng)理論證明了局部差分隱私的最優(yōu)形式是采用樓梯機(jī)制（staircase mechanism），因此，此處令屬性值保持不變的概率為puu=pvv=eε(1+eε)，則pv=1-pu=1(1+eε)，帶入式（6），可得：

算法1二值屬性擾動(dòng)算法

算法1的行1主要對(duì)數(shù)據(jù)集進(jìn)行統(tǒng)計(jì)工作，用于計(jì)算隨機(jī)擾動(dòng)方法是否滿足局部差分隱私，行3是為了確保數(shù)據(jù)分布傾斜情況下滿足差分隱私要求，行4～8用于處理屬性Ak=u的情況，行9～11用于處理Ak=v的情況。對(duì)于這兩種情況，都需要根據(jù)數(shù)據(jù)的原始分布狀態(tài)進(jìn)行二次擾動(dòng)。

下面討論采用PBB擾動(dòng)矩陣的數(shù)據(jù)集，是否滿足局部差分隱私的要求。根據(jù)局部差分隱私的定義，此處僅僅討論給定ε的值大于或等于0的情況。另外若由pu計(jì)算得到的ε′＞0.5ε，則令ε′=0.5ε，因此僅需討論ε取最大值的情況。

（1）屬性值u擾動(dòng)為u的概率為puu，擾動(dòng)為v的概率為pvu，由pu計(jì)算出ε′滿足：

由算法1行3知，ε′≤ 0.5ε，故puu/pvu≤ eε滿足局部差分隱私。

（2）屬性值v擾動(dòng)為v的概率為pvv，v擾動(dòng)為u的概率為puv，則有：

故pvv/puv滿足局部差分隱私。

3.2 多值屬性隨機(jī)化矩陣的構(gòu)造

設(shè)屬性Ak具有m個(gè)屬性值，分別用v1，v2，…，vm表示。若Ak=vi(i=1，2，…，m)在原數(shù)據(jù)集中所占的比例為pvi，則采用均勻擾動(dòng)有A?k=vj(j=1，2，…，m)，由此得擾動(dòng)矩陣PM為：的比率pvi，把隨機(jī)函數(shù)以pvi為界分為兩部分，若隨機(jī)值位于[0，pvi]，則擾動(dòng)值保持不變；若隨機(jī)值位于(pvi，1]，則需要第二次擾動(dòng)，這時(shí)仍根據(jù)它們?cè)诤瘮?shù)中的占比進(jìn)行擾動(dòng)，即擾動(dòng)時(shí)考慮它們?cè)谠紨?shù)據(jù)集的分布情況，具體過(guò)程見算法2。此時(shí)得到的擾動(dòng)矩陣PMB為式（9）所示：

與二進(jìn)制屬性的處理方式一樣，多值屬性也采用兩次擾動(dòng)的方式。首先，計(jì)算多值屬性的每一個(gè)值在數(shù)據(jù)集中所占的比例，設(shè)為pvi，i=1，2，…，m，并根據(jù)差分隱私參數(shù)ε計(jì)算它們之間的關(guān)系。第一次擾動(dòng)根據(jù)原始取值進(jìn)行擾動(dòng)，需要擾動(dòng)的數(shù)據(jù)值vi所占

式中，pvivj=P(vi|vj)，i，j=1，2，…，m，表示原始值為vj擾動(dòng)為vi的概率，與二值屬性相似，此處令pvi=eεi/(1+eεi)，i=1，2，…，m，帶入式（9）可得：

算法2多值屬性擾動(dòng)算法

算法2的行1用于統(tǒng)計(jì)屬性Ak的每一個(gè)值所占的比例，行2、3用于設(shè)置滿足局部差分隱私的隨機(jī)擾動(dòng)概率，行4～10用于處理屬性每個(gè)值的擾動(dòng)。

下面討論采用PMB擾動(dòng)矩陣的數(shù)據(jù)集，是否滿足局部差分隱私的要求。

（1）屬性值vi擾動(dòng)為vi的概率為pvivi，擾動(dòng)為vj的概率為pvivj，i，j=1，2，…，m，設(shè)由pvivj計(jì)算得到的差分隱私參數(shù)為ε′，則有：

式中，取ε=2 ln 4隨機(jī)擾動(dòng)即可滿足局部差分隱私。

（2）屬性值vi擾動(dòng)為vj的概率pvjvi，擾動(dòng)概率為pvkvi，i，j，k=1，2，…，m，則有：

式中，ε大于等于1即可滿足局部差分隱私。

3.3 多值屬性的保護(hù)

隱私保護(hù)的數(shù)據(jù)發(fā)布沒有統(tǒng)一地衡量隱私泄露標(biāo)準(zhǔn)，常用屬性披露風(fēng)險(xiǎn)衡量隱私泄露。假設(shè)攻擊者的目標(biāo)個(gè)體是r，準(zhǔn)標(biāo)識(shí)符屬性為QIr，則成功預(yù)測(cè)Sr的概率為Pr(Sr|QIr)。若攻擊者可以訪問(wèn)發(fā)布數(shù)據(jù)集了解數(shù)據(jù)集每個(gè)屬性的取值域，由其他渠道獲得目標(biāo)個(gè)體r（例如Alice）的QI值并且確定目標(biāo)個(gè)體在已發(fā)布的數(shù)據(jù)集中，但不知道發(fā)布數(shù)據(jù)中的哪個(gè)記錄屬于目標(biāo)個(gè)人。對(duì)數(shù)據(jù)發(fā)布者來(lái)說(shuō)，可以選擇是否發(fā)布失真矩陣PBB或PMB，若數(shù)據(jù)發(fā)布者為了讓分析人員更有效地分析數(shù)據(jù)，則可以選擇發(fā)布失真矩陣PBB或PMB。

設(shè)πi=P[X=ci]，i=1，2，…，k，π=(π1，π2，…，πk)T，n表示數(shù)據(jù)集的個(gè)數(shù)，Ti表示原始數(shù)據(jù)集中值為ci的屬性個(gè)數(shù)，Si表示擾動(dòng)數(shù)據(jù)集中值為ci的屬性個(gè)數(shù)，λi=P(Z=ci)，λ=(λ1，λ2，…，λk)T則有概率分布T=(T1，T2，…，Tk)T，S=(S1，S2，…，Sk)T，于是T～Mult(n，π)，S～Mult(n，λ)，此處λ=Pπ。需要注意的是數(shù)據(jù)發(fā)布者并不發(fā)布T1，T2，…，Tk，對(duì)數(shù)據(jù)分析者而言僅僅從擾動(dòng)的數(shù)據(jù)無(wú)從得知它們，因此π的值不能直接求得，只能由T的觀察值S求得。如果P是非奇異矩陣，?是λ的無(wú)偏估計(jì)，則?是π的無(wú)偏估計(jì)。λ的最大似然估計(jì)是則有：

π的無(wú)偏估計(jì)方差為：

式中，Dπ是對(duì)角矩陣，其對(duì)角元素為π1，π2，…，πk，Dλ的定義與Dπ類似。等式（12）的右邊第一項(xiàng)是數(shù)據(jù)集固有方差，第二項(xiàng)是隨機(jī)化導(dǎo)致的額外附加方差。

3.4 隨機(jī)擾動(dòng)的基本模式

數(shù)據(jù)集的屬性分為敏感屬性、準(zhǔn)標(biāo)識(shí)符屬性和其他屬性，攻擊者很容易根據(jù)原始數(shù)據(jù)集中準(zhǔn)標(biāo)識(shí)符屬性QIr推導(dǎo)出個(gè)體r的敏感屬性。為增加數(shù)據(jù)的不確定性、同時(shí)最大限度地保持?jǐn)?shù)據(jù)效用，下面針對(duì)敏感屬性、準(zhǔn)標(biāo)識(shí)符屬性以及它們的組合討論隨機(jī)化問(wèn)題。

敏感屬性隨機(jī)化（randomized response sensitive，RRS）：當(dāng)數(shù)據(jù)所有者僅對(duì)敏感屬性隨機(jī)化時(shí)，攻擊者使用觀察到的敏感值和等式（4）估計(jì)其敏感值。正確估計(jì)的概率是那么敏感屬性披露風(fēng)險(xiǎn)為

這種情況針對(duì)攻擊者知曉用戶身份，有效保護(hù)用戶敏感信息，主要處理用戶身份不敏感的場(chǎng)合。

準(zhǔn)標(biāo)識(shí)符屬性隨機(jī)化（randomized response QI，RRQI）：當(dāng)數(shù)據(jù)所有者僅對(duì)準(zhǔn)標(biāo)識(shí)符屬性進(jìn)行隨機(jī)化時(shí)，正確重構(gòu)QIr的概率由給出，因此敏感屬性披露的風(fēng)險(xiǎn)為其具體推導(dǎo)過(guò)程由下文等式（15）給出。

兩種屬性組合隨機(jī)化（randomized response both attributes，RRB）：當(dāng)數(shù)據(jù)所有者同時(shí)隨機(jī)化QI和S時(shí)，攻擊者首先需要正確重構(gòu)準(zhǔn)標(biāo)識(shí)符屬性值，其概率由給出，另外攻擊者還需要在正確重構(gòu)準(zhǔn)標(biāo)識(shí)符屬性值以后重構(gòu)敏感屬性值。這種隱私泄露情況與隨機(jī)化準(zhǔn)標(biāo)識(shí)符屬性類似，不再詳述。

下面對(duì)RRS、RRQI和RRB中敏感屬性披露風(fēng)險(xiǎn)進(jìn)行總結(jié)，并給出隨機(jī)化屬性披露風(fēng)險(xiǎn)的一般計(jì)算：假設(shè)個(gè)體r具有準(zhǔn)標(biāo)識(shí)符屬性QIr=α={i1，i2，…，im}，ik∈Ωk，它的敏感屬性Sr=u，u∈ΩS。給定目標(biāo)個(gè)體r的準(zhǔn)標(biāo)識(shí)符屬性值QIr，成功預(yù)測(cè)其敏感屬性值Sr的概率是：

等式（13）中計(jì)算Pr(Sr|QIr)所需的重建概率表達(dá)式，其準(zhǔn)標(biāo)識(shí)符的重構(gòu)概率由下式給出：

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

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

實(shí)驗(yàn)采用UCI機(jī)器學(xué)習(xí)數(shù)據(jù)集，該數(shù)據(jù)集包含48 842個(gè)記錄的美國(guó)人口普查數(shù)據(jù)，共有14個(gè)屬性。此處選取 education、maritial-status、occupation、native-country、workclass這5個(gè)屬性，其中workclass作為敏感屬性，其余屬性作為準(zhǔn)標(biāo)識(shí)符屬性。實(shí)驗(yàn)中利用KL-散度和χ2來(lái)測(cè)量原始敏感值分布和凈化數(shù)據(jù)集之間的距離，同時(shí)還驗(yàn)證程序執(zhí)行所需時(shí)間，檢驗(yàn)數(shù)據(jù)量增長(zhǎng)對(duì)運(yùn)行時(shí)間的影響。為消除概率波動(dòng)對(duì)實(shí)驗(yàn)數(shù)據(jù)的影響，每個(gè)實(shí)驗(yàn)運(yùn)行11次，目的是驗(yàn)證隨機(jī)化算法的穩(wěn)定性。

4.2 實(shí)驗(yàn)數(shù)據(jù)分析

一般情況下準(zhǔn)標(biāo)識(shí)符屬性和敏感屬性之間存在相關(guān)性，為減少相關(guān)性的干擾，在選取屬性值的時(shí)候進(jìn)行了屬性相關(guān)性分析，選取的5個(gè)屬性相關(guān)性較小，即假設(shè)屬性之間具有獨(dú)立性。為表示方便，把本文的算法稱為RRPP（randomized respond to achieve privacy preserving）。

隱私保護(hù)數(shù)據(jù)發(fā)布的目的是最大限度地減少信息損失和最小限度地泄露隱私信息，為達(dá)到度量這兩方面的目的，此處使用KL-散度和χ2來(lái)度量原始數(shù)據(jù)和擾動(dòng)數(shù)據(jù)之間的距離，其結(jié)果如表1、表2所示，其中表1是1次隨機(jī)響應(yīng)運(yùn)行結(jié)果，表2是10次運(yùn)行取平均值的結(jié)果。原始數(shù)據(jù)和擾動(dòng)數(shù)據(jù)之間的距離值越小，它們之間的差異越小，失真數(shù)據(jù)庫(kù)的效用越好。由表1和表2可以看到，在所有3個(gè)隨機(jī)化情景中，以KL-散度和χ2作為距離差異的效用損失在概率擾動(dòng)和均勻擾動(dòng)之間的差異（此處均勻擾動(dòng)轉(zhuǎn)移概率取p=0.60，p=0.75，p=0.90）。表中數(shù)據(jù)顯示，采用RRPP方法比均勻擾動(dòng)可以更有效地保留數(shù)據(jù)的效用，減少用戶信息的泄露。對(duì)均勻擾動(dòng)來(lái)說(shuō)，取p=0.90，攻擊者推測(cè)出用戶的敏感信息已經(jīng)非常大了。另外，由表1和表2的平行數(shù)據(jù)對(duì)比中可以看出，算法的1次運(yùn)行結(jié)果和10次運(yùn)行結(jié)果的平均值差異很小，說(shuō)明了算法較穩(wěn)定。

Table 1 Distance of original and perturbed dada(one time)表1 原始數(shù)據(jù)與擾動(dòng)數(shù)據(jù)的距離（1次）

由于小概率事件可以視為不可能事件，這會(huì)導(dǎo)致采用RRPP算法擾動(dòng)時(shí)發(fā)生屬性丟失現(xiàn)象。在后10次實(shí)驗(yàn)中，有3次發(fā)生native-country屬性中Holand-Netherlands屬性值丟失，1次發(fā)生Ireland屬性值丟失。而采用均勻擾動(dòng)p=0.60，p=0.75，p=0.90均沒有發(fā)生屬性值丟失現(xiàn)象。這可以解釋為RRPP算法對(duì)離群點(diǎn)具有一定的魯棒性。

Table 2 Distance of original and perturbed dada(ten times)表2 原始數(shù)據(jù)與擾動(dòng)數(shù)據(jù)的距離（10次）

表3是RRPP與均勻擾動(dòng)p=0.60，p=0.75，p=0.90的運(yùn)行時(shí)間，該時(shí)間包括擾動(dòng)、計(jì)算KL-散度、計(jì)算卡方的時(shí)間。之所以沒有把擾動(dòng)的時(shí)間單獨(dú)測(cè)量，主要是為了驗(yàn)證擾動(dòng)和進(jìn)行數(shù)據(jù)分析的時(shí)間是否可以接受。為了解算法的效率，采用執(zhí)行10次算法取平均值的方式度量運(yùn)行時(shí)間。對(duì)于RRPP算法其最小值為28.571 12 s，最大值為39.804 41 s。p=0.6時(shí)，運(yùn)行時(shí)間的最小值為22.012 51 s，最大值為35.628 62 s，p=0.75和p=0.90其運(yùn)行時(shí)間波動(dòng)較小。由運(yùn)行時(shí)間的對(duì)比可以看出，RRPP算法與均勻算法的運(yùn)行時(shí)間處于同一個(gè)數(shù)量級(jí)。

Table 3 Running time ofAdult data set表3 Adult數(shù)據(jù)集運(yùn)行時(shí)間 s

為驗(yàn)證數(shù)據(jù)增長(zhǎng)時(shí)擾動(dòng)算法的有效性，針對(duì)每個(gè)屬性以增量的方式驗(yàn)證其距離，橫軸表示增量，縱軸表示KL-散度和χ2，參與擾動(dòng)的元組數(shù)分別為1 000、2 000、4 000、8 000、16 000、32 000，這些數(shù)據(jù)是均勻抽樣所得。屬性分別取敏感屬性workclass和準(zhǔn)標(biāo)識(shí)符屬性education（對(duì)所取的5個(gè)屬性都進(jìn)行了驗(yàn)證，由于篇幅關(guān)系，此處僅選取兩個(gè)屬性作為說(shuō)明）。與驗(yàn)證Adult數(shù)據(jù)集全部數(shù)據(jù)類似，執(zhí)行算法11次，圖1（a）是敏感屬性值個(gè)數(shù)遞增workclass的KL-散度1次運(yùn)行結(jié)果，圖1（b）是敏感屬性值個(gè)數(shù)遞增workclass的χ2距離1次運(yùn)行結(jié)果；圖2（a）是敏感屬性值個(gè)數(shù)遞增workclass的KL-散度10次運(yùn)行取平均值的結(jié)果，圖2（b）是敏感屬性值個(gè)數(shù)遞增workclass的χ2距離10次運(yùn)行取平均值的結(jié)果。由圖1和圖2可以看出RRPP算法與均勻擾動(dòng)p=0.90的結(jié)果相近，說(shuō)明算法可以很好地保護(hù)用戶隱私和提供有效的數(shù)據(jù)效用。圖1的數(shù)據(jù)波動(dòng)性較大，而10次運(yùn)行結(jié)果取平均值則基本沒有大的數(shù)據(jù)波動(dòng)。另外，無(wú)論RRPP算法還是均勻擾動(dòng)在數(shù)據(jù)量較小時(shí)，其數(shù)據(jù)波動(dòng)性較大，說(shuō)明隨機(jī)響應(yīng)方法需要用于數(shù)據(jù)量較大的場(chǎng)合。

Fig.1 Distance of workclass betweenπ andπ?(one time)圖1 敏感屬性workclass的π和π?之間的距離（1次）

Fig.2 Distance of workclass betweenπandπ?(ten times)圖2 敏感屬性workclass的π和π?之間的距離（10次）

Fig.3 Distance of education betweenπandπ?(one time)圖3 準(zhǔn)標(biāo)識(shí)符屬性education的π和π?之間的距離（1次）

圖3（a）準(zhǔn)標(biāo)識(shí)符屬性education遞增時(shí)的KL-散度1次運(yùn)行結(jié)果，圖3（b）是準(zhǔn)標(biāo)識(shí)符屬性education遞增時(shí)的χ2距離1次運(yùn)行結(jié)果。圖4（a）準(zhǔn)標(biāo)識(shí)符屬性education遞增時(shí)的KL-散度10次運(yùn)行結(jié)果，圖4（b）是準(zhǔn)標(biāo)識(shí)符屬性education遞增時(shí)的χ2距離10次運(yùn)行結(jié)果。它們的結(jié)果與workclass基本相同。

由圖2和圖4可以看出，屬性不同，擾動(dòng)數(shù)據(jù)與原始數(shù)據(jù)之間的KL-散度差別不大，而χ2距離卻比較明顯，比較圖2（b）和圖4（b），可以明顯看出敏感屬性workclass和準(zhǔn)標(biāo)識(shí)符屬性education的χ2距離有所差別。不過(guò)，無(wú)論KL-散度還是χ2距離，都在一個(gè)數(shù)量級(jí)。

由圖1至圖4可以看出敏感屬性個(gè)數(shù)的增加對(duì)KL-散度和χ2影響很小，特別是數(shù)據(jù)量達(dá)到2 000以后，基本上處于非常穩(wěn)定的狀態(tài)。另外，在記錄很少的情況下有時(shí)會(huì)發(fā)生屬性值丟失現(xiàn)象，即對(duì)那些在總體中比率很小的屬性值在擾動(dòng)時(shí)發(fā)生丟失。比如在增量實(shí)驗(yàn)時(shí)，使用平均擾動(dòng)方法，幾乎不發(fā)生屬性值丟失現(xiàn)象，因此離群點(diǎn)得以保留，這會(huì)導(dǎo)致離群點(diǎn)表示的用戶隱私泄露。而RRPP方法則可以剔除離群點(diǎn)的影響，在對(duì)native-country屬性進(jìn)行擾動(dòng)過(guò)程中發(fā)生了從少數(shù)國(guó)家或地區(qū)移民美國(guó)的公民其屬性值丟失（在數(shù)據(jù)量等于1 000時(shí)，屬性值丟失嚴(yán)重），被大概率的屬性值取代，這樣會(huì)導(dǎo)致數(shù)據(jù)失真，但是保持了用戶的隱私。

Fig.4 Distance of education betweenπ andπ?(ten times)圖4 準(zhǔn)標(biāo)識(shí)符屬性education的π和π?之間的距離（10次）

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

針對(duì)均勻擾動(dòng)的隱私保護(hù)數(shù)據(jù)發(fā)布沒有考慮數(shù)據(jù)的原始分布問(wèn)題，提出一種根據(jù)數(shù)據(jù)的原始分布對(duì)發(fā)布數(shù)據(jù)進(jìn)行隨機(jī)擾動(dòng)的方法，并詳細(xì)討論了二進(jìn)制和多值屬性擾動(dòng)矩陣參數(shù)設(shè)置，以及擾動(dòng)矩陣滿足局部差分隱私的條件，最后設(shè)計(jì)實(shí)驗(yàn)予以驗(yàn)證，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行討論。實(shí)驗(yàn)結(jié)果表明，考慮數(shù)據(jù)原始概率情況下進(jìn)行隨機(jī)化擾動(dòng)顯著優(yōu)于均勻擾動(dòng)方法，相當(dāng)于均勻擾動(dòng)p=0.90的情況。實(shí)驗(yàn)結(jié)果表明，基于數(shù)據(jù)原始分布的隨機(jī)化方法可以更好地保持原始數(shù)據(jù)集的分布特性，在數(shù)據(jù)效用和披露風(fēng)險(xiǎn)方面具有較好的效果。然而，文中還有不完美的地方，主要是假設(shè)數(shù)據(jù)屬性之間關(guān)系獨(dú)立性，實(shí)際上屬性之間存在千絲萬(wàn)縷的聯(lián)系，下一步將對(duì)準(zhǔn)標(biāo)識(shí)符屬性之間存在強(qiáng)依賴關(guān)系時(shí)如何擾動(dòng)進(jìn)行研究，以更好地維持?jǐn)?shù)據(jù)效用，保護(hù)用戶的隱私信息。