一種保護原始數據的多屬性值分類挖掘算法

摘 要：針對基于隨機響應的隱私保護分類挖掘算法僅適用于原始數據屬性值是二元的問題，設計了一種適用于多屬性值原始數據的隱私保護分類挖掘算法。算法分為兩個部分：a)通過比較參數設定值和隨機產生數之間的大小，決定是否改變原始數據的順序，以實現對原始數據進行變換，從而起到保護數據隱私性的目的；b)通過求解信息增益比例的概率估計值，在偽裝后的數據上構造決策樹。

關鍵詞：數據挖掘； 隱私保護； 分類； 決策樹

中圖分類號：TP309 文獻標志碼：A 文章編號：1001-3695(2008)08-2332-03

Algorithm for privacy-preserving classification mining with multivariate data

LI Xing-guo， ZHOU Zhi-chun， LIU Hui

(School of Management， Hefei University of Technology， Hefei 230009， China)

Abstract:Randomized response technique was used in privacy-preserving classification mining， and had acquired good results. But the method was only fit for binary data. To solve this problem， this paper dasigned an algorithm which was fit for multivariate data for privacy-preserving classification mining. The algorithm divided into two parts. In the first part， compared the size of parameter and random generated number to decide whether the sequence of the original data should be changed or not， in order to disguise the original data and then protected the privacy of data. In the second part， estimated the value of gain ratio to build the decision tree on disguised data.

Key words：data mining; privacy-preserving; classification; decision tree

隨著數據挖掘技術的不斷發展，人們對數據挖掘破壞隱私問題的關注不斷上升。例如在問卷調查中，人們對于涉及自己隱私的敏感問題，通常不愿提供真實的數據。而在這些錯誤數據基礎上挖掘出的規則必然具有較低的精確性，有時甚至是完全錯誤的規則。因此，如何在進行數據挖掘的同時保護用戶的隱私數據已經成為近年來數據挖掘研究的熱點之一。近幾年，大量專家、學者在這方面作出許多有益的研究^[1-7]。

1999年，Rakesh Agrawal在KDD99上將隱私保護數據挖掘作為數據挖掘方向未來的研究重點之一^[1]。2003年，Du Wen-liang等人^[2]將隨機響應技術應用于隱私保護分類數據挖掘，但是該算法僅適用于布爾屬性值的數據。本文提出一種新的算法應用于保護隱私的分類挖掘，可以處理多屬性值的原始數據。

1 隨機響應技術在隱私保護分類挖掘算法中的應用

1.1 隨機響應技術

隨機響應(randomized response，RR)技術最初被應用于統計學中，由Warner^[3]率先提出，目的是為了解決以下調查問題：為了估計人群中具有屬性A人群的比例，需要向人群發送問卷。由于A可能涉及人們的隱私問題，一些被調查者可能拒絕回答或者作出與事實不符的回答。相關問題模型(related-question model)和不相關問題模型(unrelated-question modes)被設計用來解決此類問題。

在相關問題模型中，問卷不再直接詢問被調查者是否具有屬性A，取而代之的是兩個答案互為否定的相關問題，例如：a)被調查者具有屬性A；b)被調查者不具有屬性A。

調查者首先確定一個實數θ∈[0，1]，θ≠0.5，被調查者通過隨機數發生器產生一個隨機實數r∈[0，1]。若r＜θ則回答問題1，反之則回答問題2。這樣回答第一個問題的概率為θ，回答第二個問題的概率為1-θ。假設用P′(A=yes)和P′(A=no)來分別表示被調查者回答“yes”和“no”的概率。P(A=yes)表示被調查者中具有屬性A的近似概率，用P(A=no)表示被調查者中不具有屬性A的近似概率。為了估算被調查者中具有屬性的概率，可使用以下方程組：P′(A=no)=P(A=yes)×(1-θ)+P(A=no)×θ。其中，P′(A=yes)和P′(A=no)可以從調查數據中直接得到。當θ≠0.5且被調查者很多時，P(A=yes)和P(A=no)便會比較精確。

1.2 基于隨機響應技術的隱私保護分類挖掘

DU Wen-liang等人提出的算法可以處理具有多個布爾屬性值的分類挖掘。下面簡要介紹該方法。為簡單起見，假設數據是布爾屬性的，并以估算被調查者中具有屬性值E=[(A1=1)Λ(A2=1)Λ(A3=0)]的過程為例子。設P′(110)表示調查數據中屬性值為E=[(A1=1)Λ(A2=1)Λ(A3=0)]的概率；P′(001)表示調查數據中屬性值為E=[(A1=1)Λ(A2=1)ΛA3=0]的概率；P(110)表示被調查者中實際具有屬性值E=[(A1=1)Λ(A2=1)ΛA3=0]的近似概率；P(001)表示被調查者中實際具有屬性值E=[(A1=1)Λ(A2=1)ΛA3=0]的近似概率。其中P′(110)和P′(001)可以從調查數據中直接得到。P(110)和P(001)可以從以下方程組中得到：

