方 凱，史志才，2，賈媛媛

(1.上海工程技術大學 電子電氣工程學院，上海 201620； 2.上海市信息安全綜合管理技術研究重點實驗室，上海 200240)

隨著移動互聯(lián)網(wǎng)的快速發(fā)展，各種傳感器以及無線終端設備采集了海量的數(shù)據(jù)[1]。為了挖掘大數(shù)據(jù)的潛在價值，享受大數(shù)據(jù)帶來的方便和快捷，需要對數(shù)據(jù)進行發(fā)布[2]。如果待發(fā)布的數(shù)據(jù)不經(jīng)過隱私保護處理被直接發(fā)布，那么攻擊者可能會利用各種途徑竊取用戶的敏感信息，造成用戶的隱私泄露和財產(chǎn)損失[3]。因此，在保護用戶數(shù)據(jù)隱私的同時減少數(shù)據(jù)發(fā)布的信息損失，提高數(shù)據(jù)發(fā)布的質(zhì)量，已成為當前研究的熱點問題[4]。

傳統(tǒng)的數(shù)據(jù)發(fā)布隱私保護模型主要分為k-匿名模型[5]、l-多樣性模型[6]和t-closeness[7]模型。在這些經(jīng)典的隱私保護模型基礎上，許多算法相繼被提出[8-10]。近年來，隨著機器學習在各領域的廣泛應用，將聚類算法引入數(shù)據(jù)發(fā)布隱私保護技術引起了廣泛關注[11-12]。文獻[13]提出了一種基于k-means聚類的隱私保護方法。文獻[14]提出了一種基于多屬性泛化聚類實現(xiàn)k-匿名的算法。文獻[15]提出了一種針對混合屬性的聚類算法?，F(xiàn)有的利用聚類算法實現(xiàn)k-匿名模型的方法未考慮到離群點噪聲[16]對聚類結(jié)果的影響，且采用傳統(tǒng)分類樹[1]進行距離度量和屬性泛化會造成嚴重的信息損失。此外，利用k-means均值聚類實現(xiàn)k-匿名的算法雖然復雜度低、效率較高，但是由于其初始聚類中心點的選取具有不確定性，因此易導致算法陷入局部最優(yōu)，降低了算法的穩(wěn)定性。

在分析了現(xiàn)有的數(shù)據(jù)發(fā)布隱私保護技術的基礎上，本文提出了一種混合聚類k-匿名數(shù)據(jù)發(fā)布算法。該算法通過數(shù)據(jù)集的密度特征，選擇初始聚類中心點，使用劃分聚類算法進行迭代，從而實現(xiàn)最優(yōu)聚類來保證算法的運行效率。此外，該算法利用密度閾值剔除部分離群點噪聲，改進了傳統(tǒng)聚類算法的距離度量方式。相對于傳統(tǒng)的分類樹泛化方法，本文引入桶泛化算法[17]，減少了數(shù)據(jù)的信息損失。在同等隱私保護級別的情況下，對比了KACA算法[18]、本文提出的混合聚類k-匿名算法、基于k-匿名的k-means聚類算法[12]的信息損失和運行時間，結(jié)果證明本文提出的混合聚類k-means算法有效改善了聚類效果，降低了數(shù)據(jù)發(fā)布的信息損失。

1 基于聚類的k-匿名算法

在數(shù)據(jù)發(fā)布領域，聚類算法可以通過數(shù)據(jù)之間的相似度對數(shù)據(jù)集進行等價類劃分，降低生成的等價類信息的損失。對于待發(fā)布數(shù)據(jù)，可將其屬性劃分為標識符屬性(Individually Identifying Attribute，IIA)、準標識符屬性(Quasi-Identifier Attribute，QIA)以及敏感屬性(Sensitive Attribute，SA)[5]。標識符屬性用來特定區(qū)分某一個個體，例如電話號碼、身份證號碼等，在數(shù)據(jù)發(fā)布之前需將其進行刪除。準標識符屬性是一些組合起來可以識別某個個體的屬性或者屬性集合，例如郵政編碼、年齡、性別等屬性的集合。敏感屬性是指包含個人敏感信息的屬性，例如疾病、收入等，需要根據(jù)實際情況進行設定。

