矩陣機(jī)制下差分隱私數(shù)據(jù)發(fā)布方法的誤差分析*

吳英杰，陳靖麟，蔡劍平，王一蕾

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

1 引言

在現(xiàn)實(shí)生活中，由于數(shù)據(jù)統(tǒng)計(jì)和科學(xué)研究的需要，許多研究機(jī)構(gòu)或組織都會(huì)對(duì)外發(fā)布數(shù)據(jù)。如何保證所發(fā)布的數(shù)據(jù)既是可用的，又不會(huì)泄漏數(shù)據(jù)中所包含的個(gè)體的隱私信息，已成為當(dāng)前數(shù)據(jù)挖掘與信息共享領(lǐng)域一個(gè)十分熱門的研究課題。針對(duì)此類問(wèn)題，國(guó)際上眾多研究人員對(duì)隱私保護(hù)數(shù)據(jù)發(fā)布進(jìn)行了深入研究，提出了不少隱私保護(hù)數(shù)據(jù)發(fā)布模型。然而，現(xiàn)有的隱私保護(hù)模型大多以匿名為基礎(chǔ)，這些模型均需要特殊的攻擊假設(shè)和一定的背景知識(shí)，因此具有很大的局限性。為此，Dwork等人[1-3]提出了差分隱私模型，該模型適用于各種背景條件，并且具有嚴(yán)格的數(shù)學(xué)證明，得到了廣泛的認(rèn)可?；谠撾[私保護(hù)模型，學(xué)者們開(kāi)展了很多相關(guān)研究工作，內(nèi)容涉及直方圖發(fā)布[4-8]、連續(xù)數(shù)據(jù)發(fā)布[9]、空間劃分發(fā)布[10-11]、智能數(shù)據(jù)分析[12-14]等。

差分隱私算法通過(guò)對(duì)數(shù)據(jù)添加隨機(jī)噪聲來(lái)實(shí)現(xiàn)隱私保護(hù)，因此在保護(hù)隱私的同時(shí)必然會(huì)產(chǎn)生相應(yīng)的數(shù)據(jù)誤差。算法的誤差是評(píng)價(jià)算法的重要指標(biāo)，因此對(duì)于差分隱私算法來(lái)說(shuō)，計(jì)算均方誤差是該算法最為基本也是最為重要的工作。然而，現(xiàn)有的大部分差分隱私算法對(duì)均方誤差的估計(jì)，往往是基于實(shí)驗(yàn)或者采用先統(tǒng)計(jì)各變量的均方誤差再累加的方法。該做法使得難以對(duì)算法的均方誤差進(jìn)行定量分析，或者使得分析過(guò)程極為復(fù)雜，不能有效、簡(jiǎn)潔地讓讀者了解該算法的精確性，給讀者在算法的理解上造成一定的困擾。

近年來(lái)，許多研究學(xué)者提出了多種差分隱私數(shù)據(jù)發(fā)布算法，其中多數(shù)集中在兩方面：一是以k-叉樹(shù)的形式對(duì)數(shù)據(jù)進(jìn)行處理，然后采用一致性約束的分層結(jié)構(gòu)差分隱私算法；二是利用策略矩陣進(jìn)行變換，加噪后通過(guò)還原矩陣進(jìn)行還原的基于矩陣機(jī)制的差分隱私算法。其中，Qardaji等人[15]對(duì)以Boost為代表的分層結(jié)構(gòu)差分隱私算法的均方誤差進(jìn)行了有效的理論分析，并提出相應(yīng)的求解方法。而以Prievlet算法為代表的基于矩陣機(jī)制的差分隱私算法尚缺乏相應(yīng)的理論分析，本文通過(guò)研究現(xiàn)有的差分隱私數(shù)據(jù)發(fā)布算法對(duì)均方誤差的計(jì)算，并結(jié)合矩陣運(yùn)算的相關(guān)理論，提出基于矩陣運(yùn)算的均方誤差計(jì)算方法。本文方法能夠?qū)⒒诰仃嚈C(jī)制的差分隱私算法的均方誤差進(jìn)行一般化處理，是一種具有普遍性的方法，能夠簡(jiǎn)潔有效地求出基于矩陣機(jī)制的差分隱私算法的均方誤差。本文以Prievlet算法[4]為例進(jìn)行詳細(xì)的分析、推導(dǎo)，其他算法可通過(guò)類似推導(dǎo)完成。

