基于本地差分隱私的空間數(shù)據(jù)自適應(yīng)劃分算法

金媛媛，倪志偉，朱旭輝，陳恒恒，陳 千

（1.合肥工業(yè)大學(xué) 管理學(xué)院，合肥 230009；2.合肥工業(yè)大學(xué) 過程優(yōu)化與智能決策教育部重點實驗室，合肥 230009）

0 概述

隨著信息技術(shù)的快速發(fā)展，移動互聯(lián)、社交網(wǎng)絡(luò)、電子商務(wù)等熱門應(yīng)用收集了大量用戶數(shù)據(jù)，這些數(shù)據(jù)常被用于研究人類行為、改善交通檢測、進行位置感知推薦等方面，給人們的日常生活帶來極大便利。然而，在大數(shù)據(jù)時代，數(shù)據(jù)挖掘和分析技術(shù)快速發(fā)展，用戶的隱私數(shù)據(jù)很容易遭受攻擊和泄露，用戶的位置信息泄露會對個人隱私造成嚴重影響，因此，確保用戶的位置隱私安全在數(shù)據(jù)統(tǒng)計分析中尤為重要。幾乎所有的數(shù)據(jù)統(tǒng)計分析任務(wù)都依賴于對數(shù)據(jù)分布的理解，例如，在空間眾包［1］中，根據(jù)一定區(qū)域內(nèi)的工人數(shù)量進行任務(wù)分配［2］，通過記錄用戶位置［3］呈現(xiàn)人群密度圖，許多基于位置的應(yīng)用程序利用用戶的區(qū)域計數(shù)來優(yōu)化實際問題。因此，在收集和發(fā)布用戶位置數(shù)據(jù)時，如何有效地平衡數(shù)據(jù)隱私和數(shù)據(jù)可用性之間的關(guān)系成為目前亟待解決的難題［4］。

DWΟRK［5］提出一種差分隱私模型，為敵手在任意背景知識下的攻擊提供有力保護，其為一種強健的隱私保護模型。傳統(tǒng)的中心化差分隱私模型需要可信第三方數(shù)據(jù)收集中心來收集用戶的原始數(shù)據(jù)，用戶無法掌控自己的數(shù)據(jù)隱私，提高了個人隱私泄露風險，且互聯(lián)網(wǎng)時代大眾的隱私意識日益增強，用戶可能不愿意與數(shù)據(jù)收集者共享私人數(shù)據(jù)，從而限制了差分隱私的應(yīng)用。而本地差分隱私模型將數(shù)據(jù)隱私化的工作轉(zhuǎn)移給每個用戶，用戶的信息經(jīng)過自身設(shè)備的隱私處理后分享給其他人，避免在收集用戶信息過程中第三方數(shù)據(jù)收集中心竊取或泄露用戶隱私。谷歌、蘋果、微軟等公司已經(jīng)基于本地差分隱私模型，在大規(guī)模數(shù)據(jù)域內(nèi)對用戶的私人數(shù)據(jù)進行了頻率估計。

與中心化差分隱私模型相比，本地差分隱私模型具有強大的隱私保護性能，同時也會造成更大的誤差。本地差分隱私下的非均勻空間數(shù)據(jù)發(fā)布存在如下挑戰(zhàn)：在本地化設(shè)置中，數(shù)據(jù)收集者無法收集到用戶的真實位置數(shù)據(jù)，傳統(tǒng)方法將整個待發(fā)布位置區(qū)域均勻劃分，而大規(guī)模位置空間劃分值域通常較大，導(dǎo)致通信代價較高；對于非均勻空間位置數(shù)據(jù)，均勻劃分方法導(dǎo)致數(shù)據(jù)采集誤差較大，合適的數(shù)據(jù)空間劃分方法能夠有效提高發(fā)布數(shù)據(jù)查詢結(jié)果的精度，在本地化差分隱私場景下，需要設(shè)計高效精確的自適應(yīng)劃分方法；在本地化設(shè)置中，差分隱私預(yù)算分割將產(chǎn)生極大的噪聲誤差，需要減少隱私預(yù)算分割，降低在本地差分隱私模型下采集數(shù)據(jù)的誤差。

