差分隱私下多重一致性約束問題的逼近方法

蔡劍平，劉西蒙，熊金波，應作斌，吳英杰

（1.福州大學數學與計算機科學學院，福建 福州 350108；2.福建師范大學數學與信息學院，福建 福州 350117；3.新加坡南洋理工大學電氣與電子工程學院，新加坡 639798）

1 引言

隨著互聯網和大數據技術的快速發展，人們普遍意識到數據發布、信息共享的重要性。為了達到信息公開、成果展示或者提升商業價值、履行社會責任等目的，包括醫療、餐飲、教育、金融等在內的多個行業都在嘗試利用互聯網和大數據技術向社會公開發布統計信息。然而，數據挖掘技術的飛速發展也使人們從公開發布的信息中挖掘潛在信息的能力不斷增強。除了有價值的合法信息外，可被挖掘的信息中還潛藏著大量的個人敏感信息。利用公開發布的信息，攻擊者可結合相關背景知識，利用關聯分析等技術手段推斷或竊取個人隱私，給人們的隱私安全帶來了巨大威脅。為保護個人隱私，Dwork[1]提出了差分隱私保護技術。該技術通過對數據添加擾動的方式實現隱私保護，從理論上保證了具備任何知識的攻擊者都無法從被保護的公開數據中挖掘個人隱私，是目前公認有效的隱私保護技術。

在某些數據發布問題中，數據間滿足了某種語義上的一致性約束。由于差分隱私通過向數據添加噪聲實現隱私保護，噪聲的隨機性會徹底破壞數據間一致性約束。為了獲得滿足一致性約束的發布效果，不少文獻針對各類模型提出了有效的一致性發布算法[2-8]。然而，多數算法所適用的場景針對性較強，難以有效地應用于更廣泛的差分隱私最優一致性發布問題。

隨著差分隱私技術的日益普及，數據發布場景越來越復雜，同時數據間一致性約束問題的解決難度也越來越高。不少問題已超出了現有技術的關注范圍，雖然采用基于極大似然估計的通用解法能夠實現最優一致性發布，但通用解法效率極低，無法滿足較大規模的數據發布需求。以餐飲行業的直方圖統計發布為例，假設某餐館記錄了開業以來所有顧客的消費情況。記錄內容如表1 所示，包含了顧客標識、食物種類、消費數量以及消費時間。假設餐館提供的食物單品為可樂、漢堡、雞翅、薯條、雞塊5種，則顧客所能購買的食物單品種類數c=5 。為了向公眾展示銷售情況，餐館決定按天統計銷量并采用直方圖發布技術公開發布各單品銷量，發布內容如表2 所示。同時，為保護顧客隱私，餐館決定采用差分隱私技術并希望獲得最優的一致性發布效果。本文稱發布過程中涉及的問題為餐館銷量直方圖發布問題。考慮餐館長期以來只以套餐的形式銷售食物，并不以單品形式銷售，導致某些單品的銷量組合無法滿足該場景的語義特征。例如，餐館銷售以下3種套餐：1) 2 份可樂+漢堡+雞翅+雞塊，2) 2 份漢堡+2 份雞翅+薯條，3) 可樂+漢堡+薯條+雞塊。

表1 消費記錄

表2 銷量統計

在上述套餐組合下某些銷量數據不可能出現。例如，不會出現5 種單品的銷量均為3 份的情況。因此，除了直方圖一致性約束問題，餐館銷量直方圖發布問題還面臨由套餐組合導致的一致性約束問題。本文稱該問題為套餐一致性約束問題。餐館銷量直方圖發布問題是由兩者共同組成的全局一致性約束問題，超出了直方圖發布問題的研究范疇，更加復雜。而一致性約束子問題的求解容易得多。直方圖一致性約束問題的研究[3-5]已相當成熟，現有技術已具備實現大規模直方圖最優一致性發布的能力；并且，由于餐館提供的食物單品僅有5 種，每個套餐一致性約束子問題僅為數據規模為5 的小問題，采用通用解法[6]即可高效求解。數據規模小或存在高效算法等原因常常使子問題的求解難度比全局問題容易得多，但子問題之間并非簡單的疊加關系，分別解決子問題的結果往往不能解決全局問題。研究表明，單獨對某個子問題執行最優一致性發布算法會破壞另一個子問題發布的一致性。

