DiffPRFs：一種面向隨機森林的差分隱私保護算法

穆海蓉，丁麗萍，宋宇寧，盧國慶

（中國科學院軟件研究所基礎軟件國家工程研究中心，北京 100190）

DiffPRFs：一種面向隨機森林的差分隱私保護算法

穆海蓉，丁麗萍，宋宇寧，盧國慶

（中國科學院軟件研究所基礎軟件國家工程研究中心，北京 100190）

提出一種基于隨機森林的差分隱私保護算法DiffPRFs，在每一棵決策樹的構建過程中采用指數(shù)機制選擇分裂點和分裂屬性，并根據(jù)拉普拉斯機制添加噪聲。在整個算法過程中滿足差分隱私保護需求，相對于已有算法，該方法無需對數(shù)據(jù)進行離散化預處理，消除了多維度大數(shù)據(jù)離散化預處理對于分類系統(tǒng)性能的消耗，便捷地實現(xiàn)分類并保持了較高的分類準確度。實驗結果驗證了本算法的有效性以及相較于其他分類算法的優(yōu)勢。

差分隱私；隱私保護；隨機森林；數(shù)據(jù)挖掘

1 引言

隨著信息技術應用的普及和深入，各種信息系統(tǒng)存儲并且積累了豐富的數(shù)據(jù)。對于數(shù)據(jù)的需求極大促進了數(shù)據(jù)的發(fā)布、共享和分析。然而，數(shù)據(jù)集里通常包含著許多個人隱私信息，直接發(fā)布包含敏感信息的數(shù)據(jù)或是對已發(fā)布的數(shù)據(jù)進行分析都有可能造成個人隱私的泄露。隱私保護技術可以解決數(shù)據(jù)發(fā)布和數(shù)據(jù)分析帶來的隱私威脅問題，防止用戶的個人隱私信息或者敏感數(shù)據(jù)的泄露。

差分隱私[1～5]是Dwork在2006年針對統(tǒng)計數(shù)據(jù)庫的隱私泄露問題提出的一種新的隱私定義。在此定義下，對數(shù)據(jù)集的計算處理結果對于某個具體記錄的變化是不敏感的。所以，一個記錄加入到數(shù)據(jù)集中所產(chǎn)生的隱私泄露風險被控制在極小的、可接受的范圍內(nèi)，攻擊者無法通過觀察計算結果而獲取準確的個體信息。差分隱私能夠解決傳統(tǒng)隱私保護模型的2個缺陷：1) 差分隱私保護模型假設攻擊者能掌握最大的背景知識，在這一最大背景知識假設下，差分隱私保護無需考慮攻擊者所擁有的任何可能的背景知識；2) 它對隱私保護進行了嚴格的定義，并提供了量化評估方法。將差分隱私應用于數(shù)據(jù)挖掘中已有一些嘗試，主要研究方向包括分類及回歸分析[7～11]、top-k頻繁模式挖掘[12,13]、聚類等。

分類[6]是一類重要的數(shù)據(jù)挖掘方法，在數(shù)據(jù)預測分析中起著關鍵作用。它找出描述和區(qū)分數(shù)據(jù)類或概念的模型(導出模型是基于對訓練數(shù)據(jù)集的分析)，以便能夠使用模型預測對象的類標號。導出模型可以用多重形式表示，如分類規(guī)則、決策樹、數(shù)學公式或神經(jīng)網(wǎng)絡。決策樹是分類模型的典型代表，它是一種樹形的分類模型，樹內(nèi)節(jié)點表示在某個屬性上的測試，而葉節(jié)點表示一個類。決策樹歸納的學習和分類步驟是簡單和快速的，一般而言，決策樹分類器具有很好的準確率。決策樹是許多商業(yè)規(guī)則歸納系統(tǒng)的基礎，然而決策樹本身以及相應的計數(shù)信息都有可能泄露用戶隱私信息，存在個人隱私泄露的風險。