基于聚類的k-匿名問題可歸結(jié)為：將一個數(shù)據(jù)集D分成n個等價類，使得每個等價類至少包含k個數(shù)據(jù)記錄，則稱其滿足k-匿名模型。其中等價類是指在經(jīng)過泛化匿名操作之后，在準標識符上具有相同屬性值的一組數(shù)據(jù)集合。為了滿足匿名模型的要求，一般需要對原始數(shù)據(jù)在準標識符屬性值上進行泛化操作，其基本思想是通過概括的屬性值去代替原有的具體的屬性值，從而在一定程度上實現(xiàn)對隱私數(shù)據(jù)的保護。但是，泛化操作容易導致泛化過度，使得數(shù)據(jù)的精度有所下降。已有研究表明，使用聚類方法實現(xiàn)的匿名隱私保護可以有效減少泛化操作造成的信息損失[4]。

現(xiàn)有的基于聚類實現(xiàn)k-匿名模型的算法主要以k-means聚類算法為主。k-means是一種基于劃分的聚類算法，其流程圖如圖1所示。由圖可知，k-means聚類算法選擇初始中心點的方式是隨機選擇，并且沒有對數(shù)據(jù)集中的噪聲數(shù)據(jù)進行處理，導致聚類結(jié)果不佳，穩(wěn)定性差，易陷入局部最優(yōu)。

圖1 k-means聚類算法流程圖

2 基于混合聚類的k-匿名算法

為了解決現(xiàn)有基于聚類的k-匿名數(shù)據(jù)發(fā)布算法存在的問題，本文提出了基于混合聚類的k-匿名數(shù)據(jù)發(fā)布算法。如圖2所示，該算法主要由4個部分組成：第1部分是初始中心點選取過程；第2部分是聚類迭代過程，生成最優(yōu)聚類；第3部分是聚類調(diào)整過程，通常需要使等價類中的數(shù)據(jù)記錄介于k和2k-1之間才會有更好的聚類效果[4]；第4部分是泛化生成匿名數(shù)據(jù)集過程。

圖2 混合聚類k-匿名算法框架

算法基本步驟如下：

輸入數(shù)據(jù)集D，k-匿名參數(shù)k。

輸出匿名數(shù)據(jù)集E。

步驟1計算需要劃分的等價類或聚類的個數(shù)m=n/k(m取整數(shù)部分)，其中n為數(shù)據(jù)集D中所有記錄個數(shù)，k為k-匿名參數(shù)；

步驟2利用密度聚類思想，根據(jù)數(shù)據(jù)集密度特征選出m個最優(yōu)初始聚類中心點{S1，S2，S3，…，Sm}，同時剔除離群點噪聲干擾；

步驟3對數(shù)據(jù)集中每一條數(shù)據(jù)記錄，計算其與步驟2生成的所有聚類中心點之間的歐氏距離，并把它加入到距離最近的聚類中心，生成一個簇Ci(m>i>0)。直到所有的數(shù)據(jù)記錄都被分配到相應的簇中，計算新簇的中心點，并對舊的中心點進行更新；

步驟4重復步驟3，直到聚類中心不再發(fā)生變化或達到終止條件；

步驟5對每一個簇的大小進行調(diào)整，使其滿足k-匿名原則。定義一個集合R，若簇Ci(m>i>0)中數(shù)據(jù)記錄數(shù)大于k，則將該簇中距離聚類中心點最遠的|Ci|-k條數(shù)據(jù)記錄加入集合R中；若簇Ci(m>i>0)記錄數(shù)小于k，則將集合R中距離簇Ci最近的k-|Ci|條數(shù)據(jù)記錄加入簇Ci中，最后將集合R中剩余的記錄分別分配到距離最近的簇中。其中|Ci|表示第i個簇中所有記錄的個數(shù)；

步驟6將以上生成的簇進行泛化操作得到等價類E={E1，E2，E3，…，Em}。

2.1 距離度量方法

