基于抽樣路徑的K-匿名隱私保護(hù)算法*

吳 響，臧 昊，俞 嘯

（徐州醫(yī)科大學(xué) 醫(yī)學(xué)信息學(xué)院，江蘇 徐州 221116）

基于抽樣路徑的K-匿名隱私保護(hù)算法*

吳 響，臧 昊，俞 嘯

（徐州醫(yī)科大學(xué) 醫(yī)學(xué)信息學(xué)院，江蘇 徐州 221116）

K-匿名是信息隱私保護(hù)的一種常用技術(shù)，而使用K-匿名技術(shù)不可避免會(huì)造成發(fā)布數(shù)據(jù)的信息損失，因此，如何提高K-匿名化后數(shù)據(jù)集的可用性一直以來都是K-匿名隱私保護(hù)的研究重點(diǎn)。對(duì)此提出了一種基于抽樣路徑的局域泛化算法——SPOLG算法。該算法基于泛化格尋找信息損失較小的泛化路徑，為減少尋徑時(shí)間，引入等概率抽樣的思想，選用等概率抽樣中的系統(tǒng)抽樣方法進(jìn)行取樣，利用樣本代替數(shù)據(jù)集在泛化格上尋找目標(biāo)泛化路徑，最后在該路徑上對(duì)數(shù)據(jù)集進(jìn)行泛化。同時(shí)，本算法使用局域泛化技術(shù)，能夠降低信息損失量，提高發(fā)布數(shù)據(jù)集的可用性。實(shí)驗(yàn)結(jié)果證明，本算法匿名化的數(shù)據(jù)集信息損失度低，數(shù)據(jù)可用性高。

隱私保護(hù)；路徑；信息損失；抽樣；K-匿名

0 引言

K-匿名[1]是一種簡單而有效的隱私保護(hù)模型，實(shí)施K-匿名要考慮兩個(gè)方面：（1）確保數(shù)據(jù)發(fā)布過程中隱私不泄露；（2）發(fā)布的匿名數(shù)據(jù)具有實(shí)用性。

基于以上兩個(gè)要求，眾多學(xué)者提出了許多匿名算法。但大體上可以分為全域泛化算法[2]和局域泛化算法[3]。相比之下，局域泛化算法不僅可以實(shí)現(xiàn)K-匿名，而且一定程度上降低了匿名表的信息損失，使得泛化后的數(shù)據(jù)集更具有可用性。

然而，在局域泛化中想要尋找最優(yōu)K-匿名已經(jīng)被證明是 NP難問題[4]，如何優(yōu)化 K-匿名算法、盡可能提高數(shù)據(jù)的可用性成為亟待解決的問題。因此，本文提出了一種基于抽樣路徑的局域K-匿名算法——SPOLG(Sampling Path Optimization Local Generalization)算法。

SPOLG算法將等概率抽樣的思想引入其中，選取足夠的樣本代替總體尋找泛化路徑，在已經(jīng)尋找到的路徑基礎(chǔ)上對(duì)數(shù)據(jù)集進(jìn)行局域泛化。等概率抽樣選擇的樣本能夠代表數(shù)據(jù)集總體的分布情況，通過樣本尋徑快速找到信息損失較小的泛化路徑，極大地提高了算法效率。同時(shí)，該算法采用的局域泛化技術(shù)保證了發(fā)布的數(shù)據(jù)集具有較高的可用性。

1 基本符號(hào)和定義

1.1 K-匿名相關(guān)定義

在實(shí)現(xiàn)SPOLG算法的過程中，以表1為例對(duì)基于抽樣泛化路徑的K-匿名算法進(jìn)行相關(guān)定義。假設(shè)數(shù)據(jù)發(fā)布者所持有的數(shù)據(jù)表為 T(A1，A2，…，An)，表中每條元組指明一個(gè)特定實(shí)體的相關(guān)信息，如年齡、工作、種族、性別、工作時(shí)長、工資（敏感屬性）等。

