基于混合相似度和信任傳播的位置推薦系統

戚文博 張曦煌

(江南大學物聯網工程學院 江蘇 無錫 214000)

基于混合相似度和信任傳播的位置推薦系統

戚文博 張曦煌

(江南大學物聯網工程學院 江蘇 無錫 214000)

當前存在大量基于位置推薦的移動社交應用。提出一種基于CF算法的混合相似度和信任傳播位置推薦系統的方案。方案中主要分三個考量要素，首先將用戶偏好分為用戶靜態偏好和用戶動態偏好，對于用戶靜態偏好主要是基于位置的種類信息和歷史評價，而用戶動態偏好主要是基于地理信息和二位云模型，最后用戶的社會關系是基于信任傳播的信息。該方法優勢是不僅考慮用戶偏好的多樣性，而且通過信任傳播可以有效緩解數據稀疏性問題。并應用Hadoop以提高計算平臺的數據處理能力。該方案對比現有方法，基于CF算法的位置推薦預測用戶對新位置的喜好更加準確且高效。

位置推薦 信任傳播 協同過濾 MapReduce

0 引 言

隨著移動互聯網的飛速發展，基于定位的社交和服務類型的應用如雨后春筍般出現。位置推薦不僅僅可以幫助移動用戶及時確定能夠滿足需要的新位置，而且用戶可以通過評分系統得到客觀的評估結果，可以體現出對模糊概念最直觀的感受。位置推薦系統如今已被廣泛應用于為用戶提供及時的滿足個性化需求的信息。

根據文獻[1]，可以將用戶偏好分為靜態偏好和動態偏好。舉例，用戶到地點A吃西餐，西餐被看作用戶的靜態偏好，地點A被看作用戶的動態偏好，而且用戶的動態偏好是由用戶的靜態偏好決定的。如用戶是否要選擇去一個地點吃西餐是由該用戶的周邊環境決定的，如時間、距離等因素。當用戶有多個可選擇的地點，那這些地點可以當作動態偏好。但是位置推薦大部分都是基于標簽的CF算法，沒有考慮到用戶偏好的細節。

根據文獻[2]，地理上接近的位置具有相似的特征。用戶已經訪問的位置可以看成動態偏好，并且用戶動態偏好依賴于靜態偏好。所以如果用戶靜態偏好和已經訪問過的位置是相近的，那么就稱之為相似用戶，幾乎沒有基于這個觀點的位置推薦系統。

根據文獻[3]，在信任網絡中，由于稀疏性問題，部分用戶對項目評分數據很少，與網絡中其他用戶聯系也很少。所以需要根據信任傳播理論，來減少數據稀疏性問題，提高推薦系統的準確率。

云模型是一種處理定性概念與定量描述的不確定轉換模型。移動互聯的數據標定是基于用戶看法，口味和意見，它是主觀的、不嚴密的、模糊的。所以用云模型來處理不確定、模糊的用戶喜好是一種合適的方式。根據文獻[4]，將云模型引入推薦算法，以至提高了相似度計算的覆蓋范圍，但這種方法高估了用戶偏好相似度。

對于上述問題，本文提出了基于混合相似度和信任傳播的位置推薦系統。分別有兩個關鍵性的改進：第一個是我們把用戶偏好分為靜態偏好和動態偏好，第二個是根據信任傳播理論，來減少數據稀疏性問題。首先，本方案利用衰減函數[10]、TF-IDF[6]和信息分類去評估用戶靜態偏好的相似度。另一方面，通過二維云模型導出用戶動態偏好。最后，通過Mole Trust算法[9]得出用戶社會關系相似度，且并行于Hadoop平臺，來滿足移動用戶對于快速響應的需求。

1 相關研究

1.1 基于用戶偏好的協同過濾

許多方法已經被成熟地應用在位置推薦上。例如文獻[6]開發了一種LA-LDA算法導出用戶偏好的新位置。文獻[7]通過隨機游走算法實現位置推薦。文獻[8]通過核密度估算個性化地理因素對用戶行為的影響。在上述方案中，主要利用協同過濾算法。然而大部分基于CF算法的位置推薦是低效的，可能在實時應用場景中失敗。而且很少考慮到用戶偏好的細節，他們只選擇用標簽來定義用戶偏好。因此我們通過從位置分類信息中提取靜態偏好，二維云模型來建模動態偏好，根據信任傳播理論得出社會關系相似度來提高方案的精確度。此外我們將本方案并行在MapReduce框架來提高效率。

