基于OPTICS聚類的差分隱私保護(hù)算法的改進(jìn)

王 紅，葛麗娜，王蘇青，王麗穎，張翼鵬，梁竣程

(1.廣西民族大學(xué) 信息科學(xué)與工程學(xué)院，南寧 530006； 2.廣西民族大學(xué) 東盟研究中心(廣西科學(xué)實(shí)驗(yàn)中心)，南寧 530006； 3.深圳市億威爾信息技術(shù)股份有限公司，廣東 深圳 518000； 4.廣西廣播電視信息網(wǎng)絡(luò)股份有限公司，南寧 530006)(*通信作者電子郵箱66436539@qq.com)

0 引言

隨著網(wǎng)絡(luò)技術(shù)的發(fā)展，信息量呈現(xiàn)爆炸式的增長，如何收集、管理、分析和發(fā)布數(shù)據(jù)成為信息技術(shù)研究的重點(diǎn)。目前，以機(jī)器學(xué)習(xí)和數(shù)據(jù)挖掘?yàn)榛A(chǔ)的高級(jí)數(shù)據(jù)分析處理技術(shù)，使得在分析、使用數(shù)據(jù)上更加方便，但對(duì)于數(shù)據(jù)發(fā)布者來說，不經(jīng)過任何處理隨意將有關(guān)用戶的敏感信息進(jìn)行發(fā)布，將給用戶帶來不可預(yù)測(cè)的后果。近年來的信息安全事件頻繁發(fā)生，從QQ號(hào)碼被盜取、手機(jī)下載帶有病毒性的APP到電子銀行錢財(cái)?shù)膩G失，不少不法分子利用安全漏洞以及用戶敏感信息的泄露，給用戶造成了很大的困擾和損失，這就要求信息安全領(lǐng)域加強(qiáng)隱私信息保護(hù)的力度，給公眾用戶一個(gè)安全的網(wǎng)絡(luò)平臺(tái)。而最早的匿名隱私保護(hù)技術(shù)需要特殊的背景攻擊假設(shè)，一旦攻擊者掌握足夠相關(guān)信息，便容易出現(xiàn)鏈接攻擊和背景攻擊。Dwork[1]定義了及其嚴(yán)格的ε-差分隱私保護(hù)模型：即使攻擊者已經(jīng)知道除一條記錄外的所有記錄的敏感屬性，仍然無法推斷出有關(guān)這條記錄的任何敏感屬性，通過添加隨機(jī)噪聲便能夠?qū)τ脩舻拿舾行畔⑦M(jìn)行保護(hù)，同時(shí)保持添加過噪聲后的數(shù)據(jù)的統(tǒng)計(jì)性和屬性不變。目前，差分隱私保護(hù)在人口統(tǒng)計(jì)、推薦系統(tǒng)、網(wǎng)絡(luò)數(shù)據(jù)分析、搜索日志等方面有著重要應(yīng)用。

對(duì)吳偉民等[2]提出的DP-DBSCAN(Differential Privacy-Density-Based Spatial Clustering of Applications with Noise)差分隱私保護(hù)算法分析，針對(duì)DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[3]算法對(duì)參數(shù)輸入敏感性的問題，本文將DBSCAN算法的改進(jìn)算法——OPTICS(Ordering Points To Identify Clustering Structure)[4]算法應(yīng)用于差分隱私保護(hù)中，進(jìn)而提出改進(jìn)算法——DP-OPTICS(Differential Privacy-Ordering Points To Identify Clustering Structure)差分隱私保護(hù)算法。

1 差分隱私研究現(xiàn)狀

2006年Dwork首次提出了ε-差分隱私保護(hù)模型，主要是針對(duì)個(gè)人敏感信息泄露進(jìn)行隱私保護(hù)的一項(xiàng)技術(shù)，根據(jù)添加噪聲順序不同分為兩種方式：1)對(duì)原始數(shù)據(jù)直接添加噪聲機(jī)制，然后發(fā)布數(shù)據(jù)。這種方法的隱私保護(hù)性比較高，但是數(shù)據(jù)可用性較低。2)先對(duì)原始數(shù)據(jù)進(jìn)行轉(zhuǎn)換、壓縮、隨機(jī)擾動(dòng)等技術(shù)預(yù)處理，再對(duì)數(shù)據(jù)添加隨機(jī)噪聲，最后發(fā)布數(shù)據(jù)。這種方法信息有所缺損，但在減少發(fā)布誤差和提高數(shù)據(jù)可用性上有很大幫助。按照處理方式的不同主要有聚類變換、分類變換、層次樹變換、傅里葉變換等技術(shù)，其中聚類技術(shù)在這幾項(xiàng)預(yù)處理技術(shù)中關(guān)于數(shù)據(jù)發(fā)布的精度和時(shí)間復(fù)雜度整體對(duì)比上是比較優(yōu)良的。

