張梅舒，徐雅斌，3*

（1.網絡文化與數(shù)字傳播北京市重點實驗室（北京信息科技大學），北京100101；2.北京信息科技大學計算機學院，北京100101；3.北京材料基因工程高精尖創(chuàng)新中心（北京信息科技大學），北京100101）

0 引言

隨著信息技術的飛速發(fā)展，各個行業(yè)和領域都積累了大量的數(shù)據(jù)，而且數(shù)據(jù)規(guī)模正以驚人的速度增長［1］。大數(shù)據(jù)蘊含著巨大的商業(yè)價值，為了更好地利用大數(shù)據(jù)，數(shù)據(jù)共享勢在必行。而在共享的海量數(shù)據(jù)中，往往涉及到個人信息或者敏感數(shù)據(jù)［2］。如果直接進行數(shù)據(jù)共享就可能會泄露個人隱私信息，因此，為了保證個人敏感信息的安全，在發(fā)布數(shù)據(jù)的同時應進行隱私保護［3］。

現(xiàn)有的數(shù)據(jù)隱私保護方法主要針對單一敏感屬性的數(shù)據(jù)［4-6］。但是，在很多現(xiàn)實應用中，發(fā)布的數(shù)據(jù)往往涉及到多個敏感屬性。對多敏感屬性數(shù)據(jù)的隱私保護的研究主要是針對多維分類型敏感屬性和單維數(shù)值型敏感屬性數(shù)據(jù)，對多維數(shù)值型敏感屬性數(shù)據(jù)的隱私保護研究少有涉獵。

事實上，多維數(shù)值型敏感屬性數(shù)據(jù)更具一般性，對其進行隱私保護的研究不僅可以有效解決多維數(shù)值型敏感屬性數(shù)據(jù)發(fā)布時的隱私泄露問題，還可以擴展數(shù)據(jù)的隱私保護范圍，促進隱私保護研究的發(fā)展和大數(shù)據(jù)安全技術的進步。

楊曉春等［7］首次對多敏感屬性數(shù)據(jù)發(fā)布問題進行了詳細研究，繼承了有損連接的思想，提出了針對多敏感屬性數(shù)據(jù)進行隱私保護的多維桶分組（Multi-Sensitive Bucketization，MSB）技術，并提出了3 種不同的分組策略。金華等［8］改進了分組算法，提出了l-覆蓋性聚類分組方法。楊靜等［9］給出了一種基于值域等級劃分的個性化定制方案，并提出了一種最小選擇度優(yōu)先的面向多敏感屬性數(shù)據(jù)的l-多樣性算法。

羅方煒等［10］提出一種(l，m)-多樣性模型，該模型要求當同一敏感值的元組從等價類中刪除時，剩余的元組仍滿足獨立敏感屬性的(l-1，m)-多樣性，這樣能夠有效抵制關聯(lián)攻擊，但是仍存在敏感值語義相近問題。Jia 等［11］針對敏感值語義相近問題提出了(l，m，d)-匿名模型，但該模型的數(shù)據(jù)損失較大。劉善成等［12］提出了一種基于敏感度的分組技術——(g，l)-分組方法，不僅解決了多敏感屬性隱私數(shù)據(jù)發(fā)布的問題，同時還可有效抵制相似性攻擊和偏斜攻擊，但該方法的數(shù)據(jù)損失較大。Zhang 等［13］提出了MSA(α，l)算法，使分組后的數(shù)據(jù)滿足l-多樣性和α-最大約束，在一定程度上減少了數(shù)據(jù)損失。

李文［14］考慮了準標識符屬性的數(shù)據(jù)質量和敏感屬性的敏感程度，提出了基于主敏感屬性的排序分組算法，可減少數(shù)據(jù)損失，提高數(shù)據(jù)可用性。

