隨機(jī)投影技術(shù)數(shù)據(jù)挖掘隱私的保護(hù)方法

黃取治

(福建師范大學(xué)信息技術(shù)學(xué)院，福建　福州350007)

?

隨機(jī)投影技術(shù)數(shù)據(jù)挖掘隱私的保護(hù)方法

黃取治

(福建師范大學(xué)信息技術(shù)學(xué)院，福建福州350007)

摘要：為確保隱私保護(hù)數(shù)據(jù)挖掘中所存在的維數(shù)災(zāi)難問(wèn)題得到有效解決，文章提出了將基于隨機(jī)投影技術(shù)的一種數(shù)據(jù)挖掘隱私保護(hù)法。這種方法對(duì)攻擊者能夠以隨機(jī)投影矩陣推測(cè)的方式重建原始數(shù)據(jù)進(jìn)行了綜合考慮，首先將安全子空空間概念提出來(lái)，再構(gòu)建安全子空間映射，在低失真嵌入實(shí)現(xiàn)的同時(shí)，能夠有效確保數(shù)據(jù)安全。通過(guò)實(shí)驗(yàn)證明，在對(duì)數(shù)據(jù)隱私予以保護(hù)的前提下，這種方法為數(shù)據(jù)質(zhì)量提供有效保障。

關(guān)鍵詞：數(shù)據(jù)挖掘;隨機(jī)投影技術(shù);隱私保護(hù)

由于迅猛發(fā)展的信息技術(shù)，使得相關(guān)企業(yè)機(jī)構(gòu)能夠收集有效的個(gè)人與組織信息，進(jìn)而實(shí)施數(shù)據(jù)分析及挖掘，以此為機(jī)構(gòu)帶來(lái)更多科研及商業(yè)價(jià)值。然而，在數(shù)據(jù)分布過(guò)程中，人工普查數(shù)據(jù)、醫(yī)療數(shù)據(jù)及交易數(shù)據(jù)等很多個(gè)人隱私信息均存在隱私泄露的問(wèn)題[1]。

1相關(guān)概念

1.1　隨機(jī)投影

1.2　通用哈希函數(shù)

由均勻分布的哈希函數(shù)族中將一個(gè)哈希函數(shù)隨機(jī)選取出來(lái)，是通用哈希函數(shù)理念的主要內(nèi)容，基于給定輸入，對(duì)哈希函數(shù)隨機(jī)選擇后，在已知概率范圍中得出相同哈希值，即：從哈希函數(shù)族H中，通過(guò)隨機(jī)選擇的方式給定一個(gè)哈希值y與哈希函數(shù)h，使其滿足y=h(x)的x值是均勻分布的。

2安全子空間方法

3實(shí)驗(yàn)分析

3.1　實(shí)驗(yàn)數(shù)據(jù)與環(huán)境

實(shí)驗(yàn)對(duì)三個(gè)數(shù)據(jù)集進(jìn)行選取，這三個(gè)數(shù)據(jù)集中，有兩個(gè)選于UCI學(xué)習(xí)數(shù)據(jù)庫(kù),即：arr hythmia數(shù)據(jù)集、arcene數(shù)據(jù)集，其中arcene數(shù)據(jù)集中含有1000個(gè)屬性與900個(gè)樣本，這一數(shù)據(jù)集本身屬于二分類問(wèn)題。此外，arr hythmia數(shù)據(jù)集中有279個(gè)屬性與453個(gè)樣本。三個(gè)數(shù)據(jù)集中，還有一個(gè)數(shù)據(jù)集為Reuters-5topic，此為RCVI數(shù)據(jù)集子集。本實(shí)驗(yàn)將320個(gè)實(shí)例選取出來(lái)，在將非關(guān)鍵詞匯去除后，將4186個(gè)屬性整理出來(lái)[4]。具體實(shí)驗(yàn)環(huán)境：4GB內(nèi)存，intelcorei5處理器，MicrosoftWindows7，1TB硬盤,對(duì)matlab測(cè)試(32位)予以使用。

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

首先對(duì)比傳統(tǒng)高斯隨機(jī)投影和安全子空間法對(duì)內(nèi)積保護(hù)程度和原始數(shù)據(jù)間距離，評(píng)估在數(shù)據(jù)可用性領(lǐng)域兩種方法的性能，再選取選取K-均值聚類算法與支持向量機(jī)分算法實(shí)施測(cè)試，對(duì)在數(shù)據(jù)挖掘應(yīng)用方面兩者的有效性進(jìn)行評(píng)估，通過(guò)原始數(shù)據(jù)挖掘精度與隱私保護(hù)后挖掘精度比值對(duì)其有效性進(jìn)行度量，如果原始數(shù)據(jù)和隱私保護(hù)數(shù)據(jù)上兩者的挖掘結(jié)果精度分別為C0、Cp,則數(shù)據(jù)有效性Qc=Cp/Co.