在決策樹中應用差分隱私已經(jīng)有了一些研究成果。文獻[7]提出了基于交互式框架的應用差分隱私保護的決策樹構建算法SuLQ-based ID3。文獻[8]針對文獻[7]噪聲大的缺點，提出了利用指數(shù)機制挑選分裂屬性的DiffP-ID3和DiffP-C4.5決策樹分類方法。另外文獻[9,10]基于非交互式框架，利用數(shù)據(jù)泛化（在數(shù)據(jù)挖掘研究中,將與挖掘任務相關的數(shù)據(jù)集從較低的概念層抽象到較高的概念層的處理過程）的方法，對數(shù)據(jù)進行匿名處理并發(fā)布，提高了分類的精度。文獻[11]將差分隱私應用在決策樹提升算法隨機森林中，但提出的算法基于只能處理離散屬性的 ID3決策樹，因此需要對連續(xù)屬性進行預處理后才能對數(shù)據(jù)集進行分類。

根據(jù)這些研究及存在的問題，本文提出一種基于差分隱私保護的隨機森林分類方法。該方法相對于已有算法，消除了數(shù)據(jù)離散化的預處理步驟，便捷地實現(xiàn)分類并保持了較高的分類準確度，兼顧決策樹分類的隱私性與可用性及分類實現(xiàn)的效率。

2 理論基礎及相關研究

2.1 差分隱私背景知識

定義1 ε-差分隱私[1]。對于所有差別至多為一條記錄的 2個數(shù)據(jù)集D1和D2，給定一個隱私算法F，Range(F)表示F的取值范圍。若算法F提供ε-差分隱私保護，則對于所有S∈Range(F)，有

概率Pr[Es]表示事件Es的隱私被披露風險，由算法F隨機性所控制，隱私預算ε表示隱私保護程度，ε越小隱私保護程度越高。

從定義可以看出，差分隱私技術限制了任意一條記錄對算法F的輸出結果的影響。定義從理論角度確保算法F滿足ε-差分隱私，實現(xiàn)差分隱私保護則需要使用噪聲機制。

噪聲機制是實現(xiàn)差分隱私保護的主要技術，常用的噪聲添加機制是拉普拉斯機制[4]和指數(shù)機制[5]?；诓煌肼暀C制且滿足差分隱私的算法所需噪聲大小與全局敏感性(global sensitive)相關。

定義 2 對于任意一個函數(shù)f:D→Rd，f的全局敏感性[4]定義為

數(shù)據(jù)集D1和D2之間至多相差一條記錄。R表示映射的實數(shù)空間，d表示函數(shù)f的查詢維度。

拉普拉斯機制通過拉普拉斯分布產(chǎn)生的噪聲擾動真實輸出值來實現(xiàn)差分隱私保護。

定理 1 拉普拉斯機制[4]，對于任一函數(shù)，若算法F的輸出結果滿足下列等式，則F滿足ε-差分隱私保護。

定理2 指數(shù)機制[5]，設隨機算法M輸入為數(shù)據(jù)集D，輸出為一實體對象r∈Range ，q(D, r)為可用性函數(shù)，Δq為函數(shù)q(D, r)的敏感度。若算法M以正比于的概率從Range中選擇并輸出r，那么算法M提供ε-差分隱私保護。

2.2 隨機森林

隨機森林[14]指的是利用多棵樹對樣本進行訓練并預測的一種分類器。簡單來說，隨機森林由多棵決策樹構成，并且其輸出的類別是由單棵決策樹輸出的類別的眾數(shù)而定。Leo和 Adele最早提出了執(zhí)行隨機森林的關鍵算法。Amit、Gemen和Ho Tim Kam各自獨立地介紹了特征隨機選擇的思想，并且運用了Breiman的bootstrap aggregating思想構建了控制方差的決策樹集合。

2.2.1 訓練方法與分類方法

隨機森林的訓練和分類過程可以總結如下。

輸入：訓練數(shù)據(jù)集S，屬性集F，分類屬性集C生成的決策樹的數(shù)量t，每棵樹的深度d，每個節(jié)點使用到的屬性數(shù)量f

終止條件：節(jié)點全部記錄的分類屬性一致，或達到最大深度d

