融入個性化隱私保護的簽到激勵機制*

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

(1.浙江師范大學(xué) 數(shù)學(xué)與計算機科學(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í)慣，這對潛在客戶的識別和精準化營銷具有重要意義.因此，商家會著力研究如何激勵用戶參與簽到活動[1].現(xiàn)有的簽到激勵機制多采取集中式方案[2-6]，由中心服務(wù)器負責(zé)執(zhí)行激勵機制，通過返給簽到用戶一定的獎勵來激勵用戶持續(xù)參加簽到活動.

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

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

1)將差分隱私方法引入到簽到激勵機制中，提出了滿足差分隱私的位置和時間擾動方法；

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

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

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

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

1.1 系統(tǒng)模型

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

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

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

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

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

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

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

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

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

1.2 符號與定義

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

表1 符號說明

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

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

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

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

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

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

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

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

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

2.1 時間擾動

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

tnoisy=treal+Lap(60/ε).

(1)

式(1)中：treal表示簽到的真實時間；Lap(60/ε)為Laplace噪音.

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

2.2 位置擾動

對于位置擾動，需要考慮地理坐標的二維屬性.圖4為以X0=(0,0)為中心點、ε=0.2時所產(chǎn)生的隨機位置點X=(x,y)的分布圖.

設(shè)L為某區(qū)域內(nèi)位置集，那么一個地理擾亂函數(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ù)算，ε越小，隱私保護程度越高.

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

(3)

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

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

(4)

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

容易看出,Dε(r,θ)=Dε,R(r)·Dε,Θ(θ).因為半徑和角度是獨立的，因此,可分別從Dε,R(r)和Dε，Θ(θ)中獲得隨機噪音r和θ.

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

半徑噪音r：先求出關(guān)于變量r的累計分布函數(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ì)量評估模型

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

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

(7)

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

(8)

(9)

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

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

τ=w1·Etime+w2·Elocation.

(10)

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

4 實時簽到激勵機制

本文認為服務(wù)商返回用戶簽到活動的獎勵就是服務(wù)商獲取用戶數(shù)據(jù)的開銷.

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

ci=m+F(ui).

(11)

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

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

(12)

式(12)中，ci為返回給第i個簽到數(shù)據(jù)的獎勵.

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

5 仿真實驗分析

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

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

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

表2 POI屬性表

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

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

5.2 個人激勵

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

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

5.3 成本輸出

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

6 結(jié) 語

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

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

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