韓建民, 劉 奇, 王麗俠, 魯劍鋒, 彭 浩, 胡兆龍

(1.浙江師范大學(xué) 數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院,浙江 金華 321004;2.浙江師范大學(xué) 行知學(xué)院，浙江 金華 321004)

0 引 言

“簽到”是目前互聯(lián)網(wǎng)上最熱門的應(yīng)用之一，F(xiàn)oursquare,Gowalla,Loopt,BriteKite,Yelp,Facebook等知名互聯(lián)網(wǎng)企業(yè)先后開通簽到功能.簽到服務(wù)的廣泛應(yīng)用，在互聯(lián)網(wǎng)上產(chǎn)生了大量的簽到數(shù)據(jù)，從這些簽到數(shù)據(jù)中，人們可以挖掘出用戶的行為軌跡和生活習(xí)慣，這對(duì)潛在客戶的識(shí)別和精準(zhǔn)化營(yíng)銷具有重要意義.因此，商家會(huì)著力研究如何激勵(lì)用戶參與簽到活動(dòng)[1].現(xiàn)有的簽到激勵(lì)機(jī)制多采取集中式方案[2-6]，由中心服務(wù)器負(fù)責(zé)執(zhí)行激勵(lì)機(jī)制，通過返給簽到用戶一定的獎(jiǎng)勵(lì)來激勵(lì)用戶持續(xù)參加簽到活動(dòng).

由于簽到數(shù)據(jù)包含用戶的位置信息，簽到活動(dòng)會(huì)泄漏用戶的位置隱私,因此，近年來簽到服務(wù)中的隱私問題引起了學(xué)術(shù)和工業(yè)界的關(guān)注.目前，解決該問題的主要方法包括：1)位置擾亂，例如向位置添加噪音[7]、降低位置精度(泛化)[8]、隱藏位置[9]、虛假位置[10]等；2)用戶標(biāo)識(shí)混淆[11].這些工作都是通過擾亂原始信息來保護(hù)用戶的位置隱私.

現(xiàn)有研究工作沒有考慮到用戶的隱私偏好，而隱私保護(hù)本身就是個(gè)性化的，所以需要設(shè)計(jì)個(gè)性化的隱私保護(hù)方案.為此，筆者設(shè)計(jì)了一種具有個(gè)性化隱私保護(hù)能力的簽到激勵(lì)機(jī)制，通過隱私預(yù)算來刻畫用戶的個(gè)性化隱私需求，結(jié)合位置不可區(qū)分隱私保護(hù)方法實(shí)現(xiàn)個(gè)性化隱私保護(hù)，并設(shè)計(jì)基于數(shù)據(jù)質(zhì)量的激勵(lì)機(jī)制以鼓勵(lì)更多的用戶參與簽到.本文主要貢獻(xiàn)包括：

1)將差分隱私方法引入到簽到激勵(lì)機(jī)制中，提出了滿足差分隱私的位置和時(shí)間擾動(dòng)方法；

2)綜合考慮簽到時(shí)間與位置因素，基于擾動(dòng)前后的位置和時(shí)間數(shù)據(jù)，提出一種簽到數(shù)據(jù)質(zhì)量評(píng)估模型；

3)在激勵(lì)機(jī)制中基于簽到數(shù)據(jù)質(zhì)量，設(shè)計(jì)激勵(lì)機(jī)制中返還獎(jiǎng)勵(lì)的計(jì)算方法，既實(shí)現(xiàn)了簽到用戶個(gè)性化隱私保護(hù)，又提高了簽到數(shù)據(jù)的質(zhì)量；

4)仿真實(shí)驗(yàn)表明：所提出的簽到數(shù)據(jù)質(zhì)量評(píng)估模型是合理的，所提出的激勵(lì)機(jī)制在有效保護(hù)用戶隱私的同時(shí)，提高了簽到數(shù)據(jù)的質(zhì)量，而且服務(wù)商的費(fèi)用輸出并沒有明顯增加.

1 系統(tǒng)模型與相關(guān)術(shù)語

1.1 系統(tǒng)模型