輸出：隨機森林

2) 隨機地從屬性集F中選取f個屬性；

3) 從 f個屬性中尋找分類效果最好的屬性 k作為分裂屬性，將當前節(jié)點上樣本第k維屬性按照分類結果被劃分到子節(jié)點

利用隨機森林的預測過程如下。

對于第k棵樹：

1) 從當前樹的根節(jié)點開始，根據(jù)當前節(jié)點的分類結果集合，判斷是進入哪個子節(jié)點，直到到達某個葉子節(jié)點，并輸出預測值；

2) 重復執(zhí)行 1)直到所有 t棵樹都輸出了預測值。對于分類問題，輸出為所有樹中預測概率總和最大的那一個類，即對每個c(j)的p進行累計。

2.2.2 隨機森林的特點

隨機森林的優(yōu)點如下。

1) 在大數(shù)據(jù)集上表現(xiàn)良好，2個隨機性的引入使隨機森林不容易陷入過度擬合，并且具有很好的抗噪聲能力。

2) 能夠處理很高維度的數(shù)據(jù)，它可以處理非常多的輸入變量，并確定最重要的變量，因此被認為是一個不錯的降維方法。

3) 訓練過程速度快，可以得到屬性重要性排序。

4) 容易做成并行化方法。

5) 實現(xiàn)比較簡單。

隨機森林的缺點如下。

1) 隨機森林在解決回歸問題時因為不能給出一個連續(xù)型的輸出，導致其并沒有像分類中表現(xiàn)的那么好。當進行回歸時，隨機森林不能夠作出超越訓練集數(shù)據(jù)范圍的預測，這可能導致在對某些含有特定噪聲的數(shù)據(jù)進行建模時出現(xiàn)過度擬合。

2) 隨機森林讓統(tǒng)計建模者感到幾乎無法控制模型內(nèi)部的運行，只能在不同的參數(shù)和隨機種子之間進行嘗試。

2.3 已有研究的對比

本課題重點關注決策樹分類與差分隱私的結合。由于分類屬性高維度的特點，給差分隱私保護技術在決策樹構建過程中的應用帶來了很大的挑戰(zhàn)。

表1展示了當前在交互式框架與非交互式框架下，基于差分隱私的決策樹分類方法的研究進展。

表1 差分隱私下分類方法對比分析

SuLQ-based ID3算法[7]基于交互式框架，其基本思想是在每次計算屬性的信息增益時，使用加入噪聲的計數(shù)值，最終生成相應的決策樹。從對模擬數(shù)據(jù)集的實驗結果來看，在隱私保護預算小于 1的情況下，該算法相對于無隱私保護功能的ID3算法，其預測準確率大約降低了30%[8]。

Friedman 和 Schuster 基于 PINQ 平臺對SuLQ-based ID3算法進行了改進，利用其中的Partition算子將數(shù)據(jù)集分割成不相交的子集，然后再實現(xiàn)ID3算法。但由于每個查詢的預算相對很小，所以無法顯著降低SuLQ-based ID3所引入的噪聲。Friedman和Schuster 進一步在ID3算法中應用指數(shù)機制實現(xiàn)差分隱私保護，提出了DiffP-ID3算法[8]，有效降低了噪聲。另外，通過將離散屬性的處理擴展到連續(xù)屬性，F(xiàn)riedman 和 Schuster 還提出了DiffP-C4.5算法[8]。DiffP-C4.5算法的缺點在于，在每一次迭代中必須先用指數(shù)機制對所有連續(xù)屬性選擇分裂點，然后將所得結果與全部離散屬性一起再次通過指數(shù)機制選擇最終的分裂方案，由于每次迭代需要調(diào)用指數(shù)機制2次，因此消耗了過多的隱私保護預算。