Blum等[5]中首次將基于SuLQ框架的k-means算法應(yīng)用在差分隱私中；針對(duì)Blum所提方法應(yīng)用存在聚類結(jié)果可用性低的問題，Nissim等[6]提出抽樣—聚合框架隨機(jī)對(duì)抽樣數(shù)據(jù)進(jìn)行聚類，但是這種聚類方式只能在局部取得較好效果；Dwork等[7]進(jìn)而從預(yù)算分配的角度對(duì)基于k-means的差分隱私保護(hù)算法進(jìn)行了完善，但是仍然存在差分隱私保護(hù)k-means聚類結(jié)果可用性差的問題；李楊等[8]提出了IDPk-means聚類方法，使得聚類的可用性有較大提高。在滿足ε-差分隱私保護(hù)條件下，吳偉民等首次將基于密度的DBSCAN聚類算法用于差分隱私保護(hù)中，但是由于DBSCAN算法自身存在對(duì)參數(shù)輸入敏感的問題，進(jìn)而影響聚類效果以及噪聲添加，最終將會(huì)影響數(shù)據(jù)發(fā)布的可用性。OPTICS算法是在DBSCAN算法的基礎(chǔ)上進(jìn)行改進(jìn)的算法，解決了DBSCAN算法對(duì)參數(shù)輸入敏感的問題，本文將OPTICS算法應(yīng)用于差分隱私保護(hù)中，并提出相關(guān)的改進(jìn)算法——DP-OPTICS算法。

2 差分隱私保護(hù)相關(guān)知識(shí)

1)ε-差分隱私保護(hù)的定義。

定義1ε-差分隱私[1]。對(duì)于數(shù)據(jù)集D1和D2，至多存在一條不同的記錄(稱D1和D2為兄弟數(shù)據(jù)集)，Range(K)為隨機(jī)算法K的取值范圍，如果算法K在數(shù)據(jù)集D1和D2上的任意輸出為M∈Range(K)，能夠滿足：

Pr[K(D1)∈M]≤eε×Pr[K(D2)∈M]

(1)

則稱為算法K滿足ε-差分隱私。其中，Pr[K(D1)∈M]、Pr[K(D2)∈M]分別為輸出K(D1)和K(D2)為M的概率，ε是差分隱私參數(shù)，用來表示隱私保護(hù)程度，ε越小表示隱私保護(hù)程度越高、隱私泄露風(fēng)險(xiǎn)越低；反之，隱私泄露風(fēng)險(xiǎn)越高。

2)敏感度。

定義2 敏感度。差分隱私保護(hù)模型中敏感度是決定加入噪聲大小的關(guān)鍵參數(shù)，它指刪除數(shù)據(jù)集中任何一條記錄對(duì)查詢結(jié)果造成的最大影響。一般可以把敏感度分為全局敏感度[1]和局部敏感度[5]。給定一個(gè)函數(shù)集F、數(shù)據(jù)集為D、結(jié)果集為R，函數(shù)集中的任一函數(shù)f存在f(D)∈R，則F的全局敏感度為：

(2)

文中所提到的敏感度均為全局敏感度，D1和D2為兄弟數(shù)據(jù)集。

3)噪聲機(jī)制。

差分隱私保護(hù)算法的實(shí)現(xiàn)，主要是對(duì)敏感數(shù)據(jù)集中的數(shù)據(jù)信息添加噪聲，主要采用Laplace機(jī)制[9]和指數(shù)機(jī)制[10]。Laplace機(jī)制僅使用于數(shù)值型查詢結(jié)果，指數(shù)機(jī)制可以適用于實(shí)體對(duì)象、事務(wù)型等的查詢結(jié)果。本文主要采用Laplace機(jī)制。

定義3 Laplace機(jī)制。對(duì)于任意一個(gè)函數(shù)f:D→Rd,如果隨機(jī)算法K滿足ε-差分隱私，則向查詢結(jié)果中f(D)添加噪聲lap(Δf/ε),響應(yīng)值為：

K(D)=f(D)+lap(Δf/ε)

(3)

4)添加噪聲的方式。

定義4 同/異方差加噪方式[11-12]。在不考慮用戶查詢興趣點(diǎn)分布不均勻的情況下，認(rèn)為隨機(jī)查詢的每個(gè)數(shù)據(jù)屬性概率相同。若任意一條記錄i1和i2被查詢的概率相同，有隱私預(yù)算參數(shù)εi1=εi2則稱為同方差加噪方式；如果考慮記錄i1和i2被查詢的概率不相同，則隱私預(yù)算參數(shù)εi1≠εi2，則稱為異方差加噪方式。

5)差分隱私的組合性質(zhì)[13]。

6)隱私參數(shù)ε的選取。

