傅繼彬，張嘯劍，丁麗萍

?

MAXGDDP：基于差分隱私的決策數(shù)據(jù)發(fā)布算法

傅繼彬1，張嘯劍1，丁麗萍2

（1. 河南財(cái)經(jīng)政法大學(xué)計(jì)算機(jī)與信息工程學(xué)院，河南 鄭州 450046；2. 中國科學(xué)院軟件研究所，北京 100190）

基于層次細(xì)化的差分隱私?jīng)Q策數(shù)據(jù)發(fā)布得到了研究者的廣泛關(guān)注，層次節(jié)點(diǎn)的選擇、分類樹的構(gòu)建以及每層隱私代價(jià)的分配直接制約著決策數(shù)據(jù)發(fā)布結(jié)果的好壞，也影響最終的數(shù)據(jù)分析結(jié)果。針對現(xiàn)有基于層次細(xì)化的決策數(shù)據(jù)發(fā)布方法難以兼顧上述問題的不足，提出一種高效的分層細(xì)化方法MAXGDDP，該方法對原始分類數(shù)據(jù)進(jìn)行分層細(xì)化，在同一層次的概念細(xì)化中提出了最大值屬性索引算法，在不同層次之間利用類幾何分配機(jī)制來更加合理地分配隱私預(yù)算?；谡鎸?shí)數(shù)據(jù)集對比了MAXGDDP與DiffGen算法，實(shí)驗(yàn)結(jié)果表明該方法在保護(hù)數(shù)據(jù)隱私的同時(shí)，提高了發(fā)布數(shù)據(jù)的分類準(zhǔn)確率。

決策數(shù)據(jù)；數(shù)據(jù)發(fā)布；差分隱私；層次細(xì)化

1 引言

隨著信息技術(shù)的飛速發(fā)展，個(gè)人數(shù)字信息也在快速增長。對收集到的個(gè)人數(shù)據(jù)進(jìn)行分析和挖掘能夠發(fā)現(xiàn)大量有價(jià)值的信息，與此同時(shí)，數(shù)據(jù)中所蘊(yùn)含的敏感信息也有可能被泄露。例如，醫(yī)院把病人的電子病歷數(shù)據(jù)發(fā)布出來，通過對這些數(shù)據(jù)的分析和挖掘，可以發(fā)現(xiàn)各種疾病之間的關(guān)系或其他有利于醫(yī)學(xué)進(jìn)步的信息，但是在該過程中也可能會造成病人隱私的泄露。因此，如何解決數(shù)據(jù)發(fā)布過程中可能存在的隱私泄露問題已經(jīng)成為一個(gè)非常重要的研究課題。

基于-匿名的方法[1]及其變種方法[2~4]是解決數(shù)據(jù)發(fā)布常用的隱私保護(hù)技術(shù)，然而這類方法通常在特殊的攻擊背景知識假設(shè)下才能成立。差分隱私保護(hù)模型[5,6]的出現(xiàn)為隱私保護(hù)數(shù)據(jù)發(fā)布提供了新的方向，它不需要對攻擊者的背景知識做任何假設(shè)。因此，本文聚焦于滿足差分隱私的決策數(shù)據(jù)發(fā)布問題。目前，已有多種基于差分隱私的決策樹數(shù)據(jù)發(fā)布方法[7~9]。文獻(xiàn)[7]利用指數(shù)機(jī)制來挑選決策樹中的分割屬性，盡管該方法利用全部的隱私預(yù)算選擇最好的分割屬性，然而它是基于交互式查詢接口構(gòu)建的決策樹，一旦大量的分析者提交查詢時(shí)，該方法的分類精度就會降低。文獻(xiàn)[8,9]結(jié)合指數(shù)機(jī)制確定分割屬性，借助于決策樹自頂向下地把數(shù)據(jù)集中所有記錄劃分到葉子節(jié)點(diǎn)中去，然后對葉子節(jié)點(diǎn)中的計(jì)數(shù)值添加拉普拉斯噪聲。盡管該類法采用非交互式發(fā)布決策數(shù)據(jù)，然而卻存在2個(gè)問題：1) 數(shù)值屬性與非數(shù)值屬性分開處理，這樣需要更多的隱私噪聲；2) 自頂向下分割屬性時(shí)，采用均分的方式處理隱私預(yù)算，而均分的方式直接受到樹高度的制約?？傊?，目前還沒有一個(gè)行之有效的基于差分隱私的方法來統(tǒng)一處理數(shù)值屬性與非數(shù)值屬性，并且給出合理的隱私預(yù)算分配策略。因此，結(jié)合上述分析，本文提出了一種名為MAXGDDP的差分隱私保護(hù)算法，其中，MAX表示在屬性選擇時(shí)使用的最大值索引屬性選擇隱私保護(hù)算法，GD表示在不同層次隱私預(yù)算分配時(shí)采用幾何分布機(jī)制。該算法的具體創(chuàng)新點(diǎn)如下。

1) 為了能夠同時(shí)處理數(shù)值屬性與非數(shù)值屬性，提出了最大值索引屬性選擇算法。該方法對數(shù)值與非數(shù)值屬性進(jìn)行統(tǒng)一處理，并且極大地降低了噪聲的規(guī)模。

2) 為了合理地分配隱私預(yù)算，提出了類似幾何策略的預(yù)算分配策略。該方法能夠把預(yù)算盡量預(yù)留給決策樹的葉子節(jié)點(diǎn)。

3) 理論證明所提出的決策樹數(shù)據(jù)發(fā)布方法滿足-差分隱私。在真實(shí)數(shù)據(jù)上進(jìn)行了可用性分析，實(shí)驗(yàn)結(jié)果表明，MAXGDDP優(yōu)于同類方法。

2 相關(guān)工作

決策樹（decision tree）是常用的數(shù)據(jù)分類模型，ID3是經(jīng)典的決策樹學(xué)習(xí)算法，C4.5是ID3算法的改進(jìn)。針對決策樹數(shù)據(jù)發(fā)布時(shí)的隱私問題，主要存在2種隱私保護(hù)模型：匿名化模型與差分隱私保護(hù)模型。

