蔡劍平，吳英杰，王曉東

福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州350116

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0481-14

?

基于矩陣機(jī)制的差分隱私連續(xù)數(shù)據(jù)發(fā)布方法*

蔡劍平，吳英杰+，王曉東

福州大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，福州350116

ISSN 1673-9418 CODEN JKYTA8

Journal of Frontiers of Computer Science and Technology

1673-9418/2016/10(04)-0481-14

E-mail: fcst@vip.163.com

http://www.ceaj.org

Tel: +86-10-89056056

* The National Natural Science Foundation of China under Grant No. 61300026 (國(guó)家自然科學(xué)基金); the Natural Science Foundation of Fujian Province under Grant No. 2014J01230 (福建省自然科學(xué)基金).

Received 2015-06,Accepted 2015-08.

CNKI網(wǎng)絡(luò)優(yōu)先出版: 2015-08-27, http://www.cnki.net/kcms/detail/11.5602.TP.20150827.1411.002.html

摘要：現(xiàn)有絕大多數(shù)差分隱私算法只考慮數(shù)據(jù)的一次靜態(tài)發(fā)布，而實(shí)際許多數(shù)據(jù)分析應(yīng)用卻涉及連續(xù)數(shù)據(jù)發(fā)布。為此，提出了一種基于矩陣機(jī)制的差分隱私連續(xù)數(shù)據(jù)發(fā)布方法。該方法的核心思想是首先利用樹狀數(shù)組構(gòu)建連續(xù)數(shù)據(jù)發(fā)布問題的策略矩陣，然后對(duì)策略矩陣進(jìn)行優(yōu)化以提高發(fā)布數(shù)據(jù)的精確性。隨后，進(jìn)一步針

對(duì)現(xiàn)有基于矩陣機(jī)制的優(yōu)化算法復(fù)雜度極高的問題，提出了時(shí)間復(fù)雜度為O(lg N)的快速對(duì)角陣優(yōu)化算法（fast diagonal matrix optimization algorithm，F(xiàn)DA），以有效應(yīng)用于大規(guī)模的連續(xù)數(shù)據(jù)發(fā)布。通過實(shí)驗(yàn)比較分析了FDA算法與同類算法所發(fā)布數(shù)據(jù)的精確度，結(jié)果表明FDA算法是有效可行的。

關(guān)鍵詞：差分隱私；矩陣機(jī)制；樹狀數(shù)組；連續(xù)發(fā)布

1　引言

隨著數(shù)字技術(shù)的發(fā)展，數(shù)據(jù)越來越多地充斥于現(xiàn)實(shí)生活當(dāng)中。數(shù)據(jù)給人們生活帶來的好處不言而喻，人們不僅可以利用數(shù)據(jù)進(jìn)行評(píng)估、分析和預(yù)測(cè)，還可以從中尋找有價(jià)值的信息，如啤酒與尿布的故事。然而，在享受數(shù)據(jù)帶來的好處的同時(shí)，也應(yīng)該注意到數(shù)據(jù)中包含的個(gè)人隱私信息可能存在隱私泄露的風(fēng)險(xiǎn)。特別是當(dāng)攻擊者帶有惡意時(shí)，他就有可能利用已掌握的知識(shí)分析所發(fā)布的數(shù)據(jù)，并從中挖掘出數(shù)據(jù)所對(duì)應(yīng)用戶的隱私信息。例如，只需根據(jù)4個(gè)時(shí)空點(diǎn)就能使95%的人泄露其位置信息[1]。因此，如何在發(fā)布數(shù)據(jù)的同時(shí)避免數(shù)據(jù)中包含的隱私被泄露是數(shù)據(jù)時(shí)代亟待解決的問題之一。針對(duì)這一問題，各種隱私保護(hù)模型被提出。其中，以提供嚴(yán)格數(shù)據(jù)保護(hù)為特點(diǎn)的差分隱私模型[2-4]得到了廣泛的認(rèn)可。該模型被提出后，人們基于該模型開展了很多研究工作，內(nèi)容涉及直方圖發(fā)布[5-8]、空間劃分發(fā)布[9-10]、智能數(shù)據(jù)分析[11-12]等。相比于基于k-匿名[13]和劃分[14]的隱私保護(hù)方法該模型有效克服了需要事先對(duì)攻擊做出假設(shè)的不足。差分隱私數(shù)據(jù)發(fā)布研究的關(guān)鍵問題在于如何在保證差分隱私的前提下，同時(shí)提高所發(fā)布數(shù)據(jù)的可用性。