DiffGen算法[9]結合泛化(generalization)技術與自頂向下分割技術，結合指數(shù)機制與信息增益來確定分裂屬性。自頂向下劃分數(shù)據(jù)集D中所有記錄到?jīng)Q策樹的葉子節(jié)點，然后對葉子節(jié)點添加拉普拉斯噪聲。實驗結果表明，DiffGen方法的分類精度高于SuLQ-based ID3和DiffP-C4.5方法，但是由于該方法每一個分類屬性對應一個分類樹，當數(shù)據(jù)集中的分類屬性維度非常大時，該方法不得不維護大量的分類樹，導致基于指數(shù)機制的選擇方法效率很低，并且有可能耗盡隱私預算。

DT_Diff算法[10]對 DiffGen和DiffP-C4.5中的問題進行了改進，將所有連續(xù)屬性細分方案乘以相應的權重后和離散屬性細分方案一起構成候選方案集，再調(diào)用指數(shù)機制來選擇細分方案。這樣做減少了調(diào)用指數(shù)機制的次數(shù)，從而提高了隱私預算的利用率，使在給定的隱私預算下，數(shù)據(jù)集能夠更大程度地精確化，從而提高分類模型的準確率。

Abhijit Patil和Sanjay Singh將差分隱私應用在決策樹提升算法隨機森林中，提出了DiffPRF算法[11]，但提出算法基于只能處理離散屬性的ID3決策樹，因此需要先對連續(xù)屬性進行預處理后才能通過該算法對數(shù)據(jù)集進行分類。

上述幾種方法無論是基于交互式框架還是非交互式框架，其核心技術均為決策樹和拉普拉斯/指數(shù)機制，并且使用信息增益來選擇分裂規(guī)則。但是它們或多或少存在一些問題，主要有2點不足：1)當數(shù)據(jù)集中分類屬性的維度非常大時，導致基于指數(shù)機制的選擇方法效率很低；2)隱私預算分配策略過于單一，急需有效的策略。因此，如何對具有高維度分類屬性的數(shù)據(jù)集進行分類，以及如何設計有效的隱私預算分配策略，是未來的研究方向。本文提出的方法基于隨機森林的特性，提高了對大數(shù)據(jù)集、高維數(shù)據(jù)集分類時使用指數(shù)機制的效率，并且支持直接對連續(xù)屬性的分類，而不需先對高維連續(xù)屬性進行離散化，實驗結果驗證了本算法有較高的分類準確度。

3 算法及性能分析

本文提出一種差分隱私下的隨機森林分類方法，將差分隱私應用在隨機森林當中，在可接受的分類準確度下盡可能保護數(shù)據(jù)的隱私。

3.1 DiffPRFs算法框架

差分隱私下的隨機森林建立過程描述如下。

輸入：訓練數(shù)據(jù)集S，屬性集F，分類屬性集C，隱私預算B，生成的決策樹的數(shù)量t，每棵樹的深度d，每個節(jié)點使用到的屬性數(shù)量f

終止條件：節(jié)點全部記錄的分類屬性一致，達到最大深度d或隱私預算耗盡

輸出：滿足ε-差分隱私的隨機森林

2) for b=1 to t

3) 從S中有放回的隨機選取大小為|S|的訓練集S(i)；

8) 隨機地從屬性集F中選取f個屬性；

9) 若隨機選擇的f個屬性中包含n連續(xù)屬性，執(zhí)行步驟10)，否則，直接執(zhí)行步驟11)；

用以下概率選擇每個連續(xù)屬性的分裂點

12) 按照分裂屬性將當前節(jié)點分為2個子節(jié)點

通過以上算法建立的隨機森林對測試集進行分類的過程描述如下。

輸出：測試集中每條記錄的分類結果

1) 對于測試集T每一條記錄x；

2) for b=1 to t；

3) 從當前樹的根節(jié)點開始，根據(jù)當前節(jié)點的分類結果集合，判斷是進入哪個子節(jié)點，直到到達某個葉子節(jié)點;

3.2 算法實現(xiàn)細節(jié)

差分隱私下的隨機森林分類方法DiffPRFs分2步來實施，具體步驟如下。

1) 通過訓練數(shù)據(jù)集建立隨機森林

輸入：訓練數(shù)據(jù)集S，屬性集F，分類屬性集C，隱私預算B，生成的決策樹的數(shù)量t，每棵樹的深度d