本文的主要貢獻(xiàn)如下：

（1）基于矩陣運(yùn)算以及協(xié)方差的計(jì)算，從理論上分析任意固定查詢區(qū)間下Prievlet差分隱私算法的均方誤差，得出求解公式。

（2）在第一步的基礎(chǔ)上，求解Prievlet算法隨機(jī)查詢區(qū)間下的均方誤差，推導(dǎo)出平均均方誤差的公式，得出Prievlet算法誤差的漸進(jìn)階。

（3）提出精確度指標(biāo)，對(duì)其進(jìn)行推導(dǎo)、說(shuō)明，并對(duì)一些算法進(jìn)行求解，該指標(biāo)能夠簡(jiǎn)潔有效地說(shuō)明差分隱私算法的精確性。

（4）通過(guò)實(shí)驗(yàn)驗(yàn)證文中所求得的均方誤差公式的正確性。

2 基礎(chǔ)知識(shí)與問(wèn)題提出

2.1 基礎(chǔ)知識(shí)

差分隱私保護(hù)模型是一種強(qiáng)健的隱私保護(hù)框架，由Dwork等人[1]首次提出。差分隱私保護(hù)模型在數(shù)據(jù)發(fā)布過(guò)程中，不論攻擊者具備何種背景知識(shí)，都能保證隱私數(shù)據(jù)不泄露。

定義1（ε-差分隱私[1]）設(shè)有一對(duì)兄弟數(shù)據(jù)集D1和D2（當(dāng)且僅當(dāng)D1和D2中的記錄只有一條不同），若一個(gè)發(fā)布算法A在兄弟數(shù)據(jù)集D1和D2上的所有可能的輸出滿足以下條件，則稱算法A滿足ε-差分隱私。

定義2（ε-敏感度）統(tǒng)計(jì)某數(shù)據(jù)庫(kù)中的數(shù)據(jù)集D1和D2分別得到兩組由列向量表示的結(jié)果：Q(D1)=(x1,x2,…,xn)T，Q(D2)=(x1′,x2′,…,xn′)T。那么查詢集合Q的敏感度ΔQ滿足以下定義：

在差分隱私中，更為經(jīng)常使用的范數(shù)為1-范數(shù)，即p=1。文中的敏感度如無(wú)特殊說(shuō)明均以1-范數(shù)為度量。敏感度表明了當(dāng)D僅改變一條記錄的情況下對(duì)統(tǒng)計(jì)結(jié)果Q(D)的影響情況。一般而言敏感度越大，Q(D)受影響的程度越強(qiáng)，需要添加的噪聲也越強(qiáng)。

2.2 問(wèn)題提出

差分隱私數(shù)據(jù)發(fā)布算法經(jīng)常需要將原數(shù)據(jù)進(jìn)行線性變換后再進(jìn)行發(fā)布，此時(shí)計(jì)算出每個(gè)變量的均方誤差再進(jìn)行累和并不能反映該算法的均方誤差?？紤]如下情景：某差分隱私算法A運(yùn)行后輸出兩個(gè)隨機(jī)變量x1、x2，并計(jì)算它們的均方誤差D(x1)、D(x2)用于評(píng)價(jià)算法A。假如算法B在算法A的基礎(chǔ)上實(shí)現(xiàn)，其需要輸出z，滿足z=x1+x2。根據(jù)概率統(tǒng)計(jì)的原理可知，新算法輸出變量z的均方誤差為：

而由于協(xié)方差的存在，僅憑D(x1)、D(x2)是無(wú)法計(jì)算出D(z)的。該例子說(shuō)明完整的均方誤差分析應(yīng)該包含隨機(jī)變量之間的協(xié)方差。而在概率統(tǒng)計(jì)領(lǐng)域，人們常常使用協(xié)方差矩陣來(lái)表示一組隨機(jī)變量間的協(xié)方差（主對(duì)角線上的值表示均方誤差）。設(shè)X=(x1,x2,…,xn)T為一個(gè)隨機(jī)變量，則它的協(xié)方差矩陣為：

