面向微聚集技術的k匿名數據質量評估模型

摘 要:針對基于微聚集技術的匿名數據，提出了一個質量評估模型，該模型從匿名數據的可用性、安全性以及兩者的權衡三個角度來評估匿名數據的綜合質量。實驗結果表明，所提出的模型可以有效地評估基于微聚集的匿名數據的質量。

關鍵詞:微聚集; 數據可用性; 信息損失量; 泄密風險; k匿名

中圖分類號:TP309.2文獻標志碼:A

文章編號:1001-3695(2010)06-2344-04

doi:10.3969/j.issn.1001-3695.2010.06.100

Evaluation model for quality of kanonymity dataoriented to microaggregation

CHEN Jian-ming， HAN Jian-min

(College of Mathematics Physics Information Engineering， Zhejiang Normal University， Jinhua Zhejiang 321004， China)

Abstract:This paper proposed an evaluation model for kanonymity data from microaggregation， which could evaluate the quality of anonymity data from the aspects of data utility， data security and the tradeoff between data utility and data security. Experiments show that the proposed model can evaluate anonymity data based on microaggregation effectively.

Key words:microaggregation; data utility; information loss; disclosure risk(DR); kanonymity

k匿名模型是保護隱私信息的一種重要方法，由于其簡單有效，近年來受到了廣泛的關注。k匿名模型最初由Samarati等人[1]于1998年提出，它要求發布的數據中存在一定數量(至少為k)在準標志符上不可區分的記錄，使攻擊者不能判別出隱私信息所屬的具體個體。數據的k匿名化在一定程度上保護了個人的隱私信息，但同時也降低了數據的可用性。因此，k匿名模型的研究工作主要集中在保護隱私信息的同時，最大程度地保留數據的可用性。

泛化/隱匿[2，3]是實現數據k匿名化的傳統技術，但它在處理數值型數據時存在效率低、信息損失大等缺陷。為此，微聚集[4，5]技術被應用到微數據的k匿名化上，其基本思想是:通過某種啟發式方法將數據集劃分為若干個類，要求每個類至少包含k個元組，類內數據最大程度地相似，類間數據最大程度地不同，然后用類質心來代替類內所有元組，實現數據集的k匿名化。微聚集算法簡單有效，對連續型數據能保留更多的語義信息，因此得到了廣泛的研究。

隨著不同微聚集算法的不斷提出，k匿名數據的質量評估顯得愈發重要。k匿名數據的質量評估指標有兩個，即數據安全性和數據可用性。安全性評估，也稱泄密風險評估，用于評價匿名數據對個體隱私信息的保護程度，一般采用匿名表與原數據表同一記錄的關聯程度來度量。可用性評估，用于評價匿名數據保持原始數據特征的程度，一般采用信息損失量來度量。目前，k匿名數據質量評估的研究雖已有了一些成果，但還不完善。Truta等人[6]提出三種基于倒位和改變因子的泄密風險評估模型。Lebanon等人[7]以統計決策理論為基礎，定義了泄密風險函數，并構建了泄密風險評估框架。以上工作只研究了匿名數據的安全性，沒有考慮匿名數據的可用性。為此，本文提出了一種面向微聚集技術的k匿名數據質量評估模型(evaluation model for kanonymized data oriented to microaggregation，EM4ADOM)。

1 面向微聚集技術的k匿名數據質量評估模型

首先給出本文用到的幾個術語的定義[4]。

定義1k匿名。給定數據表T(A1，A2，…，An)，QI是T的準標志符，T[QI]為T在QI上的投影(可重復)，當且僅當T[QI]中每組值至少出現k次，則稱T滿足k匿名。

定義2 k劃分。給定數據表T(A1，A2，…，An)，QI是T的準標志符，QI含p個屬性，表中的元組X=(x1，…，xp)可視為p維空間中的p維向量點。將表T基于QI劃分為g個類，ni為第i類的元組數，要求對于i，ni≥k，且n=Σgi=1ni，則稱該劃分為數據表T基于QI的k劃分。

定義3 聚集。給定數據表T(A1，A2，…，An)，QI是T的準標志符，基于QI的一個k劃分將T劃分為g個類，設Ci為第i類的類質心，對于所有i(i=1，…，g)，用Ci取代第i類中所有元素的操作稱為聚集。