本文研究本地差分隱私模型下空間數(shù)據(jù)的采集和發(fā)布問題，提出一種空間數(shù)據(jù)分層自適應(yīng)劃分方法。分維度統(tǒng)計少量用戶的擾動位置信息并結(jié)合KD-樹劃分思想初步劃分位置空間，然后劃分多層數(shù)據(jù)空間，在此過程中采用抽樣技術(shù)對用戶進行分組，利用分組用戶統(tǒng)計結(jié)果所提供的先驗知識，采取不同的劃分粒度來對不同分布密度的數(shù)據(jù)空間進行高質(zhì)量的空間劃分。具體地，本文提出一種自適應(yīng)樹劃分方法對位置空間進行多層劃分，該方法以用戶在不同節(jié)點的統(tǒng)計數(shù)為先驗知識，通過閾值判斷分割策略、重構(gòu)樹結(jié)構(gòu)解決空間劃分值域較大的問題。在本地化差分隱私條件下，分維度統(tǒng)計用戶的擾動位置信息，利用少量用戶的位置擾動信息估計空間區(qū)域密集程度，并結(jié)合KD-樹劃分思想初步劃分位置空間，以降低位置空間劃分值域和數(shù)據(jù)采集誤差。針對本地差分隱私模型下由隱私預(yù)算分割造成的數(shù)據(jù)可用性低的問題，提出一種基于用戶集合采樣的層次劃分方法，將用戶隨機分為多個不相交的子集，以有效解決隱私預(yù)算分配次數(shù)過多的問題并降低差分隱私噪聲。

1 相關(guān)工作

隱私數(shù)據(jù)發(fā)布面臨的主要挑戰(zhàn)是如何設(shè)計一種差分隱私機制，在保護用戶隱私的同時提高查詢結(jié)果的準確性。位置空間數(shù)據(jù)［6］是一組有序的數(shù)值，在差分隱私模型下處理位置空間數(shù)據(jù)需要將一個范圍的值作為一個分類值，而分類粒度既取決于隱私參數(shù)，又取決于數(shù)據(jù)的分布，在這種方式下選擇合適的分類粒度對于發(fā)布數(shù)據(jù)的精確度具有很大影響。在中心化差分隱私中，已經(jīng)有很多國內(nèi)外學(xué)者對隱私空間的劃分做了突破性研究。

CΟRMΟDE 等［7］提出隱 私空間劃分（Private Spatial Decomposition，PSD）的概念，其基本思想是：基于空間索引結(jié)構(gòu)將數(shù)據(jù)區(qū)域劃分為互不相交的區(qū)塊，其中，每個節(jié)點表示劃分的區(qū)塊范圍，然后發(fā)布每個節(jié)點中的計數(shù)或頻率。QARDAJI 等［8］提出基于網(wǎng)格的分區(qū)策略，該策略將數(shù)據(jù)區(qū)域均勻地劃分為等寬的單元格，為每個單元格計數(shù)添加拉普拉斯噪聲，這種劃分沒有考慮空間數(shù)據(jù)具體的分布情況。針對空間數(shù)據(jù)分布的不均勻性，文獻［8］提出一種空間數(shù)據(jù)的自適應(yīng)劃分策略，其基本思想是：在稀疏區(qū)域進行粗粒度劃分，在稠密區(qū)域進行細粒度劃分，然后根據(jù)2 種粒度的劃分區(qū)塊計數(shù)，響應(yīng)范圍查詢計數(shù)。文獻［9］根據(jù)完全四分樹結(jié)構(gòu)劃分數(shù)據(jù)域，發(fā)布各層節(jié)點的信息和噪聲計數(shù)來響應(yīng)范圍查詢，但在偏斜的數(shù)據(jù)集中，其劃分的節(jié)點不平衡，這對于查詢回答而言效果并不理想。

劃分數(shù)據(jù)區(qū)域通常分為數(shù)據(jù)獨立和數(shù)據(jù)依賴2 類方法，均勻網(wǎng)格劃分和完全四分樹劃分方法屬于數(shù)據(jù)獨立的方法，劃分區(qū)域不依賴于數(shù)據(jù)點的數(shù)量或分布，而在實際數(shù)據(jù)集應(yīng)用中，數(shù)據(jù)可用性和效率并不理想，因此，學(xué)者們開始對數(shù)據(jù)依賴的劃分方法進行研究。INAN 等［10］提出基于KD-樹的數(shù)據(jù)依賴結(jié)構(gòu)劃分數(shù)據(jù)空間，但其需要利用指數(shù)機制［11］保護每一層次的分割線，劃分層次較高時隱私預(yù)算耗費很大。文獻［12］提出一種基于稀疏向量技術(shù)的KD-樹空間分割方法，該方法通過稀疏向量技術(shù)判斷是否分割樹節(jié)點，從而控制節(jié)點的噪音值。上述研究都是在有可信第三方數(shù)據(jù)收集中心的前提下，采用拉普拉斯機制對計數(shù)值進行擾動，無法在本地差分隱私模型中直接應(yīng)用。