終止條件：節(jié)點全部記錄的分類屬性一致，達到最大深度d或隱私預算耗盡

輸出：滿足ε-差分隱私的隨機森林

首先根據(jù)參數(shù)中樹的棵數(shù)，將隱私預算B均分給t棵樹；之后按照同樣的規(guī)則遞歸地生成每一棵決策樹。生成決策樹的策略如下。

2) 利用建立的隨機森林對測試數(shù)據(jù)集進行分類

輸出：測試集中每條記錄的分類結果

對測試集中的每一條記錄，應用森林中的每一棵樹對其進行分類預測。在每一個節(jié)點上都根據(jù)當前節(jié)點的分類結果集合判斷該條記錄應進入哪一個子節(jié)點，直到到達某個葉子節(jié)點，通過當前葉子節(jié)點ε獲得一個預測值。根據(jù)森林中每棵樹的預測結果得到所有預測結果中概率最大的那個分類結果。之后輸出所有記錄的分類結果。

由于隨機森林在大數(shù)據(jù)集上表現(xiàn)良好，能夠處理很高維度（即屬性較多）的數(shù)據(jù)，并且訓練速度快，這些優(yōu)點能夠很好地解決此前方法中問題，實現(xiàn)對高維度大規(guī)模數(shù)據(jù)的高準確度預測分類。

3) 可用性函數(shù)

設S為數(shù)據(jù)集，s=|S|，分類屬性C有m個不同取值，即定義了m個不同的類

在算法中為了度量用每個屬性進行分類、用不同的分裂點對連續(xù)屬性進行劃分的可用性水平，選用以下2種可用性函數(shù)。

一種是基于信息增益[15]的可用性函數(shù)，即

計算數(shù)據(jù)集S的熵為

其中，pi是S中任意元素屬于類Ci的非零概率，使用估計。

假設按屬性A劃分S中的元組，A根據(jù)訓練數(shù)據(jù)集有v個不同值使用屬性A將S劃分為u個子集，基于按A劃分對S中的元組分類所需的期望信息為

用其分類產(chǎn)生的信息增益為

3.3 算法隱私性分析

DiffPRFs算法中將給定的隱私預算B首先平均分給森林中的每一棵樹，由于每棵樹中的樣本是隨機選擇的，因此會有一定的交叉，根據(jù)差分隱私序列組合性，隨機消耗的隱私預算為每棵決策樹消耗隱私預算的疊加。樹的每一層包括葉子節(jié)點都是相同的數(shù)據(jù)集，因此平均分配了隱私預算。每一層因為在不相交的數(shù)據(jù)集上進行技術和分裂，因此每個節(jié)點分配的隱私預算就是這一層的隱私預算。根據(jù)差分隱私的并行組合性[16]，節(jié)點的隱私預算不進行累加。分給每個節(jié)點的隱私預算一半用來估計該節(jié)點的實例數(shù)(應用拉普拉斯機制)，另一半需要根據(jù)該節(jié)點是中間節(jié)點還是葉節(jié)點進行區(qū)分，若該節(jié)點為葉節(jié)點，需要用剩下的這一半隱私預算來確定類計數(shù)，同樣使用拉普拉斯機制對計數(shù)值添加噪聲。若該節(jié)點為中間節(jié)點，假設從F個屬性中隨機選出的f個屬性有n個連續(xù)屬性，將隱私預算均分為n+1份，選擇每個連續(xù)屬性的分裂點，之后從所有屬性中選擇出該節(jié)點的分裂屬性，選擇分裂點與分裂屬性時均使用指數(shù)機制進行選擇，每次使用指數(shù)機制消耗的隱私預算為，按照差分隱私的序列組合性[16]，多次指數(shù)機制消耗的隱私預算為各次的疊加。所以，算法所消耗的全部隱私預算不大于B，它具有ε?差分隱私性。