實現k匿名的微聚集算法大體可以分為兩個步驟:首先，對數據表T進行k劃分，生成由g個類組成的數據表;然后，對類進行聚集操作，得到匿名數據表T′。不同的k劃分會產生不同質量的匿名數據。因此，微聚集算法的研究焦點是:在保護個人隱私的前提下，如何最大化匿名數據的可用性。

匿名數據的安全性和可用性是兩個相互對立的指標，加強數據的安全性通常會加大信息損失量，降低數據可用性。因此，匿名數據的質量評估不應該只片面強調某一方面，而要考慮兩個指標的綜合性能。EM4ADOM模型從匿名數據的可用性、安全性以及兩者的權衡三個角度來評估匿名數據的質量。評估框架如圖1所示。該模型采用同質性差異法和統計量差異法來度量連續型數據的可用性;利用直接比較法和信息熵比較法來度量分類型數據的可用性;利用基于距離的記錄鏈接法和區間泄密法來度量匿名數據的安全性;利用數據可用性和安全性的加權平均法和UR圖法來度量匿名數據的綜合質量。

2 可用性評估模型

可用性指標反映了匿名數據保持原始數據統計特征的程度。在EM4ADOM中，連續型數據采用同質性差異法和統計量差異法來度量，分類型數據采用直接比較法和信息熵比較法來度量。

2.1 連續型數據的信息損失量度量方法

2.1.1 同質性差異法

連續型數據常采用歐氏距離來度量向量間的差異:

d(X，Y)=(∑pi=1(Xi-Yi)2)12(1)

其中:Xi、Yi分別表示向量X、Y第i維的屬性值;p為X、Y的維數。

設Gi為k劃分產生的任一等價類，則Gi的類內同質性GSE定義為式(2)。

GSE(Gi)=∑nij=1d(Xij，Xi)(2)

其中:ni表示Gi中的元組個數，ni≥k;Xij表示Gi中的第j條元組;Xi表示Gi的類質心，即Xi=1ni∑nij=1Xij。GSE越小，類內數據的同質性越強。

匿名數據的同質性測度SSE定義為式(3)。

SSE=∑gi=1GSE(Gi)=∑gi=1∑nij=1d(Xij，Xi)(3)

其中:g為等價類的個數，n=∑gi=1ni。

原始數據集的整體同質性SST定義為式(4)。

SST=∑gi=1∑nij=1d(Xij，X)(4)

其中:X為整個數據表T的平均向量，即X=1n∑gi=1∑nij=1Xij。

對給定的數據集T而言，SST固定不變，但不同的k劃分，會導致不同的SSE。類內同質性越大，SSE就越小，信息損失量也就越小，因此連續型的數據信息損失量IL可用式(5)度量。

ILh=SSE/SST(5)

ILh從原始數據和匿名數據的整體特征差異來度量匿名數據的信息損失程度。ILh越小，匿名數據可用性越強。

2.1.2 統計量差異法

同質性差異法從宏觀上反映了數據匿名化的信息損失量，而統計量差異法則是從微觀上度量信息損失量，即以原始記錄和匿名記錄之間或記錄的統計量之間的差異來度量信息損失量。統計量差異法的評估模型較多，大體上可以分為三類，即均方誤差MSE、絕對平均誤差MAE和平均偏差MV，它們從不同角度反映了數據匿名化前后的變化程度。EM4ADOM對上述統計量的評估結果進行加權平均，以獲得較全面的信息損失量。為描述方便，引入以下符號。

設原始數據表T含p個屬性(Z1，Z2，…，Zp)，n個元組(I1，I2，…，In)，T′為T的匿名表，T′含P′個屬性、n′個元組，X、X′， V、V′，R、R′分別為T、T′的數據矩陣、協方差矩陣和相關系數矩陣，xij、xij′分別為數據矩陣X、X′中的元素值，vij、vij′分別為協方差矩陣V、V′中的元素值，rij、rij′分別為相關系數矩陣R、R′中的元素值，S、S′為協方差矩陣V、V′的主對角線元素(即方差)。IL1為X-X′的平均偏差MV，描述了原始表與匿名表對應記錄之間的差異，見式(6)。IL2為X-X′的平均偏差MV和S-S′的平均偏差MV的加權平均，描述了原始表與匿名表單變量統計的差異，見式(7)。IL3為V-V′的平均偏差MV和R-R′的絕對平均誤差MAE的加權平均，描述了原始表與匿名表統計的差異，見式(8)。