此外，還有一些基于k-匿名的算法。Wu等［15］提出p-覆蓋k-匿名算法，可降低敏感屬性泄露的風險。宋明秋等［16］在k-匿名模型實現(xiàn)的過程中，通過引入屬性近似度概念，提出了一種多屬性泛化的k-匿名算法。王秋月等［17］提出了一種多敏感屬性分級的（αij，k，m）-匿名隱私保護方法。該模型為每個敏感屬性的值進行分級設置，并為每個級別設置一個特定的αij，避免具有相同級別敏感值的記錄被分在同一組中，從而可有效防止語義相似和關聯(lián)攻擊。

針對多維數(shù)值型敏感屬性數(shù)據(jù)發(fā)布的隱私保護，劉騰騰等［18］提出了l-MNSA（l-Multi-Numerical Sensitive Attribute）算法，該算法使分組后的數(shù)據(jù)在每一維數(shù)值型敏感屬性上的分布都比較均勻，能夠防止相似攻擊，但其不適合大數(shù)據(jù)。Liu等［19-20］提出了一種基于聚類和多維桶的數(shù)據(jù)隱私保護方法MNSACM，該方法在分組前將數(shù)值型敏感屬性聚類，可以在一定程度上保護數(shù)值型敏感屬性；但它沒有考慮準標識符的質量，數(shù)據(jù)發(fā)布質量較低。陸洋［21］提出了一種基于聚類和加權多維桶分組的個性化隱私保護方法WMNSAPM。該方法利用加權多維桶的思想，實現(xiàn)了個性化匿名隱私保護的效果；但該方法沒有考慮準標識符的質量，數(shù)據(jù)損失較大，而且需要由用戶自己設置桶的權重，不僅難以實現(xiàn)，而且缺乏合理性。

綜上所述，現(xiàn)有的針對多維數(shù)值型敏感屬性數(shù)據(jù)的隱私保護方法存在以下問題：1）分組時僅考慮敏感屬性的屬性值，未考慮準標識符的范圍，數(shù)據(jù)損失較大；2）提出的個性化隱私保護方法需要由用戶設置桶的權重，對用戶的專業(yè)性要求過高。

針對現(xiàn)有研究中存在的問題，本文提出如下設計方案：在數(shù)據(jù)預處理時，首先根據(jù)準標識符屬性對數(shù)據(jù)集進行聚類，由此將一個數(shù)據(jù)集分成若干個準標識符屬性值接近的子數(shù)據(jù)集，再根據(jù)數(shù)據(jù)的分布情況對數(shù)值型敏感屬性進行聚類；然后，根據(jù)多維桶的容量和敏感屬性的敏感程度計算加權選擇度，并由此構建加權多維桶；在對數(shù)據(jù)分組時，優(yōu)先考慮加權選擇度大的桶中的數(shù)據(jù)，使分組后的數(shù)據(jù)滿足多敏感屬性l-多樣性分布；最后，對分組后的數(shù)據(jù)進行匿名化處理。

本文工作如下：

1）根據(jù)準標識符的相似程度，將數(shù)據(jù)集劃分成若干準標識符屬性值接近的子集，由此可縮小數(shù)據(jù)集中準標識符的取值范圍，有利于減少信息損失；

2）考慮到用戶對于敏感屬性的敏感程度不同，根據(jù)用戶對敏感屬性的敏感程度排序得到敏感屬性的權重，將敏感屬性的權重和多維桶的桶容量作為參數(shù)，提出一種加權選擇度計算方法，有助于對數(shù)據(jù)進行個性化的隱私保護。

1 數(shù)據(jù)預處理

1.1 數(shù)據(jù)集聚類

研究發(fā)現(xiàn)，數(shù)據(jù)記錄之間往往具有內在關系，尤其是當數(shù)據(jù)量較大時，某些數(shù)據(jù)記錄在某個準標識符上具有相似的取值。為此可以通過聚類將具有較多共同特征的準標識符屬性聚為一類，并由此將數(shù)據(jù)集分為若干子集，以減小數(shù)據(jù)的隱匿程度以及準標識符的泛化率，提高數(shù)據(jù)的可用性。

本文采用簡單實用的k-means 算法根據(jù)準標識符屬性值對數(shù)據(jù)集進行聚類。