隱私參數(shù)ε越小，所得到的數(shù)據(jù)隱私保護(hù)性越高，攻擊者能夠獲取具體的數(shù)據(jù)信息記錄就越困難，但是足夠小的隱私參數(shù)導(dǎo)致數(shù)據(jù)的可用性降低。如何選取隱私參數(shù)ε，一直是差分隱私保護(hù)的重要話題。何賢芒等[14]在Lee等[15]的基礎(chǔ)給出定理1以及定理2，具體內(nèi)容如下。

定理1 采用Laplace機(jī)制分布給函數(shù)f(D)添加lap(Δf/ε)噪聲，則結(jié)果集f(D)+lap(Δf/ε)落在(-∞,f(D)+μ+L)概率為：

(4)

其中：μ為概率密度中心位置參數(shù)，L為改變位置參數(shù)的變量值，可以給定具體數(shù)值。

定理2 設(shè)位置參數(shù)μ=0,L=0.5的情況下，攻擊者對(duì)于結(jié)果數(shù)據(jù)集查詢成功的概率是：

(5)

只要攻擊者所查詢的成功概率ρ≤δ，就能有效保證數(shù)據(jù)的隱私安全性，則隱私參數(shù)ε的選取上界滿足以下條件即可：

ε≤[ln 2(1-ρ)Δf]/L

(6)

可以看出隱私參數(shù)ε的選取與數(shù)據(jù)集大小無關(guān)，僅僅與查詢函數(shù)(Δf,L)和攻擊者的成功概率ρ有關(guān)。

7)差分隱私保護(hù)算法的度量。

a)算法性能。通?？紤]時(shí)間復(fù)雜度和漸進(jìn)噪聲誤差邊界作為性能的評(píng)價(jià)標(biāo)準(zhǔn)。

b)算法誤差。通常采用歐氏距離[16]、相對(duì)誤差[17]、絕對(duì)誤差[18]、誤差的誤差[19]等來度量誤差。

c)隱私預(yù)算參數(shù)ε的分配。常用的分配策略[20]，比如線性分配、均勻分配、指數(shù)分配、自適用性分配以及混合策略分配等。

3 基于OPTICS聚類的差分隱私保護(hù)改進(jìn)算法

3.1 基于OPTICS聚類的差分隱私保護(hù)

OPTICS算法和DBSCAN算法是基于密度的聚類算法，主要優(yōu)點(diǎn)是能夠根據(jù)數(shù)據(jù)集的稠密度發(fā)現(xiàn)任意形狀的聚類，且對(duì)噪聲數(shù)據(jù)不敏感，這些特點(diǎn)能夠較好地符合用戶查詢數(shù)據(jù)的概率大小以及差分隱私保護(hù)算法預(yù)處理數(shù)據(jù)的特點(diǎn)。OPTICS算法是在DBSCAN算法的基礎(chǔ)上引入了核心距離和可達(dá)距離[21]兩個(gè)概念。具體定義如下。

定義5 對(duì)象的E鄰域。給定對(duì)象半徑E內(nèi)的鄰域?yàn)樵搶?duì)象的E鄰域。

定義6 核心對(duì)象。如果對(duì)象E鄰域內(nèi)至少包含最小數(shù)目MinPts個(gè)對(duì)象，則稱該對(duì)象為核心對(duì)象。

定義7 直接密度可達(dá)。給定一個(gè)對(duì)象集合D，如果p和q的E鄰域內(nèi)，而q是一個(gè)核心對(duì)象，則我們說對(duì)象p從對(duì)象q出發(fā)是直接密度可達(dá)的。

定義8 基于密度的簇。基于密度可達(dá)性的最大的密度相連對(duì)象的集合。不屬于任何聚類中的數(shù)據(jù)或離散點(diǎn)被認(rèn)為是低頻對(duì)象。

定義9 核心距離(core-distance， cd)。對(duì)象p的核心距離是使{p}成為核心對(duì)象的最小E′。如果p不是核心對(duì)象，則p的核心距離沒有定義。

定義10 可達(dá)距離(reachability-distance， rd)。對(duì)象q關(guān)于另一個(gè)對(duì)象p的可達(dá)距離是p的核心距離和p與q之間的歐幾里得距離之間的較大值。如果p不是核心對(duì)象，p和q之間的可達(dá)距離沒有定義。

基于OPTICS聚類的差分隱私保護(hù)算法如算法1所示。

算法1 基于OPTICS聚類的差分隱私保護(hù)算法。

步驟1 創(chuàng)建隊(duì)列L1，L2，L，有序隊(duì)列L1用來存儲(chǔ)核心對(duì)象及核心對(duì)象的直接密度可達(dá)對(duì)象，并按可達(dá)距離的升序排序；結(jié)果隊(duì)列L2用來存儲(chǔ)樣本點(diǎn)的輸出次序；輸出隊(duì)列L用來存儲(chǔ)聚類結(jié)果中添加Laplace噪聲后的數(shù)據(jù)。

