蔣浩英 ,錢 進(jìn),2* ,王滔滔 ,洪承鑫 ,余 鷹

（1.華東交通大學(xué)軟件學(xué)院，南昌，330013；2.江蘇科技大學(xué)計(jì)算機(jī)學(xué)院，鎮(zhèn)江，212003）

信息時(shí)代，數(shù)據(jù)已經(jīng)成為一種重要的戰(zhàn)略資源，數(shù)據(jù)收集和共享被廣泛應(yīng)用于各個(gè)領(lǐng)域，創(chuàng)造了不菲的價(jià)值，然而，外包式的數(shù)據(jù)共享不可避免地增加了隱私泄露的風(fēng)險(xiǎn)，威脅用戶信息安全.近年來(lái)，數(shù)據(jù)可用性和隱私性的對(duì)立引起了國(guó)內(nèi)外學(xué)者的廣泛關(guān)注，如何實(shí)現(xiàn)兩者的最大平衡成為隱私保護(hù)領(lǐng)域的研究熱點(diǎn)［1-3］.

數(shù)據(jù)匿名是一種重要的隱私保護(hù)技術(shù)，和基于數(shù)據(jù)失真和基于數(shù)據(jù)加密的技術(shù)相比，數(shù)據(jù)匿名技術(shù)能更好地平衡數(shù)據(jù)的可用性和隱私的安全性.k-匿名是一種典型的數(shù)據(jù)匿名模型，2002 年由Sweeney［4］提出后受到了廣泛關(guān)注.該模型通過(guò)在準(zhǔn)標(biāo)識(shí)屬性上構(gòu)建等價(jià)類，保證數(shù)據(jù)集中的任意一條記錄都至少存在k-1 條不可區(qū)分的記錄來(lái)降低敵手正確識(shí)別的概率，從而保護(hù)數(shù)據(jù)安全.隨后，為了進(jìn)一步提高數(shù)據(jù)匿名的效率，研究者們又相繼提出一系列新的研究成果和改進(jìn)技術(shù)，代表性的有Machanavajjhala et al［5］的l-多樣性模型，Wong et al［6］的(α，k)-匿名模型，Li et al［7］的t-closeness 模型.近年來(lái)對(duì)數(shù)據(jù)匿名改進(jìn)算法的研究仍在如火如荼地進(jìn)行.Liang and Samavi［8］通過(guò)數(shù)學(xué)優(yōu)化問(wèn)題的k-匿名公式，提出基于優(yōu)化的k-匿名算法.張強(qiáng)等［9］基于最優(yōu)聚類結(jié)果，提出最優(yōu)聚類的k-匿名隱私保護(hù)機(jī)制.翟冉等［10］利用隨機(jī)森林和k-means 算法，提出一種更適合分類預(yù)測(cè)的PFK-算法.Kacha et al［11］在自然啟發(fā)算法的基礎(chǔ)上，提出一種新的基于黑洞算法的k-匿名方法.Mehta and Rao［12］使用MapReduce 作為編程框架，提出適應(yīng)大數(shù)據(jù)隱私保護(hù)的改進(jìn)的可擴(kuò)展的l-多樣性算法.不難發(fā)現(xiàn)，現(xiàn)有的k-匿名模型及其改進(jìn)技術(shù)已經(jīng)解決了大多數(shù)隱私泄露問(wèn)題，逐漸趨于成熟.然而，無(wú)論是傳統(tǒng)的k-匿名模型還是之后的改進(jìn)技術(shù)，都存在同一個(gè)缺陷，即采取的都是二分類的匿名策略.現(xiàn)有的匿名模型無(wú)一不在匿名處理后將數(shù)據(jù)嚴(yán)格劃分為兩部分，滿足匿名需求的數(shù)據(jù)被視為安全數(shù)據(jù)進(jìn)行發(fā)布，不滿足匿名需求的數(shù)據(jù)則進(jìn)行隱匿和舍棄.但在實(shí)際決策中，這種“非此即彼”的處理方式往往過(guò)于絕對(duì)，大多數(shù)情況下，數(shù)據(jù)之間的聯(lián)系并非嚴(yán)格的二分關(guān)系，例如，很多被舍棄的數(shù)據(jù)都十分接近匿名需求，它們只需要進(jìn)行代價(jià)不大的再處理就能成為安全數(shù)據(jù)被人們利用.