為充分發揮一致性約束子問題高效求解的優勢，提升全局最優一致性問題的求解效率，本文基于最優一致性發布問題的理論分析提出了差分隱私多重一致性約束最優發布問題。該問題主張將復雜的差分隱私的最優一致性約束問題拆分成多個可高效求解的子問題，然后通過獨立求解子問題的最優一致性發布高效地實現原問題的最優一致性發布。經研究，本文提出了差分隱私下多重一致性約束問題的逼近方法，簡稱多重一致性約束逼近方法。該方法通過反復迭代求解一致性約束子問題使發布結果逼近原問題的最優一致性發布。嚴格理論論證表明，無論子問題被如何劃分，該方法總能保證多重一致性約束問題實現最優一致性發布。此外，不少同類子問題所涉及的發布數據互不相交，數據的發布過程具有獨立性，利用這種獨立性設計的并行算法可進一步提升多重一致性約束逼近方法的求解效率。

本文主要的研究工作如下。

1) 求得差分隱私下最優一致性發布的解析表達式，并深入分析了解析表達式的數學性質。

2) 基于解析表達式的分析提出差分隱私多重一致性約束問題的逼近方法，并對該方法的收斂性進行充分論證。

3) 討論多重一致性約束逼近方法的可并行性。以餐館銷量直方圖發布問題為例設計了最優一致性發布算法并進行實驗分析。

2 相關工作

自Dwork[1]提出差分隱私以來，不少國內外學者對數據發布的一致性約束問題做了深入研究，提出了許多有效的最優一致性發布算法。其中，以樹為基礎的發布模型是差分隱私一致性約束問題的典型代表。為解決直方圖發布過程中的數據不一致問題，Boosting 算法[2]通過對完全k叉樹的后置處理實現了最優一致性發布。基于Boosting 算法，Cormode 等[8]針對空間數據的劃分發布問題建立了四分樹發布模型，并提出了滿足一致性約束的Quad-Post 算法。考慮Boosting 算法只能針對完全k叉樹的不足，吳英杰等[3]提出了LBLUE（local best linear unbiased estimation）算法實現了面向任意區間樹的最優一致性發布，賈俊杰等[5]則通過將查詢區間映射為完全k叉樹的方法改進最優一致性發布。與其他算法不同，LBLUE 算法將區間樹中每對父子節點間的等式關系作為一個一致性約束子問題，然后采用迭代逼近的思想求解最優一致性發布。實際上，LBLUE 算法所解決的問題是多重一致性約束最優發布問題的一個特例，其有效性可以通過本文提出的理論得以充分解釋。因此，該算法可以視為多重一致性約束逼近方法的一個具體應用。相比于Boosting 算法，LBLUE 算法不再局限于完全樹模型，表明多重一致性約束逼近方法具備了處理更復雜模型的能力。

通過構造虛擬節點，張雙越等[7]發現了差分隱私軌跡流量發布過程中潛在的一致性約束問題，通過實現最優一致性發布有效地提升了數據發布的精確性。該結果表明，除了以樹為基礎的發布模型，差分隱私一致性約束問題還具有其他更多的表現形式。多種不同的差分隱私一致性約束子問題可能存在于一個復雜的發布場景中。然而，目前關于差分隱私一致性約束問題的研究主要針對某個特定的應用場景。雖然大多數一致發布算法都是高效的，但仍無法解決復雜發布場景所涉及的一致性約束問題。采用極大似然估計的思想，Lee 等[6]將差分隱私一致性約束問題表述為抽象的優化方程，并實現了適用于任意最優一致性約束問題的通用解法。然而，通用解法實現最優一致性發布的效率普遍較低，只能有效解決局部的或規模較小的一致性約束問題。如何合理利用高效但針對性強的一致性發布算法以及低效但通用的一致性發布算法解決更復雜的差分隱私最優一致性約束問題具有較高的研究價值。此外，目前多數差分隱私一致性約束問題的研究工作集中在發布精度或效率的提升上。關于最優一致性發布性質的研究還十分有限，現有理論難以解釋多重一致性約束之間的內在聯系。因此，差分隱私多重一致性約束問題仍存在較大的研究空間。

3 預備知識

3.1 差分隱私