步驟2 如果樣本集D中所有點(diǎn)都已處理完，則算法結(jié)束；否則選擇一個(gè)未處理(不在L2隊(duì)列中)且為核心對(duì)象的樣本點(diǎn)，找到其所有直接密度可達(dá)樣本點(diǎn)，如果該樣本點(diǎn)不存在于結(jié)果隊(duì)列中，則將其放入有序隊(duì)列中，并按可達(dá)距離排序。

步驟3 如果L1為空，則跳轉(zhuǎn)到步驟2；否則，從有序隊(duì)列中取出第一個(gè)樣本點(diǎn)(即可達(dá)距離最小的樣本點(diǎn))進(jìn)行拓展，并將取出的樣本點(diǎn)保存至L2中，如果它不存在L2當(dāng)中的話：

a)判斷該拓展點(diǎn)是否為核心點(diǎn)，如果不是，則刪除該拓展點(diǎn)；否則找到該拓展點(diǎn)所有的直接密度可達(dá)點(diǎn)。

b)判斷該直接密度可達(dá)樣本點(diǎn)是否已經(jīng)存在L2中，是則不處理；否則下一步。

c)如果有序隊(duì)列中已經(jīng)存在該直接密度可達(dá)點(diǎn)，如果此時(shí)新的可達(dá)距離小于舊的可達(dá)距離，則用新可達(dá)距離取代舊可達(dá)距離，有序隊(duì)列重新排序。

d)如果L1中不存在該直接密度可達(dá)樣本點(diǎn)，則插入該點(diǎn)，并對(duì)L1重新排序。

步驟4 將Laplace噪聲添加到聚類簇中，輸出添加噪聲后的結(jié)果集存儲(chǔ)在L中。

3.2 DP-OPTICS差分隱私保護(hù)算法

基于OPTICS聚類的差分隱私保護(hù)算法能解決輸入敏感性問題，但是在時(shí)間消耗上，卻是大于DP-DBSCAN算法的時(shí)間消耗，而且，處理稀疏型數(shù)據(jù)效果不好，因此本文利用基于密度聚類的OPTICS算法對(duì)參數(shù)輸入不敏感的特性、能夠發(fā)現(xiàn)任意形狀簇的特點(diǎn)及對(duì)離散點(diǎn)數(shù)據(jù)不敏感，適合差分隱私保護(hù)算法對(duì)大數(shù)據(jù)預(yù)處理的優(yōu)點(diǎn)，克服了OPTICS算法將離散點(diǎn)排在隊(duì)列末尾的缺點(diǎn)，采用鄰接表的形式存儲(chǔ)聚類簇，對(duì)離散點(diǎn)采用壓縮處理技術(shù)，考慮用戶查詢的概率、攻擊者攻擊成功的概率及高頻點(diǎn)和離散點(diǎn)的比例添加異方差噪聲確定隱私參數(shù)ε的比例，提出改進(jìn)的基于聚類的差分隱私保護(hù)算法DP-OPTICS。

基于密度聚類的算法來說，兩個(gè)數(shù)據(jù)點(diǎn)的距離越近，則屬于同一簇的概率也就越大。DP-OPTICS差分隱私保護(hù)算法將以此作為假設(shè)背景，在基于OPTICS聚類的差分隱私保護(hù)算法的基礎(chǔ)上，為每個(gè)對(duì)象增加鄰接表refresh存儲(chǔ)最近的相鄰數(shù)據(jù)點(diǎn)，并利用鄰接表中的指針域?qū)⒌皖l點(diǎn)放入到與之相鄰的高頻區(qū)域所在的簇中，如果該對(duì)象附近沒有相鄰的高頻區(qū)域，則將該對(duì)象聚集在相鄰的低頻數(shù)據(jù)點(diǎn)附近。DP-OPTICS差分隱私保護(hù)算法的主要思想是：為每一個(gè)核心對(duì)象創(chuàng)建鄰接表，引入一個(gè)非排序的種子隊(duì)列存儲(chǔ)待擴(kuò)張的點(diǎn)和一個(gè)r指針，r指針用來指向種子隊(duì)列中可達(dá)距離最小的點(diǎn)。當(dāng)種子隊(duì)列中的點(diǎn)為核心對(duì)象時(shí)，將其鄰域點(diǎn)直接更新到種子隊(duì)列中；所有點(diǎn)更新完之后，搜索一次種子隊(duì)列，將r指針指向種子隊(duì)列中可達(dá)距離最小的點(diǎn)。當(dāng)處理種子隊(duì)列中下一個(gè)點(diǎn)時(shí)，只需取出r指針?biāo)赶虻狞c(diǎn)即可。這種方法處理完種子隊(duì)列中的每一個(gè)點(diǎn)后，都會(huì)遍歷一次種子隊(duì)列，找到可達(dá)距離最小的點(diǎn)，搜索一次種子隊(duì)列的時(shí)間復(fù)雜度為O(n),在整體上時(shí)間復(fù)雜度有所降低。對(duì)于低頻數(shù)據(jù)采用壓縮的形式存儲(chǔ)，具體的壓縮方式采取在相同的鄰域半徑內(nèi)，不是核心對(duì)象的點(diǎn)，如果滿足[50%MinPts]個(gè)，則認(rèn)為是一個(gè)簇或者認(rèn)為該點(diǎn)為次核心點(diǎn)，否則就認(rèn)為是離散點(diǎn)，添加較大噪聲。

