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

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

0 引言

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

對吳偉民等[2]提出的DP-DBSCAN(Differential Privacy-Density-Based Spatial Clustering of Applications with Noise)差分隱私保護(hù)算法分析，針對DBSCAN(Density-Based Spatial Clustering of Applications with Noise)[3]算法對參數(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ù)模型，主要是針對個人敏感信息泄露進(jìn)行隱私保護(hù)的一項技術(shù)，根據(jù)添加噪聲順序不同分為兩種方式：1)對原始數(shù)據(jù)直接添加噪聲機制，然后發(fā)布數(shù)據(jù)。這種方法的隱私保護(hù)性比較高，但是數(shù)據(jù)可用性較低。2)先對原始數(shù)據(jù)進(jìn)行轉(zhuǎn)換、壓縮、隨機擾動等技術(shù)預(yù)處理，再對數(shù)據(jù)添加隨機噪聲，最后發(fā)布數(shù)據(jù)。這種方法信息有所缺損，但在減少發(fā)布誤差和提高數(shù)據(jù)可用性上有很大幫助。按照處理方式的不同主要有聚類變換、分類變換、層次樹變換、傅里葉變換等技術(shù)，其中聚類技術(shù)在這幾項預(yù)處理技術(shù)中關(guān)于數(shù)據(jù)發(fā)布的精度和時間復(fù)雜度整體對比上是比較優(yōu)良的。

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

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

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

定義1ε-差分隱私[1]。對于數(shù)據(jù)集D1和D2，至多存在一條不同的記錄(稱D1和D2為兄弟數(shù)據(jù)集)，Range(K)為隨機算法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)險越低；反之，隱私泄露風(fēng)險越高。

2)敏感度。

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

(2)

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

3)噪聲機制。

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

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

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

(3)

4)添加噪聲的方式。

定義4 同/異方差加噪方式[11-12]。在不考慮用戶查詢興趣點分布不均勻的情況下，認(rèn)為隨機查詢的每個數(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機制分布給函數(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的情況下，攻擊者對于結(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)算法性能。通?？紤]時間復(fù)雜度和漸進(jìn)噪聲誤差邊界作為性能的評價標(biāo)準(zhǔn)。

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

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

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

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

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

定義5 對象的E鄰域。給定對象半徑E內(nèi)的鄰域為該對象的E鄰域。

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

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

定義8 基于密度的簇?；诿芏瓤蛇_(dá)性的最大的密度相連對象的集合。不屬于任何聚類中的數(shù)據(jù)或離散點被認(rèn)為是低頻對象。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.3 實驗結(jié)果分析

3.3.1 實驗環(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 實驗結(jié)果及分析

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

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

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

采用DP-DBSCAN算法、DP-OPTICS差分隱私保護(hù)算法和基于OPTICS差分隱私保護(hù)算法對credit-g.arff數(shù)據(jù)集1 000條記錄進(jìn)行多次實驗，在鄰域半徑E和鄰域半徑內(nèi)取得最少點數(shù)MinPts分別取值為{(0.1，5)，(1，10)，(5，10)，(10，50)，(0.5，8)，(2，10)，(10，20)，(20，50)}，取經(jīng)過150次實驗的平均值。對比分析如圖1，DP-OPTICS在E和MinPts取得相對較小值的時候，局部聚類緊密性較好，整體上要比基于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)}的情況下，對高頻數(shù)據(jù)和低頻數(shù)據(jù)分別添加同方差Laplace噪聲和異方差Laplace噪聲(高頻數(shù)據(jù)與低頻數(shù)據(jù)仍然按照1∶20的比例添加噪聲)后的相對誤差，如圖2。很明顯圖2表示了采用同方差方式添加噪聲，聚類高頻數(shù)據(jù)越多，其相對誤差越大；而采用異方差方式添加噪聲，因為平衡了總體上的噪聲分配，所以整體上的誤差相對較小，因此添加異方差噪聲方式要比同方差噪聲方式在處理數(shù)據(jù)上更優(yōu)。

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

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

在ε取值相同，(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)過多次實驗取得150次實驗平均值，三者的時間對比如圖3。從圖3可以看出，相比DP-DBSCAN算法和基于OPTICS差分隱私保護(hù)算法，DP-OPTICS采用鄰接表形式，在空間復(fù)雜度比兩者的空間復(fù)雜度都小，但是運行時間耗費介于DP-DBSCAN算法和基于OPTICS算法之間，因此從整體上來說DP-OPTICS算法還是可行的。

圖3 3種算法的時間消耗對比

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

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

4 結(jié)語

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

目前，差分隱私保護(hù)的應(yīng)用主要有PINQ框架[22]、Airavat框架[23]、Rappor框架[24]，而具體的應(yīng)用較少，重點在推薦系統(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].計算機工程與科學(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].計算機科學(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é)報,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é)報,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] 程呈.基于差分隱私的興趣點推薦系統(tǒng)的設(shè)計與分析[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.