張少波，原劉杰，毛新軍，朱更明

（1.湖南科技大學(xué)計算機科學(xué)與工程學(xué)院，湖南湘潭 411201；2.國防科技大學(xué)復(fù)雜系統(tǒng)軟件工程重點實驗室，湖南長沙 410073）

1 引言

聚類是一種常用的數(shù)據(jù)挖掘方法，它按照某種特定標準將數(shù)據(jù)集分割為不同的簇，使得同一個簇中數(shù)據(jù)相似性較高［1］.K-means是聚類中的經(jīng)典算法，其實現(xiàn)簡單且聚類高效，它只適用于處理數(shù)值型數(shù)據(jù)集，而對分類型數(shù)據(jù)的聚類通常使用K-modes算法［2，3］.目前，聚類分析在數(shù)據(jù)分析、服務(wù)推薦等多個領(lǐng)域發(fā)揮著重要的作用，但聚類數(shù)據(jù)中通常包含大量的個人敏感信息，如對客戶數(shù)據(jù)進行聚類分析可為不同類型的客戶提供個性化服務(wù)，但攻擊者從這些信息中能推測出用戶的興趣愛好［4～6］.因此在使用聚類對用戶數(shù)據(jù)分析過程中，迫切需要保護用戶的個人隱私.

差分隱私［7］是采用嚴格數(shù)學(xué)定義的隱私保護模型，它可以量化用戶隱私保護程度，并且能抵御攻擊者發(fā)起的背景知識攻擊和合成攻擊［8，9］.目前差分隱私已廣泛應(yīng)用于數(shù)據(jù)挖掘、數(shù)據(jù)發(fā)布、位置服務(wù)等領(lǐng)域的隱私保護［10～12］，而且它與隨機擾動、數(shù)據(jù)交換等隱私保護技術(shù)相比［13，14］，在聚類分析數(shù)據(jù)隱私保護方面具有明顯的優(yōu)勢［15～17］.差分隱私具有強健的隱私保護能力，但它需要一個可信第三方對數(shù)據(jù)進行處理，而由第三方造成的數(shù)據(jù)泄露事件卻層出不窮，如谷歌，雅虎和微軟等公司的數(shù)據(jù)意外泄漏事件，這不僅造成了用戶隱私信息的泄露，還嚴重損害了公司聲譽.因此，現(xiàn)實中很難找到完全可信的第三方.針對該問題，本地差分隱私（Local Different Privacy，LDP）在保證數(shù)據(jù)可用性的前提下，通過在用戶端對數(shù)據(jù)進行擾動，實現(xiàn)了對用戶隱私的去第三方保護，并且它與差分隱私同樣采用了嚴格數(shù)學(xué)定義的隱私保護模型［18］，因此它已成為隱私保護領(lǐng)域中解決此類問題的重要方法.

目前，國內(nèi)外學(xué)者已提出一些本地差分隱私算法，其中RAPPOR算法是頻數(shù)統(tǒng)計的經(jīng)典算法［19］，它誤差小，數(shù)據(jù)可用性高，但它需要候選屬性值已知.針對RAPPOR的不足，文獻［20］在其基礎(chǔ)上對字符串進行映射，實現(xiàn)了無需候選屬性值已知的頻數(shù)統(tǒng)計.針對集值數(shù)據(jù)的頻繁項查詢問題，文獻［21］提出了包含兩階段機制的LDPMiner算法，文獻［22］在其基礎(chǔ)上進一步研究，提出了具有更高查詢精度的SVIM（Set-Value Item Mining）算法.不同于頻率估計方法，文獻［23］通過數(shù)據(jù)離散化操作實現(xiàn)了在［-1，1］區(qū)間中的均值估計，然而該方法的輸出結(jié)果是兩個固定值，這會導(dǎo)致估計值偏離［-1，1］區(qū)間.針對該問題，文獻［24］將［-1，1］區(qū)間中的任意值擾動到受約束區(qū)間［-C，C］，然后在此區(qū)間內(nèi)計算該擾動值的邊界.此外，本地差分隱私在空間范圍查詢，眾包數(shù)據(jù)收集等領(lǐng)域也得到了廣泛應(yīng)用［25，26］.雖然本地差分隱私可以有效應(yīng)對第三方隱私泄露問題，但將它應(yīng)用于聚類分析數(shù)據(jù)隱私保護時，仍然存在如下挑戰(zhàn)：（1）如何降低噪聲在聚類更新質(zhì)心過程中的影響.如果直接根據(jù)收集到的擾動數(shù)據(jù)對用戶進行分簇，然后再基于擾動數(shù)據(jù)計算每個簇的質(zhì)心，則會進一步放大噪聲的影響.（2）如何以較小的噪聲誤差和通訊開銷完成聚類.如果用戶將自身所有數(shù)據(jù)擾動并匯報，則所需的通訊開銷以及聚類結(jié)果的噪聲誤差會較大.針對上述挑戰(zhàn)，本文提出一種基于本地差分隱私的K-modes聚類數(shù)據(jù)隱私保護方法（Local Different Privacy K-modes，LDPK）.該方法首先對數(shù)據(jù)隨機采樣，然后采用本地差分隱私技術(shù)在用戶端對采樣數(shù)據(jù)進行擾動，最后通過服務(wù)端與用戶端的交互迭代完成聚類.本文主要貢獻如下：

