基于本地差分隱私的K-modes聚類數(shù)據(jù)隱私保護(hù)方法

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

（1.湖南科技大學(xué)計(jì)算機(jī)科學(xué)與工程學(xué)院，湖南湘潭 411201；2.國(guó)防科技大學(xué)復(fù)雜系統(tǒng)軟件工程重點(diǎn)實(shí)驗(yàn)室，湖南長(zhǎng)沙 410073）

1 引言

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

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

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

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

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

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

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

2.1 本地差分隱私

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

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

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

2.2 K-modes聚類

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

步驟1：確定需要?jiǎng)澐值拇財(cái)?shù)k，從數(shù)據(jù)集中隨機(jī)選擇k個(gè)點(diǎn)作為起始質(zhì)心.

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

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

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

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

3.1 問(wèn)題描述

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

表1 符號(hào)說(shuō)明

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

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

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

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

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

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

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

算法1數(shù)據(jù)擾動(dòng)輸入:用戶ui的數(shù)據(jù)mi={a1，a2，…，}ad,隱私預(yù)算ε;輸出:擾動(dòng)后的值(j，bj');1. 將mi={a1，a2，…，}ad編碼為Bi={b1，b2，…，bd};2. 從Bi中隨機(jī)采樣bj,同時(shí)設(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')

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

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

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

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

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

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

算法2計(jì)算迭代質(zhì)心輸入:用戶簇C={c1，c2，…，}ck,每個(gè)簇的數(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)計(jì)每個(gè)比特位得到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')對(duì)應(yīng)的屬性值7. Return νr={a1，a2，…，ad}8. Return V={ν1，ν2，…，}νk

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

3.5 隱私性和可用性分析

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

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

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

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

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

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

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

引理2通過(guò)算法2的步驟5計(jì)算出的估計(jì)頻率t'滿足無(wú)偏性.

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

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

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

對(duì)于求解出的g'可以證明其滿足無(wú)偏性：

因g'滿足無(wú)偏性，故可求出無(wú)偏估計(jì)頻率t'：

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果分析

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

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

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

實(shí)驗(yàn)的硬件環(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開(kāi)發(fā)平臺(tái)，以Python編程語(yǔ)言實(shí)現(xiàn).

實(shí)驗(yàn)采用準(zhǔn)確率AC（Accuracy）和熵E（Entropy）作為聚類質(zhì)量評(píng)價(jià)指標(biāo)，以無(wú)隱私保護(hù)下的K-modes聚類結(jié)果作為真實(shí)值.評(píng)價(jià)指標(biāo)如式（20）和式（21）所示：

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

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

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

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

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

表4 Adult大小對(duì)AC和E的影響

表5 USA大小對(duì)AC和E影響

4.2 算法性能對(duì)比

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

圖3 性能對(duì)比

5 結(jié)語(yǔ)

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

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