基于均衡接近度增強時間的興趣點推薦模型

陳江美，張岐山，張文德，何 瓏

1(福州大學 經濟與管理學院，福州 350108) 2(福州大學 信息管理研究所，福州 350108) 3(福州大學 網絡與信息化建設辦公室，福州 350108)

1 引 言

隨著智能終端設備的普及和定位技術的發展，人們更加容易地獲得實時的位置信息，基于位置的社交網絡(location-based social network,LBSN)應運而生[1].在LBSN中，用戶根據個人喜好選擇興趣相投的興趣點(point-of-interest，POI)，并以“簽到”的方式與朋友分享他們感興趣的興趣點.興趣點推薦增強了用戶的個性化體驗，如何幫助用戶從大量的興趣點中挖掘出他們喜歡的地點不斷引起學術界的關注，成為了推薦領域研究的熱點.

目前，大多數的研究[2-4]主要利用用戶的歷史簽到記錄并融合相關的上下文信息(如地理信息、社交信息等)進行推薦.為了進一步了解用戶的移動行為，少數學者將時間融入興趣點推薦領域中，但推薦精度有待提高，同時現存的研究仍面臨一些挑戰.首先，LBSN中的每個用戶僅簽到有限個興趣點，用戶簽到矩陣極其稀疏，若根據時間劃分用戶偏好矩陣，會造成更嚴重的數據稀疏問題.其次，大多數用戶在一天中的不同時間有不同的簽到偏好，例如中午去餐館，晚上去商場，如何更好地建模時間影響是一大難點.最后，LBSN中存在大量的異構信息，這些信息對興趣點推薦的性能發揮著不同程度的影響，如何有效融合這些信息值得關注.

針對以上問題，本文提出了一種基于均衡接近度增強時間的興趣點推薦模型(GB-TSP).首先，本文將時間因素融入基于用戶的協同過濾算法中，用均衡接近度方法度量時間相似度，獲得時間影響模型.其次，將時間流行度與地理影響結合，獲得空間影響模型.綜合考慮上述時空的影響，為每個用戶學習到一組興趣點并將其填充進矩陣，有效地緩解了數據稀疏性.最后，考慮時間影響，將填充后的矩陣通過矩陣分解得到最終的偏好預測矩陣，進而完成推薦.具體地，本文的創新主要體現在以下三個方面：

1)考慮合并時間的簽到矩陣極其稀疏，用均衡接近度的方法度量時間相似度，進而平滑用戶間的相似度，構建融合均衡接近度的時間影響模型.

2)采用矩陣填充的方式，通過增加簽到數據記錄來有效緩解數據稀疏的影響.再通過矩陣分解獲得用戶偏好預測矩陣，實現實時推薦.

3)有效地建模時間因素、地理位置因素和興趣點的時間流行度的影響，并將時間因素有效地融入基于用戶的協同過濾算法和矩陣分解算法中.

2 相關工作

2.1 興趣點推薦的相關研究現狀

興趣點推薦是一種基于情景信息的感知推薦，主要通過用戶簽到數據并融合相關情景信息來完成推薦工作.目前，基于地理位置的興趣點推薦研究較為成熟.相關學者提出一些經典的模型，如USG[5]、iGSLR[6]、GeoMF[7]等.USG模型將地理和社交信息融入基于用戶的協同過濾框架中，并采用冪律分布建模地理因素，但人為地賦予用戶統一的空間先驗分布無法滿足用戶個性化的偏好.iGSLR模型采用核密度估計分布來建模地理影響，一定程度上滿足了用戶個性化的需求.但由于采用簡單的線性融合方法建模用戶的簽到行為，導致推薦效果不佳.據此，文獻[7]提出將地理信息嵌入加權矩陣分解算法中，充分考慮隱式信息的影響.Zhang等人[8]將地理、社交和興趣點分類信息分別建模，并采用混合算法融合不同的情景信息.上述模型的性能雖有所提高，但由于遭受嚴重的數據稀疏影響，推薦效果一般.為了緩解稀疏問題，Li等人[9]提出“兩步走”的框架，利用地理和社交信息為每個用戶學習一組待填充興趣點，通過矩陣填充的方式緩解稀疏影響.王崢等人[10]通過社交信息度量用戶興趣相似度，結合通過非負矩陣分解算法獲得的熟悉度預測用戶相似度，使其在稀疏數據情況下計算出更精確的相似度.上述模型有效地緩解了稀疏問題，但由于考慮的情景因素有限，造成對興趣點屬性的挖掘不夠全面.基于此，相關學者[11,12]通過納入流行度信息來改善推薦性能.Yuan等人[11]利用流行度信息度量興趣點被簽到的先驗概率，并將其與基于冪律分布的地理模型結合.吳燕等人[12]綜合考慮時間、地理和興趣點流行度的影響，利用最近鄰候選興趣點的方法刻畫用戶的地理偏好，將其與興趣點流行度相結合進行推薦.同時，用戶的偏好是動態變化的，為了更好地建模用戶的移動行為模式，時間信息被充分挖掘.Gao等人[13]考慮時間非統一性和連續性的影響，將其融入矩陣分解模型中，實現實時推薦的效果.此模型有效利用時間建模，但考慮因素單一，準確率極低.在此基礎上，文獻[14]考慮時間、地理和社交信息的影響，并將各情景信息建立在統一的框架中.文獻[11]考慮地理位置因素和興趣點流行度，并嵌入時間信息.這些模型有效地考慮用戶偏好的動態變化問題，但由于將時間劃分造成更嚴重的數據稀疏問題，使得推薦的準確率不佳.

