應用正交變換保護數(shù)據(jù)中的隱私信息

摘 要：針對聚類分析時如何保護隱私的問題，從傳統(tǒng)的數(shù)據(jù)安全度評價標準出發(fā)，重新拓展了一般實數(shù)上有限維歐氏空間中隱私保護度的評價指標，提出了一種稱為OBT（基于正交變換的數(shù)據(jù)轉換方法）的算法，OBT中正交矩陣的選擇不依賴于具體數(shù)據(jù)，能夠很好地應用于大容量的數(shù)據(jù)庫上，在應用正交變換保護數(shù)據(jù)中的隱私信息時不需要進行大量的運算。

關鍵詞：數(shù)據(jù)挖掘； 隱私保護； 聚類分析； 正交變換

中圖法分類號：TP309 文獻標識碼：A 文章編號：1001-3695(2006)10-0095-03

Privacy Preserving Clustering by Isometric Transformation

ZHANG Guorong1， YIN Jian2

(1.Computer Staff Room， Guangzhou Academy of Fine Arts， Guangzhou Guangdong 510260， China; 2.School of Information Science Technology， Sun Yatsen University， Guangzhou Guangdong 510275， China)

Abstract:This paper is concentrated on the issue of protecting the underlying attribute values when sharing data for clustering and systemically discuss the process which preserves privacy information by Orthogonal Transformation. On the basis of traditionally measure of security， this paper extends the measure of privacy preserving in Euclidean space and proposes a privacy preserving method called OrthogonalBased Transformation (OBT). OBT doesn’t depend on concrete data and it makes the process needn't a great deal computation which preserves privacy information by Orthogonal Transformation.

Key words:Data Mining; Privacy Preserving; Clustering Analysis; Orthogonal Transformation

隨著數(shù)據(jù)挖掘技術的發(fā)展，大量的私人信息如購物習慣、犯罪記錄、病史、信用記錄等通過應用數(shù)據(jù)挖掘技術被廣泛地收集和分析。人們發(fā)覺數(shù)據(jù)挖掘技術可能對隱私和信息安全構成威脅。目前，為了保護數(shù)據(jù)挖掘中的隱私，防止收集的數(shù)據(jù)被誤用，人們已經(jīng)提出了多種解決方法。本文主要考慮如何保護初始數(shù)據(jù)中的隱私信息，為了解決這個問題，需要兩個重要的技術：①在隱私保護的第一階段匿名化身份信息（如姓名、社會保險號、地址等）；②對一些敏感信息（如工資、年齡等）進行轉換，因為這些信息可能通過連接到另外的數(shù)據(jù)庫就可以判斷出個人的身份[1]。本文更關注后者的技術，主要考慮在進行聚類分析時，如何通過轉換機密的數(shù)字信息來達到隱私保護的目的。

1 相關工作

保護隱私的數(shù)據(jù)挖掘已經(jīng)成為數(shù)據(jù)挖掘研究中的一個重要領域，越來越吸引密碼學、統(tǒng)計學等相關學科的學者參與其中。根據(jù)考慮對象的不同，目前的解決方法主要分為兩類：①初始數(shù)據(jù)隱私保護，即對初始數(shù)據(jù)進行扭曲、擾亂、隨機化和匿名化。這是因為初始數(shù)據(jù)中可能含有不能公開的個人隱私信息，如姓名、身份證號碼、年齡、工資等。②分布式數(shù)據(jù)隱私保護，即在雙方或多方合作進行數(shù)據(jù)挖掘時，由于某種原因，參與者往往不愿意將數(shù)據(jù)與他人共享而只愿共享數(shù)據(jù)挖掘的結果。這種情況在科學研究、醫(yī)學研究及經(jīng)濟和市場動態(tài)研究等方面屢見不鮮。這就要求人們提出保持隱私性的數(shù)據(jù)挖掘算法，對于參與者而言，只能獲得最終的挖掘結果，除此以外，不能獲得他人的其他任何信息。

對于聚類分析中的隱私保護問題已經(jīng)有一些很好的解決方法。Vaidya等人[2]提出了應用于垂直分布類型的聚類分析的方法，主要是使得每個站點在得到聚類結果時，不會泄露自己站點內(nèi)部的事務屬性值。而對于聚類分析的初始數(shù)據(jù)隱私保護方法，Stanley R.M.Oliveira等人提出的通過幾何數(shù)據(jù)轉換達到聚類隱私保護的方法[1]，主要通過幾何轉換如平移、縮放和簡單的旋轉等轉換初始數(shù)據(jù)。但是這個方法容易改變數(shù)據(jù)的相似性，從而造成聚類的誤差，同時，這個方法對于空間的維數(shù)也是有限制的。后來Stanley R.M.Oliveira等人再次提出保持空間距離不變的基于旋轉的轉換（RBT）方法[3]，實現(xiàn)了多維空間中點的等距變換，達到了很好的隱私保護效果。