現(xiàn)有關(guān)于差分隱私的數(shù)據(jù)發(fā)布方法大多關(guān)注靜態(tài)發(fā)布問題，而現(xiàn)實(shí)應(yīng)用中更多情況下需要發(fā)布方法具有連續(xù)數(shù)據(jù)發(fā)布的能力。然而，經(jīng)研究表明，這些方法無法應(yīng)用于連續(xù)數(shù)據(jù)發(fā)布問題。為此，本文對(duì)差分隱私下的連續(xù)數(shù)據(jù)發(fā)布問題展開研究。例如，某醫(yī)療數(shù)據(jù)庫(kù)中記錄了每個(gè)月的入院病人的信息，其中病人感染HIV的情況為敏感信息。表1展示了其中3個(gè)月的數(shù)據(jù)示例。同時(shí)，出于某研究目的，醫(yī)院將按月統(tǒng)計(jì)并公布入院的HIV病人數(shù)。公布的數(shù)據(jù)形如表2所示，醫(yī)院將當(dāng)前入院并且感染HIV的病人累計(jì)并于當(dāng)月發(fā)布最新數(shù)據(jù)。與數(shù)據(jù)靜態(tài)發(fā)布不同，在醫(yī)院發(fā)布完每個(gè)月的統(tǒng)計(jì)信息后，該數(shù)據(jù)并非不再改變，而是在下個(gè)月將得到更新。更重要的是，在發(fā)布每一次數(shù)據(jù)的過程中，以后需要發(fā)布的數(shù)據(jù)是無法被預(yù)知的。該問題的核心是在滿足差分隱私的條件下，尋找更精確且更高效率的連續(xù)數(shù)據(jù)發(fā)布方法。

Table 1 Medical records表1　醫(yī)學(xué)記錄表

Table 2 Statistics on HIV+ patients表2　HIV+病人數(shù)統(tǒng)計(jì)表

以上連續(xù)發(fā)布問題的一種樸素解決方案[15]是直接在前一個(gè)月發(fā)布的HIV病人加上本月新增的HIV病人數(shù)，然后再添加噪聲使其滿足差分隱私。該方案導(dǎo)致每一次發(fā)布數(shù)據(jù)的噪聲的均方誤差線性累加，最終發(fā)布的數(shù)據(jù)失去可用性。文獻(xiàn)[15]針對(duì)該問題提出了一種基于二叉樹的發(fā)布方法。然而，此方法僅僅引入二叉樹模擬發(fā)布，并未對(duì)精確性提出有效優(yōu)化。為此，本文以提高發(fā)布數(shù)據(jù)的精確性為主要目標(biāo)，將矩陣機(jī)制引入差分隱私連續(xù)數(shù)據(jù)發(fā)布問題中，以期設(shè)計(jì)出高效的基于矩陣機(jī)制的差分隱私連續(xù)數(shù)據(jù)發(fā)布方法，有效滿足大規(guī)模連續(xù)數(shù)據(jù)發(fā)布的要求。

2　相關(guān)工作

在差分隱私的數(shù)據(jù)發(fā)布中，為提高數(shù)據(jù)發(fā)布的精度，Hay[7]和Xiao等人[8]分別提出的基于一致性調(diào)節(jié)的區(qū)間樹方法和小波變換方法實(shí)現(xiàn)了較高精度的數(shù)據(jù)發(fā)布。然而，上述兩種方法只適用于差分隱私下的數(shù)據(jù)靜態(tài)發(fā)布，無法應(yīng)用于差分隱私下的連續(xù)數(shù)據(jù)發(fā)布。Chan等人[15]提出了兩種利用二叉樹結(jié)構(gòu)進(jìn)行連續(xù)數(shù)據(jù)發(fā)布的方法。第一種方法構(gòu)建一棵葉節(jié)點(diǎn)數(shù)量為2m的完全二叉樹，然后利用模擬二叉樹統(tǒng)計(jì)發(fā)布的過程進(jìn)行連續(xù)數(shù)據(jù)發(fā)布。第二種方法是第一種方法的改進(jìn)版本，它試圖通過調(diào)整二叉樹各層節(jié)點(diǎn)的隱私預(yù)算分配來達(dá)到無限發(fā)布的效果。研究表明，雖然第一種方法相比于樸素方法，數(shù)據(jù)發(fā)布的精確性有顯著的提升，然而該方法僅僅引入二叉樹結(jié)構(gòu)來模擬發(fā)布過程，并未做進(jìn)一步改進(jìn)，因此數(shù)據(jù)發(fā)布的精確性仍有較大的提升空間；第二種方法的隱私預(yù)算分配并不合理，導(dǎo)致發(fā)布數(shù)據(jù)的誤差遠(yuǎn)大于第一種方法。