IL1=1pn∑pj=1∑ni=1|xij-xij′|2Sj(6)

IL2=(1p∑pj=1|xj-xj′||xj|+1p∑pj=1|vjj-vjj′||vjj|)/2(7)

IL3=(1p(p+1)/2∑pj=1Σ1≤i≤j|vij-vij′||vij|+1p(p-1)/2∑pj=1∑1≤i≤j|rij-rij′|)/2(8)

EM4ADOM中，基于統計量差異法的信息損失量是以上三個統計量的加權平均，見式(9)。

ILs=λ1#8226;IL1+λ2#8226;IL2+λ3#8226;IL3(9)

其中:λ1、λ2、λ3為比例系數，且λ1+λ2+λ3=1。通常λ1、λ2、λ3可分別取值1/3。

匿名表的綜合信息損失量可以用ILh和ILs的平均值來度量，見式(10)。

IL=(ILh+ILs)/2(10)

2.2 分類型數據的信息損失量度量方法 

2.2.1 直接比較法(direct comparison， DC)

直接比較法采用匿名化前后數據記錄之間的距離和來度量信息損失量。設T′為T的匿名表，t、t′分別為T、T′中的記錄，ci、ci′分別為t、t′中的第i個屬性，即t∈T，t′∈T′，c∈t，c′∈t′，n、p分別為T、T′中元組數和屬性數，則信息損失量定義為式(11)。標稱型數據和序數型數據的距離定義分別見式(12)(13)。

ZIL=∑nj=1d(tj，tj′)(11)

其中:d(t，t′)=∑pi=1d(ci，c′i)。

d(ci，ci′)=0 if(ci=ci′)1 if(ci≠ci′)(12)

其中:ci為標稱型數據。

d(ci，ci′)=|{ci″|min(ci，ci′)≤ci″≤max(ci，ci′)}||D(i)|(13)

其中:ci為序數型數據，|D(i)|為屬性i的取值個數。

2.2.2 信息熵比較法(entropy comparison， EC)

信息熵表示數據的平均信息容量，熵值越小，子集劃分的純度越高，故匿名化后的信息熵值要大于匿名化之前的信息熵。信息熵比較法是通過比較匿名化前后數據集信息熵的變化程度來度量信息損失量。

設數據表T含n個記錄，T′為T的匿名表，T基于屬性i可劃分為L個等價類Ci(i=1，…，L)，ni是Ci中的樣本數。標稱型數據第j個屬性的信息熵定義為式(14)，序數型數據第j個屬性的信息熵定義為式(15)。

Hj=-∑Li=1pi log2 pi(14)

Hj=-∑L-1i=1[pi log2 pi+(1-pi)log2 (1-pi)]/(L-1)(15)

其中:pi為元組屬于等價類Ci的概率，即pi =ni/n。

若數據表由m個屬性組成，則整個數據表的信息熵定義為式(16)。

H=∑mj=1Hj(16)

基于以上定義，匿名表的信息損失量可定義為式(17)。

ILR=|original entropy-new entropy|original entropy×100(17)

3 安全性評估模型

數據安全性指標，也稱泄密風險指標，用于評估匿名表對敏感信息的保護程度，泄密風險可以采用匿名表與原數據表同一記錄之間的關聯程度來度量。若攻擊者根據匿名表中的記錄以較大概率推導出原數據表中的記錄，即匿名表與原數據表同一記錄的關聯程度較強，則該匿名表是不安全的。數據安全性度量方法主要有記錄鏈接和區間泄密方法。記錄鏈接方法可以評估連續型數據，也可以評估分類型數據，包括基于概率和基于距離的記錄鏈接方法。區間泄密方法只適合于評估連續型數據，它包括基于分級和基于標準偏差的區間泄密方法。

EM4ADOM采用基于距離的記錄鏈接方法和基于分級的區間泄密方法來度量匿名數據的安全性。

3.1 基于距離的記錄鏈接方法

定義4 鏈接成功。給定匿名表中的任一記錄R，計算R到原始表所有記錄的距離，得到距離R最近的記錄集DS1和次最近記錄集DS2，若DS1(或DS2)中存在R的原始記錄，則稱記錄R鏈接成功。