綜上，本文綜合考慮數據稀疏和用戶興趣動態變化的問題，提出了一種基于均衡接近度增強時間的興趣點推薦模型.采用矩陣填充的方式緩解稀疏問題，并將時間信息與地理位置以及興趣點流行度結合，實現實時推薦的效果.

2.2 均衡接近度方法

均衡接近度方法由張岐山教授[15]提出，由傳統的灰關聯系數發展而來的一種計算復雜貧信息系統的兩向量之間的接近度的方法.

定義 1.(灰關聯度) 設X為灰關聯因子集，X0={x0(k)|k∈K}為參考列，Xi={xi(k)|k∈K}為比較列，i={1,2,3,…,m}，K={1,2,3,…,n}:

(1)

(2)

其中，γ(X0,Xi)為第i個比較列的灰關聯度；ζ為分辨系數.

定義 2.(均衡度) 設第i個比較列的關聯系數列用Ri表示：Ri={γ(x0(k),xi(k)),k∈K}，i={1,2,3,…,m}，K={1,2,3,…,n}:

(3)

(4)

其中，B(Ri)為第i個比較列的均衡度；lnn為最大熵.

定義 3.(均衡接近度) 設B(X0,Xi)為參考列X0和比較列Xi的均衡接近度：

B(X0,Xi)=B(Ri)×γ(X0,Xi)

(5)

均衡接近度方法改進了鄧聚龍教授[16]提出的灰關聯系數的方法，能有效克服灰關聯系數存在的信息損失和局部點關聯傾向的不足.文獻[17]將均衡接近度融入到各類算法中，用來預測數據間的相似性程度，減弱局部強關聯性造成的影響.文獻[18]將灰色預測模型引入到推薦系統，用來緩解數據稀疏性和相關性等問題.基于此，考慮根據時間段劃分簽到矩陣會使得數據更加稀疏，本文提出利用均衡接近度來計算每個時間段間的相似度，將其作為平滑因子，有效改進時間影響模型，提高推薦準確率.

3 融合時空的矩陣填充模型

對融合時空影響的矩陣填充建模是本文的第一階段，主要任務是通過建立時間影響模型和空間影響模型，為每個用戶學習出一組可能簽到的興趣點和時間，將其填充進矩陣，完成矩陣填充.

3.1 基于均衡接近度的時間影響

本文將時間按小時為單位分為24個時間段，為了獲得用戶間的時間行為相似性，利用余弦相似度來計算兩用戶的相似度，如下：

(6)

其中，ru,t,l和rv,t,l分別表示用戶u和v在t時刻對興趣點l的簽到次數.

采用式(6)計算用戶相似度存在兩個問題：一是將時間劃分導致數據更加稀疏；二是用戶在某些時間段無簽到行為會造成無意義的相似度計算.因此，本文采用時間平滑技術，修正原始的簽到次數.

給定用戶u，設Ru,t=(ru,t,l1,ru,t,l2,…,ru,t,ln)表示用戶u在時間段t內的簽到向量.考慮均衡接近度能有效處理復雜貧信息系統的數據，本文用式(5)的均衡接近度度量時間段ti和tj的相似度，如下：

(7)

取所有用戶的相似度的平均值作為兩時間段的相似度，如下：

(8)

利用上述的值去平滑簽到次數ru,t,l，如下：

(9)

將式(9)代入式(6)，得到平滑后的用戶相似度：

(10)

最終，本文將通過平滑技術得到用戶u在時間段t對興趣點l的簽到得分定義如下：

(11)