本地差分隱私常被用于解決統(tǒng)計分析任務(wù)中用戶的隱私問題。Google［13］提出的RAPPΟR 方法利用Bloom Filter 技術(shù)和隨機響應(yīng)技術(shù)擾動數(shù)據(jù)，其為頻數(shù)估計中的經(jīng)典算法，已經(jīng)被谷歌Chrome 用于收集用戶的使用數(shù)據(jù)，但其通信代價較大。KAIRΟUZ等［14］提出的o-rappor 方法應(yīng)用哈希映射和分組技術(shù)，針對屬性域沒有先驗知識的情況對用戶隱私數(shù)據(jù)進行頻數(shù)統(tǒng)計。BASSILY 等［15］提出的S-Hist 方法針對分類型數(shù)據(jù)，使用柱狀圖列出數(shù)據(jù)中最頻繁出現(xiàn)的項目及其頻率估計數(shù)，這種方法基于隨機矩陣投影技術(shù)從編碼向量中隨機選取一個比特，有效降低了通信代價。文獻［16］利用隨機響應(yīng)方法解決分組無關(guān)問題模型存在的隱私泄露問題。文獻［17］提出一種數(shù)值域離散化的方法，用于解決本地差分隱私下數(shù)據(jù)域密度估計問題，表明利用域的數(shù)值特性有利于平衡數(shù)據(jù)的實用性和隱私性。文獻［18］提出本地差分隱私模型下的多維數(shù)據(jù)分類機制，其對數(shù)據(jù)的不同維度分別設(shè)置隱私預(yù)算，但是無法保證數(shù)據(jù)的可用性。

上述本地差分隱私模型下的頻率估計方法多用于一維數(shù)據(jù)，目前對于二維空間數(shù)據(jù)的發(fā)布還存在不足。文獻［19］提出一種室內(nèi)定點采集人口統(tǒng)計數(shù)據(jù)的方法，用于估計室內(nèi)區(qū)域的密度，但其應(yīng)用范圍較窄，且對于分布不均的數(shù)據(jù)集誤差較大，難以適用于大規(guī)模區(qū)域數(shù)據(jù)的采集和發(fā)布。張嘯劍等［20］提出一種空間范圍查詢方法，首先采用四分樹索引均勻劃分網(wǎng)格，數(shù)據(jù)擾動過程采用層次隨機抽樣的方法，該方法能夠有效降低通信代價，但無法根據(jù)數(shù)據(jù)集的分布自適應(yīng)地劃分區(qū)域。文獻［5］基于隨機映射矩陣提出PCE 方法，用戶可以根據(jù)自身需求進行個性化隱私設(shè)置，并統(tǒng)計不同區(qū)域中的用戶數(shù)。霍崢等［21］提出一種位置數(shù)據(jù)眾包采集方法，其通過構(gòu)造維諾圖對路網(wǎng)空間進行分割，但該方法仍然是與數(shù)據(jù)分布無關(guān)的劃分方法，空間范圍查詢精確性較低。

綜上，在中心化差分隱私中通常根據(jù)真實數(shù)據(jù)集的分布情況來自適應(yīng)劃分數(shù)據(jù)空間，然而，在本地差分隱私場景下無法獲得真實數(shù)據(jù)，因此，中心化差分隱私中的劃分方式不能直接應(yīng)用于本地差分隱私。目前，基于本地差分隱私的二維空間數(shù)據(jù)發(fā)布方法主要是在數(shù)據(jù)域上設(shè)置等寬的網(wǎng)格［19］，或者在數(shù)據(jù)域上構(gòu)造層次均勻的分區(qū)結(jié)構(gòu)［20］，這些方法無法針對偏斜和非均勻數(shù)據(jù)集進行劃分，導(dǎo)致稀疏區(qū)域產(chǎn)生大量空節(jié)點，大幅增加了噪聲誤差，而稠密區(qū)域劃分不充分，容易產(chǎn)生較大的均勻假設(shè)誤差。為了解決上述問題，本文提出一種基于本地差分隱私的空間數(shù)據(jù)分層自適應(yīng)劃分算法KDG-HT，目的是使數(shù)據(jù)收集者能夠估計輸入數(shù)據(jù)的分布情況，從而確定合適的劃分粒度。

2 相關(guān)定義與問題描述

2.1 本地差分隱私