由于準標識符屬性既有數(shù)值型的又有分類型的，聚類時應作不同的考慮。對于數(shù)值類型的屬性，數(shù)值差即為距離；對于分類型的屬性，參考文獻［12］提出的概化樹，為每個屬性構建概化樹，通過概化樹計算非數(shù)值類型屬性的距離。例如workclass 屬性的值域為｛private，federal-gov，local-gov，stategov，sef-emp-inc，sef-emp-not-inc，withou-pay，never-worked｝，構建的概化樹如圖1所示。

圖1 workclass的概化樹Fig.1 Generalized tree of workclass

概化樹的每層都有個權值。例如，該泛化樹總共四層，規(guī)定從上到下每層的權值分別為0、1、2、3。兩個分類型數(shù)據(jù)之間的距離等于該兩個節(jié)點到最小公共父節(jié)點的層次距離之和。例如，求federal-gov 和sef-emp-inc 之間的距離，需要先找到最小公共父節(jié)點work，由此兩個值的距離可計算如下：

d（federal-gov，sef-emp-inc）=(3-1)+(3-1)=4

以一個精簡后的人口普查數(shù)據(jù)集為例，其準標識符屬性有age 和workclass，數(shù)值型敏感屬性有profit 和hours-perweek。假定按照age 進行聚類，根據(jù)年齡段將數(shù)據(jù)集聚類，結果形成4個數(shù)據(jù)子集。其中的一個數(shù)據(jù)子集如表1所示。

1.2 數(shù)值型敏感屬性值聚類

為了避免敏感屬性值差異較小的兩個值分別作為獨立的桶，造成信息泄露，有必要對需要進行隱私保護的多個數(shù)值型敏感屬性值分別進行聚類。

假設一個數(shù)據(jù)表中有n 條數(shù)據(jù)記錄，該數(shù)據(jù)表包含m 維數(shù)值型敏感屬性。將每一維數(shù)值型敏感屬性值聚成多個簇，記作{Si1，Si2，…，Sij}(1 ≤i ≤m)。每個簇的屬性值個數(shù)不一定相同，但所有的簇覆蓋了這一維敏感屬性的所有值。

表1 聚類產生的一個數(shù)據(jù)子集Tab.1 A subset generated by clustering

本文同樣采用k-means 算法對數(shù)據(jù)表1 中的數(shù)值型敏感屬性profit（S1）和hours-per-week（S2）的屬性值分別進行聚類，聚類結果分別為S1和S2：

聚類后使得同一個簇的屬性值相近，不同簇的屬性值差異較大，任意兩個簇之間的交集為空集。

2 加權多維桶構建

構建加權多維桶的步驟如下：

1）構建多維桶。根據(jù)敏感屬性profit（S1）和hours-perweek（S2）的值，對表1 中的數(shù)據(jù)進行映射，得到的多維桶分組如表2 所示。其中：每個單元格代表一個桶，空格說明該桶中不包含數(shù)據(jù)；t1～t9為表1中數(shù)據(jù)的id。

表2 多維桶分組Tab.2 Multi-sensitive bucketization

2）計算每個桶的加權選擇度?；诙嗑S桶的分組算法在進行分組時，一般只考慮桶的容量大小，然而，在實際應用中，如果某些元組中包含更重要的信息，就需要優(yōu)先考慮。為此，本文為每個桶賦予一個加權選擇度，由此構建一個加權多維桶。

對于加權選擇度的計算，一般需要考慮敏感屬性值的敏感程度、桶容量和語義相似度這三個因素。然而，由于數(shù)值型屬性不存在語義相似的問題，并且屬性值的敏感程度也沒有明顯的區(qū)別，為此，本文在計算加權選擇度時，只需要將桶容量和敏感屬性的敏感程度考慮在內即可。

加權選擇度的計算步驟如下：

步驟1 獲取用戶對m 個敏感屬性的敏感程度由大到小的順序排列S1，S2，…，Sm，設定當前維的重要程度為S0，且S0＞S1；