為避免隱私泄露，差分隱私技術通過向待發布數據添加噪聲的方式實現隱私保護。通過添加噪聲，差分隱私有效地隱藏了隱私信息的存在性，確保攻擊者即使掌握了所有背景知識也無法有效推斷個人隱私。差分隱私的形式化定義如下。

定義1差分隱私[9]。若一個隨機算法M 滿足(ε,δ)?差分隱私，則對于2 個兄弟數據集D和D'滿足所有M的輸出O?Range(M) 都有以下不等式成立。

假設待發布數據由n個數據組成，分別記為x1,x2,…,xn，則數值型的發布函數為A:D→Rn。不妨將這些數據依次寫為列向量x=[x1,x2,…,xn]T的形式，滿足x=A(D)。隨機算法M 通常采用特定的噪聲機制向 A(D)添加噪聲以實現差分隱私。常見的噪聲機制主要包括拉普拉斯機制和高斯機制，其定義分別如下。

定義2拉普拉斯機制[10]。對于發布函數 A:D→Rn，拉普拉斯機制通過式(2)實現(ε,0)?差分隱私。

其中，ξ為隨機向量且各元素均符合拉普拉斯分布，即，1Δ為A 的1L?敏感度[10]。

定義3高斯機制[9]。對于發布函數A:D→nRn，高斯機制通過式(3)實現(ε δ),?差分隱私。

根據上述定義可知，無論采用拉普拉斯機制還是高斯機制，M(D)中添加的噪聲都具有獨立同分布的性質。由于噪聲隨機性，M(D)無法僅靠噪聲機制保證滿足任何一致性約束。

3.2 數據發布的一致性約束問題

在數據發布過程中，一致性約束問題是由m個一致性約束條件組成的發布問題，其發布結果要求這m個一致性約束條件同時滿足。其中，一致性約束條件的定義如下。

定義4一致性約束條件。對于由n個數據組成的待發布數據x1,x2,…,xn，一致性約束條件表示為一個關于xi的線性等式關系，如式(4)所示。

其中，mj和b是限定一致性約束條件的系數。根據上述定義，對于滿足m個一致性約束條件差分隱私發布問題，在引入噪聲機制之前，x滿足了如式(5)所示的一致性約束方程。

由式(5)可知，一致性約束問題取決于矩陣M∈Rm×n和向量b∈Rm×1。由于添加噪聲前的發布結果滿足式(5)，因此式(5)為一致性方程，至少存在一個解。本文稱滿足式(5)的所有解均為一致性發布。記 M(D)的輸出為向量～x=x+ξ，由上述分析可知，無法保證滿足式(5)。為求得差分隱私下的最優一致性發布，文獻[2,6,11-13]基于優化方程式(6)設計后置處理算法求得最優一致性發布。通常情況下，的總體誤差小于，后置處理總是能有效地提升數據發布的精確性。

根據一致性發布的存在性，定理1 論證關于優化式(6)的最優一致性發布存在且唯一，同時最優一致性發布具有明確的解析表達式。

該優化方程是關于x' 的一致方程的最小范數解。由文獻[14]可知

證畢。

作為最優一致性發布的解析表達式，式(7)可作為通用解法有效解決任意差分隱私下最優一致性約束問題。然而，式(7)所涉及的M?是關于矩陣M的Moore-Penrose 逆[14]運算。作為傳統矩陣逆運算的拓展，Moore-Penrose 逆求解過程十分復雜，運算量極大。其求解難度不低于時間復雜度為O(n3)的傳統求逆運算，無法高效地解決最優一致性約束發布問題。這導致通用解法難以有效解決數據規模較大的一致性約束問題。雖然通用解法的實用性有限，但作為小型最優一致性約束發布問題的解決方案仍然是合適的。

相較而言，針對具體發布問題設計的最優一致性發布算法的求解效率則高得多。Hay 等[2]設計的Boosting 只需對完全k叉樹分別執行一次自底向上和自頂向下的后置處理，即可實現最優一致性發布，時間復雜度僅為O(n)；張雙越等[7]設計的算法巧妙地利用軌跡流量發布問題的稀疏性實現多達數十萬個節點的交通路網的最優一致性發布。然而，上述兩項技術并不具備通用性，難以適用于其他發布場景，甚至無法直接應用于拓展模型。因此，適用范圍相對有限。