匿名化模型通常使用數(shù)據(jù)的泛化操作來起到隱私保護(hù)效果，其代表方法包括-匿名[1]、-diversity[2]、-closeness[3]、k-匿名[4]等。-匿名及其變種模型的基本思想是在數(shù)據(jù)泛化處理后，對于某條記錄在數(shù)據(jù)集中至少有?1個(gè)記錄具有和它相同的值，這些相同記錄被定義為等價(jià)組。在等價(jià)組中的記錄是不可區(qū)分的，通過這種方式來保護(hù)個(gè)人數(shù)據(jù)的隱私。這類方法的困難在于對攻擊者的背景知識建模，Ganta等[10]指出通過不可控的背景知識，個(gè)人的隱私可能受到攻擊。

差分隱私提供一種嚴(yán)謹(jǐn)并且可操作的隱私定義，基于差分隱私的數(shù)據(jù)發(fā)布和數(shù)據(jù)分析問題日益受到重視[11~14]。基于差分隱私的數(shù)據(jù)保護(hù)分為交互模式和非交互模式。

在交互模式下，用戶不能直接處理數(shù)據(jù)，只能通過隱私保護(hù)的接口進(jìn)行有次數(shù)限制的數(shù)據(jù)查詢，每次查詢都要消耗隱私預(yù)算。SuLQ-based ID3[15]實(shí)現(xiàn)了基于差分隱私保護(hù)的ID3算法，在每次計(jì)算屬性的信息增益時(shí)加入Laplace機(jī)制的噪聲計(jì)數(shù)值，但加入噪聲后導(dǎo)致預(yù)測結(jié)果準(zhǔn)確率下降。PINQ數(shù)據(jù)分析平臺[16]使用Partition算子將查詢數(shù)據(jù)集分割成不相交的子集，利用其計(jì)算時(shí)并行組合的特點(diǎn)，提高隱私保護(hù)預(yù)算的利用率，該算法直接利用噪聲計(jì)數(shù)值評估信息增益標(biāo)準(zhǔn)，再使用ID3算法生成決策樹。由于信息增益的計(jì)數(shù)值需要對每個(gè)屬性進(jìn)行計(jì)算，所以需要將整個(gè)隱私預(yù)算分配到每次查詢中，導(dǎo)致每次查詢的隱私預(yù)算較小，當(dāng)數(shù)據(jù)集較大時(shí)將引入大量噪聲。文獻(xiàn)[7]提出了基于指數(shù)機(jī)制的Differential Private ID3和C4.5算法，指數(shù)機(jī)制在一次查詢中同時(shí)評估所有屬性，減少了噪聲和隱私預(yù)算的浪費(fèi)，指數(shù)機(jī)制可以挑選屬性分割點(diǎn)。該算法在處理大量查詢時(shí)分類精度有所降低。

而非交互模式的隱私保護(hù)算法是對數(shù)據(jù)進(jìn)行處理并且發(fā)布處理后的合成數(shù)據(jù)庫，用戶能對發(fā)布的合成數(shù)據(jù)庫進(jìn)行任意處理[17]。如何合理分配隱私預(yù)算，并盡可能提高發(fā)布數(shù)據(jù)的可用性，是非交互式發(fā)布主要面臨的問題。

文獻(xiàn)[8,9]分別提出了針對決策樹分析的差分隱私數(shù)據(jù)發(fā)布算法DiffGen[8]與DT-Diff[9]。這2種算法采用“自頂向下、逐步細(xì)分”的策略，首先將數(shù)據(jù)集完全泛化，然后進(jìn)入細(xì)分迭代循環(huán)。該算法利用指數(shù)機(jī)制進(jìn)行屬性選擇，利用拉普拉斯機(jī)制進(jìn)行記錄計(jì)數(shù)的隨機(jī)化。雖然這2種算法滿足-差分隱私保護(hù)要求，但其缺點(diǎn)在于沒有充分利用給定的隱私預(yù)算，導(dǎo)致加入不必要的冗余噪聲。

Fletcher等[18]利用信噪比技術(shù)構(gòu)建隨機(jī)決策樹來發(fā)布決策數(shù)據(jù)，然而該方法利用均分的方式來處理隱私預(yù)算。Cormode等[19]在空間數(shù)據(jù)分割的隱私保護(hù)研究中提出了四分樹、kd樹層級之間的隱私代價(jià)幾何分配策略。但是決策樹和四分樹、kd樹的結(jié)構(gòu)是不同的，它在層次之間沒有固定的扇出數(shù)。

基于對以上相關(guān)工作的分析，本文提出了MAXGDDP方法來發(fā)布決策樹數(shù)據(jù)，它利用最大值索引屬性選擇算法挑選分割屬性進(jìn)行層次細(xì)化，在不同層次推導(dǎo)出基于決策樹的類幾何分布隱私預(yù)算分配策略。該方法不但滿足差分隱私，同時(shí)還能夠發(fā)布比較精確的結(jié)果。

3 定義與理論基礎(chǔ)

3.1 差分隱私相關(guān)定義

差分隱私保護(hù)方法可以確保在某一數(shù)據(jù)集中插入或刪除一條記錄的操作不會影響計(jì)算的輸出結(jié)果。另外，該保護(hù)模型不關(guān)心攻擊者所具有的背景知識，即使攻擊者已經(jīng)掌握除某一條記錄之外的所有記錄的信息，該記錄的隱私也無法被披露。差分隱私的形式化定義如下。

其中，概率Pr[·]是由算法的隨機(jī)性控制，也表示隱私被披露的風(fēng)險(xiǎn)；隱私預(yù)算參數(shù)表示隱私保護(hù)程度，越小，隱私保護(hù)程度越高。