3.2 融合時間流行度的空間影響

本文考慮用戶更傾向于簽到距離自身近的興趣點，采用文獻[19]提出的冪律分布模型對地理建模，因此用戶在距離d-km遠的位置簽到的概率為：

PrG(d)=a·db

(12)

其中，a和b是冪律分布的參數.

設用戶u的歷史簽到記錄為Lu，li∈Lu.本文將用戶u對未簽到興趣點lj的訪問概率建模如下：

(13)

最終，根據貝葉斯規則，得到用戶u對未簽到興趣點l在空間上的簽到得分，如下：

(14)

其中，∝表示正向于；P(l)表示興趣點l被所有用戶簽到的先驗概率.

在此基礎上，本文考慮用戶對興趣點的簽到概率除了與空間距離相關，還與興趣點在某時間段的流行度相關，即興趣點的受歡迎程度會隨著時間不斷變化.為了驗證這一點，圖1繪制了從Foursquare數據集中選取兩個興趣點的時間流行度的情況.其中，興趣點l在時間段t內的流行度為t時間段上所有用戶對興趣點l的簽到次數與興趣點l在所有時間段上被簽到總次數的比值.從圖1明顯看出，每個興趣點的流行度隨時間變化很大，所以考慮將時間流行度納入模型極其重要.

因此，本文將時間流行度融入空間模型，如下：

(15)

其中，|Rl|表示興趣點l被簽到的次數；|Rl,t|表示興趣點l在時間段t內的被簽到次數；式(15)第一項表示興趣點l在時間段t內被簽到的概率，即興趣點l的時間流行度.第二項表示不考慮時間因素的興趣點l的被簽到的先驗概率；參數α作為時間流行度的權重系數.

圖1 興趣點的時間流行度分布Fig.1 Distribution of POI′time popularity

因此，本文將興趣點的時間流行度融入空間影響模型，利用式(15)獲得的Pt(l)調整式(14)的p(l)，得到用戶u在時間段t對興趣點l的簽到得分，如下：

(16)

3.3 統一框架

在3.1和3.2節中，本文分別建立了時間影響和空間影響模型，通過考慮時間、空間和流行度分別對其建模.本節綜合考慮上述兩種模型，獲得最終的矩陣填充模型，將得分最高的top-n個興趣點和相應的時間填充進原始矩陣.考慮兩種模型的度量方法有差異，整合前先采用min-max歸一化的方法對兩個分數進行處理，如下：

(17)

(18)

最終，得到用戶對興趣點的綜合分數如下：

(19)

根據上述結果，將分數最高的top-n個興趣點填充進原始矩陣，完成矩陣填充的過程.

4 融合時間的矩陣分解模型

矩陣分解技術在推薦算法中被廣泛使用，對通過矩陣填充后的新矩陣進行矩陣分解是本文的第二階段.在文獻[13]提出的LRT模型的基礎上，考慮受到數據稀疏問題的影響，本文對時間接近度的計算用均衡接近度方法改進，并采用加權矩陣分解算法將時間因素融入到模型中.

4.1 時間非統一性

(20)

考慮時間的非統一性，通過優化以下的損失函數來獲得特征偏好，如下：

(21)

同時，本文通過填充矩陣得到的新矩陣Pt包含三類興趣點，分別是用戶已簽到和未簽到的興趣點，以及待填充的興趣點.并采用加權矩陣分解算法得到偏好矩陣Pt的元素pu,t,j和權重矩陣Wt的元素wu,t,l，如下：

(22)

(23)

其中，θ表示用戶u以θ的概率簽到矩陣填充納入的興趣點；η是調整參數.

4.2 時間連續性

時間連續性指用戶在連續時間狀態具有更相似的簽到偏好.為了建模此屬性，本文利用均衡接近度計算時間接近度，并將此融入模型，得到損失函數如下：

(24)

ζu(t,t-1)=simti,tj

(25)

其中，simti，tj表示用均衡接近度計算的兩個時間段間的接近度.

4.3 統一模型

通過4.1和4.2節的分析，本節綜合考慮時間非統一性和時間連續性的影響.將式(21)與式(24)綜合，最終通過解決以下優化問題來獲得用戶的簽到偏好，如下：

(26)

其中，λt表示用來調整時間正則化的參數.

本文采用交替最小二乘(ALS)法優化上述損失函數，當計算一個隱特征向量時，固定其他變量.訓練過程中Ut，V的更新公式分別如下：

(27)

(28)

最終，通過優化學習獲得矩陣Ut與V，并將其代入式(20)獲得最終的偏好預測矩陣.