4 多重一致性約束問題的逼近方法

根據差分隱私多重一致性約束最優發布問題的思想，復雜的差分隱私的最優一致性約束問題可劃分為多個最優一致性發布子問題。相比于原問題，合理劃分后的子問題往往更簡單且容易解決，或者可利用現有技術得以高效求解。由于文獻[2-7]已對諸多子問題提供了解決方案，因此本文將重點研究如何利用各部分子問題的最優一致性發布結果實現原問題的最優一致性發布。構建差分隱私多重一致性約束最優發布問題首先進行子問題劃分。由于M和b的每行代表了一個一致性約束條件，因此劃分子問題的過程即將一致性約束條件重新排列、分組的過程。形式上相當于對M和b按行進行矩陣分塊的過程，且表述同一個一致性約束子問題的所有一致性約束條件將被劃分到同一個子矩陣。設原問題劃分為k重一致性約束發布問題，則分塊過程為

其中，?為函數的復合運算符，即fj?f i(x)=f j(f i(x))；t表示函數的復合運算次數，即f2(x)=f(f(x))。根據極限表達式(8)，差分隱私下多重一致性約束問題的逼近方法的核心思想是通過依次反復求解一致性約束子問題，最終求解結果趨近于fM,b()，即原問題的最優一致性發布。這樣只需求得子問題的最優一致性發布，即可解決原問題的最優一致性發布。

5 最優一致性發布的性質分析

確保差分隱私下多重一致性約束問題的逼近方法可行的關鍵在于論證式(8)能否準確地收斂于原問題的最優一致性發布。由于該問題十分復雜，論證過程需要大量理論基礎，本節首先從最優一致性發布的性質入手開展研究工作，然后循序漸進地尋找該問題的答案。

作為式(7)的關鍵組成部分，Moore-Penrose 逆M?具有一些重要的數學性質。相關資料[15-17]表明，M?具有如下性質。

性質1[15]對于任意矩陣M∈Rm×n，都有M?=MT(MMT)?成立。

性質2[16]對于任意矩陣M∈Rm×n，都有MM?M=M成立。

性質3對于任意矩陣M∈Rm×n，都有M?M為冪等矩陣成立，且有譜范數[17]滿足。

利用這些性質，本文通過進一步分析得出如下關于最優一致性發布的定理成立。

定理 2對于任意向量x∈Rn×1，設y=fM,b(x)，則有My=b。并且fM,b(x)的運算滿足冪等律，即fM,b(x)=fM,b?fM,b(x)。

證明由于y=fM,b(x)已為滿足優化方程式(6)的最優一致性發布。將y代入式(6)中的，顯然也是方程的一個可行解。此時，目標函數，根據fM,b(x)的定義可知y=fM,b(y)。

設y'=fM,b?fM,b(x)=fM,b(y)=M?(b?My)+y，由于My=b?b?My=0，代入可得y'=y，因此冪等律得證。

根據定理2，本文有如下推論。

推論1設p∈Rn×1是任意滿足Mp=b的一致性發布，至少能夠找到一個向量x∈Rn×1使p=fM,b(x)成立。

證明根據定理2 可知，任意滿足Mp=b的一致性發布p都有p=fM,b(p)。只需令x=p，即找到一個向量x使p=fM,b(x)成立。證畢。

雖然推論1 只論證了p本身能滿足推論條件，但實際上滿足p=fM,b(x)的向量往往無窮多，不過本文的分析過程只需關注其存在性，對具體有哪些x滿足p=fM,b(x)將不再贅述。

接下來，定理3 將揭示最優一致性發布與其他一致性發布之間的關系。

定理3對于任意向量x及其最優一致性發布y=fM,b(x)，設p是滿足Mp=b的一致性發布且，則p是關于x的最優一致性發布。

證明采用反證法證明，若p不是關于x的最優一致性發布，即p≠y，則。

由于p是滿足Mp=b的一致性發布，根據推論1，可令向量q使p=fM,b(q)，有

x?p展開的結果為

y?p展開的結果為

綜上可得

利用性質2 可得

利用性質1 可得

因此，有

與題設不符，假設不成立。因此，p=y，p是關于x最優一致性發布。證畢。

通常情況下，一致性發布的數量有無窮多個而最優一致性發布只有一個。定理3 給出了判斷某個一致性發布是否為最優一致性發布的方法，對于檢驗算法是否實現了最優一致性發布具有重要意義。