為了解決差分隱私下的線性查詢問題，Li等人[16]提出了基于矩陣機(jī)制的批量查詢方法。其基本思想是通過尋找策略矩陣對(duì)線性查詢進(jìn)行優(yōu)化，進(jìn)而提高發(fā)布數(shù)據(jù)的精確性。然而，該文獻(xiàn)提出的矩陣機(jī)制僅能滿足小規(guī)模數(shù)據(jù)集和查詢負(fù)載的要求。此外，它還很容易產(chǎn)生次優(yōu)化的查詢策略，使得結(jié)果往往并不理想。為此，Yuan等人[17]利用負(fù)載矩陣低秩的性質(zhì)進(jìn)行優(yōu)化，提出了低秩矩陣機(jī)制，在一定程度上改善了原有矩陣機(jī)制的不足，提升了數(shù)據(jù)發(fā)布效率與精確性。然而，該文獻(xiàn)提出的優(yōu)化查詢使用半正定規(guī)劃算法，同樣只能適用小規(guī)模數(shù)據(jù)集和查詢負(fù)載的要求。本文研究的連續(xù)數(shù)據(jù)發(fā)布問題本質(zhì)上也是線性查詢問題，因此擬利用矩陣機(jī)制，結(jié)合連續(xù)數(shù)據(jù)發(fā)布問題本身具有的一些特性，設(shè)計(jì)出精度更高且效率更高的算法，使之具有大規(guī)模連續(xù)數(shù)據(jù)發(fā)布的能力。

3　基礎(chǔ)知識(shí)與問題

3.1差分隱私

Dwork等人[2]首次提出差分隱私保護(hù)模型。該模型保證了在數(shù)據(jù)發(fā)布過程中，無論攻擊者具有何種背景知識(shí)，都無法泄露隱私數(shù)據(jù)。其形式化定義如下：

定義1（ε-差分隱私[2]）設(shè)A表示在查詢Q的基礎(chǔ)上通過某種方式添加隨機(jī)噪聲的隨機(jī)算法。將其分別作用于兄弟數(shù)據(jù)集D和D′時(shí)的概率密度滿足以下條件，則算法A滿足ε-差分隱私。其中O表示可能的輸出集合。

定義2（敏感度）對(duì)數(shù)據(jù)集D和D′進(jìn)行統(tǒng)計(jì)得：Q(D)=(x1,x2,…,xn)T, Q(D′)=(x1′,x2′,…,xn′)T。那么查詢集合Q的敏感度ΔQ滿足以下定義：

本文主要使用1-范數(shù)，即p=1。

文獻(xiàn)[18]提出了拉普拉斯機(jī)制。該機(jī)制通過添加拉普拉斯噪音來實(shí)現(xiàn)差分隱私保護(hù)。為了表示方便，本文用表示滿足分布Laplace(0,1)的n維列向量。

3.2矩陣機(jī)制

矩陣機(jī)制是一種針對(duì)差分隱私下線性查詢問題的優(yōu)化方法。它通過將查詢集Q轉(zhuǎn)換成負(fù)載矩陣W，然后尋找最優(yōu)策略矩陣M實(shí)現(xiàn)差分隱私下線性查詢的優(yōu)化。其中查詢集Q是一組線性查詢的集合，滿足Q={q1,q2,…,qn}。每條線性查詢表示如下：

其中，X=(x1,x2,…,xm)T為數(shù)據(jù)向量；wi為該查詢于分量xi的權(quán)重。負(fù)載矩陣W由每組線性查詢的權(quán)重組成，并滿足：

原始的矩陣機(jī)制[16]通過直接尋找策略矩陣M的方式求解問題，這種做法的效率和優(yōu)化效果都不夠理想。而低秩矩陣機(jī)制[17]則是采用分解負(fù)載矩陣的方法來尋找優(yōu)化策略。該機(jī)制下，將W分解成兩個(gè)矩陣B、M。其中M表示低秩矩陣下的策略矩陣，且滿足W=BM。通過對(duì)中間結(jié)果MX添加噪聲的方式減少誤差。其形式化表示如下：