三支決策［13-16］為分類匿名提供了新思路.三支決策是一種基于人類認(rèn)知的決策方式，常用于分析和解決復(fù)雜問(wèn)題［13］，已被推廣并應(yīng)用于各個(gè)領(lǐng)域，在人臉識(shí)別［17］、數(shù)據(jù)挖掘［18］、聚類分析［19］、推薦［20］等領(lǐng)域都取得了矚目的成就，三支分類［21-23］、三支聚類［19，24］、三支概念分析［25］等諸多主題也被越來(lái)越多的學(xué)者研究和應(yīng)用.為了應(yīng)對(duì)實(shí)際決策過(guò)程中可能出現(xiàn)的不確定性情況，和“非此即彼”的二支決策相比，三支決策增加了一個(gè)處理過(guò)程，即延遲決策.延遲決策的存在使得對(duì)問(wèn)題的考慮更全面，可以避免很多不必要的損失.因此，為了提高數(shù)據(jù)的可用性，本文將三支決策的思想引入數(shù)據(jù)匿名，提出匿名上、下限的概念，并以k-匿名為例，提出基于三支決策的(Uk，Lk)-分類匿名模型.該模型充分考慮匿名過(guò)程中可能出現(xiàn)的模糊數(shù)據(jù)，通過(guò)對(duì)模糊數(shù)據(jù)的延遲決策處理，進(jìn)一步完善匿名模型，提高匿名效率.

1 相關(guān)理論

1.1 k-匿名k-匿名是Sweeney［26］提出的一種用于抵御鏈接攻擊的數(shù)據(jù)匿名模型，通常用泛化或抑制的手段對(duì)原始數(shù)據(jù)集進(jìn)行匿名處理.該模型利用準(zhǔn)標(biāo)識(shí)屬性將記錄劃分為不同的等價(jià)組，通過(guò)保證待發(fā)布數(shù)據(jù)集中的每條記錄都至少擁有k-1 個(gè)等價(jià)類的方式來(lái)降低敵手的攻擊準(zhǔn)確度.為了更清晰地表達(dá)，下面給出幾個(gè)基礎(chǔ)定義.

定義1 準(zhǔn)標(biāo)識(shí)屬性QI是待發(fā)布數(shù)據(jù)集中的一個(gè)屬性集合，通常和敏感屬性一起發(fā)布.通過(guò)結(jié)合背景信息，能以較高的概率推斷出記錄身份的最小屬性集合.

定義2 敏感屬性SA是待發(fā)布數(shù)據(jù)集中包含個(gè)人敏感信息的屬性，也是攻擊者最想確定和關(guān)聯(lián)的屬性.

表1 展示了一個(gè)原始數(shù)據(jù)集，其中{性別，年齡，學(xué)歷}為準(zhǔn)標(biāo)識(shí)屬性集，{疾病}為敏感屬性集.

表1 原始數(shù)據(jù)集Table 1 Original dataset

定義3 等價(jià)組EG在待發(fā)布數(shù)據(jù)集中，準(zhǔn)標(biāo)識(shí)屬性完全相同的記錄集構(gòu)成一個(gè)等價(jià)組，也稱為一個(gè)QI-組.

定義4 k-匿名給定一個(gè)待發(fā)布數(shù)據(jù)集T={U，Ar=QI∪S∪O}，其中，U是一個(gè)非空的記錄集合，Ar是記錄對(duì)應(yīng)的屬性集，包括準(zhǔn)標(biāo)識(shí)屬性QI、敏感屬性S以及其他屬性O(shè)，當(dāng)且僅當(dāng)T[QI]中每一個(gè)有序的值在T[QI]中至少出現(xiàn)k次，待發(fā)布數(shù)據(jù)集T滿足k-匿名.

表2 是表1 的一個(gè)5-匿名數(shù)據(jù)表，G1和G2是針對(duì)準(zhǔn)標(biāo)識(shí)屬性集{性別，年齡，學(xué)歷}的兩個(gè)等價(jià)組，|G1|≥5，滿足5-匿名；|G2|＜5，不滿足5-匿名.

表2 表1 的一個(gè)5-匿名數(shù)據(jù)表Table 2 A 5-anonymity table of Table 1

定義5 匿名上、下限匿名需要滿足的初始需求為匿名上限.不滿足卻十分接近匿名上限且在實(shí)際決策中允許少部分?jǐn)?shù)據(jù)滿足的匿名要求為匿名下限.

假設(shè)表2 的初始匿名要求為5-匿名，則其匿名上限為5；若實(shí)際決策中允許少部分?jǐn)?shù)據(jù)滿足的容錯(cuò)匿名要求為4-匿名，則4 為其匿名下限.

定義6 模糊數(shù)據(jù)T={U，At=QI∪S∪O}為待發(fā)布數(shù)據(jù)集，U/QI={G1，G2，…，Gn}是根據(jù)準(zhǔn)標(biāo)識(shí)屬性QI劃分的等價(jià)組，|Gi|代表等價(jià)組Gi的大小，f(x)代表對(duì)象x所在的等價(jià)組的大小(若x∈Gi，則f(x)=|Gi|).給定匿名閾值對(duì)(Uk，Lk)，其中，Uk表示匿名上限，Lk表示匿名下限，當(dāng)Lk＜f(x)＜Uk時(shí)，記錄x為模糊數(shù)據(jù).

