王思勃，白素平

(長春理工大學 光電工程學院，長春 130012)

0 引言

近年來，人們對隱私問題以及數(shù)據(jù)挖掘應用越來越關注，于是很多研究人員開始研究隱私保護的數(shù)據(jù)挖掘技術，簡稱PPDM。PPDM技術被廣泛應用于醫(yī)療、商業(yè)、社會學等多種領域。前期的工作主要有兩類:數(shù)據(jù)修改和數(shù)據(jù)加密［1］。數(shù)據(jù)加密技術沒有數(shù)據(jù)修改技術應用的廣泛，因為它的計算和通信代價太高。隱私保護的數(shù)據(jù)挖掘有兩個目標:隱私和精度［2］。這兩個目標往往是一種平衡關系:隱私要求方面，在挖掘者挖掘數(shù)據(jù)之前，要對隱私數(shù)據(jù)進行足夠的干擾;精度要求方面，盡管隱私數(shù)據(jù)被干擾，蘊藏在隱私數(shù)據(jù)中的數(shù)據(jù)模式仍然可以被挖掘者挖掘出來。本文提出了一個新的噪音添加算法來干擾原始數(shù)據(jù)，實驗表明，這個算法在同等條件下比其它的算法挖掘精度更高。

1 背景介紹

對于數(shù)據(jù)加密的隱私保護方法，主要實現(xiàn)分布式數(shù)據(jù)挖掘隱私保護方法。由于公鑰密碼機制保證了第三方對原始數(shù)據(jù)的不可見性以及數(shù)據(jù)的無損失性，能夠實現(xiàn)與原始挖掘相同精度的挖掘結果。但是與數(shù)據(jù)干擾方法相比，其計算和通信代價很昂貴。

數(shù)據(jù)修改技術主要有:加法噪音，乘法噪音，矩陣乘法，數(shù)據(jù)交換和K匿名［3］，本文著眼于加法噪音技術。對于加法噪音技術，2000年，Agrawal and Srikant公布了他們關于隱私保護數(shù)據(jù)挖掘的早期工作，他們提出了一個在客戶/服務器場景下，構建決策樹的加法干擾技術，通過重構原數(shù)據(jù)的數(shù)據(jù)分布得到與原數(shù)據(jù)相似的數(shù)據(jù)，然后再挖掘重構數(shù)據(jù)，缺點是重構比較麻煩。為了能夠直接通過挖掘干擾數(shù)據(jù)，而不需要修改挖掘算法，就能得到很好的挖掘效果，劉麗［4］提出了一個門限法，計算每條數(shù)據(jù)記錄的概率值，通過門限將數(shù)據(jù)記錄進行分類，這樣就跳過了重構過程，減少了程序的計算。劉麗方法的缺點是合適的門限的選取比較困難，沒有規(guī)律，要依靠經驗，不同的數(shù)據(jù)集也不同。

2 RD算法

以前的加法噪音算法都是要對干擾后的數(shù)據(jù)進行處理，然后再進行挖掘。本文提出的RD(random distance)算法是在數(shù)據(jù)干擾之前，對原始數(shù)據(jù)進行一次K均值的預挖掘，根據(jù)挖掘后的結果再進行干擾，而數(shù)據(jù)分析者只需要直接對干擾后的數(shù)據(jù)進行挖掘，就能夠得到與挖掘原數(shù)據(jù)相似的結果.RD算法中，數(shù)據(jù)提供者使用下面公式替代原始數(shù)據(jù)X:

其中，R是獨立同分布的噪音數(shù)據(jù)。

我們假設D是原始數(shù)據(jù)集，C(C1，C2...Ck)是使用k均值聚類算法挖掘原始數(shù)據(jù)的聚類結果。我們的目的就是要把D修改成D'，當數(shù)據(jù)分析者挖掘D'時，得到一個新的聚類結果，這個聚類結果與C具有較高的相似度，從而保證了挖掘精度。如圖1所示。