此外，研究還發現最優一致性發布滿足2 種不變性特征，分別是范數不變性以及內積不變性，具體內容如下。

定理4范數不變性。設p是滿足Mp=b的一致性發布，則對于向量x及其最優一致性發布y=fM,b(x)，有

證明對展開，有

定理5內積不變性。設p1和p2是滿足方程Mp=b的2 個一致性發布，對于向量x及其最優一致性發布y=fM,b(x)，則關于它們的內積滿足

證明由于p1和p2是滿足方程Mp=b的一致性發布，根據推論1，可找到向量q1和q2滿足p1=fM,b(q1)和p2=fM,b(q2)。則

再次利用式(9)可知

同理，代入可得式(12)成立。證畢。

定理4 和定理5 分別體現了多重一致性約束問題的逼近方法迭代過程中內在的2 種不變性特征，對于其收斂性的分析過程具有重大意義。

6 收斂性分析

根據上述分析結果，本節將進一步分析差分隱私下多重一致性約束問題的逼近方法的收斂性，并以此論證逼近方法經過多次迭代后將實現原問題的最優一致性發布。為了確保分析收斂性的過程便于理解，本節將依次從差分隱私下多重一致性約束問題的逼近方法能否收斂、收斂結果是否滿足一致性約束以及一致性發布結果是否滿足最優發布這3個問題逐步深入地進行收斂性分析。

首先是關于多重一致性約束問題的逼近方法能否收斂的分析。根據式(8)所示的計算過程，記第s次執行復合運算所得結果為xs，x0表示執行一致性發布前的發布，即x0=。根據定義，式(8)的復合函數計算過程實際上是一種自右向左的操作過程，記第s次計算過程所執行的函數為f[s](x)，即對第[s]個子問題求最優一致性發布，則[s]=(s? 1)modk+1。設p為滿足Mp=b的任意一致性發布。由根據定理4 所述的范數不變性，有

反復運用該定理，可得對于任意s有

但是，上述結果無法確定關于y是否滿足一致性發布。接下來，本文將嘗試論證y是否滿足方程My=b的一致性發布。采用反證法論證，首先假設y不是滿足My=b的一致性發布，即My≠b。根據多重一致性約束問題的定義，必然存在某個j使M jy≠bj。

令y'為原問題的一致性發布，即，由定理2 可知，y'為M jy=bj的解。由于y不是M jy≠bj的解，顯然y'和y不同。令，有d>0 。

根據序列{xi}的收斂性可知，對于任意μ>0，均存在足夠大的數l，可取任意s>l，均有。此時，取任意滿足s>l且[s]=j的整數s，有。

最后，本文將進一步論證y不僅是滿My=b的一致性發布，而且y是關于的最優一致性發布。

根據定理5 所述的內積不變性，對于滿足Mp=b中的任意2 個一致性發布p1和p2，有

反復運用該定理，可得

根據上述論證過程，本文成功證明差分隱私下多重一致性約束問題的逼近方法將會收斂于原問題的最優一致性發布。并且，逼近方法的收斂性是無條件的。即無論最優一致性子問題如何劃分，逼近方法總能夠成功實現最優一致性發布，體現了其強大的穩健性。因此，實踐中只需考慮所劃分子問題的易解性，通過合理的子問題劃分提升發布效率，而不必擔心劃分結果能否正確實現最優一致性發布。

7 多重一致性約束問題的并行計算

由于差分隱私下多重一致性約束問題的逼近方法在劃分子問題時只需考慮劃分的合理性，合理的劃分可使同類子問題間所涉及的子數據集互不相交，使同類子問題過程滿足獨立性。利用這種獨立性設計并行的計算過程能夠進一步提升多重一致性約束問題的求解效率。

以餐館銷量直方圖發布問題為例，5 個單品對應了5 個直方圖一致性約束子問題，套餐一致約束子問題數量與發布天數T一致。該問題是T+5 重一致性約束問題。不難發現，5 個直方圖一致性約束子問題各自關聯了一個單品，所涉及數據之間互無交集，最優一致性發布的求解結果也互不影響。因此，這5 個直方圖一致性約束子問題可并行計算。同理，套餐一致約束子問題關聯的每日發布數據也互無交集，這些子問題的求解也具有可并行性。

