reliefF算法在數(shù)據(jù)發(fā)布隱私保護中的應(yīng)用研究

鄧宗武

摘要：在數(shù)據(jù)發(fā)布中，數(shù)據(jù)發(fā)布的目的是為了其他企業(yè)或者組織等能夠通過分析研究發(fā)布后的數(shù)據(jù)得到有價值的信息。然而數(shù)據(jù)的發(fā)布會泄露數(shù)據(jù)所有者的隱私信息，因此近幾年來對于數(shù)據(jù)發(fā)布隱私保護的研究也越來越多。目前，在數(shù)據(jù)發(fā)布隱私保護方法中使用最多的是匿名化方法。該文通過結(jié)合特征選擇領(lǐng)域知識，對數(shù)據(jù)發(fā)布在隱私保護和數(shù)據(jù)可用性上進行了研究，提出了將特征選擇技術(shù)應(yīng)用在數(shù)據(jù)發(fā)布隱私保護中，從待發(fā)布的數(shù)據(jù)屬性中選擇最有利于對數(shù)據(jù)發(fā)布有研究價值的數(shù)據(jù)屬性，該方法降低了數(shù)據(jù)隱私泄露的風(fēng)險，并且有利于數(shù)據(jù)挖掘。

關(guān)鍵詞：數(shù)據(jù)發(fā)布；隱私保護；特征選擇；微聚集

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2016）15-0001-02

1 概述

數(shù)據(jù)發(fā)布隱私保護的主要思想是在不泄露數(shù)據(jù)隱私和保持數(shù)據(jù)可用性之間尋找一種平衡[1]。數(shù)據(jù)發(fā)布的目的是為了數(shù)據(jù)的收集者（如個體、企業(yè)、政府等）進行分析研究然后做出相對應(yīng)的措施來達到自己的目的。發(fā)布的數(shù)據(jù)的屬性大都是多維的，如果所有的數(shù)據(jù)屬性全部發(fā)布，數(shù)據(jù)的隱私泄露的幾率非常高，同時數(shù)據(jù)的損失也會非常大，數(shù)據(jù)可用性大大降低，一些無關(guān)數(shù)據(jù)屬性或者相關(guān)性較小的數(shù)據(jù)屬性的發(fā)布會加大隱私泄露的幾率且對于數(shù)據(jù)發(fā)布沒有研究意義，因此，研究發(fā)布數(shù)據(jù)中的屬性對于數(shù)據(jù)發(fā)布是否具有研究價值，以及在數(shù)據(jù)隱私保護和保證數(shù)據(jù)可用性之間尋找一種平衡具有非常重要的意義。本文提出將特征選擇技術(shù)和微聚集技術(shù)相結(jié)合的隱私保護方法，從待發(fā)布的數(shù)據(jù)屬性中選擇最有利于對數(shù)據(jù)發(fā)布有研究價值的數(shù)據(jù)屬性，該方法降低了數(shù)據(jù)隱私泄露的風(fēng)險，但是在一定程度上增加了信息的損失。

2 特征選擇及reliefF算法

特征選擇是一種非常常見的降維方法，它是指從原始特征集中選擇使某種評估標準最優(yōu)的特征子集，其目的是挑選一些最有效的特征從而降低數(shù)據(jù)特征維度，使選出的最優(yōu)特征子集和特征選擇前近似甚至更好的預(yù)測結(jié)果，這不但提高了模型的泛化能力、計算效率，也提高了數(shù)據(jù)的實際效用，同時可降低維度災(zāi)難的發(fā)生頻率。

Relief[2]算法在特征選擇算法中比較優(yōu)秀且常用的算法。Relief算法隨機從訓(xùn)練集中選取m個樣本實例，然后找出和選取的樣本屬于同類和不同類的兩個距離最近的樣本，計算它們之間的差異，計算樣本的每個特征和類的相關(guān)性，再用平均值分別作為各個特征的權(quán)值。

在relief算法的基礎(chǔ)上，I. Kononerko[3]等人在其基礎(chǔ)上得到了其擴展算法ReliefF，ReliefF算法是從同類和不同類中選擇k個距離最近的樣本，然后計算平均值作為各個特征的權(quán)值[3]。將得到的特征進行排序，然后根據(jù)一定的規(guī)則來判定特征是有效還是無效的；或者選擇n個權(quán)值最大的特征，去除其他特征來進行特征選擇。