從定義1可以看出，差分隱私技術(shù)限制了任意一條記錄對算法輸出結(jié)果的影響。該定義是從理論角度確保算法滿足-差分隱私，而要實(shí)現(xiàn)差分隱私保護(hù)需要噪聲機(jī)制的介入。

常用的差分隱私機(jī)制分別為拉普拉斯機(jī)制與指數(shù)機(jī)制。而基于不同噪聲機(jī)制且滿足差分隱私的算法所需噪聲大小與全局敏感性密切相關(guān)，全局敏感度的定義如下。

定義2 對于任意一個(gè)函數(shù):R，函數(shù)的全局敏感度為

其中，和至多相差一條記錄，表示所映射實(shí)數(shù)空間，表示函數(shù)的查詢維度，通常使用1度量距離。

拉普拉斯機(jī)制[20]通過對真實(shí)輸出值加入拉普拉斯分布的噪聲進(jìn)行擾動來實(shí)現(xiàn)差分隱私保護(hù)。

而指數(shù)機(jī)制[21]主要處理一些輸出結(jié)果為非數(shù)值型的算法，例如，決策樹分類算法中屬性分裂選擇問題。該機(jī)制的關(guān)鍵是設(shè)計(jì)一個(gè)效用函數(shù)，指數(shù)機(jī)制的定義如下。

3.2 決策樹

決策樹是一種簡單但是廣泛使用的分類預(yù)測模型，樹中每個(gè)節(jié)點(diǎn)表示某個(gè)概念屬性，而每個(gè)分叉則代表該屬性不同的取值，每個(gè)葉節(jié)點(diǎn)則對應(yīng)從根節(jié)點(diǎn)到該葉節(jié)點(diǎn)路徑所表示的分類過程。

決策樹算法根據(jù)訓(xùn)練集構(gòu)建一個(gè)決策樹，利用這個(gè)決策樹可以對測試數(shù)據(jù)進(jìn)行分類處理。決策數(shù)有2個(gè)優(yōu)點(diǎn)：1) 決策樹模型可讀性好，具有描述性，有助于人工分析；2) 效率高，決策樹只需要一次構(gòu)建，反復(fù)使用，每一次預(yù)測的最大計(jì)算次數(shù)不超過決策樹的深度。

決策樹構(gòu)建的基本步驟如下：1) 將所有記錄看作一個(gè)節(jié)點(diǎn)；2) 遍歷每個(gè)屬性的每一種分割方式，找到最好的分割屬性；3) 根據(jù)最佳分割屬性的取值分割成個(gè)節(jié)點(diǎn)1,…,N；4) 對1,…,N分別繼續(xù)執(zhí)行步驟2)~步驟3)，直到滿足某種分類條件為止。

決策樹的屬性根據(jù)處理方式的不同可以分為2種：數(shù)值型和非數(shù)值型。其中，數(shù)值型屬性可以用整數(shù)或浮點(diǎn)數(shù)表示，如“年收入”“年齡”等屬性。選定一個(gè)數(shù)值作為分割點(diǎn)后，每個(gè)記錄根據(jù)自己該屬性值大于或小于該分割點(diǎn)分為2個(gè)集合。非數(shù)值屬性類似編程語言中的枚舉類型，變量只能從有限的選項(xiàng)中選取，例如，“婚姻情況”只能在“單身”“已婚”或“離婚”中選擇。如果非數(shù)值屬性被選擇為分割屬性，每個(gè)記錄根據(jù)自己該屬性值，分為若干個(gè)集合。

在決策樹算法中決定使用哪個(gè)屬性進(jìn)行分割是一個(gè)核心的問題。有很多度量方法來評估分割屬性的好壞，例如，信息增益、信息增益率、最大記錄等。本文主要使用最大記錄數(shù)度量，定義如下

最大記錄是對各個(gè)分支中分類結(jié)果最大的數(shù)據(jù)記錄總和，該函數(shù)的敏感度為1。

3.3 基于泛化的非交互數(shù)據(jù)發(fā)布

在數(shù)據(jù)發(fā)布的隱私保護(hù)中，本文采用了泛化的方法。它的思想是用泛化值去替換原有的細(xì)化值以保護(hù)原有信息的隱私。例如，數(shù)據(jù)中的年齡信息，它是一個(gè)數(shù)值屬性，假設(shè)某個(gè)人年齡為25，經(jīng)過泛化處理會變?yōu)橐粋€(gè)范圍，如18~65。在每個(gè)屬性進(jìn)行泛化的過程需要一個(gè)表示概念泛化關(guān)系的分類樹。樹的根節(jié)點(diǎn)是一個(gè)最泛化的概念A(yù)ny，每個(gè)子節(jié)點(diǎn)是父節(jié)點(diǎn)的具體化的分類，圖1為國籍屬性的分類樹。

圖1 國籍屬性的分類樹

4 MAXGDDP數(shù)據(jù)發(fā)布算法

針對上述問題，本文提出了MAXGDDP算法。在分類數(shù)據(jù)的處理過程中采用逐層分割的思想，首先把所有的記錄壓縮到一個(gè)根節(jié)點(diǎn)，然后結(jié)合分割標(biāo)準(zhǔn)自頂向下分割，最后葉子節(jié)點(diǎn)存放分類的記錄分區(qū)。然而在分割過程中，如何選擇一個(gè)屬性進(jìn)行分割是分類數(shù)據(jù)發(fā)布的關(guān)鍵。針對分割屬性的選擇，提出了最大值索引屬性選擇算法（MAXDP），該算法對數(shù)值屬性和非數(shù)值屬性進(jìn)行統(tǒng)一處理。同時(shí)，在樹結(jié)構(gòu)的不同層次之間利用類幾何分布策略進(jìn)行隱私預(yù)算分配。

4.1 最大值索引屬性選擇（MAXDP）算法

