文獻標識碼: 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.
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),表中每條元組指明一個特定實體的相關信息,如年齡、工作、種族、性別、工作時長、工資(敏感屬性)等。
1.2 SPOLG算法相關定義
定義2 系統抽樣:將數據集中的元組按照ID排序,隨機選取一條元組作為起點,每隔一定的間隔抽取一個元組,直至樣本數量滿足事先給定的抽樣率。
定義3 抽樣泛化路徑:以泛化格的根節點為起點,計算其子節點對樣本泛化后的信息損失量,將信息損失量最小子節點插入路徑,自底向上,直至泛化格葉子節點。
例如:圖1中,若用<W1,R0>這個節點泛化樣本比<W0,R1>泛化樣本信息損失小,則選取<W1,R0>為路徑的第2個節點,以此類推。如<W0,R0>→<W1,R0>→<W1,R1>→<W2,R1>這條路線是一條可能的抽樣泛化路徑。
定義4 抽樣尋徑時間占比:由抽樣數據產生抽樣泛化路徑所花費的時間SP在整個算法流程中的百分比。假設整個算法花費的時間為SA,則其計算公式為:
2 算法實現
2.1 算法實現
本文提出的一個基于抽樣路徑的局域泛化算法——SPOLG算法,引進了等概率抽樣的思想,以系統抽樣樣本代替數據集尋找泛化路徑,具體算法如下:
輸入:輸入表T,準標識符集合QI,等價類約束k以及抽樣率α。
輸出:滿足K-匿名的數據集T″。
(1)抽取樣本
(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)匿名化數據表
移除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]的計算方法。
元組的信息損失量:
3.2.1 數據抽樣分析
尋徑時間占比通過式(1)進行計算,信息損失量依據公式(2)、(3)來度量,由圖2、圖3可知,當|QI|一定時,隨著采樣率的增加,抽樣尋徑時間占比均有大幅度上升,然而信息損失量的波動幅度較小,故可使用較小的采樣率;同時因抽樣率越大越符合數據集的分布,故要使用足夠數量的樣本代表數據集。綜合以上所述,本文以下實驗均采用1%的抽樣率。
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無明顯波動。綜合以上所述:本文算法在信息損失方面具有明顯的優勢,發布的數據信息失真較少,可用性高。
3.2.3 時間效率分析
圖6、圖8分別表示運行時間、k和|QI|的關系。由圖6知,當|QI|一定時,由于k值增大,泛化程度變大,產生的等價類數量變少,每個元組尋找等價類的時間大幅度降低。由圖7知,當k值一定時,隨著|QI|的增加,約束條件變多,等價類數量增多,每個元組尋找等價類的時間變大,所以本算法運行時間有所增加。綜合圖6、圖7可知,本文算法在時間效率上比Incognito算法略差,但是由于信息損失量的大幅度降低,因此本算法的綜合優勢明顯。
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.