為了保護(hù)簽到數(shù)據(jù)中的隱私信息，常用的方法就是對(duì)簽到數(shù)據(jù)進(jìn)行擾動(dòng)，然后將擾動(dòng)的數(shù)據(jù)發(fā)送給簽到服務(wù)商.這樣，服務(wù)商端的攻擊者即使獲取了簽到數(shù)據(jù)，也無法精確地推斷出簽到者的隱私信息.通常對(duì)簽到數(shù)據(jù)的擾動(dòng)越大，對(duì)用戶的隱私保護(hù)程度就越高，但同時(shí)簽到數(shù)據(jù)的質(zhì)量也會(huì)越差.所以簽到數(shù)據(jù)隱私保護(hù)工作通常需要在隱私保護(hù)和簽到數(shù)據(jù)質(zhì)量之間作出判斷.

本文所提出的個(gè)性化隱私保護(hù)簽到系統(tǒng)模型如圖1所示.簽到數(shù)據(jù)的擾動(dòng)是在用戶端App上實(shí)現(xiàn)的，整個(gè)簽到流程分4個(gè)步驟：

1)數(shù)據(jù)擾亂.簽到App依據(jù)用戶的隱私預(yù)算對(duì)簽到數(shù)據(jù)進(jìn)行擾亂，生成擾動(dòng)后的簽到數(shù)據(jù).

2)擾亂數(shù)據(jù)質(zhì)量評(píng)估.簽到App基于真實(shí)簽到數(shù)據(jù)和擾動(dòng)后的簽到數(shù)據(jù)間的差異，對(duì)擾動(dòng)后的簽到數(shù)據(jù)進(jìn)行質(zhì)量評(píng)估.

3)簽到數(shù)據(jù)包發(fā)送.簽到App將質(zhì)量評(píng)估結(jié)果、擾亂后的簽到數(shù)據(jù)打包，發(fā)送給簽到服務(wù)商.

4)服務(wù)商獎(jiǎng)勵(lì).簽到服務(wù)商接收簽到數(shù)據(jù)及簽到數(shù)據(jù)質(zhì)量評(píng)估結(jié)果，依據(jù)簽到數(shù)據(jù)的質(zhì)量，計(jì)算簽到用戶的獎(jiǎng)勵(lì)，這里的獎(jiǎng)勵(lì)可以是獎(jiǎng)金、代金券或積分等.

圖1 基于數(shù)據(jù)質(zhì)量的激勵(lì)機(jī)制系統(tǒng)模型

筆者用隱私預(yù)算來描述用戶的個(gè)性化隱私保護(hù)需求，用戶端的App基于隱私預(yù)算來實(shí)現(xiàn)簽到數(shù)據(jù)的擾動(dòng).位置數(shù)據(jù)擾動(dòng)采用地理不可區(qū)分隱私保護(hù)方法[7].其思想是在一定區(qū)域內(nèi)，攻擊者無法將受保護(hù)用戶與其他用戶區(qū)分出來.例如，圖2中受保護(hù)用戶為用戶1，用戶2是以用戶1為中心、r為半徑的區(qū)域內(nèi)的任意用戶，用戶1與用戶2的歐氏距離為dEuc(L用戶1，L用戶2)，K(L用戶1),K(L用戶2)分別表示用戶1和用戶2真實(shí)位置映射到擾亂后的位置的概率分布，設(shè)該概率分布間的散度距離為dKL(K(L用戶1),K(L用戶2))，如果散度距離越小，那么說明用戶1和用戶2映射到相近位置的概率越大，用戶1和用戶2更加不可區(qū)分.

圖2 地理不可區(qū)分保護(hù)示意圖

1.2 符號(hào)與定義

為了論述方便，本文引入以下符號(hào)(見表1)及相關(guān)定義.

表1 符號(hào)說明

定義1(差分隱私)[12]設(shè)有隨機(jī)算法M，PM為M所有可能的輸出構(gòu)成的集合.對(duì)于任意2個(gè)鄰近數(shù)據(jù)集D,D′及SM(SM?PM)，若算法滿足

Pr[M(D)∈SM]≤exp(ε)×Pr[M(D′)∈SM],

則稱算法M對(duì)數(shù)據(jù)集D提供ε-差分隱私保護(hù)，其中Pr表示概率.

exp(ε)是算法M在2個(gè)鄰近數(shù)據(jù)集上獲得相同輸出的概率比值，它體現(xiàn)了算法M所能夠提供的隱私保護(hù)水平.隱私預(yù)算ε越小，隱私保護(hù)程度越高.

