DPLORE：一種差分隱私保護(hù)位置推薦算法

楊達(dá)森

（廣東工業(yè)大學(xué) 計(jì)算機(jī)學(xué)院，廣東 廣州510006）

隨著移動(dòng)設(shè)備的發(fā)展，最新一代的移動(dòng)設(shè)備允許用戶連接到地理社交網(wǎng)絡(luò)服務(wù)中，讓用戶分享他們?cè)谠L問(wèn)特定地點(diǎn)時(shí)的親身體驗(yàn)。用戶分享的位置隱私數(shù)據(jù)常常被用于分析、統(tǒng)計(jì)和挖掘。這些有價(jià)值的隱私數(shù)據(jù)受到互聯(lián)網(wǎng)等領(lǐng)域研究者的關(guān)注，特別是在位置推薦領(lǐng)域。然而，當(dāng)前面臨的挑戰(zhàn)是如何保護(hù)用戶的位置數(shù)據(jù)的同時(shí)保證位置推薦的準(zhǔn)確度。直接向不可信推薦系統(tǒng)發(fā)布用戶歷史訪問(wèn)位置會(huì)導(dǎo)致嚴(yán)重的位置隱私泄露問(wèn)題。

用戶簽到的歷史位置可以揭示個(gè)人出行或生活方式等敏感細(xì)節(jié)。目前，位置推薦算法有協(xié)同過(guò)濾技術(shù)[1]、序列技術(shù)[2]等。協(xié)同過(guò)濾技術(shù)也可與其他信息相結(jié)合[3]，例如用戶與社交朋友地理坐標(biāo)之間的聯(lián)系。由于社交朋友更容易分享共同的興趣，因此社交鏈接信息被廣泛用于測(cè)量用戶之間的相似性，結(jié)合協(xié)同過(guò)濾技術(shù)可以提高位置推薦的精度。目前研究工作從用戶的簽到位置序列中提取序列模式，利用全局或個(gè)人馬爾可夫模型分別挖掘用戶運(yùn)動(dòng)的全局行為和個(gè)體模式信息，并根據(jù)過(guò)去的位置序列預(yù)測(cè)用戶可能感興趣的位置。而n-階馬爾可夫模型[4]通過(guò)統(tǒng)計(jì)用戶訪問(wèn)每個(gè)地點(diǎn)的頻次，然后計(jì)算每個(gè)位置被訪問(wèn)的概率作為轉(zhuǎn)移概率矩陣，并在轉(zhuǎn)移概率矩陣上使用馬爾可夫鏈生成位置推薦結(jié)果。雖然馬爾可夫模型在位置推薦中應(yīng)用很廣泛，但在計(jì)算地點(diǎn)訪問(wèn)頻次以及求概率時(shí)都有可能泄露用戶的隱私，如果直接發(fā)布馬爾可夫模型容易泄露敏感信息。

現(xiàn)有的幾種技術(shù)部分解決了位置隱私泄露問(wèn)題。第一種位置隱私保護(hù)方法是k-匿名[5]。k-匿名技術(shù)確保每個(gè)發(fā)布的位置必須與其他k?1位置不可區(qū)分。如k-匿名的擴(kuò)展模型LK-匿名隱私保護(hù)方法[6]，在公開(kāi)的軌跡數(shù)據(jù)庫(kù)中LK-匿名隱私保護(hù)要求每一個(gè)位置序列的最大長(zhǎng)度L至少與K條記錄不可區(qū)分。雖然這種類型的轉(zhuǎn)換既快又簡(jiǎn)單，但極易受背景知識(shí)攻擊。第二種方法是差分隱私保護(hù)。針對(duì)k-匿名易受背景知識(shí)的攻擊者攻擊，Dwork等[7]提出差分隱私保護(hù)模型，差分隱私是一種通過(guò)向查詢或分析結(jié)果中適當(dāng)添加噪聲來(lái)達(dá)到隱私保護(hù)效果的方法，并且嚴(yán)格定義量化評(píng)估的方法。因此攻擊者不能以偶然的概率得知某個(gè)個(gè)體的信息是否包括在數(shù)據(jù)集中，保護(hù)了用戶的位置隱私，同時(shí)仍然可以利用關(guān)于數(shù)據(jù)的噪聲統(tǒng)計(jì)結(jié)果來(lái)進(jìn)行數(shù)據(jù)挖掘。Kellaris等[8]提出了分組與平滑算法(Grouping and Smoothing,GS)，一種通過(guò)細(xì)粒度分組和平滑平均預(yù)處理計(jì)數(shù)的方法，通過(guò)初步擾動(dòng)的形式，降低了敏感度，使得GS算法能夠通過(guò)較低的拉普拉斯噪聲注入實(shí)現(xiàn)ε-差分隱私。對(duì)于發(fā)布高維度數(shù)據(jù)集問(wèn)題，Day等[9]提出一種基于敏感度控制的差分隱私數(shù)據(jù)集統(tǒng)計(jì)信息發(fā)布方法(Differential Privacy Sensitivity,DPSS)。鮮征征等[10]提出差分隱私與協(xié)同過(guò)濾結(jié)合的算法(Differential Privacy Singular and Output,DPSAOut++)來(lái)保護(hù)用戶隱私，最后向用戶推薦其感興趣的項(xiàng)目。