假設(shè)表2 中Uk=5，Lk=3，根據(jù)定義6，|G1|≥5，為可發(fā)布的安全數(shù)據(jù)；3 ＜|G2|＜5，為模糊數(shù)據(jù).

1.2 三支決策和二支決策相比，三支決策［13-16］增加了一個(gè)額外的處理過(guò)程，即延遲決策.當(dāng)對(duì)事物信息的掌握不充分、認(rèn)知不徹底、無(wú)法作出全面的風(fēng)險(xiǎn)評(píng)估時(shí)，采取延遲的方式，將這部分信息暫存到邊界域來(lái)暫緩決策，等收集了足夠的信息或?qū)︼L(fēng)險(xiǎn)了解到足夠的程度后再接受或者拒絕.圖1 對(duì)比了二支決策和三支決策的決策過(guò)程.

圖1 二支決策(a)和三支決策(b)的決策過(guò)程對(duì)比Fig.1 Decision-making process of two-way (a) and three-way (b) decisions

三支分類是一種有效的數(shù)據(jù)處理方法，也是三支決策最常見的應(yīng)用領(lǐng)域.Yao［13，21］從概率粗糙集的角度研究了三支分類問(wèn)題，探討了三支決策在概率粗糙集下的優(yōu)勢(shì)，并指出三支決策可以通過(guò)權(quán)衡不同類型的分類誤差，實(shí)現(xiàn)最低的決策成本，降低分類風(fēng)險(xiǎn).為了更好地模擬人的思考過(guò)程，定義7 從決策理論粗糙集的角度，引入評(píng)價(jià)函數(shù)和閾值來(lái)重新刻畫三支決策模型.

定義7設(shè)S=(U，R)是一個(gè)信息系統(tǒng)，U=(x1，x2，…，xn)是一個(gè)非空有限對(duì)象集合，R是論域U上的二元關(guān)系，評(píng)價(jià)函數(shù)e(x)表示對(duì)象x的評(píng)價(jià)值.引入一對(duì)閾值α和β，論域U可被劃分為三部分：

利用閾值來(lái)劃分論域可以更好地模擬人的思考過(guò)程，閾值α和β一般由決策者容忍度或?qū)＜医?jīng)驗(yàn)事先給定.

2 基于三支決策的(Uk,Lk)-分類匿名模型

為了充分考慮實(shí)際匿名過(guò)程中可能出現(xiàn)的模糊數(shù)據(jù)，解決二分類匿名的弊端，本文將三支決策的思想應(yīng)用到數(shù)據(jù)匿名中，以k-匿名為例，提出一種基于三支決策的(Uk，Lk)-分類匿名模型，其中，Uk表示匿名上限，Lk表示匿名下限.

2.1 屬性泛化抑制和泛化是k-匿名中的常用策略［26］.為了能對(duì)數(shù)值型屬性和分類型屬性進(jìn)行統(tǒng)一處理，首先利用屬性之間的泛化關(guān)系來(lái)構(gòu)建屬性泛化樹，將數(shù)據(jù)集中的準(zhǔn)標(biāo)識(shí)屬性都處理為具有層次結(jié)構(gòu)的屬性；然后，通過(guò)提升記錄在屬性泛化樹中的層級(jí)，用范圍廣的上級(jí)節(jié)點(diǎn)代替下級(jí)子節(jié)點(diǎn)，構(gòu)建等價(jià)類，實(shí)現(xiàn)k-匿名.圖2 展示了表1 中的準(zhǔn)標(biāo)識(shí)屬性集{性別，年齡，學(xué)歷}對(duì)應(yīng)的屬性泛化樹.

圖2 表1 中準(zhǔn)標(biāo)識(shí)屬性對(duì)應(yīng)的屬性泛化樹Fig.2 The attribute generalization trees corresponding to the quasi-Identifier attributes in Table 1

2.2 模型構(gòu)建屬性泛化完成后，將三支決策的思想引入數(shù)據(jù)匿名，利用三支決策對(duì)待發(fā)布數(shù)據(jù)集進(jìn)行分類決策匿名.首先，定義6 中的f(x)作為評(píng)價(jià)函數(shù)，根據(jù)定義7 將待發(fā)布數(shù)據(jù)集劃分為低敏感數(shù)據(jù)（LSR）、模糊敏感數(shù)據(jù)（FSR）和高敏感數(shù)據(jù)（HSR）.具體劃分方式如下：

其中，f(x)是記錄x所在的等價(jià)組的大小；QI是原始數(shù)據(jù)集U中的準(zhǔn)標(biāo)識(shí)屬性；(Uk，Lk)是根據(jù)實(shí)際應(yīng)用場(chǎng)景設(shè)定的匿名上、下限，可以將數(shù)據(jù)集劃分為三個(gè)成對(duì)不相交的區(qū)域.