P′(E)=P(E)×θ+P(E)×(1-θ)(1)

P′(E)=P(E)×(1-θ)+P(E)×θ(2)

在決策樹分類挖掘中，根據P(E)和P(E)計算gain值，從而選擇分裂屬性進行分裂。

該算法的局限性在于僅能處理屬性值是布爾型的數據。本文提出一種新的隨機響應方法，在進行隱私保護分類挖掘的同時，可以處理多屬性值的原始數據。

2 多屬性值數據的隱私保護數據挖掘算法

2.1 隱私保護的數據變換方法

假設要進行挖掘的數據集上有m個不同的屬性A1，A2，…，Am，各個屬性分別具有v1，v2，…，vm個屬性值；固定各個屬性值的編號，aij表示第i個屬性的第j個值。調查者首先確定一個實數θ∈(0，1)，被調查者通過隨機函數產生一個隨機實數r∈[0，1]，若r＜θ則將各個選擇屬性值1j1ai2j2…ainjn)可以從調查數據中直接得到。

2.2 與決策樹分類算法的結合

決策樹分類法是數據挖掘算法中的重要分支，它從一組無次序、無規則的實例中推理出決策樹表示的分類規則。C4.5算法從ID3算法演變而來，它采用信息增益比例作為屬性選擇的劃分標準來評估劃分，是目前實踐應用中最廣泛的一種決策樹算法。

2.2.1 C4.5決策樹生成算法^[4，5]

輸入：訓練樣本S，候選屬性的集合attribute_list；

輸出：一棵由給定的訓練數據產生的決策樹。

a）創建節點N；

b）if S中的樣本都屬于同一個類C then

c）返回N作為葉節點，以類C標記；

d）ifattribute_list為空then

e）返回N作為葉節點并以S中最普通的類為標記；

f）選擇attribute_list中具有最高信息增益比例的屬性(test_attribute);

g）標記節點N為test_attribute ；

h）fortest_attribute中的所有值αi：

(a)從N上由條件test_attribute=αi長出新的分支；

(b)設Si是S中的數據集，且Si滿足test_attribute=αi；

(c)if Si為空then加上一個葉節點，標記為S的主類；

(d)else遞歸節點C4.5(Si，attribute_list－test_attribute)。

由C4.5的算法描述可以看出，建立決策樹過程中最核心的任務就是計算信息增益比例(gainRatio)，從而為分叉點確定劃分屬性。

信息增益比例是在信息增益概念基礎上發展起來的。假設整個訓練數據集S中有n個類，則屬性A對于樣本集S的信息增益比例用下面公式給出：

gainRatio(S，A)=gain(S，A)/splitl(S，A)(5)

其中，信息增益為

gain(S，A)=entropy(S)-∑kj=1(|Sj|/|S| entropy(Sj))(6)

其中：k表示屬性A所有可能取值的個數；Sj是指數據集S中具有屬性A的第j個值aj的集合；|Sj|是指Sj中包括的元素個數；|S|則是S中包括的元素個數。信息熵：

entropy(S)=-∑nj=1Qj log2 Qj(7)

其中，對于任意數據集S，Qj表示數據集S中的樣本屬于類cj的概率。信息劃分：

splitl(S，A)=-∑kj=1p(aj)log2 p(aj)(8)

其中：k表示屬性A所有可能取值的個數；p(aj)表示數據集S中具有屬性A的第j個值aj的數據的概率。假若以屬性A的值為基準對數據集S進行劃分，splitl(S，A)就是熵的概念。

2.2.2從擾動后的數據中計算信息增益比例

如果數據沒有經過擾亂，計算信息增益比例所需要的值可以直接從原始數據中計算得到。但是在數據經過擾亂后，計算所需要的|S|、|Sj|、Qj、p(aj)無法從原始數據中直接得到，因此必須經過一定的變換得到估算值。下面以一個簡單但不失一般性的例子來說明估算過程。

對于任意一個數據集S的信息熵entropy(S)=-∑nj=1Qj log2 Qj。假設數據集S是所有具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的數據集合。A1、A2、A3分別有v1、v2、v3個屬性值，類C具有n個不同的值(c1，c2，…，cn)，類C也進行了偽裝。