針對混合型數(shù)據(jù)集[19]，需要對數(shù)值型數(shù)據(jù)和分類型數(shù)據(jù)分別進行距離度量。數(shù)值型數(shù)據(jù)一般采用基于k-means的距離度量方式。分類型數(shù)據(jù)以往都是先建立分類樹，然后根據(jù)分類樹進行距離度量。由于這種方式需要提前建立分類樹，并且泛化過程會造成巨大的信息損失，因此在本文中，針對分類型數(shù)據(jù)，采用基于k-modes[11]算法的分類型數(shù)據(jù)距離度量方式。下面分別介紹兩種針對不同數(shù)據(jù)類型的度量方法的具體計算式。

k-means算法采用歐式距離作為距離度量方式，假設樣本xi=(xi1，xi2，xi3，…，xin)與xj=(xj1，xj2，xj3，…，xjn)，其計算式如式(1)所示。

(1)

因為不同屬性的屬性值有不同的數(shù)量級，所以對數(shù)值屬性進行距離計算之前，需要對屬性進行歸一化處理，使得每個屬性的權重相同。假設年齡屬性的區(qū)間為[0～90]，工資屬性的區(qū)間為[1 000～10 000]，如果不進行歸一化處理，那么在進行距離度量時工資屬性占的權重會過大，導致聚類中心點的偏移。進行歸一化處理后，每個屬性的范圍都在[0～1]之間，便于對多維屬性的數(shù)據(jù)記錄進行距離度量。

k-modes是一種常用的對于離散屬性數(shù)據(jù)集的聚類算法。假設對于某一分類型屬性的屬性值a和b，若屬性值相同，則距離計為0；若屬性值不同，則計為1/l，其中l(wèi)為該分類屬性屬性值的個數(shù)，具體距離計算方式如式(2)所示。

(2)

2.2 初始聚類中心點選取

本文提出的基于混合聚類的k-匿名數(shù)據(jù)發(fā)布算法依據(jù)數(shù)據(jù)集的密度特征來選擇初始聚類中心點，選出的中心點分布均勻，符合數(shù)據(jù)集的分布特點，避免了隨機性對聚類結(jié)果的影響。選取步驟如下：

輸入數(shù)據(jù)集D，k-匿名參數(shù)k。

輸出初始聚類中心點。

步驟1計算出每個數(shù)據(jù)點的密度，并進行從小到大排序；

步驟2選取其中密度最大的點作為第1個聚類中心點；

步驟3將附近距離最近的k-1個點聚成一個簇，把它們放到已分類的集合中；