DP-OPTICS算法具體的流程如下。

算法2 DP-OPTICS差分隱私保護(hù)算法。

輸入：數(shù)據(jù)集D、鄰域半徑E、給定點(diǎn)數(shù)MinPts，噪聲lap(Δf/εi)和lap(Δf/εj)。

輸出：具有添加Laplace噪聲的可達(dá)距離信息的數(shù)據(jù)集。

步驟1 根據(jù)給定的數(shù)據(jù)集D、鄰域半徑E、鄰域半徑E內(nèi)核心對(duì)象最少點(diǎn)的個(gè)數(shù)MinPts，創(chuàng)建種子隊(duì)列L1、結(jié)果隊(duì)列L2、鄰接表refresh，指針r。遍歷數(shù)據(jù)集，搜索每一個(gè)對(duì)象的E鄰域，確定對(duì)象是否為核心對(duì)象，并為該對(duì)象創(chuàng)建鄰接表存儲(chǔ)鄰域點(diǎn)，初始化L1、L2為空隊(duì)列，指針r為空，標(biāo)記數(shù)據(jù)對(duì)象為unprocessed。

步驟2 如果數(shù)據(jù)集D中所有點(diǎn)都已處理完，轉(zhuǎn)至步驟5；否則選擇一個(gè)未處理對(duì)象加入到L1隊(duì)列中，將r指針指向該對(duì)象。

步驟3 若隊(duì)列L1為空，則跳轉(zhuǎn)到步驟2；否則，從L1中取出第一個(gè)樣本點(diǎn)p(即可達(dá)距離最小的樣本點(diǎn))進(jìn)行擴(kuò)張。如果p不是核心點(diǎn)，設(shè)置其可達(dá)距離為Undefined，轉(zhuǎn)至步驟4；否則，對(duì)p的鄰接表內(nèi)任一未處理的鄰近點(diǎn)q作處理：

a)若q已經(jīng)在隊(duì)列L1中，q的可達(dá)距離小于舊值，則更新q的可達(dá)距離；

b)如果q不在L1隊(duì)列中，則把p直接加入到L1隊(duì)列的尾部，并轉(zhuǎn)至步驟4。

步驟4 從L1隊(duì)列中刪除p，并將p及其可達(dá)距離寫入結(jié)果隊(duì)列中。遍歷L1隊(duì)列，制定r指針指向可達(dá)距離最小的對(duì)象并返回步驟3。

步驟5 在結(jié)果隊(duì)列L2總按照陡峭下降和陡峭上升的區(qū)域來提取數(shù)據(jù)集簇，添加lap(Δf/εi)到高頻數(shù)據(jù)簇中，添加lap(Δf/εj)到低頻聚類簇中。

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

3.3.1 實(shí)驗(yàn)環(huán)境

操作系統(tǒng)為Window 7；系統(tǒng)類型為64位操作系統(tǒng)；處理器為AMD Athlon II X4 640 Processor 3.00 GHz;安裝內(nèi)存(RAM)為4.00 GB；集成開發(fā)環(huán)境為Matlab R2012(a)、Weka3.6版本、Eclipse3.7.0；所采用的數(shù)據(jù)集來自Weka3.6版本中data文件夾下credit-g.arff數(shù)據(jù)集，Relation為german_credit；Instances為1 000；Attributes為21。

3.3.2 實(shí)驗(yàn)結(jié)果及分析

credit-g.arff數(shù)據(jù)集主要是關(guān)于德國信貸信息的統(tǒng)計(jì)，其中一共有1 000條記錄，21個(gè)數(shù)據(jù)屬性。數(shù)據(jù)各項(xiàng)屬性具體如表1所示。

