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

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

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

1 引言

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

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

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

表1 消費記錄

表2 銷量統(tǒng)計

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

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

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

1) 求得差分隱私下最優(yōu)一致性發(fā)布的解析表達式，并深入分析了解析表達式的數(shù)學性質(zhì)。

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

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

2 相關工作

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

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

3 預備知識

3.1 差分隱私

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

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

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

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

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

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

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

3.2 數(shù)據(jù)發(fā)布的一致性約束問題

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

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

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

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

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

該優(yōu)化方程是關于x' 的一致方程的最小范數(shù)解。由文獻[14]可知

證畢。

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

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

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

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

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

5 最優(yōu)一致性發(fā)布的性質(zhì)分析

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

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

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

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

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

利用這些性質(zhì)，本文通過進一步分析得出如下關于最優(yōu)一致性發(fā)布的定理成立。

定理 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)已為滿足優(yōu)化方程式(6)的最優(yōu)一致性發(fā)布。將y代入式(6)中的，顯然也是方程的一個可行解。此時，目標函數(shù)，根據(jù)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，因此冪等律得證。

根據(jù)定理2，本文有如下推論。

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

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

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

接下來，定理3 將揭示最優(yōu)一致性發(fā)布與其他一致性發(fā)布之間的關系。

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

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

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

x?p展開的結果為

y?p展開的結果為

綜上可得

利用性質(zhì)2 可得

利用性質(zhì)1 可得

因此，有

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

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

此外，研究還發(fā)現(xiàn)最優(yōu)一致性發(fā)布滿足2 種不變性特征，分別是范數(shù)不變性以及內(nèi)積不變性，具體內(nèi)容如下。

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

證明對展開，有

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

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

再次利用式(9)可知

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

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

6 收斂性分析

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

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

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

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

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

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

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

根據(jù)定理5 所述的內(nèi)積不變性，對于滿足Mp=b中的任意2 個一致性發(fā)布p1和p2，有

反復運用該定理，可得

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

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

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

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

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

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

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

由于套餐一致性約束子問題僅為數(shù)據(jù)規(guī)模為5的一致性發(fā)布問題，本文直接采用通用解法求解最優(yōu)一致性發(fā)布。根據(jù)上述分析，本文提出算法1 求解差分隱私下餐館銷量直方圖發(fā)布問題的最優(yōu)一致性發(fā)布。算法1 表明，本文提出的多重一致性約束問題逼近理論不僅能夠?qū)⒏鼜碗s的差分隱私一致性約束問題拆分成簡單的子問題，而且可以利用子問題將的獨立性實現(xiàn)并行求解算法，極大提升了算法求解性能。

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

輸入餐館銷量數(shù)據(jù)集D，隱私預算ε

輸出差分隱私直方圖一致性發(fā)布樹

8 實驗分析

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

8.1 收斂性分析

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

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

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

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

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

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

圖2 逼近方法的發(fā)布數(shù)據(jù)誤差

8.2 求解效率分析

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

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

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

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

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

圖4 逼近方法在大規(guī)模數(shù)據(jù)下的運行時間

9 結束語

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

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