基于OPTICS聚類的差分隱私保護算法的改進

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

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

0 引言

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

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

1 差分隱私研究現狀

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

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

2 差分隱私保護相關知識

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

定義1ε-差分隱私[1]。對于數據集D1和D2，至多存在一條不同的記錄(稱D1和D2為兄弟數據集)，Range(K)為隨機算法K的取值范圍，如果算法K在數據集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的概率，ε是差分隱私參數，用來表示隱私保護程度，ε越小表示隱私保護程度越高、隱私泄露風險越低；反之，隱私泄露風險越高。

2)敏感度。

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

(2)

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

3)噪聲機制。

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

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

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

(3)

4)添加噪聲的方式。

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

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

6)隱私參數ε的選取。

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

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

(4)

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

定理2 設位置參數μ=0,L=0.5的情況下，攻擊者對于結果數據集查詢成功的概率是：

(5)

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

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

(6)

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

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

a)算法性能。通常考慮時間復雜度和漸進噪聲誤差邊界作為性能的評價標準。

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

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

3 基于OPTICS聚類的差分隱私保護改進算法

3.1 基于OPTICS聚類的差分隱私保護

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

定義5 對象的E鄰域。給定對象半徑E內的鄰域為該對象的E鄰域。

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

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

定義8 基于密度的簇。基于密度可達性的最大的密度相連對象的集合。不屬于任何聚類中的數據或離散點被認為是低頻對象。

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

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

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

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

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

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

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

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

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

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

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

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

3.2 DP-OPTICS差分隱私保護算法

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

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

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

算法2 DP-OPTICS差分隱私保護算法。

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

輸出：具有添加Laplace噪聲的可達距離信息的數據集。

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

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

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

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

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

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

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

3.3 實驗結果分析

3.3.1 實驗環境

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

3.3.2 實驗結果及分析

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

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

表1 credit.arff數據集屬性

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

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

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

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

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

圖4 原始數據與經過DP-OPTICS算法處理后的隱私保護數據對比

4 結語

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

目前，差分隱私保護的應用主要有PINQ框架[22]、Airavat框架[23]、Rappor框架[24]，而具體的應用較少，重點在推薦系統[25]和社交網絡[26]上，下一步將所改進的DP-OPTICS算法應用于推薦系統中，進一步完善應用。

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] 吳偉民,黃煥坤.基于差分隱私保護的DP-DBScan聚類算法研究[J].計算機工程與科學,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] 李楊,郝志峰,溫雯,等.差分隱私保護k-means聚類方法研究[J].計算機科學,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] 何賢芒,王曉陽,陳華輝,等.差分隱私保護參數ε的選取研究[J].通信學報,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] 曾依靈,許洪波,白碩.改進的OPTICS算法及其在文本聚類中的應用[J].中文信息學報,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] 程呈.基于差分隱私的興趣點推薦系統的設計與分析[D].成都：電子科技大學,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] 王越.基于差分隱私的社交網絡隱私保護方法研究[D]. 哈爾濱:哈爾濱工業大學,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.