特征選擇的目的是選擇和分類有較大相關(guān)的特征，特征選擇沒有改變特征的語義特征和數(shù)值，只是選擇特征子集。將特征選擇應(yīng)用在數(shù)據(jù)發(fā)布中時，特征選擇是選擇和敏感屬性有較大相關(guān)的準標識符屬性，權(quán)值越高的說明該準標識符屬性和敏感屬性的相關(guān)性越高，那么該準標識符屬性對于數(shù)據(jù)發(fā)布的研究價值和意義就越大，反之則越小。原始數(shù)據(jù)集在經(jīng)過了特征選擇之后，數(shù)據(jù)屬性個數(shù)減少，即數(shù)據(jù)的維度降低了，這樣再對數(shù)據(jù)集進行匿名化時，匿名化的效率得到了提高，防止了數(shù)據(jù)“維度災(zāi)難”的發(fā)生，同時隱私泄露的風(fēng)險也相應(yīng)地降低了，但是在一定程度上增加了數(shù)據(jù)的信息損失。

3 reliefF 算法在數(shù)據(jù)發(fā)布隱私保護中的應(yīng)用

特征選擇算法選擇的是對于分類最有利的特征。而在本文中，我們要選擇的特征屬性則是和敏感屬性具有相關(guān)性的準標識符屬性。本文提出的基于reliefF的匿名化方法主要思想是：首先使用reliefF算法得到每個數(shù)據(jù)屬性的權(quán)值，即數(shù)據(jù)中每個屬性和敏感屬性的相關(guān)性；然后按照一定的規(guī)則剔除一些數(shù)據(jù)屬性，對剔除了數(shù)據(jù)屬性的數(shù)據(jù)集進行微聚集得到匿名數(shù)據(jù)表。具體步驟如下：

步驟1：數(shù)據(jù)預(yù)處理1

1）將原始數(shù)據(jù)集中的不完整數(shù)據(jù)剔除；

2）去除元組中的冗余屬性；

步驟2：數(shù)據(jù)預(yù)處理2

對預(yù)處理1中得到的數(shù)據(jù)集進行標準化，得到數(shù)據(jù)集T；

步驟3：使用reliefF算法對數(shù)據(jù)集T進行降維處理得到數(shù)據(jù)集T

該步計算元組每個屬性的權(quán)值，先將權(quán)值小于0的屬性去除，同時將大于0的屬性權(quán)值進行排序；

步驟4：使用MDAV算法對數(shù)據(jù)集T'進行微聚集得到數(shù)據(jù)集T''

對整個數(shù)據(jù)集進行微聚集，得到k值不同時的信息損失和隱私泄露風(fēng)險；

剔除權(quán)值最小的屬性得到新的數(shù)據(jù)集，對新的數(shù)據(jù)集進行微聚集，得

得到k值不同時的信息損失和隱私泄露風(fēng)險；

多次執(zhí)行，得到多個信息損失和隱私泄露風(fēng)險，比較他們之間的差異，再結(jié)合數(shù)據(jù)屬性的實際含義得到最后需要發(fā)布的數(shù)據(jù)集T"

基于reliefF的數(shù)據(jù)發(fā)布隱私保護是將reliefF和MDAV相結(jié)合來得到匿名化數(shù)據(jù)，該匿名化數(shù)據(jù)權(quán)衡了數(shù)據(jù)可用性和隱私泄露風(fēng)險之間的關(guān)系，是相對于最原始數(shù)據(jù)集發(fā)布較為有利的匿名化數(shù)據(jù)集。

3.1 數(shù)據(jù)可用性分析

同質(zhì)性測度（SSE）的計算方法為：等價類中的元組的和原始數(shù)據(jù)集的數(shù)值是相同的，而該等價類的類質(zhì)心應(yīng)為經(jīng)過特征選擇后的匿名化數(shù)據(jù)的類質(zhì)心加上被剔除的屬性的質(zhì)心0，同質(zhì)性測度則是原始數(shù)據(jù)集的數(shù)據(jù)元組和所在的等價類的類質(zhì)心之間的距離之和，此時的匿名表所有類相對于原始數(shù)據(jù)集的同質(zhì)性測度定義為R-SSE，信息損失量為R-IL=R-SSE/SST。

3.2 隱私泄露分析