以隨機(jī)向量L?n為例，它的每一個(gè)分量均是一個(gè)滿足Lap(1)（Laplace簡(jiǎn)稱Lap）分布的獨(dú)立隨機(jī)量，顯然隨機(jī)量間的協(xié)方差為0。而Lap(1)分布的均方誤差為2，則 L?n的協(xié)方差矩陣為：

然而，僅僅使用協(xié)方差矩陣進(jìn)行誤差分析遠(yuǎn)遠(yuǎn)無(wú)法滿足大多數(shù)應(yīng)用的需要。絕大多數(shù)算法涉及了隨機(jī)向量間的線性變換。為此，本文在誤差分析時(shí)將使用以下定理。

定理1[16]若隨機(jī)向量Z與X之間存在線性關(guān)系Z=AX（A為矩陣），且已知X的協(xié)方差矩陣表示為RX，則Z的協(xié)方差矩陣為RZ=ARXAT。

由協(xié)方差矩陣的性質(zhì)可知，其對(duì)角線元素為各隨機(jī)變量的均方誤差，因此人們通常利用函數(shù)trace(*)求解最終的均方誤差。由于忽略了協(xié)方差，該方法得出的均方誤差不能精確地表示算法的誤差。

3 Prievlet算法的誤差分析

3.1 Prievlet差分隱私算法

Prievlet差分隱私算法[4]通過(guò)對(duì)數(shù)據(jù)進(jìn)行前置處理來(lái)提高數(shù)據(jù)發(fā)布的精度。這種方法受到哈爾小波變換的啟發(fā)，使用哈爾小波變換矩陣先對(duì)原始數(shù)據(jù)進(jìn)行壓縮，再對(duì)壓縮后的數(shù)據(jù)添加拉普拉斯噪聲使其滿足差分隱私。然后，將原始數(shù)據(jù)與壓縮數(shù)據(jù)組合在一起構(gòu)建一棵形如圖1具有8個(gè)節(jié)點(diǎn)的Prievlet二叉樹(shù)，其中葉子節(jié)點(diǎn)為原始數(shù)據(jù)，自下而上，對(duì)于每個(gè)非葉子節(jié)點(diǎn)，其權(quán)值為左子樹(shù)葉子節(jié)點(diǎn)的權(quán)值之和減去右子樹(shù)葉子節(jié)點(diǎn)的權(quán)值之和。構(gòu)造過(guò)程見(jiàn)算法1。

Fig.1 Prievlet-two-fork-tree with 8 nodes圖1 8個(gè)節(jié)點(diǎn)Prievlet二叉樹(shù)

算法1Prievlet差分隱私算法

輸入：原始數(shù)據(jù)向量vi(1≤i≤2h)，隱私預(yù)算ε。

1.輸入初始數(shù)據(jù)。

2.對(duì)數(shù)據(jù)進(jìn)行壓縮轉(zhuǎn)換。每個(gè)非葉子節(jié)點(diǎn)的值等于左子樹(shù)葉子節(jié)點(diǎn)的權(quán)值之和減去右子樹(shù)葉子節(jié)點(diǎn)的權(quán)值之和，具體公式如下所示：

3.敏感度Δ=h+1，對(duì)所有ck添加拉普拉斯噪聲得到滿足差分隱私的壓縮系數(shù)

由算法1所得到的壓縮系數(shù)，可通過(guò)式（4）還原，求出所有滿足差分隱私算法的輸出數(shù)據(jù)：

Prievlet算法適用于區(qū)間查詢，其查詢均方誤差復(fù)雜度為O(lb3n)，n=2h。相比于其他二叉樹(shù)方法，使用小波變換方法壓縮的數(shù)據(jù)，不存在不一致性問(wèn)題，無(wú)需采用任何后置處理方法來(lái)提高算法的精確性。

3.2 分析Prievlet算法的均方誤差

通過(guò)研究Prievlet算法可以發(fā)現(xiàn)，數(shù)據(jù)經(jīng)過(guò)Prievlet算法的變換是線性的，這意味著可以用一種基于矩陣的運(yùn)算來(lái)表示Prievlet算法的變換過(guò)程。因此，可以根據(jù)Prievlet算法的變化過(guò)程構(gòu)造相對(duì)應(yīng)的策略矩陣，從而對(duì)Prievlet算法的均方誤差進(jìn)行有效的分析。