設P′(a13a24a32)表示在整個訓練數據中，被調查數據中標志具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的概率；P(a13a24a32)表示在整個訓練數據中，被調查者真正具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的近似概率。其中，P′(a13a24a32)可以直接從調查數據中得到，可以從以下公式中推導出P(a13a24a32)的估計值：

P′(a13a24a32)=P(a13a24a32)×θ+(1-θ)/v1×v2×v3(9)

P(a13a24a32)=P′(a13a24a32)/θ-(1-θ)/v1×v2×v3×θ(10)

用P′(a13a24a32cj)表示在整個訓練數據中標志具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值以及屬于類cj的數據的概率；用P(a13a24a32cj)表示在整個訓練數據中，被調查者中實際具有A1的第三個值、屬性A2的第四個值、屬性A3的第二個值以及屬于類cj的概率估算值，則可以通過以下公式推導出P(a13a24a32cj)的估計值：

P′(a13a24a32cj)=P′(a13a24a32cj)×

θ+(1-θ)/v1×v2×v3×n(11)

P(a13a24a32cj)=P′(a13a24a32cj)/θ-

(1-θ)/v1×v2×v3×n×θ(12)

數據集S中的樣本屬于類cj的概率Qj可以通過以下公式推導出：

Qj=P(a13a24a32cj)/P(a13a24a32)(13)

對于信息劃分splitl(S，A)=-∑kj=1p(aj)log2p(aj)，假如以屬性A的值為基準對數據集S進行劃分，splitl(S，A)實際上也是熵的概念。還是以上面的數據集S為例，設屬性A具有k個不同的屬性值；p(aj)表示在數據集S中，被調查者中實際具有A1的第三個值，屬性A2的第四個值，屬性A3的第二個值以及具有屬性A的第j個值aj的數據的概率。設P′(a13a24a32aj)表示在整個訓練數據集中標志具有屬性A1的第三個值，屬性A2的第四個值，屬性A3的第二個值以及屬性A的第j個值aj的概率；P(a13a24a32aj)表示在整個訓練數據中，被調查者中實際具有A1的第三個值、屬性A2的第四個值、屬性A3的第二個值以及屬性A的第j個值aj的概率估算值，則p(aj)的估計值可以通過以下公式推導出：

P′(a13a24a32aj)=P(a13a24a32aj)×

θ+(1-θ)/v1×v2×v3×k(14)

P(a13a24a32aj)=P′(a13a24a32aj)/

θ-（1-θ）/v1×v2×v3×k×θ(15)

p(aj)=P(a13a24a32aj)/P(a13a24a32)(16)

而|S|和|Sj|可以通過以下公式推導出：

|S|=m×P(a13a24a32)(17)

|Sj|=m×P(a13a24a32aj)(18)

其中：m表示整個訓練數據的數據個數。

由以上公式可以推導出在數據經過擾動后，計算信息增益比例所需要的各項值的估計值，進而得到信息增益比例的近似值。

3結束語

本文提出一種新的算法，應用于多屬性值原始數據的隱私保護分類挖掘。實驗證明，當值θ接近1且數據量較大時，該算法具有較高的精度。

參考文獻：

[1]AGRAWAL R. Data mining: crossing the chasm[C]// Proc of the 5th ACM SIGKDD Int’l Conference on Knowledge Discovery in Databases and Data Mining. New York: ACM Press，1999:439-450.

[2]DU Weng-liang， ZHAN Zhi-jun. Using randomized response techniques for privacy-preserving data mining[C]// Proc of the 9th ACM SIGKDD InternationalConference on Knowledge Discovery and Data Mining. New York: ACM Press， 2003: 505-510.

[3]WARNER S L. Randomized response: a survey technique for eliminating evasive answer bias[J]. Journal of the American Statistical Association， 1965，60(309):63-69.

[4]QUINLAN J R. C4.5: programs for machine learning[M]. San Francisco: Morgan Kaufmann Publishers， 1993.

[5]毛國君，段立娟，王實，等. 數據挖掘原理與算法[M]. 北京：清華大學出版社，2005: 123-127.

[6]NATWICHAI J， LI Xue， ORLOWSKA M E. A reconstruction-based algorithm for classification rules hiding[C]// Proc of the 17th Australasian Database Conference. Hobart: Australian Computer Society， 2006: 48-58.

[7]葛偉平. 隱私保護的數據挖掘[D]. 上海：復旦大學，2006.

注：本文中所涉及到的圖表、注解、公式等內容請以PDF格式閱讀原文