步驟4從剩下的未分類的集合中，繼續(xù)挑選密度最大的數(shù)據(jù)點作為第i(0

步驟5直到S個聚類中心點被選出。

2.3 密度計算及離群點檢測

密度計算是密度聚類的核心步驟，通過數(shù)據(jù)集的密度特征選取聚類中心點并且剔除數(shù)據(jù)集中的離群點噪聲。若離群點噪聲不經(jīng)處理就直接進行聚類泛化過程，會使得生成的等價類信息損失增大。為了減少離群點對聚類結(jié)果的影響，需要對離群點進行檢測剔除[19]。假設數(shù)據(jù)集中的每一條數(shù)據(jù)記錄當作一個對象，關于對象r的k距離是使r到它的最鄰近的k個對象的最大距離，該距離需滿足以下兩個條件：

(1)對于至少k個對象o′∈D，有distance(r，o′)≤distance(r，o)。其中D為原始數(shù)據(jù)集，distance表示兩個對象之間的歐式距離；

(2)最多有k-1個對象o″∈D，使得distance(r，o″)

圖3中r的k距離(k=9)是r與o之間的距離，可以看出r的9個最近鄰到r的距離均小于或等于r到o的距離，有8個鄰居到r的距離小于o到r的距離。

圖3 對象r的k距離

在數(shù)據(jù)隱私表D中，r是D中的一個記錄。設 distK(i)(0

(3)

對象r的密度表示為

(4)

若r的密度denK(r，D)越大，則distKNN(r，D)越小，即r與它周圍的其他記錄之間距離越近。本文選擇密度較大的點作為聚類的中心點進行迭代，符合數(shù)據(jù)集的分布規(guī)律，可以減少聚類過程的信息損失。離群點一般都是比較孤立的點，與周圍鄰近距離較大，也就是密度較小的點。因此，可以通過設定密度閾值對離群點進行剔除。

2.4 桶泛化算法

數(shù)據(jù)泛化是數(shù)據(jù)發(fā)布最常用的隱私保護方法。通過泛化操作可以將數(shù)據(jù)的信息進行概化，擴大數(shù)據(jù)的區(qū)間，或者進行語義上的概括，從而隱藏屬性的真實值，來獲得數(shù)據(jù)的隱私保護。傳統(tǒng)的泛化方法是采用分類樹進行的，這種方法需要提前對屬性建立泛化層次。如圖4所示為職業(yè)屬性的泛化層次分類樹。

圖4 職業(yè)屬性分類樹

分類樹是通過最小公共子樹節(jié)點進行泛化的，泛化的層次越高，其信息損失越大。例如，屬性值工程師和律師的最小公共子樹為專業(yè)人員，那么經(jīng)過泛化之后的屬性值為專業(yè)人員。

采用分類樹進行屬性泛化容易導致過度泛化。針對分類型屬性，本文采用桶算法進行泛化。桶泛化算法與傳統(tǒng)泛化方式不同，桶泛化算法將同一等價類的每個準標識符屬性的所有屬性值都放在一個名為桶的抽象容器內(nèi)。例如在某等價類中，對于職業(yè)屬性，其屬性值有工程師和律師，那么對于職業(yè)屬性經(jīng)過桶算法泛化后的屬性值為{工程師，律師}，數(shù)據(jù)記錄的屬性值被完整保留，并且降低了數(shù)據(jù)的信息損失。同時，對于等價類中的每條數(shù)據(jù)記錄，對應桶內(nèi)的屬性值的概率是相等的，例如上述例子中職業(yè)是工程師和律師的概率都是1/2，可以避免攻擊者通過斜偏攻擊獲取背景知識。

2.5 信息損失度量方法

信息損失度量[16]是對聚類算法的聚類效果的直觀評價，聚類效果越好，數(shù)據(jù)的信息損失越小。信息損失度分析是對數(shù)據(jù)發(fā)布質(zhì)量的度量，這里將數(shù)據(jù)分成數(shù)值型和分類型分別進行介紹。

對于待發(fā)布的數(shù)據(jù)集中的每一條數(shù)據(jù)記錄，當數(shù)據(jù)記錄的準標識符屬性類型為數(shù)值型時，其信息損失計算方法為

(5)

式中，Vmax為某一準標識符屬性在其等價類的最大值；Vmin為該標識符屬性在同一等價類的最小值；|Nj|為準標識符屬性的全局區(qū)間寬度。假設在數(shù)據(jù)表中某一屬性的值域范圍是[20～30]，則其區(qū)間寬度是10；某一條記錄經(jīng)過數(shù)據(jù)匿名處理之后，該記錄的屬性值為[20～22]，則對于該記錄的這一屬性在該等價類的信息損失度為2/10=0.2。

當數(shù)據(jù)記錄的準標識符屬性類型為分類型時，其信息損失計算方法為

(6)

式中，|cardCi|為某一準標識符屬性在其等價類的所有可能取值種類數(shù)；|Ci|為該屬性的全局取值種類數(shù)。假設disease屬性的取值范圍為{cancer，head disease，tracheitis}，某一條記錄經(jīng)過匿名處理后disease的屬性值為{cancer， head disease}，則該記錄diease屬性的信息損失度為2/3。

當數(shù)據(jù)記錄既有數(shù)值型屬性，又有分類型屬性時，其中數(shù)值型屬性的個數(shù)為n，分類型屬性的個數(shù)為m，則對于整個等價類來說，其信息損失為

(7)

式中，E為等價類；|E|為等價類中數(shù)據(jù)記錄的個數(shù)。整個數(shù)據(jù)集D的平均信息損失度為

(8)

式中，|D|為數(shù)據(jù)集中所有記錄的條數(shù)。

3 實驗與結(jié)果分析

3.1 實驗環(huán)境和數(shù)據(jù)集

本算法采用Python語言實現(xiàn)，實驗硬件配置如下：Intel(R) Core(TM) i5-3337u CPU @1.80 GHz，操作系統(tǒng)為Windows 7，內(nèi)存8 GB。實驗所用數(shù)據(jù)為UCI的Adult數(shù)據(jù)集(http://archive.ics.uci.edu/ml/)。該數(shù)據(jù)集包括部分美國人口普查數(shù)據(jù)，是隱私保護和數(shù)據(jù)挖掘研究中最常用的標準測試數(shù)據(jù)集。實驗中，對比了KACA算法、基于k-means聚類的k-匿名算法和本文提出的混合聚類k-匿名算法。

首先對數(shù)據(jù)集進行歸一化預處理，使得各屬性的值控制在[0～1]范圍內(nèi)，且假設每個屬性的權重都為1。實驗數(shù)據(jù)集信息如表1所示。

表1 實驗數(shù)據(jù)集信息

3.2 結(jié)果分析

圖5所示為當k-匿名參數(shù)值不斷增大時，3種不同算法的信息損失度對比情況，其中橫坐標為k-匿名參數(shù)k的取值，縱坐標為平均信息損失度。當k取值從10到70變化時，隨著k值增大，數(shù)據(jù)的信息損失度也不斷增大。這是因為數(shù)據(jù)集的大小不變，k增大導致等價類的個數(shù)減少，每個等價類的數(shù)據(jù)記錄個數(shù)變多。從圖中可以發(fā)現(xiàn)，在不同的k值情況下，本文提出的混合聚類k-匿名數(shù)據(jù)發(fā)布算法相對于其他兩種算法的信息損失度小，聚類效果更好，具有明顯的優(yōu)勢。

圖5 不同k值的信息損失度對比

圖6為在準標識符屬性個數(shù)不斷增加時，3種算法的信息損失度的對比情況。橫坐標為準標識符的個數(shù)，縱坐標為平均信息損失度。當準標識符屬性QI個數(shù)不斷增大時，3種不同算法的信息損失度也逐漸增加。這是因為隨著準標識符數(shù)量的增加，聚類的難度越大，劃分等價類的條件越高，從而導致需要泛化的程度越高。同時可以看到，在QI較小時，3種算法的信息損失度相近。當QI=7時，本文所提出的算法相對于其他兩種信息損失度有明顯區(qū)別，這說明數(shù)據(jù)量越大或需要劃分的準標識符越多時，本文算法可以有效減少信息損失，提高數(shù)據(jù)可用性。

圖6 不同準標識符個數(shù)下的信息損失度對比

圖7為在不同k-匿名參數(shù)情況下，3種算法的執(zhí)行時間對比，其中橫坐標為k-匿名參數(shù)值，縱坐標為算法的執(zhí)行時間。隨著k值增大，3種算法的執(zhí)行時間都呈下降趨勢，這是因為當匿名參數(shù)k增大時，最終生成的等價類變少，聚類所花費的時間也就減少。當k值相同的情況下，KACA算法執(zhí)行時間最短，k-means聚類算法和混合聚類的k-匿名算法的執(zhí)行時間差距不大，但隨著參數(shù)k的不斷增大，兩者逐漸逼近。雖然傳統(tǒng)k-匿名算法的時間復雜度較小，執(zhí)行時間快，但是靜態(tài)數(shù)據(jù)發(fā)布一般都是線下處理然后在發(fā)布，沒有嚴格的時間要求。當達到較好的數(shù)據(jù)發(fā)布質(zhì)量時，損失較小的算法執(zhí)行時間仍在可接受的范圍內(nèi)。

圖7 不同k值對應的算法執(zhí)行時間對比

4 結(jié)束語

本文將密度聚類和距離聚類相結(jié)合，提出了一種混合聚類k-匿名數(shù)據(jù)發(fā)布隱私保護算法。實驗結(jié)果表明，在滿足k-匿名的前提下，該算法能夠有效提高數(shù)據(jù)發(fā)布質(zhì)量，減少信息損失，尤其在準標識符屬性越多的情況下效果越好。但是本文在k-匿名模型的基礎上，只考慮了數(shù)據(jù)匿名發(fā)布的數(shù)據(jù)可用性，在安全性方面，其隱私披露風險是1/k。因此，在下一步的工作中，將嘗試在減少信息損失的同時進一步提高隱私保護的安全性。