1.2 云模型

云模型定義如下：

設U是一個精確值表示的定量論域，C是U上的定性概念，若定量值x∈U，且x是定性概念C的一次隨機實現。x對C的確定度μ(x)∈[0,1]是有穩定傾向的隨機數。

μ：U→[0,1] ?x∈Ux→μ(x)

(1)

x在論域U上的分布稱為云，每一個x稱為一個云滴。定性概念和定量描述之間的轉換被執行在兩個云發生器：正向云發生器(FCG)和逆向云發生器(BCG)。

基于云模型的CF算法可以在數據稀疏的狀況下仍可以得到良好的推薦效果，然而它高估了某對有很少共同點用戶的相似度。此外，一個位置點有經度和緯度兩個屬性，不能用一維BCG模型直接提取位置特點，因此需要應用二維云模型建模用戶動態偏好。

1.3 信任傳播理論

圖1中表示一個簡單信任網絡，每一個節點對應一個用戶，節點與節點之間的連線表示用戶間的信任關系，連線的權重表示信任度。網絡中有6個用戶，用戶1直接信任用戶2、3、4。直接信任度為0.8、0.4、0.2。

圖1 簡單的信任網絡

信任網絡中，由于稀疏性問題，某些用戶具有少量的信任用戶，則對推薦精確度造成很大影響。根據信任傳播理論，假設A信任B，B信任C，那么A在一定程度上也信任C。獲得更多信任用戶，需要通過直接信任用戶的信任關系，得到非直接信任用戶的間接信任度。

2 位置推薦算法

2.1 用戶靜態偏好相似度

用戶可能在不同時間點訪問一個位置許多次，因此首先評估用戶對于歷史訪問記錄的偏好。

計算用戶對歷史訪問位置的偏好。rij代表ui對于歷史訪問地點lj的偏好程度，它被定義為：

(2)

其中，T是用戶ui對地點lj訪問的時間t的集合，rijt是ui在時間點t訪問lj的偏好度。f(t)是衰減函數，如下：

f(t)=e-λ(t0-t)

(3)

其中，t0是當前時間，t是用戶訪問地點的時間。λ是一個可變參數，不同的環境下有不同的值。

計算用戶靜態偏好。pi={pie1,pie2,…,pien}是用戶ui的靜態偏好集合，pie代表用戶ui對地點元素e的靜態偏好，定義如下：

(4)

其中，Lj是用戶ui所訪問的歷史位置的集合，rile是用戶ui對包含元素e的地點l訪問后的喜好程度，Ei是被用戶ui訪問過的按照元素分類后地點的集合。Nu是所有用戶的數量，Nue是訪問過包含e元素地點用戶的數量。

計算用戶靜態偏好相似度。esim(ui,uj)代表用戶ui和uj的靜態偏好相似度，定義如下：

(5)

2.2 用戶動態偏好相似度

用戶是否訪問某個位置取決于其周圍的環境等因素。也就是說，用戶訪問某個地點在一定程度上是隨機的。因此認為歷史訪問記錄可以代表用戶的動態偏好。位置信息有兩個屬性經度和緯度，如果把一個位置點作為云滴，可以通過二維逆向云發生器建模用戶動態偏好[4]。

計算用戶動態偏好相似度，lsim(ui,uj)表示用戶ui和uj的用戶動態偏好相似度，定義為：

(6)

其中Fui=(Flion,Fliat)和Fuj=(Fljon,Fljat)表示用戶ui和uj各自的特征向；Flion=(Exlion,Enlion,Helion)，Fliat=(Exliat,Enliat,Heliat)表示用戶ui動態偏好的的特征向量；Fljon=(Exljon,Enljon,Heljon)和Fljat=(Exljat,Enljat,Heljat)表示用戶uj的動態偏好的特征向量。只考慮用戶動態偏好相似度范圍在[0,1]內。

如果En和He的值相對較小并且Ex的值大于En和He，導致Ex覆蓋了En和He的作用。因此估算基于二維云模型的用戶動態偏好相似度之前應對特征向量進行歸一化處理。

用戶動態偏好基于用戶靜態偏好。只考慮當用戶靜態偏好相似度接近的情況下，估算用戶動態偏好相似度。這樣避免了對用戶動態偏好過高的預期。

2.3 社會關系相似度