差分隱私是通過在查詢函數(shù)的返回值中加入適量的干擾噪音來實(shí)現(xiàn)的.由于加入噪音過多會(huì)降低結(jié)果的準(zhǔn)確性，過少又無法提供足夠的隱私保護(hù),所以如何確定一個(gè)最優(yōu)的噪聲加入量是差分隱私保護(hù)的關(guān)鍵所在.為此，研究者定義了參數(shù)敏感度，用于確定加入噪音量的大小.

定義2(敏感度)[13]敏感度是差分隱私中控制查詢結(jié)果加入噪音大小的參數(shù)，反映了刪除數(shù)據(jù)集中任一記錄對(duì)查詢結(jié)果產(chǎn)生的最大影響.

定義3(Laplace機(jī)制)[14]給定數(shù)據(jù)集D，設(shè)有函數(shù)f:D→Rh(R為實(shí)數(shù)集，h為數(shù)據(jù)維度)，設(shè)Δf為敏感度，若Y～Lap(Δf/ε)，即Y服從參數(shù)為Δf/ε的Laplace分布，那么隨機(jī)算法M(D)=f(D)+Y滿足ε-差分隱私.

2 簽到數(shù)據(jù)擾亂方法

用戶的簽到數(shù)據(jù)包含時(shí)間信息和位置信息，本文采用Laplace機(jī)制對(duì)簽到數(shù)據(jù)中的時(shí)間和位置進(jìn)行擾動(dòng).

2.1 時(shí)間擾動(dòng)

簽到數(shù)據(jù)中的時(shí)間單位是min，本文采用Laplace機(jī)制對(duì)時(shí)間進(jìn)行擾亂.設(shè)時(shí)間查詢敏感度為60 min，則擾動(dòng)后的時(shí)間數(shù)據(jù)為

tnoisy=treal+Lap(60/ε).

(1)

式(1)中：treal表示簽到的真實(shí)時(shí)間；Lap(60/ε)為L(zhǎng)aplace噪音.

圖3為L(zhǎng)aplace概率分布情況.從圖3可以看出，隱私預(yù)算ε越小，隨機(jī)產(chǎn)生的噪音分布越平穩(wěn)，產(chǎn)生較大噪音的概率也越大.例如，當(dāng)ε=0.8時(shí)，產(chǎn)生的噪音主要分布在[-100,100]，當(dāng)ε=0.2時(shí)，產(chǎn)生的噪音的分布區(qū)間擴(kuò)大了很多.

2.2 位置擾動(dòng)

對(duì)于位置擾動(dòng)，需要考慮地理坐標(biāo)的二維屬性.圖4為以X0=(0,0)為中心點(diǎn)、ε=0.2時(shí)所產(chǎn)生的隨機(jī)位置點(diǎn)X=(x,y)的分布圖.

設(shè)L為某區(qū)域內(nèi)位置集，那么一個(gè)地理擾亂函數(shù)滿足ε-差分隱私當(dāng)且僅當(dāng)

Pr(l*|l1)≤eεd(l1,l2)Pr(l*|l2), ?l1,l2,l*∈L.

(2)

圖3 Laplace概率分布圖 圖4 二維Laplace概率分布圖

式(2)中：Pr(l*|l)是將位置l擾亂成l*的概率；d(l1,l2)代表l1和l2之間的歐氏距離；ε是隱私預(yù)算，ε越小，隱私保護(hù)程度越高.

文獻(xiàn)[12]已證明二維Laplace機(jī)制滿足式(2)，因此本文利用二維Laplace機(jī)制對(duì)用戶的原始位置X0添加噪音，二維Laplace分布為

(3)

式(3)中：X0為用戶的原始位置；X為其他位置點(diǎn).

因?yàn)槎SLaplace的概率密度函數(shù)pdf(probability density function)只與d(X,X0)有關(guān)，因此轉(zhuǎn)化到極坐標(biāo)下計(jì)算噪音值更方便[7].根據(jù)坐標(biāo)之間的轉(zhuǎn)化公式，得到對(duì)原點(diǎn)為X0添加噪音的極坐標(biāo)方程為

(4)

由式(4)可分別得關(guān)于半徑r和角度θ的邊緣密度函數(shù)，分別為：

容易看出,Dε(r,θ)=Dε,R(r)·Dε,Θ(θ).因?yàn)榘霃胶徒嵌仁仟?dú)立的，因此,可分別從Dε,R(r)和Dε，Θ(θ)中獲得隨機(jī)噪音r和θ.