接下來(lái)，根據(jù)三支決策的思想，對(duì)不同區(qū)域的記錄采取不同的決策方式：對(duì)高于匿名上限的低敏感數(shù)據(jù)直接進(jìn)行安全發(fā)布；抑制低于匿名下限的高敏感數(shù)據(jù).為了提高數(shù)據(jù)的利用率，單獨(dú)劃分出接近匿名需求的模糊敏感數(shù)據(jù)，并對(duì)其進(jìn)行進(jìn)一步的處理（例如添加噪聲數(shù)據(jù)，使其滿足匿名需求等）.圖3 是所提模型的示意圖.由圖可見，通過(guò)分類決策匿名，三支分類匿名模型將數(shù)據(jù)處理成更符合人類思維模式的三分形式，用延遲決策的方式充分考慮實(shí)際決策中可能出現(xiàn)的不確定性因素，進(jìn)一步提高匿名效率，優(yōu)化傳統(tǒng)的二分類匿名模型.

圖3 一種基于三支決策的新型分類匿名模型Fig.3 A novel classified anonymity model based on three-way decisions

2.3 添加噪聲為了驗(yàn)證所提模型的可用性，本文結(jié)合差分隱私，用少量添加噪聲的方式來(lái)實(shí)現(xiàn)對(duì)模糊數(shù)據(jù)的延遲決策，并給出以下定理.

定理1若等價(jià)組G1和等價(jià)組G2滿足相同的k-匿名需求，則G1∪G2也滿足該匿名需求.

證明令等價(jià)組Ga={a1，a2，…，an}和等價(jià)組Gb={b1，b2，…，bm}都滿足k-匿名，|Ga|=ka，|Gb|=kb，其中|Ga|和|Gb|分別為等價(jià)組Ga和Gb的大小.根據(jù)定義4，不難得到ka≥k且kb≥k.令Gs=Ga∪Gb，|Gs|為數(shù)據(jù)集Gs中最小等價(jià)組的大小，則有|Gs|=min{|Ga|，|Gb|}=min{ka，kb}≥k.因此，|Gs|≥k.根據(jù)定義4，Ga∪Gb滿足k-匿名.

證畢.

定理2若待發(fā)布數(shù)據(jù)集中的每一個(gè)等價(jià)組都滿足相同的k-匿名需求，則待發(fā)布數(shù)據(jù)集滿足該匿名需求.

證明令待發(fā)布數(shù)據(jù)集S={G1，G2，…，Gn}，其中G1，G2，…，Gn為該數(shù)據(jù)集中的等價(jià)組.當(dāng)S中的所有等價(jià)組都滿足k-匿名時(shí)，根據(jù)定義4 可以得到|G1|≥k，|G2|≥k，…，|Gn|≥k.假設(shè)|Gs|為該待發(fā)布數(shù)據(jù)集S中最小等價(jià)組的大小，則有|Gs|=min{|Ga|，|Gb|，…，|Gn|}≥k.因此，|Gs|≥k，待發(fā)布數(shù)據(jù)集S={G1，G2，…Gn}滿足k-匿名.

證畢.

因此，根據(jù)定理1 和定理2，當(dāng)原始數(shù)據(jù)集中存在模糊數(shù)據(jù)集時(shí)，只需通過(guò)特定方式對(duì)模糊數(shù)據(jù)進(jìn)行再處理，使其滿足匿名需求，即可實(shí)現(xiàn)對(duì)這部分模糊數(shù)據(jù)的安全數(shù)據(jù)發(fā)布，提高匿名效率.本文采用少量添加噪聲的方式來(lái)處理模糊數(shù)據(jù).具體地，當(dāng)原始數(shù)據(jù)集中存在模糊數(shù)據(jù)時(shí)，在可以容忍少量噪聲數(shù)據(jù)的情況下，通過(guò)復(fù)制模糊數(shù)據(jù)組中的等價(jià)類制造并添加新的噪聲數(shù)據(jù)，使得模糊等價(jià)組中的等價(jià)類個(gè)數(shù)達(dá)到匿名上限，滿足初始的Uk-匿名需求.

以表2 為例，G2為模糊數(shù)據(jù)集，在基于三支決策的(Uk，Lk)-分類匿名模型中復(fù)制G2中的記錄，制造并添加噪聲數(shù)據(jù)，使模糊數(shù)據(jù)集G2滿足匿名上限(Uk=5)來(lái)滿足匿名需求，提高數(shù)據(jù)的可用性.表3 是處理后的基于三支決策的(5，3)-分類匿名數(shù)據(jù)集.

表3 基于三支決策的(5,3)-分類匿名數(shù)據(jù)集Table 3 A (5,3)-classified anonymous dataset based on three-way decisions