根據上述分析，結合多重一致性約束問題的逼近方法，餐館銷量直方圖發布問題可劃分為c（c=5）個直方圖一致性約束子問題與T個套餐一致約束子問題兩組。組內的各個子問題可并行地、獨立地求解。

根據上述分析，本文將設計差分隱私下餐館銷量直方圖發布問題的最優一致性發布并行求解算法。一方面，以顧客購買一次套餐作為事件提供事件級別差分隱私[18]保護，根據餐館提供的套餐分析，顧客購買套餐最多可以拿到5 份食物（套餐1和套餐2），每日銷售數據單獨發布時數據敏感度為5。

另一方面，根據Boosting算法的理論，直方圖發布的敏感度[2]取決于樹高。因此，采用拉普拉斯作為噪聲機制，餐館銷量直方圖發布問題的全局敏感度[10]為Δ1=ch。分析套餐一致性約束問題，根據套餐內容，本文關于每日銷量應滿足一致性約束方程Bvt=0。vt∈R5×1表示第t天的銷量，其第i個元素vt,i即為當天第i個單品的銷量。經分析，B的內容如式(13)所示。

由于套餐一致性約束子問題僅為數據規模為5的一致性發布問題，本文直接采用通用解法求解最優一致性發布。根據上述分析，本文提出算法1 求解差分隱私下餐館銷量直方圖發布問題的最優一致性發布。算法1 表明，本文提出的多重一致性約束問題逼近理論不僅能夠將更復雜的差分隱私一致性約束問題拆分成簡單的子問題，而且可以利用子問題將的獨立性實現并行求解算法，極大提升了算法求解性能。

算法1餐館銷量直方圖一致性并行發布算法

輸入餐館銷量數據集D，隱私預算ε

輸出差分隱私直方圖一致性發布樹

8 實驗分析

為了驗證本文所提多重一致性約束問題逼近方法解決實際問題的效果，本文以餐館銷量直方圖發布問題為例進行實驗分析。實驗將算法1 與相應的通用解法對比，從算法求解效率、收斂性、穩定等方面對多重一致性約束問題的逼近方法進行綜合分析。已有分析表明，Boosting 等差分隱私最優一致性發布問題的發布效果與加噪前數據內容無關[19]。為了實現更大規模的實驗分析，在實驗目的不受影響的前提下，本文采用虛擬數據進行實驗。并且，為保持實驗的準確與統一，實驗均采用二叉樹實現Boosting 子算法。研究表明[4]，差分隱私一致性約束問題的最優一致性發布效果在不同ε下是穩定的，為避免實驗冗長，實驗統一設ε=1 。實驗硬件環境如下：Intel?CoreTM i5-9500H CPU@3.00 GHz，8 GB 內存，1 TB 存儲空間。

8.1 收斂性分析

作為一種逼近方法，算法1 的收斂能力至關重要。因此，本節將通過跟蹤算法運行過程來對算法的收斂性進行深入分析。收斂性分析包括2 個方面，分別是一致性檢驗和發布誤差分析。雖然通用結果可由解析表達式(7)直接求解，無法直接對比兩者的迭代過程，但通用解法已被證明發布結果即為最優一致性發布，實驗對比可作為檢驗算法1 的一致性發布是否滿足最優性的可靠標準。因此，在分析發布誤差時，本文將其作為對比實驗。由于通用解法需要消耗大量資源，常規的實驗環境下通用解法難以有效滿足發布天數遠超1 000 天的發布需求。因此，本實驗以T={32,64,128,256,512,1024}天進行分組對比，實驗迭代次數固定為100 次，實驗重復多次，記錄平均結果。

作為多重一致性約束最優發布問題的基本目標，最終發布結果是否滿足一致性約束是檢驗算法有效性的重要指標。為檢驗發布結果的一致性，本文提出了一致性偏差來衡量算法1 在迭代過程中滿足一致性的情況。將s次迭代后的所有數據組織為向量形式，記為。然后，令。根據一致性約束問題的定義可知，當完全滿足一致性時，ψ(s)應該等于0。不過，上述收斂性分析表明，逼近方法是在迭代過程中不斷地令發布結果趨近于一致性。因而，本實驗采用均方誤差來衡量一致性偏差。記s次迭代后的一致性偏差為mses，則mses的計算過程如式(14)所示。