首先，需將Prievlet算法的變換過(guò)程用矩陣進(jìn)行表示。根據(jù)算法1，由ck的計(jì)算式（3），可以得到Prievlet算法的策略矩陣，同時(shí)根據(jù)式（4）可以得到Prievlet算法的還原矩陣。例如，當(dāng)數(shù)據(jù)量的大小為4時(shí)，根據(jù)以上方法，可以得到對(duì)應(yīng)的策略矩陣和還原矩陣。

Prievlet算法的策略矩陣：

Prievlet算法的還原矩陣：

其中數(shù)據(jù)通過(guò)策略矩陣變換可得到壓縮系數(shù)，然后加噪后的壓縮數(shù)據(jù)通過(guò)還原矩陣可得到加噪后的數(shù)據(jù)。

根據(jù)文獻(xiàn)[4]可知，Prievlet算法是在經(jīng)過(guò)策略矩陣變換后的系數(shù)上添加噪聲，因此對(duì)策略矩陣不需要進(jìn)行分析，而對(duì)于Prievlet算法的還原矩陣B，直接對(duì)加噪后的系數(shù)進(jìn)行線性組合來(lái)完成還原，是均方誤差的主要來(lái)源，接下來(lái)將對(duì)其進(jìn)行詳細(xì)的分析。矩陣B的構(gòu)建可根據(jù)式（4）得出，圖2是還原矩陣中單行（單個(gè)數(shù)據(jù)）的求解流程圖，整個(gè)還原矩陣B的求解見(jiàn)算法2。

Fig.2 Flow chart to solve the p line in restore matrixB圖2 還原矩陣B第p行求解流程圖

算法2求解Prievlet的還原矩陣

通過(guò)算法2得到還原矩陣后，結(jié)合定理1，可以得到通過(guò)Prievlet算法變換后的數(shù)據(jù)的協(xié)方差矩陣：

由矩陣的乘法可知Σij為矩陣B的第i行和第 j行進(jìn)行點(diǎn)乘的結(jié)果，且滿足如下定理。

定理2由矩陣B的第i行和第 j行點(diǎn)乘所得到的Σij滿足如下公式：

式中，k為節(jié)點(diǎn)i與節(jié)點(diǎn)j的最近公共祖先的高度（見(jiàn)圖1）。可由該公式計(jì)算求得：其中⊕表示二進(jìn)制表示下的按位異或運(yùn)算。

證明當(dāng)i=j時(shí)，由算法2可得，恒成立。然后t從h到1循環(huán)，每次循環(huán)都將一個(gè)由0置為因此，除Bi,1以外，B的第i行存在且僅存在一個(gè)元素從而：

則Σij計(jì)算如下：

為了便于計(jì)算，本文對(duì)式（6）進(jìn)一步化簡(jiǎn)，得到與之等價(jià)的式（7）：

又令Φk表示兩節(jié)點(diǎn)最小公共祖先層數(shù)為k時(shí)的協(xié)方差，則Φk滿足如下遞推關(guān)系：

分析完P(guān)rievlet算法的均方誤差，下面對(duì)Prievlet算法的均方誤差進(jìn)行求解。

3.3 求解Prievlet算法的均方誤差

求解Prievlet算法的均方誤差將分兩步進(jìn)行：首先對(duì)任意固定查詢區(qū)間的均方誤差進(jìn)行求解；然后求解隨機(jī)查詢區(qū)間的均方誤差。

3.3.1 求解任意固定查詢區(qū)間的均方誤差

將經(jīng)過(guò)Prievelet算法變換后的數(shù)據(jù)用向量的形式表示成則可以將查詢區(qū)間[l,r]表示成向量，那么查詢結(jié)果為

根據(jù)定理1和式（5），得到這個(gè)查詢的均方誤差為：

