隨機投影技術數據挖掘隱私的保護方法

黃取治

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

?

隨機投影技術數據挖掘隱私的保護方法

黃取治

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

摘要：為確保隱私保護數據挖掘中所存在的維數災難問題得到有效解決，文章提出了將基于隨機投影技術的一種數據挖掘隱私保護法。這種方法對攻擊者能夠以隨機投影矩陣推測的方式重建原始數據進行了綜合考慮，首先將安全子空空間概念提出來，再構建安全子空間映射，在低失真嵌入實現的同時，能夠有效確保數據安全。通過實驗證明，在對數據隱私予以保護的前提下，這種方法為數據質量提供有效保障。

關鍵詞：數據挖掘;隨機投影技術;隱私保護

由于迅猛發展的信息技術，使得相關企業機構能夠收集有效的個人與組織信息，進而實施數據分析及挖掘，以此為機構帶來更多科研及商業價值。然而，在數據分布過程中，人工普查數據、醫療數據及交易數據等很多個人隱私信息均存在隱私泄露的問題[1]。

1相關概念

1.1　隨機投影

1.2　通用哈希函數

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

2安全子空間方法

3實驗分析

3.1　實驗數據與環境

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

3.2　實驗結果

首先對比傳統高斯隨機投影和安全子空間法對內積保護程度和原始數據間距離，評估在數據可用性領域兩種方法的性能，再選取選取K-均值聚類算法與支持向量機分算法實施測試，對在數據挖掘應用方面兩者的有效性進行評估，通過原始數據挖掘精度與隱私保護后挖掘精度比值對其有效性進行度量，如果原始數據和隱私保護數據上兩者的挖掘結果精度分別為C0、Cp,則數據有效性Qc=Cp/Co.

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

1、實驗一：內積和歐式距離

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

2、實驗二：聚類

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

表1　各投影維數下聚類準確率

4結語

文章基于隨機投影技術的一種數據挖掘隱私保護法提出來，并將安全子空間映射與安全子空間的概念提出來，并創建安全子空間映射，通過投影轉換來保護原始數據，利用哈希技術對投影矩陣予以加密生成，從數學角度證明了安全子空間法本身所具有的有效性，并將相關理論依據提供出來，在高位數據挖掘處理過程中，這種方法可以對隱私問題進行更好的保護，能夠有效確保數據安全。

參考文獻：

[1]張鋒,孫雪冬,常會友等·兩方參與的隱私保護協同過濾推薦研究[J].電子學報,2009,37(1):84-89.

[2]李光,王亞東·一種改進的基于奇異值分解的隱私保持分類挖掘方法[J].電子學報,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.

(責任編輯：王德紅)

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

中圖分類號：TP311

文獻標識碼：A

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

作者簡介：黃取治(1982.09~)，福建師范大學信息技術學院講師。研究方向：計算機數據挖掘。

收稿日期：2014-11-30