楊達森

（廣東工業(yè)大學 計算機學院，廣東 廣州510006）

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

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

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

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

1 相關工作

1.1 差分隱私位置推薦

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

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

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

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

1.2 理論基礎

1.2.1 馬爾可夫鏈

2 算法框架描述及分析

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

2.1 算法框架描述

2.2 算法實現(xiàn)細節(jié)

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

3 實驗結果分析

3.1 實驗設置

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

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

3.2 實驗結果評估指標

一般來說，位置推薦算法通過計算每個候選位置對目標用戶的得分，并將得分最高的前k個位置作為推薦結果返回給目標用戶。為了評估位置推薦的效果，重要的是找出目標用戶在測試數(shù)據(jù)集中實際訪問了多少位置。因此，本文利用準確率和召回率作為評價差分隱私保護的位置推薦算法的效用，其值越大，表明結果越好。

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

3.3 結果分析

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

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

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

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

圖2 不同隱私預算ε 下的準確率和召回率Fig.2 Precision and recall under different ε

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

圖3 衰減率α 對準確率和召回率的影響Fig.3 Effect of decay rate αon precision and recall

4 結論

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