《電子技術應用》
您所在的位置:首頁 > 嵌入式技術 > 設計應用 > 基于抽樣路徑的K-匿名隱私保護算法
基于抽樣路徑的K-匿名隱私保護算法
2016年電子技術應用第12期
吳 響,臧 昊,俞 嘯
徐州醫科大學 醫學信息學院,江蘇 徐州221116
摘要: K-匿名是信息隱私保護的一種常用技術,而使用K-匿名技術不可避免會造成發布數據的信息損失,因此,如何提高K-匿名化后數據集的可用性一直以來都是K-匿名隱私保護的研究重點。對此提出了一種基于抽樣路徑的局域泛化算法——SPOLG算法。該算法基于泛化格尋找信息損失較小的泛化路徑,為減少尋徑時間,引入等概率抽樣的思想,選用等概率抽樣中的系統抽樣方法進行取樣,利用樣本代替數據集在泛化格上尋找目標泛化路徑,最后在該路徑上對數據集進行泛化。同時,本算法使用局域泛化技術,能夠降低信息損失量,提高發布數據集的可用性。實驗結果證明,本算法匿名化的數據集信息損失度低,數據可用性高。
中圖分類號: TP391
文獻標識碼: A
DOI:10.16157/j.issn.0258-7998.2016.12.030
中文引用格式: 吳響,臧昊,俞嘯. 基于抽樣路徑的K-匿名隱私保護算法[J].電子技術應用,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.
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
Abstract: 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.
Key words : privacy preservation;path;information loss;sample;K-anonymity

0 引言

    K-匿名[1]是一種簡單而有效的隱私保護模型,實施K-匿名要考慮兩個方面:(1)確保數據發布過程中隱私不泄露;(2)發布的匿名數據具有實用性。

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

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

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

1 基本符號和定義

1.1 K-匿名相關定義

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

jsj3-b1.gif

jsj3-b1-x.gif

jsj3-b2.gif

1.2 SPOLG算法相關定義

    定義2  系統抽樣:將數據集中的元組按照ID排序,隨機選取一條元組作為起點,每隔一定的間隔抽取一個元組,直至樣本數量滿足事先給定的抽樣率。

    定義3  抽樣泛化路徑:以泛化格的根節點為起點,計算其子節點對樣本泛化后的信息損失量,將信息損失量最小子節點插入路徑,自底向上,直至泛化格葉子節點。

    例如:圖1中,若用<W1,R0>這個節點泛化樣本比<W0,R1>泛化樣本信息損失小,則選取<W1,R0>為路徑的第2個節點,以此類推。如<W0,R0>→<W1,R0>→<W1,R1>→<W2,R1>這條路線是一條可能的抽樣泛化路徑。

jsj3-t1.gif

    定義4  抽樣尋徑時間占比:由抽樣數據產生抽樣泛化路徑所花費的時間SP在整個算法流程中的百分比。假設整個算法花費的時間為SA,則其計算公式為:

    jsj3-gs1.gif

2 算法實現

2.1 算法實現

    本文提出的一個基于抽樣路徑的局域泛化算法——SPOLG算法,引進了等概率抽樣的思想,以系統抽樣樣本代替數據集尋找泛化路徑,具體算法如下:

輸入:輸入表T,準標識符集合QI,等價類約束k以及抽樣率α。

輸出:滿足K-匿名的數據集T″。

    (1)抽取樣本

jsj3-2.1-x1.gif

    (2)尋找抽樣泛化路徑

       函數:path(QI,T′)

       /*QI為準標識符集,T′表示抽樣數據集*/

       Begin

       ①通過QI形成泛化格G;

       ②將泛化格G的第0層節點n0作為路徑P的起點P0

       ③通過泛化格找到n1直接泛化的節點,計算這些節點泛化T′所得到的信息損失量,選出泛化數據集T′信息損失量最小的節點n2作為路徑P的第二個節點P1;

       ④重復步驟②直至到達泛化格G的頂點ni作為路徑的終點Pi得到路徑P;

       ⑤返回路徑P;

       End

    (3)匿名化數據表

jsj3-2.1-x2.gif

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

    結束循環;

       ⑤返回數據表;

    End

    由以上步驟可知,該算法主要包括系統抽樣、尋找路徑、 匿名化數據集3個主要環節,利用系統抽樣選取樣本,在已選擇的樣本中尋找信息損失較低的泛化路徑,由已選路徑對數據集進行局域泛化。從路徑起點開始,自底向上對不滿足K-匿名的元組進行泛化,直到所有元組滿足K-匿名。

2.2 算法合理性分析

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

3 實驗驗證及結果分析

3.1 實驗環境

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

3.2 實驗結果分析

    實驗主要從信息損失度及執行時間方面對本文算法進行衡量。本實驗選用Incognito算法作為對比算法,比較了在不同個數的準標識符和不同k值條件下信息損失度和執行時間的變化。其中信息損失度采用文獻[6]的計算方法。

    元組的信息損失量:

jsj3-gs2-3.gif

3.2.1 數據抽樣分析

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

jsj3-t2-3.gif

3.2.2 信息損失量分析

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

jsj3-t4-5.gif

jsj3-b3.gif

jsj3-b4.gif

3.2.3 時間效率分析

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

jsj3-t6-7.gif

4 總結

    本文提出一種基于準標識符屬性泛化路徑的K-匿名化算法——SPOLG算法,該算法采用等概率抽樣的方法快速尋找泛化路徑,在已找到泛化路徑的基礎上進行數據集的局域泛化。實驗結果表明,該算法泛化的數據表信息損失較小,可用性高。

參考文獻

[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,Fuzziness 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,FU 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-匿名的隱私保護方法研究[D].哈爾濱:哈爾濱工業大學,2012.

此內容為AET網站原創,未經授權禁止轉載。
主站蜘蛛池模板: 五月网 | 青青青国产在线 | 五月综合色啪 | 翁熄性放纵苏玥完整小说 | 九九在线视频 | 日本一区二区三区视频在线观看 | 中国黄色片视频 | 欧美国产激情二区三区 | 国产尤物二区三区在线观看 | 日日日插插插 | 国产成人99精品免费观看 | 亚洲日本欧美 | 成人网18视频网站 | 在线韩国伦理 | 日批网站免费 | 香蕉视频污污在线观看 | 五月婷婷色综合 | 国产综合视频在线观看 | 香蕉精品一本大道在线观看 | 九九久久国产精品免费热6 九九久久亚洲综合久久久 九九伦理 | 成年人免费观看视频网站 | 中文字幕丝袜美腿 | 色图综合网 | 麻豆国产一区 | 一级特级欧美午夜片免费观看 | 又猛又黄又爽无遮挡的视频网站 | 成人欧美精品一区二区不卡 | 在线观看一区二区三区视频 | 日韩精品欧美激情亚洲综合 | 看全色黄大色黄女片18 | 日批在线 | 免费看羞羞视频的网站 | 福利视频黄 | 日批视频在线免费看 | 国产免费成人在线视频 | 日本免费不卡视频一区二区三区 | 国产一区二三区 | 在线免费黄色 | 国产精品高清免费网站 | 亚洲成综合人影院在院播放 | 天天干天天操天天 |