面向互聯(lián)網的隱私保護關鍵算法

楊秀菊

(泉州信息工程學院， 福建 泉州 　362000)

0　引　言

針對傳統(tǒng)數(shù)據(jù)匿名隱私保護技術中存在信息損失過大[1]、數(shù)據(jù)效用低下等問題，越來越多的數(shù)據(jù)挖掘技術被引用進來[2]。基于頻繁項集的關聯(lián)規(guī)則挖掘和聚類挖掘就是很好的應用范例。由于不同的聚類方法在處理不同類型、不同規(guī)模的數(shù)據(jù)各有其不同的優(yōu)缺點，而基于聚類的匿名隱私技術實際上受聚類本身的制約也比較大[3]，如何根據(jù)實際選擇比較符合的聚類方法、盡量避免因為聚類本身缺陷帶來的相應問題便成為了研究的重點之一。

1　基于k-PROTOTYPE裁剪的離散點檢測算法

離散點又稱離群點、異常點，對數(shù)據(jù)挖掘等數(shù)據(jù)統(tǒng)計處理技術產生顯著影響，同樣，在基于聚類的匿名算法中，如果未能很好地處理離散點，誤將其分入某個簇中，就有可能導致該簇的過度泛化，從而使信息損失變大。

常用的離散點檢測方法有：基于統(tǒng)計的檢測、基于鄰近度的檢測、基于密度的檢測。

基于密度的離散點檢測算法基本思想是：不將離散點看做一種簡單的二元對象，而是用一個權值來評估它的離散度。這個離散度叫局部離散因子(LOF)，表示該對象相對于其附近領域的孤立情況。

通過計算離散度來檢測離散點的方法叫LOF算法，這也是基于密度的離散點檢測的代表算法。這種方法可以同時檢測出全局離散點和局部離散點。

1.1　基于密度的離散點檢測算法的初步改進

LOF算法在查詢某對象A的第k距離領域時，實際上存在效率問題，因為在對A查詢完領域以后，這些信息都會被放棄，要查詢其領域內其他對象的領域，又必須重新開始對該對象計算第k距離和第k距離領域。但事實上，這些對象的領域與A的領域有很大的重疊。

領域遞推示意圖如圖1所示。

圖1　領域遞推示意圖

區(qū)域1與區(qū)域2內切，區(qū)域2與區(qū)域3內切。設X為A的領域中的某點，而E為A的領域邊界上的點，則以A為圓心、k-distance(A)為半徑的區(qū)域1包含了A領域中的所有點并且除去A本身的個數(shù)為k。以此類推，則對A領域中某點X，其領域中的所有點一定包含在以A為圓心，2*d(X,A)+k-distance(A)為半徑的區(qū)域中，這便省去了對X的許多“無關點”的考察。

1.2　基于k-PROTOTYPE裁剪的LOF算法

使用聚類進行數(shù)據(jù)預處理，實現(xiàn)非離散點的預先剪裁，從而有效降低LOF算法的樣本集合。為了提高整個算法的效率，預先剪裁只是為了剔除高內聚的點，對聚類質量要求并不高，因此，使用劃分聚類中的經典算法k-均值算法的擴展算法k-PROTOTYPE來處理混合屬性數(shù)據(jù)(k-均值算法只能處理數(shù)值屬性)。

1.2.1k-PROTOTYPE算法的基本定義

在改進算法k-PROTOTYPES中定義了一個對數(shù)值與分類屬性都適用的相似度的度量方法，根據(jù)此方法對數(shù)據(jù)集進行聚類，以獲得最優(yōu)聚類結果。

下面給出k-PROTOTYPES算法的相關定義：

定義1相異度。設數(shù)據(jù)集U同時包含對數(shù)值與分類屬性，X、Y為U中的兩個對象，其中

X=(x1,x2,…,xp,xp+1,…,xm)

Y=(y1,y2,…,yp,yp+1,…,ym)

m>p

且前p個為數(shù)值屬性，p+1到m為分類屬性，則對象X、Y之間的相異度公式為：

其中

定義2成本函數(shù)

1.2.2改進初始聚類中心選取的k-PROTOTYPE算法

在使用k-PROTOTYPE算法剪裁LOF之前，需要對初始聚類中心的選取做一些改進，利用等分區(qū)間思想，具體步驟如下：

