一種新的K均值挖掘的隱私保護(hù)算法

王思勃，白素平

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

0 引言

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

1 背景介紹

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

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

2 RD算法

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

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

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

圖1 RD算法示意圖

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

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

3 實(shí)驗(yàn)結(jié)果

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

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

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

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

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

表1 挖掘精度

4 結(jié)語

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

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

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

［3］李鋒，馬進(jìn)，李建華.分布式數(shù)據(jù)挖掘中的匿名隱私保護(hù)方法［J］.浙江大學(xué)學(xué)報(bào)(工學(xué)版)，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.