步驟2 利用層次分析法得到m 個敏感屬性的權重分別為W1，W2，…，Wm，當前維的權重為W0；

步驟3 利用式（1）計算加權選擇度：

其中：第i 個敏感屬性的權重為Wi，第i 維敏感屬性值與當前桶屬于同一簇的記錄數(shù)為Ci，桶容量為c。

對于表2 中的數(shù)據(jù)，假設用戶認為敏感屬性profit（S1）比hours-per-week（S2）更重要，即敏感程度S0＞S1＞S2。利用加權選擇度得到權重分別為：W0=0.63，W1=0.26，W2=0.11。利用式（1）得到各個桶的加權選擇度分別為：｛1.26，1.33，2.48，1.59，1.63，1.37，1.26，1｝。

3）給每個桶賦予相應的加權選擇度，從而得到加權多維桶。

將計算得到的加權選擇度賦給多維桶，最終得到的加權多維桶如表3 所示，其中，括號內的數(shù)字即為每個桶的加權選擇度。

表3 加權多維桶分組Tab.3 Weighted multi-sensitive bucketization

3 數(shù)據(jù)分組及匿名化處理

文獻［21］提出的WMNSAPM 方法中：首先將各維數(shù)值型敏感屬性的屬性值進行聚類；然后利用用戶指定的權值構建加權多維桶，并將數(shù)據(jù)映射到加權多維桶中；接著通過基于加權的最大維容量優(yōu)先貪心算法，構成滿足l-多樣性的分組；最后，將各個分組的準標識符進行匿名化處理。

該方法存在以下問題：

1）分組時沒有考慮準標識符屬性的范圍，如果準標識符屬性的范圍過大，在匿名化處理時會過度泛化，導致數(shù)據(jù)損失度較大、可用性較低；

2）加權多維桶的權重需要用戶設置，對用戶的專業(yè)性要求過高，準確性難以把握。

針對文獻［21］方法存在的問題，本文做了如下改進：

1）在分組之前根據(jù)準標識符屬性的范圍將數(shù)據(jù)集聚類，從而分成若干準標識符屬性值接近的子集，然后分別對每個子集進行分組及匿名化處理，由此可縮小數(shù)據(jù)集中準標識符的取值范圍，有利于減少信息損失。

2）在加權多維桶權重的計算時，根據(jù)用戶對于敏感屬性的敏感度的排序，利用層次分析法計算出敏感屬性的權重，然后根據(jù)敏感屬性的權重和多維桶的桶容量來計算出多維桶的權重。

本文方法的具體步驟包括：

1）根據(jù)準標識符屬性的范圍將數(shù)據(jù)集聚類，對得到的各個子集分別進行步驟2）～5）操作；

2）將各維數(shù)值型敏感屬性的屬性值進行聚類；

3）利用本文第2章提出的方法構建加權多維桶；

4）分組時優(yōu)先選擇加權選擇度大的桶中的數(shù)據(jù)，將數(shù)據(jù)分成滿足l-多樣性的分組；

5）將各個分組的準標識符屬性進行匿名化處理。

假設l取值為3，按照本文方法對表1中的數(shù)據(jù)進行分組，得到的結果為：｛｛t1，t2，t5｝，｛t3，t7，t9｝，｛t4，t6，t8｝｝。

最后，將分組后的數(shù)據(jù)進行匿名化處理：數(shù)值型數(shù)據(jù)取最值作為兩個邊界值，泛化為“最小值-最大值”；分類型數(shù)據(jù)將屬性值的最小公共父節(jié)點作為泛化結果，得到的待發(fā)布數(shù)據(jù)如表4所示。

表4 待發(fā)布數(shù)據(jù)Tab.4 Data to be released

4 實驗與分析

4.1 實驗環(huán)境及數(shù)據(jù)集

實驗所需數(shù)據(jù)采用UCI 機器學習中心的標準Adult 數(shù)據(jù)集，共有48 842 條數(shù)據(jù)，去除含有空值數(shù)據(jù)后的可用數(shù)據(jù)為30 162條記錄，選取其中的8個屬性進行實驗。將其中的屬性age、workclass、education、education-num、marital-status、sex 作為準標識符屬性，將屬性profit 和hours-per-week 作為敏感屬性，屬性描述見表5。