（1）構(gòu)建了一個基于本地差分隱私的K-modes聚類數(shù)據(jù)隱私保護框架.引入本地差分隱私技術(shù)在用戶端對數(shù)據(jù)進行擾動，并通過服務(wù)端與用戶端的交互迭代，實現(xiàn)了對聚類過程中用戶數(shù)據(jù)的去第三方隱私保護.

（2）為提高聚類結(jié)果的質(zhì)量并降低通訊開銷，在使用本地差分隱私技術(shù)擾動前，對數(shù)據(jù)進行隨機采樣，避免因隱私預(yù)算分割導(dǎo)致的聚類質(zhì)量降低以及發(fā)送全部數(shù)據(jù)帶來的通訊開銷較高問題.

（3）理論分析證明了方法的隱私性和可用性，真實數(shù)據(jù)集上的實驗結(jié)果表明，該方法在滿足本地差分隱私機制的前提下，有效保證了聚類結(jié)果質(zhì)量.

2 本地差分隱私與K-modes聚類

2.1 本地差分隱私

針對第三方存在泄露用戶隱私的風(fēng)險，本地差分隱私直接在用戶端對數(shù)據(jù)進行擾動，它能滿足用戶對個人隱私保護的更高要求.本地差分隱私的形式化定義如下：

定義1假設(shè)n名用戶都至少擁有一條記錄，其隱私保護算法為M、定義域為Dom、值域為Rnm.如果任意兩條記錄t(t∈Dom)和t'(t'∈Dom)，經(jīng)M處理后得到相同輸出結(jié)果t*(t*∈Rnm)的概率滿足式（1），則M滿足ε-LDP.

定義1中的ε是隱私預(yù)算，其值大于0.它表示用戶數(shù)據(jù)的隱私保護強度，ε越小，隱私保護程度越高，但相應(yīng)的數(shù)據(jù)可用性就會降低，因此在具體應(yīng)用中要從多個角度權(quán)衡ε的取值.同時從定義1可看出，本地差分隱私通過控制任意兩條記錄輸出結(jié)果的相似性來保護數(shù)據(jù)隱私.經(jīng)過本地差分隱私處理后，從輸出結(jié)果逆推出輸入數(shù)據(jù)是非常困難的.

2.2 K-modes聚類

K-modes算法由K-means擴展而來，主要應(yīng)用于分類型數(shù)據(jù)的聚類.它采用Hamming距離衡量兩個點之間的間距［27］，并通過計算屬性值的眾數(shù)來確定簇的質(zhì)心.K-modes算法的具體步驟如下.

步驟1：確定需要劃分的簇數(shù)k，從數(shù)據(jù)集中隨機選擇k個點作為起始質(zhì)心.

步驟2：分別計算數(shù)據(jù)集中每個點與每個質(zhì)心的距離，并將點劃分給距離最近的質(zhì)心.

步驟3：得到k個簇后，通過計算各個屬性值的眾數(shù)，然后確定每個簇的新質(zhì)心.

步驟4：重復(fù)步驟2和步驟3，直到相鄰兩次的聚類結(jié)果不再發(fā)生變化.

3 K-modes聚類數(shù)據(jù)隱私保護方法

3.1 問題描述