如圖1 所示，算法1 在迭代過程中出現的一致性偏差隨著迭代次數的增加而快速減少。雖然隨著T的增加，一致性偏差的收斂速度有所減少，但所有實驗都能在迭代50 次左右使一致性偏差趨近于0。因此，在迭代50 次之后，算法就具備了較令人滿意的一致性發布結果。并且隨著迭代的增加，一致性偏差單調遞減，表明算法1 的發布結果具有較強穩定性，不會在迭代過程中突然出現不一致性變大的發布結果。

圖1 逼近方法的一致性偏差分析

除了發布結果的一致性，發布誤差也是衡量發布結果優劣的重要指標。實驗采用標準差衡量發布的誤差。記s次迭代后發布結果相對于未加噪數據的標準差為errs，則errs可由式(15)求得

圖2 中，虛線表示采用通用解法求得的最優一致性發布結果。由圖2 可以看出，無論發布天數T為多少，算法都能相對穩定地收斂于最優一致性發布對應的誤差。并且在迭代前后，算法減少誤差的效果十分明顯，對于提升數據發布的精度具有重要價值。此外，從收斂效果來看，迭代初期算法即可平穩快速地收斂，使誤差能夠迅速逼近于最優一致性發布。算法只需要較少的迭代就能達到令人滿意在一致性發布效果。因此，本文所提多重一致性約束問題的逼近方法具有較高的收斂能力以及算法穩定性。

圖2 逼近方法的發布數據誤差

8.2 求解效率分析

為進一步驗證逼近方法的實用性，本節將探討算法1 求解最優一致性發布的效率。與8.1 節實驗不同，本次實驗要求算法1 達到足夠的精度才停止。因此，實驗設置算法終止條件為

將算法1 的逼近方法與通用解法對比，求得在不同的發布天數T下的算法運行時間如圖3 所示。

圖3 逼近方法與通用解法的運行時間對比

由圖3 可知，算法1 的求解效率顯著優于通用解法。從運行時間的增長幅度來看，算法1 的運行時間隨著數據量的增大接近于線性增長，與理論的時間復雜度O(Ts)相符。而通用解法增長幅度則快很多，其時間復雜度為O(T3)。雖然當處理小規模數據時，算法1 由于多次迭代運行時間略大于通用解法，但當數據規模變大時，通用解法的效率卻低很多，僅處理1 024天的數據發布就需耗時多達267 s，而算法1 僅需要0.667 s，差距高達400 倍。

實際上，算法1 所能處理的數據規模遠不止1 024 天。為探究其數據處理潛力，本文采用更大規模數據對其進行實驗并記錄求解耗時。實驗結果如圖4 所示。圖4 表明，算法1 已具備處理超大規模數據發布的能力，其所能處理的天數已高達百萬。這表明算法1 具有強大的數據處理能力，能夠滿足大多數實際發布的需要。同時也證明了本文所提出的多重一致性約束問題的逼近方法不僅具有較強的理論價值，還具有較強的實際應用價值。

圖4 逼近方法在大規模數據下的運行時間

9 結束語

通過差分隱私下多重一致性約束問題的深入研究，本文提出并論證了多重一致性約束問題的逼近方法的有效性，為利用一致性約束子問題解決復雜的差分隱私一致性約束問題的方法奠定了扎實的理論基礎。并且，本文以餐館銷量直方圖發布問題為例設計的餐館銷量直方圖一致性并行發布算法不僅充分展示了逼近方法較高的收斂能力以及求解效率，還體現了該方法具備的并行計算優勢。研究結果表明，多重一致性約束問題的逼近方法具有較高的應用價值。

后續的研究工作中將以本文的研究成果作為理論基礎，嘗試將已被研究的差分隱私一致性發布模型推廣到交通、醫療等領域，結合這些領域原本涉及的一致性發布過程實現應用范圍更廣、復雜程度更高的差分隱私數據發布算法；同時，還將對多重一致性約束問題進行更加深入的理論研究，就如何更加合理地劃分一致性約束子問題、如何提升逼近方法的收斂效率以及在不等式約束下如何實現多重一致性最優發布等問題開展研究工作，從而形成關于差分隱私最優一致性發布更加完善的理論體系。