傳統(tǒng)的差分隱私技術(shù)假設(shè)存在一個受信任的數(shù)據(jù)收集者，負責收集用戶的私人信息，并通過擾動算法發(fā)布信息。然而在實際中，很難找到讓用戶信任并愿意共享私人信息的數(shù)據(jù)收集中心，本地差分隱私不假設(shè)用戶彼此之間存在任何信任，用戶彼此間不通信，每個用戶通過一個擾動算法獨立發(fā)布自己的信息。

定義1（本地差分隱私［13］）給定隨機算法A及其輸出域Ο，對于用戶端的所有數(shù)據(jù)對νi和νj，隨機算法A滿足本地差分隱私當且僅當：

其中：ε為隱私預(yù)算，ε值越小，算法對用戶的隱私保護程度越高。式（1）表明，通過觀測算法的輸出無法判斷輸入值是νi還是νj。

隨機響應(yīng)技術(shù)［22］是實現(xiàn)LDP 的經(jīng)典方法，它的主要思想是通過對敏感問題響應(yīng)的不確定性來保護用戶的隱私信息，即用戶以p的概率翻轉(zhuǎn)它來給出真實答案，以1-p的概率給出其他答案，用戶不再需要信任任何中間數(shù)據(jù)收集者。例如，數(shù)據(jù)收集器要計算N個用戶中吸煙者的比例，于是對N個用戶提出問題：“你吸煙嗎？”用戶的回答有“是”和“否”2 種，為了保護隱私，每個用戶投擲一枚非均勻硬幣，出現(xiàn)正面的概率是p，出現(xiàn)反面的概率是1-p，用戶拋出硬幣，若出現(xiàn)正面，則回答真實答案，否則，回答相反的答案。

定理1（序列組合性［23］）給定數(shù)據(jù)集D和n個隨機算法{A1,A2,…,An}，將滿足εi-差分隱私的多個算法Ai進行序列組合，從而滿足ε-差分隱私，其中，ε=

定理2（并行組合性［23］）將給定的數(shù)據(jù)集D劃分為若干不相交的子集{D1,D2,…,Dn}，A為滿足ε-差分隱私的任一隨機算法，則算法A在{D1,D2,…,Dn}上的系列操作滿足ε-差分隱私。

本地差分隱私與中心化差分隱私都具有序列組合性和并行組合性［23］。定理1 序列組合性表明有一個算法序列同時作用在一個數(shù)據(jù)集上時，最終的差分隱私預(yù)算等于算法序列中所有算法的預(yù)算之和［24］，AG 方法以及大多數(shù)樹結(jié)構(gòu)等中心化差分隱私保護方法都應(yīng)用了這一性質(zhì)。并行組合性表明，在數(shù)據(jù)集的不相交子集上應(yīng)用滿足ε-差分隱私的算法，最終的差分隱私預(yù)算仍然為ε，本文正是利用這一性質(zhì)對空間數(shù)據(jù)實現(xiàn)本地差分隱私保護。

2.2 KD-樹空間分割

KD-樹是在K維空間中對數(shù)據(jù)集進行分割的一種二叉樹結(jié)構(gòu)，通過指定劃分維度di和劃分值ν來確定一個K-1 維的超平面，將多維空間劃分為di值小于ν和di值大于ν的子空間。在KD-樹的不同層，依次選擇K個維度中的一個，本文利用KD-樹將二維空間數(shù)據(jù)劃分為稀疏區(qū)域和密集區(qū)域，根據(jù)每個維度的區(qū)間密度確定劃分維度和劃分值。假設(shè)X軸區(qū)間密度分布Y軸區(qū)間密度分布0.3｝，稀疏區(qū)間包括{x1,x3,y1}。基于傳統(tǒng)網(wǎng)格劃分方法UG 與基于KD-樹劃分的空間平面圖如圖1 所示，在采用KD-樹進行劃分時，避免了稀疏區(qū)域被過度劃分，在大規(guī)模數(shù)據(jù)空間劃分應(yīng)用中能夠有效降低值域。

圖1 空間分割效果對比Fig.1 Comparison of spatial segmentation effects

3 基于用戶分割的空間自適應(yīng)劃分算法

3.1 設(shè)計思想