顯然，表3 的數(shù)據(jù)利用率高于表2.值得一提的是，所提模型是一個(gè)適應(yīng)性較強(qiáng)的框架模型，對(duì)于具有不確定性的模糊數(shù)據(jù)，數(shù)據(jù)處理者可以根據(jù)實(shí)際情況進(jìn)行不同的延遲決策處理，提高數(shù)據(jù)的可用性.例如，除了添加噪聲的方式，在實(shí)際應(yīng)用中也可以通過(guò)其他更適宜的方式對(duì)模糊數(shù)據(jù)進(jìn)行再處理，使其滿足匿名要求.

3 基于三支決策的(Uk,Lk)-分類匿名算法

3.1 算法實(shí)現(xiàn)基于上述分析，提出基于三支決策的(Uk，Lk)-分類匿名算法，具體的偽代碼如下.

算法中，首先對(duì)原始數(shù)據(jù)集的準(zhǔn)標(biāo)識(shí)屬性進(jìn)行最小屬性泛化，根據(jù)泛化后的準(zhǔn)標(biāo)識(shí)屬性將原始數(shù)據(jù)集劃分為n個(gè)等價(jià)組，將滿足Uk-匿名的記錄劃分到正域，存入待發(fā)布安全數(shù)據(jù)集合Q中；將靠近Uk-匿名需求的模糊數(shù)據(jù)存入邊界域，等待延遲決策；低于匿名下限的數(shù)據(jù)被視為完全不符合匿名需求的數(shù)據(jù)，劃分到負(fù)域，直接進(jìn)行抑制.需要注意的是，延遲決策在實(shí)際應(yīng)用場(chǎng)景下是多樣化的.例如，在可以容忍少量噪聲數(shù)據(jù)的情況下，通過(guò)添加噪聲使其達(dá)到Uk-匿名需求，從而提高數(shù)據(jù)的利用率.如果實(shí)際匿名要求十分嚴(yán)格，不允許添加噪聲數(shù)據(jù)，或者需要添加的噪聲過(guò)多，嚴(yán)重影響了數(shù)據(jù)的可用性，應(yīng)將這部分?jǐn)?shù)據(jù)并入負(fù)域，直接抑制.后者是極端特殊情況，相當(dāng)于普通的二支匿名.

3.2 算法分析

3.2.1 有效性分析所提算法首先構(gòu)建了屬性泛化樹，利用屬性的泛化層次關(guān)系將屬性處理為具有層次結(jié)構(gòu)的屬性集，再引入三支決策的思想對(duì)數(shù)據(jù)進(jìn)行分類匿名決策.該算法采用泛化、隱匿以及少量添加噪聲的方式對(duì)原始數(shù)據(jù)集進(jìn)行模糊處理，降低了屬性之間的關(guān)聯(lián)度，每一步都使數(shù)據(jù)集向安全需求靠攏，最大程度地實(shí)現(xiàn)數(shù)據(jù)可用性和隱私性的平衡.算法的時(shí)間復(fù)雜度為O(n).因此，提出了下述定理.

定理3(Uk，Lk)-分類匿名算法滿足數(shù)據(jù)安全發(fā)布需求.

證明該算法提出匿名上、下限的概念，并引入了三支分類的思想，將原始數(shù)據(jù)集劃分為三個(gè)兩兩不相交的區(qū)域，對(duì)不同區(qū)域的數(shù)據(jù)分類處理.正域存儲(chǔ)低敏感數(shù)據(jù)，通過(guò)屬性泛化使其滿足Uk-匿名.負(fù)域存儲(chǔ)高敏感數(shù)據(jù)，但是該部分?jǐn)?shù)據(jù)即使泛化到根節(jié)點(diǎn)也無(wú)法滿足匿名要求，所以直接舍棄.邊界域是劃分出來(lái)的邊緣模糊數(shù)據(jù)，進(jìn)行泛化后這部分?jǐn)?shù)據(jù)不滿足但十分接近匿名上限Uk.為了盡可能提高數(shù)據(jù)的可用性，對(duì)這部分特殊數(shù)據(jù)采用添加適度噪聲的方式進(jìn)行二次處理.最終，處理后每一個(gè)區(qū)域都滿足安全發(fā)布需求.

證畢.

3.2.2 安全性分析(Uk，Lk)-分類匿名算法首先利用屬性泛化樹進(jìn)行最小屬性泛化，使每個(gè)等價(jià)組都滿足匿名上限Uk，即每條記錄都存在至少Uk-1 個(gè)等價(jià)類，從而降低敵手的正確辨識(shí)率.此外，在能容忍少量噪聲的情況下，該算法對(duì)高于匿名下限Lk的邊緣模糊數(shù)據(jù)進(jìn)行了再處理，通過(guò)添加噪聲數(shù)據(jù)的方式使模糊數(shù)據(jù)集中的任意記錄也都滿足匿名上限.無(wú)論是泛化還是添加噪聲，都能有效地切斷準(zhǔn)標(biāo)識(shí)屬性之間的關(guān)聯(lián)性，抵御敵手的鏈接攻擊，防止信息泄露，顯然，最后發(fā)布的安全數(shù)據(jù)集Q滿足Uk-匿名，保護(hù)了用戶的隱私.

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

