蔡劍平，劉西蒙，熊金波，應(yīng)作斌，吳英杰

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

1 引言

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

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

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

表1 消費(fèi)記錄

表2 銷量統(tǒng)計(jì)

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

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

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

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

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

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

2 相關(guān)工作

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

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

3 預(yù)備知識(shí)

3.1 差分隱私

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

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

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

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

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

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

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

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

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

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

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

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

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

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

證畢。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

x?p展開的結(jié)果為

y?p展開的結(jié)果為

綜上可得

利用性質(zhì)2 可得

利用性質(zhì)1 可得

因此，有

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

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

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

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

證明對(duì)展開，有

定理5內(nèi)積不變性。設(shè)p1和p2是滿足方程Mp=b的2 個(gè)一致性發(fā)布，對(duì)于向量x及其最優(yōu)一致性發(fā)布y=fM,b(x)，則關(guān)于它們的內(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 種不變性特征，對(duì)于其收斂性的分析過程具有重大意義。

6 收斂性分析

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

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

反復(fù)運(yùn)用該定理，可得對(duì)于任意s有

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

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

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

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

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

反復(fù)運(yùn)用該定理，可得

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

7 多重一致性約束問題的并行計(jì)算

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

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

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

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

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

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

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

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

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

8 實(shí)驗(yàn)分析

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

8.1 收斂性分析

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

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

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

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

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

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

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

8.2 求解效率分析

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

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

圖3 逼近方法與通用解法的運(yùn)行時(shí)間對(duì)比

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

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

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

9 結(jié)束語(yǔ)

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

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