基于本地差分隱私的空間數據自適應劃分算法

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

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

0 概述

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

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

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

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

1 相關工作

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

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

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

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

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

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

2 相關定義與問題描述

2.1 本地差分隱私

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

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

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

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

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

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

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

2.2 KD-樹空間分割

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

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

3 基于用戶分割的空間自適應劃分算法

3.1 設計思想

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

圖2 KDG-HT 數據發布方法流程Fig.2 Procedure of KDG-HT data publishing method

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

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

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

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

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

3.2 算法實現

3.2.1 基于密度的KD-樹自適應劃分算法KDG

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

算法1KDG 算法

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

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

算法2MTR 算法

3.2.2 LRR 算法

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

算法3LRR 算法

3.2.3 空間數據分層自適應劃分算法KDG-HT

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

算法4KDG-HT 算法

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

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

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

4 實驗結果與分析

4.1 實驗設置

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

表1 數據集統計信息Table 1 Datasets statistics

圖3 實驗數據集可視化結果Fig.3 Visualization results of experimental datasets

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

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

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

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

4.2 數據發布可用性度量

4.2.1 基于Checkin 數據集的算法RE 值比較

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

圖4 Checkin 數據集的范圍查詢結果Fig.4 Range query results of Checkin dataset

4.2.2 基于Landmark 數據集的算法RE 值比較

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

圖5 Landmark 數據集的范圍查詢結果Fig.5 Range query results of Landmark dataset

4.2.3 噪聲誤差影響程度比較

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

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

4.3 算法運行時間比較

表2 所示為不同ε 取值下UG、RAPPΟR、GT-R和KDG-HT 算法在Checkin 數據集下的執行時間，其中運行時間不包括數據讀取以及查詢時間。從表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 算法，本文算法的劃分效率更高，主要原因是本文采用的密度自適應劃分方法有效減少了劃分層次。

表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 算法的劃分粒度受隱私預算ε 影響，ε 越大，網格劃分粒度越細，樹結構層次越高，因此，算法運行時間增加。而本文KDG-HT 算法對區域執行自適應劃分方法，ε 大小對其劃分方式影響較小，因此，在不同隱私預算下本文算法的運行效率均較高且穩定。

5 結束語

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