首先定義四個(gè)算法的效用評(píng)估函數(shù)，包括信息抑制率、泛化損失率、數(shù)據(jù)失真率以及隱私泄漏風(fēng)險(xiǎn)，然后通過(guò)實(shí)驗(yàn)來(lái)度量所提算法的性能，對(duì)比Uk-匿名模型、(Uk，Lk)-分類匿名模型以及降低匿名要求后的(Lk+1)-匿名模型的實(shí)驗(yàn)結(jié)果.實(shí)驗(yàn)使用的數(shù)據(jù)集是來(lái)自機(jī)器學(xué)習(xí)數(shù)據(jù)庫(kù)的Adult 數(shù)據(jù)集，選取其中九個(gè)屬性進(jìn)行實(shí)驗(yàn).

實(shí)驗(yàn)環(huán)境：Intel（R）Core（TM）i5-1135G7@ 2.40 GHz 2.42 GHz，16.0 GB（RAM）內(nèi)存，Eclipse IDE 2022-03.

4.1 算法效用評(píng)估函數(shù)為了評(píng)估所提模型的實(shí)用性，定義幾個(gè)算法效用的評(píng)估函數(shù)，從信息抑制、泛化損失、數(shù)據(jù)失真以及隱私泄露風(fēng)險(xiǎn)幾個(gè)方面對(duì)所提算法進(jìn)行綜合評(píng)估.

4.1.1 信息抑制率給定原始數(shù)據(jù)集T，T'是進(jìn)行k-匿名后得到的待發(fā)布的安全數(shù)據(jù)集.信息抑制率指匿名處理后記錄的損耗率，定義如下：

其中，|T|是原始數(shù)據(jù)集中的記錄條數(shù)，|T'|是待發(fā)布數(shù)據(jù)集中的記錄條數(shù).信息抑制率越低，越接近原始數(shù)據(jù)集，數(shù)據(jù)的可用性越高.

4.1.2 泛化損失率給定原始數(shù)據(jù)集T，待發(fā)布數(shù)據(jù)集T'，T中準(zhǔn)標(biāo)識(shí)屬性對(duì)應(yīng)的屬性泛化樹共有l(wèi)(l=1，2，…，m)層.泛化損失率定義如下：

其中，|Si|表示泛化到第i層的記錄條數(shù)（i≤l），|T|是原始數(shù)據(jù)集中的記錄條數(shù)，|T'|是待發(fā)布數(shù)據(jù)集中的記錄條數(shù).

當(dāng)所有記錄在底層就滿足匿名條件時(shí)，記錄無(wú)須泛化，泛化損失率為0；泛化到根節(jié)點(diǎn)時(shí)，數(shù)據(jù)幾乎不可用.因此，當(dāng)所有記錄都泛化到最頂層或者都被抑制時(shí)，泛化損失率達(dá)到最大值1.

4.1.3 數(shù)據(jù)失真率噪聲數(shù)據(jù)的添加不可避免地會(huì)導(dǎo)致數(shù)據(jù)失真.假設(shè)M是添加的噪聲數(shù)據(jù)，信息失真率定義如下：

其中，|T|為原始信息中的記錄（真實(shí)記錄）條數(shù)，|M|為噪聲記錄條數(shù).

4.1.4 隱私泄露風(fēng)險(xiǎn)假設(shè)原始數(shù)據(jù)集為T，對(duì)T采取數(shù)據(jù)匿名處理，使其滿足k-匿名后得到待發(fā)布數(shù)據(jù)集T'.待發(fā)布數(shù)據(jù)集T'的隱私泄露風(fēng)險(xiǎn)為：

其中，R(x|T') 表示敵手從待發(fā)布數(shù)據(jù)集T'中準(zhǔn)確識(shí)別出對(duì)象x真實(shí)身份的概率.

4.2 信息抑制率度量為了分析不同算法的數(shù)據(jù)利用率，在不同的匿名上限Uk下，比較三種算法的信息抑制率隨匿名下限Lk的變化情況，實(shí)驗(yàn)結(jié)果按千分之一的形式取值.

實(shí)驗(yàn)結(jié)果如圖4 所示.顯然，與單一的Uk-匿名模型相比，所提(Uk，Lk)-分類匿名模型的信息抑制率明顯降低，數(shù)據(jù)可用性得到了增強(qiáng).這是因?yàn)椴捎昧朔诸惸涿姆绞?，模糊?shù)據(jù)被單獨(dú)劃分出來(lái)進(jìn)行再處理，提高了數(shù)據(jù)的利用率.其次，可以觀察到(Lk+1)-匿名模型通過(guò)直接降低匿名要求也可以達(dá)到近似相同的效果，但這是以犧牲安全性為代價(jià)的.即使如此，所提算法在某些情況下的效果還是優(yōu)于(Lk+1)-匿名模型，這也體現(xiàn)了分類匿名的優(yōu)勢(shì).