針對(duì)位置推薦中隱私保護(hù)的問(wèn)題，本文提出基于自適應(yīng)權(quán)重的n-馬爾可夫鏈的差分隱私位置推薦算法模型。該模型不僅可以防止任意背景知識(shí)攻擊者的攻擊，還在保護(hù)用戶位置隱私的同時(shí)保證了位置推薦的準(zhǔn)確度。相對(duì)于已有的研究，算法模型分配的隱私預(yù)算更加合理，同時(shí)向用戶提供個(gè)性化的位置推薦，提高了位置推薦的精度。最后，在兩個(gè)公開(kāi)數(shù)據(jù)集上進(jìn)行實(shí)驗(yàn)，相比GS算法、DPSS算法和DPSAOut++算法，從推薦結(jié)果方面，本文提出的差分隱私位置推薦模型表現(xiàn)出了更好的實(shí)驗(yàn)效果。

1 相關(guān)工作

1.1 差分隱私位置推薦

近年來(lái)，研究者對(duì)位置推薦算法進(jìn)行了大量研究?；趨f(xié)同過(guò)濾的思想，Noulas等[11]通過(guò)提取用戶信息中地理位置的類型、時(shí)間戳、用戶移動(dòng)方向等特征結(jié)合監(jiān)督學(xué)習(xí)模型向用戶推薦下一時(shí)刻可能感興趣的地點(diǎn)。文獻(xiàn)[12]通過(guò)考慮地理和時(shí)間屬性對(duì)用戶訪問(wèn)下一地點(diǎn)的影響，提出一種混合的矩陣分解方法，以實(shí)現(xiàn)受歡迎地點(diǎn)的推薦。Lu等[13]揭示了用戶對(duì)地點(diǎn)訪問(wèn)的決策依賴于多個(gè)因素，因此設(shè)計(jì)了一個(gè)綜合考慮各種因素的推薦結(jié)果的地點(diǎn)推薦框架。這些方法主要分析用戶與地理位置之間的關(guān)系，缺乏對(duì)語(yǔ)義信息以及用戶本身偏好的考慮。

在為用戶提供推薦服務(wù)的同時(shí)，可能會(huì)出現(xiàn)用戶隱私泄露的情況。因此，位置推薦系統(tǒng)需要保護(hù)用戶個(gè)人隱私的同時(shí)，向用戶提供個(gè)性化推薦服務(wù)。文獻(xiàn)[14-15]利用ε-差分隱私將隨機(jī)噪聲添加到用戶的簽到位置的統(tǒng)計(jì)數(shù)據(jù)中，并且只向位置推薦系統(tǒng)發(fā)布這些噪聲統(tǒng)計(jì)數(shù)據(jù)。GS和DPSS算法雖然可以處理在高度敏感的數(shù)據(jù)上發(fā)布大量統(tǒng)計(jì)數(shù)據(jù)的問(wèn)題，但是對(duì)于一些具有大量統(tǒng)計(jì)數(shù)據(jù)值小的結(jié)果，例如，用戶位置簽入轉(zhuǎn)移計(jì)數(shù)，它們添加的噪聲嚴(yán)重降低了數(shù)據(jù)的可用性。