假設(shè)存在用戶集U={u1，u2，…，}un和屬性集M={A1，A2，…，Ad}.每個用戶ui(1≤i≤n)都擁有一個d維屬性元組mi={a1，a2，…，ad}，aj(1≤j≤d)是Aj的某個屬性值.K-modes算法的目標是將用戶劃分為k個簇C={c1，c2，…，}ck.在分簇過程中通常包含一些用戶敏感信息，而采用可信第三方對聚類數(shù)據(jù)進行隱私保護的方法，卻很難找到絕對可信的第三方來防止用戶隱私數(shù)據(jù)泄露.表1為本文中使用的重要符號.

表1 符號說明

3.2 具體實現(xiàn)方案

本文提出了一種基于本地差分隱私的K-modes聚類數(shù)據(jù)隱私保護方法，其整體框架如圖1所示.用戶ui向服務(wù)端發(fā)送數(shù)據(jù)時，為避免隱私預(yù)算分割并降低通訊開銷，先對數(shù)據(jù)進行隨機采樣，然后采用本地差分隱私算法對采樣數(shù)據(jù)進行擾動，最后將得到的擾動數(shù)據(jù)發(fā)送給服務(wù)端.

圖1 基于LDP的K-modes聚類框架

上述過程無需第三方對數(shù)據(jù)進行隱私預(yù)處理，確保了用戶的隱私不受不可信第三方的威脅.服務(wù)端在收集到所有用戶的擾動數(shù)據(jù)后，依據(jù)屬性集信息確定初始質(zhì)心集V={ν1，ν2，…，νk}，并將其發(fā)送給所有用戶.用戶ui從服務(wù)端接收到質(zhì)心集后，根據(jù)自身真實數(shù)據(jù)mi計算出距離最近的質(zhì)心νy(1≤y≤k)，然后依據(jù)質(zhì)心νy確定所屬的簇cy并匯報.服務(wù)端收到用戶的簇信息后，結(jié)合擾動數(shù)據(jù)求解新的質(zhì)心集.最后重復(fù)上述的交互過程不斷進行迭代，直到各個簇中的質(zhì)心在相鄰兩次迭代中不再發(fā)生變化.

3.3 用戶端數(shù)據(jù)處理

用戶端的每個用戶ui都擁有一個真實數(shù)據(jù)集mi={a1，a2，…，}ad，LDPK采用目前本地差分隱私技術(shù)中高精度的最優(yōu)一元編碼算法［28］對其進行擾動.該算法在擾動前要對數(shù)據(jù)進行編碼，以a1為例，設(shè)它對應(yīng)的屬性A1為“民族”，則屬性域大小|A1|為56，用一個長度為56的比特字符串b={0，0，…，0}表示該屬性域.每個民族對應(yīng)b中一個比特位，設(shè)a1為漢族，而漢族對應(yīng)第x個比特位，故將第x個比特位設(shè)為1，得到比特字符串b={0，…，1，0}.對mi中每個屬性值aj都按照上述過程編碼，以x表示屬性值對應(yīng)的比特位，以w(1≤w≤|bj|)表示x的取值范圍，編碼如式（2）所示：

編碼完成后得到比特字符串Bi={b1，b2，…，bj，…，bd}，然后對Bi進行隨機采樣，并對采樣值bj采用式（3）進行擾動.

算法1數(shù)據(jù)擾動輸入:用戶ui的數(shù)據(jù)mi={a1，a2，…，}ad,隱私預(yù)算ε;輸出:擾動后的值(j，bj');1. 將mi={a1，a2，…，}ad編碼為Bi={b1，b2，…，bd};2. 從Bi中隨機采樣bj,同時設(shè)置b'j={0，0，…，0},|b'j|=|bj|;3. FOR w=0 to|bj|-1 do 4. IF bj[w]=1 5. Pr[bj'[w]=1]=1/2 6. IF bj[w]=0 7. Pr[bj'[w]=1]=1 eε+1 8. Return(j，bj')

在之后的迭代過程中，服務(wù)端先計算出質(zhì)心集合V={ν1，ν2，…，νk}，并發(fā)送給所有用戶.然后每個用戶ui根據(jù)自身的真實數(shù)據(jù)mi計算出距離最近的質(zhì)心νy.最后再依據(jù)質(zhì)心νy確定所屬的簇cy，并將其匯報給服務(wù)端.