1)設定數(shù)據(jù)集中心點，數(shù)值屬性取平均值，分類屬性取眾數(shù)；

2)找到一個離中心點最遠的點，記為第一個初始點A1，最遠距離設為r；

3)在剩余點中找到與A1距離最接近r/(k-1)的點，記為第二個初始點A2；

4)以此類推，在剩余點中找到與A1距離最接近(i-1)r/(k-1)的點，記為第i個初始點Ai，直到i=k，全部k個初始點都找到。

由此可得改進初始聚類中心選取的k-PROTOTYPE算法的詳細偽代碼。

2　密度聚類的個性化屬性權重匿名算法[4]

2.1　基于OPTICS的個性化屬性權重匿名算法

2.1.1算法的基本步驟

目前能實現(xiàn)隱私保護[5]的隱私模型主要是以k-匿名模型為原型進行的拓展與優(yōu)化[6]。而在實現(xiàn)個性化屬性權重的匿名算法時，同樣選取k-匿名模型作為原型，以泛化作為主要的匿名方法。基于OPTICS的個性化屬性權重匿名算法基本步驟如下：

1)數(shù)據(jù)集預處理，生成準標識符數(shù)據(jù)表與每個分類屬性的層次分類樹；

2)進行離散點檢測，生成處理過的數(shù)據(jù)表與離散點集；

3)確定個性化屬性權重，從而得出加權距離計算公式，確定信息損失度量標準；

4)使用OPTICS進行聚類，計算生成聚類的信息損失,然后進行聚類調整；

5)泛化每個簇中的所有準標識符屬性值。

2.1.2個性化屬性權重距離公式

樣本相似度或距離度量是進行聚類前必須預先確定的。由于本算法支持對混合型數(shù)據(jù)集的處理，因此,需要分數(shù)值屬性和分類屬性進行距離定義，最后確定個性化屬性權重距離的計算公式。

2.1.2.1數(shù)值屬性的距離

設N是一個數(shù)值屬性，兩個元組對應該屬性的屬性值分別為x和y，則它們的距離為：

2.1.2.2分類屬性的距離

設D是一個分類屬性，兩個元組對應該屬性的屬性值分別為x和y，則它們的距離為：

其中,W(i,i+1)(1≤i≤h-1)為層數(shù)i到層數(shù)i+1的權重，通常等于i。

2.1.2.3二元屬性的距離

設B是一個二元屬性，兩個元組對應該屬性的屬性值分別為x和y，則它們的距離為：

綜合3種屬性的距離計算方法，最后得到個性化屬性權重距離公式。設兩個元組X和Y，其中，前a個為數(shù)值屬性，a+1到b為分類屬性，b+1到c為二元屬性，有

X=(x1,x2,…,xa,xa+1,…,xb,xb+1,xb+2,…,xc)

Y=(y1,y2,…,ya,ya+1,…,yb,yb+1,yb+2,…,yc)

則得到的個性化屬性權重距離公式為：

(1)

2.1.3信息損失度量

隱私匿名算法中[3]常用的信息損失度量標準有基于泛化層次的信息損失度量方法、基于元組辨別度的信息損失度量方法和基于熵的信息損失度量方法等。在本算法中，使用抑制單元來衡量匿名代價。其定義如下：

2.1.4初始鄰域半徑參數(shù)ε的選取

前面說過，OPTICS是針對基本密度聚類算法DBSCAN的輸入?yún)?shù)敏感性而進行的優(yōu)化，然而仍舊需要輸入初始ε，但不會對聚類結果產生太大影響。

3　實驗與驗證

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

實驗選用UCI機器學習數(shù)據(jù)庫中Adult數(shù)據(jù)集，Adult數(shù)據(jù)集包括兩組數(shù)據(jù)集:訓練集(Train)和測試集(Test)。根據(jù)實驗結果，選擇隱私保護效果比較好的QI10={Age,Capital Gain,Country,Education Num, Hours-per-week, Marital Status,Race,WorkClass}作為準標識符屬性，其中屬性{Age,Capital Gain,Education Num, Hours-per-week}為數(shù)值屬性，其余為分類屬性。實驗環(huán)境為Intel(R)Core(TM)Duoi7-3632QM處理器、2.20 GHz主頻，8 GB的內存，MicrosoftWindows7SP164位操作系統(tǒng)。編程語言為C++。