在差分隱私位置推薦算法研究中，Liu等[16]將差分隱私結(jié)合協(xié)同過(guò)濾推薦技術(shù)，實(shí)驗(yàn)表明在沒(méi)有嚴(yán)重?fù)p失推薦準(zhǔn)確率的情況下可以向用戶提供個(gè)性化推薦，但算法未能考慮到潛在因子模型。Li等[17]針對(duì)用戶興趣點(diǎn)的推薦，將原始位置序列數(shù)據(jù)轉(zhuǎn)為二部圖,然后提取二部圖中的關(guān)聯(lián)矩陣，通過(guò)向矩陣元素中添加噪聲以滿足ε-差分隱私保證。雖然保護(hù)了用戶的位置數(shù)據(jù)隱私，但算法向用戶推薦的是粗粒度的位置區(qū)域，不是具體的位置地點(diǎn)。文獻(xiàn)[18]基于不同用戶的位置信息特征，提出一種個(gè)性化的位置推薦，將用戶的特征分為隱私保護(hù)信息和非隱私保護(hù)信息兩類，使得一部分具有隱私泄露風(fēng)險(xiǎn)的用戶信息得到保護(hù)，而不具風(fēng)險(xiǎn)的信息則主要用于提高推薦的準(zhǔn)確率。

差分隱私位置推薦研究的難點(diǎn)在于位置域維度高，數(shù)據(jù)稀疏，精準(zhǔn)、個(gè)性化推薦難度大，雖然保護(hù)了用戶隱私，但是導(dǎo)致最后向用戶推薦位置的效果不佳。本文基于馬爾可夫模型，提出基于差分隱私的自適應(yīng)權(quán)重n-階馬爾可夫鏈位置推薦算法。算法對(duì)所有用戶原位置計(jì)算轉(zhuǎn)移計(jì)數(shù)矩陣，針對(duì)算法中矩陣維度大、稀疏的問(wèn)題，本文采用奇異值分解(Singular Value Decomposition,SVD)矩陣分解的方法分解轉(zhuǎn)移計(jì)數(shù)矩陣，然后利用差分隱私向分解后的矩陣添加拉普拉斯噪聲，保護(hù)用戶的隱私，最后結(jié)合自適應(yīng)權(quán)重n-階馬爾可夫鏈位置推薦算法向用戶提供個(gè)性化的推薦。

1.2 理論基礎(chǔ)

1.2.1 馬爾可夫鏈

2 算法框架描述及分析

本文提出的差分隱私保護(hù)位置推薦算法框架DPLORE分為差分隱私保護(hù)模塊和位置推薦模塊。對(duì)原始用戶位置簽到數(shù)據(jù)計(jì)算其轉(zhuǎn)移計(jì)數(shù)，然后向統(tǒng)計(jì)數(shù)據(jù)提供差分隱私保護(hù)。將已受保護(hù)的噪聲轉(zhuǎn)移計(jì)數(shù)作為位置推薦系統(tǒng)輸入，利用自適應(yīng)權(quán)重n-階馬爾可夫鏈算法向用戶推薦其感興趣的位置。在最后的位置推薦實(shí)驗(yàn)結(jié)果中，算法能夠在不失準(zhǔn)確率和召回率的情況下保護(hù)用戶的位置隱私。

2.1 算法框架描述

2.2 算法實(shí)現(xiàn)細(xì)節(jié)

算法2根據(jù)噪聲轉(zhuǎn)移計(jì)數(shù)矩陣，計(jì)算轉(zhuǎn)移概率TP，結(jié)合用戶u的歷史位置序列信息向用戶推薦得分前k高的新位置。首先，對(duì)于用戶下一個(gè)可能感興趣位置ln的選擇與用戶的簽到歷史位置相關(guān)，tp為用戶從位置lu訪問(wèn)ln的概率，即lu→ln的轉(zhuǎn)移概率為tp，因?yàn)槊恳粋€(gè)歷史位置對(duì)ln的選擇影響大小不同，即lu→ln的概率值的相關(guān)系數(shù)不是每次相等的，實(shí)際情況中，最后幾次的歷史訪問(wèn)位置與下一個(gè)感興趣位置點(diǎn)的相關(guān)系數(shù)更大，因此需要對(duì)其分配更大的權(quán)重系數(shù)，以提高推薦效果的精度。算法中自適應(yīng)權(quán)重為 2?α(|Su|?j)，其中α 為衰減率參數(shù)。算法最后向用戶返回得分前k高的新位置。

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