3.4 服務(wù)端求解質(zhì)心

服務(wù)端從所有用戶收集到擾動數(shù)據(jù)B'={b1'，b2'，…，bd'}后，首先從屬性集中隨機選取k個d維屬性元組作為初始質(zhì)心發(fā)送給用戶，然后依據(jù)擾動數(shù)據(jù)和用戶返回的簇信息計算出新的質(zhì)心集V={ν1，ν2，…，νk}.其具體步驟如下：

（1）根據(jù)每個用戶匯報的cy，將所有用戶劃分為k個簇C={c1，c2，…，ck}.|cr|(1≤r≤k)表示簇中的用戶人數(shù)，因用戶對數(shù)據(jù)進行了采樣，故簇中每個屬性對應(yīng)的用戶人數(shù)變?yōu)閨cr|d.為便于計算，后續(xù)以|cr|'表示|cr|d.

（2）計算每個簇中各個屬性值的頻率.以簇cr中的屬性Aj為例，統(tǒng)計對應(yīng)擾動數(shù)據(jù)b'j的每個比特位得到S={s1，s2，…，sl}，sl(0≤l＜|b'j|)表示b'j中第l個比特位為1的個數(shù)，再結(jié)合其他數(shù)據(jù)計算出Aj每個屬性值的估計頻率t'.

（3）服務(wù)端在計算出各個簇中所有屬性值的頻率后，選取每個屬性中頻率最高的屬性值，以它們的集合作為該簇的質(zhì)心，最終得到新的質(zhì)心集V={ν1，ν2，…，νk}.服務(wù)端質(zhì)心求解的具體過程如算法2所示.

算法2計算迭代質(zhì)心輸入:用戶簇C={c1，c2，…，}ck,每個簇的數(shù)據(jù)B'={b1'，b2'，…，bd'},p,q;輸出:新的質(zhì)心集合V={ν1，ν2，…，}νk;1. FOR C from r=1 to k do 2. From b1'to bd'do 3. 統(tǒng)計每個比特位得到S={s1，s2，…，sl}4. FOR i=0 to l-1 do 5. t'i=si-|cr|'×q|cr|'×( )p-q 6. Return a=Max(t')對應(yīng)的屬性值7. Return νr={a1，a2，…，ad}8. Return V={ν1，ν2，…，}νk

服務(wù)端最后向用戶發(fā)送新的質(zhì)心集，并根據(jù)從用戶收集到的簇信息不斷重復(fù)上述過程，直到各個簇中的質(zhì)心在相鄰兩次迭代中不再發(fā)生變化.

3.5 隱私性和可用性分析

本文提出的LDPK方法中只有算法1需要隱私預(yù)算，因此只要算法1滿足本地差分隱私的定義，則LDPK方法同樣滿足該定義.

引理1算法1滿足本地差分隱私的定義.

證明設(shè)存在屬性Aj的兩個屬性值x1和x2，由它們的擾動結(jié)果bj'可得：

因bj'中每個比特位都是獨立擾動，故式（4）只在x1和x2處不同，可以得出：

對于式（5），當bj'中的x1位置為1，x2位置為0時，它右側(cè)的比值達到最大：

因此，算法1滿足本地差分隱私的定義.

服務(wù)端在更新質(zhì)心時，由于沒有收集用戶的真實數(shù)據(jù)，它不能計算出每個屬性值的真實頻率t，只能得出估計頻率t'.為了降低噪聲的影響，我們希望計算出的t'滿足無偏性.因此，需要通過如算法2的步驟5所示來計算t'.

引理2通過算法2的步驟5計算出的估計頻率t'滿足無偏性.

證明假設(shè)t與t'分別為簇cr中某屬性值a的真實頻率與估計頻率，g與g'分別為a的真實頻數(shù)和估計頻數(shù).設(shè)a'為a對應(yīng)的比特位，s是擾動數(shù)據(jù)中a'為1的個數(shù).

由于服務(wù)端無法獲得a的真實頻數(shù)g，為了求解t'，需要計算估計頻數(shù)g'.因用戶以兩種概率對每個比特位進行響應(yīng)，故|cr|'個用戶對a'的響應(yīng)結(jié)果構(gòu)成了滿足二項分布的|cr|'個0/1序列.根據(jù)該二項分布，構(gòu)造相應(yīng)的似然函數(shù)：