匿名化處理后的數(shù)據(jù)匿名表并不能保證隱私信息得到百分百不被泄露，它仍然有被攻擊者攻擊的可能，匿名表的安全性指標是信息泄露風(fēng)險的主要考慮原則。數(shù)據(jù)安全性度量方法主要有[4]：（1）記錄鏈接方法；（2）區(qū)間泄密方法。記錄鏈接度量方法包括基于距離記錄鏈接方法和基于概率記錄鏈接方法兩張方法。本文使用的是基于距離記錄鏈接方法。

基于距離記錄鏈接方法就是通過統(tǒng)計匹配成功數(shù)所占的比例來衡量數(shù)據(jù)集的安全性，匹配成功的元組個數(shù)用LR表示，數(shù)據(jù)集總的元組個數(shù)用TR表示，則整個數(shù)據(jù)集的安全性可以用公式表示：

R-TRL = LR /TR

4 實驗結(jié)果及分析

本實驗的運行環(huán)境：2.5GHz Intel（R） Core（TM）處理器，8G內(nèi)存，Windows 8系統(tǒng)。實驗數(shù)據(jù)采用美國的Adult數(shù)據(jù)庫，目前，大部分對PPDP的匿名化模型的研究都采用Adult數(shù)據(jù)庫為測試數(shù)據(jù)。

實驗首先經(jīng)過reliefF特征選擇選擇和敏感屬性具有相關(guān)性的屬性，然后分別測試了不同的數(shù)據(jù)屬性個數(shù)在不同的數(shù)據(jù)集大小和不同k值的情況下的信息損失量和隱私泄露風(fēng)險。

表1是經(jīng)過特征選擇后權(quán)值大于0的特征的平均權(quán)值。

通過特征選擇后我們得到了和敏感屬性具有相關(guān)性的數(shù)據(jù)屬性，我們將這些屬性作為數(shù)據(jù)發(fā)布中的準標識符屬性，然后對數(shù)據(jù)集進行微聚集，得到不同的數(shù)據(jù)屬性個數(shù)在不同的數(shù)據(jù)集大小和不同k值的情況下的信息損失量和隱私泄露風(fēng)險。實驗分別測試了數(shù)據(jù)集大小為2000，k為20，10，5，數(shù)據(jù)屬性個數(shù)為10，9，8，7時的多組信息損失量和隱私泄露風(fēng)險。

圖3、圖4可以看出，當(dāng)數(shù)據(jù)屬性的維度N=8時，數(shù)據(jù)的信息損失量R-IL和隱私泄露風(fēng)險R-TRL之間的平衡相較于其他維度是較好。

圖5、圖6可以看出，當(dāng)數(shù)據(jù)屬性的維度N=8或9時，數(shù)據(jù)的信息損失量R-IL和隱私泄露風(fēng)險R-TRL之間的平衡相較于其他維度是較好。

綜合以上幾種情況分析能夠看出，當(dāng)屬性個數(shù)N=8時，數(shù)據(jù)的信息損失量R-IL和隱私泄露風(fēng)險R-TRL之間的平衡相較于其他維度是較好。

5 結(jié)束語

通過實驗驗證我們可以得出結(jié)論：通過reliefF來選擇數(shù)據(jù)發(fā)布的屬性能夠選擇對數(shù)據(jù)發(fā)布有意義的數(shù)據(jù)屬性，相對于原始數(shù)據(jù)集增加了數(shù)據(jù)的信息損失，但是在發(fā)布的匿名化數(shù)據(jù)集中，數(shù)據(jù)的準確性相較于原始數(shù)據(jù)集的更好，數(shù)據(jù)失真更小，同時也提高數(shù)據(jù)的安全性。

參考文獻：

[1] 王平水. 基于聚類的匿名化隱私保護技術(shù)研究[D].南京航空航天大學(xué)，2013.

[2] Kira K ，Rendell L A.The feature selection problem： Traditional methods and a new Algorithm[J].Proceedings of Ninth National Conference on Artificial Intelligence， 1992，05： 129-134.

[3] Kononerko I.Estimating attributes： analysis and extension of Relief[C]. In Proceedings of European conference on machine learning， Springer-Verlag New York， 1994：171-182.

[4]Panaretos J， Nikolaos T. Aspects of estimation Procedures at eurostat with some emphasis on over-space harmonization[A].Proc of the 5th Hellenic-European Conference on Computer Mathematics and its Applications[C].Athens，Greece：LEA Press，2001：853-857.