0 引言

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

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

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

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

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

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

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

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>泛化樣本信息損失小,，則選取<W1,，R0>為路徑的第2個(gè)節(jié)點(diǎn)，以此類推,。如<W0,，R0>→<W1，R0>→<W1，R1>→<W2,，R1>這條路線是一條可能的抽樣泛化路徑,。

    定義4  抽樣尋徑時(shí)間占比：由抽樣數(shù)據(jù)產(chǎn)生抽樣泛化路徑所花費(fèi)的時(shí)間S_P在整個(gè)算法流程中的百分比。假設(shè)整個(gè)算法花費(fèi)的時(shí)間為S_A,，則其計(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)抽取樣本

    (2)尋找抽樣泛化路徑

       函數(shù)：path(QI，T′)

       /*QI為準(zhǔn)標(biāo)識(shí)符集,，T′表示抽樣數(shù)據(jù)集*/

       Begin

       ①通過(guò)QI形成泛化格G,；

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

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

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

       ⑤返回路徑P,；

       End

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

    移除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)開(kāi)始,，自底向上對(duì)不滿足K-匿名的元組進(jìn)行泛化,，直到所有元組滿足K-匿名。

2.2 算法合理性分析

    本文算法使用系統(tǒng)抽樣,，能夠保證每個(gè)元組被抽取概率相同,，通過(guò)等概率抽樣樣本快速尋找到信息損失較低的泛化路徑，使得數(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ù)集是由美國(guó)人口普查數(shù)據(jù)構(gòu)成,，采用數(shù)據(jù)集中的訓(xùn)練集，并去除缺省值記錄,，共有30 162條記錄,，本文選取7個(gè)屬性作為準(zhǔn)標(biāo)識(shí)符屬性，包括性別,、種族,、婚姻狀況、教育程度,、工作,、國(guó)籍、年齡,，各屬性預(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ì)算方法,。

    元組的信息損失量：

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

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

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)過(guò)一次泛化，因此泛化后的數(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無(wú)明顯波動(dòng),。表4中數(shù)據(jù)表明，|QI|增大時(shí),，前三步泛化比例均達(dá)到60%,。由此可見(jiàn)，數(shù)據(jù)集中的大部分元組都只經(jīng)過(guò)一次泛化,，因此泛化后的數(shù)據(jù)集信息損失IL小,，隨著|QI|的增加IL無(wú)明顯波動(dòng)。綜合以上所述：本文算法在信息損失方面具有明顯的優(yōu)勢(shì),，發(fā)布的數(shù)據(jù)信息失真較少,，可用性高。

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ì)明顯,。

4 總結(jié)

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

參考文獻(xiàn)

[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.