本文針對聚類分析時如何保護隱私的問題對應用正交變換保護數(shù)據(jù)中的隱私信息進行了系統(tǒng)的討論。從傳統(tǒng)的數(shù)據(jù)安全度[4]評價方法出發(fā)，著重討論兩個不同的評價指標——距離和方向；最后給出一個不依賴具體數(shù)據(jù)的隱私保護方法，使得在應用正交變換保護數(shù)據(jù)中的隱私信息時不需要進行大量的運算。

2 隱私保護度評價方法

2．1 一般的隱私保護度評價方法

為了對比不同變換對隱私的保護程度，一般的方法是借助數(shù)據(jù)庫中評估數(shù)據(jù)安全的方法來評估隱私的保護程度。傳統(tǒng)上，數(shù)據(jù)擾亂后的安全度可以通過對比實際數(shù)據(jù)和擾亂數(shù)據(jù)的不同來測量(Adam and Wortmann，1989)。隱私的保護程度一般是由式（1）評估的[1]：

P=Var(X-X′)（1）

其中，X表示擾亂前的一維屬性值，X′表示擾亂后的一維屬性值，且

Var(X)=Var(x1，x2，…，xN)=1N×∑Ni=1(xi-x)2（2）

其中，x是x1，x2，…，xN的平均值。

2．2 拓廣的隱私保護度評價方法

一個變換為等距變換的充要條件是對應的變換矩陣是正交矩陣，因此本文直接討論應用正交變換來保護數(shù)據(jù)中的隱私信息。與RBT方法[3]不同的是，本文中原始數(shù)據(jù)和變換后的數(shù)據(jù)被看作是一個n維歐氏空間中的點集或n維向量的集合，用X和X′表示，即

X=x11x12…x1N

x21x22…x2N

…

xn1xn2…xnN

其中，n是屬性的個數(shù)，每一行表示一個屬性的取值，N是集合的容量，也表示點的個數(shù)，容易證明平移不影響隱私保護度，所以正交變換可以簡單寫成X′=AX。

（1）基于距離的隱私保護度評價

把一維數(shù)據(jù)的安全度評價公式推廣到一般的歐氏空間En，用d(x，y)表示En中兩點x，y的距離，可以把Var(X)寫成

Var(X)=Var(x1，x2，…，xN)=1N×∑Ni=1d(xi，x)2（3）

其中，x是X中點x1，x2，…，xN的重心。

可以得到與一般的隱私保護度評價方法中一維情形形式完全相同的n維歐氏空間中一個變換T或一個矩陣A的隱私保護度評價公式：

S=Var(X-X′)/Var(X)=Var(X-AX)/Var(X)（4）

（2）基于方向的隱私保護度評價

基于距離的隱私保護度評價沒有考慮方向上的變化所帶來的復雜度，因此必須給出方向隱私保護度的定義來彌補這個缺陷。把X′=AX展開如下：

x1′

x2′



xn′=a11a12…a1n

a21a22…a2n

…

an1an2…ann x1

x2



xn=∑ni=1a1ixi

∑ni=1a2ixi



∑ni=1anixi

其中，xi是X的行向量，xi′是X′的行向量，也就是變換前后數(shù)據(jù)矩陣的屬性行。

用概率的方差模型來對每一行元素所提供的變化復雜度進行量化，具體模型和求解結果如下，對第i行（i=1，2，…，n）：

（1）把元素aij取絕對值，并且除以絕對值之和以標準化為bij。

（2）εj表示分量j等于1的單位向量。

（3）建立概率模型：隨機變量Ri，取值為εj的概率bij，j=1，2，…，n。

E(Ri)=∑nj=1bijεj，令vi=∑nj=1|aij|