本文在本地差分隱私模型的基礎(chǔ)上，提出空間數(shù)據(jù)分層自適應(yīng)劃分方法KDG-HT，以對空間進行細粒度的劃分，KDG-HT 方法流程如圖2 所示。首先，對位置空間進行粗粒度劃分，基于本地差分隱私模型收集抽樣數(shù)據(jù)，改進值域劃分方式，利用位置數(shù)據(jù)分別從不同維度估計區(qū)域的用戶位置分布情況，結(jié)合KD-樹劃分思想對區(qū)域進行粗粒度劃分；然后，利用隨機采樣技術(shù)對用戶分組，使其滿足差分隱私的并行組合性，避免隱私預(yù)算分割造成過大的噪聲誤差；最后，在粗粒度空間劃分的基礎(chǔ)上，根據(jù)分組用戶統(tǒng)計結(jié)果所提供的先驗知識估計用戶分布情況，對位置空間進行細粒度劃分，得到滿足本地差分隱私的空間數(shù)據(jù)統(tǒng)計結(jié)果。

圖2 KDG-HT 數(shù)據(jù)發(fā)布方法流程Fig.2 Procedure of KDG-HT data publishing method

中心化差分隱私模型下的空間數(shù)據(jù)發(fā)布通常采用隱私預(yù)算分割策略，例如，在基于樹的空間索引技術(shù)中，依據(jù)定理1 將隱私預(yù)算分別分配給空間索引的不同層次，實現(xiàn)差分隱私保護。然而本地差分隱私使用的隨機應(yīng)答機制對于隱私預(yù)算較為敏感，隱私預(yù)算分配到每個劃分層次后所造成的噪聲誤差極大，因此，隱私預(yù)算分割策略在本地差分隱私中不適用。

由于用戶隨機分組不影響隱私性，因此本文依據(jù)定理2 提出一種用戶分割策略，將用戶集合分為K組從而保持隱私預(yù)算不變。在用戶分割策略中，存在2 個方面的噪聲影響：

1）由于子數(shù)據(jù)集分布與總體分布可能不同，使得數(shù)據(jù)集劃分引入抽樣誤差。

2）每個劃分層次的用戶總計數(shù)減少，會放大噪聲的影響。

由于抽樣誤差相比隱私預(yù)算分割所造成的噪聲誤差幾乎可以忽略不計［17］，同時可以通過KDG 算法降低劃分層次，控制由用戶總計數(shù)減少所造成的噪聲影響，因此本文算法采用的用戶分割策略能夠有效降低誤差。

3.2 算法實現(xiàn)

3.2.1 基于密度的KD-樹自適應(yīng)劃分算法KDG

KDG 算法描述如算法1 所示。

算法1KDG 算法

KDG 算法改進了值域劃分方式，將區(qū)域分為m+n個區(qū)間，相比于傳統(tǒng)的均勻網(wǎng)格將區(qū)域分為m×n個區(qū)塊，能夠大幅減少值域范圍，從而降低位置數(shù)據(jù)采集造成的噪聲誤差。從X軸、Y軸2 個維度分別劃分區(qū)間，發(fā)送給隨機采樣的少量用戶集合U′，用戶位置的不同維度數(shù)據(jù)在本地進行擾動后發(fā)送給收集方（步驟1～步驟7），收集方分別統(tǒng)計X軸和Y軸2 個維度各區(qū)間的頻數(shù)，并對估計數(shù)進行修正（步驟8）。根據(jù)設(shè)定的橫、縱坐標的密度閾值判斷區(qū)間是否為稀疏區(qū)間，獲取用戶在X軸、Y軸的分布情況（步驟10～步驟11）。由于初步獲取的用戶分布情況并不準確，因此需要根據(jù)相鄰稀疏區(qū)間的相對密度差rgdd 重構(gòu)密度區(qū)間（步驟12～步驟14），rgdd(di,di+1)=，其中，ratei、ratei+1為相鄰稀疏區(qū)間di、di+1的密度。以區(qū)間密度作為KD-樹劃分網(wǎng)格的依據(jù)（步驟15），選擇區(qū)域中密度最小的稀疏區(qū)間，如果區(qū)間一端恰好為當前待分割區(qū)域邊界，則將稀疏區(qū)間所在區(qū)域標記為稀疏區(qū)域；否則，按照稀疏區(qū)間端點將區(qū)域分割為3 個部分，稀疏區(qū)間所包含區(qū)域標記為稀疏區(qū)域。檢查已劃分的區(qū)塊，若其中存在稀疏區(qū)間，且橫坐標和縱坐標內(nèi)都包含密集區(qū)間，則對區(qū)塊繼續(xù)劃分，否則，停止劃分并得到根據(jù)密度劃分的網(wǎng)格Grid。

