一種保護原始數(shù)據(jù)的多屬性值分類挖掘算法

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

關鍵詞：數(shù)據(jù)挖掘； 隱私保護； 分類； 決策樹

中圖分類號：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

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

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

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

1.1 隨機響應技術

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

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

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

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

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

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

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

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

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

2 多屬性值數(shù)據(jù)的隱私保護數(shù)據(jù)挖掘算法

2.1 隱私保護的數(shù)據(jù)變換方法

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

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

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

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

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

輸出：一棵由給定的訓練數(shù)據(jù)產(chǎn)生的決策樹。

a）創(chuàng)建節(jié)點N；

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

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

d）ifattribute_list為空then

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

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

g）標記節(jié)點N為test_attribute ；

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

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

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

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

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

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

信息增益比例是在信息增益概念基礎上發(fā)展起來的。假設整個訓練數(shù)據(jù)集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所有可能取值的個數(shù)；Sj是指數(shù)據(jù)集S中具有屬性A的第j個值aj的集合；|Sj|是指Sj中包括的元素個數(shù)；|S|則是S中包括的元素個數(shù)。信息熵：

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

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

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

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

2.2.2從擾動后的數(shù)據(jù)中計算信息增益比例

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

對于任意一個數(shù)據(jù)集S的信息熵entropy(S)=-∑nj=1Qj log2 Qj。假設數(shù)據(jù)集S是所有具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的數(shù)據(jù)集合。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)表示在整個訓練數(shù)據(jù)中，被調(diào)查數(shù)據(jù)中標志具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的概率；P(a13a24a32)表示在整個訓練數(shù)據(jù)中，被調(diào)查者真正具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值的近似概率。其中，P′(a13a24a32)可以直接從調(diào)查數(shù)據(jù)中得到，可以從以下公式中推導出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)表示在整個訓練數(shù)據(jù)中標志具有屬性A1的第三個值、屬性A2的第四個值、屬性A3的第二個值以及屬于類cj的數(shù)據(jù)的概率；用P(a13a24a32cj)表示在整個訓練數(shù)據(jù)中，被調(diào)查者中實際具有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)

數(shù)據(jù)集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的值為基準對數(shù)據(jù)集S進行劃分，splitl(S，A)實際上也是熵的概念。還是以上面的數(shù)據(jù)集S為例，設屬性A具有k個不同的屬性值；p(aj)表示在數(shù)據(jù)集S中，被調(diào)查者中實際具有A1的第三個值，屬性A2的第四個值，屬性A3的第二個值以及具有屬性A的第j個值aj的數(shù)據(jù)的概率。設P′(a13a24a32aj)表示在整個訓練數(shù)據(jù)集中標志具有屬性A1的第三個值，屬性A2的第四個值，屬性A3的第二個值以及屬性A的第j個值aj的概率；P(a13a24a32aj)表示在整個訓練數(shù)據(jù)中，被調(diào)查者中實際具有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表示整個訓練數(shù)據(jù)的數(shù)據(jù)個數(shù)。

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

3結束語

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

參考文獻：

[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]毛國君，段立娟，王實，等. 數(shù)據(jù)挖掘原理與算法[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]葛偉平. 隱私保護的數(shù)據(jù)挖掘[D]. 上海：復旦大學，2006.

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