圖4 匿名上限Uk 不同時(shí)信息抑制率隨匿名下限Lk 的變化Fig.4 The variation of information suppression rate with Lk when Uk is different

由圖4 還可以看出，在匿名上限Uk固定時(shí)，隨著匿名下限Lk的下降，信息抑制率不斷減少，這是模糊區(qū)間增大的影響，模糊區(qū)間越大，可二次處理的數(shù)據(jù)越多，信息利用率越高.值得注意的是，模糊區(qū)間不是越大越好，過(guò)大的模糊區(qū)間會(huì)導(dǎo)致添加的噪聲過(guò)多，引發(fā)數(shù)據(jù)失真.最后，各組之間的實(shí)驗(yàn)也表明，在不同的匿名程度下三種算法的實(shí)驗(yàn)結(jié)果一致，避免了實(shí)驗(yàn)的偶然性.

4.3 泛化損失率度量屬性泛化也會(huì)帶來(lái)一定的信息損失，泛化損失率是本文提出的綜合度量算法產(chǎn)生的信息損失的評(píng)價(jià)函數(shù).圖5 給出了相同情況下三種算法的泛化損失率.由圖可見，在匿名上限Uk固定時(shí)，雖然(Uk，Lk)-分類匿名的損失率高于直接降低匿名要求的(Lk+1)-匿名模型，但低于初始的Uk-匿名模型，達(dá)到了在不改變匿名要求的同時(shí)實(shí)現(xiàn)更低的信息損失的目的，體現(xiàn)了所提算法的有效性.其次，隨著匿名下限Lk的降低，損失率降低，這和4.2 中實(shí)驗(yàn)結(jié)果的原因一致，都源自模糊區(qū)間的擴(kuò)大.

圖5 匿名上限Uk 不同時(shí)泛化損失率隨匿名下限Lk 的變化Fig.5 The variation of generalization loss rate with Lk when the Uk is different

4.4 算法的總體性能度量為了度量算法的總體性能，綜合分析三種算法在數(shù)據(jù)失真、信息抑制、泛化損失以及算法安全性上的實(shí)驗(yàn)結(jié)果.在匿名上限Uk=12，匿名下限Lk=9，7，5，3，2，1六種情況下，對(duì)三種匿名算法的實(shí)驗(yàn)數(shù)據(jù)進(jìn)行對(duì)比.實(shí)驗(yàn)結(jié)果如圖6 所示.由圖可見，(Uk，Lk)-分類匿名模型的信息抑制率和泛化損失率低于初始的Uk-匿名，數(shù)據(jù)可用性得到了明顯的提高；其次，與以降低安全性為代價(jià)的(Lk+1)-匿名算法相比，(Uk，Lk)-分類匿名模型不會(huì)增加隱私泄露風(fēng)險(xiǎn)，更能保障信息安全.總體上，所提算法可以在不改變隱私保護(hù)度的同時(shí)最大程度地提高數(shù)據(jù)的可用性，優(yōu)于初始的Uk-匿名以及以降低安全性為代價(jià)的(Lk+1)-匿名.

圖6 匿名上限Uk 固定時(shí)，數(shù)據(jù)失真率、信息抑制率、泛化損失率以及隱私泄露風(fēng)險(xiǎn)隨匿名下限Lk 的變化Fig.6 Data distortion rate，information suppression rate，generalization loss rate and risk of privacy leakage with Lk when Uk is fixed

但從圖6 也不難發(fā)現(xiàn)，隨著匿名下限Lk的降低，模糊區(qū)間增加，(Uk，Lk)-分類匿名模型產(chǎn)生的數(shù)據(jù)失真率大幅增加，過(guò)多的噪聲添加可能嚴(yán)重影響了信息的真實(shí)性.因此，設(shè)置合適的匿名下限很有必要.在實(shí)際應(yīng)用中，可以通過(guò)設(shè)置閾值來(lái)決定是否采用(Uk，Lk)-分類匿名算法，數(shù)據(jù)失真率超過(guò)一定的閾值則不推薦使用該算法.

4.5 算法顯著度分析為了進(jìn)一步檢驗(yàn)提出的方法與其他選擇算法的性能差異，以泛化損失率為例進(jìn)行統(tǒng)計(jì)顯著性分析.由于三種算法之間具有相關(guān)關(guān)系，因此使用了Friedman 檢驗(yàn)［27］.假設(shè)三種算法性能相同，計(jì)算每種算法在圖6 的六種評(píng)估環(huán)境下的平均秩.構(gòu)建統(tǒng)計(jì)變量如下：