基于距離的記錄鏈接度量方法(DLD)采用匿名表中記錄的鏈接成功率度量泄密風險。設linked_record_ num為匿名表中鏈接成功的記錄數，total_record_num為匿名表中總的記錄數，則基于距離的記錄鏈接的泄密風險的度量方法DLD見式(18)，該方法適用于所有數據類型。

DLD=linked_record_numtotal_record_num(18)

計算linked_record_num時，需要計算R到原始表所有記錄的距離，不同類型的數據距離度量方法不同，連續型數據可采用歐氏距離，分類型數據可采用式(12)(13)計算。

3.2 基于分級的區間泄密方法

基于分級的區間泄密方法需要對給定的匿名表記錄建立分級區間，方法是:將匿名表所有屬性按值大小賦予不同的級別，相同屬性值則按先后順序依次賦予不同級別，如值{37， 37， 39， 40， 38}對應級別為{1， 2， 4， 5， 3}，并以匿名值的對應級別R為中心擴展兩端來定義分級區間，規定區間中的不同級數不超過整個匿名表記錄數的p%，然后求出分級區間對應的值區間。P取值可設為1~10。

定義5 區間匹配成功。設T′是T的匿名表，n、s分別為T、T′中元組數和屬性數，t、t′分別為T、T′中的記錄。按值的大小順序對匿名表的屬性值賦予不同的級別R。Rit′為匿名表的第t′條記錄中的第i個屬性值Vit′對應的級別(i=1，2，…，s)，f(Rit′)表示返回級別Rit′的對應值，p為區間的大小。若i(i=1，…，s)，有下式成立:

Vti∈[f(Rt′i-int(p%*n/2))， f(Rt′i+int(p%*n/2))]即記錄t中的所有屬性值均落在以t的匿名值為中心建立的分級區間中，則稱記錄t區間匹配成功。

基于分級的區間泄密方法采用原數據表中區間匹配成功的記錄所占的比率作為泄密風險的度量。設in_interval為原數據表中區間匹配成功的記錄個數，n為原數據表的記錄總數，則分級的區間泄密ID的度量方法見式(19)。

ID =in_interval/n(19)

匿名數據的安全性DR可采用基于距離的記錄鏈接評估結果和基于分級的區間泄密評估結果的加權平均來度量，見式(20)。

DR=τ1#8226;DLD+τ2#8226;ID(20)

其中:τ1，τ2為比例系數，且τ1+τ2=1。通常τ1，τ2可分別取值0.5。

4 安全性和可用性權衡評估

匿名數據的安全性和可用性是兩個對立的指標。安全性加強，會增加信息損失量，降低數據可用性，反之亦然。因此，需要研究兩者間的權衡技術，通過算法選擇和參數設置得到最優的匿名數據。EM4ADOM采用的權衡方法有如下兩種:

a)加權平均法。它是采用信息損失量和泄密風險值的加權平均來度量匿名數據的綜合質量。設T為數據表，T′為T的匿名表，則匿名數據的信息損失量和泄密風險的加權平均可采用式(21)計算。

score(T，T′)=γ1#8226;IL(T，T′)+γ2#8226;DR(T，T′)(21)

其中:γ1，γ2為比例系數，且γ1+γ2=1。通常γ1，γ2可分別取值0.5。

b)RU圖法。它由一組(R， U)二維值構成，R(disclosure risk)為泄密風險，U(data utility)為數據的可用性。根據RU圖可直觀地評估匿名數據的綜合質量。

5 實驗結果及分析

5.1 連續型屬性的實驗比較

實驗運行環境為:Intel Pentium 4 3.1 GHz CPU，1.5 GB內存， Windows XP專業版操作系統。連續型數據采用Tarragona、Census和EIA，這三種微數據集現已被很多文獻作為微聚集算法的測試數據。表1為各個數據集的結構描述。

表1 實驗數據描述

datasetrecord numberdimension

Tarragona83413

Census1 08013

EIA4 09211

實驗采用性能較好的多變量定長微聚集MDAV算法對數據表匿名化，匿名數據的評估結果如表2所示。其中:τ1=0.5，τ2=0.5，λ1=0.5，λ2=0，λ3=0.5。

