MAXGDDP：基于差分隱私的決策數據發布算法

傅繼彬，張嘯劍，丁麗萍

?

MAXGDDP：基于差分隱私的決策數據發布算法

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

（1. 河南財經政法大學計算機與信息工程學院，河南 鄭州 450046；2. 中國科學院軟件研究所，北京 100190）

基于層次細化的差分隱私決策數據發布得到了研究者的廣泛關注，層次節點的選擇、分類樹的構建以及每層隱私代價的分配直接制約著決策數據發布結果的好壞，也影響最終的數據分析結果。針對現有基于層次細化的決策數據發布方法難以兼顧上述問題的不足，提出一種高效的分層細化方法MAXGDDP，該方法對原始分類數據進行分層細化，在同一層次的概念細化中提出了最大值屬性索引算法，在不同層次之間利用類幾何分配機制來更加合理地分配隱私預算。基于真實數據集對比了MAXGDDP與DiffGen算法，實驗結果表明該方法在保護數據隱私的同時，提高了發布數據的分類準確率。

決策數據；數據發布；差分隱私；層次細化

1 引言

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

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

1) 為了能夠同時處理數值屬性與非數值屬性，提出了最大值索引屬性選擇算法。該方法對數值與非數值屬性進行統一處理，并且極大地降低了噪聲的規模。

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

3) 理論證明所提出的決策樹數據發布方法滿足-差分隱私。在真實數據上進行了可用性分析，實驗結果表明，MAXGDDP優于同類方法。

2 相關工作

決策樹（decision tree）是常用的數據分類模型，ID3是經典的決策樹學習算法，C4.5是ID3算法的改進。針對決策樹數據發布時的隱私問題，主要存在2種隱私保護模型：匿名化模型與差分隱私保護模型。

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

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

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

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

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

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

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

3 定義與理論基礎

3.1 差分隱私相關定義

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

其中，概率Pr[·]是由算法的隨機性控制，也表示隱私被披露的風險；隱私預算參數表示隱私保護程度，越小，隱私保護程度越高。

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

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

定義2 對于任意一個函數:R，函數的全局敏感度為

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

拉普拉斯機制[20]通過對真實輸出值加入拉普拉斯分布的噪聲進行擾動來實現差分隱私保護。

而指數機制[21]主要處理一些輸出結果為非數值型的算法，例如，決策樹分類算法中屬性分裂選擇問題。該機制的關鍵是設計一個效用函數，指數機制的定義如下。

3.2 決策樹

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

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

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

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

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

最大記錄是對各個分支中分類結果最大的數據記錄總和，該函數的敏感度為1。

3.3 基于泛化的非交互數據發布

在數據發布的隱私保護中，本文采用了泛化的方法。它的思想是用泛化值去替換原有的細化值以保護原有信息的隱私。例如，數據中的年齡信息，它是一個數值屬性，假設某個人年齡為25，經過泛化處理會變為一個范圍，如18~65。在每個屬性進行泛化的過程需要一個表示概念泛化關系的分類樹。樹的根節點是一個最泛化的概念Any，每個子節點是父節點的具體化的分類，圖1為國籍屬性的分類樹。

圖1 國籍屬性的分類樹

4 MAXGDDP數據發布算法

針對上述問題，本文提出了MAXGDDP算法。在分類數據的處理過程中采用逐層分割的思想，首先把所有的記錄壓縮到一個根節點，然后結合分割標準自頂向下分割，最后葉子節點存放分類的記錄分區。然而在分割過程中，如何選擇一個屬性進行分割是分類數據發布的關鍵。針對分割屬性的選擇，提出了最大值索引屬性選擇算法（MAXDP），該算法對數值屬性和非數值屬性進行統一處理。同時，在樹結構的不同層次之間利用類幾何分布策略進行隱私預算分配。

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

分類數據的發布過程中，如何選擇一個好的分割節點，同時保護每個分割節點中真值計數不被泄露，是一個關鍵的問題。針對這個問題，本文提出一個滿足差分隱私的分割點選擇（MAXDP）算法。

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

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

圖2 MAXDP中的屬性選擇向量結構

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

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

通過分析決策樹的工作原理發現，沒有必要輸出0中所有的噪聲值進行比較來獲得最大值。只要獲得0中最大值所處的位置即可，即最大值的索引位置。如果返回的索引指向一個非數值屬性，對這個非數值屬性進行樹的擴展，如果返回的索引落在某個數值屬性的可能分割點的區間內，利用該索引指向的數值進行分割點的確定，并且進一步進行樹的擴展。

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

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

首先證明式(6)成立。

因此，式(6)成立。

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

進而，可證明MAXDP滿足ε-差分隱私。

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

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

其中，f表示第層的總扇出數。

因此，將為決策樹每層分配合理預算轉化為使目標函數()最小的優化問題，即

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

因此，有

由此可知，每層的隱私預算是與分類樹的各層扇出有關的，并且在各個層次之間，隱私預算與扇出的關系為

因為決策樹中第層扇出f，總是大于第?1層總扇出f1，所以ε是遞增的，在更深的層次應該分配更多的隱私預算，這有利于數據更為準確的發布。

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

由等比數列公式可得ε，即

4.3 MAXGDDP算法描述

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

算法1 MAXGDDP

輸入 初始數據集，隱私預算，細化層次

1) 對數據集中每個屬性進行初始化A=Any，其中，Any為最泛化的概念，所有的記錄放在一個初始化分區中。