文獻(xiàn)[17]指出，式（3）的敏感度ΔM與策略矩陣的列范式相等，即ΔM=M1。而低秩矩陣的均方誤差由下式求得：

研究表明，差分隱私下的數(shù)據(jù)連續(xù)發(fā)布問題能夠被轉(zhuǎn)換成基于矩陣機(jī)制的優(yōu)化問題。只需將每一次發(fā)布視為一個(gè)查詢，然后將所有發(fā)布過程視為查詢負(fù)載，并轉(zhuǎn)換成相應(yīng)的矩陣，利用矩陣機(jī)制進(jìn)行求解。

3.3問題提出

考慮一個(gè)隨著時(shí)間增長(zhǎng)，記錄會(huì)不斷產(chǎn)生并被添加其中的記錄流，該記錄流是數(shù)據(jù)發(fā)布的來源。記錄流的每條記錄都有需要保護(hù)的屬性σ，滿足σ∈{0,1}。并假設(shè)記錄集AAi表示第i-1次和第i次發(fā)布之間記錄流中被添加的記錄的集合。由AAi可求出第i次發(fā)布的數(shù)據(jù)增量ai=|{σ|σ∈AAiand σ=1}|。

定義3（連續(xù)數(shù)據(jù)發(fā)布）對(duì)于記錄流，數(shù)據(jù)發(fā)布者隨著記錄流的記錄增長(zhǎng)按照某種規(guī)則多次發(fā)布當(dāng)前記錄流中滿足σ=1的記錄數(shù)的行為即為連續(xù)數(shù)據(jù)發(fā)布。假設(shè)第i次發(fā)布的累計(jì)數(shù)據(jù)為si，那么si滿足：

差分隱私下的連續(xù)數(shù)據(jù)發(fā)布行為即通過某種隱私算法A(*)發(fā)布添加了噪聲的累計(jì)數(shù)據(jù)，從而使數(shù)據(jù)連續(xù)發(fā)布的結(jié)果滿足ε-差分隱私。同時(shí)，在此基礎(chǔ)上，本文還要求所提出的算法能夠精確而且高效地發(fā)布數(shù)據(jù)。

為了避免數(shù)據(jù)連續(xù)發(fā)布的敏感度過高而影響數(shù)據(jù)發(fā)布精度，本文主要考慮了給定次數(shù)下的滿足ε-差分隱私的次數(shù)受限的數(shù)據(jù)連續(xù)發(fā)布算法。

定義4（次數(shù)受限的數(shù)據(jù)連續(xù)發(fā)布算法）如果隱私算法A(*)至多接受并發(fā)布N次滿足ε-差分隱私的統(tǒng)計(jì)數(shù)據(jù)，則稱該算法為次數(shù)受限的數(shù)據(jù)連續(xù)發(fā)布算法。

上述問題能夠轉(zhuǎn)換成線性查詢問題，而矩陣機(jī)制能夠?qū)€性查詢問題進(jìn)行優(yōu)化。為了提出更精確的數(shù)據(jù)連續(xù)發(fā)布算法，本文將這一問題與矩陣機(jī)制相結(jié)合，并在此基礎(chǔ)上尋找快速發(fā)布算法。而且，矩陣機(jī)制是成熟的且經(jīng)過嚴(yán)格檢驗(yàn)的滿足ε-差分隱私[17]的隱私保護(hù)機(jī)制，因此基于矩陣機(jī)制的線性查詢算法只要符合式（3）的形式就保證了該算法滿足ε-差分隱私。

利用矩陣機(jī)制優(yōu)化前，需要將式（5）轉(zhuǎn)換成負(fù)載矩陣W如下：

可以看出，數(shù)據(jù)連續(xù)發(fā)布下的負(fù)載矩陣W為下三角矩陣，且滿足Wij=1,i

根據(jù)矩陣機(jī)制的特征及一般研究過程[16-17]。本文將通過以下步驟對(duì)該問題展開研究：

（1）尋找初始的策略矩陣M，將W分解為矩陣B 和M，使矩陣機(jī)制能夠較為精確地發(fā)布數(shù)據(jù)；

（2）對(duì)策略矩陣M進(jìn)行研究，尋找優(yōu)化策略以優(yōu)化數(shù)據(jù)發(fā)布的精確性；