式（9）需要進(jìn)行矩陣乘法運(yùn)算，該運(yùn)算的復(fù)雜度較高。而從2.1節(jié)的分析結(jié)果可以發(fā)現(xiàn)協(xié)方差矩陣存在規(guī)律，可以由定理2以及式（6）計(jì)算得出協(xié)方差矩陣中的任意一個(gè)值。利用上述特點(diǎn)，本文提出一個(gè)可以快速計(jì)算Prievlet算法區(qū)間查詢的均方誤差的算法。

由定理2可以得出，對(duì)于節(jié)點(diǎn)i與節(jié)點(diǎn) j，它們的均方誤差為這意味著每對(duì)節(jié)點(diǎn)的均方誤差只與最近祖先高度有關(guān)。那么對(duì)每個(gè)非葉子節(jié)點(diǎn)進(jìn)行考慮，只需計(jì)算出以該節(jié)點(diǎn)為最近公共祖先葉子節(jié)點(diǎn)的對(duì)數(shù)，再乘上對(duì)應(yīng)的協(xié)方差即可。

以圖3為例，共有8個(gè)葉子節(jié)點(diǎn)，查詢區(qū)間為[3,7]。圖中條紋標(biāo)注節(jié)點(diǎn)是查詢區(qū)間覆蓋了該節(jié)點(diǎn)的部分區(qū)間，而用灰色表示的點(diǎn)是整個(gè)區(qū)間都被查詢區(qū)間覆蓋。例如：節(jié)點(diǎn)c3所表示的是[4,8]這個(gè)區(qū)間，查詢區(qū)間[3,7]只覆蓋了其中一部分；而節(jié)點(diǎn)c5則完全被查詢區(qū)間[3,7]覆蓋。

Fig.3 Example of[3,7]query of Prievlet algorithm圖3 Prievlet算法查詢[3,7]的示例圖

對(duì)于灰色的節(jié)點(diǎn)，是被查詢區(qū)間完全覆蓋的，那么以該節(jié)點(diǎn)為最近公共祖先的節(jié)點(diǎn)對(duì)數(shù)可以由左右子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)的乘積得到。根據(jù)這個(gè)二叉樹(shù)的性質(zhì)可以知道，如果該節(jié)點(diǎn)在第k層，那么其覆蓋范圍是2k，左右子樹(shù)葉子節(jié)點(diǎn)個(gè)數(shù)都為2k-1。因此，如果一個(gè)節(jié)點(diǎn)是第k層節(jié)點(diǎn)，那么以該節(jié)點(diǎn)為最近公共祖先的葉子節(jié)點(diǎn)對(duì)數(shù)為4k-1。然后只需再計(jì)算出第k層灰色節(jié)點(diǎn)的個(gè)數(shù)即可，可由以下公式計(jì)算：

圖3中的條紋節(jié)點(diǎn)是查詢邊界上的節(jié)點(diǎn)，顯而易見(jiàn)，這種節(jié)點(diǎn)在每一層最多會(huì)出現(xiàn)2個(gè)，因此可以直接枚舉進(jìn)行求解。假設(shè)節(jié)點(diǎn)cx是第k層的節(jié)點(diǎn)，覆蓋區(qū)間為[lx,rx]，可以得出以節(jié)點(diǎn)cx為最近公共祖先的葉子節(jié)點(diǎn)對(duì)數(shù)為|P|×|R|，其中

除了考慮協(xié)方差之外，還需要對(duì)各個(gè)變量各自的均方誤差進(jìn)行考慮，即Σ矩陣中的對(duì)角線元素Σii。由定理2可以發(fā)現(xiàn)，這些均方誤差都是固定的，只需將該均方誤差乘上區(qū)間的長(zhǎng)度r-l+1即可得出。

根據(jù)上述分析，本文提出了一種求解Prievlet差分隱私算法任意區(qū)間查詢的均方誤差（算法3）。在Prievlet算法中，敏感度和隱私預(yù)算ε都是一個(gè)固定的值，這兩個(gè)參數(shù)只會(huì)影響所需添加的噪聲大小，而對(duì)于采取相同噪聲機(jī)制的差分隱私算法而言，不會(huì)產(chǎn)生影響，為了方便計(jì)算分析，暫時(shí)不予考慮，只考慮均方誤差的系數(shù)。

算法3求解任意固定區(qū)間查詢的均方誤差系數(shù)