分類數(shù)據(jù)的發(fā)布過程中，如何選擇一個(gè)好的分割節(jié)點(diǎn)，同時(shí)保護(hù)每個(gè)分割節(jié)點(diǎn)中真值計(jì)數(shù)不被泄露，是一個(gè)關(guān)鍵的問題。針對這個(gè)問題，本文提出一個(gè)滿足差分隱私的分割點(diǎn)選擇（MAXDP）算法。

該方法把決策樹同一層的數(shù)值屬性和非數(shù)值屬性統(tǒng)一處理，而且極大地降低了隱私保護(hù)噪聲的規(guī)模。該方法使用最大記錄數(shù)作為選擇分割屬性的度量方法。在傳統(tǒng)的決策樹算法中，非數(shù)值屬性如在某個(gè)數(shù)據(jù)集中的屬性“天氣”，它的值有3種可能，分別是“晴朗”“多云”“下雨”。根據(jù)這個(gè)屬性的值可以把數(shù)據(jù)記錄分為3類，根據(jù)記錄的分類可以計(jì)算出該屬性的最大記錄數(shù)值。而對于數(shù)值屬性首先要確定其分割點(diǎn)，例如，在某個(gè)數(shù)據(jù)集中的屬性“年齡”，其取值范圍是整數(shù)[18,65]，需要確定某個(gè)分割點(diǎn)把數(shù)據(jù)分為2類，所以首先要算出最優(yōu)分割點(diǎn)，然后把記錄分類，并計(jì)算該屬性的最大記錄數(shù)值，最后才可以把數(shù)值屬性和非數(shù)值屬性放在一起比較，選擇出最優(yōu)分割屬性。所以數(shù)值屬性的處理和非數(shù)值屬性的處理流程不同，數(shù)值屬性分為2步，需要更多的隱私預(yù)算。

MAXDP算法對于每個(gè)非數(shù)值屬性（如國籍屬性），只需要計(jì)算出一個(gè)最大記錄數(shù)度量值；而數(shù)值屬性（如年齡為[18,65]，在18~65之間有多種分割方式），需要對所有可能的分割點(diǎn)進(jìn)行最大記錄數(shù)度量值的計(jì)算，即一個(gè)屬性對應(yīng)多個(gè)最大記錄數(shù)值。本文把所有的計(jì)算結(jié)果放在一個(gè)統(tǒng)一的向量中，如圖2所示。每個(gè)非數(shù)值屬性對應(yīng)向量中一個(gè)空間，每個(gè)數(shù)值屬性對應(yīng)向量中一組連續(xù)的空間，每個(gè)空間點(diǎn)對應(yīng)數(shù)值屬性可能分割點(diǎn)的最大記錄數(shù)值。

圖2 MAXDP中的屬性選擇向量結(jié)構(gòu)

為了計(jì)算方便，把所有的計(jì)算結(jié)果放在一個(gè)向量0中，0=<1,2,…,c>，其中，c表示從該屬性進(jìn)行分割的最大記錄數(shù)。為了尋找分割節(jié)點(diǎn)，需要搜索簇0中的最大值。而在尋找0中的最大值時(shí)，如果不采用噪聲機(jī)制進(jìn)行擾動，則會泄露該分割節(jié)點(diǎn)所包含的具體計(jì)數(shù)值。獲得具體計(jì)數(shù)后，攻擊者即可推測出某些記錄屬于哪些具體的類別，進(jìn)而導(dǎo)致個(gè)人的隱私信息泄露。

一種最直接的方法是對0中每個(gè)計(jì)數(shù)添加ε拉普拉斯噪聲，其中，ε表示分割樹的第層所分得的隱私預(yù)算。輸出后比較大小，進(jìn)而獲得最大值。然而該方法所挑選出的最大值非常不準(zhǔn)確，其原因是?=。例如，c=12、?=100、ε=0.1，則相當(dāng)于以1 000倍的噪聲對c進(jìn)行擾動，進(jìn)而c的真實(shí)值發(fā)生很大的扭曲。

通過分析決策樹的工作原理發(fā)現(xiàn)，沒有必要輸出0中所有的噪聲值進(jìn)行比較來獲得最大值。只要獲得0中最大值所處的位置即可，即最大值的索引位置。如果返回的索引指向一個(gè)非數(shù)值屬性，對這個(gè)非數(shù)值屬性進(jìn)行樹的擴(kuò)展，如果返回的索引落在某個(gè)數(shù)值屬性的可能分割點(diǎn)的區(qū)間內(nèi)，利用該索引指向的數(shù)值進(jìn)行分割點(diǎn)的確定，并且進(jìn)一步進(jìn)行樹的擴(kuò)展。

MAXDP算法使?1，進(jìn)而極大降低了隱私保護(hù)噪聲的規(guī)模。接下來，需要證明輸出最大值索引位置的過程滿足ε-差分隱私。

定理1 MAXDP滿足ε-差分隱私。

首先證明式(6)成立。

因此，式(6)成立。

同理，可以推理出式(7)也成立。

進(jìn)而，可證明MAXDP滿足ε-差分隱私。

4.2 基于類幾何策略的隱私預(yù)算分配方法

則決策樹所攜帶的總體誤差可以表示為

其中，f表示第層的總扇出數(shù)。

因此，將為決策樹每層分配合理預(yù)算轉(zhuǎn)化為使目標(biāo)函數(shù)()最小的優(yōu)化問題，即

證明 通過Cauchy-Schwarz不等式可知

因此，有

由此可知，每層的隱私預(yù)算是與分類樹的各層扇出有關(guān)的，并且在各個(gè)層次之間，隱私預(yù)算與扇出的關(guān)系為

因?yàn)闆Q策樹中第層扇出f，總是大于第?1層總扇出f1，所以ε是遞增的，在更深的層次應(yīng)該分配更多的隱私預(yù)算，這有利于數(shù)據(jù)更為準(zhǔn)確的發(fā)布。

在決策樹的構(gòu)建過程中，各個(gè)層次總扇出和決策樹的總扇出是在選擇隱私預(yù)算之后計(jì)算最佳屬性之后才能得到，所以在計(jì)算每個(gè)層次的隱私預(yù)算時(shí)，假設(shè)=3，即可獲得=。