角度噪音θ：因?yàn)镈ε，Θ(θ)是一個(gè)常量，所以直接在均勻分布[0,2π)上產(chǎn)生隨機(jī)數(shù)即可.

半徑噪音r：先求出關(guān)于變量r的累計(jì)分布函數(shù),即

(5)

(6)

式(6)中，W-1叫作蘭伯特W函數(shù).

位置擾亂過程如下：

Input:X0//需要擾亂的用戶位置

ε//用戶的隱私預(yù)算

Output:X//擾亂后需要發(fā)送給簽到服務(wù)商的位置

1.Drawθuniformly in [0,2π)

3.X←X0+〈rcos(θ),rsin(θ)〉 //將位

置X0擾亂成位置X

4.ReturnX

3 簽到數(shù)據(jù)質(zhì)量評(píng)估模型

為了實(shí)現(xiàn)在保護(hù)用戶隱私的基礎(chǔ)上盡可能保證簽到數(shù)據(jù)的質(zhì)量，本文設(shè)計(jì)了基于數(shù)據(jù)質(zhì)量的簽到激勵(lì)機(jī)制，讓服務(wù)商根據(jù)簽到數(shù)據(jù)質(zhì)量獎(jiǎng)勵(lì)用戶.

本文設(shè)計(jì)的數(shù)據(jù)質(zhì)量評(píng)估模型由2部分構(gòu)成，即時(shí)間數(shù)據(jù)質(zhì)量和位置數(shù)據(jù)質(zhì)量.其中:時(shí)間數(shù)據(jù)質(zhì)量可采用時(shí)間相對(duì)誤差來刻畫(見式(7));位置數(shù)據(jù)質(zhì)量可采用位置精度來刻畫(見式(8)).

(7)

式(7)中：tr為簽到用戶簽到的真實(shí)時(shí)間；t為擾動(dòng)后的時(shí)間；T是預(yù)先設(shè)定好的時(shí)間間隔閾值.

(8)

(9)

式(9)中：xl,xlr表示用戶擾亂后位置與實(shí)際位置的橫坐標(biāo)；yl，ylr表示用戶擾亂后位置與實(shí)際位置的縱坐標(biāo).

綜上，簽到數(shù)據(jù)簽到數(shù)據(jù)質(zhì)量定義為

τ=w1·Etime+w2·Elocation.

(10)

式(10)中，w1，w2為權(quán)重，滿足w1+w2=1.

4 實(shí)時(shí)簽到激勵(lì)機(jī)制

本文認(rèn)為服務(wù)商返回用戶簽到活動(dòng)的獎(jiǎng)勵(lì)就是服務(wù)商獲取用戶數(shù)據(jù)的開銷.

為簡(jiǎn)化問題，假設(shè)簽到者的報(bào)酬與數(shù)據(jù)質(zhì)量之間呈線性函數(shù)關(guān)系.若簽到數(shù)據(jù)i的質(zhì)量為ui，那么簽到數(shù)據(jù)i的報(bào)酬ci為

ci=m+F(ui).

(11)

式(11)中：F(·)是由數(shù)據(jù)質(zhì)量映射為報(bào)酬的線性函數(shù)；m表示每一次簽到數(shù)據(jù)給予的基本報(bào)酬，目的是鼓勵(lì)更多的用戶參與簽到.

設(shè)服務(wù)商共收到N個(gè)簽到數(shù)據(jù)，則簽到服務(wù)商花費(fèi)的總開銷為

(12)

式(12)中，ci為返回給第i個(gè)簽到數(shù)據(jù)的獎(jiǎng)勵(lì).

由于每一位用戶的隱私需求不一樣，即隱私預(yù)算不一樣，因此簽到數(shù)據(jù)的擾亂程度也會(huì)不一樣.擾亂程度越低，相應(yīng)的簽到數(shù)據(jù)質(zhì)量越高，則簽到服務(wù)商給予簽到的報(bào)酬也會(huì)越多.

5 仿真實(shí)驗(yàn)分析

本文通過分析杭州POI地址位置數(shù)據(jù)，模擬用戶簽到行為，從個(gè)人激勵(lì)與費(fèi)用輸出2個(gè)方面將文獻(xiàn)[15-16]的結(jié)果與本文提出的激勵(lì)機(jī)制進(jìn)行對(duì)比.

5.1 數(shù)據(jù)集與實(shí)驗(yàn)環(huán)境