生成的這些決策樹組成滿足ε?差分隱私的隨機森林。每棵樹的訓練樣本是隨機選擇的，樹中每個節(jié)點屬性也是隨機選擇的。每個節(jié)點上屬性的個數(shù)一般為整個屬性個數(shù)的均方根，這樣也就一定程度上解決了高維度帶來的問題。

4 實驗結果

4.1 實驗環(huán)境及數(shù)據(jù)

本文的分類器數(shù)據(jù)處理、訓練和測試算法均采用python2.7實現(xiàn)。實驗環(huán)境為OS X Yosemite四核2.8 GHz，內(nèi)存 16 GB 1 600 MHz DDR3。本文以 UCI機器學習數(shù)據(jù)庫中的 adult數(shù)據(jù)集檢驗算法的有效性，并在相同的測試條件下與其他算法進行比較。UCI adult包含訓練集與測試集，其中，包含6個連續(xù)屬性與8個離散屬性。分類屬性income level分為“≤50k”與“≥50k”2類。訓練集中包含45 222條記錄，測試集中包含15 060條記錄。

4.2 實際數(shù)據(jù)集測試結果

在ε=0.05、0.1、0.25、0.5、0.75、1、2，t=25，每棵樹的深度d=3、4、5、6、7，可用性函數(shù)使用信息增益和最大類頻數(shù)和的設置下進行了多組實驗。每組實驗在給定的隱私預算和樹的深度下使用DiffPRFs算法對訓練數(shù)據(jù)集建立隨機森林分類模型，并用該模型對測試數(shù)據(jù)集進行分類，記錄相應的分類準確度。每組實驗進行5次，以5次結果平均值作為最終結果。實驗結果如圖1所示。

從圖1中可以看出，當ε取值較小的時候，由訓練集訓練出的隨機森林分類器分類準確度較低，而隨著ε取值增大，分類正確率雖然偶有波動，但總體趨勢是逐漸提高的。這是因為隨著ε逐漸增大，較優(yōu)的方案被選擇的幾率也隨之提高。隨著決策樹深度的增加，記錄經(jīng)過了更多屬性的篩選，分類的準確度也逐漸提高。另外2種可用性函數(shù)的準確度也非常類似，趨勢上也均符合預期。

圖1 不同條件下的DiffPRFs分類準確度

本文還設定d=5，ε=0.1、0.25、0.5、0.75、1，t=25，將提出的算法 DiffPRFs與不加入差分隱私的隨機森林算法、DiffPRF算法進行比較。其中不加差分隱私的隨機森林算法由本文提出的算法修改實現(xiàn)、DiffPRF算法同等條件下的分類準確度由文獻[11]提供。實驗結果如圖2所示。

圖2 與隨機森林及DiffPRF的比較

通過與隨機森林算法以及DiffPRF算法的比較可以看出，本文提出的算法可以達到較高的分類準確度。雖然在構建決策樹的過程中消耗了一定的隱私預算處理連續(xù)屬性，但不需對連續(xù)屬性進行離散化預處理，面對大規(guī)模高維度的數(shù)據(jù)，將連續(xù)屬性離散化十分費時費力，因此在構建決策樹的過程中進行直接處理一定程度上提高了分類的效率。在這樣的情況下分類準確度相對于DiffPRF算法只降低了非常有限的一點，這是可以接受的。本算法在保證數(shù)據(jù)安全性的前提下，提供了更加便捷高效的分類方法，連續(xù)屬性與離散屬性都可以直接處理，同時也保證了數(shù)據(jù)的可用性。

5 結束語

本文提出了一種面向隨機森林的差分隱私保護算法DiffPRFs，用于對數(shù)據(jù)構建分類器并且進行分類。通過對DiffPRF算法中指數(shù)機制方案選擇的改進，使構建的隨機森林可以在決策樹構建過程中有效地處理連續(xù)屬性，而不需要在構造隨機森林前預先進行處理，避免了對高維度、大規(guī)模數(shù)據(jù)進行離散化的高額成本。實驗結果證明本算法相較于DiffPRFs算法的分類準確度并沒有明顯降低，從而顯示了該算法的優(yōu)越性。當然由于建立了多棵決策樹，每棵樹分配的隱私預算相對較少，一定程度上影響了分類的準確度，接下來的工作中會繼續(xù)嘗試對算法進行進一步優(yōu)化，提升分類的準確度；也會嘗試在其他一些決策樹的提升算法中應用差分隱私，以期得到更好的分類準確度。