由算法3得出的Rerr，可以得出查詢區(qū)間[l,r]的均方誤差，如下所示：

分析算法3可以發(fā)現(xiàn)，其時(shí)間復(fù)雜度為O(h)，即O(lbN)，只需遍歷一次1到h就能得出答案。因此該算法能夠完成海量數(shù)據(jù)量下的均方誤差的求解任務(wù)。

3.3.2 求解隨機(jī)查詢區(qū)間的均方誤差

算法3可以快速有效地求得任意固定查詢區(qū)間下Prievlet算法的均方誤差，但固定區(qū)間查詢的均方誤差不能體現(xiàn)該算法平均情況下的均方誤差，因此下文將在算法3的基礎(chǔ)上對(duì)隨機(jī)查詢區(qū)間下Prievlet算法的均方誤差進(jìn)行求解，得出該算法平均情況下的均方誤差。

觀察式（9），對(duì)于所有查詢來(lái)說(shuō)，Prievlet算法添加的噪聲是一樣的，其不同之處是ITΣI的值不同，本文稱這部分為均方誤差系數(shù)。接下來(lái)將對(duì)均方誤差系數(shù)進(jìn)行重點(diǎn)分析。

觀察均方誤差系數(shù)ITΣI可以發(fā)現(xiàn)，該計(jì)算過(guò)程等價(jià)于取出Σ矩陣中的一個(gè)子矩陣，從第l行到r行，l列到r列，然后將子矩陣中所有元素相加的結(jié)果。

以下是一個(gè)在8個(gè)節(jié)點(diǎn)下，查詢區(qū)間為[3，7]的例子，其中矩陣是該查詢規(guī)模下的協(xié)方差矩陣，虛線框內(nèi)是被取出來(lái)的子矩陣。

接下來(lái)，對(duì)Prievlet算法的平均均方誤差進(jìn)行求解。在平均情況下，可以認(rèn)為對(duì)于所有的查詢區(qū)間[l,r],l≤n,l≤r≤n出現(xiàn)的概率都是均等的?？蓪⑸衔闹蠭TΣI的求解方式進(jìn)行變換，考慮對(duì)于每個(gè)Σij會(huì)被多少個(gè)查詢區(qū)間所用到。計(jì)算公式如下所示：

若只考慮i≤j的情況，式（12）可以進(jìn)一步化簡(jiǎn)為 cntΣij=i×(2h-j+1)。

i＞j時(shí)，可以利用Σ矩陣的對(duì)稱性進(jìn)行求解，即cntΣij=cntΣji。

從上文的分析可以看出，協(xié)方差矩陣Σ中有很多相等的值，因此可按不同的值進(jìn)行分類討論，以提高求解效率。從定理2中可以看出求解總體的均方誤差可以分為兩步。

首先求解兩個(gè)不同節(jié)點(diǎn)的均方誤差系數(shù)之和。根據(jù)兩節(jié)點(diǎn)的最近公共祖先的高度劃分，假設(shè)高度為k，那么Σij滿足Σij=Φk。然后用式（13）計(jì)算這些值被每個(gè)區(qū)間計(jì)算到的總和SΦk。如下所示：

式（13）的計(jì)算過(guò)程見(jiàn)附錄。

然后求解每個(gè)查詢區(qū)間的各個(gè)元素的獨(dú)立均方誤差總和SD。計(jì)算過(guò)程如下：

最后，將上述兩個(gè)步驟的計(jì)算結(jié)果結(jié)合，得到區(qū)間查詢的均方誤差系數(shù)總和：

式（15）計(jì)算過(guò)程見(jiàn)附錄。

根據(jù)上文方法求出查詢區(qū)間的均方誤差系數(shù)總和之后，只需將其除以區(qū)間的總個(gè)數(shù)即可得到Prievlet算法在進(jìn)行區(qū)間查詢時(shí)均方誤差系數(shù)的平均情況。計(jì)算過(guò)程如下：

h→∞時(shí)式（16）的極限為：

實(shí)驗(yàn)表明，當(dāng) h＞10時(shí)，式（16）與式（17）計(jì)算結(jié)果的差別可以忽略不計(jì)。