表1 數(shù)據(jù)表實(shí)例

定義 1 K-匿名：給定一個(gè)數(shù)據(jù)表T(A1，…，An)及其相關(guān)聯(lián)的準(zhǔn)標(biāo)識(shí)符 QIT=(Ai，…，Aj)(Ai，…，Aj?A1，…，An)，如果表1滿足 K-匿名，當(dāng)且僅當(dāng)[QIT]中的每一個(gè)元組至少在T[QIT]中出現(xiàn)k次。表2為2-匿名數(shù)據(jù)表。

表2 符合2-匿名的數(shù)據(jù)表

1.2 SPOLG算法相關(guān)定義

定義2 系統(tǒng)抽樣：將數(shù)據(jù)集中的元組按照ID排序，隨機(jī)選取一條元組作為起點(diǎn)，每隔一定的間隔抽取一個(gè)元組，直至樣本數(shù)量滿足事先給定的抽樣率。

定義3 抽樣泛化路徑：以泛化格的根節(jié)點(diǎn)為起點(diǎn)，計(jì)算其子節(jié)點(diǎn)對(duì)樣本泛化后的信息損失量，將信息損失量最小子節(jié)點(diǎn)插入路徑，自底向上，直至泛化格葉子節(jié)點(diǎn)。

例如：圖1中，若用＜W1，R0>這個(gè)節(jié)點(diǎn)泛化樣本比＜W0，R1>泛化樣本信息損失小，則選?。糤1，R0>為路徑的第2個(gè)節(jié)點(diǎn)，以此類推。如＜W0，R0>→＜W1，R0>→＜W1，R1>→＜W2，R1>這條路線是一條可能的抽樣泛化路徑。

圖1 泛化格

定義4 抽樣尋徑時(shí)間占比：由抽樣數(shù)據(jù)產(chǎn)生抽樣泛化路徑所花費(fèi)的時(shí)間SP在整個(gè)算法流程中的百分比。假設(shè)整個(gè)算法花費(fèi)的時(shí)間為SA，則其計(jì)算公式為：

2 算法實(shí)現(xiàn)

2.1 算法實(shí)現(xiàn)

本文提出的一個(gè)基于抽樣路徑的局域泛化算法——SPOLG算法，引進(jìn)了等概率抽樣的思想，以系統(tǒng)抽樣樣本代替數(shù)據(jù)集尋找泛化路徑，具體算法如下：

輸入：輸入表T，準(zhǔn)標(biāo)識(shí)符集合QI，等價(jià)類約束k以及抽樣率α。

輸出：滿足K-匿名的數(shù)據(jù)集T″。

(1)抽取樣本

①將數(shù)據(jù)集中的n條元組進(jìn)行編號(hào)；

③在第一段隨機(jī)選取編號(hào)l，其中l(wèi)∈N，l≤L；

④num=T×α，并對(duì)num取整；

⑤按照以下規(guī)則抽取樣本 T′：l，l+L，l+2L，l+ 3L，…，l+num×L；

⑥返回T′；

End

(2)尋找抽樣泛化路徑

①通過QI形成泛化格G；

②將泛化格G的第0層節(jié)點(diǎn)n0作為路徑P的起點(diǎn)P0；

③通過泛化格找到n1直接泛化的節(jié)點(diǎn)，計(jì)算這些節(jié)點(diǎn)泛化T′所得到的信息損失量，選出泛化數(shù)據(jù)集T′信息損失量最小的節(jié)點(diǎn)n2作為路徑P的第二個(gè)節(jié)點(diǎn)P1；

④重復(fù)步驟②直至到達(dá)泛化格G的頂點(diǎn)ni作為路徑的終點(diǎn)Pi得到路徑P；

⑤返回路徑P；

End

(3)匿名化數(shù)據(jù)表