[1] DWORK C. Differential privacy[C]//The 33rd International Colloquium on Automata, Languages and Programming. Berlin:Spinger-Verlag, 2006: 1-12.

[2] DWORK C. A firm foundation for private data analysis[J]. Communications of the ACM, 2011, 54(1):86-95.

[3] 張嘯劍, 孟小峰. 面向數(shù)據(jù)發(fā)布和分析的差分隱私保護[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.

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

[5] MCSHERRY F, TALWAR K. Mechanism design via differential privacy[C]//Foundations of Computer Science. 2007: 94-103.

[6] 范明, 孟小峰, 譯. 數(shù)據(jù)挖掘: 概念與技術[M]. 北京: 機械工業(yè)出版社, 2012.FAN M MENG X F. Data minify: concepts and techniques[M]. Beijing China Machine Press, 2012.

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

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

[9] 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. ACM,2011: 493-501.

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

[11] PATIL A, SINGH S. Differential private random forest[C]//Advances in Computing, Communications and Informatics International Conference. IEEE, 2014: 2623-2630.

[12] 丁麗萍, 盧國慶. 面向頻繁模式挖掘的差分隱私保護研究綜述[J].通信學報, 2014, 35(10): 200-209.DING L P, LU G Q. Survey of differential privacy in frequent pattern minify[J]. Journal on Communications, 2014, 35(10): 200-209.

[13] 盧國慶, 張嘯劍, 丁麗萍, 等. 差分隱私下的一種頻繁序列模式挖掘方法[J]. 計算機研究與發(fā)展, 2015, 52(12): 2789-2801.LU G Q, ZHANG X J, DING L P, et al. Frequent sequential pattern mining under differential privacy[J]. Journal of Computer Research and Development, 2015, 52(12) : 2789-2801.

[14] BREIMAN L. Random forests[J]. Machine Learning, 2001, 45(1):5-32.

[15] QUINLAN J R. Induction of decision trees[M]//Readings in Knowledge Acquisition and Learning．San Francisco: Morgan Kaufmann Publishers Inc，1993: 349-361．

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

DiffPRFs: random forest under differential privacy

MU Hai-rong, DING Li-ping, SONG Yu-ning, LU Guo-qing
(National Engineering Research Center of Fundamental Software, Institute of Software, Chinese Academy of Sciences, Beijing 100190, China)

A differential privacy algorithm DiffPRFs based on random forests was proposed. Exponential mechanism was used to select split point and split attribute in each decision tree building process, and noise was added according to Laplace mechanism. Differential privacy protection requirement was satisfied through overall process. Compared to existed algorithms, the proposed method does not require pre-discretization of continuous attributes which significantly reduces the performance cost of preprocessing in large multi-dimensional dataset. Classification is achieved conveniently and efficiently while maintains the high accuracy. Experimental results demonstrate the effectiveness and superiority of the algorithm compared to other classification algorithms.

differential privacy, privacy protection, random forest, data mining

The National High Technology Research and Development Program of China(863 Program) (No.2015AA016003)

TP309.2

A

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

2016-01-11；

2016-03-16

國家高技術研究發(fā)展計劃（“863”計劃）基金資助項目（No.2015AA016003）

穆海蓉（1990-），女，山西太原人，中國科學院軟件研究所碩士生，主要研究方向為差分隱私保護、數(shù)據(jù)挖掘。

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

宋宇寧（1985-），男，黑龍江哈爾濱人，中國科學院軟件研究所工程博士生，主要研究方向為差分隱私保護、數(shù)據(jù)挖掘。

盧國慶（1989-），男，山東章丘人，中國科學院軟件研究所碩士生，主要研究方向為差分隱私保護、數(shù)據(jù)挖掘。