基于隱私保護的數據相似性度量

摘要：數據對象間的相似性度量是數據挖掘中一個重要的內容。針對如何在不共享精確數據的條件下，安全計算數據對象間的相似性問題，提出了幾種基于安全多方計算協議的算法。算法很好的隱藏數據，保護隱私信息，且對相似性計算的結果沒有影響。

關鍵詞：數據挖掘；隱私保護；相似性；距離

中圖分類號：TP311文獻標識碼：A 文章編號：1009-3044(2008)12-20000-00

Privacy Preserving Data Similarity Measurement

ZHANG Guo-Rong

(Computer staff room at Guangzhou Academy of Fine Arts，Guangzhou 510260，China)

Abstract:Data similarity measurement is an important direction for data mining research. This paper is concentrated on the issue of measuring securely data similarity without sharing precise individual data records， and proposes several methods based on secure multi-party computation model. These methods efficiently hide attribute values， preserve privacy information and guarantee valid similarity measurement results.

Key words:data mining；privacy preserving；similarity；distance

1 引言

隱私保護是分布式數據挖掘中一個重要的研究方向，在雙方或多方合作進行數據挖掘時，由于某種原因，參與者往往不愿意將數據與他人共享而只愿共享挖掘的結果，這就要求人們提出保持隱私性的數據挖掘方法[1]。數據對象間的相似尺度是數據挖掘中一個重要的內容，尤其對于聚類分析，相似性度量更為重要。為了在對分布式數據進行相似性度量時保持參與者隱私，本文利用安全多方計算的相關協議，對數據的相似性進行安全計算，從而達到保護參與各方私有信息的目的。

2 基于安全多方計算的協議

安全多方計算是一種為了完成某種計算任務而采用的分布式計算協議。在協議運行前，參與計算的各方各自擁有一個保密的輸入；協議中， 各方保持隱私輸入不為它方(包括任何的第三方)所知；協議運行后；各自獲得輸出，除此之外，各方不知道其他方輸入的任何信息。文獻[2]中引入半可信的第三方參與計算。第三方是半可信的主要要求是：（1）第三方是不可信的。因此，不能從參與的各方獲得私有信息，以及從計算結果得到私有信息。（2）第三方不可以和任何一方有聯系。（3）第三方嚴格遵守協議。現實世界中半可信的第三方要比完全可信的第三方普遍的多，所以使用半可信第三方參與計算是可行的，但是，如果半可信第三方不遵守第二點要求，與某一參與方發生共謀，后果將不堪設想。因此，本文采用的是多方協商計算的方法：假設參與各方都希望得到準確的計算結果，所以他們不會發送給虛假數據對方，同時，參與各方是好奇的，所以他們會保留所接收到的數據，并試圖從這些數據中了解對方的信息。

2.1 比較協議

甲與乙各有一個私有數據，他們希望秘密比較這兩個數據的大小，當兩個數據不相等時，任何一方都不能夠知道對方的值。文獻[3]基于Φ-隱藏假設以及同態公鑰加密體制的語義安全性假設，給出了一個特殊的安全雙方計算協議——無信息泄漏的比較相等協議。該協議具有公平性：一方知道最后結果的等價條件為另一方也知道這個結果；安全性：除了最后結果以外，不泄露有關雙方輸入的任何信息；有效性：借助于茫然第三方協助完成計算任務，使協議簡單有效，但這個第三方不知道最后結果及參與方的秘密，也不能與參與方串謀作弊。但是該協議在需要大規模比較數據時顯得過于復雜。本文使用一種簡單的比較協議，并把它應用在計算兩個對象的曼哈坦距離中。

問題：P1、P2各有一些私有數據X1，X2，…，Xn和Y1，Y2， ，…，Yn，他們要共同秘密比較這些數據的大小，但任何一個用戶都不愿意向其他用戶泄露自己的私有信息。

協議Secure_ Compare：

(1) P1、P2雙方協商兩個整數a，b，其中a>>max(Xi，Yi)， i∈[1，n]

(2) P1隨機選擇數據Ri，Ri∈[-b，b]，計算Xi’=aXi-Ri，然后P1將X1’，X2’，…，Xn’發送給P2

(3) P2隨機選擇數據Ri，Ri∈[-b，b]，計算Yi’=aYi-Ri，然后P2將Y1’，Y2’，…，Yn’發送給P1