（3）綜合分析矩陣B、M以及優(yōu)化策略的性質(zhì)，在保證數(shù)據(jù)發(fā)布的精確性得到優(yōu)化的前提下，提出高效的優(yōu)化算法。

4　數(shù)據(jù)連續(xù)發(fā)布算法

4.1利用樹狀數(shù)組構(gòu)造策略矩陣

由于數(shù)據(jù)隨著發(fā)布過程動(dòng)態(tài)產(chǎn)生，未來數(shù)據(jù)無法得知，只能根據(jù)當(dāng)前以及過往的數(shù)據(jù)進(jìn)行優(yōu)化。這一特征反映到矩陣機(jī)制時(shí)，就要求矩陣機(jī)制所應(yīng)用的策略矩陣為下三角矩陣。通過各種數(shù)據(jù)結(jié)構(gòu)的對(duì)比研究，本文發(fā)現(xiàn)樹狀數(shù)組[19]更加適合于構(gòu)造基于矩陣機(jī)制的數(shù)據(jù)連續(xù)發(fā)布方法的策略矩陣。它能夠自然并且快速求解數(shù)列的前k項(xiàng)和，符合連續(xù)數(shù)據(jù)發(fā)布的基本特征。同時(shí)，初步研究表明，將它與差分隱私結(jié)合而提出的隱私保護(hù)模型能夠達(dá)到與基于二叉樹的連續(xù)數(shù)據(jù)發(fā)布方法[15]相當(dāng)?shù)木_性。同時(shí)，深入研究表明，結(jié)合樹狀數(shù)組的差分隱私模型在實(shí)現(xiàn)的巧妙性以及進(jìn)一步優(yōu)化的潛力方面，與后者相比均略勝一籌。

其中，函數(shù)lowbit(x)表示將正整數(shù)x寫成二進(jìn)制形式后，將該二進(jìn)制數(shù)的值為1的最低位的數(shù)置為1，其余位均置為0。例如，當(dāng)x=10時(shí)，其對(duì)應(yīng)的二進(jìn)制數(shù)為(1010)2，從低往高有20位為0，21位為1。那么，lowbit(x)的輸出值就將該位置為1，其他位均置為0，即(0010)2=2。再將其轉(zhuǎn)成十進(jìn)制就得到lowbit(10)=2。

該函數(shù)可以表示如下：

算法1 lowbit(x)

輸入：正整數(shù)x

輸出：x對(duì)應(yīng)的lowbit值

1. p←0,y←1;

2. while xmod2=0

針對(duì)該問題，樹狀數(shù)組提供如下解決方法。該方法計(jì)算了中間統(tǒng)計(jì)量ci，而ci由以下公式求得：

4. wend

5. return y

結(jié)合算法1以及式（7），本文按照樹狀數(shù)組求解中間統(tǒng)計(jì)量的方式構(gòu)造策略矩陣M。

算法2求解策略矩陣M

輸入：發(fā)布次數(shù)N

輸出：策略矩陣M

1. M←ON×N; //初始化為零矩陣

2. for p=1 to N do

3. pt←p ;

4. while pt

5.Mpt,p←1; //更新矩陣元素

6.pt←pt+lowbit(pt) ;

7. wend

8. end for

9. return M

下面，需要進(jìn)一步討論矩陣B的求解。由W=BM以及MN的可逆性可得，B=WNMN-1，因此只需根據(jù)樹狀數(shù)組的性質(zhì)就能夠快速地求解B。而樹狀數(shù)組的求和操作按照以下公式進(jìn)行求解：

算法3求解矩陣B

輸入：發(fā)布次數(shù)N

輸出：矩陣B

1. B←ON×N; //初始化為零矩陣

2. for p=1 to N do

3. pt←p ;

4. while pt>0

5.Bpt,p←1; //更新矩陣元素

6.pt←pt-lowbit(pt) ;

7. wend

8. end for

9. return B

上述算法結(jié)合低秩矩陣的表達(dá)式，即可得到基于樹狀數(shù)組的數(shù)據(jù)連續(xù)發(fā)布的表達(dá)式：

接下來，本文將分析該策略矩陣所產(chǎn)生的均方誤差的情況。關(guān)于MN和B有如下兩個(gè)相關(guān)定理。