從統(tǒng)計(jì)出來的數(shù)據(jù)集來看，其中有關(guān)信用卡(credit)屬性，信用歷史(credit_history)、信用額度(credit_amount)、居住地(resident_since)、財(cái)產(chǎn)大小(property_magnitude)、現(xiàn)有信用卡(existing_credits)、工作(job)、個(gè)人電話(own_telephone)等都屬于敏感信息，是需要保護(hù)的，因?yàn)榭梢愿鶕?jù)信用歷史、工作和財(cái)產(chǎn)大小、信用額等相關(guān)信息推測(cè)出個(gè)人的信用等級(jí)。雖然信用等級(jí)對(duì)于銀行、政府?dāng)?shù)據(jù)庫來說是屬于公共隱私，但是對(duì)于個(gè)人來說還是屬于個(gè)人隱私信息。

表1 credit.arff數(shù)據(jù)集屬性

采用DP-DBSCAN算法、DP-OPTICS差分隱私保護(hù)算法和基于OPTICS差分隱私保護(hù)算法對(duì)credit-g.arff數(shù)據(jù)集1 000條記錄進(jìn)行多次實(shí)驗(yàn)，在鄰域半徑E和鄰域半徑內(nèi)取得最少點(diǎn)數(shù)MinPts分別取值為{(0.1，5)，(1，10)，(5，10)，(10，50)，(0.5，8)，(2，10)，(10，20)，(20，50)}，取經(jīng)過150次實(shí)驗(yàn)的平均值。對(duì)比分析如圖1，DP-OPTICS在E和MinPts取得相對(duì)較小值的時(shí)候，局部聚類緊密性較好，整體上要比基于OPTICS聚類的差分隱私保護(hù)、DP-DBSCAN算法好。

在(E,Minpts,ε)分別取得{(0.1，5，0.1),(1，10，0.3)，(2，15，0.5)，(4，18，1.0)，(6，20，1.2)，(10，20，1.3)，(15，25，1.5)，(20，25，20)}的情況下，對(duì)高頻數(shù)據(jù)和低頻數(shù)據(jù)分別添加同方差Laplace噪聲和異方差Laplace噪聲(高頻數(shù)據(jù)與低頻數(shù)據(jù)仍然按照1∶20的比例添加噪聲)后的相對(duì)誤差，如圖2。很明顯圖2表示了采用同方差方式添加噪聲，聚類高頻數(shù)據(jù)越多，其相對(duì)誤差越大；而采用異方差方式添加噪聲，因?yàn)槠胶饬丝傮w上的噪聲分配，所以整體上的誤差相對(duì)較小，因此添加異方差噪聲方式要比同方差噪聲方式在處理數(shù)據(jù)上更優(yōu)。

圖1 相同E、MinPts、ε下的3種算法聚類結(jié)果對(duì)比

圖2 添加兩種噪聲的DP-OPTICS相對(duì)誤差對(duì)比

在ε取值相同，(E，MinPts)分別取值為{(0.1,5)，(1,10)，(3,13)，(5,15)，(10,15)，(15,20),(20,25)}的情況下，采用DP-OPTICS算法、DP-DBSCAN算法和基于OPTICS聚類的差分隱私保護(hù)算法，經(jīng)過多次實(shí)驗(yàn)取得150次實(shí)驗(yàn)平均值，三者的時(shí)間對(duì)比如圖3。從圖3可以看出，相比DP-DBSCAN算法和基于OPTICS差分隱私保護(hù)算法，DP-OPTICS采用鄰接表形式，在空間復(fù)雜度比兩者的空間復(fù)雜度都小，但是運(yùn)行時(shí)間耗費(fèi)介于DP-DBSCAN算法和基于OPTICS算法之間，因此從整體上來說DP-OPTICS算法還是可行的。

圖3 3種算法的時(shí)間消耗對(duì)比

選擇credit-g.arff數(shù)據(jù)集中credit_history、employment、personal_status等敏感屬性信息用DP-OPTICS算法進(jìn)行處理，同時(shí)選擇與未經(jīng)處理的原始數(shù)據(jù)作對(duì)比分析，在隱私參數(shù)ε=0.42的情況下添加異方差噪聲，再轉(zhuǎn)化為直方圖進(jìn)行隱私敏感信息保護(hù)，最后發(fā)布數(shù)據(jù)。具體如圖4：橫坐標(biāo)是按照等寬直方圖的方式劃分距離，Raw data代表原始數(shù)據(jù)集，Privatized代表DP-OPTICS算法處理后的隱私數(shù)據(jù)。從圖4中可以看出添加隨機(jī)噪聲后的數(shù)據(jù)始終在原始數(shù)據(jù)集的周圍上下浮動(dòng)，但仍然保持著原始數(shù)據(jù)集的整體分布屬性。在ε=0.42的基礎(chǔ)上，如果增大隱私參數(shù)ε的取值則隱私泄露的風(fēng)險(xiǎn)將增加；如果降低ε的取值則數(shù)據(jù)可用性將會(huì)降低，因此，對(duì)本文credit-g.arff數(shù)據(jù)集來說，ε=0.42有效地平衡了數(shù)據(jù)可用性和隱私保護(hù)性之間的分配，總體上效果較好。