最后只需要將根據(jù)式（16）得到的均方誤差系數(shù)乘上Prievlet算法的均方誤差，就可以得到平均情況下的均方誤差：

上述兩部分，基本的噪聲誤差不可變，取決于用戶想要保護(hù)隱私的程度。而誤差系數(shù)主要由所采用的算法和數(shù)據(jù)規(guī)模確定，其中數(shù)據(jù)規(guī)模取決于應(yīng)用的需要，不隨所采用算法的改變而改變。為反映差分隱私算法的性能，下文將對(duì)誤差系數(shù)進(jìn)行處理，將與算法性能本身無(wú)關(guān)的部分去掉，提出一種直觀的、能夠反映算法性能的評(píng)價(jià)指標(biāo)。

4 O(lb3N)精確度指標(biāo)

在現(xiàn)有的差分隱私數(shù)據(jù)發(fā)布領(lǐng)域，目前所有算法的均方誤差漸進(jìn)階最低能達(dá)到O(lb3N)[15]。因此，本文將針對(duì)此類算法提出差分隱私O(lb3N)精確度指標(biāo)，具體定義如下：

定義3（O(lb3N)精確度指標(biāo)）已知差分隱私算法Α與該算法所處理的數(shù)據(jù)規(guī)模為N。令表示在該數(shù)據(jù)規(guī)模下算法Α產(chǎn)生的平均均方誤差系數(shù)函數(shù)，則該算法O(lb3N)精確度指標(biāo)k表示為：

以Prievlet算法為例，O(lb3N)精確度指標(biāo)k計(jì)算如下：

因此，隨機(jī)區(qū)間查詢下的Prievlet算法的O(lb3N)精確度指標(biāo)為6。

與傳統(tǒng)的描述均方誤差復(fù)雜度的方法相比，上文提出的精確度指標(biāo)能更加形象地表示差分隱私算法的性能。一般而言，精確度指標(biāo)相同的算法，精確度方面性能相近；而對(duì)于精確度指標(biāo)不同的算法，隨著數(shù)據(jù)規(guī)模的增大，精確度指標(biāo)越低的算法，誤差越大。因此，該指標(biāo)能夠準(zhǔn)確地反映差分隱私算法的精確性。

另一方面，研究表明，絕大多數(shù)算法的O(lb3N)精確度指標(biāo)均為正數(shù)，這使得結(jié)果更加直觀，能夠簡(jiǎn)潔地反映差分隱私算法的精確性，便于人們對(duì)算法性能的研究和比較分析。經(jīng)過(guò)理論分析，常見(jiàn)的3種差分隱私算法，樸素二叉樹(shù)、Boost、Prievlet的 O(lb3N)精確度指標(biāo)分別為1、6、6。其中關(guān)于樸素二叉樹(shù)和Boost算法的O(lb3N)精確度指標(biāo)的前置分析計(jì)算過(guò)程在文獻(xiàn)[15]中有詳細(xì)的分析，只需將均方誤差按本文方法進(jìn)一步推導(dǎo)即可得出，這里不再贅述；而Prievlet算法的O(lb3N)精確度指標(biāo)已于前文中得出。

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

本文將通過(guò)實(shí)驗(yàn)來(lái)驗(yàn)證文中提出的求解均方誤差的算法以及公式的正確性。本文進(jìn)行多次實(shí)驗(yàn)，對(duì)多次實(shí)驗(yàn)的誤差取平均值作為實(shí)驗(yàn)誤差。同時(shí)通過(guò)算法3以及式（17）計(jì)算出相對(duì)應(yīng)的理論誤差，將兩者進(jìn)行比較，來(lái)驗(yàn)證本文理論分析的正確性。

本文實(shí)驗(yàn)是在奔騰雙核CPU T4200 2.00 GHz的計(jì)算機(jī)下完成。采用的語(yǔ)言為Matlab，實(shí)驗(yàn)中差分隱私參數(shù)ε統(tǒng)一設(shè)置為1。

5.1 驗(yàn)證任意區(qū)間查詢誤差算法