(4) P1，P2比較X1’，X2’，…，Xn’和Y1’，Y2’，…，Yn’，得到X1，X2，…，Xn和Y1，Y2， ，…，Yn的大小關系：當Xi≥Yi時，ci=0；否則，ci=1

協議中隨機選擇的Ri保證了任何一方都無法獲得對方的私有數據，但可能會提供一些數據所處大概位置的信息，不過在現實生活中進行合作計算時，數據的大概分布可以通過一般的常識了解到，所以合作雙方可以接受。協議中另一個問題是如何協商得到a，b，簡單的方法是雙方各提供一個虛擬的樣本，然后根據樣本協商得到，另一種方法是互相提出一組a，b，通過比較協商得到最后的a，b。協議最大的優點是在泄露有限的信息后，保證大規模數據比較快速進行。

2.2 點積協議

甲與乙各有一個私有向量數據，他們希望秘密計算這兩個向量的點積，任何一方都不能夠知道對方的值。文獻[2]基于半可信第三方設計了一個安全計算點積協議，甲乙雙方要計算A，B的點積，從而甲得到V1，乙得到V2，其中V1 +V2 = A?B，且V2由乙隨機生成。即A，B的點積被分為兩個保密部分，一部分歸甲方所有，另一部分歸乙方所有。協議確保了甲乙雙方均不能了解到對方的信息。但是如果半可信第三方與某一方共謀，則另一方的私有信息將受到侵犯。本文采用一種基于隨機擾亂向量的點積協議[4]，并把它應用在計算歐氏距離中。

問題：P1、P2各有一個私有向量X=(x1，x2，…xn)和Y=(y1，y2，…yn)，他們希望秘密計算這兩個向量的點積，但任何一個方都不愿意向另一方泄露自己的私有信息。

協議Secure_ Scalar product：

(1) P1、P2雙方協商一個n×n/2的矩陣C

(2) P1產生一個隨機向量R=R1，…，Rn/2，計算X''=X+C×R，發送X''給P2

(3) P2計算點積S'=????xi''*yi，Y'=CT×Y ，發送S'給P1

(4) P1計算點積S''=????yi'*Ri，S=S'-S'' ，發送最后結果S給P2

3 相似性度量

數據對象間的相似尺度是數據挖掘中一個重要的內容，尤其對于聚類分析，相似性度量更為重要。數據對象之間的相似性可以通過它們間的相異性來定義和描述。對于用區間標度變量描述的數據對象，它們之間的相似度基于對象之間的距離來計算，用距離表示相異度。本文分別討論在數據水平劃分分布時，如何在保護雙方精確數據的情況下計算數據對象之間的距離。

3.1 曼哈坦距離

定義1：假設P1、P2各有一個數據對象X=(x1，x2，…xn)和Y=(y1，y2，…yn)z，則它們的曼哈坦距離定義如下：

zgr01.tif （1）

其中，當xi≥yi時，ci=0 ；否則，ci=1

算法1：安全計算水平分布對象的曼哈坦距離。

輸入：包含m1個對象的數據庫P1和包含m2個對象的數據庫P2

輸出：對象之間距離組成的相異度矩陣

方法：

（a）P1、P2雙方各自根據公式（1）計算內部對象間的曼哈坦距離；

（b）P1、P2雙方根據協議Secure_ Compare比較不同方對象間的大小，得到ci；

（c）P1、P2雙方根據公式（1），先計算局部和，然后把結果發送給對方求和，得到對象間的曼哈坦距離；

（d）輸出相異度矩陣。

3.2 歐氏距離

定義2：假設P1、P2各有一個數據對象X＝(x1，x2， …，xp)和Y＝(y1，y2， …，yp)，則它們的歐氏距離定義如下：

算法2：安全計算水平分布對象的歐氏距離。

輸入：包含m1個對象的數據庫P1和包含m2個對象的數據庫P2

輸出：對象之間距離組成的相異度矩陣

方法：

（a）P1、P2雙方各自根據公式（2）計算內部對象間的歐氏距離；

（b）P1、P2雙方根據協議Secure_ Scalar product計算????xiyi；

（c）P1、P2雙方計算局部和 ????xi2，????yi2 ，并發送給對方；

（d）根據公式（2）計算不同方對象間的歐氏距離；