圖4 原始數(shù)據(jù)與經(jīng)過DP-OPTICS算法處理后的隱私保護(hù)數(shù)據(jù)對(duì)比

4 結(jié)語

本文在DP-DBSCAN差分隱私保護(hù)算法、基于OPTICS聚類的差分隱私保護(hù)算法基礎(chǔ)上，解決了基于OPTICS聚類的差分隱私保護(hù)存在的時(shí)間復(fù)雜度大和數(shù)據(jù)可用性低的問題，平衡了隱私保護(hù)和數(shù)據(jù)可用性之間的分配。提出的DP-OPTICS差分隱私保護(hù)算法，較好地提高了數(shù)據(jù)可用性。DP-OPTICS算法相對(duì)于DP-DBSCAN算法和基于OPTICS聚類的差分隱私保護(hù)算法來說，對(duì)數(shù)據(jù)集的聚類效果較好，時(shí)間消耗介于兩者之間。DP-OPTICS算法對(duì)于稀疏型的數(shù)據(jù)集采用壓縮方式和盡可能地歸于高頻數(shù)據(jù)范圍內(nèi)，考慮到用戶查詢數(shù)據(jù)的概率以及攻擊者能夠成功攻擊數(shù)據(jù)集記錄的概率，確定最大隱私參數(shù)，對(duì)高頻數(shù)據(jù)和低頻數(shù)據(jù)以異方差形式添加隨機(jī)噪聲，提高了數(shù)據(jù)的可用性，有效平衡了隱私參數(shù)的分配，整體上是較有優(yōu)勢(shì)的，但是在確定異方差噪聲隱私參數(shù)比例的時(shí)候，需要對(duì)用戶的查詢概率有較為準(zhǔn)確的估計(jì)及在假設(shè)最大背景下用戶成功攻擊的概率范圍，這也將會(huì)影響隱私參數(shù)最大值的確定。DP-OPTICS算法的時(shí)間耗費(fèi)也需要進(jìn)一步的降低以提高整體效率。

目前，差分隱私保護(hù)的應(yīng)用主要有PINQ框架[22]、Airavat框架[23]、Rappor框架[24]，而具體的應(yīng)用較少，重點(diǎn)在推薦系統(tǒng)[25]和社交網(wǎng)絡(luò)[26]上，下一步將所改進(jìn)的DP-OPTICS算法應(yīng)用于推薦系統(tǒng)中，進(jìn)一步完善應(yīng)用。

References)

[1] DWORK C. Differential privacy [C]// ICALP 2006: Proceedings of the 2006 International Colloquium on Automata, Languages, and Programming. Berlin: Springer, 2006: 1-12.

[2] 吳偉民,黃煥坤.基于差分隱私保護(hù)的DP-DBScan聚類算法研究[J].計(jì)算機(jī)工程與科學(xué),2015,37(4):830-834.(WU W M, HUANG H K. Study on DP-DBSCAN clustering algorithm based on differential privacy protection [J]. Computer Engineering and Science, 2015, 37 (4): 830-834.)

[3] NG R T, HAN J. Efficient and effective clustering methods for spatial data mining [C]// Proceedings of the 1994 International Conference on Very Large Data Bases. San Francisco: Morgan Kaufmann, 1994: 144-155.

[4] ANKERST M, BREUNIG M M, KRIEGEL H P, et al. OPTICS: ordering points to identify the clustering structure [J]. ACM SIGMOD Record, 1999, 28(2): 49-60.

[5] BLUM A, DWORK C, MCSHERRY F, et al. Practical privacy: the SuLQ framework [C]// Proceedings of the Twenty-Fourth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems. New York: ACM, 2005: 128-138.

[6] NISSIM K, RASKHODNIKOVA S, SMITH A. Smooth sensitivity and sampling in private data analysis [C]// Proceedings of the Thirty-Ninth Annual ACM Symposium on Theory of Computing. New York: ACM, 2007: 75-84.

[7] DWORK C. A firm foundation for private data analysis [J]. Communications of the ACM, 2011, 54(1): 86-95.

[8] 李楊,郝志峰,溫雯,等.差分隱私保護(hù)k-means聚類方法研究[J].計(jì)算機(jī)科學(xué),2013,40(3):287-290.(LI Y, HAO Z F, WEN W, et al. Study on clustering method of differential privacy protectionk-means [J]. Computer Science, 2013, 40 (3): 287-290.)

[9] DWORK C, MCSHERRY F, NISSIM K. Calibrating noise to sensitivity in private data analysis [J]. Proceedings of the VLDB Endowment, 2012, 7(8): 637-648.

[10] MCSHERRY F, TALWAR K. Mechanism design via differential privacy [C]// FOCS ’07: Proceedings of the 2007 IEEE Symposium on Foundations of Computer Science. Piscataway, NJ: IEEE, 2007: 94-103.