函數(shù)：SPOLG(T，QI，k，α)

Begin

①T′=sample(T，α)；/*T表示待抽樣數(shù)據(jù)集*/

②P=path(QI，T′)；/*P表示所得抽樣路徑*/

③T″=φ；/*T″存放泛化后的數(shù)據(jù)集*/

④queue=φ，把路徑P中第i個(gè)節(jié)點(diǎn)賦值給queue，進(jìn)入以下循環(huán)：

D=φ；/*D存放本步驟泛化的數(shù)據(jù)*/

基于queue對(duì)數(shù)據(jù)表T進(jìn)行泛化；

D={泛化后滿足K-匿名的元組}；

T″∪D；

移除T中滿足K-匿名的元組；

結(jié)束循環(huán)；

⑤返回?cái)?shù)據(jù)表；

End

由以上步驟可知，該算法主要包括系統(tǒng)抽樣、尋找路徑、匿名化數(shù)據(jù)集3個(gè)主要環(huán)節(jié)，利用系統(tǒng)抽樣選取樣本，在已選擇的樣本中尋找信息損失較低的泛化路徑，由已選路徑對(duì)數(shù)據(jù)集進(jìn)行局域泛化。從路徑起點(diǎn)開始，自底向上對(duì)不滿足K-匿名的元組進(jìn)行泛化，直到所有元組滿足K-匿名。

2.2 算法合理性分析

本文算法使用系統(tǒng)抽樣，能夠保證每個(gè)元組被抽取概率相同，通過等概率抽樣樣本快速尋找到信息損失較低的泛化路徑，使得數(shù)據(jù)集整體泛化后的信息損失較小。同時(shí)，局域泛化進(jìn)一步保證了匿名后的數(shù)據(jù)集信息損失小，因此本算法是可行的。

3 實(shí)驗(yàn)驗(yàn)證及結(jié)果分析

3.1 實(shí)驗(yàn)環(huán)境

本文使用了 UCI Machine Learning Repository中的Adults數(shù)據(jù)集作為實(shí)驗(yàn)數(shù)據(jù)集，Adult數(shù)據(jù)集是由美國人口普查數(shù)據(jù)構(gòu)成，采用數(shù)據(jù)集中的訓(xùn)練集，并去除缺省值記錄，共有30 162條記錄，本文選取 7個(gè)屬性作為準(zhǔn)標(biāo)識(shí)符屬性，包括性別、種族、婚姻狀況、教育程度、工作、國籍、年齡，各屬性預(yù)定義的泛化規(guī)則參考文獻(xiàn)[5]。實(shí)驗(yàn)平臺(tái)配置為：Core 2.50 GHz/8 GB，Windows 7，所涉代碼均由 Java實(shí)現(xiàn)，并在 Eclipse Mars.2 Release(4.5.2)上運(yùn)行。實(shí)驗(yàn)數(shù)據(jù)都是在實(shí)驗(yàn)運(yùn)行5次所得到的實(shí)驗(yàn)數(shù)據(jù)基礎(chǔ)上取得的平均值。

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

實(shí)驗(yàn)主要從信息損失度及執(zhí)行時(shí)間方面對(duì)本文算法進(jìn)行衡量。本實(shí)驗(yàn)選用Incognito算法作為對(duì)比算法，比較了在不同個(gè)數(shù)的準(zhǔn)標(biāo)識(shí)符和不同k值條件下信息損失度和執(zhí)行時(shí)間的變化。其中信息損失度采用文獻(xiàn)[6]的計(jì)算方法。

元組的信息損失量：

其中，|el|是聚類 el元組的數(shù)量，1≤l≤m，Ni是第i個(gè)數(shù)值屬性的范圍，和是聚類el中最大值和最小值，H(TCj)是分類樹的高度，H(∧(∪Cj))是具有最小公共祖先的分類子樹的高度。

3.2.1 數(shù)據(jù)抽樣分析