3.1 實(shí)驗(yàn)設(shè)置

本文提出的算法使用Python實(shí)現(xiàn)，本節(jié)中所有實(shí)驗(yàn)的硬件環(huán)境為Intel(R)Core(TM)i7 2.70 GHz，內(nèi)存為8 GB。采用2個(gè)不同規(guī)模的公開(kāi)數(shù)據(jù)集，分別是Foursquare、Brightkite來(lái)驗(yàn)證算法的有效性。首先對(duì)原始數(shù)據(jù)進(jìn)行預(yù)處理，過(guò)濾地點(diǎn)在數(shù)據(jù)集中出現(xiàn)少于5次的數(shù)據(jù)，過(guò)濾數(shù)據(jù)集中用戶簽到位置數(shù)量少于10次的用戶，以及用戶在同一時(shí)間連續(xù)在同一位置進(jìn)行簽到的異常數(shù)據(jù)，最后保留的數(shù)據(jù)集的基本統(tǒng)計(jì)信息如表1所示。

表1 數(shù)據(jù)集的基本統(tǒng)計(jì)信息Table 1 Basic statistics of dataset

3.2 實(shí)驗(yàn)結(jié)果評(píng)估指標(biāo)

一般來(lái)說(shuō)，位置推薦算法通過(guò)計(jì)算每個(gè)候選位置對(duì)目標(biāo)用戶的得分，并將得分最高的前k個(gè)位置作為推薦結(jié)果返回給目標(biāo)用戶。為了評(píng)估位置推薦的效果，重要的是找出目標(biāo)用戶在測(cè)試數(shù)據(jù)集中實(shí)際訪問(wèn)了多少位置。因此，本文利用準(zhǔn)確率和召回率作為評(píng)價(jià)差分隱私保護(hù)的位置推薦算法的效用，其值越大，表明結(jié)果越好。

準(zhǔn)確率的定義為，給出目標(biāo)用戶的得分前k高的位置推薦結(jié)果與對(duì)于用戶測(cè)試位置數(shù)據(jù)的交集數(shù)量與k的比值。用式(6)表示，其中Sr為推薦的結(jié)果集合，St為目標(biāo)用戶的測(cè)試數(shù)據(jù)集合。

3.3 結(jié)果分析

在實(shí)驗(yàn)中，每個(gè)數(shù)據(jù)集將依據(jù)用戶簽入時(shí)間順序劃分為訓(xùn)練集和測(cè)試集，一半具有較早時(shí)間戳的簽入數(shù)據(jù)作為訓(xùn)練集，另一半簽入數(shù)據(jù)作為測(cè)試集。在向用戶推薦的位置數(shù)k對(duì)實(shí)驗(yàn)結(jié)果的影響中，實(shí)驗(yàn)參數(shù)設(shè)置方面，將k設(shè)在2到22的區(qū)間范圍。默認(rèn)情況下，總隱私預(yù)算ε 為0.1，其中ε =ε1+ε2+ε3，ε1:ε2:ε3=2:1:2，衰減率參數(shù)α 為0.5，實(shí)驗(yàn)對(duì)比GS算法、DPSS算法和DPSAOut++算法，GS算法是一種通過(guò)細(xì)粒度分組和平滑平均預(yù)處理計(jì)數(shù)降低敏感度來(lái)實(shí)現(xiàn)ε-差分隱私的方法。DPSS是一種敏感度可控的差分隱私高維度數(shù)據(jù)集統(tǒng)計(jì)信息發(fā)布方法。DPSAOut++是SVD++算法結(jié)合差分隱私，對(duì)輸出結(jié)果進(jìn)行擾動(dòng)的隱私保護(hù)算法。對(duì)比實(shí)驗(yàn)結(jié)果如下。