實驗的硬件環(huán)境是Intel Core i7-4790 CPU@3.60 GHz，8.0 GB RAM，Windows 7 專業(yè)版操作系統(tǒng)，JetBrains PyCharm 2017.3 x64，算法的實現(xiàn)語言為Python3。

表5 實驗數(shù)據(jù)集的屬性描述Tab.5 Attribute description of experimental dataset

4.2 評價標準

1）信息損失度。數(shù)據(jù)分組后的匿名過程會對數(shù)據(jù)質量造成損失，降低數(shù)據(jù)可用性。數(shù)據(jù)質量的度量，主要針對準標識符被泛化的程度，常用信息損失度進行衡量。信息損失度越小，數(shù)據(jù)可用性越高。由于數(shù)據(jù)集中的準標識符屬性既有數(shù)值型又有分類型，因此信息損失度的計算要考慮兩種類型的屬性。

定義1數(shù)值型屬性的信息損失度（Information Loss of Numerical attribute，ILN）。

設Min和Max分別是一個分組的最小值和最大值，R表示整個數(shù)據(jù)表的值域范圍，則：

定義2分類型屬性的信息損失度（Information Loss of Classified attribute，ILC）。

給每個分類型屬性構建概化樹，p表示概化樹中兩個節(jié)點的最小公共父節(jié)點的高度，h 表示整個概化樹的高度，Wi，j表示概化樹i、j兩個高度之間的權值，則：

定義3分組信息損失度。

設N1，N2，…，NI，C1，C2，…，CJ是一個分組的準標識符屬性，其中Ni(1 ≤i ≤I)表示數(shù)值型數(shù)據(jù)，Cj(1 ≤j ≤J)表示分類型數(shù)據(jù)，則整個分組的信息損失度IL（Information Loss）為各個準標識符屬性的信息損失度之和，即：

假設數(shù)據(jù)表為T，處理后的分組數(shù)為M，則該數(shù)據(jù)表的信息損失度為所有分組的信息損失度之和，即：

2）隱匿率。

定義4隱匿率。隱匿處理的數(shù)據(jù)記錄在數(shù)據(jù)表所有數(shù)據(jù)記錄中所占的比例：

其中：t 表示隱匿的數(shù)據(jù)記錄條數(shù)，|T |表示數(shù)據(jù)表總的數(shù)據(jù)量。隱匿率越小，發(fā)布的數(shù)據(jù)效果越好，理想情況下該值為0。

3）附加信息損失度。初次分組后，為了減少隱匿率，在滿足l-多樣性的前提下，將剩余的數(shù)據(jù)分到已有分組中。這樣，在最終的分組中，某些敏感屬性的值可能重復，即l ＜|G|（G 表示分組的數(shù)據(jù)記錄數(shù)），這就在一定程度上增加了隱私泄露的風險，為此引入附加信息損失度來衡量這種風險。

定義5 附加信息損失度。設G{G1，G2，…Gi，…，Gm}是數(shù)據(jù)表T 上的分組，則附加信息損失度（Additional Information Loss，AIL）如下：

4）運行時間。算法的運行時間反映了算法的執(zhí)行效率，是算法性能評價的一個重要標準。

4.3 實驗結果及分析

在進行分組之前，需要對數(shù)值型敏感屬性進行聚類。本文將profit 和hours-per-week 分別聚類為9 類和7 類。因此，算法中l(wèi)-多樣性的l的取值范圍是2 ≤l ≤7。針對不同的l值，本實驗分別用文獻［19］的MNSACM 和文獻［21］的WMNSAPM以及本文方法在相同的數(shù)據(jù)集上進行隱私保護處理，然后計算各個評價指標的值。