用戶的社會關系相似度是基于信任傳播的社交關系和訪問位置的元素。例如，用戶u1和u2的訪問位置是L1={l1,l3,l4}，L2={l2,l3,l7}，l1={e1,e2}，l2={e3,e5}，l3={e1,e4}，l4={e4,e5}，l7={e2,e3}用戶u1和u2訪問的公共位置是l3，用戶u1和u2的共同位置元素是{e1,e2,e4,e5},可以獲得更加精確的用戶的社會關系。

建立用戶信任網絡，我們通過Mole Trust算法得到非直接信任用戶的間接信任度，tuv是用戶u對用戶v的間接信任度，如下：

(7)

在此設置一個閾值θt，把信任度不小于θt的用戶作為用戶u的信任用戶。

T={v|tuv≥θt,v∈U}

(8)

確定社會關系相似度，tsim(ui,uj)表示ui和uj的社會關系相似度，如下：

(9)

其中α是在[0,1]范圍內的調諧參數，Ti和Tj分別是用戶ui和uj各自的的信任關系集，Ei和Ej是用戶ui和uj各自的訪問元素集合。α=1表示用戶社交關系完全取決于共同的信任用戶，否則α=0表示用戶的社交關系完全取決于共同元素。顯然，用戶的社交關系相似度值的范圍在[0,1]內。

應用TOPSIS法來計算參數α的值，方法總結如下：

(1) 假設評估對象數量是m，每個對象的評估因素數量是n。判斷矩陣為：R=(rij)，其中i=1,2,…,m，j=1,2,…,n。

(2) 判斷矩陣R歸一化為B，B的因子為：

(10)

(3) 定義正向理想解A+和負向理想解A-。

A+={max1≤i≤m(bij)|j=1,2,…,n}={1,1,…，1}

A-={min1≤i≤m(bij)|j=1,2,…,n}={0,0,…，0}

(11)

解決方案如下：

(12)

(13)

2.4 用戶對位置的偏好

ur=(ui,uj)表示用戶ui和uj的關系，其結合用戶靜態偏好，用戶動態偏好和社會關系，定義如下：

ur(ui,uj)=β1csim(ui,uj)+β2lsim(ui,uj)+

(1-β1-β2)tsim(ui,uj)

(14)

其中兩個加權參數β1和β2(0≤β1+β2≤1)表示用戶動態偏好相似度和用戶靜態偏好相似度對比用戶社交關系相似度的相對重要性，β1=1表示用戶間關系完全依賴于用戶靜態偏好的相似性;β2=1說明用戶間關系完全取決于用戶動態偏好的相似性;β1=β2=0狀態用戶間關系只計算用戶社交關系相似度。注意參數β1、β2的值取決于TOPSIS方法。

最后pij表示用戶ui對新位置lj的偏好，可以使用基于用戶的CF算法：

(15)

2.5 時間復雜度與MapReduce并行化

位置推薦的關鍵問題是CF算法需要大量計算量。令m和n分別作為用戶數和位置數。|f|是用戶的信任用戶的數量。|esim|是用戶靜態偏好的相似度記錄的數量。|Ln|是對于某個用戶新位置的數量，方案的時間復雜度按算法執行步驟分析如下：

(1) 靜態偏好相似性時間復雜度為O(m2)。

(2) 動態偏好相似性時間復雜度為O(|esim|)。

(3) 社會關系相似性時間復雜度為O(m|f|)。

(4) 用戶對位置偏好時間復雜度為O(m|Ln|)。

因為|f|

對于步驟(1)在Hadoop平臺的并行化，主要研究兩步來計算用戶靜態偏好相似度。第一步找出某對用戶的每一個地點元素。Map1接受一組數據包括用戶信息、位置元素、偏好值，被用戶訪問過的位置元素數量作為輸入，并輸出ui,ex,pix,|eui|，Reduce1接受Map1的輸出，并輸出ex,(u1,u2,p1x,p2x,|eu1|,|eu2|)。第二步程序計算用戶靜態偏好相似度，Map2接受Reduce1的輸出作為輸入，并輸出(u1,u2),(ex,p1x,p2x,|eu1|,|eu2|)。Reduce2接受Map2的輸出，并輸出(u1,u2),csim(u1,u2)，csim(u1,u2)是用戶u1和u2的相似度。|e|是地點元素的個數。Uex是用戶訪問的元素ex的次數。這一步的時間復雜度為O(|e||Uex|2)。因為|e|<

3 實驗及結果分析