圖1是本文提出的算法DPLORE與3種不同算法在兩個(gè)不同的數(shù)據(jù)集，不同的位置推薦數(shù)k下的準(zhǔn)確率和召回率的結(jié)果。可以看出，在2個(gè)不同的數(shù)據(jù)集下，隨著k的增加，4個(gè)算法的準(zhǔn)確率都在降低，而召回率都在提高。一般來(lái)說(shuō)，通過(guò)為用戶返回更多的位置，它總是能夠發(fā)現(xiàn)用戶希望訪問(wèn)的更多位置。然而，由于這些位置的訪問(wèn)概率較低，額外推薦的位置不太可能被用戶喜歡。但本文提出的算法DPLORE準(zhǔn)確率和召回率在大多數(shù)情況下優(yōu)于其他3個(gè)對(duì)比算法。

圖1 不同k 下的準(zhǔn)確率和召回率Fig.1 Precision and recall under different k

圖2是2個(gè)數(shù)據(jù)集在不同的隱私預(yù)算下，本文提出的算法DPLORE與3種不同算法的準(zhǔn)確率和召回率的對(duì)比實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)中位置推薦數(shù)k設(shè)為10，隨著隱私預(yù)算的增加，4個(gè)算法的準(zhǔn)確率和召回率都在提高，因?yàn)殡[私預(yù)算越大，數(shù)據(jù)隱私保護(hù)的力度越小，總添加的噪聲越小，所以準(zhǔn)確率和召回率越高。本文的算法在不失準(zhǔn)確率和召回率的情況下提供了更好的差分隱私保護(hù)。

圖2 不同隱私預(yù)算ε 下的準(zhǔn)確率和召回率Fig.2 Precision and recall under different ε

圖3描述了衰減率參數(shù)α 的取值對(duì)算法準(zhǔn)確率和召回率的影響。當(dāng)參數(shù) α在0.25到1.0之間時(shí)，本文提出的算法結(jié)果變化相對(duì)穩(wěn)定，可以在這個(gè)區(qū)間選擇一個(gè)合適的值，而不是找到最優(yōu)值來(lái)避免算法過(guò)度擬合，使得算法推薦結(jié)果的準(zhǔn)確率和召回率在可接受的范圍。而當(dāng)參數(shù) α不在這個(gè)區(qū)間時(shí)，算法的準(zhǔn)確率和召回率明顯降低。這是因?yàn)椋?α值大，算法過(guò)度地認(rèn)為最近訪問(wèn)的地點(diǎn)就是用戶感興趣的地點(diǎn)，低估了過(guò)去訪問(wèn)地點(diǎn)會(huì)影響用戶下一個(gè)感興趣點(diǎn)的選擇。然而， α值小容易對(duì)所有歷史訪問(wèn)的地點(diǎn)進(jìn)行同等的看待，最終影響推薦的結(jié)果。

圖3 衰減率α 對(duì)準(zhǔn)確率和召回率的影響Fig.3 Effect of decay rate αon precision and recall

4 結(jié)論

本文提出基于差分隱私的位置推薦算法DPLORE，目的是為了提高位置推薦的準(zhǔn)確率和召回率的同時(shí)保護(hù)用戶的位置隱私。本文的算法通過(guò)改進(jìn)噪聲的添加方式，在同等隱私預(yù)算下，向分解后的轉(zhuǎn)移計(jì)數(shù)矩陣添加的噪聲量更少，在推薦算法模塊中，使用改進(jìn)的自適應(yīng)權(quán)重的n-階馬爾可夫鏈模型，在Foursquare、Brightkite數(shù)據(jù)集上的實(shí)驗(yàn)結(jié)果表明，該算法能夠在保護(hù)用戶位置隱私的同時(shí)，仍然保證位置推薦的準(zhǔn)確率和召回率。下一步嘗試將本文的算法應(yīng)用在交通軌跡數(shù)據(jù)領(lǐng)域，為其他領(lǐng)域的數(shù)據(jù)提供差分隱私保護(hù)機(jī)制，以保護(hù)數(shù)據(jù)隱私等問(wèn)題。