1）信息損失度分析。對于不同的l值，各個方法的信息損失度如圖2 所示。由圖2 可以看出，隨著l 值的不斷增大，3 個方法的信息損失度不斷增加；在l 值相同的情況下，本文方法的信息損失度比MNSACM 和WMNSAPM 的更低，對應的數(shù)據(jù)可用性更高。分析原因如下：隨著l 的增大，每個分組中的數(shù)據(jù)條數(shù)增加，分組中準標識符屬性的范圍增大，因而信息損失度增加。由于在分組之前，本文方法先根據(jù)用戶需要的準標識符屬性將數(shù)據(jù)集進行了聚類，避免了不必要的信息損失，因此，在l值相同的時候，本文方法的信息損失度更低。

圖2 不同算法的信息損失度隨l值的變化Fig.2 Information loss degrees of different algorithms varying with l value

2）隱匿率分析。對于不同的l值，各個算法的隱匿率如圖3所示。由圖3可以看出，3個方法的隱匿率都隨著l值增大而增大，當l 取值不超過4 時，本文方法與WMNSAPM 的隱匿率均較低，具有很好的性能；而當l 取值超過4 時，3 個方法的隱匿率都比較高。分析原因如下：隨著l 值的增大，在分組過程中得到的分組數(shù)越少，被隱匿的數(shù)據(jù)越多，因而隱匿率越高。由于MNSACM 在進行初次分組后，沒有對未分組數(shù)據(jù)進行二次分組，直接將其進行隱匿，所以，隱匿率更高。

圖3 不同算法的隱匿率隨l值的變化Fig.3 Concealment rates of different algorithms varying with l value

3）附加信息損失度分析。由于MNSACM 沒有對分組剩余的數(shù)據(jù)進行二次分組，不存在附加信息損失，因此，對于附加信息損失度的實驗只考慮WMNSAPM 與本文方法。對于不同的l 值，兩個算法的附加信息損失度如圖4 所示。由圖4可以看出，WMNSAPM 的附加信息損失度隨著l的增大而不斷增大；雖然本文方法的附加信息損失度也隨著l 的增大而增大，但之后趨于穩(wěn)定。分析原因如下：隨著l的增大，初次分組得到的分組數(shù)越來越少，即剩余的未分組數(shù)據(jù)越來越多，因此二次分組的數(shù)據(jù)也越來越多，進而附加信息損失度越來越大。

圖4 不同算法的附加信息損失度隨l值的變化Fig.4 Additional information losses of different algorithms varying with l value

4）運行時間分析。對于不同的l值，三個算法的運行時間如圖5 所示。由圖5 可以看出，MNSACM 和本文方法的運行時間在0～10 s，運行時間較短，效率較高。而且隨著l 值的增大，本文方法的優(yōu)勢越來越明顯，而WMNSAPM 的運行時間較長，效率較低。分析原因如下：MNSACM 沒有對未分組數(shù)據(jù)進行二次分組，故運行時間較短；本文方法在分組之前將數(shù)據(jù)進行聚類，然后對每個簇分別進行分組處理，因而每個簇的數(shù)據(jù)相對較少，故運行時間較短。

圖5 不同算法的運行時間隨l值的變化Fig.5 Running times of different algorithms varying with l value

5 結語

本文針對多維數(shù)值型敏感屬性數(shù)據(jù)的隱私保護問題展開研究，在對已有方法進行分析的基礎上，提出了一種個性化隱私保護方法。該方法首先根據(jù)準標識符屬性對數(shù)據(jù)集進行聚類，由此減少了信息損失和隱私泄露風險；在計算多維桶的權重時，考慮到用戶對敏感屬性具有不同的敏感程度，將敏感屬性的敏感程度和多維桶的桶容量作為參數(shù)，得到桶的加權選擇度；在將數(shù)據(jù)分組時，選擇加權選擇度最大的桶中的數(shù)據(jù)，使得分組中的多敏感屬性滿足l-多樣性。

實驗結果表明，相比現(xiàn)有方法，采用本文提出的方法對多維數(shù)值型敏感屬性的數(shù)據(jù)進行隱私保護，具有較低的信息損失度和較短的運行時間，提高了數(shù)據(jù)質量和運行效率。