定理2構(gòu)造矩陣B的第p行的迭代次數(shù)為將p表示為二進(jìn)制(p)2時(shí)，(p)2中包含的1的個(gè)數(shù)。

證明根據(jù)算法3的步驟6有操作pt=ptlowbit(pt)，該操作的結(jié)果是將(pt)2中值為1的最低位置為0。而由步驟3有pt由p進(jìn)行初始化。說明(p)2中包含多少個(gè)1，迭代就進(jìn)行了多少次?！?/p>

由式（4）推出該策略矩陣所產(chǎn)生的均方誤差為：

同時(shí)，結(jié)合定理2可知，B的每一行至多有O(lg N)個(gè)元素為1，其余皆為0。因此，B中元素為1的個(gè)數(shù)為O(Nlg N)。即trace(BTB)的數(shù)值復(fù)雜度也為O(Nlg N)。又由定理1可知，MN的列范數(shù)?lb N ? +1，其復(fù)雜度為O(lg N)。因而，根據(jù)式（4）可以求得總體的均方誤差為O(Nlg3N)。而對(duì)于每條查詢的均方誤差則為O(lg3N)。

綜上所述，由樹狀數(shù)組構(gòu)造的策略矩陣滿足低敏感性以及均方誤差復(fù)雜度低的特點(diǎn)，初步具備了在差分隱私下較為精確地進(jìn)行連續(xù)數(shù)據(jù)發(fā)布的能力。然而，僅僅利用樹狀數(shù)組構(gòu)造的策略矩陣并不能達(dá)到本文的精確性要求。接下來，本文將在此基礎(chǔ)上尋找更精確的數(shù)據(jù)發(fā)布算法。

一般而言，可以通過發(fā)布數(shù)據(jù)的一致性調(diào)節(jié)[7]和策略矩陣的權(quán)重系數(shù)調(diào)節(jié)等方法提高數(shù)據(jù)發(fā)布的精確性。然而，研究表明該問題已經(jīng)滿足線性一致性，具體分析如下。

定義5（線性一致性）對(duì)于負(fù)載矩陣W，記未加噪的查詢結(jié)果為Y=WQ(D)，通過低秩矩陣機(jī)制獲得的查詢結(jié)果為Y′=A(W,D)。A(W,D)滿足線性一致性當(dāng)且僅當(dāng)對(duì)于任意可以用Y線性表示的統(tǒng)計(jì)量z，對(duì)任意可以表示成z=vY的行向量v都有vY′為定值。同時(shí)，線性一致性滿足定理3。

定理3當(dāng)式（3）中的矩陣M為行滿秩矩陣時(shí)，低秩矩陣機(jī)制滿足線性一致性。

證明當(dāng)矩陣L為行滿秩矩陣時(shí)，求得其右逆矩陣M+=MT(MMT)-1，滿足M×M+=I。

由于W=BM，則B=WM+。

任取統(tǒng)計(jì)查詢z，有多個(gè)vi滿足z=viWX（其中vi之間互不相等）。

將其代入式（3）中，可得統(tǒng)計(jì)后的結(jié)果，令zi′表示由vi求得的查詢結(jié)果：

經(jīng)過化簡(jiǎn)可以看出，zi′是與vi無關(guān)的噪聲統(tǒng)計(jì)量。因此，可以得出zi′的值是相等的。□

MN為可逆矩陣，結(jié)合定理3，可得出推論：由樹狀數(shù)組構(gòu)造基于矩陣機(jī)制的數(shù)據(jù)連續(xù)發(fā)布方法滿足線性一致性。因此無法從線性一致性的角度提高數(shù)據(jù)發(fā)布的一致性。4.2節(jié)將對(duì)策略矩陣的權(quán)重系數(shù)調(diào)節(jié)問題進(jìn)行研究。

4.2利用對(duì)角矩陣提高精確性

上文分析了差分隱私下的連續(xù)數(shù)據(jù)發(fā)布的性質(zhì)，并通過樹狀數(shù)組構(gòu)造出矩陣機(jī)制的策略矩陣。而根據(jù)3.3節(jié)所描述的步驟，本文將在此基礎(chǔ)上進(jìn)行優(yōu)化。進(jìn)一步研究矩陣MN，可發(fā)現(xiàn)該矩陣未飽和。以M3為例，表示如下：

式（10）即為添加系數(shù)對(duì)角陣后的隱私保護(hù)機(jī)制。當(dāng)ΣN=IN時(shí)，該公式與式（9）等價(jià)。對(duì)應(yīng)的均方誤差公式如下所示：