由等比數(shù)列公式可得ε，即

4.3 MAXGDDP算法描述

MAXGDDP算法從最泛化概念開始，通過一系列符合隱私保護(hù)的操作對數(shù)據(jù)進(jìn)行細(xì)分處理。在進(jìn)行決策樹構(gòu)建的過程中，選擇最佳分割屬性時(shí)采用MAXDP算法。各層次之間采用類幾何分布策略分配隱私預(yù)算，整個(gè)算法的過程如算法1所示。

算法1 MAXGDDP

輸入 初始數(shù)據(jù)集，隱私預(yù)算，細(xì)化層次

1) 對數(shù)據(jù)集中每個(gè)屬性進(jìn)行初始化A=Any，其中，Any為最泛化的概念，所有的記錄放在一個(gè)初始化分區(qū)中。

2) 把整個(gè)隱私預(yù)算分為2個(gè)部分，1+2=。

3)for=1 to

4) 計(jì)算該層的隱私保護(hù)預(yù)算

5) 計(jì)算分區(qū)中所有屬性的最大記錄數(shù)度量值。非數(shù)值屬性計(jì)算出一個(gè)值，數(shù)值屬性對每個(gè)可能的分割點(diǎn)計(jì)算，得出一組值，把這些數(shù)組放在一個(gè)向量中，利用MAXDP算法選擇某個(gè)屬性A

6) 利用屬性A的細(xì)化概念層次對數(shù)據(jù)集進(jìn)行細(xì)化，并且數(shù)據(jù)集合根據(jù)細(xì)化概念進(jìn)行分區(qū)

7) 更新所有分區(qū)中記錄的統(tǒng)計(jì)計(jì)數(shù)值，并在新分區(qū)重新進(jìn)行以上計(jì)算

8) end for

對于整個(gè)算法，隱私預(yù)算分為2個(gè)部分，在決策樹的建立過程中使用1，在對葉子節(jié)點(diǎn)分區(qū)記錄計(jì)數(shù)進(jìn)行隨機(jī)化時(shí)使用2，對每個(gè)分區(qū)的記錄數(shù)利用拉普拉斯機(jī)制添加lap噪聲。根據(jù)定理3可知，MAXGDDP算法滿足-差分隱私。

5 實(shí)驗(yàn)結(jié)果與分析

實(shí)驗(yàn)中用C++實(shí)現(xiàn)了MAXGDDP隱私保護(hù)數(shù)據(jù)發(fā)布算法。實(shí)驗(yàn)機(jī)器配置為2.10 GHz 6核Xeon CPU，32 GB內(nèi)存。在實(shí)驗(yàn)數(shù)據(jù)方面，采用了3個(gè)UCI數(shù)據(jù)集Iris、Adult和Census Income。Iris數(shù)據(jù)集如表1所示，共有4個(gè)數(shù)值型的預(yù)測屬性，分類結(jié)果為3類，數(shù)據(jù)共有150條記錄。

表1 Iris數(shù)據(jù)集

Adult數(shù)據(jù)集如表2所示，共有14個(gè)預(yù)測屬性，其中，數(shù)值型有6個(gè)，非數(shù)值型有8個(gè)，分類結(jié)果有2類，數(shù)據(jù)集中去掉了屬性值未知的記錄，共有45 222條記錄。

表2 Adult數(shù)據(jù)集

在3個(gè)數(shù)據(jù)集中，Census Income數(shù)據(jù)集的屬性和記錄數(shù)都較多，共有40個(gè)屬性，其中，7個(gè)數(shù)值屬性，33個(gè)非數(shù)值屬性，數(shù)據(jù)集中去掉了屬性值未知的記錄，共有14 2521個(gè)記錄。

在MAXGDDP算法進(jìn)行概念細(xì)化的過程中，每個(gè)數(shù)據(jù)集的每個(gè)屬性都需要一個(gè)分類樹集合來配合算法的逐層細(xì)化計(jì)算。分類樹中記錄了每一個(gè)屬性的細(xì)化過程。例如，在Adult數(shù)據(jù)集中的education-num（教育年限/數(shù)值屬性）的分類樹結(jié)構(gòu)如下

{1-20 {1-12 {1-5} {5-12}} {12-20 {12-16} {16-20}}}。

workclasst（工作類別/非數(shù)值型屬性）的分類樹結(jié)構(gòu)如下

{Any {Worked {With-Pay {Private} {Self-emp {Self-emp-not-inc }{Self-emp-inc }} {Gov {Federal-gov}{Local-gov}{State-gov}}} {Without-pay}} {Never-worked}}。

對每一個(gè)數(shù)據(jù)集進(jìn)行處理的過程中，首先確定該層次的隱私預(yù)算，然后在同一層次中對數(shù)據(jù)集中的每個(gè)屬性計(jì)算最大記錄值，對于非數(shù)值屬性得到一個(gè)值，對于數(shù)值屬性得到多個(gè)值（每個(gè)值對應(yīng)于每個(gè)可能的分割點(diǎn)），把這些數(shù)值放在一個(gè)向量中，利用最大值索引屬性選擇算法返回最大值的索引位置，通過該位置確定要進(jìn)行分割的屬性，根據(jù)分類樹的結(jié)構(gòu)確定要細(xì)化的概念，并且通過屬性值的不同把數(shù)據(jù)集分到不同的數(shù)據(jù)分區(qū)中。重復(fù)該過程直到細(xì)化層次滿足要求。

在實(shí)驗(yàn)數(shù)據(jù)細(xì)化的過程中，需要加入隨機(jī)性以保證差分隱私，在每次實(shí)驗(yàn)中選擇屬性具有隨機(jī)性，所以本文對每個(gè)實(shí)驗(yàn)都執(zhí)行10次，然后計(jì)算平均的分類準(zhǔn)確率。