3.1 實驗環境

研究本方案的準確性和效率，在Hadoop集群上設置4個節點。一個節點作為命名節點其他三個作為數據節點。節點運行在4 GB內存，Inter Corei5 4590 3.3 GHz處理器和centos 6.5的PC機上。每個節點都可以支持最多2個Map或Reduce任務，需要設定相同數量的Map和Reduce任務。Map和Reduce任務不能同時執行，平臺可以支持6個Map任務和6個Reduce任務。

3.2 數據集

Yelp數據集包括五個部分：商家數據、登錄數據、評論數據、提示數據和用戶數據。主要用到評論數據共1 125 458條記錄，商家數據共42 153條記錄，用戶數據共252 898條記錄。評論數據包含用戶對位置的評級，社會關系包括在用戶數據中，類別信息包含于商家數據中。根據評論時間來分配評論數據集為訓練集和測試集，利用過去的評論數據來預測用戶對位置的偏好。把80%有更早時間戳的評論數據當作訓練集，剩余的評論數據作為測試集。

3.3 性能指標

衡量方案性能，需要用到平均絕對誤差(MAE)、均方根誤差(RMSE)、準確度、召回率、效率、加速比。N1是提取出用戶正確偏好數量，N2是算法預測的用戶偏好數量，N3是測試集中用戶偏好總數量。準確度和召回率被定義為：

(16)

加速比定義為：

(17)

n是節點數量，T1是單節點順序執行的時間，Tn是n個節點并行執行的時間。當Sn=n時獲得理想加速比。

效率表示每個節點的加速比：

(18)

當En=1時獲得理想效率。

3.4 結果分析

(1) 精度評估

如第2節所述，參數λ(式(3)中)、σ(式(5)中)、α、1-α(式(7)中)、β1、β2、1-β1-β2(式(12)中)可以用來調優方案的性能。而α、1-α、β1、β2、1-β1-β2隨著λ和σ的變化而變化，給出λ和σ的值，α、1-α、β1、β2、1-β1-β2是可以由TOPSIS和實驗數據集來確定。因此我們調優λ和σ以找到它們的最優值。

設置λ= 0.01，在0.1～0.8范圍內調優σ。RMSE和MAE結果如圖1所示。設置σ=0.55并且在0.01～0.08范圍內調優λ， RMSE和MAE結果如圖3所示。

圖2 通過RMSE與MAE調優σ

圖3 通過RMSE與MAE調優λ

從圖2和圖3，可以看到調整方案精度需要改變σ從0.1至0.8改變且λ從0.01至0.08變化。如圖2，λ= 0.01是固定的，我們得到最低點的RMSE和MAE分別為σ= 0.6和σ= 0.4。在圖3中，如果給定σ= 0.55，調優λ從0.01到0.08，得到當λ=0.02時方案的最佳RMSE和MAE。

同時調優λ和σ并找到它們的最優設置是：λ= 0.02，σ= 0.65，通過TOPSIS方法得到α= 0.568，1-α= 0.432和β1= 0.417，β2=0.294,1-β1-β2=0.289。根據實驗結果，可以得出評估社會關系時共同的信任用戶比共同的位置元素發揮更重要的作用。對于精確度方面用戶靜態偏好起到主導作用，但用戶動態偏好和社會關系對于其影響也是不可忽視的。

針對位置推薦的準確度和召回率，本方案USDTCF算法與基于位置聚類LCR算法[9]、基于用戶活動和社交信任LRBTA算法[5]進行比較，結果如圖4、圖5所示。

圖4 USDTCF算法準確率比較

圖5 USDTCF算法召回率比較

比較結果可知USDTCF算法綜合考慮了用戶動態偏好、用戶靜態偏好并基于信任傳播理論考慮用戶的社會關系，而FRBTA算法只考慮了用戶單一偏好及用戶間多種信任，LCR算法只考慮同一聚類下的其他地點進行推薦，并未考慮地點的分類元素和不同用戶間的影響。USDTCF算法在準確率和召回率兩個衡量標準上均優于LCR算法和LRBTA算法。

(2) 效率評估

驗證并行在Mapreduce框架上的效率，Yelp數據集中取出4份用戶評分副本作為實驗數據集，包括的記錄數為100、1 000、10 000和100 000。圖6和圖7為4種情況并行加速比和效率。

圖6 MapReduce并行后加速比統計

圖7 MapReduce并行后效率統計