為了能夠體現(xiàn)出實(shí)驗(yàn)效果，同時(shí)考慮實(shí)驗(yàn)需要消耗的時(shí)間，本文所采取的數(shù)據(jù)規(guī)模為1 024。隨機(jī)生成了50個(gè)查詢區(qū)間，分別計(jì)算理論上和實(shí)驗(yàn)實(shí)際產(chǎn)生的均方誤差。每個(gè)查詢區(qū)間重復(fù)實(shí)驗(yàn)100次，將每次所產(chǎn)生的均方誤差取平均作為最終的實(shí)驗(yàn)結(jié)果，而理論誤差則通過(guò)算法3計(jì)算。詳細(xì)實(shí)驗(yàn)結(jié)果如表1所示。

為了讓讀者更加直觀地比較理論誤差與實(shí)驗(yàn)誤差，將表1中的數(shù)據(jù)制作成折線圖，如圖4所示。

Fig.4 Comparison of experimental error with theoretical error in fixed query interval圖4 固定查詢區(qū)間下實(shí)驗(yàn)誤差與理論誤差的對(duì)比圖

觀察圖4可以發(fā)現(xiàn)，總體上實(shí)驗(yàn)結(jié)果與理論結(jié)果還是比較接近的，而且實(shí)驗(yàn)產(chǎn)生的誤差圍繞著理論誤差上下波動(dòng)，符合差分隱私所添加噪聲是隨機(jī)的這一特點(diǎn)。此外，表1中，有的查詢區(qū)間實(shí)驗(yàn)結(jié)果與理論結(jié)果較接近，而有的則相差較大，這說(shuō)明查詢區(qū)間的不同產(chǎn)生的誤差波動(dòng)程度不一，這也是由于實(shí)驗(yàn)次數(shù)不夠多，隨著實(shí)驗(yàn)次數(shù)增多，所有的查詢區(qū)間的誤差會(huì)與理論誤差越來(lái)越接近。

5.2 驗(yàn)證平均區(qū)間查詢誤差算法

接下來(lái)，將對(duì)前文分析得出的Prievlet算法在平均情況下的均方誤差進(jìn)行實(shí)驗(yàn)論證。為了更好地驗(yàn)證該理論分析的正確性，本文對(duì)所有可能的區(qū)間進(jìn)行實(shí)驗(yàn)，最終取平均值作為實(shí)驗(yàn)結(jié)果。本次實(shí)驗(yàn)采用的數(shù)據(jù)規(guī)模為N=2m,0≤m≤10，共10組模擬數(shù)據(jù)進(jìn)行實(shí)驗(yàn)對(duì)比。與上個(gè)實(shí)驗(yàn)一樣，本實(shí)驗(yàn)也進(jìn)行了100次重復(fù)實(shí)驗(yàn)，之后取平均值作為實(shí)驗(yàn)結(jié)果，并根據(jù)式（17）計(jì)算得出理論上的均方誤差進(jìn)行比較。實(shí)驗(yàn)結(jié)果如表2所示。

Table 1 Results of two errors in fixed query interval表1 固定區(qū)間查詢下兩種誤差的計(jì)算結(jié)果

Table 2 Experimental error and theoretical error in mean case表2 平均情況下的實(shí)驗(yàn)誤差與理論誤差

為了方便觀察,將實(shí)驗(yàn)結(jié)果用折線圖的方式表示。實(shí)驗(yàn)結(jié)果如圖5所示。

Fig.5 Comparison of experimental results with theoretical results in mean case圖5 平均情況下實(shí)驗(yàn)誤差與理論誤差的對(duì)比圖

從圖5可明顯地看出，實(shí)驗(yàn)結(jié)果與分析結(jié)果幾乎一樣，進(jìn)一步說(shuō)明了式（17）計(jì)算出的Prievlet算法均方誤差能準(zhǔn)確地反映算法性能，驗(yàn)證了該公式的正確性。

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

本文利用矩陣機(jī)制的相關(guān)理論，分析了以Prievlet算法為代表的基于矩陣機(jī)制的差分隱私數(shù)據(jù)發(fā)布方法的理論誤差，成功求解了Prievlet算法在任意區(qū)間查詢下的均方誤差和平均情況下的均方誤差公式。并在此基礎(chǔ)上提出了可有效衡量具有相同誤差漸進(jìn)階的不同差分隱私發(fā)布算法之間性能差異的精確度指標(biāo)。

附錄：