采用騰訊提供的API，實(shí)時(shí)爬取杭州市美食、K歌、購(gòu)物、電影、公園、博物館、體育、臺(tái)球、網(wǎng)吧、歌舞廳、景點(diǎn)、會(huì)議宴會(huì)、運(yùn)動(dòng)健身、麗人、結(jié)婚、酒店、愛車、親子、教育培訓(xùn)等所在場(chǎng)所的POI屬性，共3 702條記錄，見表2.模擬用戶總計(jì)14 808簽到數(shù)據(jù)，用戶的簽到數(shù)據(jù)概況見表3.

表2 POI屬性表

表3 簽到數(shù)據(jù)集

注：實(shí)驗(yàn)環(huán)境為：i5-4200M處理器，8 G內(nèi)存，Windows 10操作系統(tǒng)，Python 3.6.2.

5.2 個(gè)人激勵(lì)

圖5展示了隱私預(yù)算與報(bào)酬間的關(guān)系，本實(shí)驗(yàn)對(duì)1 000次簽到數(shù)據(jù)進(jìn)行仿真，從圖5可以看出，本文提出的激勵(lì)機(jī)制中簽到獎(jiǎng)勵(lì)與隱私預(yù)算成正相關(guān).當(dāng)個(gè)人隱私預(yù)算為0時(shí)，位置數(shù)據(jù)已完全失真，簽到者會(huì)獲得一個(gè)基本報(bào)酬m=0.8.隨著隱私預(yù)算的不斷增大，在簽到數(shù)據(jù)中添加的噪音就會(huì)不斷減小，數(shù)據(jù)有用性也會(huì)不斷增大.因此，簽到數(shù)據(jù)的獎(jiǎng)勵(lì)會(huì)不斷增加.基于任務(wù)的激勵(lì)機(jī)制與基于k-匿名的激勵(lì)機(jī)制未考慮用戶的個(gè)性化隱私保護(hù).因此，用戶參與簽到，得到的激勵(lì)值是一個(gè)固定的值.而本文所提出的基于數(shù)據(jù)質(zhì)量的簽到激勵(lì)機(jī)制，服務(wù)商可以收集到更高質(zhì)量的簽到數(shù)據(jù).

圖5 第i次簽到獎(jiǎng)勵(lì)(ci)與隱私預(yù)算(ε)之間的關(guān)系

5.3 成本輸出

圖6展示了簽到服務(wù)商費(fèi)用輸出在3種機(jī)制下收購(gòu)成本的變化情況.從圖6可以看出，隨著收集的簽到數(shù)據(jù)不斷增多，服務(wù)商收購(gòu)成本不斷增加.其中，基于k-匿名的機(jī)制收購(gòu)成本要遠(yuǎn)高于另外2種機(jī)制.任務(wù)積分機(jī)制下的收購(gòu)成本會(huì)少于本文提出的基于數(shù)據(jù)質(zhì)量的激勵(lì)機(jī)制下的收購(gòu)成本，但是它忽略了用戶的個(gè)性化隱私需求.因此，本文提出的機(jī)制在個(gè)性化隱私與成本輸出方面作出了權(quán)衡.

6 結(jié) 語

為滿足用戶個(gè)性化隱私保護(hù)需求，本文將差分隱私方法引入到簽到激勵(lì)機(jī)制中，并通過隱私預(yù)算來量化用戶隱私保護(hù)水平，實(shí)現(xiàn)個(gè)性化的隱私保護(hù).同時(shí)，設(shè)計(jì)了基于數(shù)據(jù)質(zhì)量的獎(jiǎng)勵(lì)策略，提高了簽到數(shù)據(jù)質(zhì)量.實(shí)驗(yàn)表明：融入個(gè)性化隱私保護(hù)的簽到激勵(lì)機(jī)制在保護(hù)用戶隱私的同時(shí)，保證了簽到數(shù)據(jù)的質(zhì)量.

圖6 收購(gòu)成本隨簽到數(shù)據(jù)量N增加的變化趨勢(shì)

由于激勵(lì)用戶參與簽到的因素很多，比如趣味性、競(jìng)爭(zhēng)性等，因此，下一步的工作會(huì)考慮將其他的激勵(lì)因素融入到簽到激勵(lì)機(jī)制中，從而進(jìn)一步優(yōu)化融入個(gè)性化隱私保護(hù)的簽到激勵(lì)機(jī)制.