在密度自適應(yīng)網(wǎng)格劃分的基礎(chǔ)上，仍需對稠密區(qū)域節(jié)點繼續(xù)進行細粒度劃分。MTR 算法以當前劃分節(jié)點的用戶子集統(tǒng)計計數(shù)C(Vk)為依據(jù)，區(qū)分節(jié)點是否繼續(xù)劃分，對達到計數(shù)標準的節(jié)點按照四分樹或二分樹劃分方法分裂稠密區(qū)域節(jié)點（步驟2～步驟5），否則不再分割（步驟7），經(jīng)過多次重構(gòu)后獲得多叉樹劃分結(jié)果。

算法2MTR 算法

3.2.2 LRR 算法

在不同的劃分層次統(tǒng)計不同的用戶集合，用戶根據(jù)當前劃分層次節(jié)點進行編碼，將擾動值發(fā)送給數(shù)據(jù)收集者，擾動過程中所采用的優(yōu)化隨機應(yīng)答機制與文獻［25］一致，如算法2 所示。LRR 算法描述如算法3 所示。

算法3LRR 算法

3.2.3 空間數(shù)據(jù)分層自適應(yīng)劃分算法KDG-HT

KDG-HT 算法描述如算法4 所示。

算法4KDG-HT 算法

為了有效減少劃分層次，保證大規(guī)模空間數(shù)據(jù)劃分算法能夠抽取充足的數(shù)據(jù)，KDG-HT 算法利用基于KD-樹的密度自適應(yīng)劃分方法KDG，獲得第一層密度網(wǎng)格Grid（步驟1～步驟2），將位置空間分為稀疏區(qū)域和密集區(qū)域，減少空區(qū)塊的產(chǎn)生，避免大量空節(jié)點引入的噪聲誤差（本文中η值設(shè)為5%）。然后將網(wǎng)格按照分割標準采用四叉樹進行分割，預(yù)估樹的最大高度h，本文基于文獻［8］設(shè)定：

其中：值域|Dom(D′)|表示處于密集區(qū)域的最大網(wǎng)格區(qū)域。

樹結(jié)構(gòu)每進行一次劃分，則獲取用戶子集在當前樹結(jié)構(gòu)葉子節(jié)點的分布情況，給下一層樹結(jié)構(gòu)劃分提供總體分布先驗知識（步驟5～步驟18）。收集者通過MTR 算法重構(gòu)樹T，直到樹結(jié)構(gòu)被劃分到最后一層（步驟19～步驟20），最終數(shù)據(jù)收集者得到自適應(yīng)劃分的樹結(jié)構(gòu)KDT。

4 實驗結(jié)果與分析

4.1 實驗設(shè)置

本文實驗環(huán)境為Windows7 3.40 GHz，8.0 GB，所有算法均采用Python 實現(xiàn)，編程環(huán)境為Python3.6。實驗采用2 組真實的地理數(shù)據(jù)集Checkin 和Landmark，Checkin 數(shù)據(jù)集從基于位置的社交網(wǎng)站Gowalla 獲取，Landmark 數(shù)據(jù)集是紐約市出租車2011 年的乘車和下車地理坐標數(shù)據(jù)，實驗中只取2 組數(shù)據(jù)集的經(jīng)緯度信息，2 組數(shù)據(jù)集的具體統(tǒng)計信息和可視化結(jié)果分別見表1 和圖3。

表1 數(shù)據(jù)集統(tǒng)計信息Table 1 Datasets statistics

圖3 實驗數(shù)據(jù)集可視化結(jié)果Fig.3 Visualization results of experimental datasets

利用上述2 種數(shù)據(jù)集，參照文獻［8］，本文采用相對誤 差RE 來度量RAPPΟR［13］、UG［19］、GT-R［20］、KDG-HT 算法的范圍查詢精度。設(shè)置3 種大小不同的查詢區(qū)域，針對每種類型的查詢區(qū)域隨機生成查詢，計算相對誤差的平均值。相對誤差計算如式（3）所示：

其中：Q(D)表示查詢原始數(shù)據(jù)集D的結(jié)果表示數(shù)據(jù)集D擾動后的發(fā)布數(shù)據(jù)范圍計數(shù)結(jié)果；ρ=0.001× |D|，|D|代表原始數(shù)據(jù)集大小。

本地差分隱私模型的噪音誤差受隱私預(yù)算影響較大，KDG-HT 算法提出用戶分組的方法以避免隱私預(yù)算分割，同時也會引入額外噪聲誤差，細粒度查詢所涉及的樹節(jié)點較深，噪聲誤差更具對比性，因此，實驗在上述2 種數(shù)據(jù)集以及細粒度查詢設(shè)置下計算噪聲誤差的估計值。相對誤差由噪聲誤差與均勻假設(shè)誤差構(gòu)成，噪聲誤差的計算如式（4）所示：