[11] HAY M, RASTOGI V, MIKLAU G, et al. Boosting the accuracy of differentially private histograms through consistency [J]. Proceedings of the 36th VLDB Endowment, 2010, 3(1/2): 1021-1032.

[12] PENG S, YANG Y, ZHANG Z, et al. DP-tree: indexing multi-dimensional data under differential privacy (abstract only) [C]// SIGMOD ’12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2012: 864.

[13] MCSHERRY F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [J]. Communications of the ACM, 2010, 53(9): 89-97.

[14] 何賢芒,王曉陽,陳華輝,等.差分隱私保護(hù)參數(shù)ε的選取研究[J].通信學(xué)報(bào),2015,36(12):124-130.(HE X M, WANG X Y, CHEN H H, et al. Study on the selection of differential privacy parametersε[J]. Journal on Communications, 2015, 36(12): 124-130.)

[15] LEE J, CLIFTON C. How much is enough? choosingεfor differential privacy [C]// ISC 2011: Proceedings of the 2011 International Conference on Information Security. Berlin: Springer, 2011: 325-340.

[16] HARDT M, TALWAR K. On the geometry of differential privacy [C]// Proceedings of the 2010 ACM Symposium on Theory of Computing. New York: ACM, 2010: 705-714.

[17] XIAO X, BENDER G, HAY M, et al. iReduct: differential privacy with reduced relative errors [C]// SIGMOD 2011: Proceedings of the 2011 ACM SIGMOD International Conference on Management of Data. New York: ACM, 2011: 229-240.

[18] LI Y, ZHANG Z, WINSLETT M, et al. Compressive mechanism: utilizing sparse representation in differential privacy [C]// Proceedings of the 10th Annual ACM Workshop on Privacy in the Electronic Society. New York: ACM, 2011: 177-182.

[19] XIAO X, WANG G, GEHRKE J. Differential privacy via wavelet transforms [C]// Proceedings of the 2010 IEEE 26th International Conference on Data Engineering. Piscataway, NJ: IEEE, 2010: 225-236.

[20] CHEN R, ACS G, CASTELLUCCIA C. Differentially private sequential data publication via variable-lengthn-grams [C]// Proceedings of the 2012 ACM Conference on Computer and Communications Security. New York: ACM, 2012: 638-649.

[21] 曾依靈,許洪波,白碩.改進(jìn)的OPTICS算法及其在文本聚類中的應(yīng)用[J].中文信息學(xué)報(bào),2008,22(1):51-55.(ZENG Y L, XU H B, BAI S. Improved OPTICS algorithm and its application in text clustering [J]. Journal of Chinese Information Processing, 2008, 22(1): 51-55.)

[22] MCSHERRY F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis [J]. Communications of the ACM, 2010, 53(9): 89-97.

[23] ROY I, SETTY S T V, KILZER A, et al. Airavat: security and privacy for MapReduce [C]// NSDI 2010: Proceedings of the 2010 USENIX Symposium on Networked Systems Design and Implementation. Berkeley, CA: USENIX Association, 2010: 297-312.

[24] ERLINGSSON U, PIHUR V, KOROLOVA A. RAPPOR: randomized aggregatable privacy-preserving ordinal response [C]// Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security. New York: ACM, 2014: 1054-1067.

[25] 程呈.基于差分隱私的興趣點(diǎn)推薦系統(tǒng)的設(shè)計(jì)與分析[D].成都：電子科技大學(xué),2015.(CHENG C. Design and analysis of point of interest recommendation system based on differential privacy [D]. Chengdu: University of Electronic Science and Technology of China, 2015.)

[26] 王越.基于差分隱私的社交網(wǎng)絡(luò)隱私保護(hù)方法研究[D]. 哈爾濱:哈爾濱工業(yè)大學(xué),2016.(WANG Y. Study on privacy protection method of social network based on differential privacy [D]. Harbin: Harbin Institute of Technology, 2016.)

This work is partially supported by the National Natural Science Foundation of China (61462009), the Scientific Research Foundation of Guangxi University for Nationalities (2014MDYB029), the China-ASEAN Research Center of Guangxi University for Nationalities (Guangxi Science Experimental Center) 2014 Open Project (TD201404), the Graduate Research and Innovation Project of Guangxi University for Nationalities (gxun-chxps201671).

WANGHong, born in 1990, M. S. Her research interests include information security.

GELina, born in 1969, Ph. D., professor. Her research interests include information security.

WANGSuqing, born in 1980. Her research interests include network security.

WANGLiying, born in 1991, M. S. Her research interests include information security.

ZHANGYipeng, born in 1991, M. S. His research interests include information security.

LIANGJuncheng, born in 1982. His research interests include information security.