5 實驗結果與分析

5.1 數據集

本文實驗采用Foursquare[20]和Gowalla[11]兩個真實公開數據集來評估所提出模型的性能，其包含的相關內容如表1所示.為了評估算法的準確性，本文對數據進行預處理，分別去掉簽到次數低于10個興趣點的用戶和低于10個用戶簽到的興趣點.同時，本文實驗按8∶2的比例將數據隨機分成訓練集與測試集.

表1 數據集統計Table 1 Statistics of dataset

5.2 評價標準

本文采用推薦算法中被廣泛使用的兩個評價指標：準確率precision@k與召回率recall@k，這里的k表示推薦列表的長度.公式分別如下：

(29)

(30)

其中，R(u)表示本文算法計算訓練集后獲得的興趣點推薦列表；T(u)表示用戶在測試集上真實的興趣點簽到列表.

5.3 實驗結果分析

為了驗證本文提出的GB-TSP模型的推薦性能，選取了四種具有代表性的模型與本文提出的模型進行對比，具體描述如下：

1)LRT模型[13]：將時間因素融入到矩陣分解模型中.考慮用戶簽到行為具有時間差異性和連續性兩大特征，分別對其建模，最終將兩個模型統一融入到矩陣分解模型中.

2)ASMF模型[9]：采用“兩步走”的框架，首先利用用戶偏好和地理信息為每個用戶學習一組潛在興趣點，將其填充進矩陣.再將地理因素與通過矩陣分解算法獲得的偏好矩陣結合，完成推薦.

3)TACF模型[11]：首先將時間因素融入到基于用戶的協同過濾推薦框架中，再將興趣點流行度融入到基于冪律分布的地理模型中.最終生成一個融合時間和空間模型的統一模型，將簽到分數最高的興趣點推薦給用戶.

4)LRBTSP模型[12]：首先利用時間特征建模用戶對興趣點的簽到偏好，再結合流行度特征的影響，利用最近鄰候選興趣點方法建模空間模型.最終獲得一個綜合時間、空間和興趣點流行度特征的模型.

實驗1.參數分析

本節主要分析參數β對實驗結果的影響.在矩陣填充階段計算用戶對興趣點綜合得分Su,t,l的公式(19)中，β∈[0,1]用來表示調整時間和空間影響的權重參數，其值的大小最終決定了興趣點的得分及填充的結果.圖2、圖3為β取不同的值對Foursquare和Gowalla數據集中用戶的top-5推薦的準確率和召回率的影響.從圖2和圖3可以看出，Foursquare數據集對應的準確率和召回率在β=0.8達到最好效果，而Gowalla數據集則在β=0.7時達到最好效果.兩大數據集上的實驗結果表明了參數的最優值會受到數據集的影響，因此在選取參數值時應當依據不同數據集最優選取.同時，實驗還表明了用戶對興趣點的綜合得分中的時間影響權重高于空間影響，這主要因為用戶的偏好隨時間表現出不同的行為模式，且受到數據稀疏的影響，采用均衡接近度的方法在緩解稀疏問題上發揮有效作用，使得時間影響占較大權重.但空間因素決定了用戶在物理距離上的敏感性，對用戶選擇的興趣點起到重要作用，不容忽視.因此本文在之后利用Foursquare和Gowalla數據集進行對照實驗中，分別將β設置為0.8和0.7.

圖2 不同β值對準確率的影響Fig.2 Influence of parameter β on precision

圖3 不同β值對召回率的影響Fig.3 Influence of parameter β on recall

本實驗中，對于正則化參數λu，λv，λt根據文獻[13]中的最優參數分別設置為2，2，1；參數η和θ根據文獻[9]中的最優參數預設置為10和0.1，經實驗測試同樣適用于本文模型；參數α表示興趣點流行度的重要程度，在其他參數固定的情況下，實驗通過從0到1每增加0.1來獲取α值，通過測試不同α值下GB-TSP模型的準確率和召回率，發現α=0.5時的推薦性能最好.

實驗2.驗證矩陣填充的有效性

本節對第一階段提出的矩陣填充模型的有效性加以驗證，將待填充興趣點的數量s設置為100，通過實驗分析填充前后的推薦性能.實驗分別在Foursquare和Gowalla數據集上比較k=5、8、10、12、15和20時，GB-TSP模型在填充興趣點前后的準確率和召回率的變化情況，并在實驗中將算法的其他參數設為最優值.