其中，B(:,i)表示矩陣B的第i列。

由分析可知，式（12）是一個(gè)線性約束下的凸優(yōu)化問題。針對(duì)該問題，可直接采用SQP（sequential guadratic programming）方法[20]求得最優(yōu)解。然而SQP方法是一種時(shí)間復(fù)雜度很高的算法，無法滿足大規(guī)模數(shù)據(jù)的要求。實(shí)驗(yàn)表明，對(duì)于一般計(jì)算機(jī)，該方法最多只能滿足N小于1 000的求解規(guī)模。因此，需要進(jìn)一步研究更快速的方法求得式（12）的最優(yōu)解。

4.3快速求解最小誤差

由于SQP方法求解復(fù)雜度很高，對(duì)于大規(guī)模數(shù)據(jù)，對(duì)角陣ΣN求解是無法完成的。因此，有必要對(duì)ΣN的求解進(jìn)一步優(yōu)化，并提出高效的解決方案。利用MN和B之間的特殊性質(zhì)，本文提出了一種高效的求解最小誤差的算法——快速對(duì)角陣優(yōu)化算法（fast diagonal matrix optimization algorithm, FDA）。當(dāng)N=2m-1時(shí)，該算法可以在O(lg N)的時(shí)間復(fù)雜度下求解ΣN的任意系數(shù)值λi。該算法與未使用Σ前的方法有相當(dāng)?shù)那蠼庑剩虼怂ＷC了在不影響算法復(fù)雜度的前提下提高隱私數(shù)據(jù)發(fā)布的精確性。該算法是基于以下定理提出的。

證明對(duì)于矩陣B2m-1進(jìn)一步分析可發(fā)現(xiàn)它滿足以下特性：令a<2m-1，b=2m-1+a。將其寫成二進(jìn)制形式可以描述為a=(xm-2xm-3…x0)2和b=(1xm-2xm-3…x0)2。根據(jù)算法2，不難發(fā)現(xiàn)B2m-1(a,t)= 1(t>0)當(dāng)且僅當(dāng)B2m-1(b,2m-1+t)=1。同時(shí)，由于b的2m-1位為1，因此B2m-1(b,2m-1)=1

通過以上分析，可將B2m-1寫成如下形式：

通過式（14）得：

下面將分析M2m-1與M2m-1-1之間的關(guān)系。

根據(jù)算法4，有M2m-1(t,a)=1(1≤t≤2m-1-1)當(dāng)且僅當(dāng)M2m-1(2m-1+t,b)=1。滿足?1≤t≤2m-1-1，M2m-1(2m-1,t)=1。

因此，將M2m-1與M2m-1-1寫成如下遞推關(guān)系：

令RN表示ΣN求對(duì)角線元素組成的列向量，RN=(λ1λ2…λN)T。當(dāng)N=2m-1時(shí)，可將R2m-1拆分成3個(gè)部分，即：

對(duì)于式（12），亦可將其拆分為以下3個(gè)子部分：

令f(i )(*)分別表示這3個(gè)子部分，從而將上述表達(dá)式轉(zhuǎn)換為3個(gè)子部分的和：

由式（17）可將限制條件分解成以下3個(gè)子條件：

通過以上3個(gè)子限制條件，可知子條件①受限于子條件②中λ2m-1的取值。因此，先假設(shè)λ2m-1

式（12）取最優(yōu)時(shí)，子部分①滿足：

由于滿足：

通過以上分析，可將第①部分的子問題描述如下：

綜上所述，式（13）成立?！?/p>

證明首先對(duì)h(α)進(jìn)行求導(dǎo)得：

因此，從以上結(jié)論可以得出以下關(guān)于均方誤差errm的遞推公式：

由該結(jié)果進(jìn)一步推導(dǎo)出優(yōu)化后均方誤差，如下：

而根據(jù)αi(1≤i≤m)即可求得Σm中所有λk的值。具體計(jì)算步驟如算法4所示。

算法4求解最優(yōu)對(duì)角陣系數(shù)λk=coef(k,m)

輸入：系數(shù)的標(biāo)號(hào)k，數(shù)據(jù)規(guī)模m

輸出：λk的值

1.λk←1; //初始化λk

2. kt←k,t←m;div←2m-1; // div表示子問題的分割中點(diǎn)

3. while div≠kt

4. if kt