為了評估MAXGDDP算法中隱私保護(hù)措施對數(shù)據(jù)分類性能的影響，首先，采用經(jīng)典決策樹算法C4.5對原始數(shù)據(jù)集合進(jìn)行訓(xùn)練和分類，把這個(gè)原始數(shù)據(jù)中的準(zhǔn)確率作為基線（baseline）；然后，利用MAXGDDP算法對各個(gè)原始數(shù)據(jù)集進(jìn)行隱私保護(hù)的處理，生成泛化處理后的合成訓(xùn)練集和測試集；最后，仍然采用C4.5算法，對合成訓(xùn)練集進(jìn)行決策樹的訓(xùn)練，利用得到的決策樹對合成測試集進(jìn)行分類，評估其準(zhǔn)確率，結(jié)果如圖3所示。

圖3(a)為MAXGDDP算法在Iris數(shù)據(jù)集中的評估結(jié)果。該數(shù)據(jù)集包含3個(gè)類別，共150條記錄。從3個(gè)類別中平衡選擇100條記錄作為訓(xùn)練集，50條記錄作為測試集。圖3(a)橫坐標(biāo)為細(xì)分層數(shù)，縱坐標(biāo)為合成數(shù)據(jù)集最終的分類準(zhǔn)確率，最上面的線是原始數(shù)據(jù)集的基線分類準(zhǔn)確率（94%），4條曲線為隱私保護(hù)預(yù)算分別在=0.10, 0.25, 0.50, 1.00條件下各個(gè)細(xì)化層次的準(zhǔn)確率情況。在隱私保護(hù)預(yù)算為1.00，細(xì)分層數(shù)為5時(shí)，獲得最好的分類準(zhǔn)確率（92.98%）。

圖3(b)為MAXGDDP算法在Adult數(shù)據(jù)集中的評估結(jié)果。Adult數(shù)據(jù)集是很多隱私數(shù)據(jù)發(fā)布算法都采用的數(shù)據(jù)集。該數(shù)據(jù)集共有14個(gè)預(yù)測屬性，其中，有6個(gè)數(shù)值屬性和8個(gè)非數(shù)值屬性。該數(shù)據(jù)集共有45 222條記錄，把其中30 148條記錄作為訓(xùn)練集，剩余的15 074條記錄作為測試集。本文評估了MAXGDDP算法在不同細(xì)化參數(shù)（=4,7,10,13,16）、不同隱私保護(hù)預(yù)算（=0.10, 0.25, 0.50, 1.00）的情況。圖3(b)最上面的線是原始數(shù)據(jù)集的基線分類準(zhǔn)確率（85.3%），MAXGDDP算法在細(xì)化參數(shù)為13，隱私保護(hù)預(yù)算為1.00時(shí)，獲得最好的分類準(zhǔn)確率（83.72%）。

圖3(c)為MAXGDDP算法在Census Income數(shù)據(jù)集中的評估結(jié)果，該數(shù)據(jù)集有142 521條記錄，40個(gè)屬性，其中，數(shù)值屬性7個(gè)，非數(shù)值屬性為33個(gè)。該數(shù)據(jù)集的數(shù)據(jù)量比前2個(gè)數(shù)據(jù)集更大，所以分配了更多的隱私預(yù)算。圖3(c)最上面的線是原始數(shù)據(jù)集的基線分類準(zhǔn)確率（95.6%，），MAXGDDP在細(xì)化參數(shù)為10，隱私保護(hù)預(yù)算為2.00時(shí)，獲得最好的分類準(zhǔn)確率（94.7%）。MAXGDDP在該數(shù)據(jù)集上取得了更好的性能，說明該算法具有較好的數(shù)據(jù)擴(kuò)展性。

圖3 MAXGDDP算法在3個(gè)數(shù)據(jù)集中的結(jié)果

Mohammed等[8]提出的DiffGen算法是一個(gè)經(jīng)典的分類數(shù)據(jù)發(fā)布算法，為了評估MAXGDDP算法，在3個(gè)數(shù)據(jù)集對2種算法進(jìn)行了比較。首先，為了比較不同隱私預(yù)算對2種算法的影響，在3個(gè)數(shù)據(jù)集中使用某個(gè)固定細(xì)分層數(shù)，分別使用2種算法對數(shù)據(jù)進(jìn)行隱私保護(hù)的發(fā)布處理，不同隱私預(yù)算下的結(jié)果如圖4所示。

圖4 不同隱私預(yù)算條件下的比較結(jié)果

在圖4(a)中，Iris數(shù)據(jù)集固定細(xì)分層數(shù)為5，比較不同隱私代價(jià)（=0.10, 0.25, 0.50, 1.00）下2種算法的準(zhǔn)確率可以看出，在隱私代價(jià)較小時(shí)MAXGDDP的優(yōu)勢較為明顯。

在圖4(b)中，Adult數(shù)據(jù)集固定細(xì)分層數(shù)為15，比較不同隱私預(yù)算（=0.10, 0.25, 0.50, 1.00）下2種算法分類準(zhǔn)確率可以發(fā)現(xiàn)，MAXGDDP算法在不同的隱私預(yù)算條件下，分類準(zhǔn)確率都優(yōu)于DiffGen算法。

在圖4(c)中，Income數(shù)據(jù)集細(xì)化參數(shù)固定為10，在不同的隱私預(yù)算（=0.50, 0.75, 1.00, 2.00）下比較2種算法最終的準(zhǔn)確率。Census Income數(shù)據(jù)集具有更大的數(shù)據(jù)量，在該數(shù)據(jù)中的結(jié)果可以看作不同算法在數(shù)據(jù)擴(kuò)展性方面的性能?？梢钥闯觯琈AXGDDP算法在數(shù)據(jù)量較大的情況下取得更好的分類準(zhǔn)確率結(jié)果。