尋徑時(shí)間占比通過式（1）進(jìn)行計(jì)算，信息損失量依據(jù)公式（2）、（3）來度量，由圖2、圖3可知，當(dāng)|QI|一定時(shí)，隨著采樣率的增加，抽樣尋徑時(shí)間占比均有大幅度上升，然而信息損失量的波動(dòng)幅度較小，故可使用較小的采樣率；同時(shí)因抽樣率越大越符合數(shù)據(jù)集的分布，故要使用足夠數(shù)量的樣本代表數(shù)據(jù)集。綜合以上所述，本文以下實(shí)驗(yàn)均采用1%的抽樣率。

圖2 抽樣尋徑時(shí)間占比與采樣率的關(guān)系

圖3 信息損失量與采樣率的關(guān)系

3.2.2 信息損失量分析

圖4為準(zhǔn)標(biāo)識(shí)符屬性個(gè)數(shù)|QI|=7，k取 5/10/15/20/ 25/50時(shí)，SPOLG算法和 Incognito算法匿名化數(shù)據(jù)集信息損失量的比較。由圖4知，執(zhí)行SPOLG算法和Incognito算法產(chǎn)生的信息損失量隨 k值的增加而增加，這是由于k值變大時(shí)，每個(gè)等價(jià)類所含元組數(shù)量增多，數(shù)據(jù)集泛化程度變大，故IL增大。但隨k值的變大，SPOLG算法信息損失IL增加幅度較小。其原因在表3中可以清晰看出，元組前三步泛化比例達(dá)50%以上，由此可知數(shù)據(jù)集中的大部分元組都只經(jīng)過一次泛化，因此泛化后的數(shù)據(jù)集信息損失IL小，隨著k值的變大IL增加較小。圖5表示當(dāng) k=10時(shí)，|QL|取 3/4/5/6/7，SPOLG算法與Incognito算法匿名化數(shù)據(jù)信息損失量的比較。從圖5可以看出，Incognito算法產(chǎn)生的信息損失IL呈明顯上升趨勢(shì)，本文算法隨著準(zhǔn)標(biāo)識(shí)符屬性的|QI|增多信息損失IL無明顯波動(dòng)。表4中數(shù)據(jù)表明，|QI|增大時(shí)，前三步泛化比例均達(dá)到60%。由此可見，數(shù)據(jù)集中的大部分元組都只經(jīng)過一次泛化，因此泛化后的數(shù)據(jù)集信息損失IL小，隨著|QI|的增加 IL無明顯波動(dòng)。綜合以上所述：本文算法在信息損失方面具有明顯的優(yōu)勢(shì)，發(fā)布的數(shù)據(jù)信息失真較少，可用性高。

圖4 |QI|=7時(shí)信息損失IL與k值的關(guān)系

圖5 k=10時(shí)信息損失IL與|QI|的關(guān)系

表3 不同k值下的前三步泛化情況

表4 不同|QI|值下的前三步泛化情況

3.2.3 時(shí)間效率分析

圖6、圖8分別表示運(yùn)行時(shí)間、k和|QI|的關(guān)系。由圖6知，當(dāng)|QI|一定時(shí)，由于k值增大，泛化程度變大，產(chǎn)生的等價(jià)類數(shù)量變少，每個(gè)元組尋找等價(jià)類的時(shí)間大幅度降低。由圖7知，當(dāng)k值一定時(shí)，隨著|QI|的增加，約束條件變多，等價(jià)類數(shù)量增多，每個(gè)元組尋找等價(jià)類的時(shí)間變大，所以本算法運(yùn)行時(shí)間有所增加。綜合圖6、圖7可知，本文算法在時(shí)間效率上比Incognito算法略差，但是由于信息損失量的大幅度降低，因此本算法的綜合優(yōu)勢(shì)明顯。

圖6 |QI|=7時(shí)運(yùn)行時(shí)間與k值的關(guān)系