圖1 RD算法示意圖

在RD算法中，首先遍歷數(shù)據(jù)集中的所有記錄，在使用K均值聚類之后，每一條記錄都將會被歸類，此時，數(shù)據(jù)提供者對記錄添加噪音數(shù)據(jù)。為了保證干擾后的數(shù)據(jù)模式保持不變，RD算法盡可能得去保證每條記錄在干擾前后類別不變，方法是在添加噪音數(shù)據(jù)后，調整聚類中心和干擾后記錄點之間的距離，使得數(shù)據(jù)干擾前后始終在此類別域內，如圖1所示，Ci是聚類中心，R is記錄點.噪音數(shù)據(jù)RxandRy被添加到屬性X和Y中，然后回得到點P(X+Rx，Y+Ry).此時，有三種情況需要考慮，P分別在Din(i)，D(i)和out(i)域內:

在計算Ci和P'之間的距離之后，就能計算出將要發(fā)布給數(shù)據(jù)分析者的數(shù)據(jù)點P'的坐標。RD算法偽代碼

3 實驗結果

本文實驗中，數(shù)據(jù)挖掘工具使用的是WEKA工具，噪音數(shù)據(jù)的生成使用的是Matlab 7.0實現(xiàn)的，使用的數(shù)據(jù)集來源于真實的數(shù)據(jù)集Iris，Yeast和 Glass，，實例數(shù)分別為150、1484、214，從加利福尼亞大學的UCI機器學習庫中下載得到。

實驗中，通過與Keke Chen的數(shù)據(jù)干擾進行比較來衡量算法的性能。對每一個數(shù)據(jù)集，實驗測試條件為:分類數(shù)目選取2和3，加法噪音為均值為0，方差為0.2的高斯分布。我們的結果與Keke Chen的數(shù)據(jù)干擾進行比較，每一項測試選取10組噪音數(shù)據(jù)，計算平均精度作為最終精度。圖2和3顯示了分別挖掘Iris數(shù)據(jù)集干擾前后的結果。由此可見，干擾后隱私所屬類別更明顯了，從而保證了很高的挖掘精度。

圖2 隱私數(shù)據(jù)分布

圖3 干擾后數(shù)據(jù)分布

表1顯示了測試的結果，實驗表明，在大多數(shù)情況下，我們的算法的挖掘精度要高于Keke Chen的算法。

表1 挖掘精度

4 結語

本文提出了一個新的噪音添加方法，保護了數(shù)據(jù)挖掘中的隱私數(shù)據(jù)。我們的方法根據(jù)對原數(shù)據(jù)的預挖掘結果來調整干擾后數(shù)據(jù)，從而不再需要計算代價很高的重構步驟，也不需要修改數(shù)據(jù)挖掘方法，并且能夠得到較高的挖掘精度，是一個有效可靠的隱私保護的數(shù)據(jù)挖掘方法。

［1］Jiawei Han，Micheline Kamber.范明，盂小峰等譯.數(shù)據(jù)挖掘:概念與技術［M］.北京:機械工業(yè)出版社，2001.

［2］王泳.基于隱私保護的數(shù)據(jù)挖掘［D］.贛州:江西理工大學，2008.

［3］李鋒，馬進，李建華.分布式數(shù)據(jù)挖掘中的匿名隱私保護方法［J］.浙江大學學報(工學版)，2010(2):276－283

［4］Li Liu，Murat Kantarcioglu，Bhavani Thuraisingham.Privacy Preserving Decision Tree mining from Perturbed Data［J］.In proceedings of 42th Hawaii International Conference on System Sciences.2009.

［5］K.Chen，G.Sun，and L.Liu.Towards attack-resilient geometric data perturbation［J］.In Proceedings of the 2007 SIAM International Conference on Data Mining(SDM’07)，Minneapolis，MN，April 2007:589－592.