對式（8）兩側(cè)取對數(shù)并對g求導(dǎo)即可求出它的極大似然估計g'：

對于求解出的g'可以證明其滿足無偏性：

因g'滿足無偏性，故可求出無偏估計頻率t'：

對用戶數(shù)據(jù)直接擾動存在的聚類質(zhì)量降低和通訊開銷較高問題，LDPK方法通過對數(shù)據(jù)采樣，使用戶在發(fā)送擾動數(shù)據(jù)時只需發(fā)送采樣值，大大降低了通訊開銷.但為了降低擾動數(shù)據(jù)中噪聲的影響，需要較大的數(shù)據(jù)量，而采樣使任意屬性值對應(yīng)的用戶總數(shù)變?yōu)閷嶋H值的1/d，因此需要對采用這兩種方式得到的擾動數(shù)據(jù)的可用性進行分析.

引理3對用戶數(shù)據(jù)采樣相比于分割隱私預(yù)算可以提高擾動數(shù)據(jù)的可用性.

證明設(shè)有n名用戶的數(shù)據(jù)是d維屬性元組，隱私預(yù)算為ε，其某個屬性值的估計頻數(shù)為g'，f為它對應(yīng)的比特位，s是擾動數(shù)據(jù)中f為1的個數(shù)，真實頻率為t.若不采樣且該屬性值獲得全部ε，則由式（9）可得g'的方差為：

式（13）中n×t為屬性值的真實頻數(shù)，它是一個常數(shù)，為了便于計算將其省略.同時又因兩種方法中屬性值對應(yīng)的用戶數(shù)目不同，導(dǎo)致無法直接比較它們的方差，故對式（13）進行如下轉(zhuǎn)換：

對d維屬性隨機采樣使得屬性值對應(yīng)的用戶數(shù)變?yōu)閚/d，其方差以η1表示：

對隱私預(yù)算分割使得每個屬性獲得的隱私預(yù)算變?yōu)棣?d，其方差以η2表示：

如果采用隨機采樣得到的擾動數(shù)據(jù)可用性優(yōu)于隱私預(yù)算分割，那么η2和η1應(yīng)當滿足η1＜η2，而它們之間的大小關(guān)系如下：

由上文可知隱私預(yù)算大于0.因此，對于式（17）結(jié)果的左側(cè)部分可以得出：

定義y=eε/d，將它代入式（17）的結(jié)果部分.同時又因式（18）大于0，故將式（17）結(jié)果的左側(cè)部分舍去以簡化運算，則式（17）可化簡為：

由式（19）可知η1＜η2，因此對用戶數(shù)據(jù)隨機采樣相比于分割隱私預(yù)算，可以提高擾動數(shù)據(jù)可用性.

4 實驗結(jié)果分析

實驗主要采用兩個真實數(shù)據(jù)集，一個數(shù)據(jù)集來自IPUMS網(wǎng)站的公開數(shù)據(jù)，從中選取了USA的5萬條普查數(shù)據(jù)，如表2所示，每條記錄包含5個分類屬性.另一個是隱私保護研究領(lǐng)域常用的UCI數(shù)據(jù)庫中Adult數(shù)據(jù)集，經(jīng)過刪除其中的無效記錄后共有30162條記錄，如表3所示，每條記錄分別選取6個分類屬性.

表2 USA普查數(shù)據(jù)集屬性

表3 Adult數(shù)據(jù)集屬性

實驗的硬件環(huán)境為：Intel（R）Core（TM）i5-7300HQ CPU@2.50 GHz 2.50 GHz，8.00 GB內(nèi)存.軟件環(huán)境為：Microsoft Windows 10.采用PyCharm開發(fā)平臺，以Python編程語言實現(xiàn).

實驗采用準確率AC（Accuracy）和熵E（Entropy）作為聚類質(zhì)量評價指標，以無隱私保護下的K-modes聚類結(jié)果作為真實值.評價指標如式（20）和式（21）所示：