其中，N和k分別是評(píng)價(jià)環(huán)境總數(shù)和算法個(gè)數(shù)，ri為第i種方法在N種評(píng)估環(huán)境下的分類精度的平均秩.

構(gòu)造一個(gè)隨機(jī)變量如下：

其中，隨機(jī)變量τF服從自由度為k-1 和(k-1)(N-1)的F分布.

選擇Uk-匿名、(Uk，Lk)-分類匿名以及(Lk+1)-匿名三種匿名算法，評(píng)價(jià)環(huán)境為匿名上限Uk=12，匿名下限Lk=9，7，5，3，2，1.圖7 是Friedman 雙向按秩方差的分析結(jié)果，在顯著性水平α=0.05 時(shí)，=12，自由度為2，漸進(jìn)顯著性為0.002.查閱相關(guān)資料，大于對(duì)應(yīng)的Friedman臨界值，說(shuō)明可以拒絕檢驗(yàn)的原假設(shè)，即所提算法和對(duì)比的兩種算法性能是有差別的.

圖7 Friedman 雙向按秩方差分析Fig.7 Friedman two-way analysis of variance by rank

為了進(jìn)一步比較算法的優(yōu)劣，采用Nemenyi測(cè)試作為后續(xù)檢驗(yàn)，Nemenyi 檢驗(yàn)的臨界值定義如下［27］：

當(dāng)k=3 時(shí)，q0.05=2.344，根據(jù)式（9）計(jì)算得CD=1.353.因此，所提的三種算法中(Uk，Lk)-匿名算法和其他兩種算法的平均秩之差都小于臨界閾值CD，說(shuō)明(Uk，Lk)-匿名算法和其他兩種算法的性能沒有顯著差別。

根據(jù)不同算法的結(jié)果排序，進(jìn)一步給出了Friedman 檢驗(yàn)圖，如圖8 所示，其中A1，A2，A3 分別代表Uk-匿名、(Uk，Lk)-分類匿名以及(Lk+1)-匿名三種匿名算法.

圖8 Friedman 檢驗(yàn)圖Fig.8 Friedman test graph

由圖8 可見，所提算法（A2）和對(duì)比的兩種算法都有交疊，說(shuō)明它和兩種對(duì)比算法沒有顯著差別，但其平均性能優(yōu)于傳統(tǒng)的Uk-匿名算法（A1），原因是所提算法處理了模糊數(shù)據(jù)，提高了數(shù)據(jù)利用率，證明所提算法是對(duì)傳統(tǒng)的Uk-匿名算法的改進(jìn).(Lk+1)-匿名算法（A3）的平均性能雖然最好，但通過(guò)實(shí)驗(yàn)分析可知，這是以降低安全性為代價(jià)的.綜上，所提算法可以在不改變隱私保護(hù)度的同時(shí)提高算法性能，優(yōu)于Uk-匿名和以降低安全性為代價(jià)的(Lk+1)-匿名算法.

5 結(jié)論

數(shù)據(jù)匿名是一種重要的隱私保護(hù)方案，現(xiàn)有的匿名算法大多采用二支決策的方式，對(duì)數(shù)據(jù)進(jìn)行嚴(yán)格的二分類后再進(jìn)行匿名處理.為了考慮實(shí)際決策中可能出現(xiàn)的模糊數(shù)據(jù)，將三支決策的思想引入匿名過(guò)程，以經(jīng)典的k-匿名為例，提出一種新型的三支分類匿名模型，即(Uk，Lk)-分類匿名模型.其通過(guò)分類匿名的方式篩選出模糊數(shù)據(jù)，然后對(duì)這部分?jǐn)?shù)據(jù)進(jìn)行再處理，使其滿足原來(lái)的安全需求，從而提高匿名效率.本文采用添加噪聲的方式來(lái)處理模糊數(shù)據(jù)，實(shí)驗(yàn)結(jié)果表明所提模型優(yōu)于傳統(tǒng)的二分類k-匿名模型，可以在保證隱私性的同時(shí)，最大限度地提高數(shù)據(jù)可用性，在實(shí)際應(yīng)用場(chǎng)景中更靈活.其次，為了應(yīng)對(duì)模糊數(shù)據(jù)的定義和在不同的應(yīng)用場(chǎng)景下不同的處理需求，提出的新型匿名框架可以根據(jù)實(shí)際應(yīng)用環(huán)境靈活調(diào)整算法，這也體現(xiàn)了所提模型的可擴(kuò)展性.未來(lái)將繼續(xù)探索這一點(diǎn)，以實(shí)現(xiàn)更好的隱私保護(hù)方案.