3.2　實驗結果

3.2.1基于k-PROTOTYPE裁剪的LOF算法

為了驗證離散點檢測算法的有效性，在實驗中，分別對屬性{Age,Capital Gain,Education Num,Hours-per-week,Race}中各添加了兩個總共10個的擾動數(shù)據(jù)。其中Age,Capital Gain,Education Num,Hours-per-week為數(shù)值屬性，Race為分類屬性。然后,從兩個方面分別與原始LOF算法進行對比。設定預期離散點個數(shù)n=20，數(shù)值屬性與分類屬性的相異度參數(shù)r=1。

3.2.1.1檢測率與剪枝率

調整k值，重復5次實驗。初始值設為100，增長步長為50。檢測率與剪枝率見表1。

表1　k變化時OKPLOF與LOF的檢測率與剪枝率對比

在本實驗中，k′=30 162/k。

3.2.1.2運行時間

5次實驗的運行時間對比見表2。

表2　k變化時OKPLOF與LOF的運行時間對比

3.2.2基于OPTICS的個性化屬性權重匿名算法

本實驗使用抑制長度和運行之間來評估算法，并與基于密度的聚類匿名算法DSAED進行比較。為了統(tǒng)一標準，在與DSAED進行對比實驗的過程中各準標識符的權值均設為1。

3.2.2.1個性化

主要通過OBPA算法的內部對比不同屬性重要程度下的抑制單元數(shù)，見表3。

設

W=(0.132 9,0.080 5,0.265 8,0.520 8,0.258 3,

0.637 0,0.212 4,0.424 6,0.104 7)

表3　不同屬性重要程度下的抑制單元數(shù)對比

3.2.2.2抑制單元

調整k值，重復5次實驗。抑制單元數(shù)對比見表4。

表4　k變化時的抑制單元數(shù)對比

3.2.2.3運行時間

5次實驗的運行時間對比與表4相似，表略。

3.3　結果評估

1)在第一組實驗中，OKPLOF的時間優(yōu)化效果明顯，同時從檢測率上可以看出，OKPLOF也解決了LOF算法不能處理混合屬性的問題。

2)在第二組實驗中,OBPA與DSAED均采用密度聚類，但OBPA的信息損失明顯低于DSAED，而運行時間在k值大于32時也開始低于DSAED，優(yōu)化效果得以證實。而在個性化實驗中，代表屬性重要程度的權值增加，對應準標識符的抑制單元數(shù)下降，說明權值使得等價類中該屬性的屬性值相似度更高，有效減少了泛化所帶來的信息損失，個性化算法有效。

4　結　語

實現(xiàn)了基于密度聚類并消除離散點影響的個性化屬性權重匿名算法，首先介紹了聚類和相關算法，然后針對離散點消除，對現(xiàn)成的LOF算法進行初步改進,并由此提出了通過基于優(yōu)化初始點選取的k-PROTOTYPE聚類裁剪的離散點檢測LOF算法，介紹了基于密度聚類的OPTICS算法,并闡述了屬性權重的引入，確定了個性化屬性權重距離公式，最后,提出了消除離散點影響的個性化屬性權重密度聚類匿名算法，并用實驗進行算法的對比驗證，結果證明兩個算法均合理有效。

參考文獻：

[1]王佳慧,劉川意,方濱興.面向物聯(lián)網搜索的數(shù)據(jù)隱私保護研究綜述[J].通信學報,2016,37(9):142-153.

[2]俞志斌,周彥暉.基于關鍵字的云加密數(shù)據(jù)隱私保護檢索[J].計算機科學,2015,42(s1):132-136.

[3]張曉琳,王萍,郭彥磊.社會網絡子集個性化隱私保護策略[J].計算機應用研究,2015,32(10):3026-3029.

[4]魏姁妲,逄煥利.基于區(qū)域中心點的多層次數(shù)據(jù)集密度聚類算法[J].長春工業(yè)大學學報,2016,37(6):576-580.

[5]張小波,付達杰.網絡信息資源個性化推薦中隱私保護的研究[J].軟件,2015,36(4):62-66.

[6]王良,王偉平,孟丹.FVS k-匿名:一種基于k-匿名的隱私保護方法[J].高技術通訊,2015,25(3):228-238.