其中k是聚類簇數(shù)，hj是采用隱私保護算法得到的聚類簇中正確聚類的數(shù)據(jù)個數(shù)，N是數(shù)據(jù)集的大小，ti是無隱私保護下得到的聚類簇，cj是采用隱私保護算法得到的聚類簇.實驗研究相關(guān)參數(shù)對LDPK算法性能的影響并與現(xiàn)有差分隱私保護下的K-modes算法［17］（Different Privacy K-modes，DPK）進行對比.聚類簇數(shù)k取3，同時為了降低初始質(zhì)心選擇和擾動數(shù)據(jù)中噪聲對結(jié)果的影響，每個實驗進行300次，結(jié)果取平均值.

4.1 參數(shù)變化對LDPK性能的影響

改變隱私預(yù)算ε，其他參數(shù)保持不變，分析隱私預(yù)算大小對LDPK性能的影響.由圖2可知隨著ε的增大，聚類結(jié)果的準確率隨之提升，熵隨之降低，其原因在于擾動數(shù)據(jù)中的噪聲添加量取決于ε的值.ε越小，擾動數(shù)據(jù)中添加的噪聲越多，則聚類結(jié)果質(zhì)量越低.ε越大，擾動數(shù)據(jù)中添加的噪聲越少，則聚類結(jié)果質(zhì)量越高.

圖2 隱私預(yù)算ε對算法性能的影響

將隱私預(yù)算ε設(shè)置為1.0，其他參數(shù)保持不變.從數(shù)據(jù)集中隨機抽取不同數(shù)目的記錄，分析數(shù)據(jù)集大小N對LDPK性能的影響.由表4和表5可知隨著數(shù)據(jù)集的增大，聚類結(jié)果的準確率隨之增加，熵隨之降低，其原因在于本地差分隱私中每個用戶以一定的概率匯報真實值，而根據(jù)大數(shù)定理，同等條件下實驗重復(fù)次數(shù)越多，隨機事件的結(jié)果越接近其真實頻率.因此數(shù)據(jù)量越大，響應(yīng)隨機性的影響越小，聚類結(jié)果的質(zhì)量也就越高.

表4 Adult大小對AC和E的影響

表5 USA大小對AC和E影響

4.2 算法性能對比

改變隱私預(yù)算ε，其他參數(shù)保持不變，對比LDPK與DPK的聚類結(jié)果質(zhì)量.由圖3可知，DPK的聚類結(jié)果質(zhì)量略優(yōu)于LDPK，其原因在于DPK依靠第三方對真實數(shù)據(jù)進行隱私處理，可以更好的控制噪聲添加，所以聚類結(jié)果的質(zhì)量較高.但LDPK的聚類結(jié)果質(zhì)量與DPK相比差距不大，這表明通過對用戶數(shù)據(jù)的隨機采樣以及服務(wù)端與用戶端的交互迭代，LDPK有效保證了聚類結(jié)果的質(zhì)量.同時與DPK相比，LDPK不需要任何第三方對真實數(shù)據(jù)進行隱私預(yù)處理，避免了第三方泄露用戶隱私的風(fēng)險，提高了用戶數(shù)據(jù)隱私的保護程度.

圖3 性能對比

5 結(jié)語

針對K-modes聚類數(shù)據(jù)中用戶敏感信息的隱私保護問題，當前主要依靠基于可信第三方的隱私保護方法，但實際應(yīng)用中該第三方也存在隱私泄露風(fēng)險.本文提出了一種本地差分隱私下的K-modes聚類數(shù)據(jù)隱私保護方法.該方法結(jié)合本地差分隱私和隨機采樣技術(shù)在用戶端對數(shù)據(jù)進行擾動，使得整個聚類過程中服務(wù)端都無法獲得用戶的真實信息，同時它基于去第三方思想，避免了第三方泄露用戶隱私的風(fēng)險.在真實數(shù)據(jù)集上的實驗結(jié)果表明，該方法在滿足本地差分隱私機制的前提下，有效保證了聚類結(jié)果的質(zhì)量.

本文提出的方法使用戶所有數(shù)據(jù)受到同等程度的隱私保護，但有些數(shù)據(jù)不需要很強的隱私保護度.因此在未來工作中，我們將嘗試對用戶數(shù)據(jù)敏感度分級，允許服務(wù)端直接收集敏感度較低的數(shù)據(jù)，而對敏感度較高的數(shù)據(jù)采用本地差分隱私進行保護，以滿足用戶對不同敏感度數(shù)據(jù)的個性化隱私保護需求.