2) 把整個隱私預算分為2個部分，1+2=。

3)for=1 to

4) 計算該層的隱私保護預算

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

6) 利用屬性A的細化概念層次對數據集進行細化，并且數據集合根據細化概念進行分區

7) 更新所有分區中記錄的統計計數值，并在新分區重新進行以上計算

8) end for

對于整個算法，隱私預算分為2個部分，在決策樹的建立過程中使用1，在對葉子節點分區記錄計數進行隨機化時使用2，對每個分區的記錄數利用拉普拉斯機制添加lap噪聲。根據定理3可知，MAXGDDP算法滿足-差分隱私。

5 實驗結果與分析

實驗中用C++實現了MAXGDDP隱私保護數據發布算法。實驗機器配置為2.10 GHz 6核Xeon CPU，32 GB內存。在實驗數據方面，采用了3個UCI數據集Iris、Adult和Census Income。Iris數據集如表1所示，共有4個數值型的預測屬性，分類結果為3類，數據共有150條記錄。

表1 Iris數據集

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

表2 Adult數據集

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

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

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

workclasst（工作類別/非數值型屬性）的分類樹結構如下

{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}}。

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

在實驗數據細化的過程中，需要加入隨機性以保證差分隱私，在每次實驗中選擇屬性具有隨機性，所以本文對每個實驗都執行10次，然后計算平均的分類準確率。

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

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

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

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

圖3 MAXGDDP算法在3個數據集中的結果

Mohammed等[8]提出的DiffGen算法是一個經典的分類數據發布算法，為了評估MAXGDDP算法，在3個數據集對2種算法進行了比較。首先，為了比較不同隱私預算對2種算法的影響，在3個數據集中使用某個固定細分層數，分別使用2種算法對數據進行隱私保護的發布處理，不同隱私預算下的結果如圖4所示。

圖4 不同隱私預算條件下的比較結果

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

在圖4(b)中，Adult數據集固定細分層數為15，比較不同隱私預算（=0.10, 0.25, 0.50, 1.00）下2種算法分類準確率可以發現，MAXGDDP算法在不同的隱私預算條件下，分類準確率都優于DiffGen算法。

在圖4(c)中，Income數據集細化參數固定為10，在不同的隱私預算（=0.50, 0.75, 1.00, 2.00）下比較2種算法最終的準確率。Census Income數據集具有更大的數據量，在該數據中的結果可以看作不同算法在數據擴展性方面的性能。可以看出，MAXGDDP算法在數據量較大的情況下取得更好的分類準確率結果。

綜合分析3個數據集的結果，MAXGDDP更有效地使用了隱私預算。所以在Iris數據集中，較小隱私預算條件下的MAXGDDP算法取得了較好效果，而且優勢比較明顯，因為屬性較少的情況下，分割屬性選擇的準確與否對結果影響很大。在規模較大的2個數據中，MAXGDDP在隱私預算較小時也取得了較為明顯的優勢，在隱私預算較為充足時也優于DiffGen的效果，但是差別不是很大，因為在屬性較多的情況，某個屬性的選擇對結果的影響不像小數據中那么大。

為了評估不同細分層數對2種算法的影響，在固定隱私保護預算的情況，對2種算法在不同數據集進行評估，結果如圖5所示。

圖5(a)為在Iris數據集固定隱私保護預算為0.50，細分層數（=2,3,4,5,6）下2種算法的分類準確率。從中可以發現，MAXGDDP算法在不同細化層次的條件，其分類準確率都優于DiffGen算法。

圖5(b)為在Adult數據集中固定隱私保護預算為0.50，細分層數（=4,7,10,13,16）下2種算法的分類準確率結果。在細分層數為13時，2種算法均得到最高的分類準確率，而且MAXGDDP算法在各個細分層數上均優于DiffGen算法。

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

圖5 不同細分層數條件下的比較結果

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

圖6 隱私預算幾何分布的影響

6 結束語

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

目前，MAXGDDP算法是利用靜態數據進行隱私保護的數據發布，但是隨著互聯網信息資源的數量和重要性不斷增長，從互聯網上獲取知識變得越來越重要，互聯網環境數據的顯著特征是動態更新，這種數據隨時更新的數據環境稱為動態數據環境。下一步的工作主要研究在動態數據環境下基于差分隱私的數據發布算法。

[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] 熊平, 朱天清, 王曉峰. 差分隱私保護及其應用[J]. 計算機學報, 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] 康海燕, 馬躍雷. 差分隱私保護在數據挖掘中應用綜述[J]. 山東大學學報: 理學版, 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] 張嘯劍, 孟小峰. 面向數據發布和分析的差分隱私保護[J]. 計算機學報, 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

國家自然科學基金資助項目（No.61502146, No.91646203, No.91746115）；河南省自然科學基金資助項目（No.162300410006）；河南省科技攻關基金資助項目（No.142102210384, No.172102310713）；河南省教育廳高等學校重點科研基金資助項目（No.16A520002）；河南省青年骨干教師基金資助項目；河南財經政法大學青年拔尖人才資助計劃基金資助項目

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-），男，河南許昌人，博士，河南財經政法大學副教授，主要研究方向為知識工程、機器學習、隱私保護等。

張嘯劍（1980-），男，河南周口人，博士，河南財經政法大學副教授，主要研究方向為隱私保護、差分隱私、數據庫等。

丁麗萍（1965-），女，山東青州人，中國科學院軟件研究所研究員、博士生導師，主要研究方向為數字取證、系統安全、可信計算等。