ci=D(Ri)=∑nj=1bij|εj-E(Ri)|2=∑nj=1bij((1-bij)2-b2ij+∑nk=1b2ik）=

∑nj=1bij(1-2bij+1v2i)=∑nj=1bij(1+1v2i)+∑nj=1bij(-2bij)=1-1v2i

用變換矩陣每一行的方向隱私度相乘來表示變換的方向隱私保護度，即有

R(A，X)=c1×c2×…×cn=(1-1v21)(1-1v22)…(1-1v2n)（5）

最后用兩種不同的標準來評價一個變換的隱私保護度：

P(A，X)=R(A，X)×S(A，X)（6）

3 基于正交變換的數(shù)據(jù)轉換算法(OBT)

本文在RBT的基礎上提出基于正交變換的轉換方法（OBT），利用證明的定理預先建立矩陣庫，使得變換時無須進行大量的運算。當然，在變換的時候并不總需要對原始數(shù)據(jù)的所有n個屬性進行變換，出于效率的考慮，最常見的情形是分步對若干個屬性聯(lián)合進行變換。事實上，對一個屬性聯(lián)合的一次正交變換相當于對所有屬性聯(lián)合做了一次正交變換，并且正交變換對乘法封閉，這保證了進行一系列對屬性聯(lián)合的正交變換的結果是最終對原始數(shù)據(jù)進行了一個正交變換。

定理 如果X經(jīng)過zscore標準化，并且各個屬性兩兩獨立，則lim|X|→+∞PVar((E-A)X)Var(X)-tr(E-A)T(E-A)n≥ε=0，記作Var((E-A)X)Var(X) p tr(E-A)T(E-A)n。

證明：(E-A)T(E-A)是實對稱矩陣，有n個正交單位特征向量γ1，γ2，…，γn，γ1，γ2，…，γn分別對應的特征值是λ1，λ2，…，λn，λ1+λ2+…+λn=tr((E-A)T(E-A))。

可以把X中的點x看作隨機變量，x=(x1，x2，…，xn)，令f2=∑ni=1x2i，由于X經(jīng)過標準化，

E(x2i)=E(x2i-E(xi))=D(xi)=1，i=1，2，…，n（7）

E(f2）=E(∑ni=1x2i)=∑ni=1E(x2i)=n，令D(f2)=g（8）

設x在基（γ1，γ2，…，γn）下的分解式為x=∑ni=1ciγi，如果在標準基與基(γ1，γ2，…，γn)之間的過渡矩陣為P，則ci=∑nk=1pikxk，P是正交矩陣。

由于x1，x2，…，xn兩兩獨立，則

E(c2i)=D(ci)=∑nk=1p2ikD(xk)=∑nk=1p2ik=1，令D(c2i)=gi（9）

下面考慮X={X1，X2，…，XN}，其中Xj是X集合中的點，且與x同分布，記

Xj=x1j

x2j



xnj ， (j=1，2，…，N)

令f2j=∑ni=1x2ij，則f2j與f2同分布。

由式（8）得

E∑Nj=1f2jN=∑Nj=1E(f2j)N=∑Nj=1E(f2)N=nNN=n（10）

limN→+∞D∑Nj=1f2jN=limN+∞∑Ni=1D(f2)N2=limN+∞gN=0（11）

由式（10）、式（11）和車貝謝夫不等式得

∑Nj=1f2jN pn（12）

又由Xp0

故VarX=∑Nj=1(Xj-X)T(Xj-X)N p ∑Nj=1XTjXjN=∑Nj=1f2jN p n（13）

另外，與上面相同，利用過渡矩陣P可得

cij=∑nk=1pikxkj且cij和ci同分布，i=1，2，…，n，j=1，2，…，N

所以E∑Nj=1c2ijN=∑Nj=1E(c2i)N=1，i=1，2，…，n（14）

limN→+∞D∑Nj=1c2ijN=limN→+∞∑Nj=1D(c2i)N2=limN→+∞giN=0，i=1，2，…，n（15）

由式（14）、式（15）得

∑Nj=1c2ijN p 1，i=1，2，…，n（16）

由式（13）、式（16）得

∑Nj=1c2ijNVarXp 1n(17)

最后，Var((E-A)X)VarX=1N∑Nj=1(Xj-X)T(E-A)T(E-A)(Xj-X)VarXp

1N∑Nj=1XTj(E-A)T(E-A)XjVarX=1N∑Nj=1(∑ni=1cijγi)T(E-A)T(E-A)(∑ni=1cijγi)VarX=

1N∑Nj=1(∑ni=1cijγi)T(∑ni=1cijλiγi)VarX=1N∑Nj=1∑ni=1λic2ijVarX=∑ni=1λi∑nj=1c2ijNVarX p ∑ni=1λin=

tr((E-A)T(E-A))n

利用這個公式，在X的容量比較大，并且X的屬性兩兩獨立時，基于距離的隱私保護度評價公式為

S(A，X)=S(A)=tr((E-A)T(E-A))/n（18）

P(A，X)=(1-1v21)(1-1v22)…(1-1v2n）(tr((E-A)T(E-A)）n)(19)

它與具體的數(shù)據(jù)沒有關系。

（1）算法描述

OBT主要對任意配對的兩兩獨立屬性向量組進行正交變換，對于每一個屬性向量組，隨機從矩陣庫中選擇一個符合要求的正交矩陣進行正交變換，然后輸出變換后的數(shù)據(jù)。算法首先假設數(shù)據(jù)矩陣只包含在聚類之前必須進行轉換保護的個人數(shù)值型數(shù)據(jù)而且數(shù)據(jù)已經(jīng)被zscore方法規(guī)范化，當然，屬性向量還必須兩兩獨立且需要轉換的數(shù)據(jù)必須足夠多。

在進行變換時，有兩個關鍵的步驟：

①建立矩陣庫。這一部分可以在變換之前進行，可以建立符合最低隱私保護度要求的任意維的正交矩陣庫，但一般情況可以只建立兩維和三維的矩陣庫就夠了。

②選擇并變換屬性向量對。變換的屬性向量是兩兩獨立的，為了計算簡單，一般采用每兩個屬性向量配成一對，隨機地把每兩個屬性向量Ai，Aj（i≠j）分成一對；如果屬性向量的個數(shù)是奇數(shù)，那么最后剩下的三個組成一對，從矩陣庫中隨機地選擇正交矩陣進行變換。

（2）與RBT方法的比較

與RBT[3]相同，變換之前數(shù)據(jù)經(jīng)過了規(guī)范化處理，使得所有的屬性有著相同的權重，同時標志實體的屬性（如ID）被匿名保護，數(shù)據(jù)很難通過與外部數(shù)據(jù)庫連接而被估計出來。當然最重要的是，利用變換對數(shù)據(jù)進行了扭曲，在變換的過程中，因為隨機選擇了屬性對，在要求的隱私保護度范圍內(nèi)隨機選擇變換的角度，所以很難從變換后的數(shù)據(jù)估計出原始數(shù)據(jù)，這樣，原始數(shù)據(jù)得到很好的保護，從而也就保護了數(shù)據(jù)的隱私。不同的是，在數(shù)據(jù)容量很大的情況下，為了計算符合隱私保護度的角度范圍需要進行大量的運算。而且，按照文獻[3]中的對于隱私保護度的評價方法，會有一些特殊的值與現(xiàn)實情況不符。本文重新拓廣了隱私保護度的評價方法，引入了基于方向的隱私保護度評價方法，使得結果更符合現(xiàn)實情況。更重要的是，本文證明了一個結論：在容量很大的情況下，角度的選擇與具體的數(shù)據(jù)無關，這樣就可以預先建立矩陣庫，從而避免了變換時的大量運算。

4 結論

本文針對聚類分析時如何保護隱私的問題，對應用正交變換保護數(shù)據(jù)中的隱私信息進行了系統(tǒng)的討論。從傳統(tǒng)的數(shù)據(jù)安全度[4]評價方法出發(fā)，本文重新拓廣了一般實數(shù)上有限維歐氏空間中的隱私保護度評價方法，給出一個不依賴具體數(shù)據(jù)的隱私保護方法，從而使得在應用正交變換保護數(shù)據(jù)中的隱私信息時不需要進行大量的運算。

參考文獻：

[1]S R M Oliveira， O R Zaane. Privacy Preserving Clustering by Data Transformation[C].Manaus，Amazonas，Brazil:Proc.of the 18th Brazilian Symposium on Databases， 2003.304-318.

[2]J Vaidya， C Clifton. PrivacyPreserving Kmeans Clustering over Vertically Partitioned Data[C]. Washington， DC: Proc. of the 9th ACM SIGKDD Intl. Conf. on Knowledge Discovery and Data Mining， 2003.206-215.

[3]S R M Oliveira， O R Zaane. Achieving Privacy Preservation when Sharing Data for Clustering[C]. Toronto: Proc.of the International Workshop on Secure Data Management in a Connected World in Conjunction with VLDB 2004， 2004.67-82.

[4]K Muralidhar， R Parsa， R Sarathy. A General Additive Data Perturbation Method for Database Security[J]. Management Science， 1999，45(10):13991415.

作者簡介：

張國榮，男，助教，碩士研究生，主要研究方向為數(shù)據(jù)挖掘等;印鑒，男，教授，博士，主要研究方向為數(shù)據(jù)挖掘、人工智能等。

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