圖4、圖5分別是本文模型在Foursquare和Gowalla數據集上，通過填充矩陣前后的準確率和召回率的變化情況.兩大數據集的實驗結果表明，經過第一階段的矩陣填充后的模型的推薦性能明顯優于未經過填充的模型的性能，且在Foursquare數據集上變化更大，說明矩陣填充有積極意義.矩陣填充能明顯提高推薦性能的原因主要是本文將時間劃分后會導致嚴重的數據稀疏問題，通過第一階段的矩陣填充能有效緩解數據稀疏性，同時運用均衡接近度方法能有效處理復雜貧信息系統的數據，對推薦性能的提高起到重要作用.

圖4 矩陣填充對GB-TSP模型準確率的影響Fig.4 Influence of matrix filling on precision of GB-TSP model

圖5 矩陣填充對GB-TSP模型召回率的影響Fig.5 Influence of matrix filling on recall of GB-TSP model

實驗3.不同推薦模型的性能對比

本部分實驗分別在Foursquare和Gowalla數據集的基礎上對五種推薦模型的性能進行了對比，并參照其他四種文獻設置的不同參數，使各模型都取得最佳性能，對比結果見圖6-圖9.圖6、圖7和圖8、圖9分別展示了各模型在Foursquare和Gowalla數據集的基礎上，興趣點推薦列表長度k=5、8、10、12、15和20時的推薦性能.從圖6-圖9中看出，GB-TSP模型在兩大數據集上的準確率和召回率均高于其他模型.隨著k的增加，各模型的準確率在逐漸下降與召回率在逐漸升高.這主要是向用戶推薦更多興趣點有利于用戶挖掘更多興趣點，由此促進用戶簽到次數的增加，對準確率和召回率產生一定影響.

圖6 Foursquare上不同推薦模型的準確率對比Fig.6 Precision of recommendation models on Foursquare

由圖6-圖9看出，本文所提出的GB-TSP模型的準確率和召回率明顯優于其他四種模型.其中，LRT模型推薦性能均低于其他模型，由于只考慮時間因素，且利用時間段劃分矩陣會造成更嚴重的稀疏問題.因此，LRT模型的推薦性能最低.ASMF模型考慮地理和社交因素，為用戶學習一組待填充興趣點，緩解數據稀疏性.因此，ASMF模型的推薦性能在Foursquare和Gowalla數據集上都明顯優于LRT.但ASMF模型未考慮時間因素，無法為用戶實現實時推薦.同前兩個模型相比，TACF模型有效融合了時間、地理和興趣點流行度，并將興趣點流行度融入基于冪律分布的地理模型中.因此，TACF的推薦效果有一定改善，且從圖8、圖9看出，TACF模型在Gowalla數據集上表現更好.與TACF模型不同，LRBTSP模型采用最近鄰候選興趣點的方法建模用戶的地理偏好，一定程度上提高了推薦精度，在Foursquare和Gowalla數據集均表現良好，但數據稀疏問題有待緩解.本文提出的模型有效改進了上述四種模型的不足.同LRT模型相比，GB-TSP模型考慮了更多的情景信息，并且通過矩陣填充緩解數據稀疏性.同ASMF相比，GB-TSP充分考慮時間的影響，解決了用戶興趣變化的問題.另外，GB-TSP在TACF和LRBTSP的基礎上考慮了矩陣填充階段，并將均衡接近度方法靈活地運用到時間影響模型中，有效緩解了數據稀疏的問題.同時，GB-TSP模型將時間影響充分地融入基于用戶的協同過濾算法和矩陣分解算法中，達到了實時推薦的效果.因此，GB-TSP模型的推薦效果均優于其他四種模型，表現出最高的準確率和召回率.

圖7 Foursquare上不同推薦模型的召回率對比Fig.7 Recall of recommendation models on Foursquare

圖8 Gowalla上不同推薦模型的準確率對比Fig.8 Precision of recommendation models on Gowalla

圖9 Gowalla上不同推薦模型的召回率對比Fig.9 Recall of recommendation models on Gowalla

6 結束語

對于興趣點推薦中的數據稀疏問題和用戶興趣的動態變化問題，本文提出了一種基于均衡接近度增強時間的興趣點推薦模型.該模型在基準模型的基礎上，利用均衡接近度方法增強時間接近度，將時間因素融入矩陣填充和矩陣分解兩個階段，實現實時推薦的效果.在Foursquare和Gowalla數據集上的實驗結果表明，本文提出的模型有效地整合了多種情景信息，與其他基準的推薦模型相比，該模型的準確率和召回率明顯提高.在接下來的工作中，將把異地推薦問題作為突破重點.同時，將深度學習融合到興趣點推薦中也是一個值得研究的方向.