圖7 k=10時(shí)運(yùn)行時(shí)間與|QI|的關(guān)系

4 總結(jié)

本文提出一種基于準(zhǔn)標(biāo)識(shí)符屬性泛化路徑的K-匿名化算法——SPOLG算法，該算法采用等概率抽樣的方法快速尋找泛化路徑，在已找到泛化路徑的基礎(chǔ)上進(jìn)行數(shù)據(jù)集的局域泛化。實(shí)驗(yàn)結(jié)果表明，該算法泛化的數(shù)據(jù)表信息損失較小，可用性高。

[1]SWEENEY L.A model for protecting privacy[J].International Journal on Uncertainty Fuzziness and Knowledge-Based Systems，2002，10(5)：557-570.

[2]SWEENY L.Achieving k-anonymity privacy protection using generalization and suppression[J].International Journal of Uncertainty，F(xiàn)uzziness and Knowledge-Based Systems：IJUFKS，2002，10(5)：571-588.

[3]SWEENY L．Guaranteeing anonymity when sharing medical data：the datafly system[C].Proceedings of the 1997 AMIA Annual Fall Symposium，Journal of the American Medial Informatis，Association，AMIA，1997，4(suppl)：51-55．

[4]MACHANAVAJJHALA A，GEHRKE J，KIFER D.L-diversity：Privacy beyond k-anonymity[C].Proc of the 22nd In Conference on Data Engineering.Piscataway,NJ：IEEE，2006：24-36.

[5]LI J Y，WONG C W，F(xiàn)U W C，et al.Achieving k-anonymity by clustering in attribute hierarchical structures[C].Data Warehousing and Knowledge Discovery.Springer Berlin Heidelberg，2006：405-416.

[6]任向民.基于 K-匿名的隱私保護(hù)方法研究[D].哈爾濱：哈爾濱工業(yè)大學(xué)，2012.

K-anonymous privacy protection algorithm based on the sampling path

Wu Xiang，Zang Hao，Yu Xiao
(School of Medical Informatics，Xuzhou Medical University，Xuzhou 221116，China)

K-anonymity is a common technique of information privacy protection.But K-anonymity must cause the information loss and how to improve the usability of anonymizing tables is the emphasis of K-anonymity.To solve the problem,this paper puts forward a kind of anonymous privacy protection algorithm based on generalized path—SPOLG algorithm.It introduces sampling with equal probabilities to find the generalized path whose information loss is little and raise the efficiency of data processing.Experimental results show that the algorithm could satisfy the anonymous requirement,at the same time,it is more efficient than Incognito algorithm to reduce the information loss of data released.

privacy preservation；path；information loss；sample；K-anonymity

TP391

A

10.16157/j.issn.0258-7998.2016.12.030

吳響，臧昊，俞嘯.基于抽樣路徑的 K-匿名隱私保護(hù)算法[J].電子技術(shù)應(yīng)用，2016，42(12)：115-118.

英文引用格式：Wu Xiang，Zang Hao，Yu Xiao.K-anonymous privacy protection algorithm based on the sampling path[J].Application of Electronic Technique，2016，42(12)：115-118.

2016-05-22)

吳響（1985-），男，博士，實(shí)驗(yàn)師，主要研究方向：信息安全、隱私保護(hù)。

臧昊（1992-），男，碩士，主要研究方向：軟件工程、隱私保護(hù)。

俞嘯（1989-），男，碩士，實(shí)驗(yàn)師，主要研究方向：信息安全、隱私保護(hù)。

江蘇省產(chǎn)學(xué)研聯(lián)合創(chuàng)新項(xiàng)目(BY2014033)；徐州市科技計(jì)劃項(xiàng)目(XM13B021)；國家安全生產(chǎn)重大事故防治關(guān)鍵技術(shù)科技項(xiàng)目（Jiangsu-0006-2016AQ）