從表2中可以看出，隨著k值的增加，三個數據集的信息損失量均變大，而泄密風險均變小。以表2的數據為基礎得到三個數據集的RU圖，如圖2所示。其中，信息損失量取表2中的IL列，泄密風險取表2中的DR列。從圖2(a)可以看出，k由3變到6的過程中，信息損失量會以較小的斜率增加，當k大于6后，信息損失量會以較大的斜率增加。因此，當k為5或6時，匿名表的信息損失量和泄密風險的權衡較優。同理，從圖2(b)可知，當k為5或6時，匿名表的信息損失量和泄密風險的權衡較優。從圖2(c)可知，當k為6或7時，匿名表的信息損失量和泄密風險的權衡較優。

5.2 分類型屬性的實驗比較

實驗中的分類型數據采用源于UCIrvine機器學習倉庫的Adult數據庫，該數據是由美國人口普查數據組成，它已被很多文獻作為匿名化分類型數據的實驗數據[2，3]。從中隨機選取了1 000個元組作為測試數據，本文采用的數據庫結構見表3，準標志符設為7個，敏感屬性1個。

仍舊采用MDAV算法，對數據表匿名化，利用EM4ADOM評估匿名數據，結果如表4所示。其中ZIL、ILR、DLD分別為直接比較法、信息熵比較法、基于距離的記錄鏈接法的評估結果。圖3(a)為ZIL與DLD的RU圖，圖3(b)為ILR與DLD的RU圖。從圖3(a)可知，當k為5或6時，匿名表的信息損失量和泄密風險的權衡較優;從圖3(b)可知，當k為5或7時，匿名表的信息損失量和泄密風險的權衡較優。

表3 Adult數據集描述

attributetypedistinct valuesheightattributetypedistinct valuesheight

1agenumeric7455marital statuscategorical73

2workclasscategorical836racecategorical53

3educationcategorical1647gendercategorical22

4countrycategorical4138occupationsensitive143

表4 Adult匿名表的評估結果

k直接比較法ZIL信息熵比較法ILR記錄鏈接DLD

323.100 00.463 10.992 0

433.700 02.055 50.962 0

541.500 01.992 60.941 0

647.800 05.141 00.914 0

750.700 03.319 40.938 0

856.800 06.028 40.909 0

961.200 05.139 60.915 0

1064.200 08.384 50.885 0

6 結束語

本文研究了面向微聚集的k匿名數據質量評估問題，建立了EM4ADOM評估模型，該模型從數據的可用性、安全性以及可用性和安全性的權衡三個方面綜合評估了匿名數據的質量。實驗結果表明，該模型能夠較全面、有效地評估基于微聚集技術的k匿名數據的質量。

下一步的工作是基于EM4ADOM評估模型，研究各種k匿名化算法在處理不同的統計特征數據時的性能，分析出數據統計特征、算法與匿名數據質量的關系，以便在匿名化微數據時，能夠根據數據的統計特征選擇合適的微聚集算法。

參考文獻:

[1]SAMARATI P， SWEENEY L. Generalizing data to provide anonymity when disclosing information (abstract)[C]//Proc of the 17th ACMSIGMODSIGACTSIGART Symposium on the Principles of Database Systems.1998.

[2]SWEENEY L. Achieving kanonymity privacy protection using generalization and suppression[J]. International Journal on Uncertainty， Fuzziness and Knowledgebased Systems， 2002， 10(5): 571-588.

[3]KeFEVER K， DeWITT D J， RMAKRISHNAN R. Incognito: efficient fulldomain kanonymity[C]// Proc of ACM SIGMOD. New York: ACM Press， 2005.

[4]DOMINGOFERRER J， TORRA V. Ordinal， continuous and heterogeneous kanonymity through microaggregation [J]. Journal of Data Mining and Knowledge Discovery， 2005， 11(2): 195-202.

[5]韓建民， 岑婷婷， 虞慧群. 數據表k匿名化的微聚集算法研究[J]. 電子學報， 2008， 36(10): 2021-2029.

[6]TRUTA T M， FOTOUHI F， BARTHJONES D. Assessing global disclosure risk in masked microdata[C]//Proc of Workshop on Privacy in the Electronic Society. Washington DC: ACM Press， 2004.

[7]LEBANON G， SCANNAPIECO M， FOUAD M R， et al. Beyond kanonymity: a decision theoretic framework for assessing privacy risk[C]//Proc of Privacy in Statistical Databases. Rome: Springer， 2006.