哈希函數(shù)在實(shí)驗(yàn)中通過(guò)乘法通用哈希，假設(shè)A={a∣a([2l],a∈奇數(shù)},那么，該通用哈希函數(shù)族：H={ha︱a(A},該公式中，ha(x)=div2l-m(axmod2l),如果d為偶數(shù)，則l=log2d,如果dw為奇數(shù)，那么l=log2(d+1)；如果k∈偶數(shù)，那么m=log2k,如果K∈奇數(shù)，那么m=log2(k+1),其中k表示子空間維數(shù),d表示原始數(shù)據(jù)維數(shù),div取商整數(shù)部分，mod為模運(yùn)算。

1、實(shí)驗(yàn)一：內(nèi)積和歐式距離

本實(shí)驗(yàn)對(duì)arcene數(shù)據(jù)集進(jìn)行選取，因?yàn)榫仃囯S機(jī)生成，所以實(shí)驗(yàn)各運(yùn)行大約10次，選取誤差平均值，不同投影維數(shù)下，內(nèi)積與歐式距離兩者相對(duì)誤差見(jiàn)圖1，從中可知，安全子空間對(duì)內(nèi)積與歐式距離的保護(hù)大致和高斯投影等同，而且具有越大的投影維數(shù)，其結(jié)果與高斯投影越接近，且投影維數(shù)越大，相對(duì)誤差也就越低，如果投影維數(shù)為3000，那么相對(duì)誤差就會(huì)降低0.2%。由此充分表明安全子空間在合理、有效投影維數(shù)內(nèi)能夠確保數(shù)據(jù)可用性[5]。

2、實(shí)驗(yàn)二：聚類

通過(guò)Reuters-5topic數(shù)據(jù)集與K均值算法對(duì)聚類中安全子空間有效性進(jìn)行測(cè)試，分別對(duì)數(shù)據(jù)轉(zhuǎn)換后聚類精度與原始數(shù)據(jù)聚類精度進(jìn)行測(cè)試，假設(shè)K均值算法K=5,以歐式距離作為相似度度量距離，聚類精度在各投影維數(shù)下見(jiàn)表1,在投影維數(shù)大約是原始數(shù)據(jù)維數(shù)1/2時(shí)，投影數(shù)據(jù)聚類結(jié)果和實(shí)際聚類相接近，通過(guò)對(duì)比顯示，該實(shí)驗(yàn)數(shù)據(jù)具有比較高的數(shù)據(jù)集維數(shù)，具有越高的原始維數(shù)，那么安全子空間法就具有越好的應(yīng)用效果。

表1　各投影維數(shù)下聚類準(zhǔn)確率

4結(jié)語(yǔ)

文章基于隨機(jī)投影技術(shù)的一種數(shù)據(jù)挖掘隱私保護(hù)法提出來(lái)，并將安全子空間映射與安全子空間的概念提出來(lái)，并創(chuàng)建安全子空間映射，通過(guò)投影轉(zhuǎn)換來(lái)保護(hù)原始數(shù)據(jù)，利用哈希技術(shù)對(duì)投影矩陣予以加密生成，從數(shù)學(xué)角度證明了安全子空間法本身所具有的有效性，并將相關(guān)理論依據(jù)提供出來(lái)，在高位數(shù)據(jù)挖掘處理過(guò)程中，這種方法可以對(duì)隱私問(wèn)題進(jìn)行更好的保護(hù)，能夠有效確保數(shù)據(jù)安全。

參考文獻(xiàn)：

[1]張鋒,孫雪冬,常會(huì)友等·兩方參與的隱私保護(hù)協(xié)同過(guò)濾推薦研究[J].電子學(xué)報(bào),2009,37(1):84-89.

[2]李光,王亞?wèn)|·一種改進(jìn)的基于奇異值分解的隱私保持分類挖掘方法[J].電子學(xué)報(bào),2012,40(4):739-744.

[3]CC Aggarwal, P S Yu·A General Survey of Privacy-preservingData Mining Models and Algorithms [M] .NewYork:Springer US, 2008：11-52 .

[4]SLee , M G Genton , R B Arellano-Valle .Perturbation of numericalconfidential data via skew-t distributions[J].ManagementScience , 2010, 56(2):318-333.

[5] M Dietzfelbinger , T Hagerup , J Katajainen, M Penttonen.Areliable randomized algorithm for the closest-pair problem[J].Journal of Algorithms,1997,25(1):119 -120.

(責(zé)任編輯：王德紅)

Research on Protection Method of Privacy Random Projection Based on Data Mining Technology

Huang Quzhi

(Information Technology College, Fujian Normal University, Fuzhou350007, Fujian, China)

Abstract：In order to ensure the privacy of data mining in the presence of the curse of dimensionality issues are effectively addressed, this article will dig Privacy Protection Act proposed is based on a random data projection technology. In this way the attacker can be presumed in a random manner as the projection matrix to reconstruct the original data were taken into account, first, the proposed concept of the security sub-blank space, and then build the security sub-space mapping, while embedded achieve low distortion, it is possible to ensure an effective data security. Through experiments proved to be protected under the premise of data privacy, this method provides effective protection for data quality.

Key words:data mining;stochastic projection technology;privacy protection

中圖分類號(hào)：TP311

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：1673-9507(2015)01-0129-02

作者簡(jiǎn)介：黃取治(1982.09~)，福建師范大學(xué)信息技術(shù)學(xué)院講師。研究方向：計(jì)算機(jī)數(shù)據(jù)挖掘。

收稿日期：2014-11-30