多維數值型敏感屬性數據的個性化隱私保護方法

張梅舒，徐雅斌，3*

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

0 引言

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

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

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

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

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

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

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

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

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

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

本文工作如下：

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

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

1 數據預處理

1.1 數據集聚類

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

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

由于準標識符屬性既有數值型的又有分類型的，聚類時應作不同的考慮。對于數值類型的屬性，數值差即為距離；對于分類型的屬性，參考文獻［12］提出的概化樹，為每個屬性構建概化樹，通過概化樹計算非數值類型屬性的距離。例如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

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

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

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

1.2 數值型敏感屬性值聚類

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

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

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

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

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

2 加權多維桶構建

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

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

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

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

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

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

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

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

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

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

對于表2 中的數據，假設用戶認為敏感屬性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 所示，其中，括號內的數字即為每個桶的加權選擇度。

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

3 數據分組及匿名化處理

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

該方法存在以下問題：

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

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

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

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

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

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

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

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

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

4）分組時優先選擇加權選擇度大的桶中的數據，將數據分成滿足l-多樣性的分組；

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

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

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

表4 待發布數據Tab.4 Data to be released

4 實驗與分析

4.1 實驗環境及數據集

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

實驗的硬件環境是Intel Core i7-4790 CPU@3.60 GHz，8.0 GB RAM，Windows 7 專業版操作系統，JetBrains PyCharm 2017.3 x64，算法的實現語言為Python3。

表5 實驗數據集的屬性描述Tab.5 Attribute description of experimental dataset

4.2 評價標準

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

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

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

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

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

定義3分組信息損失度。

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

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

2）隱匿率。

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

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

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

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

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

4.3 實驗結果及分析

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

1）信息損失度分析。對于不同的l值，各個方法的信息損失度如圖2 所示。由圖2 可以看出，隨著l 值的不斷增大，3 個方法的信息損失度不斷增加；在l 值相同的情況下，本文方法的信息損失度比MNSACM 和WMNSAPM 的更低，對應的數據可用性更高。分析原因如下：隨著l 的增大，每個分組中的數據條數增加，分組中準標識符屬性的范圍增大，因而信息損失度增加。由于在分組之前，本文方法先根據用戶需要的準標識符屬性將數據集進行了聚類，避免了不必要的信息損失，因此，在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 值的增大，在分組過程中得到的分組數越少，被隱匿的數據越多，因而隱匿率越高。由于MNSACM 在進行初次分組后，沒有對未分組數據進行二次分組，直接將其進行隱匿，所以，隱匿率更高。

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

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

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

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

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

5 結語

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

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