本文設(shè)置抽樣概率為5%，隱私預(yù)算參數(shù)的取值為0.1、0.3、0.5。實驗中查詢范圍分別覆蓋Checkin和Landmark 數(shù)據(jù)集 的［5%，20%］、［20%，40%］、［40%，60%］，在每種查詢范圍內(nèi)隨機生成5 000 次查詢。

4.2 數(shù)據(jù)發(fā)布可用性度量

4.2.1 基于Checkin 數(shù)據(jù)集的算法RE 值比較

圖4 所示為Checkin 數(shù)據(jù)集 下RAPPΟR、UG、GT-R 以及KDG-HT 算法的RE 值比較結(jié)果。由圖4（a）～圖4（c）可以看出，在固定查詢范圍時，ε 由0.1 變化到0.5，4 種算法的查詢精度隨著ε 增大而逐漸提高，KDG-HT 的查詢精度優(yōu)于其他3 種算法。當查詢范圍為［5%，20%］時，KDG-HT 的查詢精度相比其他3 種算法效果顯著，特別是在ε=0.3 時，本文算法精度是GT-R 算法的3 倍。從圖4 可以看出，查詢范圍從［5%，20%］變化到［40%，60%］且ε 固定時，算法查詢精度逐漸提高，這主要與查詢區(qū)域和相交節(jié)點的重合比例（scale ∈[0,1]）有關(guān)，均勻假設(shè)誤差與scale 呈反比，查詢范圍影響scale 大小，查詢范圍過小會引起均勻假設(shè)誤差較大。隨著查詢范圍的增大，查詢區(qū)域與相交節(jié)點的重合比例scale 增大，均勻假設(shè)誤差逐漸減小，從而提高了查詢精度。本文算法能夠針對性地自適應(yīng)劃分大規(guī)模數(shù)據(jù)空間，對于密集區(qū)域進行充分劃分，有效降低了均勻假設(shè)誤差，同時減少了稀疏區(qū)域空節(jié)點產(chǎn)生，降低了噪聲誤差，Checkin 數(shù)據(jù)集中數(shù)據(jù)分布不均勻、偏斜程度較高的問題得到有效解決，因此，查詢精度明顯提升。

圖4 Checkin 數(shù)據(jù)集的范圍查詢結(jié)果Fig.4 Range query results of Checkin dataset

4.2.2 基于Landmark 數(shù)據(jù)集的算法RE 值比較

圖5 所示為Landmark 數(shù)據(jù)集下RAPPΟR、UG、GT-R 以及KDG-HT 算法的RE 值比較結(jié)果。由圖5（a）～圖5（c）可以看出，在固定查詢范圍時，ε 由0.1 變化到0.5，各個算法的查詢精度隨著ε 的增大而逐漸提高，KDG-HT 的查詢精度優(yōu)于其他3 種算法，尤其當查詢范圍在［5%，20%］時，KDG-HT 的查詢精度比其他算法提高了一倍以上。4 種算法的查詢精度都隨著查詢范圍的增大而提高，這種現(xiàn)象主要是由于查詢范圍增大后，所涵蓋的節(jié)點面積增大，均勻假設(shè)誤差降低，使得查詢精度提高。由于Landmark數(shù)據(jù)集分布較為均勻，偏斜程度較低，均勻網(wǎng)格劃分方法的精度已經(jīng)達到較高水平，KDG-HT 算法查詢精度的提升空間較小，因此，其效果提升沒有Checkin 數(shù)據(jù)集中明顯。

圖5 Landmark 數(shù)據(jù)集的范圍查詢結(jié)果Fig.5 Range query results of Landmark dataset

4.2.3 噪聲誤差影響程度比較