綜合分析3個(gè)數(shù)據(jù)集的結(jié)果，MAXGDDP更有效地使用了隱私預(yù)算。所以在Iris數(shù)據(jù)集中，較小隱私預(yù)算條件下的MAXGDDP算法取得了較好效果，而且優(yōu)勢比較明顯，因?yàn)閷傩暂^少的情況下，分割屬性選擇的準(zhǔn)確與否對結(jié)果影響很大。在規(guī)模較大的2個(gè)數(shù)據(jù)中，MAXGDDP在隱私預(yù)算較小時(shí)也取得了較為明顯的優(yōu)勢，在隱私預(yù)算較為充足時(shí)也優(yōu)于DiffGen的效果，但是差別不是很大，因?yàn)樵趯傩暂^多的情況，某個(gè)屬性的選擇對結(jié)果的影響不像小數(shù)據(jù)中那么大。

為了評估不同細(xì)分層數(shù)對2種算法的影響，在固定隱私保護(hù)預(yù)算的情況，對2種算法在不同數(shù)據(jù)集進(jìn)行評估，結(jié)果如圖5所示。

圖5(a)為在Iris數(shù)據(jù)集固定隱私保護(hù)預(yù)算為0.50，細(xì)分層數(shù)（=2,3,4,5,6）下2種算法的分類準(zhǔn)確率。從中可以發(fā)現(xiàn)，MAXGDDP算法在不同細(xì)化層次的條件，其分類準(zhǔn)確率都優(yōu)于DiffGen算法。

圖5(b)為在Adult數(shù)據(jù)集中固定隱私保護(hù)預(yù)算為0.50，細(xì)分層數(shù)（=4,7,10,13,16）下2種算法的分類準(zhǔn)確率結(jié)果。在細(xì)分層數(shù)為13時(shí)，2種算法均得到最高的分類準(zhǔn)確率，而且MAXGDDP算法在各個(gè)細(xì)分層數(shù)上均優(yōu)于DiffGen算法。

圖5(c)是2種算法在Income數(shù)據(jù)集中的結(jié)果。在固定隱私保護(hù)預(yù)算為0.50的條件下，比較不同的細(xì)分層數(shù)（=4, 7, 10, 13）2種算法的分類準(zhǔn)確率。從圖5(c)中可以發(fā)現(xiàn)，MAXGDDP算法在較少細(xì)分層次條件下，優(yōu)勢較為明顯，總體而言，在不同細(xì)化層次的條件，其分類準(zhǔn)確率都優(yōu)于DiffGen算法。

圖5 不同細(xì)分層數(shù)條件下的比較結(jié)果

MAXGDDP算法實(shí)際上包括計(jì)算最佳屬性索引位置的MAXDP算法和決策樹不同層次之間的幾何策略隱私預(yù)算分配方法。本文通過實(shí)驗(yàn)評估了MAXDP算法和隱私預(yù)算分配算法的作用，結(jié)果如圖6所示。圖6中上面曲線是MAXGDDP算法疊加產(chǎn)生的分類準(zhǔn)確率，下面曲線是在MAXDP和決策樹層次間采用隱私預(yù)算平均分配的結(jié)果。2條曲線之間差值可以看作幾何策略分配算法對分類準(zhǔn)確率的作用。從圖6可以發(fā)現(xiàn)，幾何分布算法在不同數(shù)據(jù)集中對分類準(zhǔn)確率的提升都有一定的作用。

圖6 隱私預(yù)算幾何分布的影響

6 結(jié)束語

本文提出的MAXGDDP算法用于隱私保護(hù)數(shù)據(jù)發(fā)布，在保護(hù)數(shù)據(jù)中敏感信息的同時(shí)保持?jǐn)?shù)據(jù)的可用性。針對決策樹算法的特點(diǎn)，在選擇細(xì)化屬性時(shí)，利用MAXDP隱私保護(hù)算法計(jì)算最佳屬性的索引位置。在決策樹不同層次之間，利用決策樹層次的幾何分布更加合理地分配隱私預(yù)算。本文通過理論證明了該算法滿足差分隱私，并且通過實(shí)驗(yàn)也表明該方法的有效性。

目前，MAXGDDP算法是利用靜態(tài)數(shù)據(jù)進(jìn)行隱私保護(hù)的數(shù)據(jù)發(fā)布，但是隨著互聯(lián)網(wǎng)信息資源的數(shù)量和重要性不斷增長，從互聯(lián)網(wǎng)上獲取知識變得越來越重要，互聯(lián)網(wǎng)環(huán)境數(shù)據(jù)的顯著特征是動態(tài)更新，這種數(shù)據(jù)隨時(shí)更新的數(shù)據(jù)環(huán)境稱為動態(tài)數(shù)據(jù)環(huán)境。下一步的工作主要研究在動態(tài)數(shù)據(jù)環(huán)境下基于差分隱私的數(shù)據(jù)發(fā)布算法。

[1] SWEENEY L.-anonymity: a model for protecting privacy[J]. International Journal of Uncertainty, Fuzziness and Knowledge-Based Systems, 2002, 10(5): 557-570.

[2] MACHANAVAJJHALA A, KIFER D, GEHRKE J, et al.-diversity: privacy beyond-anonymity[J]. ACM Transactions on Knowledge Discovery from Data (TKDD), 2007, 1(1): 3-52.

[3] LI N, LI T, VENKATASUBRAMANIAN S.-closeness: privacy beyond-anonymity and-diversity[C]//2007 IEEE 23rd International Conference on Data Engineering. 2007: 106-115.

[4] TERROVITIS M, MAMOULIS N, KALNIS P. Privacy-preserving anonymization of set-valued data[C]//Very Large Data Base Endowment. 2008: 115-125.

[5] DWORK C. Differential privacy[C]//33rd International Colloquium on Automata, Languages and Programming, part II (ICALP 2006). 2006: 1-12.

[6] DWORK C, LEI J. Differential privacy and robust statistics[C]//The 41th Annual ACM Symposium on Theory of Computing (STOC).2009: 371-380.