從圖6可以看出加速比的提高是和數據節點數量相關的，且數據集越大結果越接近理想加速比。從圖7可以看出數據節點數增加則效率降低，且數據集越大結果越高效。實驗結果表明并行在Mapreduce框架下對加速比和效率有重要影響。

4 結 語

通過對傳統協同過濾進行改進得到基于混合相似度和信任傳播的位置推薦算法。將用戶偏好分為靜態和動態兩方面，并采用位置元素和二維云模型分別進行兩次計算。其次基于信任傳播理論運用Mole Trust算法計算出用戶社會關系相似度。然后將用戶靜態偏好相似度、動態偏好相似度和社會關系相似度整合到CF算法中。最后并行在Hadoop平臺上。實驗部分也證明了USDTCF算法在各項指標中的結果。更進一步的工作是探索更加詳盡的分類信息來預測用戶對于位置的偏好，從而提高準確率。

[1] Meng X W, Wang F, Shi Y C, et al. Mobile user requirements acquisition techniques and their applications[J]. Journal of Software, 2014,47(4):1261-1263.

[2] Tobler W R. A Computer Movie Simulating Urban Growth in the Detroit Region[J].Economic Geography,1970,46(Supp 1):234-240.

[3] Lai C H, Liu D R, Lin C S. Novel personal and group-based trust models in collaborative filtering for document recommendation[J]. Information Sciences, 2013,239(1):31-49.

[4] Wang G, Xu C, Li D. Generic normal cloud model[J]. Information Sciences, 2014,280(280):1-15.

[5] 于亞新, 李玉龍, 劉欣,等. LBSNs中基于用戶活動和社交信任的好友及位置推薦算法[J]. 小型微型計算機系統, 2014,35(10):2262-2266.

[6] Yin H, Cui B, Chen L, et al. Modeling Location-Based User Rating Profiles for Personalized Recommendation[J]. Acm Transactions on Knowledge Discovery from Data, 2015,9(3):1-41.

[7] Mourchid F, Koutbi M E, Wang J. LBRW: A Learning based Random Walk for Recommender Systems[J]. International Journal of Information Systems & Social Change, 2015, 6(3):15-34.

[8] Ye M, Yin P, Lee W C, et al. Exploiting geographical influence for collaborative point-of-interest recommendation[C]//International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, 2011:325-334.

[9] Zhang J D, Chow C Y, Li Y. CoRe: Exploiting the personalized influence of two-dimensional geographic coordinates for location recommendations[J].Information Sciences,2015, 293:163-181.

[10] Zhang Y F， Zhang M， Liu Y Q， et al.Localized matrix factorization for recommendation based on matrix block diagonal forms[C]//Proc of the 22nd International Conference on World Wide Web,2013:1511-1520.

[11] Ortega F，Bobadilla J，Hemando A，et a1.Incorporating Group Recommendations to Recommender Systems:Alternatives and Perfornance[J].Information Processing and Management,2013,49(4):895-901.

[12] Sheng B, Sun H Q, Magnor M, et al. Video colorization using parallel optimization in feature space[J]. IEEE Transactions on Circuits and Systems for Video Technology,2014,24(3):407-417.

LOCATIONRECOMMENDATIONSYSTEMBASEDONHYBRIDSIMILARITYANDTRUSTPROPAGATION

Qi Wenbo Zhang Xihuang

(SchoolofInternetofThingsEngineering,JiangnanUniversity,Wuxi214000,Jiangsu,China)

Nowadays there are a large number of mobile social applications based on location recommendation. This paper proposes a method to provide a hybrid similarity and trust propagation location recommendation system based on CF algorithm. The scheme consists of three elements, and the user preference is divided into user static preferences and user dynamic preferences. Static user preference is mainly type information and historical evaluation based on the location, and the dynamic user preference is based on geographic information and two-dimensional cloud model. The users’ social relationship is based on the information that is propagated by trust. The advantage of this method is that not only the diversity of user preferences is considered, but also the data sparseness can be effectively alleviated by trust propagation. And apply Hadoop to improve the data processing ability of computing platform. Compared with the existing methods, the proposed location recommendation based on CF algorithm is more accurate and efficient to predict the users’ preferences for new locations.

Location recommendation Trust propagation Collaborative filtering MapReduce

TP391

A

10.3969/j.issn.1000-386x.2017.09.020

2016-12-19。戚文博，碩士生，主研領域：計算機應用技術。張曦煌，教授。