（e）輸出相異度矩陣。

3.3 馬氏距離

從變量獨立的對距離尺度起作用的角度來看，歐氏距離具有“加成”的特征，而該特征在有的情況下并不適用。一個極端的情況：測量很多杯子的高度和直徑，假設測量每個杯子的高度100次，直徑1次，那么對任何杯子有101個變量，其中100個幾乎具有相同的值。如果用歐氏距離公式進行計算，則高度會支配杯子間的相似性。事實上，99個高度測量對于真正需要的尺度沒有任何貢獻，為了消除這種冗余，需要考慮變量間的協方差和相關性。

定義3：假設有n個對象，兩個變量Xi和Xj對這n個對象的取值分別為x1i，x2i， …，xni和x1j，x2j， …，xnj，那么Xi和Yi之間的樣本協方差被定義為：

zgr03.tif，其中?? 和?? 分別為Xi和Xj的樣本平均值。 （3）

定義4：為了消除協方差對Xi和Xj取值范圍的依賴性，通過標準化的方法得到Xi和Xj間的樣本相關系數：

定義5：兩個p維測量值Ai和Aj之間的馬氏距離定義如下：

其中，T表示矩陣的轉置，????是進行了標準化的協方差矩陣，????中的元素(k，l)是變量Xk和Xl間的樣本相關系數。

算法3：安全計算變量Xi和Xj的相關系數。

輸入：包含m1個對象的數據庫P1和包含m2個對象的數據庫P2

輸出：變量之間相關矩陣

方法：

(a) P1計算自己的本地數據部分和zgr06.tif ；

(b)P2計算自己的本地數據部分和 zgr07.tif ；

(c) P1，P2分別把結果發送給對方，根據公式（4）計算出向量Xi和Xj的相關系數；

(d)計算所有的變量間的相關系數，輸出變量之間相關矩陣。

算法4：安全計算水平分布對象的馬氏距離。

輸入：包含m1個對象的數據庫P1和包含m2個對象的數據庫P2

輸出：對象之間距離組成的相異度矩陣

方法：

（a）P1、P2雙方各自根據公式（5）計算內部對象間的馬氏距離；

（b）利用協議算法3計算相關矩陣，假設矩陣為zgr08.tif

（c）假設P1有對象A，P2有對象B，計算zgr09.tif

雙方計算自己的本地數據，把結果發送給對方，可以得到結果，簡記為 (d1，...，dp)；

（d）計算zgr10.tif，雙方分別計算自己的本地數據，并把結果發送給對方，根據公式（5），得到對象A，B的馬氏距離。

（e）輸出相異度矩陣。

4 結束語

隱私保護是數據挖掘中一個重要的研究方向，如何在不違反隱私規定的情況下，利用數據挖掘工具發現有意義的知識是一個熱點問題。數據對象間的相似度量是數據挖掘中一個重要的內容，尤其對于聚類分析，相似性度量更為重要。本文介紹了兩個基于安全多方計算的協議，并把它們應用在數據對象間相似性的安全計算，著重討論在數據水平劃分分布時，如何在保護雙方精確數據的情況下計算數據對象之間的曼哈坦距離、歐氏距離和馬氏距離。算法很好的隱藏數據，保護隱私信息，且對相似性計算的結果沒有影響。從而達到保護參與各方私有信息的目的。

參考文獻：

[1] 張國榮. 分布式數據挖掘的隱私保護問題[J]. 電腦知識與技術， 2006 ，8 : 30，212.

[2] W. Du and Z. Zhan. Building Decision Tree Classifier on Private Data[C]. In Proceedings of the IEEE ICDM Workshop on Privacy， Security and Data Mining， Maebashi City， Japan. December 2002. pp.1-8.

[3] 秦靜， 張振峰， 馮登國， 等. 無信息泄漏的比較協議[J]. 軟件學報， 2004 ， 15 (3) : 421-427.

[4] C. Clifton， M. Kantarcioglu， X. Lin， J. Vaidya， and M. Y. Zhu. Tools for privacy preserving distributed data mining[C]. SIGKDD Explorations， Newsletter of the ACM Special Interest Group on Knowledge Discovery and Data Mining， 2003.

收稿日期：2008-03-27

作者簡介：張國榮（1977-），男，講師，碩士，主要研究方向：數據挖掘、計算機基礎教學。

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