圖6 所示為Checkin 和Landmark 數(shù)據(jù)集在［5%，20%］查詢范圍下RAPPΟR、UG、GT-R 以及KDG-HT算法的NE 值比較結(jié)果。由圖6（a）可以看出，ε 由0.1變化到0.6，各個算法的NE 值隨著ε 的增大而逐漸降低，KDG-HT 算法的NE 值相比RAPPΟR 和UG 算法降低了5 倍以上。RAPPΟR 和UG 算法采用傳統(tǒng)的隱私預(yù)算分割策略，在本地差分隱私中，這種策略對噪聲誤差影響較大。GT-R 算法和KDG-HT 算法都利用隱私預(yù)算的并行組合性代替隱私預(yù)算分割策略，因此，都大幅降低了噪聲誤差。在ε 值較小時，KDG-HT 算法的NE 值低于GT-R 算法，這是由于KDG-HT 算法根據(jù)數(shù)據(jù)集的分布情況進行空間劃分，GT-R 算法采用均勻劃分方法，隨著ε 值的增大，噪聲影響減小，因此，在ε 值較大時，2 種算法產(chǎn)生的噪音差異減小。在圖6（b）中，KDG-HT 算法的NE 值相比RAPPΟR、UG 算法有明顯降低，但效果沒有Checkin 數(shù)據(jù)集中明顯，這也是由于KDG-HT 算法的多層空間劃分方法在非均勻數(shù)據(jù)集上優(yōu)勢較為明顯，而Landmark 數(shù)據(jù)集中分布相對均勻，尤其在隱私預(yù)算較高時，KDG-HT 與其他算法降低噪聲誤差的效果相近。由圖6 可以看出，KDG-HT 算法的噪聲誤差在2 種數(shù)據(jù)集上都明顯低于RAPPΟR、UG 算法，說明用戶分割策略帶來的噪聲影響遠小于隱私預(yù)算分割所造成的噪聲，其能夠有效降低噪聲誤差。

圖6 噪聲誤差對比Fig.6 Noise error comparison

4.3 算法運行時間比較

表2 所示為不同ε 取值下UG、RAPPΟR、GT-R和KDG-HT 算法在Checkin 數(shù)據(jù)集下的執(zhí)行時間，其中運行時間不包括數(shù)據(jù)讀取以及查詢時間。從表2可以看出，本文KDG-HT 算法具有較高的運行效率，這是由于算法中采用的用戶分割方法能夠在很大程度上降低通信代價，而GT-R 算法中用戶抽樣層次方法也能達到類似的效果，因此，KDG-HT 和GT-R 都具有較高的 運行效 率。當ε 值 為0.1 時，KDG-HT 算法比GT-R 算法的運行效率高0.14 倍，當ε 值為0.5時，KDG-HT 算法比GT-R 算法的運行效率高0.17 倍，相較GT-R 算法，本文算法的劃分效率更高，主要原因是本文采用的密度自適應(yīng)劃分方法有效減少了劃分層次。

表2 不同ε 取值下4 種算法的運行時間對比Table 2 Comparison of running time of four algorithms under different ε values s

在表2 中，隨著ε 的增大，UG、RAPPΟR、GT-R 算法運行時間增加，這是由于UG、RAPPΟR、GT-R 算法的劃分粒度受隱私預(yù)算ε 影響，ε 越大，網(wǎng)格劃分粒度越細，樹結(jié)構(gòu)層次越高，因此，算法運行時間增加。而本文KDG-HT 算法對區(qū)域執(zhí)行自適應(yīng)劃分方法，ε 大小對其劃分方式影響較小，因此，在不同隱私預(yù)算下本文算法的運行效率均較高且穩(wěn)定。

5 結(jié)束語

本文針對本地差分隱私模型下大規(guī)模空間數(shù)據(jù)采集和發(fā)布過程中存在的空間劃分問題，提出一種分層次自適應(yīng)劃分算法KDG-HT。該算法能夠通過估計數(shù)據(jù)集的分布情況自適應(yīng)劃分空間，解決了本地差分隱私模型無法獲取用戶真實位置數(shù)據(jù)的問題，同時分層次劃分方法和用戶分割策略克服了非均勻大規(guī)模空間數(shù)據(jù)范圍查詢的噪聲累積問題，有效平衡了均勻假設(shè)誤差和噪聲誤差，使數(shù)據(jù)劃分發(fā)布查詢精度得到有效提高。在2 個較具代表性的大規(guī)模數(shù)據(jù)集上的實驗結(jié)果表明，KDG-HT 算法查詢精度優(yōu)于UG、RAPPΟR 等算法。空間數(shù)據(jù)規(guī)模大且變化快，現(xiàn)有的靜態(tài)空間分割方法無法適用于本地差分隱私模型下動態(tài)空間數(shù)據(jù)的采集和發(fā)布過程。本文KDG-HT 算法能夠在本地差分隱私模型下預(yù)估空間位置數(shù)據(jù)的分布情況。下一步考慮將本文算法與滑動窗口技術(shù)相結(jié)合，并應(yīng)用于本地差分隱私模型下的動態(tài)環(huán)境隱私數(shù)據(jù)發(fā)布任務(wù)。