[7] FRIEDMAN A, SCHUSTER A. Data mining with differential privacy[C]//The 16th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining.2010: 493-502.

[8] MOHAMMED N, CHEN R, FUNG B, et al. Differentially private data release for data mining[C]//The 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2011: 493-501.

[9] ZHU T, XIONG P, XIANG Y, et al. An effective deferentially private data releasing algorithm for decision tree[C]//12th IEEE International Conference on Trust, Security and Privacy in Computing and Communications.2013: 388-395.

[10] GANTA S R, KASIVISWANATHAN S P, SMITH A. Composition attacks and auxiliary information in data privacy[C]//The 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. 2008: 265-273.

[11] ZHU T, LI G, ZHOU W, et al. Differentially private data publishing and analysis: a survey[J]. IEEE Transactions on Knowledge and Data Engineering. 2017, 29(8): 1619-1638.

[12] 熊平, 朱天清, 王曉峰. 差分隱私保護(hù)及其應(yīng)用[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(1): 101-122.

XIONG P, ZHU T Q, WANG X F. A survey on differential privacy and applications[J]. Chinese Journal of Computers, 2014, 37(1): 101-122.

[13] 康海燕, 馬躍雷. 差分隱私保護(hù)在數(shù)據(jù)挖掘中應(yīng)用綜述[J]. 山東大學(xué)學(xué)報(bào): 理學(xué)版, 2017(3): 16-23.

KANG H Y, MA Y L. Survey on application of data ming via differential privacy[J]. Journal of Shangdong University(Natural Science), 2017(3): 16-23.

[14] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護(hù)[J]. 計(jì)算機(jī)學(xué)報(bào), 2014, 37(4): 927-949.

ZHANG X J, MENG X F. Differential privacy in data publication and analysis[J]. Chinese Journal of Computers, 2014, 37(4): 927-949.

[15] BLUM A, DWORK C, MCSHERRY F, et al. Practical privacy: the SuLQ framework[C]//The Twenty-Fourth ACM SIGMOD-SIGACT- SIGART Symposium on Principles of Database Systems. 2005: 128-138.

[16] MCSHERRY F D. Privacy integrated queries: an extensible platform for privacy-preserving data analysis[C]//The 2009 ACM SIGMOD International Conference on Management of Data.2009: 19-30.

[17] GOSWAMI P, MADAN S. Privacy preserving data publishing and data anonymization approaches: a review[C]//2017 International Conference on Computing, Communication and Automation. 2017: 139-142.

[18] FLETCHER S, ISLAM M Z. A differentially private random decision forest using reliable signal-to-noise ratios[C]//Australasian Joint Conference on Artificial Intelligence. 2015: 192-203.

[19] CORMODE G, PROCOPIUC C, SRIVASTAVA D, et al. Differentially private spatial decompositions[C]//IEEE 28th International Conference on Data Engineering.2012: 20-31.

[20] DWORK C, MCSHERRY F, NISSIM K, et al. Calibrating noise to sensitivity in private data analysis[C]//Theory of Cryptography Conference. 2006: 265-284.

[21] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//48th Annual IEEE Symposium on Foundations of Computer Science. 2007: 94-103.

MAXGDDP: decision data release with differential privacy

FU Jibin1, ZHANG Xiaojian1, DING Liping2

1. College of Computer & Information Engineering, Henan University of Economics and Law, Zhengzhou 450046, China 2. Institute of Software, Chinese Academy of Sciences, Beijing 100190, China

Specialization-based private decision data release has attracted considerable research attention in recent years. The relation among hierarchical node, taxonomy tree, and budget allocation directly constrains the accuracy of data release and classification. Most existing methods based on hierarchical specialization cannot efficiently address the above problems. An effective method was proposed, called MAXGDDP to publish decision data with specialization. MAXGDDP employed MAX index attribute selection algorithm to select the highlight concept for furthering specialization in each hierarchy. Besides, for making more rational use of privacy budget, MAXGDDP relied on geometric strategy to allocate the privacy budget in each hierarchy. Compared with existing methods such as DiffGen on the real datasets, MAXGDDP outperforms its competitors, achieves data privacy and the better result of classification simultaneously.

decision data, data release, differential privacy, hierarchical specialization

TP309

A

10.11959/j.issn.1000-436x.2018049

2017-07-20；

2018-02-27

國家自然科學(xué)基金資助項(xiàng)目（No.61502146, No.91646203, No.91746115）；河南省自然科學(xué)基金資助項(xiàng)目（No.162300410006）；河南省科技攻關(guān)基金資助項(xiàng)目（No.142102210384, No.172102310713）；河南省教育廳高等學(xué)校重點(diǎn)科研基金資助項(xiàng)目（No.16A520002）；河南省青年骨干教師基金資助項(xiàng)目；河南財(cái)經(jīng)政法大學(xué)青年拔尖人才資助計(jì)劃基金資助項(xiàng)目

The National Natural Science Foundation of China (No.61502146, No.91646203, No.91746115), The Natural Science Foundation of Henan Province (No.162300410006), The Key Technologies R&D Program of Henan Province (No.142102210384, No.172102310713), The Research Program of The Higher Education of Henan Educational Committee (No.16A520002), Foundation for The Excellent Youth Teacher of Henan Province, The Young Talents Fund of Henan University of Economics and Law

傅繼彬（1975-），男，河南許昌人，博士，河南財(cái)經(jīng)政法大學(xué)副教授，主要研究方向?yàn)橹R工程、機(jī)器學(xué)習(xí)、隱私保護(hù)等。

張嘯劍（1980-），男，河南周口人，博士，河南財(cái)經(jīng)政法大學(xué)副教授，主要研究方向?yàn)殡[私保護(hù)、差分隱私、數(shù)據(jù)庫等。

丁麗萍（1965-），女，山東青州人，中國科學(xué)院軟件研究所研究員、博士生導(dǎo)師，主要研究方向?yàn)閿?shù)字取證、系統(tǒng)安全、可信計(jì)算等。